Predicate Logic

Overview

Predicate logic is a logical system that uses quantified variables over non-logical objects. A predicate is a sentence with some number of free variables. A predicate with free variables “plugged in” is a proposition.

Quantification

A quantifier refers to an operator that specifies how many members of a set satisfy some formula. The most common quantifiers are $\exists$ and $\forall$, though others (such as the counting quantifier) are also used.

Existentials

Existential quantification ($\exists$) asserts the existence of at least one member in a set satisfying a property.

Uniqueness

We can also denote existence and uniqueness using $\exists !$. For example, $\exists !x,P(x)$ indicates there exists a unique $x$ satisfying $P(x)$, i.e. there is exactly one $x$ such that $P(x)$ holds: $(\exists !x,P(x))=(\exists x,P(x))\wedge (\forall x,\forall y,(P(x)\wedge P(y))\Rightarrow (x=y)))$ The first conjunct denotes existence while the second denotes uniqueness.

Counting

Counting quantification (${\exists }^{=k}$ or ${\exists }^{\ge k}$) asserts that (at least) $k$ (say) members of a set satisfy a property.

Universals

Universal quantification ($\forall$) asserts that every member of a set satisfies a property.

Identifiers

Identifiers are said to be bound if they are parameters to a quantifier. Identifiers that are not bound are said to be free. A first-order logic formula is said to be in prenex normal form (PNF) if written in two parts: the first consisting of quantifiers and bound variables (the prefix), and the second consisting of no quantifiers (the matrix).

Bibliography

• Gries, David. The Science of Programming. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981.
• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.
• Patrick Keef and David Guichard, “An Introduction to Higher Mathematics,” n.d.