Back to Study Material Artificial Intelligence

First order logic

First order logic (FOL) is the standard formal language used in AI for representing knowledge about the world. It is called "first order" because quantific...

First order logic

The Language of AI Knowledge Representation

First order logic (FOL) is the standard formal language used in AI for representing knowledge about the world. It is called "first order" because quantification applies to individual objects, not to predicates or functions themselves (that would be higher-order logic). FOL is powerful enough to represent most everyday facts and relationships yet still admits automated reasoning procedures.

The syntax of FOL includes terms and sentences. Terms refer to objects: constants like "Paris," variables like x, and function applications like capitalOf(France). Atomic sentences apply predicates to terms: Population(Paris, 2000000) or GreaterThan(x, y). Complex sentences are built using logical connectives — AND, OR, NOT, IMPLIES, BICONDITIONAL — and the quantifiers for all and there exists.

The semantics of FOL defines meaning through an interpretation: a domain of objects, an assignment of individuals to constants, and an extension (set of true instances) for each predicate. A sentence is true or false relative to an interpretation.

A concrete example: the family relationships "Anne is the mother of Bob" and "every mother is a parent" can be expressed as Mother(Anne, Bob) and for all x, for all y, if Mother(x, y) then Parent(x, y). From these, an automated reasoner can derive Parent(Anne, Bob) through resolution.

Resolution refutation is the standard proof method for FOL. Sentences are converted to conjunctive normal form, and the resolution rule is applied repeatedly to find a contradiction with the negated goal, proving the goal must be true.

FOL is the basis of Prolog and many ontology languages. However, full FOL is semi-decidable: there is no guaranteed termination for all reasoning tasks.

Exam tip: Know the difference between FOL syntax (the formal language) and semantics (the meaning under an interpretation). Also know that FOL is semi-decidable while propositional logic is decidable — this distinction appears frequently in examinations.