Home / Courses / Intro to Proofs / Unit 1
Intro to Proofs Unit 1: Logic and Truth Tables
Propositional logic is the grammar of proof: it tells you exactly what a statement claims, when it is false, and which rewrites keep its meaning. Every later unit depends on reading conditionals and negations correctly.
Covers: Propositions and connectives, Truth tables, Conditionals and biconditionals, Converse, inverse and contrapositive, Logical equivalence and De Morgan's laws, Tautologies, contradictions and valid arguments, Negating statements
Study guide
A proposition is a declarative sentence that is either true or false. We combine propositions with connectives: negation ¬P (not P), conjunction P ∧ Q (and), disjunction P ∨ Q (inclusive or), the conditional P → Q (if P then Q), and the biconditional P ↔ Q (P if and only if Q). A truth table lists every combination of truth values for the variables and the resulting value of the compound statement. With n variables there are 2ⁿ rows, so P, Q, R need 8 rows. Building tables carefully, one column per subformula, is the most reliable way to check any claim about a statement form when you are unsure.
The conditional causes the most confusion. P → Q is false only when P is true and Q is false; in every other row it is true. In particular, when P is false the conditional is vacuously true, no matter what Q says. English has many ways to say P → Q: 'if P then Q', 'Q if P', 'P only if Q', 'P is sufficient for Q', and 'Q is necessary for P'. Watch 'only if' closely: it introduces the conclusion, not the hypothesis. The biconditional P ↔ Q is true when P and Q have the same truth value, and it means (P → Q) ∧ (Q → P).
From a conditional P → Q we can form three relatives. The converse is Q → P, the inverse is ¬P → ¬Q, and the contrapositive is ¬Q → ¬P. Only the contrapositive is logically equivalent to the original; the converse and inverse are equivalent to each other but not to P → Q. For example, 'if n is divisible by 6 then n is divisible by 3' is true, but its converse fails at n = 9. Proving a contrapositive instead of the original statement is a standard technique you will use in later units.
Two statement forms are logically equivalent (written ≡) if they have the same truth value in every row. Key equivalences include De Morgan's laws, ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q; the rewrite P → Q ≡ ¬P ∨ Q; the negation ¬(P → Q) ≡ P ∧ ¬Q; double negation; and the distributive laws. A tautology is true in every row, a contradiction is false in every row. An argument is valid when the conditional 'premises → conclusion' is a tautology, as with modus ponens and modus tollens. Affirming the consequent and denying the antecedent are invalid look-alikes.
Key ideas
- A conditional P → Q is false only when P is true and Q is false.
- 'P only if Q' means P → Q, while 'P if Q' means Q → P.
- A statement is equivalent to its contrapositive but not to its converse or inverse.
- De Morgan's laws flip ∧ and ∨ when a negation is pushed inside.
- The negation of a conditional is a conjunction: ¬(P → Q) ≡ P ∧ ¬Q.
- Two forms are equivalent exactly when their truth tables match in every row.
- A valid argument is one whose premises-imply-conclusion form is a tautology.
Formulas and rules
Common mistakes
- Treating a conditional with a false hypothesis as false instead of vacuously true.
- Confusing the converse or inverse with the contrapositive.
- Negating P ∧ Q as ¬P ∧ ¬Q instead of ¬P ∨ ¬Q.
- Writing the negation of a conditional as another conditional, such as ¬P → ¬Q.
- Translating 'P only if Q' as Q → P.
Before the test, make sure you can
- Build a complete truth table for a statement form with up to three variables.
- Translate English phrases like 'only if', 'sufficient' and 'necessary' into symbols.
- Write the converse, inverse and contrapositive of a conditional and say which is equivalent.
- Negate conjunctions, disjunctions and conditionals correctly.
- Prove or disprove a logical equivalence with a truth table or known laws.
- Identify tautologies, contradictions and valid argument forms.
- Find a counterexample row that makes a conditional false.
Words to know
- Proposition
- A declarative sentence that is either true or false, but not both.
- Conjunction
- P ∧ Q, true only when both P and Q are true.
- Disjunction
- P ∨ Q, true when at least one of P, Q is true (inclusive or).
- Conditional
- P → Q, false only when P is true and Q is false.
- Biconditional
- P ↔ Q, true exactly when P and Q have the same truth value.
- Hypothesis (antecedent)
- The 'if' part P of a conditional P → Q.
- Conclusion (consequent)
- The 'then' part Q of a conditional P → Q.
- Converse
- Q → P, formed by swapping the parts of P → Q; not equivalent to it.
- Inverse
- ¬P → ¬Q; equivalent to the converse but not to P → Q.
- Contrapositive
- ¬Q → ¬P; logically equivalent to P → Q.
- Logical equivalence
- Two forms that agree in every row of the truth table.
- Tautology
- A statement form true under every assignment of truth values.
- Contradiction
- A statement form false under every assignment of truth values.
- De Morgan's laws
- ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
- Vacuous truth
- A conditional is true whenever its hypothesis is false.
- Modus ponens
- From P and P → Q, conclude Q.
- Modus tollens
- From ¬Q and P → Q, conclude ¬P.
- Valid argument
- An argument in which the conclusion is true in every row where all premises are true.
Sample practice questions
30 more questions like these, from level 1 to 5, are in the practice set.
In logic, a proposition is best described as:
- A question or instruction about a mathematical object
- A declarative sentence that is true or false, but not both
- Any sentence that contains a variable such as x or n
- A sentence that is true for at least one choice of input
Show the answer and steps
Answer: B) A declarative sentence that is true or false, but not both
- A proposition must have a definite truth value.
- Open sentences like 'x > 3' have no truth value until x is fixed, and questions or commands have none at all.
- So a proposition is a declarative statement that is exactly one of true or false.
The conditional P → Q is false in exactly which case?
- P is false and Q is true
- P and Q have different truth values
- P is true and Q is false
- P and Q are both false
Show the answer and steps
Answer: C) P is true and Q is false
- A conditional is a promise: if P happens, Q happens.
- The promise is broken only when P happens and Q does not.
- In every other row, including all rows with P false, P → Q is true.
In the truth table of (P ∨ Q) → R, how many of the 8 rows make the statement true?
- 6
- 5
- 4
- 3
Show the answer and steps
Answer: B) 5
- The conditional is false only when P ∨ Q is true and R is false.
- P ∨ Q is true in 3 of the 4 (P, Q) combinations, and each pairs with R false once, giving 3 false rows.
- So 8 − 3 = 5 rows are true.