Mathematische Grundlagen für die Informatik || Lösungen zu den Aufgaben

Losungen zu den Aufgaben 201

Losungen zu den Aufgaben

Aufgabe 1.1

Zu a): (1) ∅ /∈ ∅, da die leere Menge kein Element enthalt. (2) ∅ ∈{∅} istoffensichtlich. (3) M ∈{{ 1, 2} , M} offensichtlich. (4) 1 /∈{{ 1, 2} , M} offen-sichtlich. (5) 3 ∈ A = {3, 4, {5, 6}} offensichtlich. (6) {4} /∈ A, denn A enthaltzwar das Element 4, aber nicht die Menge {4} als Element. (7) {5, 6} ∈ A of-fensichtlich. (8) {B} /∈ A, denn A enthalt nicht die Menge {B} = {{5, 6}}als Element. (9) ist die gleiche Aussage wie (7). (10) 6 /∈ A offensichtlich. (11)6 ∈ B offensichtlich. (12) {5, 6} /∈ B, denn B enthalt nicht die Menge {5, 6}als Element, sondern die beiden Elemente 5 und 6.

Zu (b): (1) falsch, da die leere Menge kein Element enthalt. (2) offensichtlichwahr. (3) wahr, denn die rechte Menge enthalt die Menge {a, b} als Element. (4)falsch, den die rechte Menge enthalt die Menge {a, b, c} nicht als Element. (5)und (6) sind offensichtlich wahr.

Aufgabe 1.2

(1) M1 = {0, 1, 8, 27, 64}. (2) M2 = {15, 18, 21, 27, 30, 33, 39, 42, 45}.(3) M3 = {{a} , {b} , {c} , {a, b} , {a, c} , {b, c} , {a, b, c}}.(4) M4 = {0, 1, . . . , 10}. (5) M5 = {1, 2, 3, 4, 6, 8, 12, 24}.(6) M6 = ∅. (7) M7 = {1, 2, 3}.

Aufgabe 1.3

(1) M1 ={x | x = 2k, 0 ≤ k ≤ 6

}.

(2) M2 = {x | x = k2, 2 ≤ k ≤ 11 und k ist prim}.(3) M3 = {x | x = k3, 1 ≤ k ≤ 4}.(4) M4 = {x | x = 2k + 1, k ist naturliche Zahl großer gleich 0}.

Aufgabe 1.6

Zu (2): Es sei p die Ausssage ”Der Hahn kraht auf dem Mist.“, und q sei dieAussage ”Das Wetter andert sich.“. Dann wird die umgangssprachliche Aussagedurch die aussagenlogische Formel p → (q ∨ ¬q) reprasentiert. Da q → ¬q eineTautologie ist, also immer den Wert 1 hat, folgt, dass auch p → 1 immer wahrist. Somit ist die Aussage auch insgesamt eine Tautologie.

Aufgabe 1.7

a) Die Behauptung folgt unmittelbar aus der Tatsache, dass alle Modelle furF ∪ {β} auch Modelle von F sind. Da wegen der Voraussetzung F |= α alleModelle von F auch Modelle von α sind, sind damit die Modelle von F ∪ {β}auch Modelle von α, und das ist zu zeigen.

b) Falls β /∈ F ist, dann ist nichts zu zeigen. Sei also β ∈ F . Da β allge-meingultig ist, sind alle Modelle von F auch Modelle von F − {β} (die Formel

K.-U. Witt, Mathematische Grundlagen für die Informatik, DOI 10.1007/978-3-658-03079-7_5, © Springer Fachmedien Wiesbaden 2013

202 Losungen zu den Aufgaben

β ist unerheblich fur die Erfullbarkeit von F), woraus unmittelbar die Behaup-tung folgt.

Aufgabe 1.9

