Übung 2 - (Dr. Kord Eickmeyer) mit allen Lösungen PDF

Preview

Summary

Aussagenlogikund Prädikatenlogik (FGdI II)2. ÜbungsblattFachbereich Mathematik SoSe 2020Dr. Kord Eickmeyer 13./15. Mai 2020Dr. Ulrik Buchholtz, Jonathan WeinbergerGruppenübungAufgabe G2 (Resolutionsverfahren) (a) Beweisen Sie die Folgerungsbeziehung{ p , p → q ,( p → q )→( q → r )}|= r , indem Sie d...

Description

Aussagenlogik und Prädikatenlogik (FGdI II) 2. Übungsblatt Fachbereich Mathematik Dr. Kord Eickmeyer Dr. Ulrik Buchholtz, Jonathan Weinberger

SoSe 2020 13./15. Mai 2020

Gruppenübung Aufgabe G2.1 (Resolutionsverfahren) (a) Beweisen Sie die Folgerungsbeziehung {p, p → q, (p → q) → (q → r)} |= r , indem Sie die leere Klausel  aus der Klauselmenge

{{ p}, {¬ p, q}, {p, ¬q, r}, {¬q, r}, {¬ r }}. mittels Resolution ableiten. (b) Für jede aussagenlogische Formel ϕ sei Kϕ eine Klauselmenge mit ϕ ≡

ϕ ist unerfüllbar

V

Kϕ . Laut Vorlesung gilt die Äquivalenz

 ∈ Res∗ (Kϕ ).

⇔

Charakterisieren Sie die folgenden Aussagen durch ähnliche Äquivalenzen: i. ϕ ist erfüllbar, ii. ϕ ist allgemeingültig, iii. ϕ |= ψ, iv. Φ0 ist unerfüllbar, wobei Φ0 eine endliche Menge von aussagenlogischen Formeln ist. Lösung: (a) Eine mögliche Lösung: {p} {¬ p, q }

{q}

{¬q, r }

{r}

{¬ r }

 (b)

i. Indem man beide Seiten der Äquivalenz negiert erhält man

ϕ ist erfüllbar

∈ / Res∗ (Kϕ ).

⇔

ii. Die Formel ϕ ist genau dann allgemeingültig, wenn ¬ϕ unerfüllbar ist. Daher gilt

ϕ ist allgemeingültig

⇔

 ∈ Res∗ (K¬ϕ ).

iii. Es gilt ϕ |= ψ genau dann, wenn ϕ → ψ allgemeingültig ist. Somit hat man

ϕ |= ψ

⇔

 ∈ Res∗ (K¬(ϕ→ψ) ).

Alternativ kann man argumentieren, dass ϕ |= ψ genau dann gilt, wenn ¬(ϕ → ψ) ≡ ϕ ∧ ¬ψ ≡ unerfüllbar ist. Somit gilt auch

ϕ |= ψ

⇔

V

(Kϕ ∪ K¬ψ )

 ∈ Res∗ (Kϕ ∪ K¬ψ ).

1

iv. Die endliche Formelmenge Φ0 ist unerfüllbar genau dann, wenn die Konjunktion gilt

Φ0 ist unerfüllbar Wegen

V

Φ0 ≡

V

ϕ∈Φ0

V

Kϕ ≡

⇔

V

Φ0 unerfüllbar ist. Somit

 ∈ Res∗ (KV Φ0 ).

VS ( ϕ∈Φ0 Kϕ ) gilt auch Φ0 ist unerfüllbar

