Что такое импликанты: Импликанты, система импликант

Что такое СокрДНФ

Сокращенная ДНФ функции 𝑓 – это дизъюнкция всех её простых импликант. То есть, если звучит задача “найти все простые импликанты функции”, значит, нужно построить её СокрДНФ.

Алгоритм СокрДНФ по таблице истинности

3 переменных

1. Строим СДНФ
2. Отмечаем, где функция принимает значение “1”
3. Строим кубик
4. Закрашиваем вершины, где значение “1”
5. Склеиваем рёбра кубика: 2 точки → ребро; 4 ребра в одной плоскости → грань.

А для 4 переменных

Тут вы кубик не нарисуете (если можете представить 4-мерный куб, респект, конечно, но есть метод попроще)

1. Выписываем таблицу истинности f
2. Отмечаем строки со значением функции “1”
3. Расставляем в блоки по количеству единиц в строке с переменными
4. Склеиваем строки из соседних блоков: должно быть отличие ровно в одной позиции, её обозначаем за *. Результат записываем в новый блок. Блоки идут в такой очерёдности: склейка 1 и 2 блока, 2 и 3, 3 и 4, …
5. Когда склеиваем, отмечаем, какие пары мы склеивали (какие из строк участвовали хотя бы в одной склейке)
6. Строки, которые не были помечены (не участвовали ни в одной склейке) являются одним из слагаемых СокрДНФ. 0 - это отрицание переменной по этой позиции, 1 - без отрицания.