Q:

Prove that P (P) = (QA ~ Q)] is a tautology.

Accepted Solution

A:
Answer:The statement [tex]P \leftrightarrow [(\lnot P) \rightarrow (Q \land \lnot Q)][/tex] is a tautology.Step-by-step explanation:A tautology is a formula which is "always true" that is, it is true for every assignment of truth values to its simple components.To show that this statement is a tautology we are going to use a table of logical equivalences:[tex]P \leftrightarrow [(\lnot P) \rightarrow (Q \land \lnot Q)] \equiv[/tex][tex]\equiv (P \land [(\lnot P)\rightarrow (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [(\lnot P)\rightarrow (Q \land \lnot Q)])[/tex] by the logical equivalences involving bi-conditional statements[tex]\equiv (P \land [\lnot(\lnot P)\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [\lnot(\lnot P)\lor (Q \land \lnot Q)])[/tex] by the logical equivalences involving conditional statements[tex]\equiv (P \land [P\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [ P\lor (Q \land \lnot Q)])[/tex] by the Double negation law[tex]\equiv (P \land [P\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot P\land \lnot(Q \land \lnot Q))[/tex] by De Morgan's law[tex]\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot(Q \land \lnot Q))[/tex] by the Negation law[tex]\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot Q \lor \lnot(\lnot Q))[/tex] by De Morgan's law[tex]\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)[/tex] by the Double negation law[tex]\equiv (P \land P) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)[/tex] by the Identity law[tex]\equiv (P) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)[/tex] by the Idempotent law[tex]\equiv (P) \lor(\lnot P \land \lnot P\land  (Q\lor \lnot Q))[/tex] by the Commutative law[tex]\equiv (P) \lor(\lnot P \land \lnot P\land T)[/tex] by the Negation law[tex]\equiv (P) \lor(\lnot (P \lor P)\land T)[/tex] by De Morgan's law[tex]\equiv (P) \lor(\lnot (P)\land T)[/tex] by the Idempotent law[tex]\equiv (P \lor\lnot P) \land(P \lor T)[/tex] by the Distributive law[tex]\equiv (T) \land(P \lor T)[/tex] by the Negation law[tex]\equiv (T) \land(T)[/tex] by the Domination law[tex]\equiv T[/tex]