Найдите упрощенную сумму произведений логического выражения

Просто возникли некоторые проблемы с простым упрощением. Я делаю упрощение для мажоритарного декодера с 3 входами A, B и C. Его выход Y принимает 1, если 2 или все 3 входа принимают 1. Y принимает 0 в противном случае. Выберите правильную функцию переключения Y=f(A,B,C).

Итак, после составления таблицы истинности я обнаружил, что каноническая сумма произведений сводится к

NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C

Это, упрощенно, по-видимому, сводится к Y = A * B + B * C + A * C

Какие шаги предприняты для простого выражения, подобного этому? Как это делается? Как было получено это значение в данном случае?


math algebra boolean-logic theory truthtable
person Jake Pillandfall    schedule 30.04.2011    source источник

Ответы (4)


arrow_upward
5
arrow_downward

Во-первых, обратите внимание, что для логического выражения:

A= A + A

Теперь посмотри, что

NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C
= NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C + A.B.C + A.B.C
= (NOT(A)+A).B.C + A.(NOT(B)+B).C + A.B.(NOT(C)+C)
= B.C + A.C + A.B
person highBandWidth    schedule 30.04.2011

arrow_upward
2
arrow_downward

Между прочим, WolframAlpha отлично подходит для выполнения (проверки) логических вычислений, и в этом случае формат для вашего примера:

~A && B && C || A && ~B && C || A && B && ~C || A && B && C

Кроме того, ваше конкретное выражение фактически находится на этой странице в качестве примера, выполненного иначе, чем другой ответ дан.

person pflodin    schedule 30.04.2011
comment
Хорошее предложение по использованию WolframAlpha! Оглядываясь назад, это очевидно, но я не думал об этом раньше. - person dmc; 30.04.2011

arrow_upward
0
arrow_downward

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

  • Законы Де Моргана объясняют, как преобразовать термины, объединенные И, в термины, объединенные ИЛИ (и наоборот). Это очень мощная концепция, которую стоит изучить, она позволяет переводить логическое выражение в чистую форму И-НЕ или чистую форму НЕ-ИЛИ, для чего есть очень веские причины.

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

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

Для каждой строки в таблице истинности, где выход равен 1, вы можете относительно легко сформировать логическое выражение только для этой строки. Полное логическое выражение получается путем объединения всех выражений для каждой строки с помощью операции ИЛИ. Это будет минимальное выражение (могут быть и другие, более минимального не будет).

person Jon Cram    schedule 30.04.2011

arrow_upward
0
arrow_downward

Другое объяснение.

У нас есть (1):

(not(A) and B and C ) or (A and not(B) and C) or (A and B and not C) or (A and B and C).

Мы знаем это:

A = A or A.

Таким образом, мы можем переписать (1) в (2):

(not(A) and B and C ) or (A and B and C) or
(A and not(B) and C) or (A and B and C) or
(A and B and not C) or (A and B and C)

Мы также знаем, что:

(A and B) or (A and not B) = A and (B or not B) = A

Таким образом, мы можем переписать (2) в (3):

(B and C) or (A and C) or (A and B)

Идея состоит в том, чтобы найти группы, которые можно (частично) исключить, чтобы упростить уравнение.

person Toon Krijthe    schedule 30.04.2011