De Morgan?!

Wissenschaft Physik
1

Hallo Kollegen

ich steh echt auf der leitung ich weiß nicht wie man die deMorganschen Gesetze aus den vier Axiomen für Boolsche Algebren herleitet
DeMorgan:
¬(a OR b) = ¬a AND ¬b

¬(a AND b) = ¬a OR ¬b

Boolsche Algebra:
1.) a AND(b OR c)=(a AND b) OR (a AND b)
a OR(b AND c)=(a OR b) AND (a OR b)

2.) a AND a = a
a OR a = a

3.) a OR 0 = a
a AND 1 = a

4.) a OR b = b OR a
a AND b = b AND a

DANKE!!!

Martin

2

Hallo,
irgendwie fehlt bei Deiner Axiomatisierung die Negation.

Gruss
Enno

3

Hallo,
irgendwie fehlt bei Deiner Axiomatisierung die Negation.

Gruss
Enno

danke für den hinweis

das zweite gesetz für boolsche Algebra ist:
a OR ¬a = 1

a AND ¬a = 0

4

Hallo,
ok, damit kann man zeigen, daß aus a AND b=0 und a OR b=1, b=¬a folgt, denn

a=a AND 1=a AND (b OR ¬b)=(a AND b) OR (a AND ¬b)=a AND ¬b
¬b=¬b AND 1=¬b OR (a OR b)=(¬b AND a) OR (¬b AND b)=¬b AND a=a AND ¬b

also a=¬b. Jetzt kann man z.B. a AND b=¬(¬a OR ¬b) durch (a AND b) AND (¬a OR ¬b)=0 und (a AND b) OR (¬a OR ¬b)=1 zeigen. Probier das mal.

Gruss
Enno

5

so weit war ich schon aber ich schaff die blöde umformung nicht um von ¬(a OR b) AND (1 OR 0) nach ¬a AND ¬b zu kommen

Ich wär dir echt dankbar wenn du mir das explizit aufschreiben könntest ich hab jetzt zwei Tage damit vertan.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

6

Hallo,
um z.B. (a AND b) AND (¬a OR ¬b)=0 z.Z.
(a AND b) AND (¬a OR ¬b)=((a AND b) AND ¬a) OR ((a AND b) AND ¬b)=
(b AND (a AND ¬a)) OR (a AND (b AND ¬b))=(b AND (b AND ¬b)) OR (a AND (a AND ¬a))=
((b AND b) AND ¬b) OR ((a AND a) AND ¬a)=(b AND ¬b) OR (a AND ¬a)=0 OR 0=0
Der Beweis für (a AND b) AND (¬a OR ¬b)=1 läuft analog/dual.

so weit war ich schon aber ich schaff die blöde umformung
nicht um von ¬(a OR b) AND (1 OR 0) nach ¬a AND ¬b zu kommen

Schau Dir meinen Ansatz noch mal an. Ich zeige unter Verwendung des Lemma a AND b=0 und a OR b=1 => b=¬a bzw. a=¬b, daß a AND b=¬(¬a OR ¬b). Mir ist Dein Schritt daher nicht klar.

Gruss
Enno

PS: Du mußt nochmal drüberschauen bzgl. locker verwendeter Kommutativität und Assoziativität von AND, OR.