2
$\begingroup$

The problem I need to prove is $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

I am trying to get the RHS equivalent to the LHS

So I change

$(p \lor q) \land (p \lor r)$

(using the Golden Rule)

(Golden Rule is- $p \land q \equiv p \equiv q \equiv p \lor q$)

$p \lor q \equiv p \lor r \equiv (p \lor q) \lor (p \lor r)$

?

?

and I know it ends like

$p \lor (q \equiv r \equiv (q \lor r))$

(the I reintroduce Golden Rule again)

$p \lor (q \land r)$

I am missing a few steps in the middle? but I'm not quite sure what

$\endgroup$
  • $\begingroup$ You can just construct a truth with tables with all possible combinations of truth values for $p$, $q$, $r$ as there are only $2^3 = 8$ possible combinations $\endgroup$ – freak_warrior Feb 8 '14 at 3:31
  • $\begingroup$ This is an exercise that needs to be solved with the Golden rule, sorry I forgot to mention that. Thanks though, that would make my life a lot easier if I could do that $\endgroup$ – user3255648 Feb 8 '14 at 3:37
  • $\begingroup$ You have a character that looks to me like three horizontal lines. Given the way you quote the Golden Rule I cannot figure out what the connective is. In the first line it should be $\leftrightarrow$ but in your parenthetical Golden Rule is that would not be correct. $\endgroup$ – Ross Millikan Feb 8 '14 at 4:04
  • $\begingroup$ the three horizontal lines is an equivalence, used with \equiv. It holds less tightly than a normal = sign, so parenthesis aren't used as frequent. Thanks for looking at it though $\endgroup$ – user3255648 Feb 8 '14 at 4:07
  • 1
    $\begingroup$ @RossMillikan - The Golden Rule in equational logic is an axiom. In order to "read it" correctly, you must take into account priority between connectives (highest is $\lnot$, lowest is $\equiv$) and the convention about omission of parentheses (re-introduce them from right to left). So the GR rule really is : $(((p \land q) \equiv p) \equiv q) \equiv (p \lor q)$. Ii is hard to believe, but if you check this version, you will find that is a tautology... $\endgroup$ – Mauro ALLEGRANZA Feb 9 '14 at 8:30
1
$\begingroup$

I'm using George Tourlakis, Mathematical Logic (2008); see page 42-43 for the rules and page 74 : 2.4.23 Theorem. (Distributivity: $\lor$ over $\land$ and $\land$ over $\lor$)

$(p \lor q ) \land (p \lor r)$

$p \lor q \lor p \lor r \equiv p \lor q \equiv p \lor r$

apply the Golden Rule (using Equanimity and Leibniz Merged, taht is a "derived rule"; see Tourlakis, page 57, 2.1.16 Theorem. (Eqn + Leib Merged) : $C[p := A], A \equiv B \vdash C[p := B]$; we call it "E+L")

NOTE. Due to the use of $p$ and $q$ in the formulas, I will describe the substitution in the “C-part” as “... sub-formula”

$p \lor p \lor q \lor r \equiv p \lor q \equiv p \lor r$

apply E+L, where the ‘C-part’ is $... \equiv p \lor q \equiv p \lor r$, using the “derived axiom” : $(((p \lor q) \lor p) \lor r) \equiv (((p \lor p) \lor q) \lor r)$ (proved with Associativity and Symmetry of $\lor$)

$p \lor q \lor r \equiv p \lor q \equiv p \lor r$

apply E+L where the ‘C-part’ is $...\lor q \lor r \equiv p \lor q \equiv p \lor r$, using the axiom Idempotency of $\lor$, i.e. $p \lor p \equiv p$

$p \lor q \lor r \equiv p \lor (q \equiv r)$

apply E+L where the ‘C-part’ is $p \lor q \lor r \equiv …$, using the axiom Distributivity of $\lor$ over $\equiv$, i.e. $p \lor (q \equiv r) \equiv p \lor q \equiv p \lor r$;

Now, read $p \lor q \lor r \equiv p \lor (q \equiv r)$ as $p \lor (q \lor r) \equiv p \lor (q \equiv r)$ and apply Distributivity of $\lor$ over $\equiv$, i.e. $p \lor (A \equiv B) \equiv p \lor A \equiv p \lor B$, obtaining :

$p \lor (q \lor r \equiv q \equiv r)$

Finally, apply E+L where the ‘C-part’ is $p \lor …$, using the Golden Rule, i.e. $(q \lor r \equiv q \equiv r) \equiv q \land r$:

$p \lor (q \land r)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.