UBlatt 01ML - Klausurrelevant PDF

Preview

Summary

Klausurrelevant...

Description

Fachbereich Informatik Sigrid Weil

Musterl¨osung 1

DMLA

Aufgabe 1.1 Stellen Sie folgende Aussagen als aussagenlogische Formeln dar: • Mickey lacht immer, wenn Goofy lacht. • Mickey und Donald lachen niemals gemeinsam. • Mindestens einer von den dreien lacht. • Es stimmt nicht, dass alle drei lachen. (Benutzen Sie die Variablen M, G, D f¨ur Mickey/Goofy/Donald lacht“.) ” L¨osung 1.1 • G→M • ¬(M ∧ D) • M ∨G∨D • ¬(M ∧ G ∧ D) Aufgabe 1.2 Beweisen Sie mittels Wahrheitstafel: a) p → (q → r) ≡ (p ∧ q) → r b) (p ∨ q) → r 6≡ (p → r) ∨ (q → r) L¨osung 1.2 a) Die beiden fett gedruckten Spalten sind identisch, also sind die Ausdrucke ¨ a¨quivalent. p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

(q → r) 1 1 0 1 1 1 0 1

p → (q → r) 1 1 1 1 1 1 0 1

(p ∧ q) 0 0 0 0 0 0 1 1

(p ∧ q) → r 1 1 1 1 1 1 0 1

b) In den beiden fett gedruckten Spalten gibt es Unterschiede, also sind die Ausdrucke ¨ nicht a¨ quivalent. p q r (p ∨ q) (p ∨ q) → r (p → r) (q → r) (p → r) ∨ (q → r) 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1

Aufgabe 1.3 Beweisen Sie mittels der Rechen- oder Merkregeln: a) p → q ≡ ¬q → ¬p b) (p → q) ∧ (q → ¬p) ≡ ¬p L¨osung 1.3 a) p → q ≡ ¬q → ¬p p→q

Subjunktion

≡ ¬p ∨ q

Kommutativgesetz

≡ q ∨ ¬p ≡ ¬q → ¬p

Subjunktion

b) (p → q) ∧ (q → ¬p) ≡ ¬p (p → q) ∧ (q → ¬p) ≡ (¬p ∨ q) ∧ (¬q ∨ ¬p) ≡ (¬p ∨ q) ∧ (¬p ∨ ¬q) ≡ ¬p ∨ (q ∧ ¬q) ≡ ¬p ∨ 0

Subjunktion Kommutativgesetz Distributivgesetz ullbarkeitsregel Unerf¨ Absorptionsregel

≡ ¬p

Aufgabe 1.4 Seien A = {a, b, c} und B = {a, c}, C = {∅, b, B }. Stimmt’s oder stimmt’s nicht? a) a ∈ A

e) A ⊆ C

i) {a, c} ∈ A

m) ∅ ∈ A

b) {a} ∈ A

f) C ⊆ A

j) {a, c} ∈ B

n) ∅ ∈ B

c) {a} ⊆ A

g) {a, c} ⊆ A

k) a ∈ C

o) ∅ ⊆ A

d) a ∈ B

h) {a, c} ⊆ B

l) B ∈ C

p) ∅ ⊆ B

L¨osung 1.4 a) Stimmt, da a ein Element von A ist. b) Stimmt nicht, da {a} kein Element von A ist. c) Stimmt, da a ein Element von A ist und somit {a} eine Teilmenge von A. d) Stimmt, da a ein Element von B ist. e) Stimmt nicht, da die Elemente von A nicht in C enthalten sind. f) Stimmt nicht, da die Elemente von C nicht in A enthalten sind. g) Stimmt, da die Elemente a und c in A enthalten sind und somit {a, c} eine Teilmenge von A. h) Stimmt, da die Elemente a und c in B enthalten sind und somit {a, c} eine Teilmenge von B .

i) Stimmt nicht, da {a, c} kein Element von A ist. j) Stimmt nicht, da {a, c} kein Element von B ist. k) Stimmt nicht, da a kein Element von C ist. l) Stimmt, da B ein Element von C ist. m) Stimmt nicht, da ∅ kein Element von A ist. n) Stimmt nicht, da ∅ kein Element von B ist. o) Stimmt, da ∅ Teilmenge jeder Menge ist. p) Stimmt, da ∅ Teilmenge jeder Menge ist.

