Hallo!
Leider komme ich bei folgender Aufgabe nicht weiter, weil ich nicht genau weiß wie ich das beweisen soll.
Man sieht ja genau dass hier das Assoziativgesetz gilt, aber wie beweisen ?
Die Aufgabe lautet wie folgt:
Beweisen Sie durch Ausrechnen mit den Grundregeln der Booleschen Algebra, dass für die Äquivalenz das Assoziativgesetz gilt:
(e1 e2) e3 = e1 (e2 e3)
Ich hoffe hier kann mir jemand Hilfe geben.
Vielen Dank!
Hossa 
Die Aufgabe lautet wie folgt:
Beweisen Sie durch Ausrechnen mit den Grundregeln der
Booleschen Algebra, dass für die Äquivalenz das
Assoziativgesetz gilt:
Für die Äquivalenz () gilt folgende Wahrheitstabelle:
a | b | ab | a\*b + not a\*not b
=================================
0 | 0 | 1 | 0\*0 + 1\*1 = 1
0 | 1 | 0 | 0\*1 + 1\*0 = 0
1 | 0 | 0 | 1\*0 + 0\*1 = 0
1 | 1 | 1 | 1\*1 + 0\*0 = 1
Für die Äquivalenz gibt es also offenbar einen Ersatzausdruck, bestehend aus den „normalen“ Bool’schen Operatoren:
a\Leftrightarrow b= a\cdot b+\overline a\cdot\overline b
Ich habe hier die übliche Schreibweise mit Multiplikation („und“) und Addition („oder“) verwendet.
(e1 e2) e3 = e1 (e2 e3)
Das ist jetzt DEIN Part:
Viele Grüße
Hasenfuß
Hallo!
Im Moment habe ich noch Probleme mit dem ausrechnen.
Nach einsetzen auf der linken Seite steht dort bei mir folgendes:
( e1 \land e2 \lor \overline{e1} \land \overline{e2} ) \land e3 \lor (\overline{e1 \land e2 \lor \overline{e1} \land \overline{e2}} ) \land \overline{e3}
Wie kann ich das nun weiter ausrechnen/vereinfachen ?
Hossa
Im Moment habe ich noch Probleme mit dem ausrechnen.
Nach einsetzen auf der linken Seite steht dort bei mir
folgendes:( e1 \land e2 \lor \overline{e1} \land
\overline{e2} ) \land e3 \lor (\overline{e1 \land e2 \lor
\overline{e1} \land \overline{e2}} ) \land
\overline{e3}Wie kann ich das nun weiter ausrechnen/vereinfachen ?
Ich würde die Regeln von de Morgan anwenden:
\overline{a\cdot b}=\overline a + \overline b\quad;\quad\overline{a+b}=\overline a\cdot\overline b
oder mit logischen Operatoren geschrieben:
\overline{a\land b}=\overline a \lor \overline b\quad;\quad\overline{a\lor b}=\overline a\land\overline b
Viele Grüße
Hasenfuß
Danke!
Du hast mir schon wieder gut weitergeholfen =)
Nach Anwendung von De Morgan und ausklammern, sieht das jetzt auf der linken Seite so aus:
e3 \land e1 \land e3 \land e2 \lor e3 \land \overline{e1} \land e3 \land \overline{e2} \
\lor \overline{e3} \land \overline{e1} \lor \overline{e3} \land \overline{e2} \land \overline{e3} \land e1 \lor \overline{e3} \land e2 \
Und auf der rechten Seite:
e1 \land e2 \land e1 \land e3 \lor e1 \land \overline{e2} \land e1 \land \overline{e3} \lor \overline{e1} \land \overline{e2} \lor \overline{e1} \land \overline{e3} \land \overline{e1} \land e2 \lor \overline{e1} \land e3
Wenn ich nun meiner Meinung alle überflüssige Variablen wegnehme, sieht das auf der linken Seite so aus:
e1 \land e2 \land e3 \lor \overline{e1} \land \overline{e2} \land e3
\lor \overline{e1} \land \overline{e3} \lor e1 \land \overline{e2} \land \overline{e3} \lor e2 \land \overline{e3} \
Und die rechte Seite:
e1 \land e2 \land e3 \lor e1 \land \overline{e2} \land \overline{e3}
\lor \overline{e1} \land \overline{e3} \lor \overline{e1} \land e2 \land \overline{e3} \lor \overline{e1} \land e3 \
Ich denke dass ich nun auf der linken Seite und rechten Seite jeweils einmal ausklammern kann, aber damit komme ich auch nicht weiter.
Für den Fall dass ich mich nicht verrechnet habe, wie muss ich jetzt weiter vorgehen ?
Hallo,
da blickt ja kein Mensch mehr durch…
Wenn Du auf Deine beiden Ausdrücke
(a \Leftrightarrow b) \Leftrightarrow c
und
a \Leftrightarrow (b \Leftrightarrow c)
die Äquivalenzdefinition anwendest, kommst Du auf
(…) \cdot c
beziehungsweise
a \cdot (…)
Was in die beiden Klammern „(…)“ gehört ist klar. Da es bereits in DNF vorliegt gibt es damit nix zu tun und deshalb habe ich diese Klammern auch nicht ausgeschrieben. Auf die anderen beiden Klammern trifft das Gegenteil zu. Sie haben dieselbe Struktur, nämlich
\overline{x \cdot y + \overline{x} \cdot \overline{y}}
Der Schlüssel, um das in DNF zu bringen, sind natürlich die de-Morgan-Verneinungsgesetze. Ergebnis nach ein paar Zeilen Umformerei:
… = x \cdot \overline{y} + \overline{x} \cdot y
(Exklusiv-Oder, ne?) Wenn Du nun die beiden ausgeschriebenen Klammern in den obigen Termen entsprechend ersetzt und danach scharf anschaust, kannst Du bereits erkennen, dass die beiden Terme identisch sind. Als DNF kommt beidemal
a \cdot b \cdot c
heraus (bis auf die Reihenfolge der Summanden/Faktoren – klar).
Gruß
Martin
PS: Es ist besser, das alles mit a, b, c, · und + zu veranstalten, statt mit e1, e2, e3, /\ und /. Warum?
Hallo und guten Tag,
ich hoffe damit geholfen zu haben?
Beweisen Sie durch Ausrechnen mit den Grundregeln der Booleschen Algebra, dass für die Äquivalenz das Assoziativgesetz gilt:
(e1 e2) e3 = e1 (e2 e3)
Beweis:
(A B) C = A (B C)
x € [(A B) C] -------l gem. Def. .menge
x € (A B) oder x € C — l gem. Def. .menge
x € A oder x € B oder x € C ----l gem. Zusammenfassung nach Belieben
x € A oder x € (B oder C) = x € [A (B C)]
Somit: x € [(A B) C] … x € [A (B C)]
Somit: [(A B) C] … [A (B C)] q.e.d.
L.G.
Kofler Albert