Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 1 — Abgabetermin: 23. April 2004, 11.00 Uhr

Quiz 1

Markieren Sie die nachfolgenden Aussagen als wahr (w) oder falsch (f).

[ ] Das Wort ”DrückenDrücken” kann durch die Grammatik {S→SDrückenDrücken, S→ϵ} und durch den regulären Ausdruck (DrückenDrücken)^{∗} erzeugt werden.

[ ] Die Korrektheit von Programmen kann einfach durch Testen bewiesen werden. [ ] Die Aussage ”2^{x}≥x^{2} genau dann, wenn x≥4” ist beweisbar. [ ] Aus ”A ⇒ B” und ”(nicht A) ⇒ (nicht B)” folgt ”A ⇔ B” [ ] Die Zwischenaussagen eines Beweises müssen logisch aus den Annahmen folgen.

Aufgabe 1.1 (Beweisführung: Wenn-Dann Aussagen)

Geben Sie Wahrheitstabellen für die folgenden Aussagen an, in Abhängigkeit der Wahrheitswerte für A und B: (nicht A); (nicht B); A ⇒ B; (nicht B)⇒(nicht A); (nicht A) oder B; aus A folgt B (A impliziert B); B ⇒ A; A ⇒ B und B ⇒ A; A ⇔ B.

Tipp: Sie können eine einzige Tabelle für alle Aussagen benutzen.

Aufgabe 1.2 (Deduktive Beweisführung, Gegenbeispiele)

1. Geben Sie sowohl einen informalen als auch einen formalen deduktiven Beweis für den folgenden Satz an: Wenn x ≥ 3 dann 4^{x} ≥ 4x^{2}. Sie dürfen bereits bewiesene Sätze aus der Vorlesung benutzen (z.B. den in Kapitel 1, Folie 14).

2. Zeigen Sie, dass die folgende Aussage falsch ist: x ≥ 3 genau dann, wenn 4^{x} ≥ 4x^{2}.

Tipp: Drücken Sie die Äquivalenz (”.. genau dann, wenn ..”) der Aussage durch zwei Implikations-Aussagen (”.. impliziert ..”) aus und zeigen Sie durch Angabe eines Gegenbeispiels, die Falschheit einer dieser Aussagen.

Aufgabe 1.3 (Beweis von Mengenäquivalenzen) [3 Punkte]

Geben Sie einen formalen Beweis für den folgenden Satz an:

Für beliebige Mengen R, S, T gilt R ∩ (S ∪ T) = (R ∩ S) ∪ (R ∩ T).

Tipp: Formulieren Sie die Mengengleichheit zunächst als Genau-dann-wenn Ausssage.

Übung zur Vorlesung Theoretische Informatik I Blatt 1

Aufgabe 1.4 (Wenn-Dann Aussagen, Deduktive Beweisführung) [3 Punkte]

Die folgenden Aussagen seien wahr:

(1) A ⇒ (B und C)

(2) (D oder B) ⇒ E

(3) (nicht C) ⇔ (nicht D)

(4) B ⇐ F

(5) F ⇒ ((nicht E) oder nicht D)

(6) (nicht G) ⇒ F

Geben Sie einen deduktiven Beweis für die Wahrheit der Aussage A ⇒ G an.

Aufgabe 1.5 (Induktive Beweise: Vollständige Induktion) [3 Punkte]

Beweisen Sie mit Hilfe der vollständigen Induktion die folgende Aussage S(n):

Für alle n≥0 gilt: ∑_{i=1}^{n} \frac{i}{2} = \frac{1}{4}n(n + 1)

Geben Sie in Ihrem Beweis den Induktionsbeginn S(0), die Induktionshypothese S(n) und den Induktionsschritt S(n) ⇒ S(n + 1) an.

Hausaufgaben:

Für jede Hausaufgabe können Sie maximal 3 Punkte bekommen. Die Vergabe der Punkte richtet sich nach den folgenden Regeln:

3 Punkte – die Aufgabe wurde im Wesentlichen korrekt gelöst 2 Punkte – die Aufgabe wurde nur teilweise gelöst 1 Punkt – die Lösung der Aufgabe enthielt größere Fehler oder Lücken 0 Punkte – die Aufgabe wurde nicht gelöst oder enthielt sehr viele Fehler oder Lücken

Sprechstunden:

Haben Sie Fragen, Anregungen oder Probleme? Lassen Sie es uns wissen!

• Prof. Christoph Kreitz, Raum 1.18, kreitz@cs.uni-potsdam.de, Tel. 0331/977 3060

Sprechstunde: immer, wenn die Türe des Raumes 1.18 offen steht, und am Mittwoch 11.00 bis 12.30 Uhr

• Jens Otten, Raum 1.20, jeotten@cs.uni-potsdam.de, Tel. 0331/977 3072

Sprechstunde: immer, wenn die Türe des Raumes 1.20 offen steht, und am Dienstag 14.00 bis 16.00 Uhr.