First-order logic

Zero-order logic

Terms and predicates

Predicates

Zero-order logic adds predicates. Like propositional variables, these have truth values. Unlike propositional variable, predicates take terms as inputs.

For example using propositional logic we can write the statement “you are 25” as \(\theta \).

With preterites we can write this as \(P(you, 25)\).

A propositional variable can be considered a special case of a predicate variable, where the number of inputs is \(0\).

Relations and equality

Relations

A special type of predicates is a relation. These take two terms and can be written differently: \(P(x,y)\Leftrightarrow x\oplus y\)

Equality

In preterite logic we define the relation for equality.

\(a=b\)

It is defined by the following:

  • Reflexivity : \(x=x\)

  • Symmetry: \(x=y\leftrightarrow y=x\)

  • Transivity: \(x=y\land y=z \rightarrow x=z\)

  • Substitution for functions: \(x=y\rightarrow f(x)=f(y)\)

  • Substitution for formulae: \(x=y\land P(x)\rightarrow P(y)\)

Functions and brackets

Functions (or maps)

Functions take other terms, and are themselves terms. For example if we wanted to know if someone can legally drive in a specific country, we could use:

\(P(you,age(UK))\)

A function may not be able to produce an output for all inputs. For examples \(age(green)\) has no interpretation.

Functions can also take different numbers of inputs. Constants, such as “you” and “UK” can be shown as functions with \(0\) inputs. As a result we could instead write:

\(P(you(),age(UK()))\)

We generally denote functions with a lower case letter, so would instead write:

\(P(y(),a(b()))\)

Functions are also called maps.

Signatures

Structures

A logical structure consists of:

  • Domain

  • Interpretation

  • Signature

Domain

The domain is the set of variables in the structure.

We include an infinite number of variables.

Interpretation

The interpretation assigns values to propositional and predicate variables.

Signature

A logical signature describes the language of the logic which is used to construct statements. This includes:

  • Functions

  • Relations

  • Operators

The language of a signature is all possible sentences, or formulae which can be constructed from this signature.

We include an infinite number of functions, relations and all operators.

Completeness of zero-order logic

A theory is complete if all true formulae are included.

Note that there are three types of formulae in a theory.

  • Tautologies (always true)

  • Refutable formulae (always false)

  • Satisfiable formulae which are not tautologies (true in some, but not all, interpretations).

Injective, bijective and surjective functions

Injective functions

\(f(a)=f(b)\rightarrow a=b\)

Surjective functions

All points in codomain have at least one matching point in domain

Mapping info, details

Bijective

Both injective and surjective

Other

Identity function

The identity function maps a term to itself.

Idempotent

An idempotent function is a function which does not change the term if the function is used more than once. An example is multiplying by \(0\).

Inverse functions

An inverse function of a function is one which maps back onto the original value.

\(g(x)\) is an inverse function of \(f(x)\) if

\(g(f(x))=x\)

Properties of binary functions

Binary functions can be written as:

\(f(a,b)=a\oplus b\)

A function is commutative if:

\(x\oplus y = y\oplus x\)

A function is associative if:

\((x\oplus y)\oplus z = x\oplus (y\oplus z)\)

A function \(\otimes \) is left distributive over \(\oplus \) if:

\(x\otimes (y\oplus z)=(x\otimes y) \oplus (x\otimes z)\)

Alternatively, function \(\otimes \) is right distributive over \(\oplus \) if:

\((x\oplus y)\otimes z=(x\otimes z) \oplus (y\oplus z)\)

A function is distributive over another function if it both left and right distributive over it.

Binary functions

Properties of binary functions

Binary functions can be written as:

\(f(a,b)=a\oplus b\)

A function is commutative if:

\(x\oplus y = y\oplus x\)

A function is associative if:

\((x\oplus y)\oplus z = x\oplus (y\oplus z)\)

A function \(\otimes \) is left distributive over \(\oplus \) if:

\(x\otimes (y\oplus z)=(x\otimes y) \oplus (x\otimes z)\)

Alternatively, function \(\otimes \) is right distributive over \(\oplus \) if: \((x\oplus y)\otimes z=(x\otimes z) \oplus (y\oplus z)\)

A function is distributive over another function if it both left and right distributive over it.

First-order logic

Writing first-order logic

Existential quantifier

We introduce a shorthand for “at least one term satisfies a predicate”, that is:

\(P(x_0)\lor P(x_1)\lor P(x_2)\lor P(x_2)\lor P(x_3)...\)

The short hand is:

\(\exists x P(x)\)

niversal quantifier

We introduce another shorthand, this time for:

\(P(x_0)\land P(x_1)\land P(x_2)\land P(x_2)\land P(x_3)...\)

The shorthand is

\(\forall x P(x)\)

Free and bound variables

A bound variable is one which is quantified in the formula. A free variable is one which is not. Consider:

\(\forall x P(x,y)\)

In this, \(x\) is bound while \(y\) is free.

Free variables can be interpreted differently, while bound variables cannot.

We can also bind a specific variable to a value. For example \(0\) can be defined to be bound.

Ground terms

A ground term does not contain any free variables. A ground formula is one which only includes ground terms.

\(\forall x\ x\) is a ground term.

\(\forall x P(x)\) is a ground formula.

Inference rules for first-order logic

Existential instantiation

If \(P\) is true for a specific input, then there exists an input for \(P\) where \(P\) is true.

\(P(r)\Rightarrow \exists xP(x)\)

Existential generalisation

\(\exists xP(x)\Rightarrow P(r)\)

Where \(r\) is a new symbol.

Universal instantiation

If \(P\) is true for all values of \(x\), then \(P\) is true for any input to \(P\).

\(\forall xP(x)\Rightarrow P(a/x)\)

Where \(a / x\) represents substituting \(a\) for \(x\) within \(P\).

Universal generalisation

If there is a derivation for \(P(x)\), then there is a derivation for \(\forall x P(x)\).

\(\vdash P(x)\Rightarrow \vdash \forall x P(x)\)

Duality of first-order logic

The dual of:

\(\exists x \neg P(x)\)

Is:

\(\neg \forall x P(x)\)