Assessment exercises 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

We write $\sigma ⊢\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⊢\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 ⊢\tau$ implies $f\left(\sigma \right)=f\left(\tau \right)$. Deduce that $000011110000⊬111100001111$.

(c) Prove that $\left\{\tau \in 2^{*}:\sigma ⊢\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.

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

and

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:

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