[(π β¨ π) β§ (π β π) β§ (π β π)] β π β‘ T
asked by guest
MathBot Answer:
Logic Expression ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True \left(\left(\left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r\right) \leftrightarrow \text{True} ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True ( ( ( p or q ) and ( p implies r ) and ( q implies r ) ) implies r ) if and only if True \left(\left(\left(p \text{ or } q\right) \text{ and } \left(p \text{ implies } r\right) \text{ and } \left(q \text{ implies } r\right)\right) \text{ implies } r\right) \text{ if and only if } \text{True} ( ( ( p or q ) and ( p implies r ) and ( q implies r ) ) implies r ) if and only if True
Classification tautology
Truth Table
Legend
Symbol Read As β§ and β if and only if β implies β nand β nor Β¬ not β¨ or β¨ xor \begin{array}{c|c}\textbf{Symbol} & \textbf{Read As} \\ \hline β§ & \text{and} \\ \hline β & \text{if and only if} \\ \hline β & \text{implies} \\ \hline β & \text{nand} \\ \hline β & \text{nor} \\ \hline Β¬ & \text{not} \\ \hline β¨ & \text{or} \\ \hline β¨ & \text{xor} \end{array} Symbol β§ β β β β Β¬ β¨ β¨ β Read As and if and only if implies nand nor not or xor β β
p p p q q q r r r p β¨ q p \vee q p β¨ q p β r p \rightarrow r p β r q β r q \rightarrow r q β r ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) \left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right) ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r \left(\left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True \left(\left(\left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r\right) \leftrightarrow \text{True} ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1
Simplification ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True β‘ ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r Biconditional Simplification β‘ ( ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( q β r ) ) β r Conditional Equivalence β‘ ( ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( Β¬ q β¨ r ) ) β r Conditional Equivalence β‘ ( ( p β¨ q ) β§ ( r β¨ ( Β¬ p β§ Β¬ q ) ) ) β r Distributive Law β‘ ( ( p β¨ q ) β§ ( r β¨ Β¬ ( p β¨ q ) ) ) β r De Morganβs Law β‘ ( ( p β¨ q ) β§ r ) β r Redundancy Law (2) β‘ True Conjunctive Simplification \begin{gathered} \left(\left(\left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r\right) \leftrightarrow \text{True} & \equiv & \left(\left(p \vee q\right) \wedge \left(p \rightarrow r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r & \text{Biconditional Simplification} \\ & \equiv & \left(\left(p \vee q\right) \wedge \left(\neg p \vee r\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow r & \text{Conditional Equivalence} \\ & \equiv & \left(\left(p \vee q\right) \wedge \left(\neg p \vee r\right) \wedge \left(\neg q \vee r\right)\right) \rightarrow r & \text{Conditional Equivalence} \\ & \equiv & \left(\left(p \vee q\right) \wedge \left(r \vee \left(\neg p \wedge \neg q\right)\right)\right) \rightarrow r & \text{Distributive Law} \\ & \equiv & \left(\left(p \vee q\right) \wedge \left(r \vee \neg \left(p \vee q\right)\right)\right) \rightarrow r & \text{De Morgan's Law} \\ & \equiv & \left(\left(p \vee q\right) \wedge r\right) \rightarrow r & \text{Redundancy Law (2)} \\ & \equiv & \text{True} & \text{Conjunctive Simplification} \end{gathered} ( ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ) β True β β‘ β‘ β‘ β‘ β‘ β‘ β‘ β ( ( p β¨ q ) β§ ( p β r ) β§ ( q β r ) ) β r ( ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( q β r ) ) β r ( ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( Β¬ q β¨ r ) ) β r ( ( p β¨ q ) β§ ( r β¨ ( Β¬ p β§ Β¬ q ) ) ) β r ( ( p β¨ q ) β§ ( r β¨ Β¬ ( p β¨ q ) ) ) β r ( ( p β¨ q ) β§ r ) β r True β Biconditional Simplification Conditional Equivalence Conditional Equivalence Distributive Law De Morganβs Law Redundancy Law (2) Conjunctive Simplification β
Conjunctive Normal Form True \text{True} True
Note 1: These equivalences and tautologies are used to generate the above steps. Equivalence Absorption Law p β§ ( p β¨ q ) β‘ p p β¨ ( p β§ q ) β‘ p Biconditional Equivalence p β q β‘ ( p β¨ Β¬ q ) β§ ( Β¬ p β¨ q ) p β q β‘ ( p β§ q ) β¨ ( Β¬ p β§ Β¬ q ) Biconditional Simplification p β p β‘ True p β True β‘ p p β Β¬ p β‘ False p β False β‘ Β¬ p Complement Law p β§ Β¬ p β‘ False p β¨ Β¬ p β‘ True Conditional Equivalence p β q β‘ Β¬ p β¨ q Conditional Simplification p β p β‘ True p β True β‘ True p β False β‘ Β¬ p p β Β¬ p β‘ Β¬ p True β p β‘ p False β p β‘ True Β¬ p β p β‘ p Consensus Law ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( q β¨ r ) β‘ ( p β¨ q ) β§ ( Β¬ p β¨ r ) ( p β§ q ) β¨ ( Β¬ p β§ r ) β¨ ( q β§ r ) β‘ ( p β§ q ) β¨ ( Β¬ p β§ r ) De Morganβs Law Β¬ ( p β§ q ) β‘ Β¬ p β¨ Β¬ q Β¬ ( p β¨ q ) β‘ Β¬ p β§ Β¬ q Distributive Law p β§ ( q β¨ r ) β‘ ( p β§ q ) β¨ ( p β§ r ) p β¨ ( q β§ r ) β‘ ( p β¨ q ) β§ ( p β¨ r ) ( p β¨ q ) β§ ( r β¨ s ) β‘ ( p β§ r ) β¨ ( p β§ s ) β¨ ( q β§ r ) β¨ ( q β§ s ) ( p β§ q ) β¨ ( r β§ s ) β‘ ( p β¨ r ) β§ ( p β¨ s ) β§ ( q β¨ r ) β§ ( q β¨ s ) Domination Law p β¨ True β‘ True p β§ False β‘ False Double Negation Law Β¬ ( Β¬ p ) β‘ p Idempotent Law p β§ p β‘ p p β¨ p β‘ p Identity Law p β§ True β‘ p p β¨ False β‘ p NAND p β q β‘ Β¬ ( p β§ q ) Negation Law Β¬ True β‘ False Β¬ False β‘ True NOR p β q β‘ Β¬ ( p β¨ q ) Negation of Biconditional Equivalence Β¬ ( p β q ) β‘ ( p β¨ q ) β§ ( Β¬ p β¨ Β¬ q ) Β¬ ( p β q ) β‘ ( p β§ Β¬ q ) β¨ ( Β¬ p β§ q ) Negation of Conditional Equivalence Β¬ ( p β q ) β‘ p β§ Β¬ q Redundancy Law (1) ( p β¨ q ) β§ ( p β¨ Β¬ q ) β‘ p ( p β§ q ) β¨ ( p β§ Β¬ q ) β‘ p Redundancy Law (2) p β§ ( Β¬ p β¨ q ) β‘ p β§ q p β¨ ( Β¬ p β§ q ) β‘ p β¨ q XOR p β q β‘ ( p β¨ q ) β§ ( Β¬ p β¨ Β¬ q ) p β q β‘ ( p β§ Β¬ q ) β¨ ( Β¬ p β§ q ) XOR Simplification p β p β‘ False p β True β‘ Β¬ p p β Β¬ p β‘ True p β False β‘ p XNOR p β q β‘ Β¬ ( p β q ) \begin{array}{c|c}\textbf{Equivalence} \\ \hline \text{Absorption Law} & \begin{gathered} p \wedge \left(p \vee q\right) \equiv p \\ p \vee \left(p \wedge q\right) \equiv p \end{gathered} \\ \hline \text{Biconditional Equivalence} & \begin{gathered} p \leftrightarrow q \equiv \left(p \vee \neg q\right) \wedge \left(\neg p \vee q\right) \\ p \leftrightarrow q \equiv \left(p \wedge q\right) \vee \left(\neg p \wedge \neg q\right) \end{gathered} \\ \hline \text{Biconditional Simplification} & \begin{gathered} p \leftrightarrow p \equiv \text{True} & p \leftrightarrow \text{True} \equiv p \\ p \leftrightarrow \neg p \equiv \text{False} & p \leftrightarrow \text{False} \equiv \neg p \end{gathered} \\ \hline \text{Complement Law} & \begin{gathered} p \wedge \neg p \equiv \text{False} \\ p \vee \neg p \equiv \text{True} \end{gathered} \\ \hline \text{Conditional Equivalence} & p \rightarrow q \equiv \neg p \vee q \\ \hline \text{Conditional Simplification} & \begin{gathered} p \rightarrow p \equiv \text{True} & p \rightarrow \text{True} \equiv \text{True} & p \rightarrow \text{False} \equiv \neg p \\ p \rightarrow \neg p \equiv \neg p & \text{True} \rightarrow p \equiv p & \text{False} \rightarrow p \equiv \text{True} \\ \neg p \rightarrow p \equiv p\end{gathered} \\ \hline \text{Consensus Law} & \begin{gathered} \left(p \vee q\right) \wedge \left(\neg p \vee r\right) \wedge \left(q \vee r\right) \equiv \left(p \vee q\right) \wedge \left(\neg p \vee r\right) \\ \left(p \wedge q\right) \vee \left(\neg p \wedge r\right) \vee \left(q \wedge r\right) \equiv \left(p \wedge q\right) \vee \left(\neg p \wedge r\right) \end{gathered} \\ \hline \text{De Morgan's Law} & \begin{gathered} \neg \left(p \wedge q\right) \equiv \neg p \vee \neg q \\ \neg \left(p \vee q\right) \equiv \neg p \wedge \neg q \end{gathered} \\ \hline \text{Distributive Law} & \begin{gathered} p \wedge \left(q \vee r\right) \equiv \left(p \wedge q\right) \vee \left(p \wedge r\right) \\ p \vee \left(q \wedge r\right) \equiv \left(p \vee q\right) \wedge \left(p \vee r\right) \\ \left(p \vee q\right) \wedge \left(r \vee s\right) \equiv \left(p \wedge r\right) \vee \left(p \wedge s\right) \vee \left(q \wedge r\right) \vee \left(q \wedge s\right) \\ \left(p \wedge q\right) \vee \left(r \wedge s\right) \equiv \left(p \vee r\right) \wedge \left(p \vee s\right) \wedge \left(q \vee r\right) \wedge \left(q \vee s\right) \end{gathered} \\ \hline \text{Domination Law} & \begin{gathered} p \vee \text{True} \equiv \text{True} \\ p \wedge \text{False} \equiv \text{False} \end{gathered} \\ \hline \text{Double Negation Law} & \neg \left(\neg p\right) \equiv p \\ \hline \text{Idempotent Law} & \begin{gathered} p \wedge p \equiv p \\ p \vee p \equiv p \end{gathered} \\ \hline \text{Identity Law} & \begin{gathered} p \wedge \text{True} \equiv p \\ p \vee \text{False} \equiv p \end{gathered} \\ \hline \text{NAND} & p \uparrow q \equiv \neg \left(p \wedge q\right) \\ \hline \text{Negation Law} & \begin{gathered} \neg \text{True} \equiv \text{False} \\ \neg \text{False} \equiv \text{True} \end{gathered} \\ \hline \text{NOR} & p \downarrow q \equiv \neg \left(p \vee q\right) \\ \hline \text{Negation of Biconditional Equivalence} & \begin{gathered} \neg \left(p \leftrightarrow q\right) \equiv \left(p \vee q\right) \wedge \left(\neg p \vee \neg q\right) \\ \neg \left(p \leftrightarrow q\right) \equiv \left(p \wedge \neg q\right) \vee \left(\neg p \wedge q\right) \end{gathered} \\ \hline \text{Negation of Conditional Equivalence} & \neg \left(p \rightarrow q\right) \equiv p \wedge \neg q \\ \hline \text{Redundancy Law (1)} & \begin{gathered} \left(p \vee q\right) \wedge \left(p \vee \neg q\right) \equiv p \\ \left(p \wedge q\right) \vee \left(p \wedge \neg q\right) \equiv p \end{gathered} \\ \hline \text{Redundancy Law (2)} & \begin{gathered} p \wedge \left(\neg p \vee q\right) \equiv p \wedge q \\ p \vee \left(\neg p \wedge q\right) \equiv p \vee q \end{gathered} \\ \hline \text{XOR} & \begin{gathered} p \oplus q \equiv \left(p \vee q\right) \wedge \left(\neg p \vee \neg q\right) \\ p \oplus q \equiv \left(p \wedge \neg q\right) \vee \left(\neg p \wedge q\right) \end{gathered} \\ \hline \text{XOR Simplification} & \begin{gathered} p \oplus p \equiv \text{False} & p \oplus \text{True} \equiv \neg p \\ p \oplus \neg p \equiv \text{True} & p \oplus \text{False} \equiv p \end{gathered} \\ \hline \text{XNOR} & p \odot q \equiv \neg \left(p \oplus q\right) \end{array} Equivalence Absorption Law Biconditional Equivalence Biconditional Simplification Complement Law Conditional Equivalence Conditional Simplification Consensus Law De Morganβs Law Distributive Law Domination Law Double Negation Law Idempotent Law Identity Law NAND Negation Law NOR Negation of Biconditional Equivalence Negation of Conditional Equivalence Redundancy Law (1) Redundancy Law (2) XOR XOR Simplification XNOR β p β§ ( p β¨ q ) β‘ p p β¨ ( p β§ q ) β‘ p β p β q β‘ ( p β¨ Β¬ q ) β§ ( Β¬ p β¨ q ) p β q β‘ ( p β§ q ) β¨ ( Β¬ p β§ Β¬ q ) β p β p β‘ True p β Β¬ p β‘ False β p β True β‘ p p β False β‘ Β¬ p β p β§ Β¬ p β‘ False p β¨ Β¬ p β‘ True β p β q β‘ Β¬ p β¨ q p β p β‘ True p β Β¬ p β‘ Β¬ p Β¬ p β p β‘ p β p β True β‘ True True β p β‘ p β p β False β‘ Β¬ p False β p β‘ True β ( p β¨ q ) β§ ( Β¬ p β¨ r ) β§ ( q β¨ r ) β‘ ( p β¨ q ) β§ ( Β¬ p β¨ r ) ( p β§ q ) β¨ ( Β¬ p β§ r ) β¨ ( q β§ r ) β‘ ( p β§ q ) β¨ ( Β¬ p β§ r ) β Β¬ ( p β§ q ) β‘ Β¬ p β¨ Β¬ q Β¬ ( p β¨ q ) β‘ Β¬ p β§ Β¬ q β p β§ ( q β¨ r ) β‘ ( p β§ q ) β¨ ( p β§ r ) p β¨ ( q β§ r ) β‘ ( p β¨ q ) β§ ( p β¨ r ) ( p β¨ q ) β§ ( r β¨ s ) β‘ ( p β§ r ) β¨ ( p β§ s ) β¨ ( q β§ r ) β¨ ( q β§ s ) ( p β§ q ) β¨ ( r β§ s ) β‘ ( p β¨ r ) β§ ( p β¨ s ) β§ ( q β¨ r ) β§ ( q β¨ s ) β p β¨ True β‘ True p β§ False β‘ False β Β¬ ( Β¬ p ) β‘ p p β§ p β‘ p p β¨ p β‘ p β p β§ True β‘ p p β¨ False β‘ p β p β q β‘ Β¬ ( p β§ q ) Β¬ True β‘ False Β¬ False β‘ True β p β q β‘ Β¬ ( p β¨ q ) Β¬ ( p β q ) β‘ ( p β¨ q ) β§ ( Β¬ p β¨ Β¬ q ) Β¬ ( p β q ) β‘ ( p β§ Β¬ q ) β¨ ( Β¬ p β§ q ) β Β¬ ( p β q ) β‘ p β§ Β¬ q ( p β¨ q ) β§ ( p β¨ Β¬ q ) β‘ p ( p β§ q ) β¨ ( p β§ Β¬ q ) β‘ p β p β§ ( Β¬ p β¨ q ) β‘ p β§ q p β¨ ( Β¬ p β§ q ) β‘ p β¨ q β p β q β‘ ( p β¨ q ) β§ ( Β¬ p β¨ Β¬ q ) p β q β‘ ( p β§ Β¬ q ) β¨ ( Β¬ p β§ q ) β p β p β‘ False p β Β¬ p β‘ True β p β True β‘ Β¬ p p β False β‘ p β p β q β‘ Β¬ ( p β q ) β β Tautology Conjunctive Simplification ( p β§ q ) β p ( p β§ q ) β q Contradiction Β¬ ( p β§ Β¬ p ) Contrapositive ( p β q ) β ( Β¬ q β Β¬ p ) Disjunctive Addition p β ( p β¨ q ) q β ( p β¨ q ) Disjunctive Syllogism ( ( p β¨ q ) β§ Β¬ q ) β p ( ( p β¨ q ) β§ Β¬ p ) β q Hypothetical Syllogism ( ( p β q ) β§ ( q β r ) ) β ( p β r ) Modus Ponens ( p β§ ( p β q ) ) β q Modus Tollens ( Β¬ q β§ ( p β q ) ) β Β¬ p \begin{array}{c|c}\textbf{Tautology} \\ \hline \text{Conjunctive Simplification} & \begin{gathered} \left(p \wedge q\right) \rightarrow p \\ \left(p \wedge q\right) \rightarrow q \end{gathered} \\ \hline \text{Contradiction} & \neg \left(p \wedge \neg p\right) \\ \hline \text{Contrapositive} & \left(p \rightarrow q\right) \leftrightarrow \left(\neg q \rightarrow \neg p\right) \\ \hline \text{Disjunctive Addition} & \begin{gathered} p \rightarrow \left(p \vee q\right) \\ q \rightarrow \left(p \vee q\right) \end{gathered} \\ \hline \text{Disjunctive Syllogism} & \begin{gathered} \left(\left(p \vee q\right) \wedge \neg q\right) \rightarrow p \\ \left(\left(p \vee q\right) \wedge \neg p\right) \rightarrow q \end{gathered} \\ \hline \text{Hypothetical Syllogism} & \left(\left(p \rightarrow q\right) \wedge \left(q \rightarrow r\right)\right) \rightarrow \left(p \rightarrow r\right) \\ \hline \text{Modus Ponens} & \left(p \wedge \left(p \rightarrow q\right)\right) \rightarrow q \\ \hline \text{Modus Tollens} & \left(\neg q \wedge \left(p \rightarrow q\right)\right) \rightarrow \neg p \end{array} Tautology Conjunctive Simplification Contradiction Contrapositive Disjunctive Addition Disjunctive Syllogism Hypothetical Syllogism Modus Ponens Modus Tollens β ( p β§ q ) β p ( p β§ q ) β q β Β¬ ( p β§ Β¬ p ) ( p β q ) β ( Β¬ q β Β¬ p ) p β ( p β¨ q ) q β ( p β¨ q ) β ( ( p β¨ q ) β§ Β¬ q ) β p ( ( p β¨ q ) β§ Β¬ p ) β q β ( ( p β q ) β§ ( q β r ) ) β ( p β r ) ( p β§ ( p β q ) ) β q ( Β¬ q β§ ( p β q ) ) β Β¬ p β β
