# How to solve Distributivity of $\lor$ over $\land$

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

• 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 – freak_warrior Feb 8 '14 at 3:31
• 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 – user3255648 Feb 8 '14 at 3:37
• 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. – Ross Millikan Feb 8 '14 at 4:04
• 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 – user3255648 Feb 8 '14 at 4:07
• @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... – Mauro ALLEGRANZA Feb 9 '14 at 8:30

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