Does first-order logic require numbers?

No. Its objects can represent people, components, documents or other entities, with predicates describing their relationships.

Does an existential statement identify a named object?

Not necessarily. It states that a suitable object exists under the interpretation; further information may be needed to identify it by a particular name.

Can a reasoner always answer every first-order question?

No. Unrestricted entailment has fundamental decidability limits, although restricted languages and particular problems can be handled effectively.

AI Glossary / Graphs and symbolic AI / Intermediate

First-order logic

Definition

First-order logic is a formal language for describing objects, their properties and relationships, and statements quantified over those objects. It extends propositional logic with variables, predicates, functions and quantifiers. Its defined syntax and semantics let reasoning systems determine which conclusions follow from a set of premises.

What it means

Propositional logic treats whole statements as named units. First-order logic exposes structure inside them: who owns an item, which component belongs to a device, or whether every request has a reviewer. A general rule can apply to many objects without listing a separate version for each name.

The word first-order means its ordinary quantifiers range over objects in a domain, not directly over all properties or relations. It does not mean first in time, a beginner's approximation or a numerical optimization order. The language's precision concerns reasoning from premises; it does not verify that the premises accurately describe the real world.

How it works

Constants name objects, variables range over domain elements, predicates describe properties or relations, and function symbols denote object-valued mappings. Connectives such as and, or, not and implies combine statements. The universal quantifier means “for every,” while the existential quantifier means “there exists.”

An interpretation supplies the domain and meanings of the symbols. A statement's truth is evaluated relative to that interpretation. A knowledge base entails a conclusion when the conclusion is true in every interpretation satisfying the premises.

Inference procedures manipulate these formal expressions. Some useful fragments support efficient reasoning, while unrestricted first-order entailment is only semidecidable: a complete proof procedure can eventually establish valid entailments, but it may fail to terminate when a requested entailment does not hold. Practical systems therefore choose fragments, resource limits or specialized reasoning methods appropriate to their tasks.

Three practical examples

1. A parts knowledge base states that every sensor is a component. From Sensor(S7), a reasoner can infer Component(S7), assuming the rule and assertion are accepted.

2. A workflow model expresses that each submitted request has some assigned reviewer. The formula must distinguish that condition from requiring one single reviewer to cover every request.

3. A verification exercise represents relationships between objects and checks whether a proposed conclusion follows. A proof establishes consistency with the encoded premises, not that the encoding captures every requirement of the real system.

Think of it this way

Think of a carefully defined grammar for writing rules about a cast of objects. Names identify the cast, relationship words connect them, and quantifiers specify whether a statement concerns every member or at least one. The analogy helps explain construction. Formal logic goes further by giving precise truth conditions and inference rules rather than depending on readers to resolve ambiguity.

Worked example

Suppose the domain contains people and documents. Let Reviews(p,d) mean person p reviews document d, and let Person(p) and Document(d) identify the relevant categories.

The statement “every document has a reviewer” can be written: for every d, if Document(d), then there exists p such that Person(p) and Reviews(p,d). Different documents may have different reviewers. In contrast, “one person reviews every document” says there exists p such that Person(p) and, for every d, Document(d) implies Reviews(p,d).

Consider two documents A and B and two people Mira and Noor. Mira reviews only A; Noor reviews only B. Every document has a reviewer, so the first statement is true. No person reviews both documents, so the second is false. The example demonstrates why changing quantifier order changes meaning. It does not require reviewers to be distinct in the first formula; the same person could review several documents if the relationship allowed it.

Illustrative case study

Fictional case study: Oak Knowledge encodes an internal assignment rule. Its first formula accidentally requires a single reviewer for all requests, although the intended rule only requires each request to have a reviewer. A small two-request example exposes the mismatch.

The team rewrites the quantifier order and adds examples that should satisfy the rule and examples that should violate it. It also records whether missing assignments are unknown or considered absent by the application. The case illustrates formalization review, without claiming that the resulting knowledge base validates real policies or handles every exception.

Common misconceptions and mistakes

Universal and existential quantifiers are not interchangeable, and their order often matters. Another common mistake is using “and” where a universal rule needs “implies”: saying every object is a sensor and tested is much stronger than saying every sensor is tested.

Ordinary first-order logic does not automatically assign probabilities to uncertain statements. It also does not impose a universal closed-world assumption: a missing assertion need not be false. Function symbols require a defined interpretation, and constants need not name distinct objects unless the model or additional axioms establish distinctness. Familiar-looking notation should not hide these semantic choices.

Business use

First-order logic can clarify complex relationships and provide a foundation for knowledge representation or formal verification. Start by defining the domain, vocabulary and intended rule meanings. Test formulas against small situations before relying on large automated proofs.

Choose a reasoning fragment and tool suited to the required queries, and record resource limits. Preserve the distinction between no proof found, a demonstrated counterexample and a verified entailment. Keep input provenance and model assumptions available to reviewers. The main value is explicit, checkable reasoning over a defined representation, supported by careful work on what that representation means.

Check your understanding

If Mira reviews A and Noor reviews B, does that establish that one person reviews every document?

Answer: No. It supports a reviewer for each of the two documents, but neither person is stated to review both. The existential-universal claim is stronger than the universal-existential claim here.

Related terms

Learn next

Translate several everyday rules using predicates and quantifiers, then construct small counterexamples to alternative quantifier orders. Study unification and resolution afterward, keeping the meaning of formulas separate from the procedures used to prove consequences.

Sources

Primary sources: Russell and Norvig, first-order logic and inference teaching material: https://aima.cs.berkeley.edu/slides-pdf/chapter08.pdf and https://aima.cs.berkeley.edu/slides-pdf/chapter09.pdf . These support syntax, semantics, quantification and inference limits. The reviewer example and fictional case are original teaching material.

Previous: First order interaction Next: First-order Markov process