Построение минимальной дизъюнктивной нормальной формы

Формула (булева функция) имеет минимальную ДНФ, если она содержит наименьшее количество литералов среди всех ДНФ, эквивалентных ей.

Пример:

ДНФ ─ содержит 4 литерала, но она не является минимальной. Преобразуем ее ()=1·=. Получили один литерал.

Рассмотрим алгоритм Квайна Мак-Клоски:

Пусть функция задана СДНФ и ,- два элементарных произведения, входящих в СДНФ. Пусть х ─ литерал, такой, что = xk и = k. Тогда = хk k = (x ) k = k. Мы получили элементарное произведение, содержащее на один литерал меньше.

Такая операция называется склейкой.

Пример:

Ф=pqrрrqr. Произведем склейку первой и второй, а так же третьей и четвертой элементарных произведений.

Ф = pr(q)(q)r prr.

Дата добавления: 2014-01-06