What First-Order Logic Lets an AI System Say, and What It Cannot

What first-order logic can express, why provers may never finish, and how OWL 2 and Prolog keep logic usable in AI systems.

Guide: AI BasicsLast verified: October 20266 min read

First-order logic is a formal language for stating facts about objects and the relations between them, using constants, variables, predicates, functions, the usual connectives, and the quantifiers "for all" and "there exists." Kurt Gödel's 1930 completeness theorem guarantees that every valid sentence has a proof, but Alonzo Church and Alan Turing showed in 1936 that no algorithm can decide validity for every sentence. A logic-based AI program therefore gets exact answers when it finds a proof, and may search without end when no proof exists.

Key takeaways

  • Quantifiers let one sentence cover every object in a domain, which propositional logic cannot do without listing each object.
  • Completeness means a proof procedure can find a proof of any valid sentence, given enough time.
  • Church and Turing (1936) proved that no single procedure can always decide whether a sentence is valid.
  • Description logics, the basis of the W3C's OWL 2 DL, trade some expressive power for better computational behavior.
  • First-order logic hand-codes knowledge. It does not learn from examples the way machine learning does.

What the quantifiers add

Propositional logic treats each statement as an indivisible true-or-false unit. To say that every course in a catalog has a prerequisite, it needs one separate statement per course. First-order logic breaks a statement into parts: names for objects (the constants), variables that stand for any object, predicates that describe objects or relate them, and functions that build new terms such as mother(ann). The Stanford Encyclopedia of Philosophy's entry on classical logic presents the same building blocks, plus an identity symbol and the two quantifiers.

The payoff is that a short sentence can speak about an unbounded domain. The table shows three translations from English. The second row also shows the most common beginner error: pairing "for all" with "and" instead of "if-then," which wrongly claims that everything is a student.

English sentenceFirst-order formulaNote
Every student who passed has a transcript.∀x ((Student(x) ∧ Passed(x)) → HasTranscript(x))A universal claim usually takes an if-then form.
Some student passed.∃x (Student(x) ∧ Passed(x))An existential claim usually takes an "and" form. Writing it with "if-then" makes it true whenever any non-student exists.
Everyone has a mother.∀x ∃y Mother(y, x)Swapping the quantifiers to ∃y ∀x would claim one person is everyone's mother.

The formulas are illustrative examples written for this article, not taken from a published system.

What completeness guarantees

Gödel's completeness theorem, published in 1930, says that a consistent set of first-order sentences has a model, and combined with soundness it means a sentence is provable exactly when it is valid. The practical meaning for AI is that a theorem prover working systematically will eventually reach a proof of any true consequence. Two further results follow from the same machinery. Compactness says a set of sentences has a model if every finite subset does. The Löwenheim-Skolem theorems say that a satisfiable set of sentences in a countable language has a model with a finite or countably infinite domain, and that a set with arbitrarily large finite models also has models of every larger infinite size. First-order sentences therefore cannot pin down what "countably infinite" or "uncountable" means.

Where it stops being decidable

Completeness is a statement about valid sentences only. In 1936 Church published a note showing that the first-order functional calculus has no decision method, and Turing reached the same conclusion in his paper on computable numbers the same year. The Stanford Encyclopedia of Philosophy's entry on the Church-Turing thesis records both results and adds that Hilbert and Bernays gave a separate proof in 1939. Combined with completeness, the consequence for software is lopsided: a valid claim can be confirmed by search, but when a claim is not provable the search may never return. Real provers handle this with time limits, and an answer of "no result" does not mean "false."

The annual CADE ATP System Competition (CASC) shows what that looks like in practice. Its site describes it as the yearly evaluation of fully automatic, classical logic theorem provers. Its reports go back to the 1997 conference, and the thirtieth edition is the latest listed, so provers have been compared head to head for decades.

Keeping the logic computable

Much practical work uses a restricted fragment of first-order logic whose reasoning problems are better behaved. The W3C's OWL 2 Web Ontology Language became a W3C Recommendation on December 11, 2012. The OWL 2 overview says its Direct Semantics is compatible with the SROIQ description logic, which it calls a fragment of first-order logic with useful computational properties. Three sub-languages, called profiles, make further trades. OWL 2 EL supports polynomial-time reasoning for large ontologies, and the W3C profiles document says its class constructors are sufficient to express SNOMED CT, a very large biomedical ontology. OWL 2 QL allows queries to be rewritten for ordinary relational databases. OWL 2 RL suits rule-based engines.

Prolog sits at the other end of the same family. Programs are written as facts and rules, and the language is defined in ISO/IEC 13211-1, published in 1995 and still the current edition after a review in 2024. The matching step inside both Prolog and resolution provers is covered in a separate article on unification.

What it does not do

First-order logic stores knowledge that a person wrote down. A sentence like the ones in the table appears in a system only because an engineer entered it or a pipeline extracted it, and the logic itself does not estimate probabilities or improve with data. The quality of the answers depends on the rules being complete and correct, which is a labor cost that grew with every domain it was applied to. This is one reason statistical methods took over many tasks, while logic remained in places where an auditable chain of reasoning matters: formal verification, configuration checking, and structured knowledge bases.

A reader judging a claim about "logic-based AI" can ask four questions:

  • Which fragment is used: full first-order logic, a description logic, or rules only?
  • Who wrote the knowledge, and how is it kept current?
  • What happens when the prover cannot decide a query within its time limit?
  • Is any part of the system statistical, and if so, where does the logic end?

FAQ

Is first-order logic the same as predicate logic?

In most textbooks the terms are used interchangeably for the logic with quantifiers over individual objects. Higher-order logics also quantify over properties or sets, and the Stanford Encyclopedia entry notes that second-order logic under its standard semantics has no sound and complete deductive system.

Can a computer always decide whether a first-order statement is true?

No. A search can confirm that a valid sentence is provable, but Church and Turing showed in 1936 that no procedure decides validity for all sentences. Restricted fragments, such as many description logics, are chosen so that decisions are possible.

Does modern machine learning use first-order logic?

Mostly not. Neural networks learn numeric parameters from data. Logic appears alongside them in hybrid designs and in knowledge bases, but a claim that a given product reasons in first-order logic needs a source that names the fragment and the prover.

Where is the logic standardized?

Two public standards cover different corners. The W3C defines OWL 2 for ontologies on the web, and ISO/IEC 13211-1 defines the core of Prolog.

Last verified: October 2026

Sources

  • Classical Logic, Stanford Encyclopedia of Philosophy, Stanford University
  • The Church-Turing Thesis, Stanford Encyclopedia of Philosophy, Stanford University
  • OWL 2 Web Ontology Language Document Overview (Second Edition), W3C Recommendation, December 11, 2012
  • OWL 2 Web Ontology Language Profiles (Second Edition), W3C Recommendation, 2012
  • ISO/IEC 13211-1:1995, Information technology, Programming languages, Prolog, Part 1: General core, ISO and IEC
  • CADE ATP System Competition (CASC), TPTP project

New to artificial intelligence?

Start with the basics, then follow the guides to tools, rules, and effects on society.

Start with AI Basics