WikiSort.ru - Не сортированное

Шаг 1: находим основные импликанты

Пусть функция задана с помощью следующей таблицы истинности:

# ${\displaystyle {x}}$ ${\displaystyle {y}}$ ${\displaystyle {z}}$ ${\displaystyle {t}}$ ${\displaystyle f({x},{y},{z},{t})}$ 0 0 0 0 0 0 1 0 0 0 1 0 2 0 0 1 0 0 3 0 0 1 1 0 4 0 1 0 0 1 5 0 1 0 1 0 6 0 1 1 0 0 7 0 1 1 1 0

# ${\displaystyle {x}}$ ${\displaystyle {y}}$ ${\displaystyle {z}}$ ${\displaystyle {t}}$ ${\displaystyle f({x},{y},{z},{t})}$ 8 1 0 0 0 1 9 1 0 0 1 1 10 1 0 1 0 1 11 1 0 1 1 1 12 1 1 0 0 1 13 1 1 0 1 0 14 1 1 1 0 1 15 1 1 1 1 1

Можно легко записать СДНФ, просто просуммировав минтермы (не обращая внимание на неполностью определённые термы), где функция принимает значение 1.

${\displaystyle f={\bar {x}}y{\bar {z}}{\bar {t}}+x{\bar {y}}{\bar {z}}{\bar {t}}+x{\bar {y}}z{\bar {t}}+x{\bar {y}}zt+xy{\bar {z}}{\bar {t}}+xyzt.}$

Для оптимизации запишем минтермы, включая те, которые соответствуют равнодушным состояниям, в следующую таблицу:

Теперь можно начинать комбинировать между собой минтермы, то есть проводить операцию склеивания. Если два минтерма отличаются лишь символом, который стоит в одной и той же позиции в обоих, заменяем этот символ на «-», это означает, что данный символ для нас не имеет значения. Термы, не поддающиеся дальнейшему комбинированию, обозначаются «*». При переходе к импликантам второго ранга, трактуем «-» как третье значение. Например: −110 и −100 или −11- могут быть скомбинированы, но не −110 и 011-. (Подсказка: Сначала сравнивай «-».)

 Количество "1"   Минтермы     | Импликанты 1-го уровня | Импликанты 2-го уровня
 ------------------------------|-----------------------|----------------------
 1             m4       0100   | m(4,12)  -100*        | m(8,9,10,11)   10--*
               m8       1000   | m(8,9)   100-         | m(8,10,12,14)  1--0*
 ------------------------------| m(8,10)  10-0         |----------------------
 2             m9       1001   | m(8,12)  1-00         | m(10,11,14,15) 1-1-*
               m10      1010   |-----------------------|
               m12      1100   | m(9,11)  10-1         |
 ------------------------------| m(10,11) 101-         |
 3             m11      1011   | m(10,14) 1-10         |
               m14      1110   | m(12,14) 11-0         |
 ------------------------------|-----------------------|
 4             m15      1111   | m(11,15) 1-11         |
                               | m(14,15) 111-         |

Шаг 2: таблица простых импликант

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

Принцип выбора импликант такой же как и в методе Куайна. Простые импликанты, которые является ядрами выделены жирным шрифтом. В этом примере, ядра не перекрывают все минтермы, в таком случае может быть выполнена дополнительная процедура упрощения таблицы (см. Метод Петрика). Есть два варианта:

${\displaystyle f_{x,y,z,t}=y{\bar {z}}{\bar {t}}+x{\bar {y}}+xz\ }$

${\displaystyle f_{x,y,z,t}=y{\bar {z}}{\bar {t}}+x{\bar {t}}+xz.\ }$