Truth Tables

Mathematics normally uses a two-valued logic: every statement is either true or false. You use truth tables to determine how the truth or falsity of a complicated statement depends on the truth or falsity of its components.

Complex, compound statements can be composed of simple statements linked together with logical connectives (also known as "logical operators") similarly to how algebraic operators like addition and subtraction are used in combination with numbers and variables in algebra. Conjunction (AND), disjunction (OR), negation (NOT), implication (IF...THEN), and biconditionals (IF AND ONLY IF), are all different types of connectives.

Independent, simple components of a logical statement are represented by either lowercase or capital letter variables. These variables are "independent" in that each variable can be either true or false independently of the others, and a truth table is a chart of all of the possibilities. Therefore, if there are \(N\) variables in a logical statement, there need to be \(2^N\) rows in the truth table in order to list out all combinations of each variable being either true (T) or false (F). For example, if there are three variables, A, B, and C, then the truth table with have 8 rows:

Two simple statements can be converted by the word "and" to form a compound statement called the conjunction of the original statements. We use the symbol \(\wedge \) to denote the conjunction. If \(p\) and \(q\) are two simple statements, then \(p \wedge q\) denotes the conjunction of \(p\) and \(q\) and it is read as "\(p\) and \(q\)." \(_\square\)

The truth table for the conjunction \(p \wedge q\) of two simple statements \(p\) and \(q\):

• The statement \(p \wedge q\) has the truth value T whenever both \(p\) and \(q\) have the truth value T.
• The statement \(p \wedge q\) has the truth value F whenever either \(p\) or \(q\) or both have the truth value F.

Two simple statements can be converted by the word "or" to form a compound statement called the disjunction of the original statements. We use the symbol \(\vee \) to denote the disjunction. If \(p\) and \(q\) are two simple statements, then \(p\vee q\) denotes the disjunction of \(p\) and \(q\) and it is read as "\(p\) or \(q\)." \(_\square\)

The truth table for the disjunction of two simple statements:

• The statement \(p\vee q\) has the truth value T whenever either \(p\) and \(q\) or both have the truth value T.
• The statement has the truth value F if both \(p\) and \(q\) have the truth value F.

An assertion that a statement fails or denial of a statement is called the negation of a statement. The negation of a statement is generally formed by introducing the word "no" at some proper place in the statement or by prefixing the statement with "it is not the case" or "it is false that." The negation of statement \(p\) is denoted by "\(\neg p.\)" \(_\square\)

Truth table for \(\neg p\):

Negation of Compound Statements

a) Negation of a conjunction
\(\hspace{1cm}\)The negation of a conjunction \(p \wedge q\) is the disjunction of the negation of \(p\) and the negation of \(q:\) \[\neg (p \wedge q) = {\neg p} \vee {\neg q}.\]

b) Negation of a disjunction
\(\hspace{1cm}\) The negation of a disjunction \(p \vee q\) is the conjunction of the negation of \(p\) and the negation of \(q:\) \[\neg (p \vee q) ={\neg p} \wedge {\neg q}.\]

c) Negation of a negation
\(\hspace{1cm}\) The negation of a negation of a statement is the statement itself: \[\neg (\neg p) \equiv p.\]

Two statements, when connected by the connective phrase "if... then," give a compound statement known as an implication or a conditional statement.

If \(p\) and \(q\) are two statements, then it is denoted by \(p \Rightarrow q\) and read as "\(p\) implies \(q\)." Here \(p\) is called the antecedent, and \(q\) the consequent. \(_\square\)

The truth table for the implication \(p \Rightarrow q\) of two simple statements \(p\) and \(q:\)

That is, \(p \Rightarrow q\) is false \(\iff\)(if and only if) \(p =\text{True}\) and \(q =\text{False}.\)

Mr. and Mrs. Tan have five children--Alfred, Brenda, Charles, Darius, Eric--who are assumed to be of different ages.

1. If Charles is not the oldest, then Alfred is.

2. If Eric is not the youngest, then Brenda is.

3. If Darius is not the oldest, then he is immediately younger than Charles.

4. If Alfred is older than Brenda, then Darius is the oldest.

Determine the order of birth of the five children given the above facts.

---

We let

• \(a\) be the proposition that Charles isn't the oldest;
• \(b\) be the proposition that Alfred is the oldest;
• \(c\) be the proposition that Eric isn't the youngest;
• \(d\) be the proposition that Brenda is the youngest;
• \(e\) be the proposition that Darius isn't the oldest;
• \(f\) be the proposition that Darius is just younger than Charles;
• \(g\) be the proposition that Alfred is older than Brenda.

