How to prove the distributive law for propositional logic without using truth tables or natural deduction.

Question

I haven't learnt natural deduction yet so I'm completely stuck on how to proceed. One tip I was given was to use the properties of negation but again, that's not really helping.

Answer 1

Use the definitions of the symbols.

---

$(P\wedge Q)\vee R$ means at least one from these cases: $P\wedge Q$ is true, or $R$ is true.

If $P\wedge Q$ is the case, then $P$ and $Q$ are both true. When $P$ is true, $P$ or $R$ is true; which means $P\vee R$ is true. Likewise when $Q$ is true, $Q\vee R$ is true. So having both $P$ and $Q$ means $(P\vee R)$ and $(Q\vee R)$ are true. Which means this case entails $(P\vee R)\wedge(Q\vee R)$.

If $R$ is the case, then we have $P$ or $R$; which means $P\vee R$. Likewise this case entails $Q\vee R$. Thus this case also entails $(P\vee R)\wedge(Q\vee R)$.

Therefore $(P\wedge Q)\vee R$ entails $(P\vee R)\wedge(Q\vee R)$.

---

Now show that $(P\vee R)\wedge(Q\vee R)$ entails $(P\wedge Q)\vee R$ .

Answer 2

You cannot prove this using only the rules as given, and here is why:

Use a classical two-value logic, interpret the $\neg$, $T$, and $C$ as normal, but interpret the $\lor$ as the classical $XOR$, and the $\land$ as the classical $\leftrightarrow$. Finally, define the $\Rightarrow$ and $\Leftrightarrow$ in accordance with the first and third equivalence principle respectively.

The Double Negation principle holds as normal, so the last equivalence principle holds. The two equivalence principles before that are easily verified as well. Also, since the classical $XOR$ and $\leftrightarrow$ are commutative, the newly interpreted $\lor$ and $\land$ are as well, so that takes care of principles 6 and 7. Then, since the $XOR$ and $\leftrightarrow$ are each other's dual, we have principles 4 and 5. Pricniples 1 and 3 hold by definition, and principle 2 is easily verified. So: with this interppretation, all of your given equivalence hold.

However, Distribution no longer holds, since the $XOR$ does not distribute over the $\leftrightarrow$. So, the Distribution priciple cannot be derived from the given $10$ equivalence principles.

Are you sure you have all of them listed?