Predicate
Logic ∀∃

§0Why We Need Predicate Logic

Propositional logic treats each statement as an indivisible atom — P, Q, R. That's powerful for reasoning about how whole statements combine, but it is blind to internal structure. Consider the most famous argument in logic:

In propositional logic this is just three unrelated atoms, P, Q, R, and the inference P, Q ∴ R is plainly invalid. Yet the argument is obviously, undeniably valid. The validity lives inside the sentences — in the objects (Socrates), the properties (being human, being mortal), and the word "all."

Predicate logic (also first-order logic, FOL, or the predicate calculus) opens the atom. It can name individuals, ascribe properties and relations to them, and — crucially — quantify: say things about all objects or some object. It is expressive enough to formalize essentially all of mathematics, and it is the backbone of databases, AI knowledge representation, program verification, and automated theorem proving.

§1The Vocabulary of First-Order Logic

FOL adds several new kinds of symbol to the propositional connectives you already know.

Terms vs. formulas

A term names an object: a constant, a variable, or a function applied to terms. A formula says something true or false: a predicate applied to terms (an atomic formula), or such atoms combined with connectives and quantifiers. The litmus test: a term refers; a formula asserts.

§2Quantifiers, Scope & Binding

The two quantifiers are the heart of FOL.

Over a finite domain the quantifiers are just iterated connectives. If the domain is {a, b, c}, then:

This is precisely why ∀ becomes all() and ∃ becomes any() when we model logic in Octave.

Scope, free & bound variables

The scope of a quantifier is the sub-formula it governs. A variable occurrence is bound if it lies in the scope of a quantifier using that variable, and free otherwise. A formula with no free variables is a sentence — only sentences have a definite truth value in a model.

§3Translating English into FOL

Translation is the skill that takes the most practice. Master four canonical patterns and most sentences fall into place.

Practice — tap a card to reveal the formula

§4Models, Interpretations & Truth

A propositional formula's truth depends only on a row of T/F values. A first-order formula's truth depends on a richer thing: a model (or structure, or interpretation).

For example, let D = {1, 2, 3, 4, 5}, interpret Even as {2, 4} and Prime as {2, 3, 5}. Then ∃x (Even(x) ∧ Prime(x)) is true (witness: 2), while ∀x (Even(x) → Prime(x)) is false (4 is even but not prime).

◆The World Evaluator

Below is a visible model — a little universe of five objects, a through e, each with a shape, size, and colour, arranged left to right. Type any first-order sentence and the engine evaluates it against this world, showing the verdict plus which objects act as witnesses or counterexamples. Switch worlds to see truth values change.

§6Multiple Quantifiers & Why Order Matters

The real expressive power — and the real subtlety — of FOL appears when quantifiers nest. Reading order is everything: ∀x ∃y and ∃y ∀x say genuinely different things.

You can witness this directly in the evaluator. Try ∀x ∃y Larger(y, x) ("everything has something larger") versus ∃y ∀x Larger(y, x) ("something is larger than everything"). Both are false in our worlds, but for different reasons — and the per-object breakdown shows you exactly which object breaks each one.

§7Quantifier Negation & Equivalences

The quantifiers are duals: each is the negation of the other with a flipped inner negation. This is De Morgan's law lifted to predicate logic.

To push a negation through a string of quantifiers, flip every quantifier and move the negation inward:

Other useful first-order equivalences (provided the swapped variable does not occur free in the displaced part):

⚠ Caution: ∀ does not distribute over ∨, and ∃ does not distribute over ∧. "Everyone is rich or poor" ≠ "everyone is rich, or everyone is poor."

§8Properties of Relations

Binary predicates let us define the structural properties that pervade mathematics. Each is a one-line first-order sentence about a relation R.

In the Octave lab you'll test all three properties of a relation by simple matrix operations.

§9Identity & Counting

Adding the identity relation = (true exactly when both terms denote the same object) lets first-order logic count — something no predicate alone can do.

Identity also formalizes definite descriptions. Russell analyzed "the present King of France is bald" as: there exists exactly one king of France, and he is bald — ∃x (King(x) ∧ ∀y(King(y) → y = x) ∧ Bald(x)). Since no such king exists, the sentence is simply false, dissolving a famous puzzle.

§10Quantifier Rules of Inference

Natural deduction extends to predicate logic with four rules for introducing and eliminating quantifiers. Each comes with a restriction that prevents fallacies.

The Socrates argument, finally proved

1.  ∀x (Human(x) → Mortal(x))     (premise)
2.  Human(socrates)               (premise)
3.  Human(socrates) → Mortal(socrates)   (1, Universal Instantiation)
4.  Mortal(socrates)              (2, 3, Modus Ponens)    ∴ proved

This is the argument propositional logic could not touch. Predicate logic validates it in four lines.