Aus der Voraussetzung α ≡ β folgt I∗(α) = I∗(β) fur alle Belegungen I von αund β. Aus der Definition der Bijunktion folgt, dass dann auch I∗(α ↔ β) = 1fur alle Belegungen gilt, woraus folgt, dass α ↔ β eine Tautologie ist, alsoα ⇔ β gilt.

Aus der Voraussetzung α ⇔ β folgt, dass α ↔ β eine Tautologie ist, d.h.I∗(α ↔ β) = 1 fur alle Belegungen I gilt, woraus wegen der Definition derBijunktion folgt, dass I∗(α) = I∗(β) fur alle Belegungen I und damit α ≡ βist.

Aufgabe 1.11

(1) Mithilfe der Idempotenz von ∧ und der Definition von ↑ ergibt sich:

¬α ≡ ¬(α ∧ α) ≡ α ↑ α

(2) Mithilfe doppelter Negation, Definition von ↑ und a) ergibt sich:

α ∧ β ≡ ¬¬(α ∧ β) =≡ ¬(α ↑ β) ≡ (α ↑ β) ↑ (α ↑ β)

(3) Mithilfe doppelter Negation, Definition von ↓ und (1.11) ergibt sich:

α ∨ β ≡ ¬¬(α ∨ β) ≡ ¬(α ↓ β) ≡ (α ↓ β) ↓ (α ↓ β)

(4) Mithilfe doppelter Negation, de Morgan-Regel und a) ergibt sich:

α ∨ β ≡ ¬¬(α ∨ β) ≡ ¬(¬α ∧ ¬β) ≡ ¬α ↑ ¬β ≡ (α ↑ α) ↑ (β ↑ β)

Aufgabe 1.12

Wir zeigen, dass die Menge {¬,∨,∧}, also die Boolesche Basis, eine aussagen-logische Basis ist. Mithilfe der de Morgan-Regeln folgt dann zum einen

α ∧ β ≡ ¬¬(α ∧ β) ≡ ¬(¬α ∨ ¬β)

und zum anderen

α ∨ β ≡ ¬¬(α ∨ β) ≡ ¬(¬α ∧ ¬β)

und damit, dass {¬,∨} bzw. {¬,∧} ebenfalls aussagenlogische Basen sind. DesWeiteren wissen wir, dass α → β ≡ ¬α ∨ β und damit α ∨ β ≡ ¬α → β gilt.Es folgt damit unmittelbar, dass auch {¬,→} eine aussagenlogische Basis ist.Da wir in vorherigen Beispielen und Ubungsaufgaben gezeigt haben, dass die


Verknupfugnen ¬,∨,∧ sowohl durch ↓ als auch durch ↑ definierbar sind, folgt,dass sowohl {↓} als auch {↑} boolesche Basen sind.

Es bleibt zu zeigen, dass {¬,∨,∧}, d.h. die Menge der aussagenlogischen Ver-knupfungen, mit der wir die Sprache der Aussagenlogik definiert haben, eineaussagenlogische Basis ist. Wir zeigen das ”zu Fuß“, d.h. indem wir zeigen, dassjede der 16 Verknupfungen durch {¬,∨,∧} definierbar ist. Dazu betrachten wirdie Wahrheitstabellen fur alle 16 Verknupfungen:

α β ∗0 ∗1 ∗2 ∗3 ∗4 ∗5 ∗6 ∗7 ∗8 ∗9 ∗10 ∗11 ∗12 ∗13 ∗14 ∗15

1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 11 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 10 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 10 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Die Verknupfung ∗0 entspricht der Konstanten 0, diese ist aquivalent zu α ∧¬α.∗1 ist die NOR-Verknupfung ↓, und es gilt α ↓ β ≡ ¬(α∨β). ∗2 ist die Negationvon ∗13. ∗3 ist die Negation von ∗12. ∗4 ist die Negation der Subjunktion ∗11. ∗5

