Propositional and Predicate Logic

Definition: Formal mathematical systems for constructing rigorous statements using logical operators (AND, OR, NOT, Implication) and, in predicate logic, quantifiers over variables (Universal ∀, Existential ∃).

How It Works

Propositional logic evaluates atomic statements (“it is raining”) that are strictly True or False, and combines them with connectives: ∧ (AND), ∨ (OR), ¬ (NOT), → (implies), ↔ (if and only if)
P ↔ Q (biconditional) is True exactly when P and Q share the same truth value, equivalent to (P → Q) ∧ (Q → P) holding simultaneously
Predicate logic extends propositional logic with predicates, functions like P(x) that become True or False only once a specific value is substituted for x
The Universal Quantifier ∀x P(x) asserts P(x) holds for every value of x in the domain, the Existential Quantifier ∃x P(x) asserts P(x) holds for at least one value
Truth tables enumerate every combination of True/False inputs to a compound statement, exhaustively determining its output for each case, the definitive way to check whether two expressions are logically equivalent
Logical implication P → Q is only False when P is True and Q is False, it’s vacuously True whenever P is False, regardless of Q
De Morgan’s Laws convert between AND/OR and their negations: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q, and extend to quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x)
A tautology is a compound statement that’s True under every possible input, a contradiction is False under every input, most statements are neither, called contingencies
The domain of discourse must be specified for quantified statements to be meaningful, ∀x P(x) means something different over “all integers” than over “all students in this class”
Nested quantifiers read left to right, ∀x ∃y P(x,y) means “for every x, there is some y (possibly depending on x) such that P holds”
Logical equivalence (≡) means two statements have identical truth values under every possible input, provable either by matching truth tables or by a chain of algebraic law applications
The contrapositive of P → Q is ¬Q → ¬P, always logically equivalent to the original, while the converse Q → P and inverse ¬P → ¬Q are generally not

Key Logical Laws

Law	Statement
Double Negation	`¬¬P ≡ P`
De Morgan’s (AND)	`¬(P ∧ Q) ≡ ¬P ∨ ¬Q`
De Morgan’s (OR)	`¬(P ∨ Q) ≡ ¬P ∧ ¬Q`
Implication elimination	`P → Q ≡ ¬P ∨ Q`
Contrapositive	`P → Q ≡ ¬Q → ¬P`
Distributive	`P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)`
Quantifier negation	`¬∀x P(x) ≡ ∃x ¬P(x)` and `¬∃x P(x) ≡ ∀x ¬P(x)`

Under the Hood

This tree decomposes the compound statement (P ∧ Q) → R into its structural parts. The root operator is the implication, →, since it’s the last operator applied when reading the expression, everything to its left is the antecedent, everything to its right is the consequent. The antecedent itself decomposes further: it’s an AND of two simpler propositions, P and Q, which are the leaves of the tree, atomic and not decomposed any further.

This is exactly how a compiler or logic engine parses a boolean expression: recursively, from the outermost (lowest-precedence) operator down to the atomic propositions at the leaves. Evaluating the tree means evaluating the leaves first, then combining results upward, P ∧ Q first, then checking whether that result implies R.

Operator precedence determines how an expression without explicit parentheses gets parsed into a tree at all. The standard order, from tightest to loosest binding, is ¬, then ∧, then ∨, then →, then ↔, exactly mirroring why ¬P ∧ Q means (¬P) ∧ Q and not ¬(P ∧ Q), and why parentheses are added liberally in formal writing to avoid relying on a reader remembering the convention.

Worked Example 1

Given: Build the truth table for P → Q and confirm it’s only False in exactly one row.
Step: Enumerate all 4 combinations: P=T,Q=T → T; P=T,Q=F → F; P=F,Q=T → T; P=F,Q=F → T.
Answer: P → Q is False only when P=T and Q=F, confirming implication is vacuously True whenever the antecedent is False.

Worked Example 2

Given: Prove ¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan’s Law) using a truth table.
Step: For all 4 combinations of P, Q: at P=T,Q=T, ¬(P∧Q)=F and ¬P∨¬Q = F∨F = F, match. At P=T,Q=F, ¬(P∧Q)=T and ¬P∨¬Q = F∨T = T, match. The remaining two rows (P=F,Q=T and P=F,Q=F) both also give T on both sides by the same pattern.
Answer: All four rows match exactly, so ¬(P ∧ Q) ≡ ¬P ∨ ¬Q is a valid logical equivalence.

Worked Example 3

