Propositional logic & proofs: practice problems with step-by-step solutions
Also called: truth tables · propositional calculus · predicate logic
Free Propositional logic & proofs practice problems with diagrams, hints and full worked solutions. New values every time, at three levels: truth tables, equivalences and proof methods, quantifiers and arguments.
Free practice problemEasy
Complete the truth table (1 = true, 0 = false). In how many rows N is (p → r) ↔ (r ∨ q) true?
A proposition is a statement that is either true or false, such as “7 is prime”. We write it with a letter, p or q, and its truth value as 1 (true) or 0 (false).
Connectives build larger formulas from smaller ones:
¬p (not p) flips the value.
p ∧ q (and) is 1 only when both are 1.
p ∨ q (or) is 0 only when both are 0. It is the inclusive or: both may be true.
p → q (if p then q) is 0 only when p = 1 and q = 0.
p ↔ q (if and only if) is 1 when p and q have the same value.
The implication surprises many students: when p is false, p → q is true whatever q is. A promise “if it rains, I take an umbrella” is only broken on a rainy day without an umbrella.
Self-check p = 0 and q = 1. What is the value of p → q?
0
1
It depends on the context
Undefined
Answer: 1. An implication is only false when the condition holds and the conclusion fails (p = 1, q = 0). With p = 0 it is true, whatever q is.
2Truth tables
A truth table lists every combination of truth values of the variables. With n different variables there are 2ⁿ rows: 4 for two variables, 8 for three, 16 for four. A variable that appears twice still counts once.
Work from the inside out. Give every subformula its own column, so each new column only needs one connective applied to columns you already have.
List the variables and write all 2ⁿ combinations, starting with all 1s.
Add a column for each subformula, innermost first.
Fill each column using the rule of its main connective.
Read the answer from the last column: count the 1s, or find the row asked for.
Self-check How many rows does the truth table of (p ∧ q) → (r ∨ p) have?
16
4
6
8
Answer: 8. The formula has three different variables, p, q and r, so 2³ = 8 rows. p appears twice but is one variable; 16 would be 2⁴ for four occurrences.
3A worked example
Follow every step. Try to predict the next one before you open it.
Worked example
In how many rows of its truth table is (p → q) ∧ ¬q true?
1
Variables and rows
Two variables, p and q, so 4 rows: (1, 1), (1, 0), (0, 1), (0, 0).
2
Column p → q
It is 0 only in the row p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Column ¬q
¬q: 0, 1, 0, 1
4
The conjunction
Both columns must be 1. That happens only in the last row, p = 0 and q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Answer
The formula is true in 1 row, the row p = 0, q = 0. This is why p → q and ¬q together give ¬p (modus tollens).
4Equivalences and proof methods
Two formulas are equivalent (≡) when their truth-table columns are identical. A tautology is 1 in every row, a contradiction 0 in every row, and a contingency is neither.
The laws you use most:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
These laws are the basis of the proof methods. A proof by contrapositive of p → q proves ¬q → ¬p instead, which is equivalent. A proof by contradiction assumes p ∧ ¬q, the only way the implication can fail, and derives something impossible.
Watch out: the converse q → p and the inverse ¬p → ¬q are not equivalent to p → q.
Self-check Which formula is equivalent to ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Answer: ¬p ∨ ¬q. By De Morgan the ∧ becomes ∨ and both parts are negated. ¬p ∧ ¬q is the negation of p ∨ q, a different statement: it is false when exactly one of p and q is true, where ¬(p ∧ q) is true.
5Quantifiers and valid arguments
With variables over a domain, ∀x P(x) says “P holds for every x” and ∃x P(x) says “P holds for at least one x”. A negation swaps the quantifier:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Move the negation inwards one step at a time; inside, use the propositional laws. For example ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “not every P is a Q” means “some P is not a Q”.
An argument is valid when the conclusion is 1 in every row in which all premises are 1. Classic valid forms are modus ponens (p → q, p, so q), modus tollens (p → q, ¬q, so ¬p) and the hypothetical syllogism (p → q, q → r, so p → r).
A row with all premises 1 and the conclusion 0 is a counterexample. Affirming the consequent (p → q, q, so p) is invalid: the row p = 0, q = 1 is a counterexample.
Self-check What is the negation of “every student passed”, ∀x P(x)?
¬P(x) for one fixed student x
∀x ¬P(x): no student passed
∃x P(x): some student passed
∃x ¬P(x): some student did not pass
Answer: ∃x ¬P(x): some student did not pass. One student who failed is enough to make “every student passed” false. “No student passed” is much stronger than the negation.
6Common mistakes
Treating p → q as false when p is false. It is only false when p = 1 and q = 0.
Counting a repeated variable twice when finding the number of rows.
Confusing the contrapositive ¬q → ¬p with the converse q → p or the inverse ¬p → ¬q.
Negating ∀x P(x) as ∀x ¬P(x): the quantifier must change to ∃.
Writing ¬(p ∧ q) as ¬p ∧ ¬q: De Morgan also swaps the connective.
Self-check Which statement is the contrapositive of “if n² is even, then n is even”?
If n is even, then n² is even
If n is odd, then n² is odd
If n² is odd, then n is odd
n² is even and n is odd
Answer: If n is odd, then n² is odd. Swap the two parts and negate both: not (n even) → not (n² even). “If n is even, then n² is even” is the converse; the last option is what a proof by contradiction assumes.
7How exam questions look
Easy: truth tables. You find the number of rows, count the rows in which a formula is true, or click the one row that makes a formula true or false.
Medium: equivalences and proof methods. You decide whether a formula is a tautology, a contradiction or a contingency, pick the equivalent formula, or the statement to prove in a proof by contrapositive or by contradiction.
Hard: quantifiers and arguments. You negate quantified statements, choose the conclusion that follows from premises, click the counterexample row of an invalid argument, or count true rows in a four-variable table.
Exactly one row of the truth table makes ¬(p ∨ q) → q false. Click that row.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Show hints
a → b is 0 only when a = 1 and b = 0. ¬a flips the value. a ∨ b is 0 only when both are 0.
Work out the main connective first: what must its two sides be for the whole formula to be 0?
Give each part its own column: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Show the answer and explanation
Truth tables: a formula with n different variables has 2ⁿ rows, one for every combination of truth values (1 = true, 0 = false). Work from the inside out and give every subformula its own column. ¬a flips the value; a ∧ b is 1 only when both are 1; a ∨ b is 0 only when both are 0; a → b is 0 only when a = 1 and b = 0; a ↔ b is 1 when both sides are equal.
Which formula is logically equivalent to (b ∧ c) → a? Click it.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Show hints
Equivalent formulas agree in every row of the truth table. One row where they differ rules an option out.
Try a row that makes (b ∧ c) → a 0 and check which options are also 0 there.
Exportation: (a ∧ b) → c ≡ a → (b → c). Both are 0 only when a = 1, b = 1 and c = 0.
Show the answer and explanation
Logical equivalence: two formulas are equivalent (≡) when they have the same value in every row of the truth table. A tautology is 1 in every row, a contradiction is 0 in every row, and a contingency is neither. Useful laws: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositive); ¬(a → b) ≡ a ∧ ¬b; and the distributive laws, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
The law
Exportation: (a ∧ b) → c ≡ a → (b → c). Both are 0 only when a = 1, b = 1 and c = 0.
(b ∧ c) → a ≡ b → (c → a)
Check with the truth table
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Answer
b → (c → a)
The columns after the bar are the options in the order shown.
Example 3Hard
The premises (q ∧ p) → r; q; ¬r are given. Which conclusion follows from them? Click it.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Show hints
A conclusion follows when it is 1 in every row in which all premises are 1.
Find the rows that make all premises 1, then test each option in those rows.
This is a standard rule: modus tollens with a conjunction.
Show the answer and explanation
Quantifiers and arguments: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Move a negation inwards, swap every quantifier it passes, and negate the inner formula with the propositional laws, such as ¬(a → b) ≡ a ∧ ¬b. An argument is valid when the conclusion is 1 in every row in which all premises are 1. A single row with true premises and a false conclusion is a counterexample and shows the argument is invalid.
Rows with all premises true
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Conclusion
¬p (modus tollens with a conjunction)
Answer
¬p
Questions and answers
What is Propositional logic & proofs?
A proposition is a statement that is either true or false, such as “7 is prime”. We write it with a letter, p or q, and its truth value as 1 (true) or 0 (false).
Connectives build larger formulas from smaller ones:
How do I solve Propositional logic & proofs problems step by step?
Count the different variables: the truth table has 2ⁿ rows, starting with all of them 1.
Give every subformula its own column and fill the columns from the inside out.
Apply the rule of each connective: → is 0 only for 1 → 0, ↔ is 1 when both sides agree.
For equivalences, compare the final columns row by row; for an argument, look only at the rows in which every premise is 1.
To negate a quantified statement, move ¬ inwards, swap ∀ and ∃, and negate the inner formula.
What are common mistakes in Propositional logic & proofs?
Treating p → q as false when p is false.
Counting a repeated variable twice when finding the number of rows.
Confusing the contrapositive ¬q → ¬p with the converse q → p.
Negating ∀x P(x) as ∀x ¬P(x) instead of ∃x ¬P(x).
Applying De Morgan without swapping ∧ and ∨.
What do the Propositional logic & proofs exercises cover?
Easy: truth tables
Medium: equivalences and proof methods
Hard: quantifiers and arguments
Every problem has new values, so you learn the method instead of an answer. Stuck? Open a small hint first, and the full explanation only when you need it.
How practising works
Every problem has new values, so you learn the method instead of an answer.
Stuck? Open a small hint first, and the full explanation only when you need it.
Your progress, mistakes and saved problems are kept, so you can review before the exam.