Минимизация конъюнктивных нормальных форм

Для построения минимальной конъюнктивной нормальной формы (МКНФ) функции f нужно построить минимальную ДНФ функции и в полученной минимальной ДНФ заменить знак & на знак , знак заменить на знак &, а над каждой переменной поставить знак отрицания. Это и будет минимальная КНФ функции f. Следует учесть, что ( - двойное отрицание).

Пример.

Построить минимальную КНФ функции f из примера (*).

Решение: Построим таблицу истинности для функции . Для этого значение 0 заменим на 1, а значение 1 заменим на 0.

 

x	y	z

 

 

Строим СДНФ функции :

СДНФ .

Строим СКНФ функции :

СКНФ .

Раскроем скобки в выражении для СКНФ функции . Получим сокращённую ДНФ функции :

сокр. ДНФ .

Составим таблицу покрытий.

 

(1)
(2)
(3)
(4)

 

Решеточное выражение равно

34(2 3)(1 2)(1 4) = (342 343)(1 21 14 24) = (342 34)(1 24) =

= 34(1 24) = 341 3424 = 134 234.

Выражению 134 соответствует тупиковая ДНФ функции , равная , которая содержит 6 переменных и отрицаний переменных.

Выражению 234 соответствует тупиковая ДНФ функции , равная , которая содержит 6 переменных и отрицаний переменных.

Так как обе тупиковые ДНФ функции содержат по 6 переменных или отрицаний переменных, то каждая из них является минимальной ДНФ функции . Построим по ним минимальные КНФ функции f. В формуле заменим знак & на знак , знак заменим на знак &, а над каждой переменной поставим знак отрицания. Получим форму . Это и будет минимальная КНФ функции f.

В формуле заменим знак & на знак , знак заменим на знак &, а над каждой переменной поставим знак отрицания. Получим форму . Это минимальная КНФ функции f.

Минимизация в классе нормальных форм

Для того, чтобы построить минимальную нормальную форму (МНФ) функции f, необходимо выполнить следующие действия:

1. Построить все минимальные ДНФ функции f.

2. Найти все минимальные КНФ функции f.

3. Из полученных форм нужно выбрать форму с наименьшим числом переменных и отрицаний переменных. Это и есть минимальная нормальная форма (МНФ) функции f.

Пример.

Построить минимальную нормальную форму (МНФ) функции f из примера (*)

Решение: Минимальная ДНФ функции f равна и содержит 5 переменных и отрицаний переменных. Обе минимальные КНФ функции f ( и ) содержат по 6 переменных и отрицаний переменных. Поэтому минимальная нормальная форма функции f совпадает с минимальной ДНФ функции f и равна

.

 

Задачи для самостоятельного решения

1. Построить СДНФ, СКНФ, сокращённую ДНФ, тупиковую и минимальную ДНФ, минимальную КНФ, минимальную нормальную форму для функции f, таблица истинности которой имеет следующий вид:

 

 

а).

 

x	y	z

 

б).

 

x	y	z

 

 

в).

 

x	y	z

 

г).

 

x	y	z

 

 

д).

x	y	z

 

Практическое занятие №4

Основные понятия теории графов.