ist die Negation von ∗10. ∗6 ist das exklusive Oder ⊕ aquivalent zur Negationder Bijunktion ∗9. ∗7 ist die NAND-Verknupfung: α ↑ β ≡ ¬(α ∧ β). ∗8 ist dieKonjunktion. ∗9 ist die Bijunktion, und es gilt α ↔ β ≡ (¬α∨β)∧(α∨¬β). ∗10

ist die Projektion auf β, aquivalent zu β ∨ (α∨¬α). ∗11 ist die Subjunktion, undwir wissen, dass α → β ≡ ¬α ∨ β gilt. ∗12 ist die Projektion auf α, darstellbardurch α ∨ (β ∨ ¬β). ∗13 ist die Subjunktion β → α definierbar durch α ∨ ¬β.∗14 ist die Disjunktion ∨. ∗15 entspricht der Konstanten 1, welche definierbar istdurch 1 ≡ α ∨ ¬α.

Aufgabe 1.13

(3) Es gilt wegen (2) sowie mithilfe bekannter Aquivalenzen aus Tabelle ??

ifte(α, 0, 1) ≡ (α → 0) ∧ (¬α → 1) ≡ ¬α ∧ 1 ≡ ¬α

womit gezeigt ist, dass die Negation mit der Verknupfung ifte definierbar ist.

Des Weiteren gilt ebenfalls mit (2) und Tabelle ??

ifte(α, β, 1) ≡ (α → β) ∧ (¬α → 1) ≡ (α → β) ∧ 1 ≡ α → β

womit gezeigt ist, dass die Subjunktion mit der Verknupfung ifte definierbar ist.

Da {¬,→} eine aussagenlogische Basis bildet (Frege-Basis), und deren beideElemente durch die Verknupfung ifte definierbar sind, folgt die Behauptung.

Aufgabe 1.17

Es ist Mα = {{p,¬q} , {p, q,¬r} , {p,¬q, r}}.

Aufgabe 1.18

(1) Mα = {{p,¬q, r} , {q, r} , {¬p, r} , {q,¬r} , {¬r}}


(2) Wir rechnen und lassen triviale Klauseln weg:

Res(Mα) = { {p,¬q, r} , {q, r} , {¬p, r} , {q,¬r} , {¬r} ,

{p, r} , {¬q, r} , {p,¬q} , {q} , {¬p, q} , {¬p} }Res2(Mα) = { {p,¬q, r} , {q, r} , {¬p, r} , {q,¬r} , {¬r} ,

{p, r} , {¬q, r} , {p,¬q} , {q} , {¬p, q} , {¬p}{r} }

Res3(Mα) = { {p,¬q, r} , {q, r} , {¬p, r} , {q,¬r} , {¬r} ,

{p, r} , {¬q, r} , {p,¬q} , {q} , {¬p, q} , {¬p}{r} , � }

Es gilt Res4(Mα) = Res3(Mα) und damit Res∗(Mα) = Res3(Mα).

(3) Da � ∈ Res∗(Mα) ist, folgt, dass α unerfullbar ist.

(4) Folgender Resolutionsgraph deduziert die leere Klausel:

{ p,¬q, r } { q, r } {¬p, r } {¬r }

{ p, r } {¬p }

{ r }

�

Aufgabe 1.19

Zu (2):

a) P → (¬W → S)

b) P → ¬W

c) P → S

Zu (3):

a) ¬P ∨W ∨ S

b) ¬P ∨ ¬W


c) ¬P ∨ S

Zu (4): Die Formelmenge der Aussagen a) und b) ist gegeben durch:

F = {¬P ∨W ∨ S,¬P ∨ ¬W }

Prasident I vermutetF |= ¬P ∨ S

Diese Implikation trifft zu, falls die Formelmenge

F ′ = {¬P ∨W ∨ S,¬P ∨ ¬W,¬(¬P ∨ S) }

d.h.F ′ = {¬P ∨W ∨ S,¬P ∨ ¬W, P ∧ ¬S) }

unerfullbar ist. Die zugehorige Klauselmenge ist

