Associative property proof for conjunction and disjunction in natural deduction

Question

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...

Answer 1

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

Answer 2

For the first two problems, the conjunction-elimination rule(s) allow you to start with the conjunction and then break it down into the letters. Then you put the letters into some formulas to get to the right-hand side of the arrow.

For the second two, you can make assumptions which correspond to the proper subformulas of the disjunction. Note you can arbitrarily make as many assumptions as you like in natural deduction, so long as you keep track of the scope of each assumption. A proper subformula is a formula S which lies within a formula F such that the number of symbols of S is less than the number of symbols of F (every 'A' in a different position is a different formula in this definition). Since you can make always make more assumptions in the context of natural deduction, you can make the assumptions slowly as if you were breaking the disjunctions down into it's subformulas. Then using the disjunction-introduction rules you can reach the desired conclusion. Then using conditonal-introduction you can show that hypotheses implied the conclusion allowing you to use disjunction-elimination to produce the right-hand side of the arrow.