Mathematik und Logik

8. Übungsaufgaben im 2007W

für 2007-12-04

1. Zeigen Sie: (u^˜)^˜ = u.
2. Zeigen Sie: (g∘f)˟=g˟∘f˟.
3. Testen Sie, ob die Funktion, definiert durch
   

   e(⟨⟩) =0, e(u▻α) =10⋅e(u)+α,

   tatsächlich die zu gegebenen Dezimalziffern gehörige Zahl bestimmt. Definieren Sie dann eine Funktion d, welche zu jeder Zahl n∊ℕ die Liste ihrer Ziffern im Dezimalsystem bestimmt, und beweisen Sie, daß tatsächlich e(d(n))=n, für alle n.
4. Unter welcher Bedinung liefern u φ^← e und e φ^→ u dasselbe Ergebnis?
5. Definieren Sie eine Funktion, welche für verschachtelte Listen die Länge jeder Liste bestimmt, z.B. 
   

   ℓ ⟨⟨1,2,3⟩,⟨⟩,⟨4⟩,⟨4,5⟩,⟨5,3,3⟩⟩ = ⟨3,0,1,2,3⟩.
6. Definieren Sie eine Funktion, welche verschachtelte Listen etwas abflacht, z.B. 
   

   f ⟨⟨1,2,3⟩,⟨⟩,⟨4⟩,⟨4,5⟩,⟨5,3,3⟩⟩ = ⟨1,2,3,4,4,5,5,3,3⟩.
7. Definieren Sie eine Funktion, welche aus der Liste der Zahlen zwischen 0 und n alle zu n teilerfremden Zahlen auswählt.
8. Eine Menge Σ heißt diskret, wenn für je zwei Elemente x,y∊Σ gilt
   

   x=y ∨ xy,

   in dem Sinne, daß man tatsächlich eine Methode kennt, welche stets entscheidet, welche der beiden Alternativen zutrifft.
   Zeigen Sie, daß Σ˟ diskret ist, wann immer Σ diskret ist.