MF ′ = { {¬P, W, S }, {¬P,¬W }, {P }, {¬S } }

Zu (5): Folgender Resolutionsgraph zeigt, dass MF ′ unerfullbar ist. Prasident Ihat also Recht mit seiner Vermutung.

{¬P, W, S }) {¬S })

{¬P, W } {¬P,¬W }

{¬P } {P }

�

Aufgabe 1.20

Zu (1): Umwandlung der Klauseln in Subjunktionen:

p ∧ q → r

s → t

p ∧ t→ 0

1 → p (5.1)p → q


Wegen der Klausel (5.1) erhalten wir mit Verfahrensschritt (1) folgende rotenMarkierungen:

p ∧ q → r

s → t

p ∧ t→ 0

1 → p

p → q (5.2)

Anwendung von Verfahrensschritt (2i) fuhrt wegen der Klausel (5.2) zur folgen-den blauen Markierung:

p ∧ q → r (5.3)s → t

p ∧ t→ 0

1 → p

p → q

Anwendung von Verfahrensschritt (2i) fuhrt wegen der Klausel (5.3) zur folgen-den grunen Markierung:

p ∧ q → r

s → t

p ∧ t→ 0

1 → p

p → q

Es ist kein Verfahrensschritt mehr anwendbar, die Formel ist erfullbar, und dieBelegung I(p) = I(q) = I(r) = 1 sowie I(s) = I(t) = 0 ist ein Modell fur α.

Zu (2): Umwandlung der Klauseln in Subjunktionen:

1 → p (5.4)p → q

q ∧ s → r

p ∧ r → 0

1 → s (5.5)

Wegen der Klauseln (5.4) und (5.5) erhalten wir mit Verfahrensschritt (1) folgen-de roten Markierungen:

1 → p

p → q (5.6)q ∧ s → r

p ∧ r → 0

1 → s


Anwendung von Verfahrensschritt (2i) fuhrt wegen der Klausel (5.6) zur folgen-den blauen Markierung:

1 → p

p → q

q ∧ s → r (5.7)p ∧ r → 0

1 → s

Anwendung von Verfahrensschritt (2i) fuhrt wegen der Klausel (5.7) zur folgen-den grunen Markierung:

1 → p

p → q

q ∧ s → r

p ∧ r → 0 (5.8)1 → s

Wegen Klausel (5.8) besagt Verfahrensschritt (2ii), dass die Formel β unerfullbarist.

Aufgabe 1.21

Direkter Beweis: Es gilt(√

a−√

b)2≥ 0. Daraus folgt a − 2

√a · b + b ≥ 0

und daraus die Behauptung.

Aufgabe 1.22

(1) Wir nehmen an, dassa + b

2<√

a · b

gilt. Dann folgt a − 2√

a · b + b < 0 und daraus(√

a−√

b)2

< 0, was einWiderspruch gegen die Tatsache ist, das Quadratzahlen nicht negativ sind.

(2) Direkter Beweis: Da x, y ∈ U+ ist, gibt es m, n ∈ N0 mit x = 2m + 1 undy = 2n + 1. Es gilt x · y = 4mn + 2m + 2n + 1 = 2(mn + m + n) + 1 ∈ U+.

Widerspruchsbeweis: Da x, y ∈ U+ ist, gibt es m, n ∈ N0 mit x = 2m + 1 undy = 2n + 1. Wir nehmen an, dass xy ∈ G+ ist. Dann muss (2m + 1)(2n + 1) ∈G+, also 2(mn + m + n) + 1 ∈ G+ sein, was einen Widerspruch dazu bedeutet,dass sich alle z ∈ G+ als z = 2k fur ein geeignetes k ∈ N darstellen lassen.

Aufgabe 1.23

(1) Nach Definition 1.21 ist zu zeigen: x ∈ A ⇒ x ∈ A, d.h. wir mussen zeigen,dass die Subjunktion x ∈ A → x ∈ A immer wahr ist.


