I have the following logical expression to solve/Simplify. Anyone able to help please??
$(P\land Q\land R)\lor (P\land\lnot Q\land R)\lor (P\land \lnot Q\land \lnot R)$
[Math] Simplifying a propositional formula
propositional-calculus
Related Solutions
You can think about it in this way: $(A\to B)\land(\neg A\to C)$ is a rule you're given, which tells you what happens when you know the truth value of $A$. If $A$ is true, then you must have $B$; if $A$ is false, you must have $C$. And since $A\lor\neg A$ is a tautology (always true), then either you have $A$ and $B$ or you have $\neg A$ and $C$, which we can write as $(A\land B)\lor(\neg\land C)$.
More formally: \begin{align}(A\to B)\land(\neg A\to C)&\equiv (\neg A\lor B)\land(A\lor C)\\&\equiv(\neg A\land A)\lor(\neg A\land C)\lor(B\land A)\lor(B\land C)\\&\equiv(\neg A\land C)\lor(B\land A)\lor(B\land C)\\&\equiv(\neg A\land C)\lor(B\land A)\end{align}
Some details on the above derivation:
- The first line is simply expressing $\to$ in terms of $\left\{\lor,\neg\right\}$.
- Next, we distribute the parentheses over the conjunction (you could actually break it into two steps, one distributing over the disjunction, the second over the conjunction, but I think it is clear enough that way).
- In the third line we remove the $(A\land\neg A)$ term, which is clearly a contradiction, so that it doesn't influence the truth value of the whole proposition.
- And the final step, as I explained in the first paragraph, is to notice that if we have $\neg A$, $C$ follows, and we have $A$, $B$ follows. Thus $(B\land C)$ doesn't contribute to the truth value of the whole proposition, since whenever it is true, one of $(\neg A\land C)$ or $(B\land A)$ is already true.
Finally, a deduction:
- $\vdash (A\to B)\land(\neg A\to C)$ --- Hypothesis
- $\vdash A\to B$ --- Simplification, 1
- $\vdash \neg A\to C$ --- Simplification, 1
- $\vdash A\lor\neg A$ --- Axiom 1 (tautology)
- $\vdash A$ --- Assumption [a]
- $\vdash B$ --- Modus Ponens, 2-5
- $\vdash A\land B$ --- Adjunction, 5-6
- $\vdash (A\land B)\lor(\neg A\land C)$ --- $\lor$-introduction, 7
- $\vdash\neg A$ --- Assumption [b]
- $\vdash C$ --- Modus Ponens, 3-8
- $\vdash \neg A\land C$ --- Adjunction, 8-9
- $\vdash (\neg A\land C)\lor(A\land B)$ --- $\lor$-introduction, 11
- $\vdash (A\land B)\lor(\neg A\land C)$ --- $\lor$-elimination, 4, discharging [a] and [b]
$$[(\color{blue}{p} \land \lnot q) \lor (\color{blue}{p} \land q)] \land q \equiv [\color{blue}{p} \land (\color{red}{{\lnot q \lor q}})] \land q\tag{distributivity}$$
$$ \equiv (\color{blue}{p} \land \color{red} \top) \land q$$
$$\equiv \color{blue}{p} \land q$$
That is, the distributive law declares that $$[p\land (\lnot q \lor q)] \equiv [(p \land \lnot q) \lor (p \land q)]$$ That means that it is the same law when we write it: $$[(p \land \lnot q) \lor (p \land q)] \equiv [p\land (\lnot q \lor q)]$$
Addendum
Best Answer
We proceed to employ the distributive laws of $\land$ and $\lor$ over one another, DeMorgan's law about negation, and the associativity of these operations.
Here it gets a bit technical:
$$\begin{align} &(P\land Q\land R)\lor (P\land\lnot Q\land R)\lor (P\land \lnot Q\land \lnot R) &\iff\\ &(P\land Q\land R)\lor (P\land \lnot Q\land R)\lor (P\land \lnot(Q\lor R))&\iff\\ &(P\land Q\land R)\lor (P\land \lnot(Q\lor\lnot R))\lor (P\land \lnot(Q\lor R))&\iff\\ &(P\land (Q\land R))\lor (P\land (\lnot(Q\lor\lnot R)\lor \lnot(Q\lor R)))&\iff\\ &P\land ((Q\land R)\lor (\lnot(Q\lor\lnot R)\lor \lnot(Q\lor R)))&\iff\\ &P\land ((Q\land R)\lor\lnot((Q\lor\lnot R)\land (Q\lor R)))&\iff\\ &P\land ((Q\land R)\lor\lnot(Q\lor (\lnot R\land R)))&\iff\\ &P\land ((Q\land R)\lor\lnot Q)&\iff\\ &P\land ((\lnot Q\lor Q)\land (\lnot Q\lor R))&\iff\\ &P\land (\lnot Q\lor R) \end{align}$$
This seems simplified enough.
Addendum: Another way to solve such problem (especially when number of variables is very low) is to write a very big truth table, in this case, 8 lines long.
Then you can look closely and see when the sentence is true, it will happen to be true when $P$ is true, and either $Q$ is false or $R$ is true, this means that the original sentence is equivalent to this very short one.
This method though is very hard to do when there are more than three variables, or when the original sentence is very very complicated.