Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Boolesche Algebra

Boolesche Algebra

Universität / Fachhochschule

Tags: Axiom, huntington

Freakyskip aktiv_icon

13:12 Uhr, 07.10.2014

Hallo Zusammen,

ich habe ein Problem im Zusammenhang mit der Booleschen Algebra, die Rechenregeln herzuleiten bzw. Allgemein ein Beweis aufzusetzen.

Als Beispiel folgende Rechnenregel:

x + x \cdot y = x

Wie kann ich das

u . a

mit Huntingschen Axiome nachweisen bzw. wie setzt man ein Beweis formal richtig auf?

Yokozuna aktiv_icon

17:13 Uhr, 07.10.2014

Hallo,

man muss die linke Seite mit Hilfe der Huntington'schen Axiome so umformen, dass man das gleiche erhält, wie auf der rechten Seite:

x + x \cdot y = |

(neutrales Element)

x \cdot 1 + x \cdot y = |

(Distributivgesetz)

x \cdot (1 + y) = |

(hier ist noch zu zeigen, dass

1 + y = 1

ist)

x \cdot 1 = |

(neutrales Element)

x

Nun noch der Beweis, dass

1 + y = 1

ist:

1 + y = |

(Kommutativgesetz)

y + 1 = |

(neutrales Element)

(y + 1) \cdot 1 = |

(Komplement)

(y + 1) \cdot (y + y') = |

(Distributivgesetz)

y + 1 \cdot y' = |

(Kommutativgesetz)

y + y' \cdot 1 = |

(neutrales Element)

y + y' = |

(Komplement)
1

Damit haben wir durch Umformungen mittels der Huntington'schen Axiome gezeigt, dass die linke Seite gleich der rechten Seite ist.

Viele Grüße
Yokozuna

Freakyskip aktiv_icon

23:34 Uhr, 07.10.2014

Leider verstehe ich die Antwort nicht.

Ich gehe davon aus: x+x⋅y=x

Wie kann ich jetzt Stück für Stück rangehen, mittels Huntington um das herzuleiten und abschließend zu beweisen.

Weil die Schritte konnte ich nicht nachvollziehen, weshalb das neutrale Element da Einfluss hat, weil

x + x \cdot y

und nicht

x \cdot 1

Danke nochmals!

Yokozuna aktiv_icon

01:07 Uhr, 08.10.2014

Es gibt leider kein Patentrezept in der Art: "Zuerst wendet man das Kommutativgesetz an, dann das Komplementärgesetz, dann ...". Welche der Huntington'schen Axiome man in welcher Reihenfolge anwenden muss, hängt von der zu beweisenden Rechenregel ab. Außerdem gibt es möglicherweise nicht nur einen Weg, den Term umzuformen.
Am besten ist es, wenn man sich ein paar Beweise anschaut und idealerweise auch versteht, dann bekommt man ein paar Ideen an die Hand, wie man so einen Beweis angehen kann. Außerdem ist so ein Beweis meistens mit etwas Herumprobieren verbunden. Auch ich musste bei diesem Beispiel erst ein wenig probieren. Je mehr Erfahrung man hat, umso weniger muss man in der Regel probieren und umgekehrt (wenig Erfahrung = viel probieren).

Ich schreibe nochmal die Huntington'schen Axiome auf, die wir zur Verfügung haben. Seien

a, b

und

c

Elemente der Boolschen Algebra und sei 1 das neutrale Element bzgl.

\cdot

und 0 das neutrale Element bzgl.

+,

dann gilt:

K 1 : a \cdot b = b \cdot a

und

K 2 : a + b = b + a

(Kommutativgesetz)

D 1 : a \cdot (b + c) = (a \cdot b) + (a \cdot c)

und

D 2 : a + b \cdot c = (a + b) \cdot (a + c)

(Distributivgesetz)

N 1 : a \cdot 1 = a

und

N 2 : a + 0 = a

(Neutralitätsgesetz)

C 1 : a \cdot a' = 0

und

C 2 : a + a' = 1

(Komplementärgesetz)

Wir wollen beweisen

x + x \cdot y = x

. Welches der Axiome könnte uns am ehesten weiter helfen. Dazu sehen wir uns die linke Seite an, die wir ja umformen wollen. Offensichtlich wird uns das Kommutativgesetz oder das Komplementärgesetz hier nicht weiterhelfen. Aber

x + x \cdot y

sieht doch so aus wie linke Seite in Axiom

D 2

. Also wenden wir mal Axiom

D 2

an:

x + x \cdot y = (x + x) \cdot (x + y)

Hmmm! Jetzt haben wir da rechts zwei Ausdrücke, auf die offenbar keines der Axiome mehr passt. Wie wäre es denn mit Axiom

D 1 : a \cdot (b + c) = (a \cdot b) + (a \cdot c)

Auf der linken Seite von Axiom

D 1

passt

x + x \cdot y

nicht, da die Operatoren gerade anders herum sind, aber vielleicht kann man ja

x + x \cdot y

so umformen, dass man die rechte Seite von Axiom

D 1

erhält. Das geht in der Tat mit Hilfe von Axiom

N 1

. Nach

N 1

gilt

x \cdot 1 = x

. Also kann ich damit das einzelne

x

im Term

x + x \cdot y

durch

x \cdot 1

ersetzen:

x + x \cdot y = (x \cdot 1) + (x \cdot y)

Nun können wir Axiom

D 1

anwenden:

x + x \cdot y = (x \cdot 1) + (x \cdot y) = x \cdot (1 + y)

Nun sieht es erst mal wieder wie eine Sackgasse aus, denn wir können hier keines der obigen Axiome direkt anwenden. Aber ich habe ein bischen im Wikipedia-Artikel über Boolsche Algebra gespickt und gesehen, dass offensichtlich

1 + y = 1

gilt. Damit wären wir praktisch fertig, denn es gilt dann zusammen mit Axiom

N 1

x + x \cdot y = (x \cdot 1) + (x \cdot y) = x \cdot (1 + y) = x \cdot 1 = x

Leider ist die Rechenregel

1 + y = 1

nicht unter den Huntington'schen Axiomen. Also müssen wir die Rechenregel

1 + y = 1

erst noch mit Hilfe der Huntington'schen Axiome beweisen. Den Beweis hierfür mache ich jetzt erst mal nicht mehr (er steht ja schon in meinem ersten Beitrag).

Versuche mal, das was ich bisher erklärt habe nachzuvollziehen. Vielleicht kommst Du jetzt ein bischen weiter.

Viele Grüße
Yokozuna

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1189405

1189208

	Status: nicht eingeloggt	Noch nicht registriert?