Logical equivalence and the laws of logic begin with the idea that two compound statements may look different but behave exactly the same in every truth-value assignment. Having learned basic connectives and truth tables, we now use final truth-table columns to decide when two symbolic forms have the same meaning. Equivalent forms of compound statements are important because they allow implications, biconditionals, and exclusive-or statements to be rewritten using simpler connectives. In this lesson, equivalent forms of compound statements will be used to replace one logical expression by another without changing its truth value. :::definition[Logical Equivalence] Let $s_1$ and $s_2$ be two statements. Then $s_1$ and $s_2$ are said to be logically equivalent if they have the same truth value for every assignment of truth values to their primitive statements. We write $s_1\Leftrightarrow s_2$. ::: :::definition[Logical Equivalence by Truth Tables] Let $s_1$ and $s_2$ be compound statements formed from the same primitive statements. Then $s_1\Leftrightarrow s_2$ if and only if the final columns of their truth tables are identical. ::: Use the comparator to test logical equivalence by matching final truth-table columns. Choose a standard equivalence pair and read both expressions across all four assignments of $p$ and $q$. The two forms are equivalent exactly when the final columns agree in every row. This helps you see why an expression may be rewritten without changing its logical meaning. :::scientific-preview[Equivalence Column Comparator] ::: :::definition[Implication as Disjunction] For primitive statements $p$ and $q$, $$\begin{equation*} p\to q\Leftrightarrow \neg p\lor q. \end{equation*}$$ This shows that the implication connective can be eliminated by using negation and disjunction. ::: :::definition[Biconditional as Mutual Implication] For primitive statements $p$ and $q$, $$\begin{equation*} p\leftrightarrow q\Leftrightarrow (p\to q)\land(q\to p). \end{equation*}$$ Using implication as disjunction, $$\begin{equation*} p\leftrightarrow q\Leftrightarrow(\neg p\lor q)\land(\neg q\lor p). \end{equation*}$$ ::: :::definition[Exclusive-Or as Ordinary Connectives] For primitive statements $p$ and $q$, $$\begin{equation*} p\underline{\lor}q\Leftrightarrow(p\lor q)\land\neg(p\land q). \end{equation*}$$ The statement $p\underline{\lor}q$ is true exactly when one of $p$ and $q$ is true and the other is false. ::: :::theorem[Equivalent Forms of Exclusive-Or] Let $p$ and $q$ be primitive statements. Then $$\begin{equation*} p\underline{\lor}q\Leftrightarrow(p\land\neg q)\lor(\neg p\land q) \end{equation*}$$ and $$\begin{equation*} p\underline{\lor}q\Leftrightarrow\neg(p\leftrightarrow q). \end{equation*}$$ ::: :::proof Given that $p$ and $q$ are primitive statements. To prove that $p\underline{\lor}q\Leftrightarrow(p\land\neg q)\lor(\neg p\land q)$ and $p\underline{\lor}q\Leftrightarrow\neg(p\leftrightarrow q)$. The statement $p\underline{\lor}q$ is true exactly when exactly one of $p$ and $q$ is true. This occurs precisely in the two cases $p=1,q=0$ and $p=0,q=1$. Therefore, $$\begin{equation*} p\underline{\lor}q\Leftrightarrow(p\land\neg q)\lor(\neg p\land q). \end{equation*}$$ Again, $p\leftrightarrow q$ is true exactly when $p$ and $q$ have the same truth value. Therefore, $\neg(p\leftrightarrow q)$ is true exactly when $p$ and $q$ have different truth values. Hence, $$\begin{equation*} p\underline{\lor}q\Leftrightarrow\neg(p\leftrightarrow q). \end{equation*}$$ $\square$ ::: :::solved-problem Express $p\underline{\lor}q$ using only $\neg$, $\lor$, and $\land$. ::: :::solution Given that $p$ and $q$ are primitive statements. To express $p\underline{\lor}q$ using only $\neg$, $\lor$, and $\land$. By the definition of exclusive-or, $$\begin{equation*} p\underline{\lor}q\Leftrightarrow(p\lor q)\land\neg(p\land q). \end{equation*}$$ Using De Morgan's Law, $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q. \end{equation*}$$ Therefore, $$\begin{equation*} p\underline{\lor}q\Leftrightarrow(p\lor q)\land(\neg p\lor\neg q). \end{equation*}$$ Hence, the exclusive-or connective may be eliminated. ::: :::solved-problem Verify that $p\to q\Leftrightarrow\neg p\lor q$ by truth table. ::: :::solution Given that $p$ and $q$ are primitive statements. To verify that $p\to q\Leftrightarrow\neg p\lor q$, construct the truth table: $$\begin{equation*} \begin{array}{c|c|c|c|c} p&q&\neg p&p\to q&\neg p\lor q\\ \hline 1&1&0&1&1\\ 1&0&0&0&0\\ 0&1&1&1&1\\ 0&0&1&1&1 \end{array} \end{equation*}$$ The final columns are identical. Hence, $p\to q\Leftrightarrow\neg p\lor q$. ::: :::solved-problem Verify the biconditional chain $$\begin{equation*} [(p\leftrightarrow q)\land(q\leftrightarrow r)\land(r\leftrightarrow p)]\Leftrightarrow[(p\to q)\land(q\to r)\land(r\to p)]. \end{equation*}$$ ::: :::solution Given that $p$, $q$, and $r$ are primitive statements. The left side is true exactly when $p$, $q$, and $r$ all have the same truth value. The right side is false only when one of the cyclic implications has true hypothesis and false conclusion. In a cycle, avoiding all such false cases forces the truth values to be all $1$ or all $0$. Therefore, both compound statements are true under exactly the same assignments. Hence, the two compound statements are logically equivalent. ::: :::exercise Verify each equivalence: (1) $p\to(q\land r)\Leftrightarrow(p\to q)\land(p\to r)$. (2) $[(p\lor q)\to r]\Leftrightarrow[(p\to r)\land(q\to r)]$. (3) $p\underline{\lor}q\Leftrightarrow\neg(p\leftrightarrow q)$. ::: :::answer (1) Both sides are false exactly when $p=1$ and at least one of $q,r$ is $0$. (2) Both sides are false exactly when $r=0$ and at least one of $p,q$ is $1$. (3) Both sides are true exactly when $p$ and $q$ have different truth values. ::: :::faq[Frequently Asked Questions] Q: How is logical equivalence tested? A: Compare the final columns of the truth tables. Identical final columns give logical equivalence. Q: Why eliminate implication and biconditional? A: It helps simplify expressions and proves that some connectives can be built from others. Q: Is $s_1\Leftrightarrow s_2$ the same notation as $s_1\leftrightarrow s_2$? A: The first records equivalence of statement forms; the second is itself a compound statement. ::: :::call-to-action[Practise Equivalent Forms] subtitle: Rewrite implication, biconditional, and exclusive-or forms before studying De Morgan's Laws. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/de-morgans-laws button-ghost: Previous Section | /discrete-mathematics/mathematical-logic/basic-logical-connectives-and-truth-tables/truth-table-applications :::