Monday, September 26, 2011 CC-BY-NC
Introduction to predicate logic

Maintainer: admin

1Something about boolean algebras

If $B$ is a finite boolean algebra and $A = \{a_1, \ldots, a_n\}$ is the set of atoms of $B$, then the map taking $b$ to $\{x \in A, x \subseteq b\}$ is an isomorphism of partial orders.

That is, $f$ is a bijection between $B$ to $\mathcal{P}(A) (f(\bot) = \varnothing)$ and for $b, b' \in B, b \leq b' \iff f(b) \subseteq f(b')$

2Predicate logic

2.1Logical symbols

  • Connectives ($\lnot, \land, \lor, \to, \iff$ as before)
  • Variables ($x,y,x', \bar{y}, z, \ldots$)
  • Brackets ($(,)$)
  • Quantifiers ($\exists, \forall$)
  • The equality symbol ($=$)


A signature is a collection of non-logical symbols, each with an assigned kind and arity1.

2.2.1Types of symbols

  • Constant symbols ($c, d', \ldots$)
  • For each $n$, an $n$-ary function symbol that stands for a function $\mathcal{M}^n \to \mathcal{M}$ where $\mathcal{M}$ is part of the underlying set. The arity is part of the signature. not really sure what this is saying
  • For each $n$, an $n$-ary predicate symbol $P,Q \ldots$ (stand for subsets of $\mathcal{M}^n$

Note: We treat these non-logical symbols as prefix operators. For instance, we would write $+x3$, not $x+3$.

2.2.2An example

Suppose your structure is the Euclidean plane.

"$x$ is between $y$ and $z$

$Bxyz$ for some predicate symbol $B$

Note: the signature may be empty or have just one of the above kinds or two or all three!


Given a signature $\Sigma$, a term is one of the following:

  1. Any variable or function symbol
  2. for any $n$-nary function symbol $f$ and term $t_1, \ldots t_n$ we have a term $ft_1, \ldots, f_n$

The standard signature for studying $\mathbb{N}$ has $\{0, S, +, \cdot, <\}$, where:

  • $0$ is a constant
  • $S$ is a unary function symbol (the successor function; informally, $Si = (i + 1)$)
  • $+, \cdot$ are binary function symbols
  • $<$ is a binary predicate symbol
  1. The number of inputs for a function. Unary, binary, ternary, etc.