, вопросы, ДМ)


Вопросы к экзамену по дисциплине: « Дискретная математика»
для группы 31 ПИ
Что называется высказыванием? Перечислите виды логических операций над высказываниями и сформулируйте их определение. Приведите примеры высказываний
Какие связки простейшие? Назовите другие связки. Что такое таблица истинности высказывания и как она строится?
3. Какие существуют логические отношения между высказываниями? Перечислите варианты импликации.
Сформулируйте основные законы алгебры высказываний. Как их доказать?
Что такое булева функция? Как строится таблица истинности для булевых функций?
Основные свойства элементарных булевых функций. Приведите примеры.
Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. (ДНФ и КНФ). Алгоритм построения ДНФ и КНФ.
Определение совершенного одночлена. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. Алгоритм построения СДНФ и СКНФ.
Дайте определение многочлена Жегалкина и сформулируйте теорему Жегалкина. Метод неопределенных коэффициентов для построения многочлена Жегалкина.
Понятие множества. Основные символы. Обозначение множеств. Способы задания множества. Что такое подмножество? Универсальное множество. Приведите примеры.
Основные операции над множествами. Приведите примеры.
Что такое диаграмма Эйлера—Венна? Проиллюстрируйте с помощью диаграммы Эйлера—Венна объединение и пересечение трех множеств.
Что называется кортежем. Что такое: декартово произведение множеств. Приведите примеры.
Назовите основные свойства бинарных отношений. Какое отношение называется рефлексивным, симметричным, антисимметричным, транзитивным? Какое отношение называется отношением эквивалентности?
Отображение множеств. Какие отображения называются сюръективными, инъективными и биективными? Что такое мощность множества?
Понятие функции. Какие функции называются сюръективными, инъективными и биективными?
Понятие сложной функции. Понятие обратной функции.
Элементы теории графов. Основные понятия. Полный граф. Дополнение графа.
Степень вершины графов. Приведите примеры.
Путь (маршрут) в графе.
Связность графа. Приведите примеры.
Циклы. Приведите примеры.
Ориентированные графы. Основные понятия.
Операции над графами. Приведите примеры.
Способы задания графов. (аналитический, геометрический и матричный).
Какие два графа называются изоморфными? Алгоритм изоморфизма двух графов.
Типы графов. Эйлеровы графы. Алгоритм построения эйлерова цикла.
Типы графов. Гамильтоновы графы.
Что такое комбинаторика и для чего она нужна.
Что называется перестановкой n-элементного множества.
Что называется размещением n-элементного множества.
Что называется сочетанием n-элементного множества
Многочлен Жегалкина. Сформулируйте 1-метод построения многочлена Жегалкина.
Многочлен Жегалкина. Сформулируйте 2-метод построения многочлена Жегалкина. Метод неопределенных коэффициентов.
Коммутационные схемы.
Практические задания к экзаменационным билетам
Найдите среди указанных ниже предложений высказывания. Укажите их истинностные значения.
а) Который час?
б) Целое число 1 есть наименьшее положительное целое число.
в) Если х = 3, то 2х = 6.
г) Берегись автомобиля!
д) город Сочи — Столица летней олимпиады 2015г.
Постройте коммутационные схемы, соответствующие булевым выражениям: (q(r + s))((p'q') + (qr')).
Пусть р, q и г обозначают следующие высказывания:
р : Путешествие на Марс является дорогостоящим,
q : Я совершу путешествие на Марс,
г : У меня есть деньги.
Запишите в символической форме такие высказывания:
а) У меня нет денег и я не совершу путешествие на Марс.
б) У меня нет денег и путешествие на Марс является дорогостоящим или я совершу путешествие на Марс.
Вычислите: А) 6! + 7!; Б) в)
Пусть дано высказывание-импликация:«Если он играет в футбол, то он популярен».
Для этой импликации напишите:
А) конверсию: Б) инверсию: В) контрапозицию:
Опишите множества, соответствующие закрашенной части диаграммы Венна (рис):

С помощью таблиц истинности проверьте, являются ли эквивалентными высказывания:

Опишите множества, соответствующие закрашенной части диаграммы Венна (рис):

Докажите эквивалентность функций:

Изобразите орграф, у которого V = {а, 6, с} и Е = {(а, 6), (Ь, с), (с, 6), (с, а)}.
Докажите тождественную истинность формулы:
Постройте многочлен Жегалкина 1-м методом для функции f = 01001000;
Для функции : Постройте конъюнктивную нормальную форму (КНФ) и сделайте проверку.
Используйте диаграммы Венна для двух множеств и заштрихуйте те ее части, которые изображают заданные множества:
Найдите СДНФ и СКНФ функции f (х1, х2, х3), заданной следующей таблицей истинности:
х1х2х3 f (х1, х2, х3)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Задача: Сколькими способами можно изготовить трёхцветный флаг с горизонтальными полосами, если есть материал 7 разных цветов?
Постройте многочлен Жегалкина для функции f = 0101;
Приведите булево выражение, соответствующее коммутационной схеме (рис1.):
Для каких из следующих пар множеств имеет место одно из соотношений.


