24.2 Logics

24.2.1 Foundational things

These are the meta-definitions for any given logic (that is, they are kind of a \saytemplate for defining a specific logic). Once we answer these questions, we have a logic!

Definition 24.2.1

An interpretation assigns a value to specified free symbols in a formula.

Definition 24.2.2

An interpretation is suitable for a formula if it binds all free variables.

Definition 24.2.3

Given a formula FF (or a set of formulas), a model MM is an interpretation for which FF is true.

In formulas, this is either

𝒜(F)=1\displaystyle\mathcal{A}(F)=1 (24.6)
𝒜F\displaystyle\mathcal{A}\vDash F (24.7)
Definition 24.2.4

Logical consequence If for every interpretation whenever FF is true, GG is too, then we write

FG\displaystyle F\vDash G (24.8)
Definition 24.2.5

Logical equivalence ???

FG\displaystyle F\vDash G (24.9)
MG\displaystyle M\vDash G (24.10)
Definition 24.2.6

Tautology notation If FF is a tautology (informally it is always true) then we write

F\vDash F (24.11)

That is, FF cannot be derived

Definition 24.2.7

Unsatisfiability If FF is unsatisfiable we write

FF\vDash\bot (24.12)
Theorem 24.2.1

Relation between tautology and unsatisfiability We can prove that

(F)(¬F)\big{(}\vDash F\big{)}\iff\big{(}\lnot F\vDash\bot\big{)} (24.13)

This apparently follows from what this means.

Theorem 24.2.2

Normal forms The statements of the theorem is that we can always write any formula in a normal form.

Consider some formula in propositional logic, for which we have a truth table. We then consider the 11 entries. For these rows, we might have something in the form

(ABCF0101)\begin{pmatrix}A&B&C&F\\ 0&1&0&1\end{pmatrix} (24.14)

Then we add a term which is one if and only if A=0,B=1,C=0A=0,B=1,C=0. For example, in this case we would have something that looks a bit like

(¬AB¬C).(\lnot A\land B\land\lnot C)\lor.... (24.15)

For conjunctive normal form, this is a little more complex, but we could do something like

(ABC)()()(A\lor B\lor C)\land(...)\land...\land(...) (24.16)

then instead of making terms one when the conditions trigger, we make terms zero when the conditions are not triggered.

24.2.2 Definition of propositional logic

24.2.3 Definition of predicate logic

Syntax of predicate logic

Definition 24.2.8

We begin by defining the syntax of predicate logic; we have:

  1. 1.\say

    variables, which we can denote as xix_{i}\in\mathbb{N} (in order to ensure that we have an infinite reserve of these), but we normally write using letters (e.g. a,b,u,wa,b,u,w) as it is easier for (most) humans to understand these

  2. 2.\say

    functions such as fi(k)f_{i}^{(k)} (where ii is an index used to identify a specific function, and kk denotes the \sayarity, aka number of arguments the function takes)

  3. 3.

    Predicates, in the form Pi(k)P_{i}^{(k)}

This is not a particularly interesting language - we would ideally be able to build more complex syntactically valid objects out of these simple ones we have defined. We define a \sayterm inductively (or recursively). A term (from a purely syntactical point of view) is defined as something in the form

fi(k)(t1,t2,,tk)f_{i}^{(k)}(t_{1},t_{2},...,t_{k}) (24.17)

This is all very well, but we would also like our terms to be finite (infinitely recursive pieces of language are not particularly pleasant). We must also, therefore, define a \saybase case (i.e. some terms which are not defined in terms of other terms, so that it is at least possible for our terms to terminate). todo: finish this part (above)

We also define formulae, using these rules

  1. 1.

    Pi(k)(t1,,tk)P_{i}^{(k)}(t_{1},...,t_{k}) is a formula,

  2. 2.

    If FF and GG are formulae, then so are ¬F\lnot F, FGF\land G as well as FGF\lor G

  3. 3.

    If FF is a formula, then xiF\forall x_{i}F and xiF\exists x_{i}F are also formulae.

Example 24.2.1

The formula (in Equation 24.18, below) is not valid.

P(x)P(y,z)P(x)\lor P(y,z) (24.18)

