From propositional to predicate calculus: terms, predicates, quantifiers

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 mortal(X))$ = "all men are mortal". - Existential $\exists Y\,s$ — $s$ holds for *at least one* value. $\exists Y\,friends(Y, peter)$ = "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 mortal(X))$. "Someone is a friend of Peter" becomes the existential $\exists Y\,friends(Y, peter)$. 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.