13 / 18 · Account for every step
A proof is a chain of permissions
Justify short natural-deduction steps using stated premises and rules.
Builds on Everyone has one, or one for everyone?
Go to practice ↓A question to keep in mind
A conclusion feels obvious. Can you show the exact steps that license it?
A proof records how a conclusion follows through permitted rules. Unlike a truth table, it need not list all assignments. Every line must be a premise, an explicitly opened assumption, or a result justified from available earlier lines.
Conjunction elimination (∧E) takes P or Q from P ∧ Q. Conjunction introduction (∧I) combines available P and Q into P ∧ Q. Conditional elimination (→E), also called modus ponens, takes Q from P → Q and P.
Cite line numbers so another reader can inspect the dependency. A valid rule cannot be applied to premises that only resemble its required form. These exercises ask you to justify authored proof steps, not enter arbitrary proofs into a general theorem prover.
Work through an example
- 1. P ∧ Q (premise). 2. Q → R (premise).
- 3. Q (∧E, line 1). 4. R (→E, lines 2 and 3).
- Q was extracted, not guessed. R used the entire conditional and its antecedent.
Your turn
0 / 3Complete the justifications for this direct proof.
Read solution · does not award completion
- 4. Q → →E, 1 + 2
- 5. R → →E, 3 + 4
- 6. Q ∧ R → ∧I, 4 + 5
Lines 4 and 5 each apply a conditional to its antecedent. Line 6 combines two established statements. No extra assumption is needed.
Given P ∧ (Q ∨ R), which follows directly by ∧E?
Read solution · does not award completion
Q ∨ R
Respect parentheses: apply the rule to the main connective.
A proof has P → Q and Q, then labels P '→E'. What is wrong?
Read solution · does not award completion
It affirms the consequent rather than applying →E.
The counterexample P = F, Q = T from lesson 7 still exposes this mistake.
Bring it back to your own work
Rewrite a three-step mathematical or programming explanation as numbered lines. Mark any step without an explicit justification.