- •Псковский государственный политехнический институт
- •Н.В. Мотина
- •Дискретная математика
- •Методические указания по выполнению контрольных работ
- •230101 «Вычислительные машины, комплексы, системы и сети»,
- •230201 «Информационные системы и технологии»
- •Псков Издательство ппи
- •Часть 1. Краткий теоретический материал 6
- •Часть 2 47
- •Порядок выполнения контрольной работы
- •Часть 1. Краткий теоретический материал
- •1. Операции над множествами
- •1.1. Понятие множества
- •1.2. Объединение, пересечение, дополнение, разность множеств
- •1.3. Прямое произведение множеств
- •Контрольные вопросы
- •2. Отношения
- •2.1. Понятие бинарного отношения
- •2.2. Обратное отношение
- •2.3. Композиция отношений
- •2.4. Векторы
- •Контрольные вопросы
- •3. Соответствия
- •Контрольные вопросы
- •4. Виды графов
- •4.1. Понятие графа
- •4.2. Связность
- •4.3. Планарность
- •4.4. Деревья
- •Контрольные вопросы
- •5. Способы задания графов
- •5.1. Матрица смежности
- •5.2. Матрица инциденций
- •Контрольные вопросы
- •6. Маршруты, цепи, циклы
- •6.1. Основные определения
- •6.2. Эйлеровы циклы
- •6.3. Гамильтоновы циклы
- •Контрольные вопросы
- •7. Преобразование логических выражений
- •7.1. Понятие логической функции
- •Продолжение табл.2
- •7.2. Тождества булевой алгебры
- •7.3. Правила преобразования некоторых логических функций
- •Контрольные вопросы
- •8. Минимизация логических функций
- •8.1. Минимизация с помощью карт Карно
- •8.2. Метод Квайна поиска СокДнф
- •8.3. Метод Квайна – Мак-Класки
- •8.4. Нахождение мкнф с помощью карты Карно
- •8.5. Минимизация логических функций, представленных в конъюнктивной форме, с использованием правил, аналогичных правилам минимизации логических функций в дизъюнктивной форме
- •8.6. Минимизация неполностью определенных логических функций с помощью карты Карно
- •8.7. Минимизация неполностью определенных логических функций без использования карты Карно
- •Контрольные вопросы
- •9. Свойства логических функций
- •Контрольные вопросы
- •Часть 2 Варианты заданий Задание 1. Операции над множествами
- •Задание 2. Отношения
- •Задание 3. Соответствия
- •Задание 4. Виды графов
- •Задание 5. Способы задания графов
- •Задание 6. Маршруты, цепи, циклы
- •Задание 7. Преобразование логических выражений
- •Задание 8. Минимизация логических функций
- •Задание 9. Свойства логических функций
- •Пример оформления контрольной работы
- •Рекомендуемая литература
- •Мотина Надежда Владимировна
Контрольные вопросы
1. Если f(x1, x2, ..., xi–1, 0, xi+1, ..., xn) = f(x1, x2, ..., xi–1, 1, xi+1, ..., xn) на одном из наборов данных, можно ли сказать, что функция f не зависит существенно от xi?
2. Можно ли сказать, что функция является самодвойственной, если она принимает противоположные значения на какой-нибудь одной паре противоположных наборов?
3. Является ли истинным следующее неравенство: (1, 0, 1) (0, 1, 0)?
4. Является ли следующий полином Жегалкина линейным: f(x1, x2) = x1 x1x2 ?
Часть 2 Варианты заданий Задание 1. Операции над множествами
Вариант 1
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = C \ (A B);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 2
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A B С;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B) \ C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 3
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = С \ B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A B;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 4
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = B С;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 5
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ С;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A С;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 6
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ С;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B С) \ (A B);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D1.
Вариант 7
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ A;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A C) \ B;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 8
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = C \ A;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B) \ C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D1.
Вариант 9
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (B C) \ A;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 10
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A \ (B C);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 11
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ B \ C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (B C) A;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 12
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ A \ C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A C) B;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 13
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = C \ A \ B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B) C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 14
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ (B C);
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (B C) A;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 15
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = (A C) \ B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = C \ (A B);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 16
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = (A B) \ C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B) (B C);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 17
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = (A B) \ C;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = ((A C) \ B) ((B C) \ A);
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D2.
Вариант 18
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A B;
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A B C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.
Вариант 19
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ (A C);
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A B C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 D1.
Вариант 20
Даны множества: Определить множества:
A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = (A B) (A C) (B C);
B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A B) \ C;
C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 D2.