Refactoring boolean 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 sind nur Reduzieren der ORs so wird es

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

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

Answer 1

Ihr Beispiel ist die die Verteilbarkeit von und über die Nutzung oder, wie here gezeigt.

Alles, was Sie tun müssen, ist, dass Sie 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

Werfen Sie einen Blick auf DeMorgan's Theorem. Der Link weist auf ein Dokument hin, das sich auf elektronische Tore bezieht, aber die Theorie bleibt gleich.

Es besagt, dass jede logische binäre Ausdruck, wenn wir

1. ändern alle Variablen auf ihre Ergänzungen unverändert bleibt.
2. Ändern Sie alle UND-Operationen in ORs.
3. Ändern Sie alle OR-Operationen zu ANDs.
4. Nehmen Sie das Komplement des gesamten Ausdrucks.

(zitiert aus dem Dokument oben verlinkten)

Answer 3

Soweit ich Boolesche Algebra weiß nicht nur mit AND und OR-Operationen bauen werden können. Wenn Sie nur diese zwei Operationen haben, können Sie keine NOT-Operation empfangen.

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

Hier sind einige vollständige Sätze:

• UND und NICHT
• ODER und NICHT

Answer 4

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

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

neige ich dazu, technische Abkürzung für das oben und Schreiben zu verwenden: (. Oder nichts)

• und als ein Produkt;
• ODER als Summe (+); und
• NICHT als ein einziges Zitat ('). So

:

(A+B)(D+E)F 

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

von De Morgan's Law:

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

So können Sie Ihren Ausdruck umschreiben als:

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

Answer 5

Sie können beim Lesen über Karnaugh maps interessiert. Sie sind ein Werkzeug, um boolesche Ausdrücke zu vereinfachen, aber Sie könnten sie auch verwenden, um alle einzelnen Ausdrücke zu bestimmen. Ich bin nicht sicher, wie Sie das in einen Algorithmus verallgemeinern könnten, für den Sie ein Programm schreiben könnten.

Answer 6

Das könnte Sie auch interessieren Conjunctive Normal form oder sein Bruder, Disjunctive normal form.