Difficulty: Introductory to Intermediate | Prerequisites: None, though comfort with basic logical reasoning helps.
This is the backbone of CS 182 (Foundations of Computer Science) at Purdue. Boolean algebra, propositional logic, and inference rules show up in every corner of computer science, from circuit design to algorithm correctness proofs. If you can read a truth table, negate a quantifier, and apply modus ponens without hesitating, you are in good shape for the midterm and for most of what follows in the course.
Boolean algebra gives you the rules for combining true/false values with AND, OR, NOT, and implication. Logic laws (DeMorgan's, distributive, identity) let you rewrite expressions into equivalent forms, quantifiers let you make statements about "all" or "some" elements, and inference rules (modus ponens, modus tollens, syllogisms) let you derive new truths from existing ones. Master these and you can construct proofs, simplify logical expressions, and answer most of the midterm's logic section.
Implication (P → Q)
A conditional statement read as "if P then Q." It is false only when P is true and Q is false; in every other case it evaluates to true. Think of it as a promise: the promise is only broken when you said you would do something (P true) and then did not (Q false).
Disjunctive Normal Form (DNF)
A way of writing a Boolean expression as an OR of ANDed terms, built directly from the true rows of a truth table. In simple terms, you look at every row where the output is 1, AND together the variables for that row (negating any that are 0), then OR all those terms together.
DeMorgan's Laws
Two equivalences for distributing negation over AND/OR: ¬P ∧ Q) ≡ ¬P ∨ ¬Q, and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q. Think of it as: negation swaps AND with OR (and vice versa) and flips each variable.
Distributive Law
OR distributes over AND, and AND distributes over OR, just like multiplication distributes over addition in arithmetic. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).
Identity Laws
Fundamental tautologies and contradictions: ¬P ∧ P ≡ False, ¬P ∨ P ≡ True, and the implication rewrite P → Q ≡ ¬P ∨ Q. These are the building blocks you reach for when simplifying expressions.
Universal Quantifier (∀x)
"For all x" or "for every x." A statement ∀x P(x) claims P holds for every element in the domain.
Existential Quantifier (∃x)
"There exists an x." A statement ∃x P(x) claims at least one element in the domain satisfies P.
Modus Ponens
If you know p is true and p → q is true, you can conclude q. Think of it as: the condition is met, so the consequence follows.
Modus Tollens
If you know ¬q (the consequence is false) and p → q, you can conclude ¬p. The contrapositive direction: if the result did not happen, the cause did not happen either.
Hypothetical Syllogism
Chaining implications: if p → q and q → r, then p → r. Think of it as a logical domino chain.
Disjunctive Syllogism
If p ∨ q is true and ¬p is true, then q must be true. One option is eliminated, so the other stands.
Contraposition
p → q is logically equivalent to ¬q → ¬p. Flipping and negating both sides of an implication preserves its truth.
Resolution
From p ∧ q and ¬p ∧ r, derive q ∧ r. The conflicting literal (p and ¬p) cancels out, leaving what survives on both sides.
The implication P → Q has this truth table:
P | Q | P → Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
The only row that produces false is P = true, Q = false. This trips students up because "false implies anything" evaluates to true.
Write out the full truth table for your expression
Identify every row where the output is 1 (true)
For each true row, AND together the variables, negating any variable that is 0 in that row
OR all the resulting terms together
Worked example from the source: for a function that is true when (p=1, q=1) and when (p=0, q=0), the DNF is (p ∧ q) ∨ (¬p ∧ ¬q).
DeMorgan's Laws
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Negation flips the operator and negates each operand.
Distributive Laws
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Identity Laws
¬P ∧ P ≡ False (contradiction)
¬P ∨ P ≡ True (tautology)
P → Q ≡ ¬P ∨ Q (implication rewrite, heavily tested)
∀x means "for all x"
∃x means "there exists an x"
Negating quantifiers swaps them and negates the predicate:
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)
In plain terms: "not everything satisfies P" is the same as "something fails P." And "nothing satisfies P" is the same as "everything fails P."
Modus Ponens: p, p → q ∴ q
Modus Tollens: ¬q, p → q ∴ ¬p
Hypothetical Syllogism: p → q, q → r ∴ p → r
Disjunctive Syllogism: p ∨ q, ¬p ∴ q
Contraposition: p → q ∴ ¬q → ¬p
Resolution: p ∧ q, ¬p ∧ r ∴ q ∧ r
Students often think P → Q is false when P is false. It is not. "False implies anything" is always true. The only way an implication is false is when the premise is true and the conclusion is false.
When negating quantifiers, students frequently forget to flip the quantifier. ¬∀x P(x) is not ∀x ¬P(x). The quantifier itself changes: ∀ becomes ∃, and the predicate gets negated.
Students confuse the direction of modus tollens. You need ¬q (the negation of the conclusion) to derive ¬p. Having ¬p and p → q tells you nothing about q on its own.
DeMorgan's is sometimes applied without flipping the operator. Negating an AND gives you an OR of the negations, not an AND of the negations. Both parts change: the operator flips, and each operand gets negated.
⚠️ The implication truth table is a near-guaranteed exam question. Know that F → T is true and F → F is true.
⚠️ Converting a truth table to DNF is a standard midterm task. Practise building the expression row by row.
⚠️ Quantifier negation (¬∀ ≡ ∃¬ and ¬∃ ≡ ∀¬) appears in proof questions. Be able to do it mechanically.
⚠️ Modus ponens and modus tollens are the two inference rules most commonly tested in isolation. Know the direction of each without hesitation.
⚠️ The implication rewrite P → Q ≡ ¬P ∨ Q is used in nearly every proof simplification problem.
True or false: P → Q is false when P is false and Q is true. Answer: False. An implication is false only when P is true and Q is false.
Fill in the blank: ¬(P ∨ Q) ≡ ____ Answer: ¬P ∧ ¬Q (DeMorgan's)
True or false: ¬∀x P(x) is equivalent to ∀x ¬P(x). Answer: False. It is equivalent to ∃x ¬P(x).
Fill in the blank: Given p → q and q → r, you can conclude ____ by hypothetical syllogism. Answer: p → r
True or false: P → Q ≡ ¬P ∨ Q. Answer: True. This is the implication rewrite identity.
Q: Write the DNF for a function f(p, q) that is true when p = 1, q = 0 and when p = 0, q = 1.
A: (p ∧ ¬q) ∨ (¬p ∧ q). Take each true row, AND the literals (negating where the variable is 0), then OR them.
Q: Using DeMorgan's Law, simplify ¬(A ∨ B).
A: ¬A ∧ ¬B. Negation distributes, and the OR flips to AND.
Q: Given the premises p → q and ¬q, what can you conclude and by which rule?
A: ¬p, by modus tollens.
Q: Negate the statement ∀x (x > 0 → x² > 0). Write the result in simplified form.
A: ∃x (x > 0 ∧ x² ≤ 0). The universal becomes existential, and the implication P → Q becomes P ∧ ¬Q when negated (since ¬(¬P ∨ Q) ≡ P ∧ ¬Q).
Q: Prove using inference rules: given p → q, q → r, and p, derive r.
A: By hypothetical syllogism on p → q and q → r, get p → r. Then by modus ponens on p and p → r, conclude r.
Boolean algebra and inference rules feed directly into proof techniques covered later in CS 182, including mathematical induction and structural induction. The quantifier rules reappear whenever you work with sets ("for all elements in A") and in Big O proofs ("there exists a c and n₀ such that..."). If you are comfortable negating quantifiers here, the formal definition of Big O will make much more sense.
Boolean algebra, propositional logic, truth table, implication, conditional, material conditional, DeMorgan's theorem, De Morgan's laws, distributive property, tautology, contradiction, identity law, complement law, disjunctive normal form, DNF, sum of products, universal quantifier, existential quantifier, for all, there exists, quantifier negation, modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, contrapositive, contraposition, resolution rule, rules of inference, logical equivalence, CS 182, Purdue, foundations of computer science