Refactoring Boolesche Gleichung

Question

Angenommen, Sie haben einen Booleschen Regel / Ausdruck wie so

(A OR B) AND (D OR E) AND F

Sie wollen es konvertieren in so viele und nur Ausdrücke wie möglich, wie so

A AND D AND F
A AND E AND F
B AND D AND F
B AND E AND F

Sie reduzieren nur die OR ist so wird es

(A AND D AND F) OR (A AND E AND F) OR (...)

Gibt es eine Eigenschaft in Boolesche Algebra, die dies tun würde?

Answer 1

Ihr Beispiel nutzt die die Verteilbarkeit von AND über OR, wie gezeigt hier .

Alles, was Sie tun müssen, ist, dass nacheinander anwenden. Zum Beispiel mit x*(y+z) = (x*y)+(x*z) (wobei * UND und + bezeichnet OR):

0. (A + B) * (D + E) * F
1. Apply to the first 2 brackets results in ((A+B)*D)+((A+B)*E)
2. Apply to content of each bracket results in (A*D+B*D)+(A*E+B*E)
3. So now you have ((A*D+B*D)+(A*E+B*E))*F
4. Applying the law again results in (A*D+B*D)*F+(A*E+B*E)*F
5. Apply one more time results in A*D*F+B*D*F+A*E*F+B*E*F, QED

Answer 2

Hier finden Sie aktuelle DeMorgans des Satz. Der Link verweist auf ein Dokument zu elektronischen Toren beziehen, aber die Theorie bleibt gleich.

Es besagt, dass jede logische Binärausdruck bleibt unverändert, wenn wir

1. Ändern Sie alle Variablen auf ihre Ergänzungen.
2. Ändern Sie alle UND-Operationen zu OPs.
3. Ändern Sie alle ODER-Verknüpfungen zu ANDs.
4. Nehmen Sie die Ergänzung des gesamten Ausdrucks.

(Zitat aus dem oben verlinkten Dokument)

Answer 3

Sie können beim Lesen über Karnaugh Karten . Sie sind ein Werkzeug für die Booleschen Ausdrücken vereinfacht, aber man konnte sie als auch alle einzelnen Ausdrücke zu bestimmen. Ich bin mir nicht sicher, wie Sie diese in einen Algorithmus verallgemeinern könnten Sie ein Programm für obwohl schreiben konnte.

Answer 4

Vielleicht haben Sie Interesse an konjunktive Normalform oder sein Bruder, disjunktive Normalform .

Answer 5

Soweit ich Boolesche Algebra weiß nicht nur mit AND und OR-Operationen bauen werden können. Wenn Sie nur diese zwei Betrieb haben, sind Sie nicht in der Lage NOT-Operation zu erhalten.

Sie können einen beliebigen Ausdruck in den vollständigen Satz konvertieren von Boolesche Operationen.

Hier sind einige vollständige Sätze:

• AND und NOT
• OR und NOT

Answer 6

Angenommen, Sie die NOT-Operation verwenden können, können Sie einen beliebigen Booleschen Ausdruck mit nur ANDs oder nur OPs umschreiben. In Ihrem Fall:

(A OR B) AND (D OR E) AND F

Ich neige dazu, technische Abkürzung für die oben zu verwenden und schreiben:

• und als ein Produkt (oder gar nichts.);
• oder als Summe (+); und
• NICHT als Apostroph ( ').

So:

(A+B)(D+E)F

Die logische Folge Arithmetik ist eigentlich ganz nützlich für die Factoring-Bedingungen.

Mit dem De Morgan Gesetz :

(A+B) => (A'B')'

So können Sie Ihren Ausdruck umschreiben kann:

(A+B)(D+E)F
(A'B')'(D'E')'F