Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Формула называется СДНФ, если:

1) она является ДНФ;

2) каждая элементарная конъюнкция ДНФ содержит все наименования переменных, от которых зависит формула, и каждое наименование входит в него один раз;

3) среди элементарных конъюнкций ДНФ нет одинаковых.

Примеры:

1. - СДНФ

2. - не является СДНФ, т.к. в первой скобке нет переменной Z.

Формула называется СКНФ, если

1) она является КНФ;

2) каждая элементарная дизъюнкция КНФ содержит все наименования переменных, от которых зависит формула и это наименование входит только один раз;

3) среди элементарных дизъюнкций КНФ нет одинаковых.

Пример:

- СКНФ

Теорема 1: Если формула не тождественно истинная, то для нее существует и при том единственная СКНФ.

Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ.

Совершенные формы можно строить с помощью:

1) равносильных преобразований;

2) таблиц истинности.

Алгоритм построения СДНФ с помощью таблице истинности:

Рассмотрим этот алгоритм на конкретном примере, используя таблицу истинности

1) выбираем те строки таблицы , на которых формула принимает значение истина: 2, 4, 7, 8;

2) для каждой выбранной строки строим элементарную конъюнкцию из переменных, от которых зависит формула следующим образом: если переменная в строке принимает значение истина, то она непосредственно входит в элементарную конъюнкцию, если ложь, то она входит с отрицанием;

3) из элементарных конъюнкций составляем ДНФ.

- СДНФ

Замечание: Если все строки формулы в таблице истинности принимают значение ложь, то СДНФ построить нельзя.

Алгоритм построения СКНФ по таблице истинности:

Данный алгоритм аналогичен алгоритму построения СДНФ.

1) выбираем строки таблицы, на которых формула принимает значение ложь: 1, 3, 5, 6;

2) для каждой выбранной строки строим элементарную дизъюнкцию из переменных, от которых зависит формула, следующим образом: если переменная в строке принимает значение ложь, то она сама входит в элементарную дизъюнкцию, если истина, то она входит с отрицанием;

3) из элементарных дизъюнкции составляем КНФ.

- СКНФ

Замечание: Если все строки формулы в таблице принимают значение истина, то СКНФ построить нельзя.

С точки зрения алгебры логики представление функции в виде СНКФ рациональнее, когда таблица истинности содержит меньше нулей , чем единиц

Описанный способ нахождения СНДФ и СНКФ исходной формулы по таблице истинности бывает более трудоёмким, чем следующий:

Алгоритм построения СДНФ с помощью равносильных преобразований:

1) приводим исходную формулу к ДНФ;

2) если в элементарную конъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ;

3) если в элементарную конъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной;

4) если в некоторую элементарную конъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к ДНФ;

5) если в полученной ДНФ имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них.

В результате получаем СДНФ.

Пример:

Пусть дана ДНФ функции. Найдте СДНФ функции.

-СДНФ

Алгоритм построения СКНФ с помощью равносильных преобразований:

1) приводим исходную формулу к КНФ;

2) если в элементарную дизъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из КНФ;

3) если в элементарную дизъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной;

4) если в некоторую элементарную дизъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к КНФ;

5) если в полученной КНФ имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них.

В результате получаем СКНФ.

Пример:

Пусть дана КНФ функции . Найти СКНФ функции.

- СКНФ.

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

Рассмотрим следующие алгоритмы:

1) Для определения типа формулы надо построить ДНФ (КНФ) и

проверить критерий ложности (критерий истинности). Если критерий выполнен, то формула тождественно ложна (тождественно истинна), если нет, то строим КНФ (ДНФ) и проверяем критерий истинности

(критерий ложности), если критерий выполнен, то формула тождественно истинна (тождественно ложна) в противном случае, формула только выполнима.

2) Для определения типа формулы надо построить СДНФ или СКНФ. Если СДНФ построена, то формула не является тождественно ложной. Далее считаем число слагаемых в СДНФ: если их ,где n - число переменных, от которых зависит формула, то формула тождественно истинна, в противном случае выполнима.

Если СКНФ построена, то формула не тождественно истинна. Если число слагаемых в СКНФ равно , где n - число переменных, то формула тождественно ложна, в противном случае формула выполнима.

III. БУЛЕВЫ ФУНКЦИИ.