Mathematik und Logik

7. Übungsaufgaben im 2007W

für 2007-11-27

1. Zeigen Sie:
   

   ∀A∊ℙ(¬¬¬A \implies A).
2. Zeigen Sie
   

   ∀A∊ℙ(A∨¬A) ⇔ ∀A∊ℙ(¬¬A \implies A).
3. Können Sie die Allgemeingültigkeit der Formel
   

   ( ( P\implies Q)\implies P) \implies P

   nachweisen?
   Vereinfacht sich die Angelegenheit, wenn Sie
   

   ∀A∊ℙ(A∨¬A)

   verwenden?
4. Zeigen Sie, daß die Länge einer Liste ein Homomorphismus ist, d.h.
   

   ∀u,v∊Σ˟⎢u◊v⎥=⎢u⎥+⎢v⎥.
5. Definieren Sie rekursiv eine Funktion ▻ ∊Σ˟→Σ→Σ˟, welche an eine Liste hinten anfügt, z.B.⟨3,5,6⟩▻2 = ⟨3,5,6,2⟩.
   Wie ist der Zusammenhang zwischen ▻ und ◊?
   Vergessen Sie nicht, das Ergebnis anhand einfacher Beispiele zu testen.
6. Die Spiegelung [(u)\tilde] einer Liste u kehrt die Reihenfolge der Elemente um, also z.B.[⟨1,2,3⟩\tilde]=⟨3,2,1⟩. Definieren Sie diese Funktion rekursiv und zeigen Sie mittels Listen-Induktion, daß [(u◊v)\tilde]=[(v)\tilde] ◊ [(u)\tilde].
7. Wir hätten für Listen statt ◅ genausogut ▻ als Konstruktor neben ⟨⟩ verwenden können. Wie würden dann Induktion und Rekursion aussehen? Wie würde man ◊ und ◅ dann definieren?
8. Zeigen Sie für alle Listen u,v:
   

   u◊v=⟨⟩ ⟹ u=⟨⟩ ∨ v=⟨⟩.