Aufgabe 1.5 Seien X und Y ⊆ Z gegeben durch X = {−5, −3, −1, 1, 3, 5, 7, 9} und Y = {−1, 0, 1, 2} Bestimmen Sie

a) X ∪ Y

c) X × {a, b}

b) ℘(Y )

d)

C (Y

× X)

L¨osung 1.5 a) X ∪ Y = {−5, −3, −1, 1, 3, 5, 7, 9} ∪ {−1, 0, 1, 2} = {−5, −3, −1, 0, 1, 2, 3, 5, 7, 9}

b)

℘(Y ) = {{}, {−1}, {0}, {1}, {2}, {−1, 0}, {−1, 1}, {−1, 2}, {0, 1}, {0, 2}, {1, 2}, {−1, 0, 1}, {−1, 0, 2}, {0, 1, 2}, {−1, 1, 2}, {−1, 0, 1, 2}}

c)

X × {a, b} = {(−5, a), (−5, b), (−3, a), (−3, b), (−1, a), (−1, b), (1, a), (1, b), (3, a), (3, b), (5, a), (5, b), (7, a), (7, b), (9, a), (9, b)}

d)

C (Y

× X) = C (Y ) ∗ C (X) = 4 ∗ 8 = 32

Aufgabe 1.6 F¨ı¿ 21 r eine Menge u und eine Teilmenge p ⊆ ℘(u) hei¨ı¿ 21 t p eine Partition von u, wenn gilt: • Die Vereinigung aller Mengen in p ist gleich u. • Die Mengen in p sind paarweise disjunkt (das hei¨ı¿ 21 t, dass der Schnitt zweier Mengen aus p immer leer ist). Geben Sie alle Partitionierungen in nichtleere Teilmengen der Menge {a, b, c, d} an. (Hinweis: es gibt 15 verschiedene.)

L¨osung 1.6 P0 = {{a, b, c, d}} P1 = {{a, b, c}, {d}} P2 = {{a, b, d}, {c}} P3 = {{a, c, d}, {b}} P4 = {{b, c, d}, {a}} P5 = {{a, b}, {c, d}} P6 = {{a, c}, {b, d}} P7 = {{a, d}, {b, c}} P8 = {{a, b}, {c}, {d}} P9 = {{a, c}, {b}, {d}} P10 = {{a, d}, {b}, {c}} P11 = {{b, c}, {a}, {d}} P12 = {{b, d}, {a}, {c}} P13 = {{c, d}, {a}, {b}} P14 = {{a}, {b}, {c}, {d}} Aufgabe 1.7 Ein Pr¨adikat P auf der Menge M = {a, b, c, d} sei durch die folgende Matrix gegeben, die an der Position (x, y) den Eintrag 1 hat, genau dann wenn P (x, y) gilt, ansonsten ist der Eintrag 0. (Wie ublich ¨ bezeichne die erste Komponente die Zeile, die zweite Komponente die Spalte). a b c d

a 1 0 1 0

b 0 0 0 1

c 0 1 0 0

d 1 0 1 0

Geben Sie an, ob die Formeln α bzw. β erf¨ullt sind oder nicht: ¨ Sie Ihre Antworten z.B. durch Ubersetzung in eine verbale Formulierung oder durch Angabe Begrunden ¨ eines (Gegen-)Beispiels. a) α ≡ ∃x ∀y : ¬P (x, y) b) β ≡ ∃x ∃y ∀z : P (x, z) = P (y, z) c) Negieren Sie die Formel β aus Aufgabenteil b) d) Drucken ¨ Sie pr¨adikatenlogisch aus: Auf der Diagonalen kommt sowohl 1 als auch 0 vor.“ ” L¨osung 1.7 ullt, denn es gibt keine Zeile, die nur aus 0 besteht. a) α ist nicht erf¨ ullt, denn f¨ur x = a und y = c sind die Zeilen gleich. b) β ist erf¨ c) ¬β ≡ ∀x ∀y ∃z : P (x, z) 6= P (y, z) d) ∃x∃y : P (x, x) ∧ ¬P (y, y)...