- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1, x1x2, x1x2}.
|
Т0 |
Т1 |
L |
M |
S |
0 |
+ |
- |
+ |
+ |
- |
1 |
- |
+ |
+ |
+ |
- |
x1x2 |
+ |
+ |
- |
+ |
- |
x1x2 |
+ |
- |
+ |
- |
- |
Согласно
критериальной таблице, полной является
и система {1, x1x2,
x1x2}.
Константа 0 введена в эту систему для
удобства, тогда мы можем записать полином
Жегалкина в виде, где а
равны
0, если члены х
х
...х
,
в полиноме отсутствуют.
4.
Выясним, полна ли система
.
Составим критериальную таблицу, очевидно
.
Чтобы показать, что
,
достаточно найти одну функцию
и
.
Возьмем
,
удовлетворяющую требуемым условиям.
Если f
S\T0,
то f(0,
..., 0) = 1, f(1,
..., 1)=0, следовательно, f
M,
f
T1.
Рассмотрим функцию h
= x1x2
x2x3
x1x3=1,
набор ее значений (11101000), h
S\T0,
но h
L.
Следовательно, критериальная таблица
имеет вид:
|
Т0 |
Т1 |
L |
M |
S |
L |
- |
+ |
+ |
- |
- |
S\T0 |
- |
- |
- |
+ |
- |
и А – полная система функций.
Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1 x2 x3} – базис.
Контрольная работа
Вариант I
Составить таблицу истинности для булевой функции:
Составить СДНФ и СКНФ для:
Найти минимальную (сокращённую) ДНФ для в.ф. ы
Определить является ли следующая система функций полной {0,1,¬x,
}Дана формула
.
Определите булевую функцию, которую
реализует данная формула (составить
таблицу истинности)
Вариант II
Составить таблицу истинности для булевой функции:
Составить СДНФ и СКНФ для:
Найти минимальную (сокращённую) ДНФ для в.ф. ы
Определить является ли следующая система функций полной
Дана формула
.
Определите булевую функцию, которую
реализует данная формула (составить
таблицу истинности)
Раздел 4. Предикаты и бинарные отношения.
Тема 4.1 Понятие предиката. Область определения и область истинности предиката.
Предикатом
называется функция
,
где
произвольное множество, а
определённое двоичное множество
.
Иначе
говоря,
местным
предикатом, определённым на множестве
называется двузначная функция от
аргументов из произвольного множества
.
Множество
называется предметной областью предиката,
переменные
- предметными переменными. В принципе,
можно определить предикат как функцию
,
то есть допустить, что переменные
принимают значения из различных множеств
– в некоторых случаях это оказывается
удобным.
Для
любых
и
существует взаимно однозначное
соответствие между
местными
отношениями и
местными
предикатами на множестве
,
определяемое следующим образом. Каждому
местному
отношению
соответствует предикат
такой, что
тогда и только тогда, когда
;
всякий предикат
определяет отношение
такое, что
тогда и только тогда, когда
.
При этом
задаёт область истинности предиката.
Всякой
функции
можно поставить в соответствие
местный предикат
такой, что
тогда и только тогда, когда
.
Поскольку функция должна быть однозначной,
то это соответствие требует, чтобы для
любого
выполнялось
.
Поэтому обратное соответствие (от
предиката к функции) возможно только
при выполнении указанного условия.
Пример 1.
а)
Предикат
является двухместным предикатом,
предметной областью которого могут
служить любые множества действительных
чисел. Высказывание
истинно, а высказывание
ложно. Если вместо одной из переменных
подставить число, то получится одноместный
предикат:
и так далее.
б)
В описаниях вычислительных процедур
и, в частности, в языках программирования,
часто встречаются указания типа
“повторять цикл до тех пор, пока
переменные
и
не станут равными или прекратить
вычисление цикла после ста повторений”.
Если обозначить через
счётчик повторений, то описанное здесь
условие примет вид
,
а само указание в целом описывается
выражением: “повторять, если
”.
