Loesung blatt 01 losung lmu 2021 erste blatt PDF

Preview

Summary

Dr. Jan Johannsen Ludwig-Maximilians-Universität München Stephan Holzner Institut für Informatik 15. April 2021Lösungsvorschlag zur 1. Übung zur VorlesungLogik und Diskrete StrukturenHinweise: - Die A-Aufgaben bezeichnen Aufgaben, die in den Tutorien in Anwesenheit gerechnet oder besprochen werden, ...

Description

Dr. Jan Johannsen Stephan Holzner

Ludwig-Maximilians-Universität München Institut für Informatik 15. April 2021

Lösungsvorschlag zur 1. Übung zur Vorlesung

Logik und Diskrete Strukturen Hinweise: • Die A-Aufgaben bezeichnen Aufgaben, die in den Tutorien in Anwesenheit gerechnet oder besprochen werden, die H-Aufgaben sind Hausaufgaben. • Es gibt auf jede Hausaufgabe Übungspunkte. Übungspunkte geben Bonuspunkte für die Klausur, aber nur, wenn die Klausur ohnehin bestanden wurde. • Abgabefrist (für die H-Aufgaben) ist der 30. April 2021

A1-1 Mengen Berechnen Sie folgende Mengen: a) {h, a, l} ∪ { l, o} LÖSUNGSVORSCHLAG: {h, a, l, o}

b) {1, 2, 4} ∪ {2, 3, 4, 5} LÖSUNGSVORSCHLAG: {1, 2, 3, 4, 5}

c) {1, 2, 3} ∩ {3, 4, 5} LÖSUNGSVORSCHLAG: {3}

d) P({1, 2, 3}) LÖSUNGSVORSCHLAG: {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

e) {1, 2, 3} × {{4, 5}} LÖSUNGSVORSCHLAG: {(1, {4, 5}), (2, {4, 5}), (3, {4, 5})}

f) {1, 2, 4} \ {1, 2, 3, 5, 6, 7}

LÖSUNGSVORSCHLAG: {4}

g) {1, 2, 4} △ {1, 2, 3, 5} LÖSUNGSVORSCHLAG: {3, 4, 5}

A1-2 Kardinalitäten Geben Sie die Kardinalität folgender Mengen an: a) P({∅}) LÖSUNGSVORSCHLAG: 2 b) {x ∈ N0 ; x < 5} LÖSUNGSVORSCHLAG: 5 c) {x ∈ Z; x < 5} LÖSUNGSVORSCHLAG: Es gibt unendlich viele negative Zahlen, damit ist die Kardinalität unendlich d) {{1, 2, 3, 4}, {5, 7, 9}} LÖSUNGSVORSCHLAG: 2 e) {x ∈ N0 } ∩ {1, . . . , 100} LÖSUNGSVORSCHLAG: |{x ∈ N0 } ∩ {1, . . . , 100}| = |{1, . . . , 100}| = 100

f) {3, 4, 5} × {2, 7, 8, 9} LÖSUNGSVORSCHLAG: |{3, 4, 5}| = 3, |{2, 7, 8, 9}| = 4 ⇒ |{3, 4, 5} × {2, 7, 8, 9}| = 3 · 4 = 12

g) {p ∈ N0 ; p ist Primzahl} × {x ∈ N0 ; x < 5}

LÖSUNGSVORSCHLAG: Sei P = {p ∈ N0 ; p ist Primzahl} und Q = {x ∈ N0 ; x < 5}. Die Kardinalität von P ist unendlich. Die Kardinalität von Q = 5 . Damit ist |P × Q| = |P | · |Q| = |P | · 5 = ∞ Also ist diese Kardinalität unendlich.

A1-3 Disjunktheit Geben Sie aus folgenden Mengen alle Paare von Mengen an, die disjunkt sind • A = {1, 2, 3} • B = {4, 6, 8} • C = {2, 3, 5, 7} • D = {4, 8, 9}

LÖSUNGSVORSCHLAG: Zur Lösung eine Tabelle, die für jedes Paar an Mengen den Schnitt dieser Mengen angibt: A B C D

A A ∅ {2, 3} ∅

B ∅ B ∅ {4, 8}

C {2, 3} ∅ C ∅

D ∅ {4, 8} ∅ D

Die Paare, deren Einträge ∅ ist, sind disjunkt. Dies sind: (A, B), (A, D), (B, A), (B, C ), (C, B), (C, D), (D, A), (D, C) Da M disjunkt mit N ⇐⇒ N disjunkt mit M , wäre die Frage auch mit weniger Paaren beantwortet, etwa (A, B), (B, C), (C, D), (D, A). Mit Paaren sind in der Regel geordnete Paare gemeint, aber da der Fokus auf Disjunktheit lag, wäre diese Antwort hier auch in Ordnung.

A1-4 Mengenoperationen a) Zeigen oder widerlegen Sie, dass gilt: (A ∩ B) ∪ (C ∩ D) = (A ∪ C) ∩ (B ∪ D)

LÖSUNGSVORSCHLAG: Die Richtung “⊇ ist falsch. Gegenbeispiel: Seien A = D = {0} und B = C = {}. Dann ist A ∪ C = B ∪ D = 0, aber A ∩ B = C ∩ D = , die Null ist also in der Menge auf der rechten Seite enthalten, aber nicht auf der linken. Richtig wäre die Aussage: (A ∩ B) ∪ (A ∩ D) ∪ (C ∩ B) ∪ (C ∩ D) = (A ∪ C ) ∩ (B ∪ D).

