Source: CS 18200 Foundations of Computer Science, Purdue University
Tags: propositional logic, truth tables, logical equivalence, biconditional, implication, sufficient condition, quantified logic, universal quantifier, existential quantifier, predicate logic, De Morgan's laws for quantifiers, negation of quantifiers
Difficulty: Introductory to Intermediate
Prerequisites: Familiarity with basic Boolean operators (AND, OR, NOT). If you have not yet seen truth tables, start there before tackling quantified logic.
Propositional logic is the formal language for reasoning about statements that are either true or false. It underpins every proof technique, every conditional check in programming, and every database query you will ever write. Quantified logic extends this by letting you make claims about entire collections of objects ("for all x" or "there exists an x"). Together, these two layers form the foundation for the rest of CS 18200 and most of theoretical computer science. If you are coming in cold, think of propositional logic as the grammar of mathematical argument.
Propositional logic deals with combining true/false statements using connectives (AND, OR, NOT, implication, biconditional) and evaluating them with truth tables. Quantified logic adds universal (for all) and existential (there exists) quantifiers so you can reason about predicates over a domain of objects. The key skills are building truth tables, translating English into formal logic, and manipulating quantifier expressions using equivalence laws.
Proposition
A declarative sentence that is either true or false, but not both. In simple terms, it is any statement you can assign a T or F to.
Negation (¬p)
The logical opposite of a proposition p. If p is true, ¬p is false, and vice versa. Think of it as flipping the truth value.
Conjunction (p ∧ q)
True only when both p and q are true. In simple terms, this is the logical AND.
Disjunction (p ∨ q)
True when at least one of p or q is true. In simple terms, this is the logical OR (inclusive).
Implication (p → q)
Read "if p then q." False only when p is true and q is false. This is the connective students struggle with most, because it is true whenever the hypothesis p is false, regardless of q.
Biconditional (p ⟺ q)
True when p and q share the same truth value (both true or both false). Think of it as "p if and only if q."
Sufficient condition
Saying "A is a sufficient condition for B" means A → B. If A happens, that is enough to guarantee B, but B might happen for other reasons too.
Necessary condition
Saying "A is a necessary condition for B" means B → A. B cannot happen without A.
Tautology
A compound proposition that is true under every possible assignment of truth values.
Contradiction
A compound proposition that is false under every possible assignment of truth values.
Predicate / propositional function
A statement containing one or more variables that becomes a proposition once each variable is assigned a value from the domain. For example, P(x) = "x is even" is a predicate over the integers.
Universal quantifier (∀x)
"For all x." The statement ∀x P(x) claims P(x) is true for every element in the domain.
Existential quantifier (∃x)
"There exists an x." The statement ∃x P(x) claims P(x) is true for at least one element in the domain.
De Morgan's laws for quantifiers
¬∀x P(x) ≡ ∃x ¬P(x), and ¬∃x P(x) ≡ ∀x ¬P(x). In simple terms, negating "everything satisfies P" gives "something fails P," and negating "something satisfies P" gives "nothing satisfies P."
For n variables, the truth table has 2ⁿ rows.
List all variable columns first, then compute intermediate sub-expressions, then the final expression.
A biconditional p ⟺ q is true exactly when p and q match.
An implication p → q is false only in the single row where p = T and q = F.
Worked example: [p ⟺ (q ∧ r)] → (¬r ∨ p)
The approach:
Compute the inner parts first: ¬r, then (¬r ∨ p), then (q ∧ r), then the biconditional, then the outer implication.
This expression turns out to be true in 7 of 8 rows. The only row producing F is p = F, q = F, r = T: here the biconditional is T (both sides false? No, q ∧ r = F and p = F, so the biconditional is T), but ¬r ∨ p = F, making the implication F.
Key takeaway: the implication fails only when its left side (the biconditional) is true and its right side (¬r ∨ p) is false.
The most common pitfall is confusing sufficient and necessary conditions.
"A sufficient condition for B is C" translates to C → B. The sufficient condition goes on the left of the arrow.
"A necessary condition for B is C" translates to B → C. The necessary condition goes on the right.
Worked example: "A sufficient condition for you driving to the store or ordering takeout is that it was not raining outside."
Let p = "You drove to the store," q = "You ordered takeout," r = "It was raining outside."
"Not raining" is the sufficient condition, so it sits on the left: ¬r → (p ∨ q).
When you need to show two quantified expressions are equivalent, work from one side to the other using these tools:
Rewrite implications: p → q ≡ ¬p ∨ q
Distribute quantifiers past connectives that do not bind their variable
Apply De Morgan's laws for quantifiers to push or pull negations through ∀ and ∃
Apply ordinary De Morgan's laws to flip ∧ and ∨ under negation
Worked example: Show ∀x[Q(x) → ∃y(P(x,y) ∨ ¬Q(y))] ≡ ¬[∃x∀y(¬P(x,y) ∧ Q(x) ∧ Q(y))]
Starting from the left side:
Replace the implication: ∀x[¬Q(x) ∨ ∃y(P(x,y) ∨ ¬Q(y))]
Since ¬Q(x) does not depend on y, absorb it into the ∃y: ∀x∃y(P(x,y) ∨ ¬Q(x) ∨ ¬Q(y))
Factor using De Morgan's: ∀x∃y(P(x,y) ∨ ¬(Q(x) ∧ Q(y)))
Negate both sides and flip quantifiers: ¬[∃x∀y¬(P(x,y) ∨ ¬(Q(x) ∧ Q(y)))]
Push the inner negation in: ¬[∃x∀y(¬P(x,y) ∧ Q(x) ∧ Q(y))]
This matches the right side.
Read the sentence carefully for scope. "Whenever all X" is a universal quantifier as the outer layer, and "there is a Y" is existential nested inside.
Worked example: "There is a student who sells cookies and another student with straight A's whenever all students are home for Winter Break."
Define: C(x) = "x sells cookies," A(x) = "x has straight A's," W(x) = "x is home for Winter Break."
"Whenever all students are home" = ∀x W(x) as the hypothesis.
"There is a student who sells cookies and another with straight A's" = ∃y∃z(C(y) ∧ A(z)) as the conclusion.
Combined: ∀x(W(x) → ∃y∃z(C(y) ∧ A(z)))
Students often think p → q is false when p is false. It is not. An implication with a false hypothesis is vacuously true. The only way p → q is false is when p is true and q is false.
Students mix up sufficient and necessary conditions. "Sufficient for B" means it implies B (goes on the left of the arrow). "Necessary for B" means B implies it (goes on the right).
When negating quantified statements, students sometimes flip the quantifier but forget to negate the predicate, or negate the predicate but forget to flip the quantifier. Both steps are required.
Students sometimes treat ∀x∃y as interchangeable with ∃y∀x. The order of mixed quantifiers matters: "for every x there exists a y" is much weaker than "there exists a single y that works for every x."
⚠️ Truth table construction is a reliable source of exam marks. Double-check your intermediate columns.
⚠️ Sufficient vs. necessary condition translation appears frequently and is easy to get backwards under pressure.
⚠️ Quantified logic equivalence proofs require showing every step. Skipping steps loses marks.
⚠️ English-to-logic translation with nested quantifiers ("whenever all... there exists...") tests whether you understand quantifier scope.
True or false: The implication p → q is true when p is false, regardless of q.
True. This is vacuous truth.
True or false: ¬∀x P(x) is equivalent to ∀x ¬P(x).
False. The correct equivalence is ¬∀x P(x) ≡ ∃x ¬P(x).
Fill in the blank: "A sufficient condition for B" translates to ___ → B.
A (the sufficient condition).
True or false: p ⟺ q is true when p = T and q = F.
False. The biconditional requires both sides to have the same truth value.
Q: Build a truth table for (p → q) ∧ (q → p) and compare it to p ⟺ q. What do you notice?
A: They produce identical columns. This is because p ⟺ q is logically equivalent to (p → q) ∧ (q → p).
Q: Translate to propositional logic: "A necessary condition for passing the exam is completing the homework."
A: Let p = "You pass the exam" and h = "You completed the homework." Necessary condition for p is h means p → h.
Q: Negate the statement ∃x∀y(P(x,y) ∧ Q(y)) and simplify.
A: ¬∃x∀y(P(x,y) ∧ Q(y)) ≡ ∀x∃y¬(P(x,y) ∧ Q(y)) ≡ ∀x∃y(¬P(x,y) ∨ ¬Q(y)).
Q: Translate to quantified logic (domain: all people): "Everyone who studies hard passes, and there is someone who studies hard."
A: Let S(x) = "x studies hard" and P(x) = "x passes." The statement is ∀x(S(x) → P(x)) ∧ ∃x S(x).
This material connects directly to set theory (the next topic in CS 18200) because set operations like union, intersection, and complement mirror the logical connectives AND, OR, and NOT. Proof techniques covered later in the course rely on propositional logic to structure arguments, and quantified logic appears in every formal specification in software engineering and database query languages (SQL's WHERE clause is predicate logic in disguise).
propositional logic, truth table, logical connective, negation, conjunction, disjunction, implication, biconditional, if and only if, iff, sufficient condition, necessary condition, tautology, contradiction, contingency, predicate logic, quantified logic, universal quantifier, for all, existential quantifier, there exists, De Morgan's laws, quantifier negation, vacuous truth, CS 18200, foundations of computer science, Purdue, discrete math logic