§11Proof Strategy, Prenex Form & Decidability

A typical first-order proof strips quantifiers off the premises (UI / EI), works in propositional logic on the instances, then re-attaches quantifiers on the conclusion (UG / EG). A second worked example — proving ∃x R(x) from ∀x (S(x) → R(x)) and ∃x S(x):

1.  ∀x (S(x) → R(x))     (premise)
2.  ∃x S(x)              (premise)
3.  S(c)                 (2, Existential Instantiation — c fresh)
4.  S(c) → R(c)          (1, Universal Instantiation)
5.  R(c)                 (3, 4, Modus Ponens)
6.  ∃x R(x)              (5, Existential Generalization)   ∴ proved

Prenex normal form

Every first-order formula is equivalent to one in prenex normal form: all quantifiers pulled to the front, followed by a quantifier-free matrix, e.g. ∀x ∃y ∀z (… ). The recipe: rename variables apart, push negations in with quantifier-negation laws, then migrate quantifiers outward. Skolemization goes further, replacing each existential with a function of the universals before it — the key preprocessing step for automated theorem provers.

§12The GNU Octave Predicate-Logic Lab

GNU Octave models first-order logic beautifully over a finite domain. Unary predicates become logical vectors; binary relations become logical matrices. The universal quantifier is all(), the existential is any(), and the conditional is ~A | B. Copy any block into Octave (or the free sandbox at octave-online.net) and run it.

Lab 1 — Predicates as vectors; ∀ and ∃

% Domain = {1,2,3,4,5}. Predicates are logical vectors over the domain.
domain = 1:5;
Cube  = logical([1 1 0 0 0]);   % objects 1,2 are cubes
Small = logical([0 1 0 1 1]);

printf('∃x Cube(x)            : %d\n', any(Cube));      % exists a cube
printf('∀x Small(x)           : %d\n', all(Small));     % all are small
printf('∀x (Cube(x)->Small(x)): %d\n', all(~Cube | Small));   % all cubes small?
printf('∃x (Cube(x)&Small(x)) : %d\n', any(Cube & Small));   % some small cube?

Lab 2 — Quantifier negation (the duals)

P = logical([1 1 0 1 1]);
printf('¬∀x P(x)  ==  ∃x ¬P(x) ?  %d\n', (~all(P)) == any(~P));
printf('¬∃x P(x)  ==  ∀x ¬P(x) ?  %d\n', (~any(P)) == all(~P));

Lab 3 — Binary relations & nested quantifiers

A relation is a matrix: R(i,j)=1 means object i relates to object j. Watch ∀x∃y and ∃y∀x come apart.

% sizes of objects 1..5 (2 = large, 1 = small)
sz = [2 1 2 1 1];
R  = bsxfun(@gt, sz', sz);       % R(i,j) = Larger(i,j) = sz(i) > sz(j)

printf('∀x∀y Larger(x,y) : %d\n', all(all(R)));
printf('∃x∃y Larger(x,y) : %d\n', any(any(R)));
% ∀x ∃y R(x,y): every object is larger than something? (each ROW has a 1)
printf('∀x∃y Larger(x,y) : %d\n', all(any(R, 2)));
% ∃y ∀x R(x,y): something larger than EVERY object? (some COLUMN all 1s)
printf('∃y∀x Larger(x,y) : %d\n', any(all(R, 1)));

Lab 4 — Reflexive, symmetric, transitive

% colour codes for objects 1..5 (1=red, 2=blue, 3=green)
col = [1 2 2 1 3];
S = bsxfun(@eq, col', col);     % SameColor(i,j)

reflexive  = all(diag(S));            % ∀x R(x,x)
symmetric  = isequal(S, S');           % ∀x∀y (R(x,y)->R(y,x))
twostep    = (double(S) * double(S)) > 0;   % reachable in 2 steps
transitive = all(all(~twostep | S));   % ∀x∀y∀z chain rule

printf('SameColor:  reflexive=%d  symmetric=%d  transitive=%d\n', ...
        reflexive, symmetric, transitive);
% all three true => SameColor is an equivalence relation

Lab 5 — Identity & numerical quantifiers

Cube  = logical([1 1 0 0 0]);
Green = logical([0 0 0 0 1]);

printf('∃x P(x)  at least one cube : %d\n', sum(Cube) >= 1);
printf('at least TWO cubes         : %d\n', sum(Cube) >= 2);
printf('∃!x exactly one green      : %d\n', sum(Green) == 1);
% Uniqueness as identity:  ∃x(P(x) & ∀y(P(y) -> y=x))  <=>  sum(P)==1

◆Self-Test Quiz

Ten questions across the whole course. Click an answer for instant feedback and an explanation.

§Symbol & Syntax Reference