close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

ENTDECKEN SZENE SHOPPING STANDARDS LEBEN

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
3
21. Oktober 2014
Diskrete Strukturen
Abgabetermin: 28. Oktober 2014, 14 Uhr in die DS Briefk¨
asten
Hausaufgabe 1 (4 Punkte)
Die Mengendarstellung der nat¨
urlichen Zahlen bzw. der Null wird durch die folgende
Operation definiert. Die Null wird dargestellt durch die leere Menge 0 = ∅. Die Darstellung
n des Nachfolgers n+1 einer Zahl n ∈ N0 ist definiert durch n = n∪{n}. (Der Fettdruck
dient der metasprachlichen Bezeichnung von Mengen.)
Generieren Sie die expliziten Darstellungen der Zahlen 1, 2, 3, 4 ∈ N als Mengen.
Hausaufgabe 2 (4 Punkte)
Gegeben seien die Mengen und A = {−1, 0, 1} und B = {a, aa, bb} .
1. Geben Sie das kartesische Produkt A × B extensional an !
2. Es bezeichne ◦ das Produkt von Relationen. Welche Kardinalit¨at hat
(A × B) ◦ (B × A) ?
Hausaufgabe 3 (4 Punkte)
1. Zeichnen Sie ein Hasse-Diagramm H f¨
ur die Relation x Teiler von y“, i. Z. x|y, auf
”
der Teilmenge M = [24] \ [5] der nat¨
urlichen Zahlen.
Geben Sie die reflexive H¨
ulle von H extensional an.
2. Bestimmen Sie das Bild der Relation H.
Hausaufgabe 4 (4 Punkte)
Wir wissen, dass X ∩ ∅ = ∅ und X ∪ ∅ = X f¨
ur alle Mengen X gilt.
1. Seien D1 , D2 und D3 paarweise disjunkte Mengen. Zeigen Sie, dass f¨
ur
A = D1 ∪ D2 und B = D2 ∪ D3 das Absorptionsgesetz A ∪ (A ∩ B) = A gilt.
2. Zeigen Sie, dass das Absorptionsgesetz A = A ∪ (A ∩ B) f¨
ur beliebige Mengen A, B
gilt.
Hausaufgabe 5 (4 Punkte)
Sei n eine nat¨
urliche Zahl. Dann bezeichnet y n das Produkt mit n Faktoren y.
1
Eine Zahl y heißt eine n-te Wurzel aus x, i. Z. y = x n , wenn y n = x gilt. Zeigen Sie:
1
1
gilt, dann gibt es m und n mit m < m und n < n, so dass 5 3 = m
.
Wenn 5 3 = m
n
n
1
Was bedeutet dies f¨
ur die Frage, ob 5 3 eine rationale Zahl ist?
Hinweis: m, m , n, n sind stets nat¨
urliche Zahlen, m
, m sind Br¨
uche und stellen rationale
n n
Zahlen dar.
Zusatzaufgabe 1 (wird nicht korrigiert)
1. F¨
ur Zahlen s und t heißt m = (s + t)/2 das arithmetische Mittel von s und t.
Man zeige f¨
ur rationale Zahlen s < t, dass dann s < m < t gilt!
2. Zwischen je zwei rationalen Zahlen s und t liegen unendlich viele rationalen Zahlen.
Man sagt deshalb, dass die rationalen Zahlen dicht liegen.
Zeigen Sie: wenn s und t rationale Zahlen sind mit s < t, dann gibt es unendlich
viele rationale Zahlen r1 , r2 , . . . mit s < r1 < r2 < . . . < t.
2
Hinweis: Die Vorbereitungsaufgaben dienen der h¨auslichen Vorbereitung der Tutoraufgaben
und werden in der Zentral¨
ubung unterst¨
utzt.
Vorbereitung 1
1. Gibt es eine injektive Abbildung f : N × N → N? Begr¨
undung!
2. Gibt es eine surjektive Abbildung f : N → Z? Begr¨
undung!
3. Gilt f¨
ur f : X → Y und A ⊆ X stets f −1 (f (A)) ⊆ A? Begr¨
undung!
Vorbereitung 2
Bestimmen Sie die Semantik des folgenden aussagenlogischen Ausdrucks in den Variablen x, y, z als Wahrheits(wert)tabelle:
((x → y) ∧ ¬(x → z)) ∨ (z → y) .
Vorbereitung 3
Seien x, y, z Variablenbezeichungen aus dem Vokabular der aussagenlogischen Syntax.
1. Sei β eine Belegung mit β(x) = 1, β(y) = 0, β(z) = 1. Ist β passend zu dem Ausdruck x ↔ z ?
2. Wie viele minimale passende Belegungen gibt es zu x ↔ y ? Welche sind das?
3. Berechnen Sie [x ↔ y](β), mit obigem β !
4. Ist x ↔ y allgemeing¨
ultig? Begr¨
undung!
Vorbereitung 4
1. Geben Sie eine aussagenlogische Formel F an, so dass F und ¬F erf¨
ullbar sind!
2. Geben Sie eine nicht erf¨
ullbare Formel an!
Vorbereitung 5
Seien q, r, s Variablenbezeichnungen aus dem Vokabular der aussagenlogischen Syntax. Die aussagenlogischen Formeln F und G seien gegeben durch
F = (q ∨ r) ↔ (q ∨ s)
und G = ((q ∨ r) ↔ (q ∨ s)) ↔ (q ∨ (r ↔ s)) .
1. Zeigen Sie, dass F und ¬F erf¨
ullbare Formeln sind.
2. Bestimmen Sie die Semantik von G. Zeigen Sie, dass F und G semantisch nicht a¨quivalent sind,
d. h. F ≡ G.
3. Zeigen Sie, dass ¬G ein Widerspruch ist. Was bedeutet dies f¨
ur G ?
3
Tutoraufgabe 1
1. Finden Sie ein Beispiel f¨
ur Mengen X, Y, A1 , A2 mit A1 , A2 ⊆ X und eine Abbildung
f : X → Y , so dass f (A1 \ A2 ) = f (A1 ) \ f (A2 ) gilt.
2. Ist die Abbildung f : Z → N0 mit f (x) = x2 injektiv, surjektiv, bijektiv? Begr¨
undung!
3. Zeigen Sie, dass f¨
ur die Komposition ◦ zweier Abbildungen f : A → B und
g : B → C gilt: Ist g ◦ f bijektiv (auf C), dann ist f injektiv und g surjektiv
(auf C).
Tutoraufgabe 2
Seien p, q, r Variablenbezeichnungen aus dem Vokabular der aussagenlogischen Syntax.
1. Zeigen Sie, dass ¬p ∨ q¬ keine aussagenlogische Formel ist.
2. Bestimmen Sie die Wahrheitstabelle f¨
ur den folgenden booleschen Ausdruck:
((p → q) ∧ (p → r)) ∨ (q ∧ r) .
Tutoraufgabe 3
Seien p, q, r, s Variablenbezeichnungen aus dem Vokabular der aussagenlogischen Syntax.
Die aussagenlogischen Formeln F und G seien gegeben durch
F = (q ∨ r) ↔ (q ∨ s) und G = ((q ∨ r) ↔ (q ∨ s)) ↔ (q ∨ (r ↔ s)) .
1. Geben Sie alle zu F passenden, minimalen Belegungen als geeignet sortierte Liste
B an.
2. Bestimmen Sie die Bedeutung [F ] von F , indem Sie B zu einer Wahrheitstabelle f¨
ur
[F ] erweitern.
3. Bestimmen Sie die Semantik von G. Zeigen Sie, dass F und G semantisch nicht
¨aquivalent sind, d. h. F ≡ G.
4
Document
Kategorie
Gesundheitswesen
Seitenansichten
11
Dateigröße
110 KB
Tags
1/--Seiten
melden