Blatt 06 PDF

Preview

Summary

übung...

Description

Prof. Dr. B. Steffen

Daniel Busch – Markus Frohme – Annika Fuhge – Marc Jasper – Dawid Kopetzki – Oliver Rüthing

Übungen zur Vorlesung

Mathematik für Informatik 1 Wintersemester 2020/21 Übungsblatt 6

Bitte sehen Sie eine gemeinsame Gruppenabgabe in Moodle vor (nur im PDF-Format!). Beachten Sie die Abgabefrist! Schreiben Sie unbedingt immer Ihren vollständigen Namen, Ihre Matrikelnummer und die Nummer Ihrer Übungsgruppe auf Ihre Abgaben! Abgabefrist: 18.12.2019, 14:00 Uhr

(2+3 Punkte)

Aufgabe 6.1 Vollständige Induktion

1. Zeigen Sie durch vollständige Induktion, dass für alle natürlichen Zahlen n ∈ N gilt: n X

2i = 2n+1 − 1

i=0

2. Sei x ∈ R mit x ≥ −1. Zeigen Sie durch vollständige Induktion, dass für alle natürlichen Zahlen n ∈ N gilt: (1 + x)n ≥ n x + 1

Aufgabe 6.2 Verallgemeinerte Induktion Die Fibonacci-Funktion fib : N → N ist induktiv definiert durch: fib(0) =df fib(1) =df

0 1

fib(n) =df

fib (n − 2) + fib (n − 1) für n ≥ 2

(3 Punkte)

Beweisen Sie mit Hilfe verallgemeinerter Induktion, das für alle natürlichen Zahlen n ∈ N gilt: (n ≥ 11) ⇒ fib (n) ≥

 n

3 2

Aufgabe 6.3 Strukturelle Induktion (4 Punkte) Zeigen Sie, dass für jeden Booleschen Term t ∈ BT ein semantisch äquivalenter Term t′ existiert, der weder T noch F enthält. Führen Sie den Beweis durch strukturelle Induktion über den Aufbau von t.

(Bonusaufgabe: 2+3 Punkte)

Aufgabe 6.4 Noethersche Induktion

1. In Aufgabe 5.3 wurde gezeigt, dass die lexikographische Ordnung ≤lex auf N × N eine partielle Ordnung ist. Zeigen Sie, dass ≤lex auch Noethersch ist. 2. Wir betrachten die rekursiv definierte Ackermann-Funktion (siehe Buch Seite 175):

ack : N × N → N ack(n, m) =

   m+1  

ack(n − 1, 1)

if n = 0 if n > 0, m = 0

ack (n − 1, ack (n, m − 1))

if n > 0, m > 0

Beweisen Sie durch Noethersche Induktion über die lexikographische Ordnung der Argumente: ∀ n, m ∈ N. m < ack (n, m)

2...