# Logic for Computer Scientists/Predicate Logic/Syntax

## Definition 1 (Syntax of predicate logic - Terms)

Assume a

• countable set of function symbols ${\displaystyle \{f{_{i}}^{k}\mid i,k=1,2,3,\cdots \}}$
• a countable set of ${\displaystyle \{x_{i}\mid i=1,2,3,\cdots \}}$

The set of terms is defined by the following induction:

• Variables ${\displaystyle x_{i}}$ are terms.
• If ${\displaystyle t_{1},\cdots ,t_{k}}$ are terms and ${\displaystyle f_{i}^{k}}$ is a function symbol, then ${\displaystyle f_{i}^{k}(t_{1},\cdots ,t_{k})}$ is a term.

Terms of type ${\displaystyle f_{i}^{0}()}$ are special ones, they are called constants. In this case we omit the braces and denote them as ${\displaystyle f_{i}^{0}}$.

Terms are the syntactic counterpart of the above mentioned objects. Constants will denote the elements of the domain and function symbols will denote a way to refer to such objects.

The following definition introduces the formulae.

## Definition 2 (Syntax of predicate logic - Formulae)

Assume a countable set of predicate symbols${\displaystyle \{p_{i}^{k}\mid i=1,2,3,\cdots \}}$. The set of (well-formed) formulae is defined by the following induction:

• If ${\displaystyle t_{1},\cdots ,t_{k}}$ are terms and ${\displaystyle P_{i}^{k}}$ is a predicate symbol, then ${\displaystyle P_{i}^{k}(t_{1},\cdots ,t_{k})}$ is a formula.
• If ${\displaystyle F}$ and ${\displaystyle G}$ are formulae, then ${\displaystyle (F\land G)}$ and ${\displaystyle (F\lor G)}$ are formulae.
• If ${\displaystyle F}$ is a formula, then ${\displaystyle \lnot F}$ is a formula.
• If ${\displaystyle x}$ is a variable and ${\displaystyle F}$ a formula, then ${\displaystyle \forall xF}$ and ${\displaystyle \exists xF}$ are formulae.

Formulae of type ${\displaystyle P_{i}^{k}(t_{1},\cdots ,t_{k})}$ are called atoms or atomic formulae.

Note that the concept of subformulae applies exactly like in the propositional case (Syntax (Propositional Logic)).

We introduce the following abbreviations, which will be used with indices as well:

${\displaystyle u,v,w,x,z,}$ for variables
${\displaystyle a,b,c,\cdots }$ for constants
${\displaystyle f,g,h,\cdots }$ for function symbols
${\displaystyle p,q,r,\cdots }$ for predicate symbols

Note the arity of function and predicate symbols is ommited in these abbreviations; we assume that it will be obvious from the context.

Example: Assume we want to represent the following equation, which holds for arbitrary elements in a field:

${\displaystyle x*(y+z)=x*y+x*z}$

The two operators ${\displaystyle *}$ and ${\displaystyle +}$ are represented in a predicate logic formula as binary function symbols ${\displaystyle f_{1}^{2}}$ and ${\displaystyle f_{2}^{2}}$, the three variables are ${\displaystyle x_{1},x_{2}}$ and ${\displaystyle x_{3}}$, and the equality relation ${\displaystyle =}$ is the binary predicate symbol ${\displaystyle P_{1}^{2}}$. Altogether we have the following formula in predicate logic:

${\displaystyle \forall x_{1}\forall x_{2}\forall x_{3}(P_{1}^{2}(f_{2}^{2}(x_{1},f_{1}^{2}(x_{2},x_{3})),f_{1}^{2}(f_{2}^{2}(x_{1},x_{2}),f_{2}^{2}(x_{1},x_{3}))))}$

In the following we will use the obvious and more liberal notation as in the propositional case.

## Definition 3: Bound and Free Occurrences of Variables

An occurrence of a variable ${\displaystyle x}$ in a formula ${\displaystyle F}$ is called bound, if it occurs in a subformula of ${\displaystyle F}$ which is of the form ${\displaystyle \exists x\;G}$ or ${\displaystyle \forall x\;G}$. Otherwise we call the occurrence free.

A formula, which does not contain a free occurrence of a variable is called closed.

Example: The following formula contains both free and bound occurrences of ${\displaystyle x}$ and ${\displaystyle y}$.

${\displaystyle \forall z(Q(z)\land \forall x(P(x,y))\lor \exists y(P(x,y)))}$