LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 1104/26/2304/26/23 03:04 PM03:04 PM

Weitere Übungsbeispiele Weitere Übungsbeispiele zur Booleschen Algebrazur Booleschen Algebra

Franz JehleFranz JehleBoolesche Algebra, 4.3 / 4.4Boolesche Algebra, 4.3 / 4.4

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 22

Axiome für Boolesche Axiome für Boolesche VerbändeVerbände

Für alle a, u, c Für alle a, u, c єє V gilt: V gilt:I.I. a) au = u aa) au = u a b) a + u = u + a b) a + u = u + a II.II. a) (au) c = a (u c) a) (au) c = a (u c)

b) (a + u) + c = a + (u + c) b) (a + u) + c = a + (u + c)III.III. a) a (a + u) = aa) a (a + u) = a

b) a + a u = a b) a + a u = a IV.IV. a) a (u + c) = a u + a c a) a (u + c) = a u + a c

b) a + u b) a + u c = (a + u) (a + c)c = (a + u) (a + c)

V.V. a) a a) a · 1 = a· 1 = a b) a + 0 = ab) a + 0 = aVI.VI. a) a a) a = 0 = 0 b) a + b) a + = 1 = 1

Verband

distributiver Verband

komplem

entärer distributiver V

erband

Seite 3 Seite 4 Seite 5 Seite 6 Seite 7 Seite 8 Seite 9

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 33

1.1. BeispielBeispiel• Es ist zu zeigen, dass dieEs ist zu zeigen, dass dieVerschmelzungsgesetze III Verschmelzungsgesetze III aus den aus den Verknüpfungsaxiomen I, IV, V und VI Verknüpfungsaxiomen I, IV, V und VI

abgeleitet abgeleitet werden können.werden können.

Lösung (Gesetz III b)Lösung (Gesetz III b)

a + au = ?a + au = ?Verschmelzungs- / AbsorptionsgesetzeVerschmelzungs- / AbsorptionsgesetzeWir wollen zeigen, dass gilt:Wir wollen zeigen, dass gilt:a + au = aa + au = a

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 44

• Nach Axiom V a• a + au = a ∙1 + a u• Nach Axiom IV a• a + au = a (1 + u) • Nach Axiom V a• a + au = a [(1 + u) · 1]• Nach Axiom I b und VI b• a + au = a [(u + 1) (u + ū)• Nach Axiom IV b• a + au = a (u + 1 ∙ ū)• Nach Axiom I a und V a• a + au = a (u + ū)

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 55

• Nach Axiom VI b• a + au = a · 1• Nach Axiom V a• a + au = a

• q.e.d.• Beweis erfolgreich

erbracht.

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 66

2. Beispiel2. Beispiel• Wir wollen zeigen, dass es bei Wir wollen zeigen, dass es bei

der Definition der Booleschen der Definition der Booleschen Verbände genügt hätte, statt Verbände genügt hätte, statt der Existenz von der Existenz von genau genau einemeinem komplementären komplementären Element Element ā zu a ā zu a єє V die V die Existenz von Existenz von mindestens mindestens einemeinem komplementären komplementären Element Element ā zu fordern.ā zu fordern.

• Lösung Lösung Wir nehmen an, es gäbe zu a Wir nehmen an, es gäbe zu a

zwei komplementäre zwei komplementäre Elemente Elemente

und und . .

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 77

Nach den Axiomen VI muss dann gelten:

(1) a · = 0 (2) a + = 1 (3) a · = 0 (4) a + = 1

Es gilt:Es gilt:

Nach Axiom V a:Nach Axiom V a:

= · 1

Nach Voraussetzung (4): = · (a + )

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 88

Nach Axiom IV a:Nach Axiom IV a: = = · a + · a + · ·

Nach Axiom I a und Voraussetzung (1):Nach Axiom I a und Voraussetzung (1): = 0 + = 0 + · ·

Nach Axiom I b:Nach Axiom I b: = = · · + 0 + 0

Nach Voraussetzung (3):Nach Voraussetzung (3): = = · · + a · + a ·

Nach Axiom I a und IV a:Nach Axiom I a und IV a: = = ( ( + a) + a)

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 99

Nach Axiom I b:Nach Axiom I b: = = ∙ (a + ∙ (a + ))

Voraussetzung (2):Voraussetzung (2): = = ∙ 1 ∙ 1

Nach Axiom V a:Nach Axiom V a: = =

Es ist also stets:Es ist also stets: = =

04/26/2304/26/23 03:04 PM03:04 PM LdL am 17.06. 2004 - S. Roth LdL am 17.06. 2004 - S. Roth 1010

Damit istDamit ist gezeigt, dass es bei der Definition der gezeigt, dass es bei der Definition der Booleschen Verbände ausgereicht hätte, die Booleschen Verbände ausgereicht hätte, die

Existenz Existenz von genau einem von genau einem komplementären Element komplementären Element ā zu fordern.ā zu fordern.

q.e.d.q.e.d.

Beweis erfolgreich erbracht.Beweis erfolgreich erbracht.