Prove association with OR

Question

I need to proof association based on the formula below and I don't know how to even start

\begin{align} &(p\lor q) \lor r \vdash p \lor (q \lor r) \\ \end{align}

I feel like banging my head against a wall because it should be easy and looks obvious but I simply can't work it out right now and haven't found that example explained in hours of googling

Answer 1

I am not an expert in formal logic at all. I am not sure what you are allowed to assume. But if you are allowed to already assume 1) associativity with "and", and 2) that a statement always implies its contrapositive, then start with the consequent, and ...

$ \neg(p\vee (q\vee r)) \vdash \neg p \wedge \neg (q \vee r) \vdash \neg p \wedge (\neg q \wedge \neg r) \vdash ( \neg p \wedge \neg q) \wedge \neg r \vdash \neg(p \vee q)\wedge \neg r \vdash \neg((p\vee q) \vee r) $

So

$ \neg(p\vee (q\vee r)) \vdash \neg((p\vee q) \vee r) $

But

$ \neg a \vdash \neg b$ is always equivalent to $b \vdash a$, so

$ (p\vee q) \vee r \vdash p\vee (q\vee r) $

Answer 2

I think disjunction elimination is your friend here.

Namely, as a natural deduction, if you have as a starting assumption $(p \vee q) \vee r$, then you can have two subproofs, one of which that assume $p \vee q$, the other of which assumes $r$. If you can prove in each of those subproofs, under those assumptions, the desired consequence $p \vee (q \vee r)$, then you can use disjunction elimination on $(p \vee q) \vee r, p \vee q \to p \vee (q \vee r), r \to p \vee (q \vee r)$ to get $p \vee (q \vee r)$.

Answer 3

Alternative approach

You want to prove that LHS $\implies $ RHS, where

LHS is $~(p\lor q) \lor r $
and RHS is $~p \lor (q \lor r).$

You can break the LHS into cases.

$\underline{\text{Case 1}:~(p\lor q)}$
This may be split into subcases:

$\underline{\text{Case 1a}:~p}$
Here, $p \implies [p \lor (q\lor r)] =~$ RHS.

$\underline{\text{Case 1b}:~q}$
Here, $q \implies (q\lor r) \implies [p \lor (q\lor r)] =~$ RHS.

$\underline{\text{Case 2}:~r}$
Here, $r \implies (q\lor r) \implies [p \lor (q\lor r)] =~$ RHS.

Since the LHS is given to be true, one of the 3 possibilities, Case 1a, Case 1b, or Case 2 must be true. In all 3 cases, the RHS must be true.

Answer 4

You have the premise $(p\lor q)\lor r)$ which is a disjunction of disjunctions.

You seek to conclude $p\lor(q\lor r)$ which is also a disjunction of disjunctions.

Therefore your proof shall only use the rules of disjunction elimination and disjunction introduction.

$$\def\fitch#1#2{~~\begin{array}{|l}#1\\\hline#2\end{array}}\fitch{(p\lor q)\lor r}{\fitch{~}{\fitch{~}{~}\\\fitch{~}{~\\~}\\~}\\\fitch{~}{~\\~}\\p\lor(q\lor r)}$$