close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Diskrete Strukturen

EinbettenHerunterladen
Technische Universit¨at M¨
unchen
Fakult¨at f¨
ur Informatik
Lehrstuhl f¨
ur Wissenschaftliches Rechnen
Prof. Dr. Hans-Joachim Bungartz
Dr. Werner Meixner
Wintersemester 2014/15
¨
Ubungsblatt
4
28. Oktober 2014
Diskrete Strukturen
Abgabetermin: 4. November 2014, 14 Uhr in die DS Briefk¨
asten
Hausaufgabe 1 (5 Punkte)
F¨
ur beliebige Mengen A, B, C gelten nach Vorlesung die Gleichungen Idempotenz, Kommutativit¨at, Assoziativit¨at, Distributivit¨at sowie Neutralit¨at (X ∪ ∅ = X) und Nulleigenschaft (X ∩ ∅ = ∅) f¨
ur Mengenoperationen. Zus¨atzlich wurde in HA 4, Blatt 3 das
Absorptionsgesetz A ∪ (A ∩ B) = A gezeigt.
1. Zeigen Sie unter ausschließlicher Verwendung der oben genannten Gleichungen die
Gleichung
(B ∩ (A ∪ C)) ∩ (A ∩ B) = A ∩ B
2. Wie kann man diese Gleichung mit Hilfe des in TA 3.2, Blatt 1 benutzten abstrakten
Venn-Diagramms zeigen?
Hausaufgabe 2 (5 Punkte)
¨
Uber
M = {a, b, c} betrachten wir die folgenden Relationen R1 = {(b, c), (c, b), (a, a)} ,
R2 = {(a, b), (b, c), (c, c), (c, b)} und R3 = {(a, c), (b, c), (a, a), (b, b), (c, c)} .
1. Welche dieser Relationen sind reflexiv, transitiv?
Begr¨
unden Sie Ihre Antworten!
2. Berechnen Sie R1 ◦ R2 , R2∗ und R3∗ !
Hausaufgabe 3 (5 Punkte)
Seien n ∈ N und Mn = [n] × [n]. Wir bezeichnen Mn als die Menge der Gitterpunkte
mit ganzahligen Komponenten aus [n]. Wir definieren u
¨ber Mn eine bin¨are Relation Gn
zwischen benachbarten“ Gitterpunkten durch Gn = Hn ∪ Vn mit
”
Hn = { ( (x, y), (x+1, y) ) | x ∈ [n−1], y ∈ [n] } (horizontal benachbart) ,
Vn = { ( (x, y), (x, y+1) ) | x ∈ [n], y ∈ [n−1] } (vertikal benachbart) .
1. Bestimmen Sie die Anzahl der Elemente der transitiven H¨
ulle von G3 .
Begr¨
unden Sie Ihr Ergebnis!
2. Wir betrachten die Komposition G33 = (G3 ◦ G3 ) ◦ G3 der Relation G3 .
Wie viele Elemente enth¨alt G33 ? Begr¨
undung!
Geben Sie ein Hasse-Diagramm der reflexiven transitiven H¨
ulle von G33 an! Begr¨
undung!
Hausaufgabe 4 (5 Punkte)
Es sei die Funktion c : N × N → N gegeben durch
c(x, y) =
(x + y − 1)(x + y − 2)
+ x.
2
Vorschrift: Man beginne im Schritt n = 1 mit (1, 1). Wenn man im n-ten Schritt die Tupel
(x, y) mit n = x+y −1 durchlaufen hat, dann durchlaufe man im n¨achsten Schritt n+1
alle Tupel (x, y) mit x+y − 1 = n+1, und zwar so, dass die Paare mit kleinerer erster
Koordinate x zuerst durchlaufen werden.
Diese Vorschrift definiert pr¨azise die Abbildung c.
1. Zeigen Sie mit Hilfe der Funktion c, dass die Menge N der nat¨
urlichen Zahlen und
die Menge N × N der Paare nat¨
urlicher Zahlen gleichm¨achtig sind!
2. Konstruieren Sie eine surjektive Abbildung f : Z → (Q+ ∪ {0}) der Menge der
ganzen Zahlen Z auf die Menge der nichtnegativen rationalen Zahlen Q+ ∪ {0} !
2
Hinweis: Die Vorbereitungsaufgaben dienen der h¨auslichen Vorbereitung der Tutoraufgaben
und werden in der Zentral¨
ubung unterst¨
utzt.
Vorbereitung 1
¨
Zeigen Sie durch Benutzung von Aquivalenzregeln
die Allgemeing¨
ultigkeit bzw. logische
¨
Aquivalenz der folgenden Ausdr¨
ucke.
1. (p ∧ q) → p .
2. q → (p ∨ q) .
3. (p ∧ q) ↔ p ≡ p → (p ∧ q) .
4. q ↔ (p ∨ q) ≡ (p ∨ q) → q .
Vorbereitung 2
Die ¨aquivalente Einf¨
ugung neuer Variablen in einen aussagenlogischen Ausdruck benutzt
die Gesetze true ≡ ¬x ∨ x oder false ≡ ¬x ∧ x. Bestes Beispiel ist der Beweis der
sogenannten Absorptionsgesetze.
¨
Zeigen Sie die folgenden Aquivalenzen
p ≡ p ∨ (p ∧ q) und p ≡ p ∧ (p ∨ q) .
Vorbereitung 3
Eine konjunktive Normalform (KNF) eines aussagenlogischen Ausdrucks ist im Sinne der
Vorlesung eine Konjunktion von Disjunktionen (Klauseln), d.h. eine Formel der Form
mi
n
i=1 ( j=1 Li,j ) mit n, mi ∈ N0 und Literalen Li,j . Entsprechend ist eine disjunktive Nori
malform (DNF) eine Disjunktion von Konjunktionen der Form ni=1 ( m
j=1 Li,j ).
Diese Normalformen sind i.A. nicht eindeutig. Wenn in jeder Klausel einer KNF alle Variablen der Formel genau einmal vorkommen und keine Klausel mehrfach vorkommt, dann
spricht man von einer vollst¨andigen KNF. Entsprechend definiert man eine vollst¨andige
DNF.
1. Leiten Sie eine vollst¨andige disjunktive Normalform f¨
ur die folgende Formel F1 her:
F1 := ¬p ∨ (p ∧ q ∧ r) .
2. Leiten Sie durch ¨aquivalente Umformung eine vollst¨andige konjunktive Normalform
f¨
ur die folgende Formel F2 her:
F2 := (¬p ∨ q) ∧ (¬p ∨ r) .
¨
3. Leiten Sie mit Hilfe der vollst¨andigen Normalformen die Aquivalenz
F1 ≡ F2 her.
Vorbereitung 4
Sei H eine beliebige aussagenlogische Formel und x eine aussagenlogische Variable.
1. Zeigen Sie, dass H ↔ ((x → H) ∧ (¬x → H)) allgemeing¨
ultig ist.
2. Zeigen Sie, dass H ↔ ((x → H[x \ true]) ∧ (¬x → H[x \ false])) allgemeing¨
ultig ist.
3
Tutoraufgabe 1
1. Wie viele bin¨are (boolesche) Operationen
: {0, 1} × {0, 1} → {0, 1} gibt es, so
dass
x false
ein Widerspruch ist?
2. Sei eine beliebige bin¨are boolesche Operation, so dass x
ist. Zeigen Sie, dass dann die Formel
(x
(y ↔ z)) → ((x
y) ↔ (x
false ein Widerspruch
z))
eine Tautologie ist.
Hinweis: Untersuchen Sie getrennt die passenden minimalen Belegungen β, f¨
ur die
[y ↔ z](β) = 1 bzw. f¨
ur die [y ↔ z](β) = 0 gilt.
Tutoraufgabe 2
Ben¨
utzen Sie im Folgenden die Ergebnisse der Vorbereitungsaufgaben 1 und 4.
¨
1. Zeigen Sie durch Anwendung von Aquivalenzregeln
die sogenannte goldene Regel“
”
(p ∧ q) ↔ p ≡ q ↔ (p ∨ q) .
2. Wir beweisen nun die goldene Regel noch einmal in der allgemeing¨
ultigen Form
((p ∧ q) ↔ p) ↔ (q ↔ (p ∨ q)) .
Allerdings soll nun die Fallunterscheidung im Sinne der VA 4 ben¨
utzt werden. Machen Sie die Fallunterscheidung durch Substitution true bzw. false f¨
ur p und wenden
¨
Sie entsprechende Aquivalenzregeln
zur Vereinfachung an.
Tutoraufgabe 3
Wir untersuchen die aussagenlogischen Normalformen f¨
ur den folgenden aussagenlogischen
Ausdruck F aus TA 2.2 von Blatt 3:
F := ((p → q) ∧ (p → r)) ∨ (q ∧ r) .
1. Zeigen Sie, dass die folgende Formel FK eine konjunktive Normalform f¨
ur F ist:
FK := (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ r) .
2. Bestimmen Sie die vollst¨andige disjunktive Normalform f¨
ur F .
¨
3. Vergleichen Sie F semantisch mit F1 und F2 aus VA 3. Welche Aquivalenzen
k¨onnen
Sie daraus ableiten?
4. Wenden Sie das Verfahren DPLL Nr.2 der Vorlesung auf FK an und beweisen Sie
damit, dass die Formel FK erf¨
ullbar ist.
4
Document
Kategorie
Gesundheitswesen
Seitenansichten
23
Dateigröße
91 KB
Tags
1/--Seiten
melden