# Assessment exercises 1

Exercise 1.1.

The set of strings of finite length formed from the symbols $0$ and $1$ is denoted $2 *$ or $2 < ω$. A system of deduction for strings $σ ∈ 2 *$ is given with deduction rules

1. From a string $σ$ you may deduce $σ ′$ where $σ ′$ is the result of replacing any substring $0 0$ of $σ$ with $1$. In other words, from $σ = x 0 0 y$ you may deduce $σ ′ = x 1 y$.
2. From a string $τ$ you may deduce $τ ′$ where $τ ′$ is the result of replacing any substring $1 1$ of $τ$ with $0000$. In other words, from $τ = x 1 1 y$ you may deduce $τ ′ = x 0 0 0 0 y$.

We write $σ ⊢ τ$ to mean $τ$ may be deduced from $σ$ by finitely many applications of these rules.

(a) Find the set ${ τ ∈ 2 * : 1 1 1 ⊢ τ }$, carefully justifying your answer.

(b) Let $f ( σ )$ be the number of $0$s in $σ$ plus twice the numbers of $1$s in $σ$. Show that $σ ⊢ τ$ implies $f ( σ ) = f ( τ )$. Deduce that $000011110000 ⊬ 111100001111$.

(c) Prove that ${ τ ∈ 2 * : σ ⊢ τ }$ is finite for all $σ ∈ 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

$( p → ( p → p ) )$

and

$( ( p → p ) → 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 $→$, $p$, $q$, $r$, but no brackets. A well-formed-formula (wff) is a string of the form $x → y → z → … → 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:

1. the string $ϕ → ϕ$ may be written down (derived) at any time, and
2. if $ϕ → ψ$ and $ϕ$ have both been written down (derived) then so may $ψ$ be,

for any wffs $ϕ , ψ$. Show that if $θ$ can be derived in $S$ then $θ$ contains an odd number of occurences of the symbol $→$.

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