Home

FOL

First-order logic (FOL) is a formal system for specifying and reasoning about objects and their relations. It extends propositional logic by introducing quantifiers and predicates, enabling statements about mathematical structures, graphs, and the natural world.

The language of FOL includes a nonempty domain, constant symbols, function symbols, and predicate symbols with

An interpretation assigns a domain and meanings to function and predicate symbols: functions map tuples to

FOL uses deductive systems, such as natural deduction or sequent calculus. Gödel’s completeness theorem states that

Key results include the compactness and Löwenheim–Skolem theorems. FOL is more expressive than propositional logic, yet

FOL underpins much of mathematics, computer science, formal verification, and knowledge representation. Its development culminated in

specified
arities.
Terms
are
built
from
constants
and
function
symbols;
atomic
formulas
have
the
form
P(t1,...,tn).
Formulas
are
formed
from
atomic
formulas
with
connectives
(and,
or,
not,
implies)
and
quantifiers
(for
all,
exists).
A
sentence
has
no
free
variables.
domain
elements;
predicates
denote
relations
on
the
domain.
Truth
of
a
formula
is
relative
to
an
interpretation,
and
to
a
variable
assignment
for
free
variables.
A
theory
is
a
set
of
sentences;
a
model
satisfies
all
sentences
of
the
theory.
every
valid
sentence
is
provable,
and
every
provable
sentence
is
valid.
In
general,
FOL
validity
is
undecidable,
but
the
set
of
valid
sentences
is
recursively
enumerable.
cannot
capture
finiteness
in
a
single
sentence
and
admits
nonstandard
models
of
familiar
theories.
the
work
of
Frege,
and
later
Gödel,
Löwenheim,
Skolem,
and
many
others
in
the
20th
century.