First-Order Logic — Definition, Formula & Examples

First-order logic is a system of formal logic that extends propositional logic by introducing quantifiers ("for all" and "there exists") and predicates that can express properties of objects and relationships between them.

First-order logic (also called predicate logic) is a formal language consisting of variables ranging over a domain of discourse, predicate symbols, function symbols, logical connectives ( $\land, \lor, \neg, \rightarrow, \leftrightarrow$ ), and the universal quantifier $\forall$ and existential quantifier $\exists$ , together with a deductive system for deriving valid conclusions from well-formed formulas.

Key Formula

\forall x\, (P(x) \rightarrow Q(x))

Where:

$\forall$ = Universal quantifier, meaning "for all"
$x$ = A variable ranging over the domain of discourse
$P(x)$ = A predicate asserting a property of x
$Q(x)$ = Another predicate asserting a property of x
$\rightarrow$ = Conditional (if...then)

How It Works

In first-order logic, you build statements using predicates applied to variables and then bind those variables with quantifiers. A predicate like

P(x)

asserts a property about

x

, such as "

x

is even." The expression

\forall x\, P(x)

claims the property holds for every element in the domain, while

\exists x\, P(x)

claims at least one element satisfies it. You combine these with logical connectives to form complex statements. Negating quantified statements swaps the quantifier:

\neg(\forall x\, P(x))

is equivalent to

\exists x\, \neg P(x)

Example

Problem: Let the domain be all integers. Translate into first-order logic: "Every even integer is divisible by 2." Then write its negation.

Define predicates: Let E(x) mean "x is even" and D(x) mean "x is divisible by 2."

Translate the statement: "Every even integer is divisible by 2" becomes: for all x, if x is even then x is divisible by 2.

\forall x\, (E(x) \rightarrow D(x))

Negate the statement: Push the negation inward: the universal quantifier becomes existential, and the conditional is negated.

\exists x\, (E(x) \land \neg D(x))

Answer: The original statement is

\forall x\, (E(x) \rightarrow D(x))

. Its negation is

\exists x\, (E(x) \land \neg D(x))

, meaning "there exists an even integer that is not divisible by 2."

Why It Matters

First-order logic is the standard language for writing mathematical proofs, defining database queries (SQL is rooted in it), and specifying properties in software verification. Mastering it is essential for discrete mathematics, abstract algebra, and any course that requires rigorous proof techniques.

Common Mistakes

Mistake: Negating

\forall x\, P(x)

\forall x\, \neg P(x)

instead of

\exists x\, \neg P(x)

Correction: Negation flips the quantifier. "Not everything has property P" means "something lacks property P," so use

\exists x\, \neg P(x)