Das Pradikat x ∈ A kann wahr oder falsch sein. Folgende Wahrheitstafel zeigtdie beiden moglichen Belegungen fur die Subjunktion:

x ∈ A x ∈ A x ∈ A → x ∈ A1 1 10 0 1

x ∈ A → x ∈ A ist also immer wahr (es handelt sich um eine Tautologie der Artα → α), d.h. es gilt x ∈ A ⇒ x ∈ A und damit die Behauptung A ⊆ A.

Aufgabe 1.24

(1) Es ist P(∅) = {∅} sowie P(P(∅)) = P({∅}) = {∅, {∅}} (beides folgt z.B.umittelbar aus Folgerung 1.14).

(2) Die einzige Menge mit dieser Eigenschaft ist die leere Menge M = ∅. In (1)sieht man, dass ∅ ⊆ P(∅) gilt (es gilt ja ∅ ⊆ A fur jede Menge A, siehe Folgerung1.13 a). Ist M = ∅, also z.B. a ∈ M , und wurde M ⊆ P(M) sein, dann warea ∈ P(M). Die Elemente von P(M) enthalten aber – außer der leeren Menge– nur Mengen, die die Elemente von M enthalten, aber nicht die Elemente alssolche.

Aufgabe 1.26

Ein Beispiel ist die Aussagenlogik. Weitere Beispiele sind die Potenzmengenal-gebren einelementiger Mengen, wie z.B. P({∅}) = {∅, {∅}}.

Aufgabe 2.2

(1) Es sei p(x, y) das Pradikat xRy, q(x, y) das Pradikat yRx und r(x, y) dasPradikat x = y. Die Definition der Antisymmetrie wird reprasentiert durch (wirlassen aus schreibtechnischen Grunden die Variablen weg):

p ∧ q → r

Die Aussage in der Aufgabe wird reprasentiert durch

p ∧ ¬r → ¬q

Wir zeigen, dass diese beiden Ausdrucke aquivalent sind:

p ∧ q → r ≡ ¬(p ∧ q) ∨ r ≡ ¬p ∨ r ∨ ¬q ≡ ¬(p ∧ ¬r) ∨ ¬q ≡ p ∧ ¬r → ¬q

(2) Die logische Darstellung der Definition der Injektivitat und die logische Dar-stellung der Aufgabe haben die gleiche Struktur wie die Aussagen in Aufgabe(1): Wenn wir p fur x1Ry1∧x2Ry2, q fur x1 = x2 und r fur y1 = y2 setzen, dannist die Definiton der Injektivitat gegeben durch

p ∧ q → r


und die Behauptung durchp ∧ ¬r → ¬q

Die Aquivalenz dieser beiden Ausdrucke haben wir bereits in (1) gezeigt.

(3) lasst sich vollkommen analog zu (2) beweisen – fuhren Sie bitte den Beweisselber!

(4), (5) Diese Behauptungen gelten offensichtlich.

Aufgabe 2.6

a), c) und d) folgen unmittelbar aus Satz 2.1.

b) Sei I eine Indexmenge und {Ai}i∈I eine Partition von A. Wir definierenR ⊆ A × A durch: xRy gilt genau dann, wenn x, y ∈ Ai fur ein i ∈ I ist,d.h. zwei Elemente x, y ∈ A gehoren zur Relation R genau dann, wenn sie zurselben Klasse Ai von A gehoren. Es ist offensichtlich, dass R reflexiv und sym-metrisch ist. Gilt xRy und yRz, dann mussen x, y, z zur selben Klasse von Agehoren, dann gilt aber auch xRz. R ist also auch transitiv. R ist also eine Aqui-valenzrelation auf A, womit die Behauptung gezeigt ist.

Aufgabe 2.7

(1) Der Beweis erfolgt analog zum Beweis in Beispiel 2.8 b), wir mussen nur 3durch m ersetzen. Die AquivalenzKlassen (Restklassen) sind

