1

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$ – AgentS Sep 24 '14 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$$ – AgentS Sep 24 '14 at 21:24
  • Yes that looks good ! – AgentS Sep 24 '14 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)$$ – AgentS Sep 24 '14 at 21:33

1 Answers1

3

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)$

Lehs
  • 13,791
  • 4
  • 25
  • 77
  • 1
    These polynomials used for Boolean expressions are sometimes called Zhegalkin polynomials: http://en.wikipedia.org/wiki/Zhegalkin_polynomial – paw88789 Oct 05 '14 at 10:37