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

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

Данная функция имеет следующую СКНФ:

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

1 шаг. Преобраз

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

· импликация

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

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

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

Например:

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

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

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

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

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

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

Задание №5

Найти СКНФ для формулы:

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

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

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

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

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

3. шаг. Делаем дизъюнкции правильными

4. шаг. Делаем дизъюнкции полными

5. шаг. Применяем шаг 2. Получаем

6. шаг. Получили две одинаковые дизъюнкции, оставляем одну из них

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

4 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

4.1 Равносильные формулы и их доказательство

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

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

· на улице светит солнце, и в аудитории идут занятия;

· на улице светит солнце, или в аудитории идут занятия;

· если на улице светит солнце, то в аудитории идут занятия. и. т. д.

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

Рассмотрим некоторые определения.

Алфавит – любое непустое множество.

Символ – элемент алфавита.

Произвольная конечная последовательность символов, называется, словом или выражением.

Выражение называется формулой, если оно удовлетворяет следующим требованиям:

1. любая высказывательная переменная есть формула;

2. если X и Y – формулы, то выражения

…Y

тоже являются формулами.

Упорядоченный набор высказывательных переменных называется списком.

Оценка из списка – это сопоставление каждой переменной ее истинного значения.

4.2 Равносильные формулы

Пусть X и Y – формулы алгебры высказываний, а х1… хn – набор простых высказываний, входящих хотя бы в одну из формул. Формулы X и Y будем называть равносильными, если при всех значениях истинности х1… хn значения истинности совпадают . равносильность обозначается ., но знак = ошибкой не будет.