Understanding First-Order Logic
Propositional logic can only combine indivisible whole statements. It can say that it is raining and that the ground is wet, but it has no way to talk about objects and their relationships, and no way to state a general rule that applies to every object of a kind. Each instance would need writing out separately.
First-order logic adds the missing structure. Terms name objects, predicates express properties and relations among them, functions map objects to objects, and quantifiers range over objects. The universal quantifier asserts something of every object, the existential asserts the existence of at least one. This is what lets a single sentence capture a general rule.
Sentences of this kind form a knowledge base against which inference can be performed: deriving conclusions that follow necessarily from what is asserted. A sound inference procedure derives only true consequences, and a complete one can derive every consequence that follows. Automated theorem provers implement such procedures, most commonly by resolution.
The expressiveness has costs. Inference in first-order logic is semi-decidable, so a procedure can confirm entailment but may run forever on a non-entailed query. And the logic is categorical: a statement is true or false, with no way to express that something is merely probable. Representing uncertainty is precisely why probabilistic frameworks such as Bayesian networks exist alongside logical ones.
Example of First-Order Logic
The rule "every student who passes the exam receives a certificate" is a single first-order sentence quantified over all objects: for every x, if x is a student and x passes, then x receives a certificate. Propositional logic would need one separate statement per student.
Adding the specific facts that Amina is a student and that Amina passed lets an inference procedure derive that Amina receives a certificate. The conclusion was never stated; it follows necessarily from the general rule together with the particular facts.
The framework is rigid in a revealing way. "Most students who pass receive a certificate" cannot be expressed at all: first-order logic offers only "all" and "some". Representing that middle ground requires probability, which is one of the main reasons purely logical approaches were supplemented by probabilistic ones.
Frequently Asked Questions
How does first-order logic differ from propositional logic?
Propositional logic treats statements as indivisible atoms. First-order logic decomposes them into objects, predicates, and functions, and adds quantifiers, so a single sentence can state a general rule over all objects rather than enumerating cases.
What do soundness and completeness mean for an inference procedure?
Soundness means everything it derives genuinely follows from the knowledge base. Completeness means everything that follows can eventually be derived. Both are desirable; for first-order logic, complete procedures exist but may not terminate on queries that do not follow.
Why is uncertainty a problem for logical representation?
Because every sentence is simply true or false. A rule admitting exceptions cannot be stated without either being wrong or being cluttered with explicit exception conditions. Probabilistic representations handle degrees of belief directly, which is why they largely displaced purely logical ones for reasoning under uncertainty.
The Bottom Line
First-order logic represents knowledge as objects, relations, and quantified rules, supporting inference that derives what necessarily follows. It is far more expressive than propositional logic, but it is computationally demanding and has no native way to express uncertainty.