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

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.

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

If $F$ and $G$ are formulae, then so are $\lnot F$ , $F\land G$ as well as $F\lor G$
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

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

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