Упростить булеву функцию F = A′B′C′D′ + A′B′CD′ + A′BC′D + A′BCD′ + AB′C′D′ + AB′C′D + ABC′D′ + ABCD до минимальной суммы произведений.

Step-by-step solution

1. 1

   Преобразуем выражение в список минтермов. Каждый конъюнкт (произведение) читается как 4-битный шаблон $ABCD$ (штрихованная переменная — это $0$):

   $A'B'C'D' = m_0, \ A'B'CD' = m_2, \ A'BC'D = m_5, \ A'BCD' = m_6$

   $AB'C'D' = m_8, \ AB'C'D = m_9, \ ABC'D' = m_{12}, \ ABCD = m_{15}$

   Таким образом,

   $F = \Sigma m(0, 2, 5, 6, 8, 9, 12, 15)$

   Изначально имеем $8$ слагаемых и $32$ литерала.

2. 2

   Находим простые импликанты. Объединяя смежные минтермы (различающиеся ровно в одном разряде) и оставляя только максимальные группы, получаем семь простых импликант:

   $A'B'D'\,(0,2), \quad A'CD'\,(2,6), \quad B'C'D'\,(0,8), \quad AC'D'\,(8,12)$

   $AB'C'\,(8,9), \quad A'BC'D\,(5), \quad ABCD\,(15)$

   Каждая группа состоит только из двух клеток — ни одного блока из четырёх, так как ни одна четвёрка этих минтермов не образует квадрат на карте Карно.

3. 3

   Определяем существенные импликанты. Минтерм $m_5$ покрывается только $A'BC'D$, а $m_{15}$ — только $ABCD$, поэтому эти два полных минтерма являются существенными и должны быть включены. Аналогично, $m_6$ содержится только в $A'CD'$, $m_9$ — только в $AB'C'$, а $m_{12}$ — только в $AC'D'$, то есть ещё три существенных простых импликанты.

4. 4

   Покрываем оставшиеся минтермы. Пять существенных слагаемых $A'BC'D$, $ABCD$, $A'CD'$, $AB'C'$, $AC'D'$ покрывают $\{2,5,6,8,9,12,15\}$, остаётся только $m_0$. Его можно покрыть либо $A'B'D'$, либо $B'C'D'$, обе группы по два элемента, поэтому существует ровно два минимальных покрытия с одинаковой стоимостью.

5. 5

   Записываем минимальную СДНФ. Выбирая $A'B'D'$:

   $F = A'B'D' + A'CD' + A'BC'D + AB'C' + AC'D' + ABCD$

   Альтернативный минимальный вариант — заменить $A'B'D'$ на $B'C'D'$. В любом случае стоимость — $6$ слагаемых и $20$ литералов, что меньше исходных $8$ слагаемых и $32$ литералов.

6. 6

   Проверяем по полной таблице истинности. Подставляя все $16$ возможных наборов значений переменных, минимизированное выражение даёт $1$ ровно на $\{0,2,5,6,8,9,12,15\}$ и $0$ в остальных случаях. Причина скромного сокращения — в структуре: минтермы вроде $m_5$ ($0101$) и $m_{15}$ ($1111$) не имеют соседей в наборе, поэтому они остаются полными четырёхлитеральными произведениями независимо от группировки на карте.