Β¬[( π βπ) β¨ π ] β [(Β¬ πβ Β¬ π) β§π]
asked by guest
MathBot Answer:
Logic Expression Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) \neg \left(\left(r \rightarrow r\right) \vee q\right) \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) not ( ( r implies r ) or q ) implies ( ( not q implies not r ) and r ) \text{not} \left(\left(r \text{ implies } r\right) \text{ or } q\right) \text{ implies } \left(\left(\text{not } q \text{ implies } \text{not } r\right) \text{ and } r\right) not ( ( r implies r ) or q ) implies ( ( not q implies not r ) and r )
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 β β
r r r q q q r β r r \rightarrow r r β r ( r β r ) β¨ q \left(r \rightarrow r\right) \vee q ( r β r ) β¨ q Β¬ ( ( r β r ) β¨ q ) \neg \left(\left(r \rightarrow r\right) \vee q\right) Β¬ ( ( r β r ) β¨ q ) Β¬ q \neg q Β¬ q Β¬ r \neg r Β¬ r Β¬ q β Β¬ r \neg q \rightarrow \neg r Β¬ q β Β¬ r ( Β¬ q β Β¬ r ) β§ r \left(\neg q \rightarrow \neg r\right) \wedge r ( Β¬ q β Β¬ r ) β§ r Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) \neg \left(\left(r \rightarrow r\right) \vee q\right) \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1
Simplification Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) β‘ Β¬ ( True β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) Conditional Simplification β‘ Β¬ True β ( ( Β¬ q β Β¬ r ) β§ r ) Domination Law β‘ False β ( ( Β¬ q β Β¬ r ) β§ r ) Negation Law β‘ True Conditional Simplification \begin{gathered} \neg \left(\left(r \rightarrow r\right) \vee q\right) \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) & \equiv & \neg \left(\text{True} \vee q\right) \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) & \text{Conditional Simplification} \\ & \equiv & \neg \text{True} \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) & \text{Domination Law} \\ & \equiv & \text{False} \rightarrow \left(\left(\neg q \rightarrow \neg r\right) \wedge r\right) & \text{Negation Law} \\ & \equiv & \text{True} & \text{Conditional Simplification} \end{gathered} Β¬ ( ( r β r ) β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) β β‘ β‘ β‘ β‘ β Β¬ ( True β¨ q ) β ( ( Β¬ q β Β¬ r ) β§ r ) Β¬ True β ( ( Β¬ q β Β¬ r ) β§ r ) False β ( ( Β¬ q β Β¬ r ) β§ r ) True β Conditional Simplification Domination Law Negation Law Conditional 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 β β
