Week S2.1. Intro to Predicate Logic

Basic Elements of First-Order Logic

Propositional logic is not flexible as each propositional statement is in some way indivisible / atomic, they cannot be decomposed into the elements they refer to.

Example: Problems with Propositional Logic

Consider a system where:

• $P$: all friends of Max are friends of John
• $Q$: Paul is a friend of Max
• $R$: Paul is a friend of John

We cannot represent a system in which $R$ follows from $P$ and $Q$ because in this propositional logic, for this specific case, we have that $P,Q/\models R$.

In propositional logic, $P,Q\models R⟺$ all models of $P$, $Q$ are models of $R$. But the truth value of $R$ does not depend on the truth values of $P$ and $Q$, as there is no link between them. For this reason, we cannot derive $R$ from $P$ and $Q$.

Objects / Individuals & Domain

Predicate

A predicate is a building block of statements in first-order logic, it is used to assert a property of an object or a relationship between objects.

Link to original

Atomic formula

Applying a predicate to one or more terms creates an atom, which is also a simple formula of this language, called an atomic formula.

Link to original

Monadic Predicate

A monadic (or unary) predicate can be used to give a property to a single individual (denoted by a term), the notation has the form:

$$Predicate(\text{term})$$

Examples:

• $Yellow(\text{car})$ - The car is yellow.
• $Prime(29)$ - 29 is prime.

Link to original

Polyadic Predicate

A polyadic predicate can be used to assign a relation to an ordered list of individuals, the notation has the form:

$$Predicate({\text{term}}_1,...,{\text{term}}_n)$$

where $Predicate$ is an $n$-place (or, otherwise $n$-ary) predicate.

$n$ is the Arity of the predicate.

Examples:

• $Divides(13,91)$: $13$ divides $91$ (with no remainder)
• $In(\text{helsinki},\text{finland})$: Helsinki is in Finland

Link to original

Function (FOL)

A function symbol is used to specify an individual by means of one or more other individuals. The notation, for an $n$-ary function symbol is:

$$function({\text{term}}_1,...,{\text{term}}_n)$$

Examples:

• $square\_root(17)$ is the square root of $17$.
• $product(19,91)$ is $19\times 91$.

Link to original

Equality (FOL)

In first-order logic, we can use an equality operator ($=$) to state that two objects equal to one another.

We use the notation:

$${\text{term}}_1={\text{term}}_2$$

This also forms an atomic formula.

Examples of use:

• $1=succ(0)$
• $\neg (1=succ(2))$

Link to original

Variables and Quantifiers

Terms, predicates, and functions cannot encode statements which refer to potentially unknown or unnamed objects. For these sorts of statements, we introduce symbols that are placeholders for unnamed objects.

Variables

Variable (Predicate Logic)

A variable is a term which does not refer to a fixed individual but is free to change what it refers to over the whole range of available individuals.

Example use of variables:

• $Person(x)$: $x$ is a person.
• $Student(paul,x)$: $Paul$ is a student at $x$.

Link to original

Quantifiers

Quantification

Quantification is a means of expressing statements which do not refer to any named individuals.

Link to original

Existential Quantifier

Existential quantifier

The existential quantification of $P(x)$ for a particular domain, denoted by $\exists xP(x)$, is the proposition that "there exists a value for $x$ in the domain such that $P(x)$ is true".

• The truth value of $\exists xP(x)$ might change when domain changes.
• Domain must always be specified when used.

For example, take $P(x)$ is "$x<-3$":

• If the domain is all integers, then it is true.
  • We simply need to give one example, such as $x=-5$ then $P(-5)$ is true.
• If the domain is the positive integers, then it is false.

To say “(at least one) car is yellow”, we write that for some $x$, $x$ is yellow:

$$(\exists x)(Colour(x,yellow))$$

In general, the notation for existential quantifiers is $(\exists x)(\phi)$, where $\phi$ is a formula in which $x$ and possible other variables may appear..

Link to original

Examples:

• $\exists x(Boy(x)\wedge Likes(x,jane))$: Some boy likes Jane.
• $\exists x(Boy(x)\wedge Like(jane,x))$: Jane likes some boy.
• $\neg \exists xLikes(x,jane)$: No-one likes Jane.
• $\exists x(\neg \exists yLikes(x,y))$: Someone does not like anyone.

