Math Problem Solver

Logic Expression
Symbol: $\left(\left(P \rightarrow Q\right) \wedge \left(R \rightarrow Q\right)\right) \leftrightarrow \left(\left(P \vee R\right) \rightarrow Q\right)$
Text: $\left(\left(P \text{ implies } Q\right) \text{ and } \left(R \text{ implies } Q\right)\right) \text{ if and only if } \left(\left(P \text{ or } R\right) \text{ implies } Q\right)$

Classification tautology

Truth Table

Legend

Simplification$$\begin{gathered} \left(\left(P \rightarrow Q\right) \wedge \left(R \rightarrow Q\right)\right) \leftrightarrow \left(\left(P \vee R\right) \rightarrow Q\right) & \equiv & \left(\left(\neg P \vee Q\right) \wedge \left(R \rightarrow Q\right)\right) \leftrightarrow \left(\left(P \vee R\right) \rightarrow Q\right) & \text{Conditional Equivalence} \\ & \equiv & \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \leftrightarrow \left(\left(P \vee R\right) \rightarrow Q\right) & \text{Conditional Equivalence} \\ & \equiv & \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \leftrightarrow \left(\neg \left(P \vee R\right) \vee Q\right) & \text{Conditional Equivalence} \\ & \equiv & \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \leftrightarrow \left(\left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \neg \left(\left(\neg P \wedge \neg R\right) \vee Q\right)\right) \wedge \left(\neg \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{Biconditional Equivalence} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg \left(\neg P \wedge \neg R\right) \wedge \neg Q\right)\right) \wedge \left(\neg \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg \left(\neg \left(P \vee R\right)\right) \wedge \neg Q\right)\right) \wedge \left(\neg \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\neg \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{Double Negation Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\neg \left(\neg P \vee Q\right) \vee \neg \left(\neg R \vee Q\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\left(\neg \left(\neg P\right) \wedge \neg Q\right) \vee \neg \left(\neg R \vee Q\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\left(P \wedge \neg Q\right) \vee \neg \left(\neg R \vee Q\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{Double Negation Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\left(P \wedge \neg Q\right) \vee \left(\neg \left(\neg R\right) \wedge \neg Q\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{De Morgan's Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\left(P \wedge \neg Q\right) \vee \left(R \wedge \neg Q\right) \vee \left(\neg P \wedge \neg R\right) \vee Q\right) & \text{Double Negation Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\left(P \wedge \neg Q\right) \vee Q \vee \left(R \wedge \neg Q\right) \vee \left(\neg P \wedge \neg R\right)\right) & \text{Commutative Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(P \vee Q \vee \left(R \wedge \neg Q\right) \vee \left(\neg P \wedge \neg R\right)\right) & \text{Redundancy Law (2)} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(P \vee Q \vee R \vee \left(\neg P \wedge \neg R\right)\right) & \text{Redundancy Law (2)} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(P \vee Q \vee R \vee \neg P\right) & \text{Redundancy Law (2)} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(P \vee \neg P \vee Q \vee R\right) & \text{Commutative Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \left(\text{True} \vee Q \vee R\right) & \text{Complement Law} \\ & \equiv & \left(\left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right)\right) \wedge \text{True} & \text{Domination Law} \\ & \equiv & \left(\left(\neg P \vee Q\right) \wedge \left(\neg R \vee Q\right)\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right) & \text{Identity Law} \\ & \equiv & Q \vee \left(\neg P \wedge \neg R\right) \vee \left(\left(P \vee R\right) \wedge \neg Q\right) & \text{Distributive Law} \\ & \equiv & Q \vee \left(\left(P \vee R\right) \wedge \neg Q\right) \vee \left(\neg P \wedge \neg R\right) & \text{Commutative Law} \\ & \equiv & Q \vee P \vee R \vee \left(\neg P \wedge \neg R\right) & \text{Redundancy Law (2)} \\ & \equiv & Q \vee P \vee R \vee \neg P & \text{Redundancy Law (2)} \\ & \equiv & Q \vee P \vee \neg P \vee R & \text{Commutative Law} \\ & \equiv & Q \vee \text{True} \vee R & \text{Complement Law} \\ & \equiv & \text{True} & \text{Domination Law} \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}$$