Boolsche Algebra: a~b~c + ~a~b = ~b~c + ~a~b Wir können Rechenweg nicht erklären

Servus,

unser Azubi kam letztens mit einer Aufgabe aus der boolschen Algebra:

(~a~bc)+(a*~b*~c)+(~a*~b*~c)**

Das soll so weit wie möglich vereinfacht werden.
Damit wir sinnvoll helfen und erklären können, müssen wir natürlich Lösung und Rechenweg kennen.

Wir haben (aus Faulheit 😄) einen Online-Rechner verwendet:
http://www.elektroniker-bu.de/boolesche.htm#ergebnis
Der zu folgendem Ergebnis kommt: ~a~b+~b~c**

Nun haben wir ein Ergebnis, was wir nicht rechnerisch hergeleitet bekommen.
Dass das Ergebnis allerdings stimmt, konnten wir mit Hilfe des Karnaugh-Veitch-Diagramms beweisen

Den Rechenweg bis zu dem Zwischenergebnis ~a~b+a~b*~c** ist leicht nachzuvollziehen:

Wir können von (~a~bc)+(~a*~b*~c)** das ~a~b* ausklammern:
~a~b(c+~c)+a*~b*~c**
Das c+~c ist immer 1 und kann daher weg gelassen werden:
~a~b+a~b*~c**

Nun behauptet der Rechner, dass das a weg gelassen werden kann:
~a~b+~b~c**

Meine Frage ist jetzt: Warum?
Wir haben keine Regel gefunden, mit der sich das erklären lässt.

Hat da jemand eine Idee?

Beste Grüße

Ich hab zwar Mathe studiert, aber diese Sytax war mir komplett neu (und ziemlich gewöhnungsbedürftig).

(¬a && ¬b) || (a && ¬b && ¬c)

True, wenn nicht b und nicht a. (erster Term)
Außerdem:
True, wenn nicht b und a und nicht c. (zweiter Term)

Um insgesamt true zu werden, muss also auf jeden fall b false sein.
Wenn zusätzlich a false ist, ist das Gesamtergebnis true, egal, wie Term 2 ist.
Wenn a true ist, muss c false sein. Das bedeutet, im zweiten Term ist a irrelevant. Der wird eh nur ausgewertet, wenn a true ist.

LaTino

Ganz simpel

(a & !b & !c) | (!a & !b & !c)

ist gleich

(a | !a) & (!b & !c)

ist gleich

(!b & !c)

Oder bring den Ausdruck in die KNF, dann sieht man's sofort.

LaTino

Ich weiß, die Schreibweise ist grausam 😄
Wenn man es mit mathematischen Zeichen aufgeschrieben hat. ist es aber deutlich besser lesbar.
Die Negierung schreibe ich dann als Strich über dem Ausdruck, das Und als Punkt und das Oder als Plus. Man merkt recht schnell, dass diese Schreibweise ziemlich intuitiv ist, da oft normale Mathematik ist.

Und ja, logisch ist das, uns ging es um den Rechenweg an sich bzw. die Herleitung.
Unser Azubi muss ja auch den Rechenweg bieten können, logische Gedankengänge reichen da scheinbar nicht.

Aber ich hab die Lösung, es ist eine weiter gedachte Form des De Morganschen Gesetzes, das sagt:

!(A & B) = !A | !B
!(A | B) = !A & !B

Wobei Doppelnegationsgesetz auch passen würde, das sagt:

!!A = A

Ich negiere die komplette Gleichung, also sowohl Ergebnis als auch die Formel.
Dann kann ich weiter vereinfachen, muss aber daran denken, am Ende wieder Ergebnis und Formel zu negieren.

Mal so ähnlich wie C# geschrieben und unter der Annahme, dass X das Ergebnis ist:

X = (!A & !B & C) | (A & !B & !C) | (!A & !B & !C)

Die Lösung in Schritten:

 X = (!A & !B & C) | (A & !B & !C) | (!A & !B & !C)
 X = (!A & !B & C)| (!A & !B & !C) | (A & !B & !C)
 X = (!A & !B & (C | !C)) | (A & !B & !C)
 X = (!A & !B) | (A & !B & !C)
 X = !B & (!A | (A & !C))
!X = !(!B & (!A | (A & !C)))
!X = B | (A & (!A | C))
!X = B | (A & !A) | (A & C)
!X = B | (A & C)
 X = !B & (!A | !C)
 X = (!A & !B) | (!B & !C)

Und genau das ist die Lösung, die der Rechner ausgespuckt hat.