2)
3)
Изобразите орграф, у которого
V = {а, 6, с, в] и Е = {(а, Ь), (Ь, с), (с, с), F, d), (d,b),(c,d),(d,a)};
Даны множества: А ={1, 2, 3, 7, 11}; B = {-3, 0, 3, 12} Определите множества: а) б) с)
Постройте многочлен Жегалкина 2-м методом ( метод неопределенных коэффициентов) для функции f = 0100
С помощью диаграммы Эйлера – Венна определите множество:
Упростите следующие формулы с помощью законов поглощения: X(XvY)(XvZ);
Из множеств {a, b, c} и { 1, 2} составьте кортежи.
Решите уравнение: Ax2 = 182;
Дано множество А = { 1, 2, 3 }. Напишите декартово произведение этого множества А х А.
Из полученного множества составьте бинарное отношение R, которое будет считаться
А) Рефлексивным; Б) Иррефлексивным; В) Симметричным;
С) Антисимметричным; Д) Транзитивным.
Постройте коммутационную схему, соответствующую данному булевому выражению. (q(r + s))((p'q') + (qr'));
Является ли отношение определенное на декартовом произведении множеств и функцией? Если да, то будет ли данная функция сюръекцией, инъекцией ?Дана матрица: , постройте орграф, для которого данная матрица является
матрицей смежности.
Какая из заданных функций являются инективными; сюръективными; биективными:
1) 2)
3)
Упростите следующие формулы с помощью законов склеивания:
Дано: f(x) = x2 + 1; g(x) = x + 3; Составьте обратную функцию функции: y = x3 + 6;
Опишите множества, соответствующие закрашенной части диаграммы Венна (рис):
Постройте полный граф с n-вершинами, если А) n=2; B) n=3; C) n=5.
Решите уравнение: Ax-22 + Cxx-2 = 101;
Перепишите следующие высказывания в обозначениях булевой алгебры:

39. Изобразите граф у которого V = { a,b,c,d,e} и E = {(a,b); (a,e); (b,e); (b,d); (b,c); (c,d)}
40. Пусть р, q и г обозначают следующие высказывания:
р : Мой компьютер — быстродействующий,
q : Я окончу проект вовремя,
г : Я сдам экзамен.
Запишите в символической форме такие высказывания:
а) У меня не быстродействующий компьютер или я закончу проект во-
время.
б) Я не закончу проект вовремя и не сдам экзамен.
в) Неверно, что я закончу проект и сдам экзамен.
г) У меня быстродействующий компьютер или я не закончу проект вовремя и сдам экзамен.
41. составьте таблицу истинности для выражения:
42. Постройте графы Содержащие а) 4 ребра; б) 6 – ребер; в) 5 – ребер; г) 10 – ребер.
43. Решите уравнение: Cxx-2 = 45;
44. В графе (рис.)
Определите степень входа и степень выхода каждой вершины.
Найдите источник, сток.
Определите число путей от V5 до V2.
Назовите вершину, которая не достижима ни из одной вершины графа
45. Упростите формулу с помощью законов логики:
46. Докажите тождественную истинность формулы:
47. Дана матрица: , постройте орграф, для которого данная матрица является
матрицей смежности.
48. Используйте диаграммы Венна для двух множеств и заштрихуйте те ее части, которые изображают заданные множества:

49. Пусть даны графы G1 (X, E ); G2 ( Y, E ) Установите, изоморфны ли данные графы (рис.)
50. Пусть р, q и г обозначают следующие высказывания:
р : Эта игра очень трудна,
q : Я играю в шахматы,
г : Игра в шахматы требует времени.
Интерпретируйте следующие выражения как обычные высказывания:
а) q /\ r; б) ~p V ~r; в) (p V r) /\ q; г) p /\ q /\ r;
51. Составьте СДНФ к
52. Вычислите: а) ; б) ; с) ;
53. Составьте таблицу истинности для формулы:
54. Вычислите: а) ; б) ; с) ;
55. Нарисуйте граф с пятью вершинами, который не является связным.
56. Сколькими способами можно составить список из 5 учеников?
57. Составьте СКНФ к
58. Сколько различных трёхзначных чисел можно составить из цифр 1,2,3,4,5,6, если цифры не повторяются.
59. Пусть A = {1,2,3}, и B = {x, y}
Напишите все элементы декартова произведения A x B; B x A и B x B;
60. Сколькими способами можно выбрать двух дежурных из 25 учащихся класса?
61. Составьте таблицу истинности для формулы:
62. Постройте многочлен Жегалкина 1-методом для функции f = 11010000
63. Постройте многочлен Жегалкина 2-м методом (Метод неопределенных коэффициентов) для функции f = 11010000
64. Нарисуйте граф с пятью вершинами, который не является связным
65. Студентам дали список из 10 книг, которые рекомендуют прочитать на каникулах. Сколькими способами можно выбрать 6 из них?
Разработано преподавателем
А.В. Дерябина

Приложенные файлы

  • docx 8884999
    Размер файла: 166 kB Загрузок: 0

Добавить комментарий