Why? Because PP may not be a variadic function (i.e. it may not have more than kk terms as arguments) but it is constructed with one term (xx) and also with two terms y,zy,z which is not valid.

Example 24.2.2

A syntactically valid formula in propositional logic is

xyz(P(x,y)P(y,z)P(x,z)).\forall x\forall y\forall z\Big{(}P(x,y)\land P(y,z)\rightarrow P(x,z)\Big{)}. (24.19)

Of course, we have not yet defined what this formula means (beyond whether or not we may write it), for that we require semantics.

Example 24.2.3

Another syntactically valid formula is

P(x,z)xyQ(x,y,z).P(x,z)\lor\exists x\forall yQ(x,y,z). (24.20)

We still have no idea what this means semantically, just that it is a valid formula.

Free variables in predicate logic

Definition 24.2.9

Continuing with example 24.2.3, we can make a substitution of xx for f(y,z)f(y,z), which would give us

P(f(y,z),z)P(f(y,z),z)\lor... (24.21)

Interpretations in predicate logic

Example 24.2.4

Consider the formula

x(P(x)P(f(x,a))).\forall x\Bigl{(}P(x)\lor P\big{(}f(x,a)\big{)}\Bigr{)}. (24.22)

we can consider this in the universe \mathbb{N}, and define

p(x)=1x is evenp(x)=1\iff\text{$x$ is even} (24.23)

and further define

f(x,y)=x+yf(x,y)=x+y (24.24)

and then fix a=3a=3, in which case we can ask is 𝒜\mathcal{A} a \saymodel for FF. It is, as for every xx, either xx is even, or x+3x+3 is even.

Example 24.2.5

Consider the previous example, but with a different interpretation

U=\displaystyle U=\mathbb{R} (24.25)
P(x)=1x0\displaystyle P(x)=1\iff x\geqq 0 (24.26)
f(x,y)=x×y\displaystyle f(x,y)=x\times y (24.27)
a=2\displaystyle a=2 (24.28)

In this case, B(A)=0B(A)=0.

Example 24.2.6

Is this a true statement:

{F1,F2} is satisfiableF1 is satisfiableF2 is satisfiable?\{F_{1},F_{2}\}\text{ is satisfiable}\iff F_{1}\text{ is satisfiable}\land F_{% 2}\text{ is satisfiable}? (24.29)

This is not a true statement! If the right-hand side is true, this does not necessarily mean that the two separate interpretations, one for F1F_{1} and one for F2F_{2} are true for {F1,F2}\{F_{1},F_{2}\}.

This is analogous to the fact that

x(FG)xFxG\exists x(F\land G)\not\equiv\exists xF\land\exists xG (24.30)

is not true, as although the left-hand implies the right, the other way is not true.

Example 24.2.7

A predicate logic interpretation. Let us return to the familiar formula

(A¯¬B¯)(B¯¬C¯)(\underline{A}\lor\lnot\underline{B})\land(\underline{B}\lor\lnot\underline{C}) (24.31)

We would like to find an interpretation which makes this true.

For example, we could define 𝒜\mathcal{A} as

𝒜=0\displaystyle\mathcal{A}=0 (24.32)
=1\displaystyle\mathcal{B}=1 (24.33)
𝒞=0\displaystyle\mathcal{C}=0 (24.34)
𝒟=1\displaystyle\mathcal{D}=1 (24.35)

But how would we define the value of

𝒜((FG))=1?\mathcal{A}((F\land G))=1? (24.36)

Here’s a sensible definition of what this means semantically

𝒜((FG))=1𝒜(F)=1 and 𝒜(G)=1\mathcal{A}\Big{(}(F\land G)\Big{)}=1\iff\mathcal{A}(F)=1\text{ and }\mathcal{% A}(G)=1 (24.37)

This might seem in some way informal, but here’s the problem; at some point we will need to introduce some axioms.

24.2.4 Logical calculi

A logical calculus is a simple thing; it’s a way to connect truth and syntax. This is especially useful in computer systems where it is easy (well, easy-ish) to carry out syntactic manipulations (this is closely related to a branch of computer science called term rewriting).