- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 8.3 Уточнения понятия алгоритм.
Существует четыре уточнения понятия алгоритм (тезисы):
Тезис Тьюринга: Общий метод (алгоритм) для решения задач из класса финитно-поставленных существует тогда и только тогда, когда кодовая функция , вычисляется на машине Тьюринга.
Тезис Чорча: Функция f, определенная на множестве N вычислима тогда и только тогда, когда она является частично рекурсивной.
Нормальный алгоритм Маркова:
, где , все рi, ai – слова в алфавите А, А – конечный алфавит.
Схема работает следующим образом: пусть - это слово из алфавита А, тогда отыскиваем сверху первую строку, левая часть которой входит по крайней мере 1 раз в слово :
Заменяем самое левое вхождение рi в слове самым правым вхождением ai. Если ни одно рi не входит в слово , то будем считать, что алгоритм не применим к этому слову.
Заменив рi на ai, получим новое слово и повторим процесс.
Процесс заканчивается на том шаге, когда .
Тезис Маркова: Для того, чтобы класс финитно-поставленных задач имел алгоритм решения необходимо и достаточно, чтобы существовал нормальный алгоритм Маркова, перерабатывающий код условия задачи в код ее ответа.
Итоговая (выходная) контрольная работа.
Вариант 1
Сколько существует подмножеств у множества А={2,7,11}?
11
3
8
6
7
5
2. Даны множества М=[2,8] N[4,10]. Найти множество N\M.
(8,10]
[8,10]
(4,10]
(4,10]
(2,4]
[2,4]
[2,4)
A={1,4}, B{2,3,5}. Определите сколько элементов содержит множество AxB.
5
6
4
7
Определите операцию, истинности таблица которой имеет вид
X |
Y |
? |
И |
И |
И |
И |
Л |
Л |
Л |
И |
Л |
Л |
Л |
Л |
дизъюнкция
конъюнкция
импликация
отрицание
Установите соответствие:
I Диструбутивный закон
Закон двойного отрицания
Закон моргана
а) ¬ ¬ x ≈ x
б) x ∧ (x ∨ z)≈ (x ∧ y)∨ (x ∧ z)
в) ¬(x ∧ y) ≈ ¬x∨ ¬y
Вставьте пропущенный символ в закон поглощения: x ___ ≈x
и
л
x
y
Высказывательная форма (¬x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (x ∨ y ∨ ¬z) является:
Приведённой
СДНФ
СКНФ
Верны a) и b)
Верны a) и с)
Является ли высказывательная форма (x→y)→(¬ y→¬x) тавтологией
нет
да
Дан предикат Найти область истинности предиката.
R
(-∞,+∞)
Сколько высказываний можно получить, навешивая кванторы на двухместный предикат?
8
2
4
6
Является ли формулой слово (где – одноместный, а - трёхместный предикатные символы).
нет
да
Если подстановку разложить в произведение циклов, то число циклов будет равно:
3
4
6
2
1
Декремент подстановки в задании 12 равен:
3
2
1
4
5
Подстановка в задании 12 является:
четной
нечетной
Дан граф Г
B
A
C E F
D
У графа Г:
5 ребер и 5 вершин
5 ребер и 6 вершин
6 ребер и 5 вершин
6 ребер и 6 вершин
Определить степень вершины А в задании 15.
4
3
2
1
Если у графа 3 вершины, причем степень первой равна 1, степень второй равна 2, а степень третьей – 3, то сколько ребер имеет граф?
4
3
2
5
Определите длину пути от вершины А до вершины F в задании 15:
3
5
4
∞
Является ли ребро <АВ> мостом?
нет
да
Граф
эйлеров
не эйлеров
Пусть Г1 – плоский связный граф без перегородок с 3 гранями и 5 ребрами. Сколько вершин у графа Г1?
2
8
4
6
A C
B
D
Найти S(AB).
2
3
∞
1
У дерева 8 вершин. Сколько ребер имеет дерево?
8
7
9
4
Вариант 2
Сколько существует подмножеств у множества А={12,17,21,22}?
22
4
16
14
12
20
Даны множества М=[1,6] N[2,11]. Найти множество N\M.
(6,11]
[6,11]
[1,11]
(1,11]
(2,6]
[2,6]
[2,6)
A={1,3,4}, B{5,8}. Определите сколько элементов содержит множество AxB.
5
6
4
7
Определите операцию, истинности таблица которой имеет вид
X |
Y |
? |
И |
И |
И |
И |
Л |
И |
Л |
И |
И |
Л |
Л |
Л |
дизъюнкция
конъюнкция
импликация
отрицание
Установите соответствие:
-
II Диструбутивный закон
Закон двойного отрицания
Закон Моргана
а) ¬ ¬ x ≈ x
б) x ∨ (x ∧ z)≈ (x ∨ y) ∧ (x ∨ z)
в) ¬(x ∨ y) ≈ ¬x ∧ ¬y
Вставьте пропущенный символ в закон поглощения: x ___ ≈x
и
л
x
y
Высказывательная форма (¬x ∨ y ) ∧ (x ∨ ¬y ) является:
Приведённой
СДНФ
СКНФ
Верны a) и b)
Верны a) и с)
Является ли высказывательная форма (x→y) ∨ (¬ y→¬x) тавтологией
нет
да
Дан предикат Найти область истинности предиката.
Z
среди ответов нет верного.
Сколько одноместных предикатов можно получить, навешивая кванторы на двухместный предикат?
8
2
4
6
Является ли формулой слово (где – одноместный, а - двуместный предикатные символы).
нет
да
Если подстановку разложить в произведение циклов, то число циклов будет равно:
3
4
6
2
1
Декремент подстановки в здании 12 равен:
3
2
1
4
5
Подстановка в здании 12 является:
четной
нечетной
Дан граф Г
B
A
C E F
D
У графа Г:
5 ребер и 5 вершин
7 ребер и 6 вершин
6 ребер и 5 вершин
6 ребер и 6 вершин
Определить степень вершины А в здании 15.
4
3
2
1
Если у графа 3 вершины, причем степень первой равна 1, степень второй равна 2, а степень третьей – 3, то сколько ребер имеет граф?
4
3
2
5
Определите длину пути от вершины А до вершины F в здании 15:
3
5
4
∞
Является ли ребро <АВ> мостом?
нет
да
Граф
эйлеров
не эйлеров
Пусть Г1 – плоский связный граф без перегородок с 3 гранями и 5 ребрами. Сколько вершин у графа Г1?
2
8
4
6
A C
B
D
Найти S(AB).
2
3
∞
1
У дерева 8 вершин. Сколько ребер имеет дерево?
8
7
9
4