From statement 1, \(a \rightarrow b\).
From statement 2, \(c \rightarrow d\).
From statement 3, \(e \rightarrow f\).
From statement 4, \(g \rightarrow \neg e\), where \(\neg e\) denotes the negation of \(e\).

Note that if Alfred is the oldest \((b)\), he is older than all his four siblings including Brenda, so \(b \rightarrow g\). Since \(g \rightarrow \neg e\) (statement 4), \(b \rightarrow \neg e\) by transitivity. But if we have \(b,\) which means Alfred is the oldest, it follows logically that \(e\) because Darius cannot be the oldest (only one person can be the oldest). Translating this, we have \(b \rightarrow e\).

Hence, \((b \rightarrow e) \wedge (b \rightarrow \neg e) = (\neg b \vee e) \wedge (\neg b \vee \neg e) = \neg b \vee (e \wedge \neg e) = \neg b \vee C = \neg b,\) where \(C\) denotes a contradiction. The only possible conclusion is \(\neg b\), where Alfred isn't the oldest. From statement 1, \(a \rightarrow b\), so by modus tollens, \(\neg b \rightarrow \neg a\). Hence Charles is the oldest.

Note that by pure logic, \(\neg a \rightarrow e\), where Charles being the oldest means Darius cannot be the oldest. From statement 4, \(g \rightarrow \neg e\), so by modus tollens, \(e = \neg(\neg e) \rightarrow \neg g\). From statement 3, \(e \rightarrow f\), so by modus ponens, our deduction \(e\) leads to another deduction \(f\). With \(f\), since Charles is the oldest, Darius must be the second oldest.

Since \(g\) means Alfred is older than Brenda, \(\neg g\) means Alfred is younger than Brenda since they can't be of the same age. Since there is someone younger than Brenda, she cannot be the youngest, so we have \(\neg d\). Since \(c \rightarrow d\) from statement 2, by modus tollens, \(\neg d \rightarrow \neg c\). Hence Eric is the youngest.

Considering all the deductions in bold, the only possible order of birth is Charles, Darius, Brenda, Alfred, Eric. \(_\square\)

Biconditional logic is a way of connecting two statements, \(p\) and \(q\), logically by saying, "Statement \(p\) holds if and only if statement \(q\) holds." In mathematics, "if and only if" is often shortened to "iff" and the statement above can be written as

\[p \equiv q.\]

The truth table for biconditional logic is as follows:

\[ \begin{align} {\color{Blue} \textbf{p}} &&{\color{Blue} \textbf{q}} &&{\color{Blue} p \equiv q} \\ \text{T} &&\text{T} &&\text{T} \\ \text{T} &&\text{F} &&\text{F} \\ \text{F} &&\text{T} &&\text{F} \\ \text{F} &&\text{F} &&\text{T} \end{align} \]

This can be interpreted by considering the following statement:

I go for a run if and only if it is Saturday. This combines both of the following:

• If it is Saturday, I go for a run.
• If I go for a run, it will be a Saturday. (Or "I only run on Saturdays.")

These are consistent only when the two statements "I go for a run today" and "It is Saturday" are both true or both false, as indicated by the above table.

Truth tables are often used in conjunction with logic gates. A few common examples are the following:

• Inverter
• Buffer
• AND
• OR
• NAND
• NOR
• XOR
• XNOR

For example, the truth table for the AND gate OUT = A & B is given as follows:

\[ \begin{align} {\color{Blue} \textbf{A}} &&{\color{Blue} \textbf{B}} &&{\color{Blue} \textbf{OUT}} \\ \text{0} &&\text{0} &&0 \\ \text{0} &&\text{1} &&0 \\ \text{1} &&\text{0} &&0 \\ \text{1} &&\text{1} &&1 \\ \end{align} \]

The truth table for the XOR gate OUT \(= A \oplus B\) is given as follows:

\[ \begin{align} {\color{Blue} \textbf{A}} &&{\color{Blue} \textbf{B}} &&{\color{Blue} \textbf{OUT}} \\ \text{0} &&\text{0} &&0 \\ \text{0} &&\text{1} &&1 \\ \text{1} &&\text{0} &&1 \\ \text{1} &&\text{1} &&0 \\ \end{align} \]

ALWAYS REMEMBER THE GOLDEN RULE: "And before or"

When combining arguments, the truth tables follow the same patterns. It is simplest but not always best to solve these by breaking them down into small componentized truth tables.

\((p \rightarrow q ) \wedge (q \vee p)\)

p \rightarrow q ||p||row 1 col 2||q|| ||row 2 col 1||row 2 col 2||row 2 col 1||row 2 col 2||

• Logic Gates

• Propositional Logic