Discrete Math · Undergraduate
Propositional Logic and Truth Tables
Quick answer
A proposition is a statement that is either true or false. The connectives not (¬), and (∧), or (∨) and if–then (→) build compound statements whose truth depends only on their parts, which a truth table lays out row by row. Two statements are logically equivalent when their columns match. The most useful equivalences are the contrapositive, p → q ≡ ¬q → ¬p, and De Morgan's laws, ¬(p ∧ q) ≡ ¬p ∨ ¬q. The converse, q → p, is not equivalent.
What you'll learn
- Translate statements into propositional logic
- Build truth tables for compound statements
- Decide when two statements are logically equivalent
- Use the contrapositive and De Morgan's laws
Statements and connectives
A proposition is a statement that is true or false: ” is prime” (true), ” is odd” (false). Letters such as and stand for propositions, and connectives combine them.
| Symbol | Read | True when |
|---|---|---|
| not | is false | |
| and | both are true | |
| or | at least one is true | |
| if then | anything except true and false |
“Or” in logic is inclusive: is true when both are true.
Truth tables
A truth table lists every combination of truth values for the letters and the value of the compound statement in each. With letters there are rows.
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | F | T | T |
| F | F | F | F | T |
Why “if false, then anything” is true
The conditional is a promise: “if happens, will happen.” The promise is broken only when happens and does not, the second row. When does not happen, nothing was promised, so the statement cannot be called false. In logic a statement that is not false is true, so both rows with false give . “If , then the moon is cheese” is a true statement: it promises nothing about our world.
Worked examples
Common mistakes
Practice problems
-
How many rows does a truth table with three letters , , have?
Answer
Full solution
Each letter is true or false, so there are combinations.
-
Is always true?
Answer
Yes; it is a tautology.
Full solution
When is true the first part is true; when is false the second part is.
-
Write the contrapositive of “if , then ”.
Answer
“If , then .”
Full solution
Negate both parts and swap them: .
-
Write the converse of “if , then ”. Is it true for all real ?
Answer
“If , then .” False: .
Full solution
but is not greater than .
-
Use De Morgan’s law to negate “the file is open or the disk is full”.
Answer
“The file is not open and the disk is not full.”
Full solution
.
-
When is false?
Answer
Never; it is a tautology.
Full solution
For it to be false, would have to be true and false, which is impossible.
-
Negate “if is prime, then is odd”. Is the original true?
Answer
” is prime and is even.” The original is false, because makes the negation true.
Full solution
The negation of is , and is a prime that is even.
-
A student says “if it is a rectangle, it is a square” must be true because “if it is a square, it is a rectangle” is true. What is wrong?
Answer
That is the converse, which is not equivalent to the original.
Full solution
Only the contrapositive, “if it is not a rectangle, it is not a square”, follows from the original.
Frequently asked questions
What is a proposition?
A statement that is either true or false, such as "7 is prime". Questions and commands are not propositions.
When is p → q false?
Only when p is true and q is false. If p is false, the conditional is true however q turns out, because no promise was broken.
What is the contrapositive?
The contrapositive of p → q is ¬q → ¬p. It is logically equivalent to the original, so proving one proves the other.
Is the converse equivalent?
No. The converse of p → q is q → p, and it can be false when the original is true: "if it is a square, it is a rectangle" is true, but its converse is not.
What are De Morgan's laws?
¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q: negating an and gives an or of negations, and the reverse.