- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 3.4 Представление булевой функции в виде минимальной днф.
Метод квайна, минимизация при помощи карт Вейча-Карно
Самостоятельная работа №6. Самостоятельная работа №7
Тема 3.5 Полнота множества функций.
Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.
Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция.
Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций..
Составление сложных функций из элементарных функций системы называется суперпозицией.
Достаточное условие полноты системы.
Пусть система функций {f1, f2, …, fm} (I) полная и любая из функций этой системы может быть выражена через функции g1, g2, …, gl , тогда система { g1, g2, …, gl}(II) тоже полная.
Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия.
Тема 3.6 Важнейшие замкнутые классы.
Пусть MР2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M].
Множество функций М называется замкнутым классом, если [M]=M.
Пример:
1) P2 – замкнутый класс.
2) Множество {1,x1x2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 x2}] = {f(x1, ..., xn) = c0 c1x1 cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 х2, будет формулой над М: f(G1, x3) = (x1 x2) x3.
В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:
М – полная система, если [M] = P2.
3) A = {f(x1, ..., xn) f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g1, ..., gn A, т.е. f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0, тогда f(g1, ..., gn) [A]. Посмотрим, принадлежит ли функция f(g1, ..., gn) множеству А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g1(x1, x2) = x1 x2, g2(x) = x A. Возьмем g2(g1(x1, x2)) = x1 x2 [A], g2(g1(1, 1)) = 1 1 = 0, следовательно, g2(g1(x1, x2)) A, отсюда [A] A и А – незамкнутый класс.
Важнейшие замкнутые классы в р2
1) Т0 - класс функций, сохраняющих константу 0.
Т0 = { f(x1, ..., xn f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0 и Т0 Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2, не входящих в Т0: x1&x2, x1x2, xТ0 и x1|x2, x1 x2, Т0. Покажем далее, что [Т0] = Т0. Вложение Т0 [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0]. Покажем, что [Т0] Т0. Для этого надо показать, что Ф = f(f1, ..., fm) [ Т0], если все функции f, f1, f2, f3, ..., fm Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0, поэтому достаточно показать, что Ф = f (f 1, ..., fm) Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.
Число функций, зависящих от n переменных и принадлежащих Т0, будет равно
2) T1 – класс функций, сохраняющих константу 1.
T1 = {f(x1, ...) f(1, 1, ...) = 1}; x1&x2, x1x2, xT1, х1х2, x1 x2T1, следовательно Т1 – собственное подмножество Р2.
Покажем, что [T1] T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) [T1], где f, f1, ..., fn T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) T1, отсюда следует [T1] = T1.
3) S – класс самодвойственных функций.
S = {f(x1, ...)f* = f }; x, , x1x2x3S, x1&x2, x1x2, x1x2S, следовательно, S – собственное подмножество Р2. |S(n)| = . Покажем, что [S]S. Ф = f(f1, ..., fn) [S], если f, f1, ..., fn S, а также, что Ф S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.
4) L – класс линейных функций.
L = {f(x1, ...) f = c0c1x1...cnxn}; очевидно, L , с другой стороны
L P2, так как x1&x2 L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn L. Тогда Ф = а0 а1(с10 с11х1 ... c1nxn1) a2(c20 c21x1 c22x2...c2nxn2)...an(cm0 cm1x1 ... cmnxnm) = в0 в1х1 ... вnхn ФL.
5) М – класс монотонных функций.
Набор = (1, ..., n) предшествует набору = (1, ..., n) и обозначается , если для 1in ii, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования ( ) является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.
Функция f(x1, ..., xn) называется монотонной, если для двух наборов и , таких что , выполняется f( ) f( ). Функции 0, 1, x, x1&x2, x1x2 M, x1x2, x1 x2, x1 ~ x2 M.
Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию Ф[M], Ф = f(f1, ..., fm), где f, f1, ..., fmM, причем можем считать, что все они зависят от n переменных. Пусть набор = 1, ..., n), = (1, ..., n). Рассмотрим Ф1, ..., n) = f(f11, ..., n), …, fm1, ..., n)) и Ф(1, ..., n) = f(f1(1, ..., n), ..., fm(1, ..., n)). Здесь f1() f1(), ..., fm() fm(), тогда набор (f1(), ..., fm()) (f1(), ..., fm()), но тогда Ф() Ф(), так как fM, отсюда Ф = f(f1, ..., ) – монотонная функция.
Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.
Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.
Доказательство. Пусть f(x1, ..., xn) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i1, …, ik есть все те номера аргументов, для которых , p=1, …, k. На всех остальных аргументных местах j имеем j = j. В выражении заменим нули на местах i1, …, ik на x. В результате получим функцию g(x), для которой g(0) = f( ) = 1 и g(1) = f( ) = 0. Функция g(x) является отрицанием.
Классы T0, T1, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.
|
T0 |
T1 |
L |
S |
M |
x |
+ |
+ |
+ |
+ |
+ |
|
- |
- |
+ |
+ |
- |
0 |
+ |
- |
+ |
- |
+ |
1 |
- |
+ |
+ |
- |
+ |
x1x2 |
+ |
+ |
- |
- |
+ |
A={x, , 0, 1, x1x2) не является полной системой функций так как всегда есть функции Р2 не входящие в эти классы.
Задачи
1. Доказать, что пересечение любых двух замкнутых классов замкнуто.
2. Доказать, что объединение двух замкнутых классов не всегда замкнуто