# Propositional calculus – Can someone find a formal proof for the equivalence between these statements

logicpropositional-calculus

I have verified that these two statements are logically equivalent (via proof table), and since propositional calculus is sound and complete, there must also exist a step-by-step formal proof leading from one statement to the other and vice versa, using inference rules. And yet I cannot seem to find it! Please help me sleep at night!

(P2 ∧ ¬P0) ∨ (P0 ∧ P1),

(P0 → P1) ∧ (¬P0 → P2)

I have tried using a lot of rules of inference including
p → q ≡ ¬p ∨ q,
and deMorgan's laws to no avail…

#### Best Answer

There are likely prettier ways of going about it, but this was what I saw:

Starting with distribution of disjunction over conjunction ($$\vee$$ over $$\wedge$$) on the first expression yields $$[(P_2 \wedge \neg P_0) \vee P_0] \wedge [(P_2 \wedge \neg P_0) \vee P_1],$$ and distributing the other way yields $$(P_2 \vee P_0) \wedge (P_2 \vee P_1) \wedge (\neg P_0 \vee P_1).$$

Rewriting this as $$(P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1),$$ it should be clear that the second expression is a logical consequence of the first by simplification. (aka $$\wedge$$-elimination) Now we just need to show that the implication goes the other way, which is fairly simple.

$$1. \textbf{Assume}\ (P_0 \to P_1) \wedge (\neg P_0 \to P_2)$$
$$\ \ \ 2. P_0 \to P_1$$ ($$1,$$ simplification)
$$\ \ \ 3. \neg P_0 \to P_2$$ ($$1,$$ simplification)
$$\ \ \ 4. \neg P_2 \to P_0$$ ($$3,$$ contrapositive)
$$\ \ \ 5. \neg P_2 \to P_1$$ ($$2,4,$$ hypothetical syllogism)
$$\ \ \ 6. (P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1)$$ ($$1, 5, \wedge$$-introduction)
$$7. [(P_0 \to P_1) \wedge (\neg P_0 \to P_2)] \to [(P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1)]$$ ($$1,6,\to$$-introduction)

So, because the implications in both directions are tautologies, the material equivalence is a tautology and the statements are logically equivalent.