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\).
A special type of predicates is a relation. These take two terms and can be written differently: \(P(x,y)\Leftrightarrow x\oplus y\)
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 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.
A logical structure consists of:
Domain
Interpretation
Signature
The domain is the set of variables in the structure.
We include an infinite number of variables.
The interpretation assigns values to propositional and predicate variables.
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.
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).
\(f(a)=f(b)\rightarrow a=b\)
All points in codomain have at least one matching point in domain
Mapping info, details
Both injective and surjective
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\).
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\)
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 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.
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)\)
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)\)
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.
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.
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)\)
\(\exists xP(x)\Rightarrow P(r)\)
Where \(r\) is a new symbol.
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\).
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)\)
The dual of:
\(\exists x \neg P(x)\)
Is:
\(\neg \forall x P(x)\)