[ k ]m = {q ·m + k | q ∈ Z}

fur 0 ≤ k ≤ m− 1. Der Index von ≡m ist m.

(2) Wenn m ein Teiler von n ist, dann gibt es eine Zahl t ∈ Z mit n = t ·m. Wirmussen zeigen, dass es zu k mit 0 ≤ k ≤ n− 1 ein k′ mit 0 ≤ k′ ≤ m− 1 gibt,so dass [ k ]n ⊆ [ k′ ]m gilt. Das geeignete k′ erhalten wir, wenn wir k durch mteilen:

k = qk ·m + k′ mit 0 ≤ k′ ≤ m− 1

qk ∈ Z ist der Quotient und r ist der kleinste positive Rest, die bei Division vonk durch m entstehen. Es gilt nun

x ∈ [ k ]n genau dann, wenn x = q · n + k fur ein q ∈ Z

genau dann, wenn x = q · n + qk ·m + k′ fur q, qk ∈ Z

genau dann, wenn x = q · t ·m + qk ·m + k′ fur q, qk, t ∈ Z

genau dann, wenn x = (q · t + qk) ·m + k′ fur q, qk, t ∈ Z

genau dann, wenn x = q′ ·m + k′ fur q′ = q + qk + t ∈ Z

genau dann, wenn x ∈ [ k′ ]m

womit wir wie angestrebt [ k ]n ⊆ [ k′ ]m gezeigt haben.


Aufgabe 2.10

a) folgt unmittelbar aus der Definition 2.10.

b) folgt unmittelbar aus c).

c) folgt unmittelbar aus der Symmetrie von R.

d) folgt unmittelbar aus e).

e) Die Behauptung folgt wegen der Symmetrie von R: Es gilt

xRy gdw. yRx gedw. xR−1y

Aufgabe 3.1

Wir nehmen an, dass ϕ(01) = y = 02 ist. Da y = 02 ist, hat y einen Vorgangerz ∈ S2: s2(z) = y. Sei x ∈ S1 das Urbild von z: ϕ(x) = z. Wir erhalten mitdiesen Gleichungen und der Strukturgleichung (3.1)

ϕ(01) = y = s2(z) = s2(ϕ(x)) = ϕ(s1(x))

und damit gilt 01 = s1(x), da ϕ injektiv ist. Damit ware 01 Nachfolger von x, wasein Widerspruch zum Axiom P1 darstellt. Damit ist unsere Annahme widerlegtund die Behauptung gezeigt.

Aufgabe 3.3

Die Gultigkeit der Induktionsanfange ist bei allen Aufgaben leicht zu verifizie-ren, deshalb zeigen wir nur die Induktionsschritte.

(1) 2(n + 1) + 1 = 2n + 1 + 2 ≤ 2n−1 + 2 ≤ 2n−1 + 2n−1 = 2 · 2n−1 = 2n

(2)∑n+1

i=1 2(i− 1) =∑n

i=1 2(i− 1) + 2((n + 1)− 1) = n2 + 2n + 1 = (n + 1)2

(3)∑n+1

i=0 qi =∑n

i=0 qi + qn+1 = 1−qn+1

1−q+ qn+1 = 1−qn+1+qn+1−qn+2

1−q= 1−qn+2

1−q

(4) xn+1−yn+1

x−y= x(xn−yn)+yn(x−y)

x−y= x · xn−yn

x−y+ yn ∈ Z

(5)∑n+1

i=11

i(i+1)=∑n

i=11

i(i+1)+ 1

(n+1)(n+2)= n

n+1+ 1

(n+1)(n+2)= n+1

n+2

(6) Der Induktionsschritt reduziert sich darauf zu zeigen, dass (−1)2n+1(2n +1)2 + (−1)2n+2(2n + 2)2 = (2n + 1) + (2n + 2) ist, was durch Nachrechnenerledigt werden kann: Beide Seiten ergeben 4n + 3.

