Propositional Logic and Truth Tables
Propositional Logic and Truth Tables is a basic part of mathematical reasoning. It helps us decide whether statements are true or false, and it gives us a clear way to analyze compound statements built from simpler ones.
In mathematics, logic is important because proofs, definitions, and arguments all depend on correct reasoning. Truth tables are one of the easiest and most reliable tools for checking the value of a logical statement.
In this lesson, you will learn what propositions are, how logical operators work, and how to build and use truth tables for compound statements.
1. What is a proposition?
A proposition is a statement that is either true or false, but not both.
- “2 is an even number” is a proposition. It is true.
- “7 > 10” is a proposition. It is false.
- “What time is it?” is not a proposition because it is a question.
- “Close the door” is not a proposition because it is a command.
We usually use letters such as \(p\), \(q\), and \(r\) to represent propositions.
For example:
- \(p\): “It is raining.”
- \(q\): “The ground is wet.”
2. Logical operators
Compound statements are formed by joining simpler propositions using logical operators. The main operators you need to know are negation, conjunction, disjunction, implication, and biconditional.
(a) Negation
The negation of \(p\) is written as \(\neg p\) and means “not \(p\).”
- If \(p\) is true, then \(\neg p\) is false.
- If \(p\) is false, then \(\neg p\) is true.
Example:
- \(p\): “5 is positive.”
- \(\neg p\): “5 is not positive.”
(b) Conjunction
The conjunction of \(p\) and \(q\) is written as \(p \land q\) and means “\(p\) and \(q\).”
A conjunction is true only when both parts are true.
(c) Disjunction
The disjunction of \(p\) and \(q\) is written as \(p \lor q\) and means “\(p\) or \(q\).”
In mathematics, “or” usually means inclusive or. That means \(p \lor q\) is true when at least one of \(p\) or \(q\) is true, including when both are true.
(d) Implication
The implication from \(p\) to \(q\) is written as \(p \to q\) and means “if \(p\), then \(q\).”
This is often the most confusing operator at first. The statement \(p \to q\) is false only when \(p\) is true and \(q\) is false. In all other cases, it is true.
(e) Biconditional
The biconditional is written as \(p \leftrightarrow q\) and means “\(p\) if and only if \(q\).”
This statement is true when \(p\) and \(q\) have the same truth value, meaning both are true or both are false.
3. Basic truth tables
A truth table lists all possible truth values of propositions and shows the truth value of a compound statement for each case.
For two propositions \(p\) and \(q\), there are four possible combinations:
$$ \begin{array}{c|c} p & q \\\hline T & T \\ T & F \\ F & T \\ F & F \end{array} $$
Now let us look at the truth tables for the main logical operators.
Negation
$$ \begin{array}{c|c} p & \neg p \\\hline T & F \\ F & T \end{array} $$
Conjunction
$$ \begin{array}{c|c|c} p & q & p \land q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array} $$
Disjunction
$$ \begin{array}{c|c|c} p & q & p \lor q \\\hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array} $$
Implication
$$ \begin{array}{c|c|c} p & q & p \to q \\\hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} $$
Biconditional
$$ \begin{array}{c|c|c} p & q & p \leftrightarrow q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \end{array} $$
4. How to build a truth table
To evaluate a compound statement, follow these steps:
- List all possible truth values of the simple propositions.
- Create extra columns for each part of the statement.
- Work from the inside outward, especially when brackets are used.
- Fill in the final column to get the truth value of the whole statement.
It is very important to evaluate the expression in the correct order. Brackets should be handled first, just as in algebra.
5. Worked Example 1: Evaluating \(p \land q\)
Let \(p\) and \(q\) be propositions. Construct the truth table for \(p \land q\).
Step 1: List all possible values of \(p\) and \(q\).
$$ \begin{array}{c|c|c} p & q & p \land q \\\hline T & T & \\ T & F & \\ F & T & \\ F & F & \end{array} $$
Step 2: Use the rule for conjunction: it is true only when both are true.
$$ \begin{array}{c|c|c} p & q & p \land q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array} $$
Conclusion: \(p \land q\) is true only in the first row.
6. Worked Example 2: Evaluating \(\neg p \lor q\)
Construct the truth table for \(\neg p \lor q\).
Step 1: Start with columns for \(p\) and \(q\), then add a column for \(\neg p\), and finally for \(\neg p \lor q\).
$$ \begin{array}{c|c|c|c} p & q & \neg p & \neg p \lor q \\\hline T & T & F & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \end{array} $$
Explanation:
- When \(p=T\), then \(\neg p=F\).
- When \(p=F\), then \(\neg p=T\).
- The disjunction \(\neg p \lor q\) is true when at least one part is true.
Conclusion: The statement is false only in the second row.
7. Worked Example 3: Evaluating \((p \lor q) \to p\)
This example is slightly harder because it has brackets and an implication.
Step 1: Evaluate the part inside the brackets first, which is \(p \lor q\).
Step 2: Use that result to evaluate the implication \((p \lor q) \to p\).
$$ \begin{array}{c|c|c|c} p & q & p \lor q & (p \lor q) \to p \\\hline T & T & T & T \\ T & F & T & T \\ F & T & T & F \\ F & F & F & T \end{array} $$
Why is the third row false?
In the third row, \(p=F\) and \(q=T\). So \(p \lor q=T\). That gives \(T \to F\), which is false. This is the only case where an implication is false.
8. Worked Example 4: Evaluating \((p \to q) \leftrightarrow (\neg q \to \neg p)\)
This is an important statement in logic because it compares an implication with its contrapositive.
We will build the table step by step.
$$ \begin{array}{c|c|c|c|c|c} p & q & p \to q & \neg q & \neg p & (\neg q \to \neg p) \\\hline T & T & T & F & F & T \\ T & F & F & T & F & F \\ F & T & T & F & T & T \\ F & F & T & T & T & T \end{array} $$
Now compare the two implication columns using a biconditional.
$$ \begin{array}{c|c|c|c|c|c|c} p & q & p \to q & \neg q & \neg p & \neg q \to \neg p & (p \to q) \leftrightarrow (\neg q \to \neg p) \\\hline T & T & T & F & F & T & T \\ T & F & F & T & F & F & T \\ F & T & T & F & T & T & T \\ F & F & T & T & T & T & T \end{array} $$
Conclusion: The final column is true in every row. So the statement is always true.
9. Tautology, contradiction, and contingency
Truth tables also help classify statements.
- A tautology is a compound statement that is true in every possible case.
- A contradiction is a compound statement that is false in every possible case.
- A contingency is a compound statement that is true in some cases and false in others.
Examples:
- \(p \lor \neg p\) is a tautology.
- \(p \land \neg p\) is a contradiction.
- \(p \land q\) is a contingency.
Let us verify two of these with truth tables.
Tautology example: \(p \lor \neg p\)
$$ \begin{array}{c|c|c} p & \neg p & p \lor \neg p \\\hline T & F & T \\ F & T & T \end{array} $$
The final column is always true, so this is a tautology.
Contradiction example: \(p \land \neg p\)
$$ \begin{array}{c|c|c} p & \neg p & p \land \neg p \\\hline T & F & F \\ F & T & F \end{array} $$
The final column is always false, so this is a contradiction.
10. Important ideas to remember about implication
Many students find implication strange because “if \(p\), then \(q\)” does not behave exactly like everyday speech. In formal logic, the rule is simple:
$$p \to q \text{ is false only when } p \text{ is true and } q \text{ is false.}$$
You can remember this by thinking: the promise “if \(p\), then \(q\)” is broken only when \(p\) happens but \(q\) does not.
For example, consider:
“If a number is divisible by 4, then it is even.”
- If the number is divisible by 4 and is even, the statement is true.
- If the number is not divisible by 4, the statement is still considered true in formal logic, because the condition did not occur.
11. Common mistakes
- Mixing up conjunction and disjunction: \(p \land q\) needs both true, but \(p \lor q\) needs at least one true.
- Forgetting that mathematical “or” is inclusive: if both parts are true, \(p \lor q\) is still true.
- Misreading implication: \(p \to q\) is not false when \(p\) is false.
- Skipping intermediate columns: always create columns for smaller parts of the statement first.
- Ignoring brackets: evaluate grouped parts before combining the whole expression.
12. Quick strategy for solving truth table questions
- Identify the simple propositions involved.
- Count how many rows are needed. For \(n\) propositions, you need \(2^n\) rows.
- Write the rows in a systematic order.
- Add columns for negations and bracketed expressions.
- Fill in one column at a time carefully.
- Check the final column to answer the question.
For example:
- 1 proposition gives \(2^1 = 2\) rows.
- 2 propositions give \(2^2 = 4\) rows.
- 3 propositions give \(2^3 = 8\) rows.
13. Final summary
Propositional logic studies statements that are either true or false. Compound statements are made using operators such as negation \((\neg)\), conjunction \((\land)\), disjunction \((\lor)\), implication \((\to)\), and biconditional \((\leftrightarrow)\).
A truth table is a systematic way to determine the truth value of a compound statement for every possible combination of truth values of its parts. By building truth tables carefully, you can evaluate logical expressions, test whether two statements are equivalent, and decide whether a statement is a tautology, contradiction, or contingency.
Once you understand the patterns for each logical operator, truth tables become a powerful and straightforward tool in mathematics.
Put what you read to the test
You've worked through Propositional Logic and Truth Tables. Try answering a few questions to see what stuck — and what might deserve a quick reread before you move on.