Given: Negate the quantified statement “All students passed the exam,” formally ∀x (Student(x) → Passed(x)).
Step: Apply ¬∀x P(x) ≡ ∃x ¬P(x), then push the negation through the implication using ¬(A → B) ≡ A ∧ ¬B: ¬∀x (Student(x) → Passed(x)) ≡ ∃x (Student(x) ∧ ¬Passed(x)).
Answer: The correct negation is “There exists a student who did not pass,” not “No students passed,” a common error that misapplies the quantifier flip.

Worked Example 4

Given: Determine whether P → Q and its converse Q → P are logically equivalent, using P = “it is a dog” and Q = “it is an animal.”
Step: P → Q (“if it’s a dog, it’s an animal”) is true for every dog. The converse Q → P (“if it’s an animal, it’s a dog”) is false for a cat, an animal that is not a dog.
Answer: P → Q and Q → P are not logically equivalent, a concrete counterexample (a cat) disproves the converse while the original implication still holds.

Why It Matters

Forms the mathematical foundation for boolean algebra, hardware digital logic gates, program conditionals, and formal software verification
Underlies database query languages, SQL’s WHERE clauses are propositional expressions, and relational calculus is built directly on predicate logic
Gives software engineers a rigorous way to reason about conditional logic bugs, most “the if-statement never triggers” bugs are traceable to a truth-table-checkable logic error
Trains precise reading of specifications and legal or contractual text, both of which frequently hinge on exactly how a nested “and”/“or”/“unless” clause should be parsed
Gives precise, unambiguous meaning to specifications and contracts, formal predicate logic removes the ambiguity that plain natural language leaves in requirements documents
Powers automated theorem provers and SAT/SMT solvers, tools that check whether a large propositional formula is satisfiable underpin modern hardware verification and program analysis
Provides the semantic backbone for programming language type systems, a type checker is, at its core, a predicate logic engine proving statements about a program’s structure
Makes formal contracts (preconditions, postconditions, invariants) precise enough to check automatically, rather than left as a paragraph of English in a doc comment
Underlies static analysis and linting tools, many warnings about unreachable code or always-true conditions are the tool applying propositional logic to the code’s control flow

Common Pitfalls

Confusing logical implication (P → Q) with causality, P → Q being True says nothing about P causing Q, only that they don’t co-occur as True-then-False
Misapplying De Morgan’s Laws when negating quantified predicates, forgetting to flip ∀ to ∃ (or vice versa) alongside negating the inner predicate
Treating the converse (Q → P) or inverse (¬P → ¬Q) as logically equivalent to the original implication P → Q, only the contrapositive (¬Q → ¬P) is actually equivalent
Forgetting that “or” in formal logic is inclusive by default, P ∨ Q is True when both are True, unlike the exclusive “either/or” sense common in everyday English
Assuming a statement true for one specific example proves a universally quantified claim, ∀x P(x) requires every case, not just the ones checked
Mixing up the order of nested quantifiers, ∀x ∃y P(x,y) and ∃y ∀x P(x,y) are generally not equivalent statements, even though they look similar
Reading ∃x P(x) as claiming exactly one x satisfies P, existential quantification only guarantees at least one, not uniqueness
Forgetting that an empty domain makes ∀x P(x) vacuously True and ∃x P(x) automatically False, regardless of what P says
Overusing implication where a biconditional is actually meant, “P if and only if Q” is a stronger, two-directional claim than a single “if P then Q”
Assuming a quantified statement’s truth transfers across different, unstated domains, “all birds can fly” quietly depends on which birds are in scope

Comparison

	Propositional Logic	Predicate Logic	Boolean Algebra	Natural Language
Atomic units	Whole statements (True/False)	Predicates over variables	Binary values (0/1)	Words and sentences
Quantifiers	None	`∀`, `∃`	None	Informal (“all,” “some”)
Expressiveness	Limited to fixed statements	Can express “for all x” and “there exists x”	Equivalent to propositional logic, applied to circuits	Highest, but ambiguous
Used for	Truth-functional reasoning	Formal specifications, math proofs	Digital circuit design	Everyday communication
Handles “for all”/“there exists”	No	Yes, natively	No	Informally, loosely
Verifiable by truth table	Yes, finite table	Not directly, domain can be infinite	Yes, finite table	No

Example

De Morgan’s Law, ¬(P ∧ Q) ≡ (¬P ∨ ¬Q), is used directly in code review: refactoring if (!(isValid && isReady)) into the equivalent, often more readable if (!isValid || !isReady) relies on exactly this logical identity holding for boolean expressions in any programming language.

SQL’s relational calculus, one of the formal foundations behind the relational database model, is built directly on predicate logic: a query like “find all customers where balance > 0” is a predicate P(x) evaluated over every row, and joins correspond to combining predicates over multiple relations.

Referenced by

Dig deeper

Spot an error in this note?