From propositional to predicate calculus: terms, predicates, quantifiers

◈ 4 cards

Define constant / variable / function / predicate (with arity), atomic sentences, and ∀/∃; learn the Prolog case convention and why predicate calculus is more expressive — but undecidable.

Why propositional logic is not enough

Propositional calculus treats P as one opaque token, so to say "every man is mortal" you would need a separate symbol for each man — infinitely many. Predicate calculus fixes this by letting you look inside a claim and quantify over objects. Instead of one symbol P for "it rained Tuesday", you write weather(tuesday, rain), and then generalise with a variable: weather(X, rain) for any day X.

The four symbol kinds

Predicate calculus terms denote objects in the world; predicates denote relationships among objects.

Constant — names one specific object. By the textbook (and Prolog) convention, a constant begins with a lowercase letter: socrates, tuesday. The truth symbols true/false are reserved constants.
Variable — stands for an unspecified object; begins with an uppercase letter: X, Day. (Students reverse this constantly — burn it in: lowercase = constant, uppercase = variable.)
Function — a function symbol of arity $n$ applied to $n$ terms, e.g. father(socrates) or plus(2, 3). A function expression evaluates to an object, so it is a kind of term — it names a thing.
Predicate — a relationship of arity $n$ that is true or false, e.g. man(socrates) (arity 1), likes(peter, X) (arity 2).

Arity is the number of arguments. Two symbols with the same name but different arity are distinct: father/1 (the function "the father of") and father/2 (the predicate "X is the father of Y") are different entities.

An atomic sentence is a predicate of arity $n$ followed by $n$ terms in parentheses — the smallest unit with a truth value, the leaf of the grammar. Everything built from connectives and quantifiers is a compound sentence.

Quantifiers

Variables become meaningful only when quantified:

Universal $\forall X s$ — $s$ holds for every value of $X$ in the domain. $\forall X (man (X) \to m or t a l (X))$ = "all men are mortal".
Existential $\exists Y s$ — $s$ holds for at least one value. $\exists Y f r i e n d s (Y, p e t er)$ = "someone is a friend of Peter".

A variable not inside any quantifier's scope is free; a sentence with every variable quantified is closed; a sentence with no variables at all is ground (e.g. man(socrates)). In AI usage all variables must be quantified.

Worked example: expressing two rules

"Every man is mortal" becomes the universally quantified implication $\forall X (man (X) \to m or t a l (X))$ . "Someone is a friend of Peter" becomes the existential $\exists Y f r i e n d s (Y, p e t er)$ . Note peter is lowercase (a constant — a specific person) while X and Y are uppercase (variables ranging over the domain).

The price of expressiveness: undecidability

The trade-off is sharp. Propositional calculus is decidable — a truth table is finite and always terminates. Predicate calculus is undecidable in general: deciding whether $\forall X P (X)$ holds may require testing every $X$ , and if the domain is infinite that test may never halt. This is why AI inference engines use sound, complete-but-non-terminating proof procedures and bound the domain in practice.