1
$\begingroup$

I'm supposed to prove equivalence associativity using propositional logic axioms. My teacher insists that I use mathematical symbols. Half of the proof is given and I am to derive the second half.

The start is to prove:

$((p=q)=r) =(p = (q = r))$

The first half was done. Using axioms, $((p=q)=r)$ resolves to:

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

In order to prove that the other side is equivalent, I chose to start with the second side, $(p = (q = r))$, and try to reach the same line as above. Below are my steps, and I can almost see it, but I can't find an axiom that lets me simplify it further without going in another direction that takes me further from where I want to be. In other words, I have no idea if I'm on the right path and if so, what is the next step...

Here's my steps so far:

$\begin{align} (p = (q = r)) = (p\Rightarrow(q = r))\wedge((q=r)\Rightarrow p) \tag{Equality axiom} \end{align} $

Going after $(p\Rightarrow(q = r))$ side first, which will give half of the line from above I'm trying to get to:

$\begin{align} (p\Rightarrow(q = r)) &= (p \Rightarrow(q\Rightarrow r \wedge r\Rightarrow q))\\ &=(p \Rightarrow((\neg q\vee r) \wedge (\neg r\vee q))\\ &=(\neg p \vee ((\neg q \vee r)\wedge(\neg r \vee q)))\\ &=(\neg p \vee (\neg q \vee r))\wedge(\neg p\vee(\neg r \vee q)) \end{align} $

Now that last line looks very close to $(\neg p \vee \neg q \vee r) \wedge (\neg p \vee q \vee \neg r)$ except for the parentheses. Is there an axiom with the disjunction operator that allows me to ignore them? Or did I make a mistake and am I going in the totally wrong direction?

After thinking a bit more and drawing a truth table, I see that $ (p \vee (q \vee r))$ is equivalent to $(p \vee q \vee r)$.

Truth Table for associativity of OR

But what is the axiom for this?

$\endgroup$
1
$\begingroup$

Now that last line looks very close to $(¬p∨¬q∨r)∧(¬p∨q∨¬r)$ except for the parentheses. Is there an axiom with the disjunction operator that allows me to ignore them?

Because disjunction is associative you may dispense with the brackets in a dijunctive series without detracting from the meaning of the statement.

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

Likewise, because disjunction is commutative you may exchange the order of a disjunctive series and remain equivalent.

$$(¬p∨q∨¬r) \;\equiv\; (¬p∨¬r∨q)\qquad\text{et cetera}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.