Voprosy_Diskretnaya_matematika_2013_I
.docПриложение №7 к Положению об организации и проведении промежуточной
аттестации студентов. Утверждено Приказом от 05.11.2009 г. № 108
ФГОУ СПО «Уральский радиотехнический колледж им. А.С. Попова»
|
|||
ОДОБРЕНЫ |
|
УТВЕРЖДАЮ |
|
ЦМК «ЭВМ» |
|
Заместитель директора по учебной работе
________ Д.В. Колесников |
|
|
|
|
|
Протокол от «____» ___ 20 ___ г. № ___ |
|
|
|
Председатель ЦМК
__________ Поликарпова С.В. |
«____» ___________20___ г. |
|
Вопросы к зачету по дисциплине
«Дискретная математика»
для специальности 080802 Прикладная информатика
семестр 4
-
Высказывания. Конъюнкция высказываний. Таблица истинности конъюнкции.
-
Высказывания. Дизъюнкция высказываний. Таблица истинности дизъюнкции.
-
Высказывания. Строгая дизъюнкция высказываний. Таблица истинности строгой дизъюнкции.
-
Высказывания. Импликация высказываний. Таблица истинности импликации.
-
Высказывания. Эквиваленция высказываний. Таблица истинности эквиваленции.
-
Высказывания. Отрицание высказываний. Таблица истинности высказывания.
-
Тождественно-истинные и тождественно-ложные формулы; равносильные формулы.
-
Законы алгебры логики.
-
Понятие булевой функции. Булевы функции одной переменной.
-
Понятие булевой функции. Булевы функции двух переменных.
-
Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ).
-
Методика представления булевой функции в виде совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).
-
Минимизация булевых функций с помощью карт Карно.
-
Двойственность булевых функций.
-
Полнота множества функций. Теорема Поста.
-
Предикаты. Логические операции над предикатами.
-
Кванторные операции над предикатами.
-
Понятие множества, пустого множества, универсума.
-
Графическое изображение множеств (диаграммы Эйлера-Венна).
-
Способы задания множеств.
-
Сравнение множеств.
-
Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность) и их связь с логическими операциями.
-
Свойства операций над множествами.
-
Мощность множества. Принцип включения-исключения.
-
Декартово (прямое) произведение множеств. Декартова степень множества.
-
Отношения на множествах. Бинарное отношение.
-
Виды бинарных отношений на множестве (тождественное, обратное, дополнение, универсальное).
-
Свойства бинарных отношений на множестве (рефлексивное, антирефлексивное, симметричное, антисимметричное, транзитивное, полное).
-
Представление отношений в ЭВМ, матрица отношения.
-
Композиция отношений. Степень отношения.
-
Ядро отношения.
-
Функция. Область определения функции. Область значения функции.
-
Свойства функции: инъективность, сюръективность, биективность.
-
Неориентированный граф. Смежность и инцидентность вершин и ребер. Степень вершины. Кратные ребра.
-
Маршруты, цепи, циклы, расстояние между вершинами.
-
Ориентированный граф (орграф). Дуга, контур. Степени входа и выхода вершин.
-
Изоморфизм графов.
-
Плоские графы.
-
Связность графов. Компоненты связности. Мост.
-
Эйлеров граф. Критерий эйлеровости графов.
-
Взвешенный граф. Матрица весов.
-
Гамильтонов граф. Гамильтонов цикл в графе.
-
Полный граф. Свойства полного графа.
-
Операции над графами: объединение, пересечение, кольцевая сумма, дополнение.
-
Задание графа списками вершин, списками ребер.
-
Задание графа матрицей смежности.
-
Задание графа матрицей инцидентности.
-
Подграфы. Остовный и собственный подграфы.
-
Дерево. Свойства дерева.
-
Дерево с корнем. Двоичное дерево.
-
Минимальное остовное дерево. Алгоритм Прима.
-
Минимальное остовное дерево. Жадный алгоритм.
-
Кратчайший путь между вершинами. Алгоритм Дейкстры.
-
Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний.
-
Принцип работы автомата.
-
Таблица автомата.
-
Диаграмма автомата.
-
Словарная функция автомата.
-
Финальная функция автомата.
-
Правильный автомат (автомат Мура). Упрощённый вид диаграммы для правильных автоматов.
Примерные задания
-
Составить таблицу истинности для функции, найти ее СДНФ и СКНФ, минимизировать полученную СДНФ с помощью карт Карно:
-
Составить таблицу истинности для функции, найти ее СДНФ и СКНФ, минимизировать полученную СДНФ с помощью карт Карно:
-
Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.
-
Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.
-
Определить, истинными или ложными являются высказывания
-
,
-
,
-
,
-
,
-
,
построенные из предикатов
P(x): x – положительное число,
Q(x,y): x > y,
R(x,y) : студент x изучает дисциплину y.
-
Q(x,y): студент x учится в колледже y. Запишите на естественном языке высказывания и определите их истинность:
-
,
-
,
-
,
-
,
-
,
-
.
-
По каналу связи передаются 3 сообщения, каждое из которых может быть правильно принято, независимо от других. Формализуйте высказывания (запишите с помощью символики алгебры логики):
-
«все сообщения будут искажены»;
-
«будет искажено только первое сообщение»;
-
«одно сообщение будет искажено»;
-
«хотя бы одно сообщение будет искажено».
-
Участок электрической цепи состоит из четырех элементов, каждый из которых работает независимо от других. Формализуйте высказывание «Участок цепи работает безотказно».
-
Участок электрической цепи состоит из четырех элементов, каждый из которых работает независимо от других. Формализуйте высказывание «Участок цепи вышел из строя».
-
Докажите справедливость законов алгебры логики.
-
Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.
-
Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.
-
Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.
-
Записать предикат с помощью математической символики:
-
Среди чисел а, b, с есть хотя бы одна пара взаимно противоположных.
-
Данные числа х, у являются координатами точки, лежащей в первой координатной четверти.
-
Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).
-
Величина d является корнем только одного из уравнений и .
-
Даны два множества A = , , , B = , , . Что представляет собой множества А\В, А В, АВ, В\А?
-
Найдите (BÈ А)\C, AÇ (B\C), (CÇ А)È B, если , , .
-
Три множества A, В и С изображены кругами Эйлера. Запишите множество, которое соответствует закрашенной области:
a) b)
-
Изобразите множества кругами Эйлера:
-
, если , ,;
-
, если , ,;
-
, если , ,.
-
Из 105 опрошенных человек 38 любят смотреть по телевизору фильмы ужасов, 29 − мелодрамы, 65 − комедии, смотрят фильмы ужасов или мелодрамы − 56, смотрят комедии или мелодрамы − 81, смотрят фильмы ужасов или комедии − 91, не смотрят телевизор вообще 4 человека. Сколько человек смотрят только комедии?
-
На экзамене по дискретной математике из 45 человек группы первое задание выполнили 17 человек, второе – 20, третье – 20, первое и второе – 5, второе и третье – 7, первое и третье – 6, все три – 4. Сколько студентов не выполнили ни одного задания?
-
Определите свойства отношения R, если A –множество всех людей, .
-
Определите свойства отношения R, если A –множество всех людей, .
-
Пусть , , , , , , . Найдите композицию отношений и .
-
Пусть , , . Задайте отношение R перечислением пар, постройте матрицу отношения, изобразите отношение графом. Найдите , ядро отношения Ker R.
-
Пусть , , . По матрице отношения R, запишите отношение R перечислением пар, изобразите отношение графом. Определите свойства отношения.
-
Дан граф:
-
Укажите степени вершин;
-
Найдите расстояния между вершинами и ,
-
Составьте цепь и простую цепь, соединяющие и ;
-
Составьте цикл, содержащий ;
-
Определите вид данного графа (является ли граф связным, ориентированным, эйлеровым, гамильтоновым, полным, деревом);
-
Составьте для него матрицу смежности и матрицу инцидентности.
-
Составьте матрицу смежности и матрицу инцидентности для ориентированного графа:
-
Найдите минимальное остовное дерево графа с помощью алгоритма Прима (Рис 1).
-
Найдите кратчайший маршрут между вершинами А и Л с помощью алгоритма Дейкстры (Рис 1).
-
Найдите минимальное остовное дерево графа с помощью жадного алгоритма (Рис 1).
Преподаватели: Алферьева О.В.
Рис 1