# Logic Notes

Published on the

## Introduction

• A formal logical system consists of a formal language for encoding arguments and a deductive system. Arguments consist of formulae. Arguments usually start with it a set of formulae consist of premises. Arguments seek to prove a formula, called the conclusion.
• The deductive system uses axioms and rules of inference to derive new formulae from existing formulae.

## Propositional Logic

• Propositional logic is branch of mathematical logic, studying truth-false value propositions, constructed from other propositions.
• Propositional logic “strips away real world context”. It is a formal language. Formal languages are made of two things: syntax and semantics. The syntax of propositional logic is made of a set of variables and a set of logical connectives. We may also additional add propositional constants to our language. Valid strings in our language are known as formulae.
• The language of propositional logic can be defined with a context-free grammar; it is a context-free language.
• We shall use the logical connectives: $$\{\wedge, \vee, \neg, \to, \leftrightarrow\}$$, standing for conjunction, disjunction, negation, implication and bi-implication.
• A truth assignment of a formulae is a mapping between variables and truth/falsity.
• Note that $$p \to q$$ can be rewritten as $$q \vee \neg p$$. This makes intuitive sense, as if $$p \to q$$, and $$q$$ isn’t true, this means $$p$$ can’t be true. Also note that $$p \leftrightarrow q$$ can be written as $$(p \to q) \wedge (q \to p)$$.
• A set of logical connectives are adequate if they can represent all logical connectives. $$\{\wedge, \neg\}$$ is an example of an adequate set.
• The set $$\{\uparrow\}$$ is also an adequate set. This is the symbol for NAND (which has an opposite truth table to conjunction).
• The set $$\{\downarrow\}$$ is also an adequate set. This is the the symbol for NOR (which has an opposite truth table to disjunction).
• The symbols $$\top$$ and $$\bot$$ are the symbols for falsity and truth respectively; these are 0-arity logical connectives (also known as propositional constants). They can also be used to create adequate sets.
• The logical connectives $$\{\wedge, \vee\}$$ are truth-preserving, this means whenever all parameters to the connectives are $$\top$$, the connectives map to $$\top$$. This means that they cannot alone be an adequate set, as it would be impossible to create Boolean functions which are not truth-preserving by only the composition of these functions.
• Another set $$\{\to, \neg\}$$ is also adequate, which can be proven with the identity for $$\to$$ and De Morgan’s laws.
• Some other properties $$\{\wedge, \vee\}$$ have are associativity, commutativity and idempotent. These are properties that $$\{\to\}$$ does not have.
• Two formulae in propositional logic are equivalent if they have the same value under every truth assignment.
• A literal is a propositional variable or a negation.
• Conjunctive normal form is a conjunction of zero or more disjunctions made of one or more literals e.g. $$(A \vee B) \wedge (\neg B \vee C)$$.
• Disjunctive normal form is a disjunction of zero of more conjunctions made of one or more literals e.g. $$(A \wedge B) \vee (\neg B \wedge C)$$.
• A tautology is a formula that is true in every circumstance e.g. $$p \to (q \to p)$$.
• A contradiction is a formula that is true in no circumstances.

## Logical Consequence

• If $$\phi$$ is a set of formulae, and $$\psi$$ is a formula, then it is the case that $$\phi \models \psi$$ if whenever every formula in $$\phi$$ holds then $$\psi$$ holds.
• This is a semantic concept as it relies on the meaning of $$\phi$$ and $$\psi$$, as opposed to a syntactic concept.
• If $$\models \psi$$ then $$\psi$$ is a tautology.
• If $$\phi \not\models \psi$$ then $$\psi$$ does not necessarily hold whenever all the formulae in $$\phi$$ hold, $$\not\models \psi$$ means that $$\psi$$ is not a tautology.
• If $$\phi \models \bot$$ means that $$\phi$$ is a contradiction, as there are no circumstances in which $$\phi$$ holds.
• If $$\phi \models \psi$$, then $$\models (\phi \to \psi)$$.
• If $$\phi$$ is satisfiable there is some truth assignment for which all the formulae in $$\phi$$ hold.

## Hilbert Calculus

