Having learned how truth values arise, we now organise them systematically. Truth tables for basic connectives list every possible truth-value assignment and show how each connective behaves. This method removes ambiguity from compound statements. In this lesson, truth tables for basic connectives will provide the computational foundation for testing tautologies, contradictions, and valid arguments. :::definition[Truth Table] A truth table lists the truth value of a compound statement for every possible assignment of truth values to its component statements. Truth tables provide a systematic way to analyze compound statements. ::: :::definition[Truth Table for Negation] Let $p$ be a statement. The truth table for negation is $$\begin{equation*} \begin{array}{c|c} p & \neg p\\ \hline 0 & 1\\ 1 & 0 \end{array} \end{equation*}$$ Given that negation reverses truth value, the truth values in the two columns are opposite. ::: :::definition[Truth Table for Basic Binary Connectives] Let $p$ and $q$ be statements. The truth table for the basic binary connectives is $$\begin{equation*} \begin{array}{c|c|c|c|c|c|c} p & q & p\land q & p\lor q & p\underline{\lor}q & p\to q & p\leftrightarrow q\\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \end{array} \end{equation*}$$ ::: The table should be read row by row. In each row, the values of $p$ and $q$ are fixed first, and then each compound statement is evaluated. Conjunction is true only in the final row. Inclusive disjunction is false only in the first row. Implication is false only in the row $p=1$, $q=0$, while biconditional is true exactly when the two entries match. :::definition[Truth Condition for Conjunction] The statement $p\land q$ is true if and only if both $p$ and $q$ are true. Therefore, $p\land q=1$ only when $p=1$ and $q=1$. ::: :::definition[Truth Condition for Disjunction] The statement $p\lor q$ is false if and only if both $p$ and $q$ are false. Therefore, $p\lor q=0$ only when $p=0$ and $q=0$. ::: :::definition[Truth Condition for Exclusive Disjunction] The statement $p\underline{\lor}q$ is true if and only if exactly one of $p$ and $q$ is true. Thus, $p\underline{\lor}q=1$ when $(p,q)=(1,0)$ or $(p,q)=(0,1)$. ::: :::definition[Truth Condition for Implication] The statement $p\to q$ is false if and only if $p$ is true and $q$ is false. Thus, $p\to q=0$ only when $p=1$ and $q=0$. In all other cases, $p\to q=1$. ::: :::definition[Truth Condition for Biconditional] The statement $p\leftrightarrow q$ is true if and only if $p$ and $q$ have the same truth value. Thus, $p\leftrightarrow q=1$ when $(p,q)=(0,0)$ or $(p,q)=(1,1)$. ::: :::theorem[Number of Rows in a Truth Table] If a compound statement contains $n$ distinct primitive statements, then its truth table has $2^n$ rows. ::: :::proof Given that a compound statement contains $n$ distinct primitive statements. To prove that its truth table has $2^n$ rows. Each primitive statement has exactly two possible truth values, namely $0$ and $1$. For the first primitive statement there are $2$ choices, for the second primitive statement there are $2$ choices, and this pattern continues through all $n$ primitive statements. Therefore, by the multiplication principle, the total number of truth-value assignments is $$\begin{equation*} 2\cdot 2\cdot 2\cdots 2=2^n. \end{equation*}$$ Hence, the truth table has $2^n$ rows. $\square$ ::: :::solved-problem Let $p,q,r,s,t$ be primitive statements. Find the number of rows in the truth table of $(p\land\neg q)\to[(r\lor s)\leftrightarrow t]$. ::: :::solution Let the primitive statements be $p,q,r,s,t$. There are five distinct primitive statements. Using the row formula, $$\begin{align*} 2^n&=2^5\\ &=32. \end{align*}$$ Hence, the truth table has $32$ rows. ::: :::solved-problem Determine all truth-value assignments that make $[(p\lor q)\land r]\to(s\land t)$ false. ::: :::solution Let the implication be false. An implication is false only when its hypothesis is true and its conclusion is false. Hence, $$\begin{align*} (p\lor q)\land r&=1,\\ s\land t&=0. \end{align*}$$ The first relation gives $r=1$ and at least one of $p,q$ equal to $1$. The second relation gives at least one of $s,t$ equal to $0$. Hence, the implication is false exactly for assignments satisfying $r=1$, $p=1$ or $q=1$, and $s=0$ or $t=0$. ::: Enter truth values $0$ or $1$ for $p$ and $q$, choose a connective, and compare the output with the truth table. Try the four rows $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$. Pay special attention to implication, because its false row is the most common source of mistakes. The checker is useful for verifying the truth tables for basic connectives without replacing the need to understand the rule. :::calculator[Basic Connective Truth Value Checker] @libraries: none ::: :::exercise Find the number of rows in truth tables containing (1) $3$ primitive statements, (2) $6$ primitive statements, and (3) $n$ primitive statements. ::: :::answer (1) $2^3=8$. (2) $2^6=64$. (3) $2^n$. ::: :::faq[Frequently Asked Questions] Q: Why does a truth table with $n$ primitive statements have $2^n$ rows? A: Each primitive statement has two possible truth values, and the choices multiply. Q: Which connective has the most surprising truth table? A: Implication often surprises students because $p\to q$ is false only in the row $p=1$, $q=0$. Q: Is exclusive or the same as inclusive or? A: No. Exclusive or is false when both statements are true. ::: :::call-to-action[Master the Basic Truth Tables] subtitle: Memorise the false rows and true rows of each connective before translating compound statements. button: Next Lesson | /discrete-mathematics/mathematical-logic/basic-logical-connectives-and-truth-tables/symbolic-translation-of-compound-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/basic-logical-connectives-and-truth-tables/open-sentences-and-truth-values :::