Основные положения дискретной математики

Данная функция имеет следующую СДНФ: . Однако, если функция задана формулой, то строить СДНФ по таблице не рационально, тогда применяют следующий алгоритм: построение СДНФ состоит из двух этапов, каждых из которых состоит их трех шагов. На первом этапе строят ДНФ, а на втором этапе из ДНФ строят СДНФ.

1 шаг. Преобразуем форм

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

· импликация

· эквивалентность

· перенос отрицания: из свойств: и можно произвести следующие преобразования:

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

Например:

3 шаг. Если в ДНФ имеется несколько одинаковых элементарных конъюнкций, то мы оставляем только одну (используя свойство идемпотентности: ).

4 шаг. Делаем все элементарные конъюнкции правильными путем одним из следующих преобразований:

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

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

5 шаг. Делаем все элементарные конъюнкции полными. Если в некоторую конъюнкцию не входит переменная y , то необходимо рассмотреть равносильное выражение и вновь применить шаг 2. Если недостающих переменных несколько, то нужно добавить несколько конъюнктивных членов вида .

6 шаг. После применения 5-го шага могут вновь появится одинаковые конъюнкции. Поэтому на шестом шаге применяют шаг 3.

Задание №5.

Найти СДНФ для следующей формулы:

=

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

Используя свойство , получим

используя свойство ,получим

=

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

Используя свойство дистрибутивности получим

=

3. шаг. Все конъюнкции получились правильными, делаем их полными

4. шаг. Одинаковых конъюнкций нет, следовательно оставляем их все.

получили совершенную дизъюнктивную нормальную форму.

(в конце примера опущен знак конъюнкции)

3.2 Совершенная конъюнктивная нормальная форма (СКНФ)

Формула вида , называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется, конъюнктивной нормальной формой

Элементарная дизъюнкция, называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания).

Правильная элементарная дизъюнкция, называется полной относительно переменных х1…хn , если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Совершенной конъюнктивной нормальной формой относительно переменных х1…хn , называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных х1…хn.

Теорема 3: всякую функцию f можно представить в СКНФ

, (4)

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

3.2.1 Алгоритм преобразования формулы в СКНФ

Преобразование формулы в СКНФ производится аналогично преобразованию формулы в СДНФ. Отличие состоит в том, что образовывать нужно не конъюнкции, а дизъюнкции.

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

Например таблицей задана функция от трех переменных равная 1, если большинство аргументов равно 1.

Таб. 5

 Скачать реферат