I am fairly new to natural deduction, and I don't seem to get it. I was given a task of proving through natural deduction associative property of logical conjunction and disjunction. So, I should prove this:
(A ∧ B) ∧ C ⇒ A ∧ (B ∧ C)
A ∧ (B ∧ C) ⇒ (A ∧ B) ∧ C
and
(A ∨ B) ∨ C ⇒ A ∨ (B ∨ C)
A ∨ (B ∨ C) ⇒ (A ∨ B) ∨ C
I would be really grateful if someone could explain to me what steps I should take in order to prove it, as I am new to logic and, unlike Hilbert-systems, don't really get natural deduction…
Best Answer
You use first conjunction eliminiation to from the premise show $A$, $B$ and $C$ respectively and then conjunction introduction to show the consequence. Then you use the deduction theorem.
For example:
$$\begin{align} (A\land B)\land C&\vdash (A\land B)\land C \\ (A\land B)\land C&\vdash (A\land B) \\ (A\land B)\land C&\vdash A \\ (A\land B)\land C&\vdash B \\ (A\land B)\land C&\vdash C \\ (A\land B)\land C&\vdash B\land C \\ (A\land B)\land C&\vdash A\land(B\land C) \\ &\vdash(A\land B)\land C \Rightarrow A\land(B\land C) \end{align}$$
For the disjunction case you'll use case analysis. Basically the key step is that you show that both $(A\lor B)\Rightarrow A\lor (B\lor C)$ and $C\Rightarrow A\lor (B\lor C)$. Then from the assumption $(A\lor B)\lor C$ you can conclude $A\lor (B\lor C)$. The first implication follows pretty directly from disjunction elimination while the second requires an extra step (from $C$ we can first conclude $B\lor C$ and in turn from that conclude $A\lor (B\lor C)$.