Universal Quantifier

Universal quantifier

The universal quantification of $P(x)$ for a particular domain, denoted by $\forall xP(x)$, is the proposition "$P(x)$ is true for all values of $x$ from the domain". $\forall$ means "For all".

• The truth value of $\forall xP(x)$ might change if domain changes.
• Domain must always be specified when universal quantifier is used.

For example, take $P(x)$ is "$x>0$":

• For the domain of positive integers, $\forall xP(x)⇝T$.
• For the domain of all integers, $\forall xP(x)⇝F$.

To say “Everyone does not like Jane”, we write that for every $x$, $x$ does not like Jane:

$$(\forall x)(\neg Likes(x,jane))$$

In general, the notation for universal quantifiers is $(\forall x)(\phi)$ where $\phi$ is a formula in which $x$ and possible other variables may appear.

Link to original

Examples:

• $\forall x(Boy(x)\to \neg Likes(x,jane))$: Every boy does not like Jane.
• $\neg \forall xLikes(x,jane)$: Not everyone likes Jane.
• $\forall x(Likes(x,bob)\to Likes(x,mary))$: Everyone who likes Bob, likes Mary.
• $\forall x\forall y(Likes(x,y)\to Likes(y,x))$: Everyone is liked by each person that they like.

Mixing Quantifiers

You can mix different types of quantifiers together:

• $\forall x(Person(x)\to \exists y(University(y)\wedge Student(x,y)))$: Everyone studies at some university.
• $\forall x(University(x)\to \exists y(Person(y)\wedge Student(x,y)))$: Every university has at least one student.
• $\forall x(Person(x)\to \neg (\exists y\exists z(University(y)\wedge University(z)\wedge \neg (y=z)\wedge Student(x,y)\wedge Student(x,z))))$: Everyone studies in at most one university.

Scope of quantifiers

Consider the quantified formula $(Qx)(\varphi )$ where $Q$ is a quantifier (either $\exists$ or $\forall$) and $\varphi$ is a formula.

Scope (Quantifiers)

Given $(Qx)(\varphi )$, scope of a quantifier $Qx$ is $\varphi$.

Link to original

Bound Variable (Quantifiers)

Given $(Qx)(\varphi )$, the occurrence of the variable $x$ immediately after the quantifier symbol $Q$ is said to be bound.

All occurrences of the variables $x$ in $\varphi$, are said to be bound.

Link to original

Free Variable (Quantifiers)

An occurrence of a variable that is not bound is said to be free.

Link to original

Sentence (Quantifiers)

A formula without free variables is called a sentence.

Link to original

Examples of Scope

1. $(\exists x)P(x,y)\wedge R(x)$ The scope of $\exists x$ is $P(x,y)$. The first two occurrences of $x$ are bound, where the third occurrence of $x$ is free. The occurrence of $y$ is free.
2. $(\exists x)(P(x,y)\wedge R(x))$ The scope of $\exists x$ is $P(x,y)\wedge R(x)$. All occurrences of $x$ are bound. Occurrence of $y$ is free.
3. $(\exists x)((\forall y)P(x,y)\wedge R(x))$ The scope of $\exists x$ is $(\forall y)P(x,y)\wedge R(x)$. The scope of $\forall y$ is $P(x,y)$. All occurrences of variables are bound.

Solving the initial example: “problems with propositional logic”

If we go back to our three initial statements:

• $P$: all friends of Max are friends of John
• $Q$: Paul is a friend of Max
• $R$: Paul is a friend of John

We can encode them in a first-order logic language:

• $(\forall x)(Friend(x,max)\to Friend(x,john))$
• $Friend(paul,max)$
• $Friend(paul,john)$: in FOL, this can be derived from first two statements.

To solve this, we need to formally define the semantics of logic and notion of logical consequence in FOL.

Formal Definition of FOL language syntax

The language of a first-order logic is characterized by the terms, functions, predicates, quantifiers, and so on.

Different meanings can be associated with a sequence of symbols, hence different semantics can be associated with a first-order language, two of them are: Classical and Herbrand semantics. These two semantics are different but similar, and under some circumstances equivalent.

Classical Semantics

Classical semantics is usually adopted in mathematical logics.