b) Zeigen oder widerlegen Sie, dass gilt: A △ B = (A ∪ B) \ (A ∩ B) LÖSUNGSVORSCHLAG: Richtig. Beweis Richtung “⊆”: Sei x ∈ A △ B, also entweder x ∈ A \ B oder x ∈ B \ A. Falls x ∈ A und x ∈ / B, dann x ∈ A ∪ B, aber x ∈ / A ∩ B, also x ∈ (A ∪ B) \ (A ∩ B). Fall x ∈ B \ A analog. Richtung “⊇”: Sei x ∈ A ∪ B, aber x ∈ / A ∩ B. Falls x ∈ A, dann x ∈ / B, also x ∈ A B. Falls x ∈ B, dann x ∈ / A, also x ∈ B \ A. Insgesamt also x ∈ A△B.

H1-1 Mengen

(3 Punkte; Abgabe: H1-1.txt oder H1-1.pdf)

Berechnen Sie folgende Mengen: a) ({1, 3, 4, 5} ∩ {1, 3, 6}) ∪ {1, 2, 6} LÖSUNGSVORSCHLAG: {1, 2, 3, 6}

b) P({l, d, s}) LÖSUNGSVORSCHLAG: {∅, {l}, {d}, {s}, {l, d}, {l, s}, {d, s}, {l, d, s}}

c) {{{a, b}, {c, d, e}}} × {1, 2, 3} LÖSUNGSVORSCHLAG: {({{a, b}, {c, d, e}}, 1), ({{a, b}, {c, d, e}}, 2), ({{a, b}, {c, d, e}}, 3)}

d) {(a, b), (c, d)} ∪ ({b, c} × {d, a})

LÖSUNGSVORSCHLAG: {(a, b), (c, d)} ∪ {(b, d), (b, a), (c, d ), (c, a)} = {(a, b), (c, d), (b, d ), (b, a), (c, a)}

H1-2 Kardinalitäten

(3 Punkte; Abgabe: H1-2.txt oder H1-2.pdf)

Geben Sie die Kardinalität folgender Mengen an: a) {1, 2, 3, 4, 5} LÖSUNGSVORSCHLAG: 5 b) {{a, d, e, k }} LÖSUNGSVORSCHLAG: 1 c) {{2, 3, 4}, {1}, {8, 9}} × {−2, −1, ..., 2} LÖSUNGSVORSCHLAG: Ausgeschrieben sieht die Menge so aus: {({2, 3, 4}, −2), ({1}, −2), ({8, 9}, −2), ({2, 3, 4}, −1), ({1}, −1), ({8, 9}, −1), ({2, 3, 4}, 0), ({1}, 0), ({8, 9}, 0), ({2, 3, 4}, 1), ({1}, 1), ({8, 9}, 1), ({2, 3, 4}, 2), ({1}, 2), ({8, 9}, 2), Sie hat eine Kardinalität von 15. Schneller findet man die Lösung, wenn man |A × B| = |A| · |B| = 3 · 5 = 15 verwendet.

d) {t ∈ {−1, . . . , 35}; t mod 4 = 0} LÖSUNGSVORSCHLAG: Die Menge ist {0, 4, 8, 12, 16, 20, 24, 28, 32}. Die Kardinalität ist also 9.

e) P (P ({s, q, r, t})) LÖSUNGSVORSCHLAG: |P(P({s, q, r, t}))| = 2|P({s,q,r,t})| = 22

|{s,q,r,t}|

4

= 22 = 65536

f) {m ∈ N0 } × {n ∈ N0 ; n > 6 und n2 < 36} LÖSUNGSVORSCHLAG: 0. (Ohne weiter über die erste Menge nachzudenken, können wir sehen dass die zweite Menge leer ist.)

H1-3 Disjunktheit

(2 Punkte; Abgabe: H1-3.txt oder H1-3.pdf)

Geben Sie aus folgenden Mengen alle Paare von Mengen an, die disjunkt sind • A = {d, e, f } • B = {c, d, e} • C = {b, c, e, f, i} • D = {a, b, h} • E = {f, h, i} LÖSUNGSVORSCHLAG: Zur Lösung eine Tabelle, die für jedes Paar an Mengen den Schnitt dieser Mengen angibt: A B C D E

A A {d, e} {e} ∅ {f }

B {d, e} B {c, e} ∅ ∅

C {e} {c, e} C {b} {i}

D ∅ ∅ {b} D {h}

E {f } ∅ {i} {h} E

Die Paare, deren Einträge ∅ ist, sind disjunkt. Dies sind: (A, D), (B, D), (B, E ), (D, A), (D, B), (E, B) Da M disjunkt mit N ⇐⇒ N disjunkt mit M , wäre die Frage auch mit weniger Paaren beantwortet, etwa (A, D), (B, D), (B, E). Mit Paaren sind in der Regel geordnete Paare gemeint, aber da der Fokus auf Disjunktheit lag, wäre diese Antwort hier auch in Ordnung.

H1-4 Mengenoperationen

(2 Punkte; Abgabe: H1-4.txt oder H1-4.pdf)

Beweisen Sie folgende Aussage: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C ) LÖSUNGSVORSCHLAG: Beweis Richtung “⊆”: Sei x ∈ A ∩ (B ∪ C), dann ist x ∈ A und entweder x ∈ B oder x ∈ C . Damit ist x ∈ A ∩ B oder x ∈ A ∩ C Richtung “⊇”: Sei x ∈ (A ∩ B) ∪ (A ∩ C). Falls x ∈ A ∩ B, dann ist x ∈ A und x ∈ B also auch x ∈ B ∪ C. Fall (A ∩ C) analog....