Упрощение группы предложений И и ИЛИ

Question

Итак, если у меня есть группа предложений И и ИЛИ:

Y = ( A + B ) . ( A + C' ) . ( B + D' )

Могу ли я упростить это так:

Y = A . ( B + C' ) . ( B + D' ) ; Because A is common to ( A + B ) and ( A + C' )
Y = A . B . ( C' + D' )         ; Because B is common to ( B + C' ) and ( B + D' )

Спасибо за ваше время.

Answer 1

Нет, если вы используете следующие значения:

A = 1
B = 0
C = 0
D = 0

Тогда исходное утверждение верно, если ваша упрощенная версия ложна.Вы можете найти другой способ представить его, расширив логическое выражение, а затем попытаться алгебраически уменьшить его, например:

(A + B)(A + C')(B + D')
(AA + AC' + AB + BC')(B + D')                          // expand first 2 groups
AAB + ABC' + ABB + BBC' + AAD' + AC'D' + ABD' + BC'D'  // expand all groups
AB + ABC' + AB + BC' + AD' + AC'D' + ABD' + BC'D'      // apply identity to reduce
AB + BC' + AD'                                         // eliminate redundant expressions

Этот конечный результат будет выглядеть так в вашей записи

(A . B) + (B . C') + (A . D')

Еще один шаг может привести к

B . (A + C') + (A . D')

или

A . (B + D') + (B . C')

Answer 2

Единственная эквивалентность, которую я могу счесть полезной, это

(A + B). (A + C ') === A + (B.C')

Так становится

(A + (B.C ')). (B + D ')

if B: --> A . D'
else: --> (A+C')

Не знаю, поможет ли это вам сделать что-то более эффективное / полезное

A   B   C'  D'  f()
TRUE    TRUE    TRUE    TRUE    TRUE
TRUE    TRUE    TRUE    FALSE   TRUE
TRUE    TRUE    FALSE   TRUE    TRUE
TRUE    TRUE    FALSE   FALSE   TRUE
TRUE    FALSE   TRUE    TRUE    TRUE
TRUE    FALSE   TRUE    FALSE   TRUE
TRUE    FALSE   FALSE   TRUE    FALSE
TRUE    FALSE   FALSE   FALSE   FALSE
FALSE   TRUE    TRUE    TRUE    TRUE
FALSE   TRUE    TRUE    FALSE   FALSE
FALSE   TRUE    FALSE   TRUE    TRUE
FALSE   TRUE    FALSE   FALSE   FALSE
FALSE   FALSE   TRUE    TRUE    FALSE
FALSE   FALSE   TRUE    FALSE   FALSE
FALSE   FALSE   FALSE   TRUE    FALSE
FALSE   FALSE   FALSE   FALSE   FALSE

Смотрите вживую в электронной таблице: Документы Google

Answer 3

Поздний ответ. Недавно я узнал больше о алгоритме Куайна-МакКласки и картах Карно , которые являются систематическими подходами к имитации булевых выражений.

Я наткнулся на эту реализацию Python , которая казалась приятной и подумала, что проверю свой более ранний ответ, используя ее:

import logic
A,B,C,D = logic.bools('ABCD')

print logic.boolsimp((A & B) | (A & ~C) | (B & ~D))

Конечно, он печатает

(B & ~D) | (~C & A) | (B & A)

^{Pythonists: не обращайте внимания на странный выбор операторов для логических операций; это в основном связано с тем, что and, or и not не могут быть перегружены в Python}

---

Проверка работоспособности

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

print logic.boolsimp((A & B) | (A & ~C))
print logic.boolsimp(A & (B | ~C))

печатает дважды одинаковый вывод ((~C & A) | (B & A))

Answer 4

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

@A = B = C = D = True
Original = True
First = True
Second = False

@A = C = True, B = D = True
Original = True
First = False
Second = False

@A = True, B = C = D = False
Original = True
First = True
Second = False

@A = C = False, B = D = True
Original = True
First = False
Second = False

@A = C = D = False, B = True
Original = True
First = False
Second = False