(7) Zeigen Sie zuerst, dass∑n

i=1 i3 = n2(n+1)2

4gilt. Dann folgt die Behauptung

mit der im Beispiel 3.3 a) (Seite 125) bewiesenen Gleichheit∑n

i=1 i = n(n+1)2

.

(8)∏n

i=0 Ai = An ·∏n−1

i=0 Ai = An(An − 2) = (22n+ 1)(22n

+ 1 − 2) =

(22n+ 1)(22n − 1) = 22n · 22n − 1 = 22n+2n − 1 = 22·2n − 1 = 22n+1 − 1 =

22n+1+ 1− 2 = An+1 − 2

(9) Diese Behauptung stiummt fur n ∈ N0 mit 0 ≤ n ≤ 41, aber nicht furn = 41: 412 − 41 + 41 = 412 ∈ P.


Aufgabe 3.6

(iv) Fn+2Fn− Fn+1 = (Fn+1 + Fn)Fn− (Fn + Fn−1)2 = Fn+1Fn + F 2

n − F 2n −

2FnFn−1−F 2n−1 = Fn+1Fn−FnFn−1−FnFn−1−F 2

n−1 = Fn(Fn+1−Fn−1)−Fn−1(Fn +Fn−1) = F 2

n−Fn−1Fn+1 = (−1)(Fn+1Fn−1−F 2n) = (−1) ·(−1)n =

(−1)n+1

Aufgabe 3.9

Wir nehmen an, dass P(N) abzahlbar ist, M1, M2, M3, . . . sei eine solche Ab-zahlung, und x1, x2, s3, . . . sei eine Abzahlung von N. Damit stellen wir folgende(boolesche) Matrix auf:

x1 x2 x3 . . . xj . . .M1 b11 b12 b13 . . . b1j . . .M2 b21 b22 b23 . . . b2j . . .M3 b31 b32 b33 . . . b3j . . .

......

......

......

...Mi bi1 bi2 bi3 . . . bij . . ....

......

......

......

Dabei ist

bij =

