First-Order Logic

Propositional logic works with propositions, which are statements that, as a whole, are assigned either true or false.

In contrast, first-order logic (also known as predicate logic) works with predicates, which are statements that contain variables and can be true or false depending on the values of those variables. That is, first-order logic extends propositional logic by allowing formulae to depend on variables.

In turn, first-order logic allows us to express statements about objects and their properties, as well as relationships between objects.

Predicates and Quantifiers

A predicate is a function that takes one or more variables as input and returns a propositional formula:

Definition 27: Predicate

A predicate is a function $𝑃 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$ that takes $𝑛$ variables as input and returns a propositional formula. The variables $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}$ are called the arguments of the predicate.

Example.

Let

𝑃 (𝑥)

be the predicate “

𝑥

satisfies my special property.” A truth assignment

𝜎

over a predicate must now specify, for each possible value of

𝑥

, whether

𝑃 (𝑥)

is true or false. For example, if the domain of

𝑥

is the set of natural numbers, then

𝜎

must specify whether

𝑃 (0)

is true or false, whether

𝑃 (1)

is true or false, and so on.

Definition 28: Universal Quantifier

The universal quantifier $\forall$ is a logical operator that takes a variable and a proposition as input and produces a new proposition. The proposition $\forall 𝑥 𝑃 (𝑥)$ is true if and only if $𝑃 (𝑥)$ is true for every possible value of $𝑥$ .

Definition 29: Existential Quantifier

The existential quantifier $\exists$ is a logical operator that takes a variable and a proposition as input and produces a new proposition. The proposition $\exists 𝑥 𝑃 (𝑥)$ is true if and only if there exists at least one value of $𝑥$ such that $𝑃 (𝑥)$ is true.

Resource 3: Properties Involving Quantifiers

	Property	Equivalence
Negation Laws	Negation of $\forall$	$\neg \forall 𝑥 𝜑 \equiv \exists 𝑥 \neg 𝜑$
Negation Laws	Negation of $\exists$	$\neg \exists 𝑥 𝜑 \equiv \forall 𝑥 \neg 𝜑$
Distributivity Laws	Distributivity of $\forall$ over $\land$	$\forall 𝑥 (𝜑 \land 𝜓) \equiv \forall 𝑥 𝜑 \land \forall 𝑥 𝜓$
	Distributivity of $\exists$ over $\lor$	$\exists 𝑥 (𝜑 \lor 𝜓) \equiv \exists 𝑥 𝜑 \lor \exists 𝑥 𝜓$
	Non-distributivity of $\forall$ over $\lor$	$\forall 𝑥 (𝜑 \lor 𝜓) ≢ \forall 𝑥 𝜑 \lor \forall 𝑥 𝜓$
	Non-distributivity of $\exists$ over $\land$	$\exists 𝑥 (𝜑 \land 𝜓) ≢ \exists 𝑥 𝜑 \land \exists 𝑥 𝜓$
Commutativity Laws	Commutativity of $\forall$	$\forall 𝑥 \forall 𝑦 𝜑 \equiv \forall 𝑦 \forall 𝑥 𝜑$
Commutativity Laws	Commutativity of $\exists$	$\exists 𝑥 \exists 𝑦 𝜑 \equiv \exists 𝑦 \exists 𝑥 𝜑$