Exercise 1.1.

The set of strings of finite length formed from the symbols $0$ and $1$ is denoted ${2}^{*}$ or ${2}^{<\omega}$. A system of deduction for strings $\sigma \in {2}^{*}$ is given with deduction rules

- From a string $\sigma $ you may deduce $\sigma \prime $ where $\sigma \prime $ is the result of replacing any substring $00$ of $\sigma $ with $1$. In other words, from $\sigma =x00y$ you may deduce $\sigma \prime =x1y$.
- From a string $\tau $ you may deduce $\tau \prime $ where $\tau \prime $ is the result of replacing any substring $11$ of $\tau $ with $0000$. In other words, from $\tau =x11y$ you may deduce $\tau \prime =x0000y$.

We write $\sigma \u22a2\tau $ to mean $\tau $ may be deduced from $\sigma $ by finitely many applications of these rules.

(a) Find the set $\left\{\tau \in {2}^{*}:111\u22a2\tau \right\}$, carefully justifying your answer.

(b) Let $f\left(\sigma \right)$ be the number of $0$s in $\sigma $ plus twice the numbers of $1$s in $\sigma $. Show that $\sigma \u22a2\tau $ implies $f\left(\sigma \right)=f\left(\tau \right)$. Deduce that $000011110000\u22ac111100001111$.

(c) Prove that $\left\{\tau \in {2}^{*}:\sigma \u22a2\tau \right\}$ is finite for all $\sigma \in {2}^{*}$.

(d) Explain why (b) above may be regarded as
a soundness theorem

. Briefly suggest a corresponding
completeness theorem

and state one or more additional
deduction rules that may be required for your completeness
theorem to be true.

Exercise 1.2.

(a) Let $p$ be a proposition with truth value *true*
or *false*. Show that one of

and

$$\left(\right(p\to p)\to p),$$is a true statement irrespective of whether or not $p$ is true or false and the other is not.

(b) A proof system $S$ is presented for the alphabet with symbols
$\to $, $p$, $q$, $r$, but no brackets. A
*well-formed-formula* (wff) is a string of the form
$x\to y\to z\to \dots \to w$, where
$x,y,z,w$ are arbitrary letters
(not necessarily distinct) and there are one or more such letters.
The rules for this proof-system are:

- the string $\varphi \to \varphi $ may be written down (derived) at any time, and
- if $\varphi \to \psi $ and $\varphi $ have both been written down (derived) then so may $\psi $ be,

for any wffs $\varphi ,\psi $. Show that if $\theta $ can be derived in $S$ then $\theta $ contains an odd number of occurences of the symbol $\to $.

(c) Give an example of a string of symbols from $p,q,r,\to $ which has an odd number of occurrences of $\to $ but is not derivable in $S$. Hint: consider the number of times each letter can occur in the string $\varphi $.