Link to original

Herbrand Semantics

Herbrand semantics is usually adopted in relational database theory and applications.

Link to original

Syntax of FOL

Vocabulary (Predicate Logic)

A vocabulary (signature) $\sigma$ is a collection of:

• a non-empty set $\{c_1,...,c_n\}$ of constants (symbols).
• a possible empty set $\{f_1,...,f_n\}$ of functions (symbols), each of them associated with an integer $\text{arity}(f_i)=a_i\ge 1$.
• a possibly empty set $\{P_1,...,P_n\}$ of predicates (or relations), each of them associated with an integer $\text{arity}(P_i)=a_i\ge 0$.

Link to original

Alphabet (Predicate Logic)

Given a vocabulary $\sigma$, the alphabet $A_{\sigma }$ of a first-order language over $\sigma$ is a set of symbols comprising:

• a countably infinite set of variables $\{x,y,z,...\}$ (with super and subscripts)
• $\top ,\perp$: the Boolean values true and false
• $\neg ,\wedge ,\vee ,\to ,\leftrightarrow$: the logical connectives
• $\forall ,\exists$: the quantifiers’ symbols
• $=$: the equality symbol; $t_1\ne t_2\text{ may replace }\neg (t_1=t_2)$
• $(,)$: the parentheses
• $,$: the comma
• all the constant, predicate, and function, symbols (with their associated arity) from $\sigma$

Link to original

Expression (Predicate Logic)

An expression of a first-order language is any finite sequence of symbols of the alphabet of the language.

$A_{\sigma }^{\ast }$ is set of all expressions that can be built by the symbols in the alphabet $A_{\sigma }$.

Link to original

