- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •1Вариант
- •2 Вариант
- •Раздел 1. Основы теории множеств
- •Тема 1.1 Основные понятия теории множеств.
- •Тема 1.2 Операции над множествами.
- •Самостоятельная работа № 1
- •Тема 1.3 Свойства операций.
- •Контрольная работа
- •1 Вариант
- •2 Вариант
- •Раздел 2. Формулы логики.
- •Тема 2.1 Основные логические операции.
- •Тема 2.2 Формулы логики.
- •Самостоятельная работа №2.
- •Тема 2.3 Дизъюнктивная нормальная форма.
- •Различны все члены дизъюнкции;
- •Тема 2.4 Конъюнктивная нормальная форма.
- •Тема 2.5 Равносильные формулы. Свойства.
- •Раздел 3. Булевы функции.
- •Тема 3.1 Понятие булевой функции.
- •Тема 3.2 Совершенная днф. Совершенная кнф. Совершенной дизъюнктивной формой формулы алгебры высказываний (сднф) называется днф, в которой:
- •Различны все члены дизъюнкции;
- •Самостоятельная работа №5.
- •Тема 3.3 Минимальная днф.
- •Тема 3.4 Представление булевой функции в виде минимальной днф.
- •Самостоятельная работа №6. Самостоятельная работа №7
- •Тема 3.5 Полнота множества функций.
- •Тема 3.6 Важнейшие замкнутые классы.
- •Важнейшие замкнутые классы в р2
- •Тема 3.7 Теорема Поста.
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1, x1x2, x1x2}.
- •Контрольная работа
- •Раздел 4. Предикаты и бинарные отношения.
- •Тема 4.1 Понятие предиката. Область определения и область истинности предиката.
- •Тема 4.2 Логические операции над предикатами.
- •Самостоятельная работа №8.
- •Тема 4.3 Кванторные операции над предикатами.
- •2. Квантор существования
- •- «Все люди любят всех людей».
- •- «Существует человек, который кого-то любит» .
- •- «Существует человек, который любит всех людей».
- •Тема 4.4 Понятие предикатной формулы.
- •Тема 4.5 Равносильность предикатов. Исчисление предикатов.
- •Самостоятельная работа №9.
- •Тема 4.6 Бинарные отношения и их свойства.
- •Самостоятельная работа №10. Контрольная работа
- •Раздел 5. Отображения. Подстановки.
- •Тема 5.1 Отображения и их свойства.
- •Самостоятельная работа №11.
- •Тема 5.2 Композиция отображений и обратное отображение.
- •Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.
- •Самостоятельная работа №12. Контрольная работа
- •1 Вариант
- •2 Вариант
- •3 Вариант
- •4 Вариант
- •5 Вариант
- •Раздел 6. Метод математической индукции.
- •Тема 6.1 Принцип метода математической индукции.
- •Раздел 7. Основы теории графов.
- •Тема 7.1 Понятие неориентированный граф. Основные определения.
- •Лабораторная работа № 1.
- •Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
- •Лабораторная работа № 2.
- •Тема 7.3 Метрические характеристики графа.
- •Лабораторная работа № 3.
- •Тема 7.4 Двудольные и изоморфные графы.
- •Лабораторная работа № 4.
- •Тема 7.5 Эйлеровы и гамильтоновы графы.
- •Лабораторная работа № 5
- •Тема 7.6 Плоские графы.
- •Тема 7.7 Деревья. Код Пруфера.
- •Тема 7.8 Понятие ориентированный граф (орграф).
- •Тема 7.9 Достижимость вершин в орграфе.
- •Раздел 8. Элементы теории алгоритмов.
- •Тема 8.1 Определение класса финитно-поставленных задач.
- •Тема 8.2 Машины Тьюринга.
- •Тема 8.3 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 2.4 Конъюнктивная нормальная форма.
Высказывательная форма, состоящая из переменных или отрицательных переменных, применением только одной операции конъюнкции, называется элементарной конъюнкцией.
Высказывательная форма, состоящая из элементарных дизъюнкций, применением только одной операции конъюнкции называется конъюнктивной нормальной формой (КНФ).
Теорема: Для любой высказывательной формы существуют равносильные ДНФ и КНФ.
Доказательство:
по теореме 1 существует Ы* - приведенная равносильная высказывательная форма, т.е. , к Ы* применим первый дистрибутивный закон необходимое число раз, тогда получим приведенную форму, которая будет являться ДНФ, если закон уже применить нельзя. Если невозможно применить первый дистрибутивный закон, то все члены любой конъюнкции в этой форме является либо переменными или отрицаниями переменных.
Для того чтобы получить КНФ необходимо к высказывательной форме применить второй дистрибутивный закон, также нужное число раз.
Способы построения ДНФ и КНФ для любой высказывательной формы:
составляется Ы* - приведенная высказывательная форма, являющаяся равносильной (т.е. применяется необходимое число раз законы Моргана, импликации)
для получения ДНФ к Ы* применяется первый дистрибутивный закон:
для получения КНФ к Ы* применяется второй дистрибутивный закон:
Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:
различны все члены конъюнкции;
различны все члены каждой дизъюнкции;
ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;
каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид
,
где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0.
Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов.
Опишем два способа приведения к совершенным нормальным формам.
1-й способ – аналитический
Приведение к СКНФ. Алгоритм приведения.
привести формулу с помощью равносильных преобразований к КНФ.
удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;
если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.
Полученная формула и является СКНФ данной формулы.
Привести следующие формулы к СКНФ с помощью равносильных преобразований:
1. ;
2. .
Решение.
1.
2.
2-й способ – табличный.
Составляем таблицу истинности для данной функции.
Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.
Построить СКНФ для данных формул логики высказываний.
1. .
2.
Решение.
Строим таблицу значений, используя предыдущий пример.
№ |
x |
y |
z |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
2 |
0 |
1 |
0 |
0 |
3 |
0 |
1 |
1 |
0 |
4 |
1 |
0 |
0 |
1 |
5 |
1 |
0 |
1 |
1 |
6 |
1 |
1 |
0 |
0 |
7 |
1 |
1 |
1 |
1 |
Рассматриваем только наборы, на которых формула принимает значение ноль.
СКНФ (0): № 0, 1, 2, 3, 6:
Строим таблицу значений, используя предыдущий пример.
№ |
x |
y |
F=(x y)xy |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
0 |
3 |
1 |
1 |
1 |
СКНФ (0): № 0, 1, 2: