Например, мы можем определить предикатную сигнатуру

объявляя a объектной константой, P – унарной предикатной константой, и Q – бинарной предикатной константой.

Возьмём предикатную сигнатуру s, которая включает по крайней мере одну предикатную константу и не включает ни одного из следующих символов:

• объектные переменные x, y, z, x₁, y₁, z₁, x₂, y₂, z₂, ...,
• пропозициональные связки,
• квантор всеобщности " и квантор существования $,
• скобки и запятая.

Алфавит логики предикатов состоит из элементов из s и четырёх групп дополнительных символов, указанных выше. Строка – это конечная последовательность символов из этого алфавита.

Терм – это объектная константа или объектная переменная. Строка называется атомарной формулой, если она является пропозициональной константой или имеет вид R(t₁, ..., t_n), где R – предикатная константа арности n (n > 0) и t₁, ... , t_n – термы. Например, если мы рассматриваем сигнатуру (4), то P(a) и Q(a, x) – атомарные формулы.

Множество X строк замкнуто относительно правил построения (для логики предикатов), если

• каждая атомарная формула принадлежит X,
• для любой строки F если F принадлежит X, то F тоже принадлежит,
• для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G),
• для любого квантора K, любой переменной v и любой строки F если F принадлежит X, то также принадлежит Kv F.

Строка F является (предикатной) формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.