# Can this logic expression be further simplified?

I am learning logic at faculty and of course it causes a little bit of confusion sometimes.

$P \lor \neg Q \lor (P \land \neg R)$

Am I forgetting a law (probably yes)?

• hint : $P \lor (P \land \neg R) = P \land (1 \lor \neg R) = P$ Commented Sep 24, 2014 at 21:16
• I see no error yet @Yved Daoust :) Below more steps : $$P \lor (P \land \neg R) = (P\land 1 ) \lor (P \land \neg R)= P \land (1 \lor \neg R) = P$$ Commented Sep 24, 2014 at 21:24
• Yes that looks good ! Commented Sep 24, 2014 at 21:25
• yes associative law holds for both $\lor$ and $\land$ : $$(A\lor B)\lor C = A\lor (B \lor C)$$ $$(A\land B)\land C = A\land (B \land C)$$ Commented Sep 24, 2014 at 21:33

The solution in the comments is a smart human solution, which could be very difficult to find for a big general logical expression. But there is an algorithm that almost always works (to a point) but that sometimes is tedious:

1. Express all logical connectives expressed in XOR, AND and TRUE $: (+,\cdot,1)$
2. Use the algebraic laws (commutativity, associativity, distributivity, additive and multiplicative units, idempotence $X\cdot X=X$, and the additive inverse $X+X=0$) in Boolean rings to simplify almost like for numbers.
3. Eventually try to simplify by substitute back to other connectives as below.

\begin{array}{l|l} connective & substitute \\ \hline \neg X& 1+X\\ X\wedge Y& XY\\ X\vee Y& X+Y+XY\\ X\oplus Y&X+Y\\ X\Rightarrow Y&1+X+XY\\ X\Leftrightarrow Y&1+X+Y \end{array}

Your example (tedious): $(P\vee\neg Q)\vee(P\wedge\neg R)\equiv(P+(1+Q)+P(1+Q))\vee(P(1+R))\equiv$ $(P+1+Q+P+PQ)\vee(P+PR)\equiv(1+Q+PQ)\vee(P+PR)\equiv$ $(1+Q+PQ)+(P+PR)+(1+Q+PQ)(P+PR)\equiv\\1+Q+PQ+P+PR+P+PR+QP+QPR+PQP+PQPR\equiv$ $1+P+P+Q+PQ+PQ+PQ+PR+PR+QPR+QPR\equiv\\1+Q+PQ\equiv(\neg Q\vee P)\equiv(Q\Rightarrow P)$