Københavns Universitet

Naturvidenskabelig embedseksamen, første del Matematik & Beregninger

Skriftlig eksamen 3. februar 2006

Sættet består af 3 opgaver, som vægtes ens. Ligeledes vægtes alle delspørgsmål i en opgave ens. I tilfælde af fejl eller unøjagtigheder i opgaveteksten forventes det, at eksaminanderne selv præciserer besvarelsens forudsætninger. Alle sædvanlige hjælpemidler er tilladt. Opgavesættet besvares på separate ark, der udleveres af eksamenstilsynet. Besvarelsen kan formuleres på dansk eller engelsk eller en blanding heraf. Indskrivning med blyant er tilladt. Opgaveteksten kan deltagerne tage med sig.

Mathematics and Computation Exam February 3, 2006

Exercise 1. Specify for the following list of terms and statements the values of the terms and whether the statements hold or fail:

(a) 1.00F − 0.7655 ^{·}  (b) (−5) % 2 ^{·}
(c) 4 > 1, 3 > 2 ^{·}  (d) ⟨1⟩ : : (⟨2, 3⟩ : : ⟨ ⟩) : : ⟨ ⟩ ≡ ⟨⟨1⟩, ⟨2 : : ⟨3⟩⟩⟩ ^{·}
(e) (λy.⟨λy.y | y:=3 · y⟩) ’ x ^{·} (f) Y ’ λx.−x ^{·}
(g) N : : ⟨ ⟩ head ^{·}  (h) (N : : ⟨ ⟩) Head ^{·}
(i) ElimB ⊳ 5 ∈ B ⊳ \overline{B} ’ 5 ^{·} (j) N : : 3 : : ⊥ ⪯ N : : 4 : : ⊥ ^{·}
(k) N ˙. . F = F ^{·}  (l) λx.case(x, F, T) ≡ ⟨ ⟩ ^{·}
(m) ∃x ∈ Z: x! = 2 ^{·}  (n) ∃x ∈ Z: ∀y ∈ Z: y = x ^{·}
(o) ∀x ∈ Z: ∃y ∈ Z: x = y ^{·} (p) 15 // (εx ∈ N: 15 // x = 5) ^{·}

Exercise 2. I define

f(m, x) ≐ if(m = 0, x, f(m − 1, x tail)) .

Prove the following lemma:

Mac lemma L06.1.1: ∃m ∈ N: f (m, ⟨ ⟩) = ⟨ ⟩ ^{·}

Hint: The proof may use the following instance of Mac rule Definition: f(m, ⟨ ⟩) ≡ if(m = 0, x, f(m − 1, ⟨ ⟩ tail)) ^{·}

Exercise 3. Prove the following antilemma:

Mac antilemma L06.1.2: ∀x ∈ F: ⟨ ⟩ ’ ( ¬x ) Tail = x Tail ^{·}

Hint: The proof may use the following instance of Mac rule ElimAll: F ∈ Set ⊳ L06.1.2 ⊳ N ˙. . F ∈ F ⊳ ⟨ ⟩ ’ ( ¬ N ˙. . F) Tail = (N ˙. . F) Tail ^{·}