Als Regel formuliert:

A | (!A & B) = A | B

Die Herleitung:

 X = A | (!A & B)
!X = !A & (A | !B)
!X = (A & !A) | (!A & !B)
!X = !A & !B
 X = A | B

Die Grundregel die man hier anwenden kann ist das Distributivgesetz

( a & b ) | ( a & c ) = a & ( b | c )

Wenn wir dann folgendes gleichsetzen

a = !A & !B
b = C
c = !C

dann ergibt sich auch der Rechenweg (siehe dritter Schritt)

Stimmt, das tue ich schon von Schritt 1 bis 2 und das war auch nicht das Problem.
Ich klammere bloß nicht !B & !C aus, sondern !A & !B, was am Ende aber zum gleichen Ergebnis führt.

Wenn ich - wie Du - !B & !C ausklammere, ergibt das folgenden Rechenweg:

X = (!A & !B & C) | (A & !B & !C) | (!A & !B & !C)
X = (!A & !B & C) | (!B & !C & (A | !A))
X = (!A & !B & C) | (!B & !C)

Dann habe ich da im linken Term immer noch ein C drin, was ich nicht mit dem Distributivgesetz raus bekomme.
Mit der Regel:

A | (!A & B) = A | B

kann ich das aber schon raus ziehen.

Diese eine Regel stand so nicht in Wikipedia und wir haben sie zwar logisch sehen, aber nicht herleiten können.

Bisschen umständlich, all das oO

(1) (!A & !B & C) | (A & !B & C) | (!A & !B & !C) =                    //!B ausklammern
(2) !B & (!A & C | A & C | !A & !C) =                                       //innen: C aus den ersten beiden ausklammern
(3) !B & (C & (!A | A) | !A & !C) =                                          //!A | A ist überflüssig
(4) !B & (C | !A & !C) =                                                        //aus"multiplizieren", i.e. erweitern
(5) !B & ((C | !A) & (C | !C))                                                 // C | !C ist überflüssig
(6) !B & (C | !A)                                                                  //und da ist schon die KNF

Schritt 4->5 wäre auch die Herleitung der Antwort auf deine Frage im ersten Post.

LaTino
(EDIT: falsche Ausgangformel. (mittlerer Term müsste !C sein, richtig?) Ändert aber nichts an den Schritten.)

Dir ist da ein kleiner Fehler unterlaufen:
In Schritt 1 im zweiten Term sollte das C negiert sein, das kannst Du daher auch nicht ausklammern.
Wenn ich dann das !C ausklammere, dann kommt man wieder bei (!A & !B & C) | (!B & !C) raus, mit einem C im linken Term.
So oder so gibts immer ein nicht negiertes C oder A auf einer Seite, was ich nur mit diesem einen Gesetz raus bekomme.

Und ja, es ist umständlich, ich hab mich auch erst gefragt, wozu man das braucht O.o
Jetzt, wo ich so viel herum gerechnet habe (schriftlich) finde ich aber, dass das doch deutlich einfacher ist, als wenn man es direkt im Code macht.
Vorausgesetzt man nutzt +=Oder und *=Und, wie wir es alle in der Schule mit Addition und Multiplikation gelernt haben.

Lohnt allerdings auch nur, wenn man mal so komplexe Bedingungen hat und dann kann man es meist auch einfacher machen, indem man Teile der Bedingung in Variablen auslagert.
Also eigentlich ist's nutzlos für einen Softwareentwickler, aber es schadet ja nicht ^^

In der Elektronik könnte das aber nützlich werden, denke ich ...

Mit der Regel:

A | (!A & B) = A | B  

kann ich das aber schon raus ziehen.

Diese eine Regel stand so nicht in Wikipedia und wir haben sie zwar logisch sehen, aber nicht herleiten können.

Entschuldige, aber du wendest hier das Distributionsgesetz an.

a | ( b & c ) = ( a | b ) & ( a | c )

Setzen wir für

a = A
b = !A
c = B

dann erhalten wir

A | ( !A & B ) = ( A | !A ) & ( A | B ) 
= true & ( A | B ) 
= A | B

Und das Distributionsgesetz steht in der Wikipedia 😉

O.o

Gibt's hier eigentlich auch diesen Smilie, der seinen Kopf gegen eine Steinmauer haut?

Den bräucht ich jetzt 😄

Dass mir das nicht aufgefallen ist, aber Du hast vollkommen recht 😄
Das macht auch die Rechnung bedeutend einfacher, so dass auch unser Azubi eine relle Chance hat, das zu verstehen 😄