Math Problem Solver

Logic Expression
Symbol: $\left(\neg q \wedge \left(p \rightarrow q\right)\right) \rightarrow \neg p$
Text: $\left(\text{not } q \text{ and } \left(p \text{ implies } q\right)\right) \text{ implies } \text{not } p$

Classification tautology

Truth Table

Legend

Simplification$$\begin{gathered} \text{Modus Tollens} \\ \begin{gathered} \left(\neg q \wedge \left(p \rightarrow q\right)\right) \rightarrow \neg p & \equiv & \left(\neg q \wedge \left(\neg p \vee q\right)\right) \rightarrow \neg p & \text{Conditional Equivalence} \\ & \equiv & \left(\neg q \wedge \neg p\right) \rightarrow \neg p & \text{Redundancy Law (2)} \\ & \equiv & \text{True} & \text{Conjunctive Simplification} \end{gathered} \end{gathered}$$ Note: Solution may not be as simplified as possible.

Conjunctive Normal Form$$\text{True}$$

Note 1: These equivalences and tautologies are used to generate the above steps.
Note 2: Two logical statements are logically equivalent if they always produce the same truth value. Consequently, p ≡ q is same as saying p ↔ q is a tautology. $$\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}$$ $$\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}$$