DISKRETE MATHEMATIK
Dr. E. Prisner, Dr. J. Sustal,
Dr. W. Preuß, S. Fröhlich,
Sommersemester 2000
Übungsblatt 4
Abgabe in der 5. Semesterwoche
4.1
Geben Sie eine möglichst kurze, zur Formel
(((¬p Ú q) ®
((p ® q) Ù
(q ® p))) Ù
(¬ (p ® q) ® ¬
(p « q)))
äquivalente Formel an.
4.2
Es gelten folgende Erfahrungsregeln:
- (P1) Wenn der Bus werktags verkehrt, dann ist er pünktlich
oder stark besetzt.
- (P2) Wenn der Bus pünktlich und schwach besetzt ist, dann ist er
gut temperiert,
- (P3) Wenn der Bus unpünktlich und schlecht temperiert ist,
dann ist er stark besetzt.
Formalisieren Sie diese und die folgenden Aussagen
und entscheiden Sie
(entweder semantisch durch Wahrheitstafeln oder durch
Anwendung von Äquivalenzen und Schlussregeln),
welche der nachfolgenden
Aussagen logisch aus obigen Aussagen (P1), (P2), (P3) folgen.
- (A) Der Bus kann auch nichtwerktags stark besetzt sein.
( Anders ausgedrückt:
Die Aussage (E): "Fährt der Bus nichtwerktags, so ist er schwach besetzt",
folgt nicht aus (P1), (P2) und (P3).
)
- (B) Wenn der Bus stark besetzt ist, dann ist er nie sowohl pünktlich
als auch gut temperiert.
- (C) Nichtwerktags, aber nur nichtwerktags, kommt es vor, daß der Bus trotz
schwacher Besetzung und guter Temperierung unpünktlich ist.
-
(D) An Werktagen wird es bei schwacher Besetzung nie vorkommen,
daß der Bus unpünktlich oder schlecht temperiert ist.
(Einige Eigenschaften beinhalten eine Graduierung, womit sie
sich besser mit der Fuzzy-Logik, oder mit der Mehrwertigen Logik
formalisieren lassen. Wir setzen vereinfacht voraus, daß eine Eigenschaft entweder
voll, oder gar nicht vorhanden ist.)
4.3 Bringen Sie die Formel
(¬ A ® D)
«
(C Å ¬ B)
in eine äquivalente
disjunktive Normalform.
4.4
(optional)
Zeigen Sie, daß {¬ , ®}
eine Junktorbasis bildet.
zu Blatt 5
April 2000