Boolsche Algebra de Morgan

[Peter M. (Gast)]

Hallo,
wie kommt man da drauf: A∨B ≡ ¬(¬A)∨¬(¬B) ≡ ¬(¬A ∧ ¬B)

Also besonders vom 2. zum 3. Schritt. Vom 1. um 3. komme ich einfach da 
muss man ja einfach aus oder und machen, dann beide Variablen negieren 
und das Ganze negieren. Aber wie leitet sich das ganze über den 2. 
Schitt her?

[Timmo H. (masterfx)]

Ist doch logisch. Laut De Morgan:
¬A ∨¬B = ¬(A ∧ B).
Da dein A und B aber doppelt negiert ist sind sie eben auch in der 
Klammer noch negiert.

[Karl H. (kbuchegg)]

Was ergibt die Verneinung einer Verneinung?

A∨B ≡ ¬( ¬( A∨B ) )

De Morgan anwenden um die innere Klammer aufzulösen

¬( ¬( A∨B ) ) ≡ ¬( ¬A ∧ ¬B )

und nochmal De Morgan um die noch verbliebene Klammer aufzulösen

¬( ¬A ∧ ¬B )  ≡  ¬¬A ∨ ¬¬B

[Thomas P. (tpircher)]

Halb offtopic: Claude Shannons Doktorarbeit, in der er als erster 
boolsche Algebra und de Morgans Theorem auf die Digitaltechnik anwendet, 
ist beim MIT einsehbar:

http://hdl.handle.net/1721.1/11173

[Peter M. (Gast)]

Danke jetzt habe ich das verstanden. Ich habe nicht gesehen, dass man 
die Negation für beide Variablen anwenden kann. Also das gilt:

¬¬A∨¬¬B≡ ¬( ¬( A∨B ) )

[Peter M. (Gast)]

wobei ich sehe gerade das geht ja auch nicht so direkt. Weil 
¬A∨¬B≠¬(A∨B). Der Herleitungsweg ist einfach anders. Über die Negation 
beider Variablen. Ich wollte ja aber eigentlich wissen wie man das über 
die Negation der Einzelnen Variablen hin bekommt.

[Karl H. (kbuchegg)]

Peter M. schrieb:
> wobei ich sehe gerade das geht ja auch nicht so direkt. Weil
> ¬A∨¬B≠¬(A∨B).

Das wird ja auch nirgends benutzt. Du musst genauer schauen.
Jedesmal wenn ein NICHT in die Klammer hineingezogen wird, dreht sich 
innerhalb der Klammer das UND zu einem ODER um (bzw. umgekehrt). Genau 
das ist der De Morgan.

[Karl H. (kbuchegg)]

Peter M. schrieb:
> wobei ich sehe gerade das geht ja auch nicht so direkt. Weil
> ¬A∨¬B≠¬(A∨B). Der Herleitungsweg ist einfach anders. Über die Negation
> beider Variablen. Ich wollte ja aber eigentlich wissen wie man das über
> die Negation der Einzelnen Variablen hin bekommt.

Die Negation einer Negation ändert das Ergebnis nicht

  A ==  nicht nicht A

[Peter M. (Gast)]

Das ist mir schon alles klar. Nur ich wollte ja wissen, wie man es 
darüber herleitet:¬(¬A)∨¬(¬B) du hast ja beide Variablen doppelt negiert 
und nicht beide jeweils einzeln.