yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1.5 Дизъюнктивные и конъюнктивные нормальные формы.

Математическая логика

1.5 Дизъюнктивные и конъюнктивные нормальные формы.

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

Определение 1.7 Всякая булева формула, построенная с помощью одной только операции дизъюнкции над булевыми переменными или их отрицаниями, называются элементарной дизъюнкцией. Например, x1 v x2 v¬x3 v x4 - элементарная дизъюнкция.

Определение 1.8. Всякая  булева формула, построенная с помощью одной только операции конъюнкции над переменными или их отрицаниями, называется элементарной конъюнкцией. Например, х1 х2¬x3¬x4, х ¬уz -элементарные конъюнкции.

Теорема 1.1. Для того, чтобы элементарная дизъюнкция равнялась единице, необходимо и достаточно, чтобы .в нее входила некоторая переменная вместе со своим отрицанием.

Теорема 1.2. Для того, чтобы элементарная конъюнкция равнялась нулю, необходимо и достаточно, чтобы в нее входила некоторая переменная вместе со своим отрицанием.

Справедливость теорем 1.1, 1.2 следует из аксиомы (1.4) я определения операций дизъюнкции и конъюнкции.

Определение 1.9. Булева функция называется конституентной единицы (или минтермом), если она равна единице только на одном наборе своих аргументов.

    Определение 1.10. Булева функция называется конституентой нуля (или ), если она равна нулю только на одном наборе своих аргументов.

    Теорема 1.1. Для того, чтобы элементарная дизъюнкция равнялась единице, необходимо и достаточно, чтобы .в нее входила некоторая переменная вместе со своим отрицанием.

Теорема 1.2. Для того, чтобы элементарная конъюнкция равнялась нулю, необходимо и достаточно, чтобы в нее входила некоторая переменная вместе со споим отрицанием.

Справедливость теорем 1.1, 1.2 следует из аксиомы (1.4) и определения операций дизъюнкции и конъюнкции

Определение 1.9. Булева функция называется конституентной единицы (или минтермом), если она равна единице только на одном наборе своих аргументов.

Определение 1.10. Булева функция называется конституентной нуля (или котурном), если она равна нулю только на одном наборе своих аргументов.

Пример. Среди булевых функций двух аргументов функции конъюнкция, стрелка Пирса являются конституэнтами единицы, а функции дизъюнкция, импликация, штрих Шеффера являются конституэнтами нуля.

Теорема 1.3. Не тождественно ложная элементарная конъюнкция от n переменных является конституентой единицы от n переменных.

Доказательство. Введем обозначение: х°= ¬ х, х'=х. Обозначим параметр 0 или 1 через a. Тогда х=1, если х = а и х=0, если ха.

Рассмотрим элементарную конъюнкцию вида, о которой известно, что она не равна нулю тождественно. Отсюда следует (по теореме 1.1), что все входящие в нее переменные различны и им можно придавать независимые значения. Придадим переменной x значение а х, - а и т.д. до х.Тогда элементарная конъюнкция равна единице по самому выбору значений х, x, ..., х. Выбор этих значений таков, что если переменная Х| входит в элементарную конъюнкцию без отрицания, то а,=0 и переменной х, тоже придаем значение равное нулю. Таким образом, будет найден набор, на котором данная конъюнкция будет равна единице. Единственность такого Набора следует на определения операции конъюнкции.

Из теоремы 1.3 следует, что всякую конституенту единицы можно представить в виде элементарной конъюнкции. Для этого необходимо образовать конъюнкцию всех ее аргументов и расставить отрицания над теми переменными, которые равную нулю на наборе, обращающем функцию в единицу-

Аналогичную теорему можно доказать для элементарной дизъюнкции.

Теорема 1.4. Не тождественно истинная элементарная дизъюнкция от и переменных является конституентой нуля от n переменных.

Из этой теоремы следует, что любую конституенту нуля можно представить в виде элементарной дизъюнкции. Для этого необходимо образовать дизъюнкцию всех переменных и расставить отрицания над теми переменными, которые равны единице в наборе, обращающем функцию в нуль.

Пример. Функция f(x,y,z,v) равна единице на единственном наборе: оно, следовательно она является конституентой единицы. Ее можно записать в виде: f(x,y,z,v)=-.xyz-v

Определение 1.11. Дизъюнкция элементарных конъюнкций, не содержащая двух одинаковых произведений, называется дизъюнктивной нормальной формой (ДНФ).

Определение 1.12. Дизъюнктивная нормальная форма, все слагаемые которой есть конституенты единицы, называется совершенней  дизъюктивной нормальной формой (СДНФ).

Определение 1.13. Конъюнкция элементарных дизъюнкций, не содержащая двух одинаковых сумм, называется нормальной конъюнктивной формой (КНФ).

Определение 1.14. Конъюнктивная нормальная форма, все сомножители которой есть конституенты нуля, называется совершенной конъюнктивной нормальной (СКВФ).                    

Теорема 1.6. Любую булеву функцию можно представить в виде СДИФ и С КНФ.

Доказательство. Рассмотрим произвольную булеву функцию t(x1,x2,....xn). Пусть f0, и a1, - наборы, на которых функция принимает значение, равное единице, а также fl и B1,B2,...,Bn k - наборы, на которых функция равна нулю. Построим элементарные конъюнкции Ка1, Ка2,..., Кank, каждая из которых содержит все n переменных и не является тождественно ложной. Построим эти элементарные конъюнкции таким образом. чтобы Ка1, принимала значение, равное единице, ни наборе а1. Ка2 -на наборе а, и т. д. Согласно теореме 1.3, каждая из этих конъюнкций является конституентой единицы, и на остальных наборах принимает значение, равное нулю. По своему построению совокупность всех этих конституент единицы описывает все единицы данной функции. Поэтому их дизъюнкция равносильна  данной функции: f(x1,...,xn)=Ku1(x,....,x1,)vKa2(x1,...,xn,)v...v Kan,.k(x1,...,xn). По определению 1.12 полученная формула является совершенной нормальной дизъюнктивной формой данной функции.

Аналогично можно показать, что формула А=Кβ1, Кβ2, Кβnk, являющаяся конъюнкцией всех конституент нуля на наборах, где функция равна нулю, равносильна данной функции, и является СКНФ функции.

Пример. Построение СДНФ и СКНФ булевой функции.

 

Таблица 1.4.

X

 

0

0

0

0

1

1

1

1

У

 

0

0

1

1

0

0

1

1

Z

 

0

1

0

1

0

1

0

1

f(x,y.z)

 

1

0

0

1

1

1

0

0

СДНФ: f(x,y,z)=¬x¬y¬zv¬xyzvx¬y¬zvx¬yz;

СКНФ: f(x,y,z)=(xvyv¬z)(xv¬yvz)( ¬xv¬yvz)( ¬xv¬yv¬z).

Таким образом, для построения СДНФ булевой функции необходимо рассмотреть все наборы, на которых функция равна единице, И образовать конституенты единицы, соответствующие этим наборам. Полученные конституенты объединить знаками дизъюнкции. Двойственное правило существует для построения СКНФ. Другой способ заключается в том, что любую булеву формулу можно привести к виду ДНФ (КНФ) и СДНФ (СКНФ) с помощью эквивалентных преобразовании, используя соотношения (1.1) - (1.13).

 

9