рефакторинг логического уравнения - PullRequest
Новая
       32

рефакторинг логического уравнения

1 голос
/ 31 мая 2009

Допустим, у вас есть логическое правило / выражение вроде 

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

Вы хотите преобразовать его в как можно больше И только выражений, например 

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

Вы просто уменьшаете ИЛИ, чтобы оно стало 

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

Есть ли свойство в булевой алгебре, которое бы это делало?

Ответы [ 6 ]

5 голосов
/ 31 мая 2009

Взгляните на теорему Деморгана . Ссылка указывает на документ, касающийся электронных ворот, но теория остается прежней.

Он говорит, что любое логическое двоичное выражение остается неизменным, если мы

  1. Заменить все переменные на их дополнения.
  2. Измените все операции И на ИЛИ.
  3. Измените все операции ИЛИ на AND.
  4. Возьмите дополнение всего выражения.

(цитата из вышеуказанного связанного документа)

3 голосов
/ 31 мая 2009

В вашем примере используется дистрибутив AND над OR, как показано здесь .

Все, что вам нужно сделать, это применить это последовательно. Например, используя x*(y+z) = (x*y)+(x*z) (где * обозначает AND, а + обозначает 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
2 голосов
/ 31 мая 2009
2 голосов
/ 31 мая 2009

Вам может быть интересно прочитать о картах Карно . Они являются инструментом для упрощения логических выражений, но вы также можете использовать их для определения всех отдельных выражений. Я не уверен, как вы можете обобщить это в алгоритм, для которого вы могли бы написать программу.

0 голосов
/ 31 мая 2009

Предполагая, что вы можете использовать операцию NOT, вы можете переписать любое логическое выражение только с AND или только OR. В вашем случае: 

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

Я склоняюсь к использованию инженерных сокращений для вышесказанного и пишу:

  • И как продукт (или ничего);
  • ИЛИ как сумма (+); и
  • НЕ как одиночная кавычка (').

Итак: 

(A+B)(D+E)F

Следствие арифметики на самом деле весьма полезно для факторинга.

По Закон де Моргана : 

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

Таким образом, вы можете переписать ваше выражение как: 

(A+B)(D+E)F
(A'B')'(D'E')'F
0 голосов
/ 31 мая 2009

Насколько я знаю, булева алгебра не может быть построена только с помощью операций И ​​и ИЛИ. Если у вас есть только эти две операции, вы не можете получить операцию НЕ.

Вы можете преобразовать любое выражение в полный набор логических операций.

Вот несколько полных наборов:

  • И, а НЕ
  • ИЛИ, а НЕ
...