• Hilbert Calculus is a possible deductive system for propositional logic.
• The rule of inference used is called modus ponens and is that if $$\phi \to \psi$$ and $$\phi$$, then $$\psi$$.
• The three axioms used are:
1. $$\phi \to (\psi \to \phi)$$
2. $$(\phi \to (\psi \to \theta)) \to ((\phi \to \psi) \to (\phi \to \theta))$$
3. $$((\neg \phi \to \neg \psi) \to (\psi \to \phi))$$
• In propositional logic, Hilbert calculus can within a finite number of application of the above rules on the premises of an argument, derive all valid statements that are true about them. If $$\phi \vdash \psi$$ then we say the conclusion $$\psi$$ is derivable from the premises $$\phi$$, or $$\psi$$ is a theorem of $$\phi$$. Similarly if $$\phi \not\vdash \psi$$ then $$\psi$$ is not a theorem of $$\phi$$.
• When talking about propositional logic with Hilbert calculus deriving $$\psi$$ from $$\phi$$, we may use $$\phi \vdash_H \psi$$.
• Propositional logic with Hilbert calculus is a sound formal system. A formal system is sound if $$\phi \vdash_H \psi$$ means $$\phi \models \psi$$, in other words only true statements can be proven.
• Propositional logic with Hilbert calculus is a complete formal system. A formal system is complete if $$\phi \models \psi$$ means that $$\phi \vdash_H \psi$$ in other words all true statements can be proven.
• The axioms in Hilbert calculus are also known as axiom schemata. An axiom schema is a propositional formula whose variables can be substituted by any valid formula and the formula is assumed to hold.
• Here is an example of a Hilbert calculus derivation:

Proposition: $\{\neg \neg B\} \vdash_H B$ Proof: \begin{align} \text{(1) } \ & (\neg \neg B) \to (\neg \neg \neg \neg B \to \neg \neg B) & \text{Ax 1} \\ \text{(2) } \ & \neg \neg B & \text{Ass}\\ \text{(3) } \ & (\neg \neg \neg \neg B \to \neg \neg B) & \text{MP 1,2}\\ \text{(4) } \ & (\neg \neg \neg \neg B \to \neg \neg B) \to (\neg B \to \neg \neg \neg B) & \text{Ax 3}\\ \text{(5) } \ & (\neg B \to \neg \neg \neg B) & \text{MP 4,3}\\ \text{(6) } \ & (\neg B \to \neg \neg \neg B) \to (\neg \neg B \to B) & \text{Ax 3}\\ \text{(7) } \ & (\neg \neg B \to B) & \text{MP 5,6}\\ \text{(8) } \ & B & \text{MP 2,7}\\ \end{align}

## First-order Logic

• First-order logic is an extension of propositional logic that includes quantified variables. A first-order language consists of functions and predicates. Predicates may be 0-ary in which case they are analogous to propositional variables. All other variables in first-order logic are quantified variables, referring to the domain of discourse. A first-order language may exist without functions, however without predicates, with an arity greater than 0, the first-order language is essentially a propositional language. Predicates go hand-in-hand with quantification, since the quantified variables must be arguments to predicate to be of use.
• In is important however to note in a first-order language, functions and predicates only exist syntactically and have no meaning. A structure of a first-order language provides the semantic meaning to a first-order language. It contains a non-empty set that is the domain, from which quantified variables emerge. (If the domain were empty, then $$(\exists x\;\top) \vee \neg(\exists x\;\top)$$ would be $$\bot$$).
• A structure for a first-order language also provides “interpretations” for the functions and predicates.
• A first-order theory consists of a set of axioms for a first-order language. These axioms are assumed as true. For a structure to be a model of a theory, its interpretation of the functions and predicates must satisfy the axioms.
• The functions and predicates of a first-order language are said to be the signature of the first-order language, bearing in mind that they are merely symbols.
• It is also possible to construct a first-order language with an infinite number of functions and an infinite number of predicates. This means that the first-order language can be used with whatever structure is needed to axiomatise a concept.

## Properties of Formal Systems

• As stated before propositional logic is both sound and complete. There is another notion of completeness, however, known as negation completeness. A formal system is negation complete if either $$\phi$$ or $$\neg\phi$$ can be derived for all $$\phi$$. Propositional logic is not negation complete. This can be shown by using a single propositional variable. There is not enough information, to say whether this one propositional variable, holds or not.
• First-order logic is also sound and complete. Kurt Gödel, an Austrian and later American, logician showed the latter in Gödel’s completeness theorem.
• This is not necessarily a problem with first-order logic, as it is possible to restrict the predicates and functions as well as add axioms to ensure everything is derivable. This means that it may be possible, and it is indeed, possible to create first-order languages that are negation complete.
• If it is possible to decide whether a formula in some first-order language is universally valid or not, then the formal system is decidable.
• Propositional logic is decidable, by truth tables, although this is highly inefficient in the worst cases.
• Note that if a first-order language is negation complete, this means that it must be decidable, since all possible proofs can be enumerated over, until either a proof of some proposition $$\phi$$ or its negation is found.
• However, a first-order language sufficiently powerful to express arithmetic cannot be negation complete. This was shown in Gödel’s incompleteness theorem. Of course, it is still possible that there exists a general decision procedure for all first-order languages, however this was shown not to be the case by, Alonzo Church through Lambda Calculus, and Alan Turing through Turing machines.
• It is also the case that since first-order languages are, generally undecidable, if we can show a particular first-order language as undecidable, we can also show it as negation incomplete.
• It is also important to note that even though first-order languages are generally undecidable, there are restricted first-order languages such as monadic first-order logic, that is decidable.

