# 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 $F$ (or a set of formulas), a model $M$ is an interpretation for which $F$ is true.

In formulas, this is either

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

Logical consequence If for every interpretation whenever $F$ is true, $G$ is too, then we write

 $\displaystyle F\vDash G$ (24.8)
###### Definition 24.2.5

Logical equivalence ???

 $\displaystyle F\vDash G$ (24.9) $\displaystyle M\vDash G$ (24.10)
###### Definition 24.2.6

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

$\vDash F$ (24.11)

That is, $F$ cannot be derived

###### Definition 24.2.7

Unsatisfiability If $F$ is unsatisfiable we write

$F\vDash\bot$ (24.12)
###### Theorem 24.2.1

Relation between tautology and unsatisfiability We can prove that

$\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 $1$ entries. For these rows, we might have something in the form

$\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=0$. For example, in this case we would have something that looks a bit like

$(\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

$(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.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 $x_{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,w$) as it is easier for (most) humans to understand these

2. 2.\say

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

3. 3.

Predicates, in the form $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

$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.

$P_{i}^{(k)}(t_{1},...,t_{k})$ is a formula,

2. 2.

If $F$ and $G$ are formulae, then so are $\lnot F$, $F\land G$ as well as $F\lor G$

3. 3.

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

###### Example 24.2.1

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

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

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

###### Example 24.2.2

A syntactically valid formula in propositional logic is

$\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)\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 $x$ for $f(y,z)$, which would give us

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

### Interpretations in predicate logic

###### Example 24.2.4

Consider the formula

$\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)=1\iff\text{x is even}$ (24.23)

and further define

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

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

###### Example 24.2.5

Consider the previous example, but with a different interpretation

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

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

###### Example 24.2.6

Is this a true statement:

$\{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 $F_{1}$ and one for $F_{2}$ are true for $\{F_{1},F_{2}\}$.

This is analogous to the fact that

$\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

$(\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

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

But how would we define the value of

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

Here’s a sensible definition of what this means semantically

$\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).