Compound truth tables do more than compute values row by row. They allow us to decide whether a statement is always true, always false, or true only in some cases. This leads to tautologies, contradictions, and valid arguments. In this lesson, tautologies, contradictions, and valid arguments will be tested by final columns of truth tables. :::definition[Tautology] A compound statement is called a tautology if it is true for every possible truth-value assignment of its component statements. Thus, the final column of its truth table contains only $1$'s. ::: :::definition[Contradiction] A compound statement is called a contradiction if it is false for every possible truth-value assignment of its component statements. Thus, the final column of its truth table contains only $0$'s. ::: :::definition[Notation for Tautology] The symbol $T_0$ denotes any tautology. ::: :::definition[Notation for Contradiction] The symbol $F_0$ denotes any contradiction. ::: Use the classifier to focus on the final column of a truth table. Enter a string of truth values such as 1111, 0000, or 1011 and classify the pattern. A final column with only true values represents a tautology, while a final column with only false values represents a contradiction. Any mixture of true and false values means the statement is neither a tautology nor a contradiction. :::calculator[Final Column Classifier] ::: :::example[Tautology and Contradiction] Consider the compound statements $q\to(p\lor q)$ and $q\land(\neg q\land p)$. Their truth table is $$\begin{equation*} \begin{array}{c|c|c|c|c|c|c} p & q & p\lor q & q\to(p\lor q) & \neg q & \neg q\land p & q\land(\neg q\land p)\\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array} \end{equation*}$$ The final column of $q\to(p\lor q)$ contains only $1$'s, so it is a tautology. The final column of $q\land(\neg q\land p)$ contains only $0$'s, so it is a contradiction. ::: :::definition[Argument] An argument is a collection of statements consisting of premises and a conclusion. The premises are the given statements. The conclusion is the statement claimed to follow from the premises. ::: :::definition[Premises and Conclusion] Let $p_1,p_2,p_3,\ldots,p_n$ be premises, and let $q$ be the conclusion. The argument has the form $$\begin{equation*} p_1,\ p_2,\ p_3,\ldots,p_n\ \therefore\ q. \end{equation*}$$ ::: :::definition[Implication Form of an Argument] To test whether the conclusion follows from the premises, consider $$\begin{equation*} (p_1\land p_2\land p_3\land\cdots\land p_n)\to q. \end{equation*}$$ The hypothesis is the conjunction of all premises, and the conclusion is $q$. ::: :::definition[Valid Argument] An argument with premises $p_1,p_2,\ldots,p_n$ and conclusion $q$ is valid if $$\begin{equation*} (p_1\land p_2\land\cdots\land p_n)\to q \end{equation*}$$ is a tautology. Thus, whenever all premises are true, the conclusion must also be true. ::: :::definition[Generalized Conjunction] The statement $p_1\land p_2\land\cdots\land p_n$ is true if and only if every $p_i$ is true for $1\leq i\leq n$. ::: :::solved-problem Verify that $[q\to(p\to r)]\to[(q\to p)\to(q\to r)]$ is a tautology. ::: :::solution Construct intermediate columns for $p\to r$, $q\to(p\to r)$, $q\to p$, $q\to r$, and $(q\to p)\to(q\to r)$. The truth table is $$\begin{equation*} \begin{array}{c|c|c|c|c|c|c|c} p & q & r & p\to r & q\to(p\to r) & q\to p & q\to r & [q\to(p\to r)]\to[(q\to p)\to(q\to r)]\\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \end{equation*}$$ Since the final column contains only $1$'s, the given compound statement is a tautology. ::: :::solved-problem Identify which of the following are tautologies: (1) $\neg(p\land q)\to\neg q$. (2) $p\to(r\to q)$. (3) $(q\to p)\to r$. (4) $(r\to q)\to(q\to r)$. (5) $[q\land(q\to r)]\to r$. (6) $(p\lor q)\to q$. (7) $p\leftrightarrow(\neg q\lor r)$. (8) $[(p\to r)\land(r\to q)]\to(p\to q)$. ::: :::solution A statement is a tautology only when its final truth-table column contains only $1$'s. Testing the final columns gives: (1) not a tautology, because it is false when $p=0,q=1$. (2) not a tautology, because it is false when $p=1,r=1,q=0$. (3) not a tautology. (4) not a tautology, because it is false when $q=1,r=0$. (5) a tautology. (6) not a tautology, because it is false when $p=1,q=0$. (7) not a tautology. (8) a tautology. Hence, the tautologies are (5) and (8). ::: :::exercise Decide whether each statement is a tautology, contradiction, or neither: (1) $p\lor\neg p$. (2) $p\land\neg p$. (3) $p\to p$. (4) $p\leftrightarrow\neg p$. ::: :::answer (1) Tautology. (2) Contradiction. (3) Tautology. (4) Contradiction. ::: :::faq[Frequently Asked Questions] Q: Is every true statement a tautology? A: No. A tautology must be true for every truth-value assignment, not just true in one situation. Q: How is validity tested by truth tables? A: Form the implication from the conjunction of premises to the conclusion, then test whether it is a tautology. Q: Can a contradiction ever be true? A: No. Its final truth-table column contains only $0$'s. ::: :::call-to-action[Test Logical Forms] subtitle: Practise identifying tautologies and contradictions before applying truth tables to real situations. button: Next Lesson | /discrete-mathematics/mathematical-logic/basic-logical-connectives-and-truth-tables/truth-table-applications button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/basic-logical-connectives-and-truth-tables/parentheses-in-compound-truth-tables :::