Как упростить булевы уравнения - PullRequest
0 голосов
/ 12 сентября 2018

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


У меня есть логическое уравнение: [boolean equation] e.g. (!B && A) || A

есть ли лучший способ для этого?

1 Ответ

0 голосов
/ 12 сентября 2018

Булево уравнение следует простым правилам вычислений, известным как Boolean Algebra.

С помощью этих правил вы можете упростить любое булево уравнение с тяжелой работой:

 Associativity of ∨ :         x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z 
 Associativity of ∧ :         x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z
 Commutativity of ∨ :                 x ∨ y = y ∨ x 
 Commutativity of ∧ :                 x ∧ y = y ∧ x 
 Distributivity of ∧ over ∨ : x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z )
 Identity for ∨ :                     x ∨ 0 = x
 Identity for ∧ :                     x ∧ 1 = x 
 Annihilator for ∧ :                  x ∧ 0 = 0 

 The following laws hold in Boolean Algebra, but not in ordinary algebra:

 Annihilator for ∨ :                  x ∨ 1  = 1
 Idempotence of ∨ :                    x ∨ x = x 
 Idempotence of ∧ :                    x ∧ x = x  
 Absorption 1:                 x ∧ ( x ∨ y ) = x  
 Absorption 2:                 x ∨ ( x ∧ y ) = x 
 Distributivity of ∨ over ∧ : x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z )

 Complementation 1 :                  x ∧ ¬x = 0
 Complementation 2 :                  x ∨ ¬x = 1
 Double negation :                     ¬(¬x) = x
 De Morgan 1 :                       ¬x ∧ ¬y = ¬(x ∨ y)
 De Morgan 2 :                       ¬x ∨ ¬y = ¬(x ∧ y)

Обратите внимание, что

  • представляет OR (||)
  • представляет AND (&&)
  • ¬ представляет NOT (!)
  • = представляет EQUALS (==)

Но с большей сложностью вашего уравнения это делаетсяРука почти невозможна.Первый шаг к завершению - таблица истинности 1034 *.Это должно выглядеть примерно так: Truth table

Вы можете создавать таблицы истинности также в Интернете, например, с помощью этого инструмента .

ИзВ таблице истинности вы можете создать KV-Map .Они могут выглядеть следующим образом:

KV-Map

Есть также онлайн-инструменты для создания KV-карт (я рекомендую этот )).

Как заполнять эти карты в соответствии с вашей таблицей истинности, здесь не тема.

Как получить булевы уравнения из KV-Map - это тоже не тема, но рекомендуемый инструментрассчитать это для вас: calculation

В заключение к проблеме: если вы хотите оптимизировать свои логические уравнения, создайте таблицу истинности с вашим уравнением: Truth table

Заполните KV-карту:

KV-Map

и замените уравнение вычисленным кратчайшим возможным путем: Calculation


Дополнение: уравнение, рассчитанное по KV-карте, является кратчайшим возможным путем.Есть еще некоторые преобразования, которые вы можете сделать с булевой алгеброй, но это не сделает эти уравнения более простыми.

...