Transcript
Christian Eisentraut & Julia Krämer www.vorkurs-mathematik-informatik.de
Mathematik-Vorkurs für Informatiker Logik Aufgabe 1. (4 Punkte) Stellen Sie sich vor, Sie müssten den Vorkurs bestehen. Gegeben seien die folgenden Aussagen. • a := “Sie haben 95% aller Übungsaufgaben bearbeitet.” • b := “Sie waren in 14 von 15 Übungsstunden anwesend.” • c := “Sie waren in 14 von 15 Vorlesungen anwesend.” • d := “Sie haben den Stoff der Vorlesungen sinnvoll nachgearbeitet.” • e := “Sie haben die Klausur bestanden.” Die Aussagen werden wie folgt verknüpft: ((a ∧ b) ↔ e) ∧ (c ∨ d) ∧ e. Geben Sie die Bedingungen an, die gelten müssen, damit Sie den Vorkurs bestehen, und erklären Sie, wieso. Aufgabe 2. (2 + 3 + 3 = 8 Punkte) Der aussagenlogische Operator “∧” (NAND bzw. not and) wird wie folgt definiert: Die erweiterte Backus-Naur-Form der Aussagenlogik lautet mit dem Operator NAND L ∋ Φ, Ψ ::= ¬Φ | ... | Φ∧Ψ. Seine Wahrheitstafel sieht wie folgt aus: p q p∧q f f w f w w w f w w w f Mit Hilfe der Wahrheitstabelle kann man auch die Semantikabbildung um NAND erweitern. (a) Erweitern Sie induktive Definition der Semantikabbildung aus der Vorlesung bzw. aus dem Skript um den Operator “∧”. (b) Zeigen Sie, dass ∧ bezüglich der Aussagenlogik vollständig ist, d.h. dass sich alle anderen Operatoren mit NAND darstellen lassen. (c) Definieren Sie nun den Operator NOR (not or). Ist dieser auch vollständig bezüglich der Aussagenlogik?
1
Aufgabe 3. (4 Punkte) Betrachten Sie die folgende Aussage: Wenn jede schlechte Bäckerin eine gute Bäckerin als Mutter hat, dann gibt es mindestens eine gute Bäckerin mit einer guten Bäckerin als Großmutter. Übersetzen Sie die Aussage mit Hilfe der Prädikate P (x) := “x ist gute Bäckerin” und Q(x, y) := “x ist Mutter von y” in einen prädikatenlogischen Ausdruck. Aufgabe 4. (2 + 4 + 2 = 8 Punkte) Betrachten Sie den folgenden Satz: “Ein Barbier ist ein Mann, der genau alle Männer rasiert, die sich nicht selbst rasieren.”. (a) Schreiben Sie diesen Satz in eine formale Definition der Form: Sei y ein Element der Menge aller Männer, y ist genau dann ein Barbier, wenn es den Ausdruck …erfüllt. Verwenden Sie das Prädikat P (x, y) über der Menge aller Männer, welches definiert ist als “x rasiert y”. (b) Finden Sie mittels Umformungen nach den Gesetzen der Prädikaten- und Aussagenlogik etwas über den Wahrheitsgehalt der Aussage heraus. Was wissen Sie nun über Barbiere? (c) Wie können Sie das Problem sinnvoll beheben? Machen Sie einen Vorschlag!
2