Since no constraint is imposed over how symbols can be arranged in expressions, many expressions can be nonsensical so we need to select some expressions that make sense for us, e.g. $)\forall \leftrightarrow \exists (\wedge x((Friend(\forall ,\vee )$.

Terms (Predicate Logic)

The $\sigma$-terms of a first-order language over $\sigma$ are the expressions from $A_{\sigma }^{\ast }$ defined via the following rules:

• every variable is a $\sigma$-term
• every constant in $\sigma$ is a $\sigma$-term
• if the expressions $t_1,...,t_n$ are $\sigma$-therms and $f$ is an $n$-ary function in $\sigma$, then the expression $f(t_1,...,t_n)$ is also a $\sigma$-term

Link to original

Formulas (Predicate Logic)

Given a vocabulary $\sigma$, the $\sigma$-formulas of a first-order language over $\sigma$ are expressions from $A_{\sigma }^{\ast }$ defined by the following rules:

• $\top$ and $\perp$ are $\sigma$-formulas
• if $t_1$ and $t_2$ are $\sigma$-terms, then $t_1=t_2$ is also a $\sigma$-formula (an atomic formula)
• if $t_1,...,t_n$ are $\sigma$-terms and $P$ is an $n$-ary predicate in $\sigma$, then the atom $P(t_1,...,t_n)$ is also a $\sigma$-formula (also an atomic formula)
• if $\varphi$ is a $\sigma$-formula, then $\neg (\varphi )$ is also a $\sigma$-formula
• if $\varphi$ and $\phi$ are $\sigma$-formulas, then $(\varphi \wedge \phi ),(\varphi \vee \phi ),(\varphi \to \phi ),\text{ and }(\varphi \leftrightarrow \phi )$ are also $\sigma$-formulas
• if $x$ is a variable and $\varphi$ is a $\sigma$-formula $(\exists x)(\varphi )$ and $(\forall x)(\varphi )$ are also $\sigma$-formulas

Link to original

First-order Language

The first-order (or predicate logic) language over the vocabulary $\sigma$, denoted by $\mathcal{L}[\sigma ]$, is the set of all expressions over $A_{\sigma }^{\ast }$ that are moreover $\sigma$-formulas.

Link to original

Interpretations for FOL formulas

Semantic of FOL

We have seen how FOL formulas are written, we now need to be able to evaluate whether a FOL formula is true or false, this is the semantic of FOL.

Link to original

Similarly to propositional logic, the truth-value of a FOL formula depends onthe truth-values assigned to its “components”.

Interpretation (Predicate Logic)

An interpretation $\mathcal{I}$ for a first-order logic language consists of a non-empty domain $D$ of objects, over which the variables may range, together with an assignment of a meaning to the predicate, constants, functions, and symbols.

Link to original

Example: Importance of Domain

Consider the formula $\exists x(x+x=3)$, where the symbol "$+$" is interpreted as the usual sum operation and the symbol "$3$" is interpreted as the object “number $3$”.

If the domain in the interpretation is the set $\mathbb{N}$ of natural numbers, then the formula is false in the interpretation. If the domain in the interpretation is the set $\mathbb{Q}$ of rational numbers, then the formula is true in the interpretation.

Hence, the domain in the interpretation can make a difference in the truth value of a formula.

Example: Importance of interpreting predicates

Consider the formula $\forall x\exists yA(x,y)$ and an interpretation with domain $\mathbb{N}$ (the set of natural numbers). If the binary predicate $A$ is interpreted as “successor”, i.e. $A(x,y)$ is true whenever $y$ is the successor of $x$ in $\mathbb{N}$, we have $A(2,3)$ and $A(5,6)$ as true, whereas $A(3,6)$ and $A(4,1)$ are false.

Otherwise if we interpret it as the “predecessor”, $A(x,y)$ is true when $y$ is the predecessor of $x$ in $\mathbb{N}$ then the opposite is true. Hence, different interpretations of the predicates can make a difference in the truth table of a formula.

Satisfaction of a formula

Satisfaction of a formula

Let $\varphi$ be a $\sigma$-formula of a first-order language $\mathcal{L}[\sigma ]$, and let $\mathcal{I}$ be an interpretation for $\mathcal{L}[\sigma ]$. The interpretation $\mathcal{I}$ satisfies the formula $\varphi$, denoted by $\mathcal{I}\models \varphi$, based on the following inductive rules:

• $\mathcal{I}\models \top$ at all times and never $\mathcal{I}\models \perp$.
• For terms, $t_1$ and $t_2$, $\mathcal{I}\models t_1=t_2⟺t_1$ and $t_2$ are interpreted in $\mathcal{I}$ as the same object in the domain.
• For an $n$-ary predicate $P$ and terms $t_1,...,t_n$, $\mathcal{I}\models P(t_1,...,t_n)⟺P(t_1,...,t_n)$ is true in $\mathcal{I}$.
• For a formula $\varphi$, $\mathcal{I}\models \neg (\varphi )⟺\mathcal{I}\models \varphi$ does not hold.
• For formulas $\varphi$ and $\phi$, $\mathcal{I}\models (\varphi \wedge \phi )⟺\mathcal{I}\models \varphi$ and $\mathcal{I}\models \phi$.
• For formulas $\varphi$ and $\phi$, $\mathcal{I}\models (\varphi \vee \phi )⟺\mathcal{I}\models \varphi$ or $\mathcal{I}\models \phi$.
• For formulas $\varphi$ and $\phi$, $\mathcal{I}\models (\varphi \to \phi )⟺\mathcal{I}\models (\neg \varphi \vee \phi )$.
• For formulas $\varphi$ and $\phi$, $\mathcal{I}\models (\varphi ⟺\phi )⟺\mathcal{I}\models ((\varphi \to \phi )\wedge (\phi \to \varphi ))$.
• For a variable $x$ and a formula $\varphi$, $\mathcal{I}\models (\exists x)(\varphi )⟺$ for all objects $d\in D$, $\mathcal{I}\models \varphi (x/d)$. For a $D$ of finite size, $\mathcal{I}\models (\exists x)(\varphi )$ equals $\models {\bigvee }_{d\in D}(x/d)$.
• For a variable $x$ and a formula $\varphi$, $\mathcal{I}\models (\forall x)(\varphi )⟺$ for all objects $d\in D,\mathcal{I}\models \varphi (x/d)$. For a $D$ of finite size, $\mathcal{I}\models (\forall x)(\varphi )$ equals $\mathcal{I}\models {\bigwedge }_{d\in D}\varphi (x/d)$.

Notation: in the formulas above, $\varphi (x/d)$ denotes the formula obtained from $\varphi$ in which all free occurrences of $x$ are substituted for the object $d$.

Link to original

Model (Predicate Logic)

If $\mathcal{I}$ satisfies $\varphi$, $\mathcal{I}$ is said to be a model of $\varphi$. If $\mathcal{I}$ does not satisfy $\varphi$, it can be denoted by $\mathcal{I}/\models \varphi$.

For an interpretation $\mathcal{I}$ and a formula $\varphi$, we can also write $\mathcal{I}(\varphi )=1$ and $\mathcal{I}(\varphi )=0$ to say that $\mathcal{I}$ satisfies and does not satisfy $\varphi$ respectively.

Link to original

Satisfiable (Predicate Logic)

A formula is satisfiable if it admits a model, e.g. this formula is a contradiction: $(\forall x)(P(x)\to Q(x))$.

Link to original

Unsatisfiable (Predicate Logic)

A formula is unsatisfiable (contradiction) if it does not admit any model, e.g. this formula is a tautology: $(\exists x)(P(x)\wedge \neg P(x))$.

Link to original

Valid (Predicate Logic)

A formula is valid (tautology) if it is satisfied by all interpretations, e.g. this formula is a tautology: $(\forall x)(P(x))\to (\exists x)(P(x))$.

Link to original

Example: Truth-value of a formula 1

Consider the formula $\exists x\forall y(P(y)\to x=y)$ for the following interpretations:

Interpretation	Evaluation	Explanation
$D=\{a\}$ $P(a)=\top$	$\top$
$D=\{a\}$ $P(a)=\perp$	$\top$
$D=\{a,b\}$ $P(a)=P(b)=\top$	$\perp$	There is no witness, shown by counter-examples for each of the possible choices of $x$: $(x=a;y=b)$ and $(x=b;y=a)$
$D=\{a,b\}$ $P(a)=P(b)=\perp$	$\top$
$D=\{a,b\}$ $P(a)=\top$ $P(b)=\perp$	$\top$	The witness is $x=a$, as for this specific choice of $x$ there is no counter-example on $y$.

Example: Truth-value of a formula 2

Consider the interpretations below where symbols $<$, $+$ and $\times$ are interpreted in the usual way for different mathematical operations. And consider $0$ as the constant symbol interpreted as the number zero.

Say whether the following formulas are true or not depending on the domain of interpretation.

Formula	$\mathbb{N}$	$\mathbb{Z}$	$\mathbb{Q}$	$\mathbb{R}$
$(\exists z)(\forall n)(n\ne z\to z<n)$	$\top$	$\perp$	$\perp$	$\perp$
$(\forall x)(\forall y)(\exists z)(x+y=z)$	$\top$	$\top$	$\top$	$\top$
$(\forall x)(\forall z)(\exists y)(x+y=z)$	$\perp$	$\top$	$\top$	$\top$
$(\forall x)(\forall y)(x<y\to (\exists z)(x<z\wedge z<y))$	$\perp$	$\perp$	$\top$	$\top$
$(\forall x)(\forall y)(\exists z)(x\times y=z)$	$\top$	$\top$	$\top$	$\top$
$(\forall x)(\forall z)(x\ne 0\to (\exists y)(x\times y=z))$	$\perp$	$\perp$	$\top$	$\top$
$(\forall y)(\neg (y<0)\to (\exists x)(x\times x=y))$	$\perp$	$\perp$	$\perp$	$\top$

Logical consequence

An interpretation $\mathcal{I}$ is a model of the set $\Phi$ of $\sigma$-formulas, denoted by $\mathcal{I}\models \Phi ⟺\mathcal{I}\models \varphi$ for all $\varphi \in \Phi$.

A set $\Phi$ of $\sigma$-formulas is satisfiable $⟺\Phi$ admits a model.

The $\sigma$-formula $\gamma$ is a logical consequence of a set of $\Phi$ of $\sigma$-formulas, denoted by $\Phi \models \gamma ⟺$ every model of $\Phi$ is also a model of $\gamma$.

$\varnothing \models \varphi$ or $\models \varphi$ means that $\varphi$ is valid because all interpretations are models of the empty set $\varnothing$.

Two $\sigma$-formulas $\varphi$ and $\phi$ are logically equivalent, denoted by $\varphi \equiv \phi ⟺\{\phi \}\models \varphi$ and $\{\varphi \}\models \phi$.