Нормальная форма записи

Конъюнктивная и дизъюнктивная нормальная форма

Литерой будем называть переменную или ее отрицание.

Дизъюнкт – это дизъюнкция литер.

Совершенный дизъюнкт – это дизъюнкт, число литер в котором совпадает с числом переменных.

Конъюнкт – это конъюнкция литер.

Совершенный конъюнкт – это конъюнкт, число литер в котором совпадает с числом переменных.

Конъюнктивная нормальная форма – это конъюнкция дизъюнктов.

Совершенная конъюнктивная нормальная форма – это конъюнкция совершенных дизъюнктов.

Дизъюнктивная нормальная форма – это дизъюнкция конъюнктов.

Совершенная дизъюнктивная нормальная форма – это дизъюнкция совершенных конъюнктов.

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

Пусть $$F(X1, X2, …Xn)$$ – логическая функция от n переменных. Построим для нее таблицу истинности. Рассмотрим те кортежи, на которых F принимает значение 1. Для каждого такого кортежа построим совершенный конъюнкт. Если переменная $$Xk$$ в этом кортеже имеет значение 1, то соответствующая литера в конъюнкте совпадает с $$Xk$$, в противном случае литера задает отрицание $$Xk$$. По правилам построения так построенный конъюнкт на данном кортеже равен 1 и совпадает со значением функции на этом кортеже. ДНФ – задается как дизъюнкция всех таких конъюнктов. Построенная ДНФ эквивалентна функции $$F$$, поскольку совпадает с ней на всех кортежах. Заметьте, что на кортежах, не вошедших в наше построение, все конъюнкты будут иметь значение 0.

Рассмотрим пример построения ДНФ. Пусть $$F$$ – функция от четырех переменных. Она определена на 16 кортежах. Пусть на двух из них она имеет значение 1, а на остальных – 0. Приведем фрагмент таблицы истинности, где показаны только те два кортежа, на которых функция равна 1.

Построим по первому кортежу совершенный конъюнкт $$K1$$:

$$K1 = \neg X1 \neg X2 \neg X3 \neg X4$$

Построим по второму кортежу совершенный конъюнкт $$K2$$:

$$K2 = \neg X1 X2 X3 \neg X4 $$

Понятно, что по построению, конъюнкт $$K1$$ истинен на первом кортеже, а $$K2$$ – на втором.

Построим совершенную ДНФ для функции $$F$$.

$$F \equiv K1 | K2$$

На двух рассмотренных кортежах ДНФ имеет значение 1, поскольку один из конъюнктов имеет это значение. На остальных кортежах оба конъюнкта будут иметь значение 0. Поясним на примере. Рассмотрим, например, кортеж $$<1, 1, 1, 0>$$. В оба кортежа первая литера входит со знаком отрицания, поэтому на всех кортежах, где первая переменная получает значение 1, оба конъюнкта будут иметь значение 0, и ДНФ будет иметь значение 0. Аналогично обстоит дело и с другими кортежами, на которых функция имеет значение 0, там и конъюнкты будут равны нулю.

Построение КНФ - конъюнктивной нормальной формы

Пусть $$F(X1, X2, …Xn)$$ – логическая функция от $$n$$ переменных. Построим для нее таблицу истинности. Рассмотрим те кортежи, на которых $$F$$ принимает значение 0. Для каждого такого кортежа построим совершенный дизъюнкт. Если переменная $$Xk$$ в этом кортеже имеет значение 0, то соответствующая литера в конъюнкте совпадает с $$Xk$$, в противном случае литера задает отрицание $$Xk$$. По правилам построения так построенный дизъюнкт на данном кортеже равен 0 и совпадает со значением функции на этом кортеже. КНФ – задается как конъюнкция всех таких дизъюнктов. Построенная КНФ эквивалентна функции $$F$$, поскольку совпадает с ней на всех кортежах. Заметьте, что на кортежах, не вошедших в наше построение, все дизъюнкты будут иметь значение 1.

Рассмотрим пример построения KНФ. Пусть $$F$$ – функция от четырех переменных. Она определена на 16 кортежах. Пусть на двух из них она имеет значение 0, а на остальных – 1. Приведем фрагмент таблицы истинности, где показаны только те два кортежа, на которых функция равна 0.

Построим по первому кортежу совершенный дизъюнкт $$D1$$:

$$D1 = X1 | X2 | X3 | X4$$

Построим по второму кортежу совершенный конъюнкт $$K2$$:

$$D2 = X1 | \neg X2 | \neg X3 | X4 $$

Понятно, что по построению, дизъюнкт $$D1$$ ложен на первом кортеже, а $$D2$$ – на втором.

Построим совершенную КНФ для функции $$F$$.

$$F \equiv D1 D2$$

На двух рассмотренных кортежах КНФ имеет значение 0, поскольку один из дизъюнктов имеет это значение. На остальных кортежах оба дизъюнкта будут иметь значение 1. Поясним на примере. Рассмотрим, например, кортеж $$<1, 1, 1, 0>$$. В оба кортежа первая литера входит без знака отрицания, поэтому на всех кортежах, где первая переменная получает значение 1, оба дизъюнкта будут иметь значение 1, и КНФ будет иметь значение 1. Аналогично обстоит дело и с другими кортежами, на которых функция имеет значение 1, там и дизъюнкты будут равны единице.