refactorización ecuación booleana

Question

Digamos que usted tiene una regla / expresión booleana como tal

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

Se desea convertir en tantos y sólo expresiones como sea posible, al igual que

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

Se le acaba la reducción de la O de lo que se convierte

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

¿Hay una propiedad en el álgebra de Boole que hacer esto?

Answer 1

Su ejemplo es la explotación de la propiedad distributiva de la y otra vez o, como se muestra aquí .

Todo lo que necesita hacer es aplicar esa sucesivamente. Por ejemplo, usando x*(y+z) = (x*y)+(x*z) (donde * denota Y y + denota 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

Tome un vistazo a teorema de De Morgan de. Las enlace apunta a un documento relativo a puertas electrónicas, pero la teoría sigue siendo el mismo.

Se dice que cualquier expresión lógica binaria se mantiene sin cambios si

1. Cambiar todas las variables a sus complementos.
2. Cambio y operaciones para RUP.
3. cambiar total o operaciones de AND.
4. Tome el complemento de toda la expresión.

(citando el documento vinculado arriba)

Answer 3

Usted puede estar interesado en leer acerca de Karnaugh mapas . Son una herramienta para simplificar expresiones booleanas, pero se puede utilizar para determinar todas las expresiones individuales. No estoy seguro de cómo se puede generalizar esto en un algoritmo que podría escribir un programa para el embargo.

Answer 4

Usted podría estar interesado en conjuntivo forma normal o su hermano, disyuntivo forma normal.

Answer 5

Por lo que yo sé álgebra de Boole no se puede construir sólo con la AND y OR operaciones. Si sólo tiene esta operación a dos que no son capaces de NO operación de recepción.

Puede convertir cualquier expresión a la conjunto completo de las operaciones booleanas.

Aquí hay algunos conjuntos completos:

• AND y NOT
• O y NO

Answer 6

Suponiendo que usted puede utilizar la operación NO, puede volver a escribir cualquier expresión booleana AND con sólo o sólo RUP. En su caso:

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

que tienden a utilizar la abreviatura de ingeniería para el anterior y escribir:

• Y como un producto (o nada.);
• O como una suma (+); y
• NO como una comilla simple ( ').

Así que:

(A+B)(D+E)F

El corolario de la aritmética es bastante útil para factorizar términos.

Ley de De Morgan :

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

Así se puede reescribir su expresión como:

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