24.2 Logics
24.2.1 Foundational things
These are the metadefinitions 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
That is, $F$ cannot be derived
Definition 24.2.7
Unsatisfiability If $F$ is unsatisfiable we write
Theorem 24.2.1
Relation between tautology and unsatisfiability We can prove that
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
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
For conjunctive normal form, this is a little more complex, but we could do something like
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
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.
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
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
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
Interpretations in predicate logic
Example 24.2.4
Consider the formula
we can consider this in the universe $\mathbb{N}$, and define
and further define
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:
This is not a true statement! If the righthand 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
is not true, as although the lefthand implies the right, the other way is not true.
Example 24.2.7
A predicate logic interpretation. Let us return to the familiar formula
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
Here’s a sensible definition of what this means semantically
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, easyish) to carry out syntactic manipulations (this is closely related to a branch of computer science called term rewriting).