Основные положения дискретной математики (стр. 7 из 11)
.Например:
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значения истинности совпадают . равносильность обозначается
., но знак = ошибкой не будет.Отношение равносильности является рефлексивным, симметричным и транзитивным.
Перечислим основные равносильности:
1. Двойное отрицание
;2. Коммутативность
3. Дистрибутивность
4. Ассоциативность
11. Идемпотентность
·
·
12. Свойства констант
·
·
·
·
·
·
13. Правила де Моргана
·
·
14. Закон противоречия\
·
15. Закон исключенного третьего
·
4.3 Доказательство равносильностей
Доказательство равносильностей можно осуществить двумя способами:
· с помощью таблицы истинности;
· с помощью рассуждений.
Пример (Задание №6): докажем равносильность
а) с помощью таблицы.
Таб. 6
| X | Y | Z |  |  |  |  |  |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Мы видим в 5-ом и 8-ом столбцах получили одинаковые значения, тем самым мы доказали равносильность данной формулы.
б) с помощью рассуждений.
1. допустим истинность левой части
2. установим истинное значение для всех истинностных переменных, входящих в список или оценку списка
3. оценку списка подставим в правую часть равносильности
4. установим истинность для правой части
5. все повторим справа налево.
I.