## Proofs

• Here is a proof of the soundness of propositional logic with Hilbert calculus:

Proposition: If $$\phi \vdash_H \psi$$, then $$\phi \models \psi$$.

Proof: We shall use induction on the length of the derivation. The base case will be for the first line of the derivation. We shall refer to the propositions on each line of the derivation as $$\psi_1, \psi_2... \psi_n$$.

Base Case: The first line of our derivation, can either arise as an axiom or an assumption. All axioms are tautologies so must be true, so if $$\psi_1$$ is an application of an axiom, the $$\phi \models \psi_1$$. Similarly, if it is an assumption then $$\psi_1 \in \phi$$, so $$\phi \models \psi_1$$.

Inductive Case: Assume $$\phi \models \psi_1 ... \psi_{i-1}$$. If $$\psi_i$$ is an axiom then, it is a tautology, so $$\phi \models \psi_i$$. if is an assumption then $$\psi_i \in \phi$$ so $$\phi \models \psi_i$$. Finally if $$\psi_i$$ is an application of the modus ponens inference rule, then there must be some $$k$$, such that $$k < i$$ and that $$(\psi_k \to \psi_i)$$ and $$\psi_k$$ appear in the derivation previously. If $$\psi_k$$ appears in the derivation then $$\psi_k$$ must be true. Since $$\psi_k \to \psi_i$$ appears in the derivation, then that must also be true. Because of the truth table for implication, $$\psi_i$$ must also be true, so $$\phi \models \psi_i$$.

Conclusion: If $$\phi \models \psi_{i-1}$$ then $$\phi \models \psi_i$$. Since $$\phi \models \psi_1$$, $$\phi \models \phi_k$$, where $$1 \le k \le n$$. Since $$\psi$$ must appear in its derivation, if $$\phi \vdash_H \psi$$, then $$\phi \models \psi$$.

• Here is a proof of the negation incompleteness of first-order logic able to express a sufficient amount of arithmetic i.e. Gödel’s incompleteness theorem:

Proposition: The first-order theory of Peano arithmetic is negation incomplete.

Proof: We shall show this by introduce the notion of Gödel numbering. We shall assign a distinct numeric value to every symbol in our first-order language. Then we shall show that any statement in our first-order language consisting of $$n$$ symbols can be encoded as a natural number, by matching them with the first $$n$$ prime numbers. The product of each prime number raised to the power of the numeric value of its respective symbol, is a unique representation of the string as a natural number. This is because the result can be prime factorised, to get the symbols in their original positions. For instance, the first symbol will the exponent of 2 (as a numeric value), in the prime factorisation of the result. This is what is meant by Gödel numbering, every statement in our first-order language is a natural number; or to put it another way, every proof in our first order language can be expressed a natural number.

Note to represent quantified variables, e.g. $$\exists x$$ and $$\forall y$$ a unary notation can be used to represent different variables. E.g. $$x_1$$, $$x_{11}$$, $$x_{111}$$. This can be extended to represent as many quantified variables as needed, with a finite number of symbols.

The proof resets on a single predicate $$\mathsf{Proof(x, y, z)}$$, however note that this predicate is not really a predicate (unless you want to it to be). This is because the predicate is really a short-hand for a very long expression in our first-order language. Optionally, you can say there exists a bi-implication in the form $$\mathsf{Proof(x, y, z)} \leftrightarrow \phi$$, where $$\phi$$ is a placeholder for this really long expression, in other words, $$\mathsf{Proof(x, y, z)}$$ is not necessary. Either the way the predicate relies on a very important notion: all computable functions can be expressed solely with the Peano axioms (well provided the Church-Turing thesis holds). In any case, the predicate $$\mathsf{Proof(x, y, z)}$$ holds if $$x$$ is the Gödel-encoded proof of the Gödel-encoded statement $$y$$ with integer $$z$$ substituted in it. Now, we shall make a new short-hand predicate, $$\mathsf{Prf(y)} \leftrightarrow \neg\exists x\;\mathsf{Proof(x, y, y)}$$, $$\mathsf{Prf(y)}$$ holds when there doesn’t exist a proof of the Gödel-encoded statement $$y$$ with $$y$$ substituted in it. Now let $$g$$ be the Gödel number of that predicate. Does $$\mathsf{Prf(g)}$$ hold? If it does hold there isn’t a proof of $$\mathsf{Prf(g)}$$. But if it does hold, there must be a proof of $$\mathsf{Prf(g)}$$. Contradiction. If it doesn’t hold, then that means there is a proof of $$\mathsf{Prf(g)}$$. But since it doesn’t hold, there can’t be. Contradiction. Both contradictions are due to the completeness of first-order logic, shown by Gödel previously. In other words there is neither a proof of $$\mathsf{Prf(g)}$$ or $$\neg\mathsf{Prf(g)}$$. Hence there are some statements, for which neither $$\phi$$ nor $$\neg\phi$$ hold in the first-order theory of arithmetic.