⇔

 ∈ Res∗ (

[

Kϕ ).

ϕ∈Φ0

Aufgabe G2.2 (Kompaktheit) Der Kompaktheitssatz (der Aussagenlogik) besagt: Ist jede endliche Teilmenge einer Formelmenge Φ erfüllbar, so ist auch Φ als Ganzes erfüllbar. (a) Zeigen Sie, dass Kompaktheit äquivalent ist zu der folgenden Aussage: Gilt Φ  ψ, so gibt es eine endliche Teilmenge Φ0 ⊆ Φ mit Φ0  ψ. (b) Zeigen Sie, dass die Existenz eines vollständigen und korrekten Beweiskalküls den Kompaktheitssatz impliziert. Lösung: (a) Wie man die Aussage in (a) aus dem Kompaktheitssatz herleitet, wurde bereits in der Vorlesung gezeigt: Man nehme Φ  ψ an. Dann ist Φ ∪ {¬ψ} unerfüllbar. Nach dem Kompaktheitssatz ist eine endliche Teilmenge Ψ0 ⊆ Φ ∪ {¬ψ} unerfüllbar. Man setze Φ0 := Ψ0 \{¬ψ} ⊆ Φ. Wegen Ψ0 ⊆ Φ0 ∪{¬ψ} ist auch Φ0 ∪{¬ψ} unerfüllbar. Also gilt Φ0  ψ. Umgekehrt zeigen wir, wie man den Kompaktheitssatz aus der Aussage in (a) herleitet: Man nehme an, dass Φ nicht erfüllbar ist. Dann gilt Φ  0. Nach Annahme gibt es eine endliche Teilmenge Φ0 ⊆ Φ mit Φ0  0. Also kann Φ0 nicht erfüllbar sein. (b) Um den Kompaktheitssatz zu zeigen, können wir die Aussage in (a) nachweisen: Angenommen es gilt Φ  ψ. Dann ist dies in unserem vollständigen Beweiskalkül beweisbar, also Φ ⊢ ψ. Beweise sind endliche Bäume und können daher nur endlich viele Annahmen aus Φ enthalten. Daher gilt Φ0 ⊢ ψ für eine endliche Menge Φ0 ⊆ Φ. Mit der Korrektheit des Beweiskalküls folgt Φ0  ψ, wie gewünscht. Aufgabe G2.3 (Kompaktheit und Bit-Sequenzen) Eine Interpretation I : V = {p1 , p2 , . . . } → B kann als unendliche Bit-Sequenz I(p1 )I(p2 )I(p3 ) . . . aufgefasst werden. Sei P eine Menge solcher Sequenzen und sei P das Komplement von P . Wir nehmen an, dass sowohl P als auch P durch (unendliche) Mengen aussagenlogischer Formeln spezifiziert werden können, dass für geeignete Φ, Ψ ⊆ AL(V ) also

P

=

{I | I |= Φ},

P

=

{I | I |= Ψ}

gilt. Zeigen Sie, dass P und P dann sogar schon durch endliche Formelmengen Φ0 ⊆ Φ und Ψ0 ⊆ Ψ spezifiziert werden können. Folgern Sie, dass man nur endlich viele Bits aus I betrachten muss, um zu entscheiden, ob I ∈ P gilt. Lösung: Die Vereinigung Φ∪Ψ kann keine Modelle haben, da solche Modelle sowohl zu P als auch zu P gehören würden. Der Kompaktheitssatz sagt nun, dass schon eine endliche Teilmenge Γ ⊆ Φ ∪ Ψ keine Modelle hat. Da jede Formel in Γ zu Φ oder zu Ψ gehört, können wir Γ = Φ0 ∪ Ψ0 mit Φ0 ⊆ Φ und Ψ0 ⊆ Ψ schreiben. Um

P = {I | I |= Φ0 } zu zeigen nehmen wir zunächst I  Φ0 an. Da Φ0 ∪ Ψ0 unerfüllbar ist, gilt I 2 Ψ0 und erst recht I 2 Ψ . Somit hat man I∈ / P und daher I ∈ P . Gilt umgekehrt I ∈ P , so hat man I  Φ und erst recht I  Φ0 . Genauso zeigt man

P = {I | I |= Ψ0 }. Um nun I ∈ P zu entscheiden, müssen wir nur die Werte I(pi ) für die endlich vielen Aussagenvariablen in Φ0 betrachten.

2

Hausübung onig und Kompaktheitssatz) (12 Punkte) Aufgabe H2.1 (Lemma von K˝ Das Lemma von K˝onig besagt: Jeder unendliche, endlich verzweigte Baum hat einen unendlichen Pfad (vgl. AL-Skript, onig mithilfe des Kompaktheitssatzes bewiesen. Tatsächlich sind beide Lemma 4.4). Im AL-Skript wird das Lemma von K˝ Sätze äquivalent. Hier soll nun die umgekehrte Implikation bewiesen werden. (a) Sei T = (V, E, λ) ein Baum. Die Tiefe (engl. depth) dep(v ) eines Knotens v 6= λ ist die Länge des (eindeutigen) Pfades λ → . . . → v . Die Höhe von λ ist dep(λ) = 0. Die n-te Stufe (engl. level) eines Baums T ist gegeben durch lv T (n) := {v ∈ V | dep(v ) = n} für n ≥ 0. Zeigen Sie: Ein unendlicher Baum T ist genau dann endlich verzweigt, wenn l n := |lv T (n)| für alle n ≥ 0 endlich ist. onig um den Kompaktheitssatz zu zeigen. (Hinweis: Sei Φ eine endlich erfüllbare (b) Benutzen Sie das Lemma von K˝ Formelmenge, d.h. jede endliche Teilmenge Φ0 ⊆ Φ sei erfüllbar. Definieren Sie einen Baum TΦ , dessen Knoten aus geeigneten (partiellen) Belegungen bestehen. Benutzen Sie (a), um zu zeigen, dass TΦ die Voraussetzungen des onig erfüllt.) Lemmas von K˝ Lösung: (a)

„ =⇒ “: Wir nehmen an, T sei endlich verzweigt. Generell S gilt lv T (0) = {λ} und für n ≥ 0, dass lv T (n+ 1) = {w ∈ V | Es existiert v ∈ lv T (n) mit (v , w) ∈ E .} = v ∈lv T (n) E[v ]. Hierbei ist E[v ] = {w ∈ V | (v , w) ∈ E} die Menge der direkten Nachfolger von v . [1 Pkt.] Wir zeigen per Induktion nach n, dass für alle n ≥ 0 die Mengen lv T (n) endlich sind. Der Induktionsanfang ist wegen lv T (0) = {λ} erfüllt. [0.5 Pkt.] Zum S Induktionsschritt nehmen wir an, dass l n := lv T (n) endlich ist. Dann ist l n+1 := |lv T (n + 1)| = | v ∈lv T (n) E[v ]| ≤ |lv T (n)| · max v ∈lvT (n) |E[v ]|. Nach Induktionsvoraussetzung ist l n = |lv T (n)| endlich. Da T nach Annahme endlich verzweigt ist, gilt auch |E[v ]| < ∞ für alle v ∈ V . Damit ist auch m := maxv ∈lv T (n) |E[v ]| endlich, und somit l n+1 ≤ l n · m < ∞. [1.5 Pkt.] „ ⇐= “: Wir nehmen an, es gelte l n = |lv T (n)| < ∞ für alle n ≥ 0. (Für n = 0 gilt nach Definition l0 = 1.) Wir wollen zeigen, dass dann alle ev := |E[v ]| für v ∈ V ebenfalls endlich sind. Sei v ∈ V gegeben. Da T ein Baum ist, gibt es eine eindeutig bestimmte natürliche Zahl n ∈ N mit v ∈ lv T (n). [2 Pkt.] Dann gilt E[v ] ⊆ lv T (n + 1). [1 Pkt.] (Für n = 0 ist v = λ und E[v ] = E[λ] = lv T (1).) Wir erhalten ev = |E[v ]| ≤ |lv T (n + 1)| = l n+1 < ∞. [1 Pkt.]

(b) Sei V = {pi | 1 ≤ i ∈ N} eine abzählbare Variablenmenge. Wir schreiben AL = AL(V ) und für n ∈ N seien Vn = {p1 , . . . , pn } und ALn = AL(Vn ). Wir betrachten eine endlich erfüllbare Formelmenge Φ ⊆ AL. Es ist Φn := Φ ∩ ALn die Menge der Formeln aus Φ, die höchstens die Variablen p1 , . . . , pn enthalten. Wir definieren den Baum T := TΦ = (V, E, λ) wie folgt:

lv T (0) := {;},

λ := ;

lv T (n + 1) := {I : Vn+1 → {0, 1} | I |= ϕ für alle ϕ ∈ Φn+1 } [1 Pkt.] Dies definiert die Knotenmenge V mit Wurzel λ = ;. Die Kanten definieren wir induktiv, indem wir für einen gegebenen Knoten I ∈ lv T (n) die Menge seiner Nachfolger definieren als

E[I] := {I′ ∈ lv T (n + 1) | I′ |Vn = I}. [1 Pkt.] In der Tat ist der so definierte Graph T = (V, E, λ) ein Baum, da jeder Knoten I 6= ; einen eindeutigen Vorgänger hat. Für n ∈ N ist |lv T (n)| ≤ 2n , daher ist wegen (a) der Baum T endlich verzweigt. Wir zeigen, dass T unendlich ist, d.h., dass lv T (n) 6= ; für alle n ∈ N. Nach Definition gilt |lv T (0)| = 1. Sei also n ≥ 1. Wir betrachten die Menge Φn = Φ ∩ ALn der Formeln aus Φ, die höchstens die Variablen p1 , . . . , pn enthalten. Ist Φn endlich, dann ist lv T (n) 6= ;, da Φ endlich erfüllbar ist. Wir nehmen daher an, Φn sei unendlich, etwa Φn = {ϕk | k ∈ N}. Für beliebiges k ≥ 1 betrachten wir die endliche Teilmenge Φn,k := {ϕ1 , . . . , ϕk } ⊆ Φn . Dann existiert wegen der endlichen Erfüllbarkeit von Φ für jedes k ≥ 1 eine Belegung Ik : Vn → {0, 1} mit Ik |= Φn,k . Es gibt aber nur endlich viele1 Abbildungen Vn → {0, 1}. Daher existiert eine Belegung I : Vn → {0, 1}, sodass für unendlich viele k ≥ 1 gilt I = Ik .2 Wir erhalten insbesondere I ∈ lv T (n). [2 Pkt.] Somit ist T ein unendlicher, endlich verzweigter Baum. Nach dem Lemma von K˝ onig hat T einen unendlichen Pfad {In |S n ∈ N}, wobei In ∈ lv T (n). Wir erhalten dann eine Belegung I : V → {0, 1} von Φ, indem wir für ϕ ∈ Vk ⊆ n∈N Vn = V setzen I(ϕ) := Ik (ϕ ). [2 Pkt.] 1 2

genau 2n Dieses Schlussprinzip ist eine Instanz des sog. Schubfachprinzips (engl. pigeonhole principle).

3

Aufgabe H2.2 (Hornklauseln) (12 Punkte) Wir betrachten die Menge H = {{¬p, ¬t, s}, {p}, {¬p, ¬q , r}, {t}, {¬p, ¬s, q }, {¬s, ¬r, t}, {¬p, ¬u, r}, {¬u}, {¬q}} von Hornklauseln. (a) Bestimmen Sie die minimale erfüllende Interpretation der nicht-negativen Klauseln aus H . Entscheiden Sie, ob H erfüllbar ist. (b) Geben Sie einen Ableitungsbaum im Resolutionskalkül an, welcher  aus der Klauselmenge H herleitet. (c) Bei der Einheitsresolution darf die Resolvente zweier Klauseln nur gebildet werden, wenn eine der Klauseln aus einem einzelnen Literal besteht. Zeigen Sie: Die Einheitsresolution ist im Allgemeinen nicht vollständig, für Hornklauseln aber schon. Lösung: (a) Beginnend mit der leeren Menge bestimmt man schrittweise die Variablen, welche in jedem Modell der nichtnegativen Klauseln aus H erfüllt sein müssen. Das ergibt

X0 = ;, X1 = {p, t}, X2 = {p, t, s}, X3 = {p, t, s, q}, X4 = {p, t, s, q, r}, X5 = X4 = X∞ . Die negative Klausel {¬q} ist unter der minimalen Interpretation falsch. Dies bedeutet, dass die Klauselmenge H unerfüllbar ist. Alternativ kann man die Unerfüllbarkeit mit dem sog. Markierungsalgorithmus3 nachweisen: Dieser resultiert in der Berechnung

[Start mit H] {{¬ p, ¬t, s}, {p}, {¬ p, ¬q, r}, {t }, {¬ p, ¬s, q}, {¬s, ¬r, t}, {¬p , ¬u, r}, {¬u}, {¬q }} [I(p) = 1]  {{¬ t, s}, {¬q, r}, {t }, {¬s, q}, {¬s, ¬r, t}, {¬u, r}, {¬u}, {¬q }} [I(t) = 1]  {{s}, {¬q, r}, {¬s, q}, {¬s, ¬r}, {¬u, r}, {¬u}, {¬q }} [I(s) = 1]  {{¬q, r}, {q }, {¬ r}, {¬u, r}, {¬u}, {¬q }} [I(q) = 1]  {}. Da in der letzten Formelmenge die leere Klausel  enthalten ist, kann man wiederum folgern, dass H unerfüllbar ist. In einigen Fällen kann man auch die minimale erfüllende Interpretation der positiven Klauseln ablesen. Im Allgemeinen ist es aber möglich, dass dieser Markierungsalgorithmus die leere Klausel  findet, bevor die minimale Interpretation der positiven Klauseln vollständig bestimmt ist (so auch im vorliegenden Fall). [4 Pkt.] (b) Eine mögliche Lösung ist:

{¬p, ¬t, s}

{ p}

{¬t, s}

{t }

{s}

{¬ p, ¬s, q }

{¬p, q}

{p }

{q}

{¬q } 

[4 Pkt.] 3

Vgl. etwa U. Schöning. Logik für Informatiker, 5. Auflage, Heidelberg u.a.: Spektrum, 2000, S. 32

4

(c) Die Klauselmenge {{ p, q}, {¬ p, q}, {p, ¬q}, {¬ p, ¬q}} ist unerfüllbar. Es ist aber keine Einheitsresolution möglich, da keine Klausel aus einem einzelnen Literal besteht. Dies zeigt, dass die Einheitsresolution im Allgemeinen nicht vollständig ist. [1 Pkt.] Um zu zeigen, dass die Einheitsresolution für Hornklauseln vollständig ist, argumentieren wir per Induktion über die Anzahl der Formeln in einer unerfüllbaren Menge H von Hornklauseln: Wenn die leere Klausel  bereits in H enthalten ist, dann sind wir sofort fertig. Anderenfalls muss H eine positive Klausel {p} enthalten (sonst wäre H durch pi 7→ 0 erfüllbar). Nun bilden wir die Klauselmenge

H ′ = {C\{¬p} | C ∈ H , C 6= {p}}. Dann ist H ′ immer noch eine Menge von Hornklauseln und immer noch unerfüllbar (eine erfüllende Interpretation von H ′ ließe sich durch I(p) := 1 in eine erfüllende Interpretation von H umwandeln). Wegen der Bedingung C 6= {p} enhält H ′ eine Klausel weniger als H . Nach Induktionsvoraussetzung ist  also per Einheitsresolution aus H ′ herleitbar. Die Blätter des entsprechenden Herleitungsbaums sind mit Klauseln C\{¬p} ∈ H ′ beschriftet. Um einen Herleitungsbaum mit Blättern aus H zu erhalten, leitet man C\{¬p} per Einheitsresolution aus C ∈ H und {p} ∈ H her. [3 Pkt.] Aufgabe H2.3 (Endliche boolesche Algebren) (12 Punkte) In dieser Aufgabe sehen wir, dass sich jede endliche boolesche Algebra als Potenzmengenalgebra realisieren lässt. Sei im folgenden B = (B, ·, +,′ , 0, 1) eine endliche boolesche Algebra, d.h. B eine endliche Menge. Auf B betrachten wir die partielle Ordnung ≤ mit x ≤ y : ⇐⇒ x · y = x (vgl. H1.3). Sei AB die Menge der Atome in B . (a) Zeigen Sie, dass für alle x ∈ B gilt x · 0 = 0. Folgern Sie damit, dass x ≤ y genau dann gilt, wenn x · y ′ = 0. (3 Punkte) (b) Zeigen Sie: Für jedes Element x ∈ B mit x 6= 0 gibt es ein Atom b ∈ B mit b ≤ x .

(1 Punkt)

(c) Sei x ∈ B . Zeigen Sie, dass x die kleinste obere Schranke (Supremum) der Menge A x := {a ∈ AB | a ≤ x} ist, d.h. es ist a ≤ x für alle a ∈ A x und für alle y ∈ B mit a ≤ y für alle a ∈ A x gilt x ≤ y . (Hinweis: Benutzen Sie (a) und (b).) (2 Punkte) (d) Zeigen Sie, dass die Abbildung

ϕ : B → P (AB ),

x 7→ A x

ein Isomorphismus ist. (Hinweis: Zur Surjektivität betrachten Sie für U ⊆ AB das Element x := Σu∈U u.) (6 Punkte) Lösung: (a) Es gilt (BA5)

(BA1)

x ≤x

(BA5)

x · 0 = x · (x · x ′ ) = (x · x) · x ′ = x · x ′ = 0.

(*)

[1 Pkt.]

Sei x ≤ y (Ann. 1). Dann folgt

x · y′

(Ann. 1)

=

(BA1)

(*)

(x · y) · y ′ = x · ( y · y ′ ) = x · 0 = 0.

[1 Pkt.]

Umgekehrt nehmen wir nun x · y ′ = 0 (Ann. 2) an. Dies führt zu (BA4)

x · y = x · y +0

(Ann. 2)

=

(BA3)

(BA5)

(BA4)

x · y + x · y ′ = x · ( y + y ′ ) = x · 1 = x.

[1 Pkt.]

Bemerkung: In diesem Aufgabenteil wird die Endlichkeit von B noch nicht benutzt, d.h. die Aussagen gelten für beliebige boolesche Algebren. (b) Sei x ∈ B \{0}. Da B endlich ist, ist die Menge x ↓:= { y ∈ B | y ≤ x} endlich. Sei x 1 ≤ . . . ≤ x n ≤ x eine absteigende Kette (d.h. total geordnete Menge) maximaler Länge in x ↓ mit x i 6= 0 für i = 1, . . . , n. Dann ist x 1 ein Atom. [1 Pkt.] (c) Nach Konstruktion ist x eine obere Schranke von A x . Sei y eine weitere obere Schranke von A x . Wir wollen zeigen, dass x ≤ y . Dazu nehmen wir an, es wäre x 6≤ y . Wegen (a) wäre x · y ′ 6= 0. Wegen (b) gäbe es ein Atom b ∈ AB mit b ≤ x · y ′ . Dann gälte b ≤ x und b ≤ y ′ . Wegen b ≤ x wäre dann auch b ≤ y . Dies lieferte b ≤ y · y ′ = 0 im Widerspruch zur Annahme, dass b ein Atom ist. [2 Pkt.]

5

(d)

• ϕ ist ein Homomorphismus: Wir zeigen zunächst, dass für x, y ∈ B gilt, dass ϕ(x · y) = ϕ (x) ∩ ϕ ( y) und ϕ (x + y) = ϕ (x) ∪ ϕ ( y). Sei zunächst a ∈ ϕ(x · y) = A x · y . Dann gilt a ≤ x · y , also insbesondere a · (x · y) = a (1). Dies impliziert (BA1,2)

(1)

(BA1),(1)

a · x = (a · (x · y)) · x = (a · (x · x)) · y = (a · x) · y = a. Analog zeigt man a · y = a. Also ist a ≤ x und a ≤ y , d.h. a ∈ A x ∩ A y = ϕ(x) ∩ ϕ( y). Sei umgekehrt a ∈ ϕ(x) ∩ ϕ( y) = A x ∩ A y . Dann ist a ≤ x (2) und (BA1)

(2)

(3)

a ≤ y (3). Wir erhalten a · (x · y) = (a · x) · y = a · y = a, also a ∈ A x · y = ϕ(x · y). Insgesamt haben wir ϕ (x · y) = ϕ (x) · ϕ( y) gezeigt. [1 Pkt.] Nun betrachten wir a ∈ ϕ(x + y), d.h. a ist ein Atom mit a ≤ x + y (4). Ist x = 0, dann gilt a ≤ y , also a ∈ A y ⊆ A x ∪ A y = ϕ(x) ∪ ϕ( y). Analog argumentiert man für y = 0. Wir nehmen nun an, dass x 6= 0 und y 6= 0. Angenommen, a 6≤ x und a 6≤ y . Wegen der Idempotenz der Multiplikation erhielten wir x · a ≤ a. Da a ein Atom ist, erhielten wir x · a = 0 oder x · a = a. Wegen a 6≤ x (4) (BA3) (5),(6) folgte x · a = 0 (5). Analog wäre y · a = 0 (6). Dann ergäbe sich a = a · (x + y) = (a · x) + (a · y) = 0. Dies ist ein Widerspruch zur Annahme, dass a ein Atom ist. Also gilt a ∈ A x oder a ∈ A y , d.h. a ∈ A x ∪ A y = ϕ(x) ∪ ϕ( y). Zur umgekehrten Inklusion sei a ∈ ϕ(x) ∪ ϕ( y), also a ≤ x oder a ≤ y . Sei o.B.d.A. a ≤ x . Wir schreiben x

(BA4)

(BA5)

(BA3)

= x + 0 = x + ( y · y ′ ) = (x + y) · (x + y ′ ). Daraus folgt   (BA1,2), Idemp. (BA3) (BA4,5) x · ( x + y) = ( x + y ) · (x + y ′ ) · ( x + y) = (x + y) · (x + y ′ ) = x + ( y · y ′ ) = x.

Also gilt x ≤ x + y . Wegen a ≤ x und der Transitivität der Ordnung folgt a ≤ x + y , also a ∈ A x + y = ϕ(x + y). Insgesamt gilt also ϕ (x · y) = ϕ (x) ∩ ϕ ( y). [1.5 Pkt.] (a)

Es verbleibt noch ϕ(0) = ; und ϕ(1) = AB zu zeigen. Es gilt a ≤ 0 für a ∈ B genau dann, wenn 0 = a · 0 = a. Da Atome nach Definition ungleich 0 sind, ist ϕ(0) = A0 = ;. Offenbar gilt x ≤ 1 für alle x ∈ B wegen (BA4). Daraus folgt ϕ(1) = AB . [0.5 Pkt.] • ϕ ist bijektiv: Die Abbildung ϕ ist bijektiv: Zur Injektivität betrachten wir x, y ∈ B mit A x = A y . Wegen (c) sind x und y dann beides kleinste obere Schranken von A x und A y , d.h. x = y . [1 Pkt.] Zur Surjektivität sei U ⊆ AB . GiltP U = ;, dann ist x = 0 (eindeutig bestimmtes) Urbild von U , d.h.S ϕ(0) = ;. Sei 4 U S 6= ;. Sei wie im Hinweis x := u∈U u. Da ϕ ein Homomomorphismus ist, haben wir ϕ(x) = u∈U ϕ(u) = u∈U Au . Wir wollen zeigen, dass U = ϕ(x). [1 Pkt.] S Sei v ∈ U . Da v nach Voraussetzung ein Atom ist, gilt v ∈ Av ⊆ u∈U Au = ϕ(x). S Umgekehrt betrachten wir nun v ∈ ϕ (x) = u∈U ϕ (u). Dann existiert u ∈ U mit v ≤ u. Da u und v Atome sind, gilt v = u ∈ U . [1 Pkt.]

4

Die Summe existiert, da B ⊆ U endlich ist.

6...