{1, xj ∈Mi

0, xi /∈Mi

Mithilfe der Diagonalen der Matrix definieren die Menge MD durch:

xk ∈MD genau dann, wenn xk /∈Mk (d.h. genau dann, wenn bkk = 0) (5.9)

MD ist eine Menge naturlicher Zahlen, also ein Element von P(N). Diese Men-ge muss also in der Abzahlung M1, M2, M3, . . . vorkommen, d.h. es muss eineNummer r geben, mit MD = Mr. Fur das Element xr gibt es zwei Falle: (1)xr ∈MD oder (2) xr /∈MD. Fur diese gilt:

(1): Aus xr ∈ MD folgt xr ∈ Mr wegen MD = Mr und daraus wegen (5.9)xr /∈MD

(2): Aus xr /∈ MD folgt xr /∈ Mr wegen MD = Mr und daraus wegen (5.9)xr ∈MD

Beide Falle fuhren also zu einem Widerspruch, womit unsere Annahme wider-legt und die Behauptung gezeigt ist.

Aufgabe 3.11

(1) Durchschnitt und Vereinigung sind kommutative und assoziative Verjnupfun-gen, also sind beide Strukturen kommutative Monoide. In der Struktur (i) istdie leere Menge das Einselement, denn es gilt A ∪ ∅ = ∅ ∪ A = A fur alleA ∈ P(M). In der Struktur (ii) ist die Menge M das Einselement, denn es giltA ∩M = M ∩ A = A fur alle A ∈ P(M). Abgesehen von dem Fall M = ∅


read(x);ω := 0;while x + ω + 1 = 0 do

ω := ω + 1endwhile;write(ω)

Abb. 18: Berechnung der nirgends definierten Funktion ω durch μ-

Rekursion

bilden beide Strukturen keine Gruppen, denn in der Struktur (i) gibt es zu keinerMenge A ∈ P(M) mit A = ∅ eine Menge B ∈ P(M) mit A ∪ B = ∅, und inder Struktur (ii) gebt es zu keiner Menge A ∈ P(M) mit A = M eine MengeB ∈ P(M) mit A ∩B = M .

(2) Es sei Π(M) = {f : M → M | f bijektiv} die Menge der bijektiven Funk-tionen von der Menge M in die Menge M ; damit betrachten wir die Rechen-struktur (Π(M), ◦). Die Struktur ist ein Monoid, denn Kompositon von Funktio-nen ist assoziativ (siehe Satz 2.4 (Seite 102. Das Einselement ist die identischeAbbildung idM (siehe Satz 2.2 a) und b) auf Seite 102). Das Inverse zur Bijekti-on f ist die Umkehrfunktion f−1. Aus Ubung 2.11 (2) und wegen Beispiel 2.16auf Seite 107 wissen wir, dass die Komposition von Funktionen im Allgemeinennicht kommutativ ist.

Aufgabe 4.3

(1) Idee: Die Eingabe x wird um1 erhoht, damit x + 1 auch fur x = 0 großer als0 ist. x + 1 wird dann permanent um 1 erhoht, womit der Wert niemals gleich0 wird, d.h. die Schleife terminiert fur keine Eingabe x (siehe Abbildung 18).Entsprechend unserem Schema ergibt sich als μ-rekursive Funktion ω:

ω = μ[C[ν; C[add ; π2

1, π22

]]](2) Falls y = 0 ist, ist div nicht definiert, fur x = y ist das Ergebnis 1, sonst wirdq beginnend bei 0 hochgezahlt, bis g(x, y, q) = x− y(q + 1) = 0 ist:

div(x, y) = equal(y, 0) · ω(x) + equal(x, y) + μ [g(x, y, d)]

(3) Der Rest ergibt sich durch

mod(x, y) = x− y · div(x, y)

(4) Wir passen Beispiel 4.2 b) (Seite 174) im Exponenten an:

n√

= μ[C[sub; π2

1, C[exp; π3

3, π32

]]]


read(x, n);y := 0;while x� exp(y, n) = 0 do

y := y + 1endwhile;write(y)

Abb. 19: Berechnung der Funktion n√

durch μ-Rekursion

Abbildung 19 zeigt eine Implementierung dieses Verfahrens.

(5), (6) Wir uberlegen uns zunachst diese Funktionen in Pseudocode:

min(x, y) = sign(x− y) · y + sign(y − x) · x + equal(x, y) · xmax (x, y) = sign(x− y) · x + sign(y − x) · y + equal(x, y) · x

sowie zur kurzeren und ubersichtlicheren Darstellung die Hilfsfunktionen

s(a, b, c) = sign(a− b) · cs = C[mult ; C

[sign; C

[minus ; π3

1, π32

], π3

3

]]eq(d, e, f) = equal(d, e) · f

eq = C[mult ; C

[equal ; π3

1, π32

], π3

3

]Damit erhalten wir

min(x, y) = s(x, y, y) + s(y, x, x) + eq(x, y, x)

min = C[add ; C

[add ; C

[s; π2

1, π22, π

22

],

C[s; π2

2, π21, π

21

]], C[eq; π2

1, π22, π

21

]]max (x, y) = s(x, y, x) + s(y, x, y) + eq(x, y, x)

max = C[add ; C

[add ; C

[s; π2

1, π22, π

21

],

C[s; π2

2, π21, π

22

]], C[eq; π2

1, π22, π

21

]](7) Rechnen Sie nach, dass

geq(x, y) = max (sign(x− y), equal(x, y))

gilt!

(8) binom(n, k) = div(fak(n),mult(fak(k), fak(n− k)))

Documents

Mathematische Grundlagen für die Informatik || Lösungen zu den Aufgaben