refactoring équation booléenne

Question

Disons que vous avez une règle booléenne / expression comme si

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

Vous voulez convertir en autant et seulement expressions que possible, comme si

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

Vous êtes juste réduirez le OU de sorte qu'il devient

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

Y at-il une propriété en algèbre booléenne qui ferait cela?

Answer 1

Votre exemple exploite la distributivité de l'ET-dessus ou, comme le montre ici .

Tout ce que vous devez faire est d'appliquer que successivement. Par exemple, en utilisant x*(y+z) = (x*y)+(x*z) (où * représente AND et + représente 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

Jetez un oeil à théorème De Morgan. Le lien pointe vers un document relatif aux portes électroniques, mais la théorie reste la même.

Il dit que toute expression binaire logique reste inchangé si nous

1. Changer toutes les variables à leurs compléments.
2. Modifier toutes les opérations et Ors.
3. modifier tout ou opérations ANDs.
4. Prendre le complément de l'expression entière.

(citant le document lié ci-dessus)

Answer 3

Vous pouvez être intéressé par la lecture sur Karnaugh Cartes . Ils sont un outil pour simplifier les expressions booléennes, mais vous pouvez les utiliser pour déterminer toutes les expressions individuelles. Je ne sais pas comment vous pouvez généraliser cela dans un algorithme, vous pouvez écrire un programme bien.

Answer 4

Vous pourriez être intéressé par Forme normale conjonctives ou son frère, forme normale disjonctive .

Answer 5

Pour autant que je sais l'algèbre de Boole ne peut pas être construite uniquement avec AND et OR opérations. Si vous avez seulement cette opération deux vous n'êtes pas en mesure de ne pas recevoir l'opération.

Vous pouvez convertir une expression à la pleine ensemble des opérations booléennes.

Voici quelques ensembles complets:

• ET et NON
• OR et NOT

Answer 6

En supposant que vous pouvez utiliser l'opération NOT, vous pouvez réécrire toute expression booléenne avec seulement ou seulement ANDs ORs. Dans votre cas:

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

J'ai tendance à utiliser un raccourci d'ingénierie pour ce qui précède et écrire:

• ET en tant que produit (ou rien.);
• OU en tant que somme (+); et
• non pas comme une apostrophe ( ').

(A+B)(D+E)F

Le corollaire de l'arithmétique est en fait très utile pour les termes d'affacturage.

loi de De Morgan :

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

Vous pouvez réécrire votre expression:

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