Having the proposition:
$$
(\lnot p \rightarrow q) \land (\lnot p \rightarrow \lnot q)\land(p \rightarrow q) \land (p \rightarrow \lnot q)
$$
I want to prove this to be contradiction. So far I have that:
$$
p \rightarrow q \equiv \lnot p \lor q
$$
But now I am stuck because I want to proceed with the Distributive Law, but don't know how to apply it in my new situation:
$$
(p \lor q) \land (p \lor \lnot q) \land (\lnot p \lor q) \land (\lnot p \lor \lnot q)
$$
Prove Something is a Contradiction only by Logical Equivalencies
discrete mathematicslogicpropositional-calculus
Related Solutions
What we would like to prove is a conjunction, so it suffices to prove each conjunct separately and then glue them together at the end. This problem would probably be easier and more intuitive using proof by contradiction, but after talking with the asker, I will provide a direct proof.
$$\begin{array}{lr} 1. & (P \rightarrow Q)\wedge(Q \rightarrow R) & \text{Premise} \\ 2. & P \rightarrow Q &\text{Simplification, 1}\\ 3. & Q \rightarrow R & \text{Simplification, 1}\\ 4. & \neg{P} \vee Q & \text{Conditional Law, 2}\\ 5. & \neg{Q} \vee R & \text{Conditional Law, 3}\\ 6. & Q \vee \neg{Q} & \text{Tautology} \\ 7. & \neg{P} \vee R & \text{Constructive Dilemma, 4,5,6}\\ 8. & P \rightarrow R & \text{Conditional Law, 7}\\ 9. & (P \rightarrow Q) \vee (Q \rightarrow R) &\text{Addition, 2}\\ 10. & (Q \rightarrow P) \vee (Q \rightarrow R) &\text{Addition, 3}\\ 11. & (P \rightarrow Q) \vee (R \rightarrow Q) &\text{Addition, 2}\\ 12. & Q \vee \neg{Q} & \text{Tautology}\\ 13. & (Q \vee \neg{Q}) \vee (P \vee \neg{R}) & \text{Addidition, 12}\\ 14. & (\neg{Q} \vee P) \vee (\neg{R} \vee Q) & \text{Associative Law, 13}\\ 15. & (Q \rightarrow P) \vee (R \rightarrow Q) & \text{Conditional Law, 14}\\ 16. & \big((P \rightarrow Q) \vee (Q \rightarrow R)\big)\wedge \big((Q \rightarrow P) \vee (Q \rightarrow R)\big) & \text{Conjunction, 9,10}\\ 17. & \big((P \rightarrow Q) \vee (R \rightarrow Q)\big)\wedge \big((Q \rightarrow P) \vee (R \rightarrow Q)\big) & \text{Conjunction, 11,15}\\ 18. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R) & \text{Distributive Law, 16}\\ 19. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q) & \text{Distributive Law, 17}\\ 20. & \Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R)\Big) \wedge & \\ &\Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q)\Big) & \text{Conjunction, 18,19}\\ 21. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee \big((Q \rightarrow R) \wedge (R \rightarrow Q) \big) & \text{Distributive Law, 20}\\ 22. & (P \equiv Q) \vee (Q \equiv R) & \text{Definition of Biconditional, 21}\\ \therefore & (P \rightarrow R)\wedge \big((P \equiv Q) \vee (Q \equiv R)\big) & \text{Conjunction, 8,22} \end{array}$$
As desired.
Here are some useful but elementary equivalence principles:
Complement
$$P \lor \neg P \Leftrightarrow \top$$
$$P \land \neg P \Leftrightarrow \bot$$
Annihilation
$$P \lor \top \Leftrightarrow \top$$
$$P \land \bot \Leftrightarrow \bot$$
Identity
$$P \land \top \Leftrightarrow P$$
$$P \lor \bot \Leftrightarrow P$$
Idempotence
$$P \lor P = P$$
$$P \land P = P$$
Also, as you noticed, the whole big right terms does indeed not get you anywhere ... you need to work in the left term $\neg P \lor R$
So, starting a few lines from before you get 'stuck' (because indeed, you're just going in loops at that point) (and also throwing in some necessary parentheses):
$(\neg P \lor R) \land [\color{red}((\neg P \lor Q) \land (P \lor \neg Q)\color{red}) \lor \color{red}((\neg R \lor Q) \land (R \lor \neg Q)\color{red})] =$
$(\neg P \land [((\neg P \lor Q) \land (P \lor \neg Q)) \lor ((\neg R \lor Q) \land (R \lor \neg Q))]) \lor (R \land [((\neg P \lor Q) \land (P \lor \neg Q)) \lor ((\neg R \lor Q) \land (R \lor \neg Q))]) =$
$[\neg P \land ((\neg P \lor Q) \land (P \lor \neg Q))] \lor [\neg P \land ((\neg R \lor Q) \land (R \lor \neg Q))] \lor [R \land ((\neg P \lor Q) \land (P \lor \neg Q))] \lor [R \land ((\neg R \lor Q) \land (R \lor \neg Q))] =$
(dropping unncessary parentheses)
$[\neg P \land (\neg P \lor Q) \land (P \lor \neg Q)] \lor [\neg P \land (\neg R \lor Q) \land (R \lor \neg Q)] \lor [R \land (\neg P \lor Q) \land (P \lor \neg Q)] \lor [R \land (\neg R \lor Q) \land (R \lor \neg Q)]$
OK, now two handy laws are:
Absorption
$$P \land (P \lor Q) = P$$
Reduction
$$P \land (\neg P \lor Q) = P \land Q$$
Applying these, we get:
$[\neg P \land \neg Q] \lor [\neg P \land (\neg R \lor Q) \land (R \lor \neg Q)] \lor [R \land (\neg P \lor Q) \land (P \lor \neg Q)] \lor [R \land Q ]$
OK, and now 'unDistribute' the $\neg P $ and the $R$:
$= [\neg P \land (\neg Q \lor ((\neg R \lor Q) \land (R \lor \neg Q)))] \lor [R \land (((\neg P \lor Q) \land (P \lor \neg Q)) \lor Q) ]$
and now you can distribute the $\neg Q$ and the $Q$:
$= [\neg P \land (\neg Q \lor (\neg R \lor Q)) \land (\neg Q \lor (R \lor \neg Q))] \lor [R \land ((\neg P \lor Q) \lor Q) \land ((P \lor \neg Q) \lor Q) ] =$
(dropping unncessary parentheses)
$[\neg P \land (\neg Q \lor \neg R \lor Q) \land (\neg Q \lor R \lor \neg Q)] \lor [R \land (\neg P \lor Q \lor Q) \land (P \lor \neg Q \lor Q) ]$
And now you can use those simplification laws from the start of my post:
(Complement:)
$[\neg P \land (\neg R \lor \top) \land (R \lor \neg Q)] \lor [R \land (\neg P \lor Q) \land (P \lor \top) ]$
(Annihilation:)
$=[\neg P \land \top \land (R \lor \neg Q)] \lor [R \land (\neg P \lor Q) \land \top ]$
(Identity:)
$=[\neg P \land (R \lor \neg Q)] \lor [R \land (\neg P \lor Q)]$
(Distribution:)
$=(\neg P \land R) \lor (\neg P \land \neg Q) \lor (R \land \neg P) \lor (R \land Q)$
(Commutation:)
$=(\neg P \land R) \lor (\neg P \land \neg Q) \lor (\neg P \land R) \lor (R \land Q)$
(Idempotence:)
$=(\neg P \land R) \lor (\neg P \land \neg Q) \lor (R \land Q)$
(Distribution 2*2*2:)
$=(\neg P \lor \neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor \neg P \lor Q) \land (\neg P \lor \neg Q \lor Q) \land (R \lor \neg P \lor R) \land (R \lor \neg Q \lor R) \land (R \lor \neg P \lor Q) \land (R \lor \neg Q \lor Q)$
(Complement:)
$=(\neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor Q) \land (\neg P \lor \top) \land (\neg P \lor R) \land (\neg Q \lor R) \land (R \lor \neg P \lor Q) \land (R \lor \top)$
(Annihilation:)
$=(\neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor Q) \land \top \land (\neg P \lor R) \land (\neg Q \lor R) \land (R \lor \neg P \lor Q) \land \top$
(Identity:)
$=(\neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor Q) \land (\neg P \lor R) \land (\neg Q \lor R) \land (R \lor \neg P \lor Q) $
(two Absorptions and an Idempotence:)
$=(\neg P \lor R) \land (\neg P \lor Q) \land (\neg Q \lor R)$
Phew! Almost there ....
Now, use:
Adjacency
$$P = (P \lor Q) \land (P \lor \neg Q)$$
Applied to where we were:
$(\neg P \lor R) \land (\neg P \lor Q) \land (\neg Q \lor R)$
(Adjacency:)
$=(\neg P \lor R \lor Q) \land (\neg P \lor R \lor \neg Q) \land (\neg P \lor Q) \land (\neg Q \lor R)$
(Two Absorptions)
$(\neg P \lor Q) \land (\neg Q \lor R)$
.. and finally we're there! Sheesh!
Related Question
- Proof of distributivity of implication over implication
- Need to prove $(p \land q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.
- Simplifying the proposition $\Bigl(\bigl(P\lor Q\bigr)\land \lnot\bigr(\lnot P\land(\lnot Q\lor\lnot R)\bigl)\Bigr)$
- Natural Deduction Proof without Logical Equivalences
Best Answer
By the distributive rule, we have:
$$\begin{align}(p \lor q) \land (p \lor \lnot q) \land (\lnot p \lor q) \land (\lnot p \lor \lnot q)&\equiv [p \lor (q\land \lnot q)] \land [\lnot p \lor (q \land \lnot q)]\\ \\ &\equiv (p \lor \bot) \land (\lnot p \lor \bot)\\ \\ &\equiv (p \land \lnot p)\\ \\ &\equiv \bot\end{align}$$
Note that $\bot$ means "logically false," aka a "contradiction".