- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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.7 Теорема Поста.
Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T0, T1, L, S, M.
Доказательство. Докажем необходимость этого условия. Пусть система
N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N Q, очевидно, [N] [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана.
Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0T0, f1T1, fLL, fsS и fmM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x1&x2, }.
1. Пусть g(x) = f0(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая:
g(1) = 1. Тогда g(x) 1. Функция h(x) = f1(g(x), …, g(x)) = f1(1, …, 1) = 0, т.е. h(x) 0. Получили константы 0 и 1;
g(1) = 0. Тогда g(x) = . По лемме о несамодвойственной функции суперпозицией над {fs, } можно получить одну из констант, например, 0. Тогда f0(0, …, 0) = 1 есть другая константа.
В обоих случаях получили обе константы.
2. По лемме о немонотонной функции суперпозицией над {fm, 0, 1} можно получить отрицание.
3. По лемме о нелинейной функции суперпозицией над {fL, 1, } можно получить конъюнкцию. Теорема доказана.
Следствие. Всякий замкнутый класс функций из Р2, не совпадающий с Р2 содержится, по крайней мере, в одном из замкнутых классов T0, T1, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P2, что неверно.
Примеры использования теоремы Поста.
1. Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = x1x2x3} полна в Р2. Составим таблицу, которая называется критериальной :
|
Т0 |
Т1 |
L |
M |
S |
x1x2 |
+ |
+ |
- |
+ |
- |
0 |
+ |
- |
+ |
+ |
- |
1 |
- |
+ |
+ |
+ |
- |
x1x2x3 |
+ |
+ |
+ |
- |
+ |
x1 x2 x3 |
x1x2x3 |
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 0 0 0 1 0 0 1 |
Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы , которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».
Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4}L, {f1, f3, f4}T1, {f1, f2, f4}T0, {f1, f2, f3}M.
2. Мы знаем, что система {x1|x2} – полна в Р2. Какова для нее критериальная таблица? x1|x2= = x1x21.
|
Т0 |
Т1 |
L |
M |
S |
x1|x2 |
- |
- |
- |
- |
- |