• Here is a proof of the undecidability of first-order logic:

Proposition: There is no general procedure to verify whether a set of formulae in first-order logic are universally valid.

Proof: In order to prove the aforementioned proposition, we will show there are propositions $$\phi$$ for which either $$\phi$$ or $$\neg\phi$$ must hold, and there does not exist a general procedure to determine whether $$\phi$$ or $$\neg\phi$$ are universally valid. To do this we shall show to how to axiomatise Turing machines, a first-order theory, I shall call $$\mathcal{T}$$. The Turing machine we will axiomatise will be represented by the quintuple $$(Q, \Sigma, B, \Gamma, \delta, q_0, F)$$. Note that the Turing machine, for convenience will have a semi-infinite tape, however, this is equivalent to Turing machine with a two-way infinite tape. $$\mathcal{T}$$ shall have the following functions:

• A 0-ary constant, $$0$$
• A 1-ary successor functions, $$s$$

$$\mathcal{T}$$ shall have the following predicates:

• $$\forall q \in Q, M_q(x, y)$$ which holds when the Turing machine is in state $$q$$ after $$x$$ steps, and scanning the $$y$$ square.
• $$\forall \sigma \in \Sigma, N_\sigma(x, y)$$ which holds when the Turing machine has symbol $$\sigma$$ after $$x$$ steps on the $$y$$ square.
• A 2-ary equals predicate

$$\mathcal{T}$$ shall have the following basic axioms in addition to the axioms for equality:

• $$\forall x\;\forall y\;(s(x) = s(y)) \to x = y)$$ i.e. the successor function is injective
• $$\neg \exists x\;s(x) = 0$$ i.e. 0 does not have a successor
• $$\forall x\;\neg(x = 0) \to \exists y\;s(y) = x$$ i.e. all numbers other than 0 have predecessors

$$\mathcal{T}$$ shall also have the following axioms for the Turing machine’s initial configuration:

• $$M_{q_0}(0, 0)$$
• Where $$\theta_1 ... \theta_n$$ are the initial symbols on the Turing machine’s tape, $$N_{\theta_1}(0,0) ... N_{\theta_n}(0, n-1)$$. Bearing in mind that $$n-1$$ is to be written formally as the application $$s$$ to 0, $$n-1$$ times.
• All other tape symbols are blank: $\forall x\;(\bigwedge_{i \in \{1..n\}} \neg (x = i)) \to (N_B(0, x))$

$$\mathcal{T}$$ also needs axioms to represent state transitions in the form, $$\delta(q, \sigma) = (q', \sigma', L)$$ or $$\delta(q, \sigma) = (q', \sigma', R)$$.

• To represent $$\delta(q, \sigma) = (q', \sigma', L)$$:

$\forall x\;\exists y\;(M_q(x, y) \wedge N_{\sigma}(x, y)) \to (M_{q'}(s(x), s(y)) \wedge N_{\sigma'}(s(x), y))$

• To represent $$\delta(q, \sigma) = (q', \sigma', R)$$:

$\forall x\;\exists y\;(M_q(x, s(y)) \wedge N_{\sigma}(x, s(y))) \to (M_{q'}(s(x), y) \wedge N_{\sigma'}(s(x), s(y)))$

• To represent non-changed tape symbols, for all $$\sigma \in \Sigma$$:

$\forall x\;\forall y\;(\neg M_{\sigma}(x, y) \to N_{\sigma}(s(x), y))$

To represent whether the machine halts the following sentence can be used, where $$X$$ represents pairs of $$(q, \sigma)$$ for which $$\delta$$ is undefined:

$\exists x\;\exists y\;(\bigvee_{(q, \sigma) \in X} (M_q(x, y) \wedge N_{\sigma}(x, y)))$

Clearly, because the halting problem is unsolvable, there cannot be an algorithm to decide whether the above proposition holds for a Turing machine. However, clearly there must exist a truth value to the above proposition. Therefore, first-order logic is undecidable.

## Bibliography

• Stanford’s online Coursera course on Automata Theory. The course is no longer available, but the video lectures have been put on YouTube.
• New Turing Omnibus by A. K. Dewdney
• The Annotated Turing by Charles Petzold
• Logic by Wilfrid Hodges
• Predicate and Propositional Logic: A Model of Argument by Derek Goldrei
• Representing Turing Machines, available here.