Propositional logic is the study of how to combine simple true/false statements using connectives (AND, OR, NOT, IF...THEN) and evaluate whether the resulting compound statements are true or false. You will translate English sentences into symbolic form, simplify expressions by substituting known truth values, prove logical equivalence using truth tables, convert expressions to disjunctive normal form (DNF), and determine whether a formula can ever be made true (satisfiability).
Difficulty: Introductory
Prerequisites: None. This is typically the first formal topic in a discrete mathematics or foundations of computer science course. Familiarity with basic Boolean logic (true/false) helps but is not required.
Propositional logic sits at the very start of CS 182 (Foundations of Computer Science) and underpins nearly everything that follows: predicate logic, proofs, set theory, and algorithm correctness. The core idea is deceptively simple: take statements that are either true or false, connect them with logical operators, and reason about what must follow. Where this topic fits in the broader course: it gives you the formal language you will use to write precise mathematical arguments for the rest of the semester. If you are behind, start here, as predicate logic (the next unit) builds directly on these skills.
Proposition (propositional variable)
A declarative sentence that is either true (T) or false (F), never both. Variables such as p, q, r stand in for propositions.
In simple terms, a proposition is any statement you can stamp "true" or "false" on. "It is sunny" qualifies; "Close the door" does not.
Negation (NOT, ¬)
Flips the truth value: ¬p is true exactly when p is false.
Think of it as the logical opposite switch.
Conjunction (AND, ∧)
True only when both operands are true.
Think of it as: both sides must hold for the whole thing to hold.
Disjunction (OR, ∨)
True when at least one operand is true (inclusive OR, unless stated otherwise).
In simple terms, at least one side needs to be true. In this course, OR is inclusive by default.
Implication (conditional, IF...THEN, →)
p → q is false only when p is true and q is false. In every other case it is true.
Think of it as a promise: the promise is only broken when the condition holds but the result does not. A false premise makes the whole implication vacuously true.
Biconditional (IF AND ONLY IF, ↔)
True when both sides share the same truth value.
In simple terms, p ↔ q means p and q are either both true or both false.
Tautology
An expression that is true under every possible assignment of truth values to its variables.
Think of it as a formula that can never be false, no matter what.
Contradiction
An expression that is false under every possible assignment of truth values.
The opposite of a tautology: always false.
Satisfiable expression
An expression for which there exists at least one assignment of truth values that makes it true.
In simple terms, if you can find even one row in the truth table where the expression comes out true, it is satisfiable.
Unsatisfiable expression
An expression that is false under every assignment, i.e. a contradiction. No combination of variable values makes it true.
Logical equivalence (≡)
Two expressions are logically equivalent when they have the same truth value under every possible assignment.
Think of it as: two different-looking formulas that always agree.
Disjunctive Normal Form (DNF)
An expression written as a disjunction (OR) of one or more conjunctions (ANDs) of literals. Each conjunction is called a clause or minterm.
In simple terms, DNF looks like (stuff AND stuff) OR (stuff AND stuff) OR ... where each "stuff" is a variable or its negation.
Conjunctive Normal Form (CNF)
An expression written as a conjunction (AND) of one or more disjunctions (ORs) of literals. The dual of DNF.
Modus ponens
A rule of inference: from p → q and p, conclude q.
If the implication holds and the premise is true, the conclusion must be true.
Modus tollens (contrapositive reasoning)
A rule of inference: from p → q and ¬q, conclude ¬p.
If the implication holds and the conclusion is false, the premise must have been false.
Converse
The converse of p → q is q → p. The converse is not logically equivalent to the original.
Contrapositive
The contrapositive of p → q is ¬q → ¬p. The contrapositive is always logically equivalent to the original.
The first skill is mapping natural-language sentences onto propositional variables and connectives.
Assign a variable to each atomic statement (p = "The temperature is above 32°F", q = "It is sunny", r = "Alice will jog outside").
"If A or B, then C" becomes (A ∨ B) → C.
Example: "If the temperature is above 32°F or it is sunny, Alice will jog outside" translates to (p ∨ q) → r.
"A only if B" means A → B (not B → A).
"A if and only if B" means A ↔ B.
"Neither A nor B" means ¬A ∧ ¬B.
Watch the scope of connectives. Parentheses matter. "If p or q, then r" is (p ∨ q) → r, which is different from p ∨ (q → r).
Once you have a conditional statement and know certain facts, you can apply inference rules.
Modus ponens: Given (p ∨ q) → r and p is true, then (p ∨ q) is true (since p alone makes the disjunction true), so r must be true. You can conclude Alice jogs outside.
Modus tollens (contrapositive): Given (p ∨ q) → r and ¬r (Alice will not jog), you conclude ¬(p ∨ q), which by De Morgan's law gives ¬p ∧ ¬q. So both "the temperature is not above 32°F" and "it is not sunny" follow.
Converse error (affirming the consequent): Knowing r is true does not let you conclude p or q. The implication only flows one direction.
Inverse error (denying the antecedent): Knowing ¬p alone does not let you conclude ¬r, because q could still make the antecedent true.
Given an expression and partial truth-value assignments, substitute the known values and simplify.
Worked example with the expression (p ∨ (¬q ∨ r)) ∧ ¬(r → ¬q):
Part (a): p = T, q = F, r = T
r → ¬q becomes T → T = T, so ¬(r → ¬q) = F.
Anything ANDed with F is F.
Result: F
Part (b): p = F, q = T (r unknown)
Left side: F ∨ (¬T ∨ r) = F ∨ (F ∨ r) = r.
Right side: ¬(r → ¬T) = ¬(r → F) = ¬(¬r) = r.
Expression becomes r ∧ r = r.
Part (c): q = F (p and r unknown)
Left side: p ∨ (T ∨ r) = p ∨ T = T.
Right side: ¬(r → T) = ¬T = F.
T ∧ F = F.
Key simplification identities to remember: X ∨ T = T, X ∧ F = F, X ∨ F = X, X ∧ T = X, ¬¬X = X.
Two expressions are logically equivalent (≡) when they produce the same output for every combination of inputs. The standard proof method is a truth table.
Example: Are (p → q) ∧ (p → r) and p → (q ∨ r) equivalent?
Rewrite implications: (¬p ∨ q) ∧ (¬p ∨ r) vs. ¬p ∨ (q ∨ r).
Consider p = T, q = F, r = F: left side gives (F ∨ F) ∧ (F ∨ F) = F ∧ F = F; right side gives F ∨ (F ∨ F) = F. Both false here.
Consider p = T, q = T, r = F: left side gives (F ∨ T) ∧ (F ∨ F) = T ∧ F = F; right side gives F ∨ (T ∨ F) = T.
Left is F, right is T. Not equivalent. One counterexample is enough.
The left expression (p → q) ∧ (p → r) is strictly stronger: it requires both q and r when p is true. The right expression p → (q ∨ r) only requires at least one of them.
DNF rewrites any expression as an OR of AND-clauses, where each clause contains only literals (variables or their negations).
Procedure:
Eliminate implications: replace A → B with ¬A ∨ B.
Push negations inward using De Morgan's laws: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B.
Distribute ∧ over ∨ until you have a flat OR-of-ANDs structure.
Alternatively, build the truth table and write one conjunction per true row, then OR them together.
Worked example: ¬(p ∨ ¬q) → (¬r ∧ (p → r))
Rewrite the outer →: (p ∨ ¬q) ∨ (¬r ∧ (p → r)).
Rewrite inner →: (p ∨ ¬q) ∨ (¬r ∧ (¬p ∨ r)).
Distribute: (p ∨ ¬q) ∨ ((¬r ∧ ¬p) ∨ (¬r ∧ r)).
¬r ∧ r = F, so drop it: (p ∨ ¬q) ∨ (¬p ∧ ¬r).
Already in DNF: p ∨ ¬q ∨ (¬p ∧ ¬r).
Each single literal counts as a valid DNF clause on its own.
A formula is satisfiable if at least one truth-value assignment makes it true. Unsatisfiable means no assignment works.
Example (a): (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (¬p ∨ r)
Try p = T, q = T, r = T, s = F: clause 1 = T, clause 2 = T, clause 3 = T. Satisfiable.
Example (b): p ∧ (¬p ∨ r) ∧ ¬r ∧ (¬p ∨ ¬r ∨ q)
p must be T (first clause). Then ¬p ∨ r forces r = T. But ¬r forces r = F. Contradiction. Unsatisfiable.
For small formulas, try to find a satisfying assignment by propagating forced values. If you reach a contradiction, the formula is unsatisfiable.
De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
Implication rewrite: p → q ≡ ¬p ∨ q
Contrapositive: p → q ≡ ¬q → ¬p
Double negation: ¬¬p ≡ p
Distribution: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Absorption: p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p
Identity: p ∧ T ≡ p, p ∨ F ≡ p
Domination: p ∨ T ≡ T, p ∧ F ≡ F
Idempotent: p ∨ p ≡ p, p ∧ p ≡ p
Complement: p ∨ ¬p ≡ T, p ∧ ¬p ≡ F
p | q | p → q |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
The only row where → is false: true premise, false conclusion.
Propositional logic is the foundation of digital circuit design: every logic gate (AND, OR, NOT) maps directly to a connective, and simplifying Boolean expressions is how engineers reduce the number of gates on a chip. It also underpins database query languages (SQL WHERE clauses are propositional expressions) and the condition checks in every if-statement you write in code.
Students often think p → q means "p causes q." It does not. The conditional is about truth values only, not causation. A false antecedent makes the implication true regardless of q.
Students confuse the converse (q → p) with the contrapositive (¬q → ¬p). The contrapositive is equivalent to the original; the converse is not.
Students assume that showing the conclusion is true proves the argument is valid. Validity requires that the conclusion is true in every case where the premises are true, not just in one case.
Students forget that inclusive OR means "at least one, possibly both." In everyday English, "or" often implies exclusivity, but in this course OR is inclusive unless stated otherwise.
⚠️ Implication truth table: know it cold. The "F → anything = T" row is tested constantly.
⚠️ Converse vs. contrapositive: expect a question asking you to identify which is equivalent to the original.
⚠️ DNF conversion: you will be asked to convert at least one expression by hand. Practise the elimination and distribution steps.
⚠️ Satisfiability vs. tautology vs. contradiction: the exam will likely give you a CNF expression and ask you to classify it.
True or False: The implication F → F evaluates to True.
Fill in the blank: The contrapositive of p → q is ____.
True or False: p ∨ (p ∧ q) simplifies to p ∧ q.
True or False: An expression that is a tautology is also satisfiable.
Fill in the blank: By De Morgan's law, ¬(p ∧ q) ≡ ____.
Answers: 1. True. 2. ¬q → ¬p. 3. False (it simplifies to p, by absorption). 4. True (a tautology is true under every assignment, so certainly at least one). 5. ¬p ∨ ¬q.
Q: Given (p ∨ q) → r, p is true, and r is false, what can you conclude?
A: Since p is true, (p ∨ q) is true. But r is false, so the implication (p ∨ q) → r is false. This contradicts the given that the implication is true, so these premises are inconsistent.
Q: Simplify (p ∨ (¬q ∨ r)) ∧ ¬(r → ¬q) when q = F.
A: Substituting q = F: left side becomes p ∨ (T ∨ r) = T. Right side: ¬(r → T) = ¬T = F. So T ∧ F = F.
Q: Convert ¬(p ∧ q) → r into DNF.
A: Rewrite →: (p ∧ q) ∨ r. This is already in DNF (an OR of two clauses: one conjunction and one literal).
Q: Is the expression p ∧ ¬p ∧ q satisfiable?
A: No. p ∧ ¬p is always false, so the entire expression is a contradiction regardless of q.
Q: Prove that (p → q) ∧ (p → r) is not equivalent to p → (q ∨ r).
A: Find one counterexample. Let p = T, q = T, r = F. Left: (T → T) ∧ (T → F) = T ∧ F = F. Right: T → (T ∨ F) = T → T = T. F ≠ T, so not equivalent.
This connects directly to predicate logic (the next unit), which extends propositional logic by adding quantifiers ("for all", "there exists") and predicates that take variables. Every proof technique you encounter later in the course (induction, contradiction, contrapositive proofs) relies on the inference rules introduced here. Satisfiability in propositional logic is also the basis of the SAT problem, one of the most important problems in computational complexity theory.
propositional logic, Boolean logic, Boolean algebra, truth table, logical connectives, AND OR NOT, conjunction disjunction negation, implication conditional, biconditional, modus ponens, modus tollens, contrapositive, converse, inverse, tautology, contradiction, satisfiability, SAT, unsatisfiable, logical equivalence, disjunctive normal form, DNF, conjunctive normal form, CNF, De Morgan's laws, CS 182, foundations of computer science, discrete math, Purdue CS 182