| Autor |
Beitrag |
    
Diebels
| | Veröffentlicht am Dienstag, den 14. November, 2000 - 15:20: | 
|
Hallo!
Wie beweist man die Regeln von de Morgan. Dabei soll nur die Defintion der Boolschen Algebra verwendet werden.(=keine konkrete Algebra). Es soll benutzt werden, daß das Komplemment a' von a eindeutig bestimmt ist.(d.h. (a vereinigt c = 1)geschnitten (a geschnitten c = 0) => c = a')
Bei jedem Schritt sollen die Regeln angebenen werden, worauf man sich abstützt.
Bitte helft mir,
Diebels |
Markus
| | Veröffentlicht am Donnerstag, den 16. November, 2000 - 08:59: |
|
Ein möglicher Beweis geht mit den Wahrheitstafeln
Erst die Inhalte der Klammern ausrechnen, dann
negieren und mit den Werten der rechten Seite
vergleichen
WM_ichhoffedashilft Markus |
H.R.Moser,megamath.
| | Veröffentlicht am Freitag, den 17. November, 2000 - 20:55: |
|
Hi Diebels,
Deine Aufgabe benötigt offenbar eine lange
Inkubationszeit !
Es ist jetzt angebracht, Dir einen
möglichen Beweis der
d e M o r g a n - Gesetze vorzuführen
A] Bezeichnung
Der Satz ist in der Boolschen Algebra angesiedelt
Wegen der bequemen Schreibweise verwende ich
das Pluszeichen für die Vereinigung:
A + B bedeutet die Bildung derVereinigung
von A und B
AB bedeutet die Bildung des Durchschnitts
Unter A' verstehen wir die Komplementärmenge von A
Für die Universalmenge steht das Zeichen 1 ,
für die leere Menge des Symbol 0 .
B] Verwendete Axiome der Boolschen Algebra
(1) A+0 = A für alle A
(2) 1A = A für alle A
(3) A + B = B + A (Kommutativgesetz der Addition)
(4) AB = BA (Kommutativgesetz der Multiplikation)
(5) A + BC = (A+B)(A+C) (Distributivgesetz der Addition)
(6) A(B+C) = AB + AC (Distributivgesetz der Multiplikation
(7) Zu A existiert A', sodass A+A'= 1 und AA' = 0
Anmerkung
Die Assoziativgesetze für die Addition und die
Multiplikation figurieren nicht in dieser Liste
sie können als Sätze aus den Axiomen hergeleitet werden.
C] Formulierung der beiden Gesetze von De Morgan
[Augustus De Morgan (1806-1871,brit.Methematiker,
formulierte die Gesetze anno 1847 expressis verbis]
Sie lauten mit obigen Bezeichnungen:
(I): (A+B)' = A' B'
(II): (AB)' = A' + B'
Die beiden Gesetze sind zueinander dual.
D] Vorbereitung : Herleitung einer Hilfsformel
Es gilt:
A + AB = A.......................................................................(H)
Beweis
A + AB = 1A + AB ( nach (2) )
= A1 + AB ( nach (4) )
= A( 1+ B ) ( nach (6) )
= A 1 (nach einem elementaren Satz)
= 1 A ( nach (4) )
= A ...............................w.z.b.w.
E] Herleitung des ersten Gesetzes von De Morgan
(A+B)' =A'B'
bedeutet doch, dass A'B' das Komplemenzt von A+B ist
Um dies zu beweisen, brauchen wir nur nachzuweisen,
dass die beiden folgenden Beziehungen gelten:
(a) A + B + A' B' = 1 und
(b) (A+B) A' B' = 0
Nachweis von (a):
In die Beziehung A + A' = 1 setzen wir für A die Beziehung
A = A + A B ein ( nach dem Hilfssatz (H) ); es kommt
A + AB + A' = 1 nach (2) ersetzen wir A' durch A'1:
A + AB + A'1 = 1
Da B+B' = 1,ersetzen wir die eins auf der linken Seite
der Gleichung durch B + B' , somit:
A + AB + A' (B+B') = 1.
Jetzt verwenden wir die distributiven, kommutativen und
assoziativen Gesetze der Boolschen Algebra und erhalten
in Analogie zur elementaren Algebra der Reihe nach
A + A B + A'B + A'B' =1
A+( A+A' ) B + A'B' = 1, beachte: A + A' =1 nach (7),also:
A + 1 B + A'B' = 1, nach kommt: (2) kommt:
A + B + A'B' = 1 , damit ist (a) bewiesen
Nachweis von (b):
(A+B) A'B' = A(A'B') + B(A'B') (Distributivgesetz)
= A(A'B') + B (B'A') (Kommutativgesetz)
= (AA')B' + (BB')A' (Assoziativgesetz)
= 0 B' + 0 A' (nach (7) )
= 0 + 0 ( nach (8) )
= 0......................... w.z.b w.
Mit den Beweisen von (a) und (b) ist der erste Teil
des Satzes von De Morgan bewiesen.
Der zweite Satz ist dual dazu und lässt sich
wörtlich mit dem Dualitätsprinzip auf den soeben
geführten Beweis zurückführen.
Man braucht bloss die Summen durch Produkte zu
ersetzen und umgekehrt.
Wir verschenken diese Mühe und passen.
Mit freundlichen Grüssen
H.R.Moser,megamath |
H.R.Moser,megamath.
| | Veröffentlicht am Freitag, den 17. November, 2000 - 21:25: |
|
Hi,
Ein kleiner Nachtrag:
1. Bei der Anwendung des Dualitätsprizips sin die Zeichen
eins und null in Ihren Rollen zu vartauschen
2. Zur Belohnung dafür, dass Ihr eine Thema der
Boole'schen Algebra ins Board gestellt habt, gibt eine
kleine Aufgabe:
Man beweise mit dem Gesetz von De Morgan
den Satz:
Für C = AB gilt:
A' B + A B ' = ( A + B ) C '
Wie lautet der duale Satz ?
Mit freundlichen Grüssen
H.R.Moser,megamath. |
|
