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