13. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
14. Сумма степеней всех вершин графа G(V,X) равна 42. Найдите количество рёбёр данного графа.
15. Дана булева функцияf (x1, x2, x3)=(01100110). Необходимо:
- представить данную булеву функцию тремя способами: аналитически, геометрически, с помощью таблицы истинности.
- определить существенность и фиктивность переменных в булевой
функции.
-представить данную булеву функцию в виде СДНФ и СКНФ с
помощью таблицы истинности.
16. Определите следующие логические законы:
1)а в в а
2) а(вс)=(ав)с
3)
17. В классе 40 человек. Играют в баскетбол 26 человек, занимаются плаванием 25, ходят на лыжах 27. Одновременно занимаются плаванием и баскетболом 15, баскетболом и лыжами 16, плаванием и лыжами 18 человек. Один из учащихся освобождён от занятий по физкультуре. Сколько человек занимается всеми указанными видами спорта?
18. Какой булевой функции соответствует геометрическая интерпретация?
i.
19. Проверить принадлежность к классам S0, S1, S, L, M функцию
20. Какой булевой функции соответствует геометрическая интерпретация?
21. Зашифруйте, используя теорию вычетов, сообщение «САВА»
22. Переведите в символическую форму следующее сложное высказывание:
«Если ваза упадёт, то она разобьется. Ваза разбита, значит, она упала»
23. Какой вид имеет логическая функция F( )=( )
24. Составить предикат функционального отношения:
при х=2 у=5;
при х=3 у=10;
при х=4 у=17.
25. С помощью таблиц истинности проверьте эквивалентность формул
26. Определите логические операции и оформите таблицу истинности для
данных логических операций:
а)
б)
в)
г)
27. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
28. Определите логические операции и оформите таблицу истинности для данных логических операций:
а)
б)
29. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
30. Сколькими способами могут встать в очередь в билетную кассу 5 человек?
31. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью треугольника Паскаля.
32. Проверить является ли формула суммой ряда (Метод математической индукции)
33. Дана подстановка = 1 5 2 4 3 . Найти
4 3 2 1 5
34. Доказать, что справедливо равенство: (Метод математической индукции)
35. Какой вид имеет логическая функция F( )=
36. Даны два множества А={-2, -4, -6, -8, 2, 4, 6, 8} и
38. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью метода неопределенных
коэффициентов.
39. Даны два высказывания: А – спортсмен участвовал в авторалли; В – спортсмен разбил машину. Дайте словесную формулировку высказываний, соответствующих следующим логическим операциям:
а)
б)
40. Перейти от ДНФ к КНФ:
41. Из 110 студентов английский изучают 44 человека, немецкий-50 человек, французский-49, английский и немецкий-13, английский и французский-14, немецкий и французский-12, Все три языка изучают 5 учащихся. Сколько студентов изучают только один язык?
42. Определите логические операции и оформите таблицу истинности для данных логических операций:
а) │Y
б)
43. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00111110) с помощью треугольника Паскаля.
44. Переведите в символическую форму следующее сложное высказывание: «Этот человек или джентльмен, или студент. Но он не джентльмен, значит, он студент».
45. Проверить принадлежность к классам S0, S1, S, L и М следующие
функции: = , =
С помощью теоремы Поста проверить полноту системы .
46. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00111110) с помощью треугольника Паскаля
47. Дана подстановка = 1 5 3 4 2 . Найти
4 3 2 1 5
48. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00010011) с помощью метода неопределенных
коэффициентов.
49. Найдите множество .
50. Проверить принадлежность к классам S0, S1, S, L и М следующие функции: = , =
С помощью теоремы Поста проверить полноту системы
51. Перейти от КНФ к ДНФ
52. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
53. Зашифруйте, используя теорию вычетов, сообщение «БЕДА»
54. Какой вид имеет логическая функция F( )=
Рассмотрено
на заседании ПЦК
Протокол №_____
от «____»_________ 20 __ г.
Председатель ПЦК
УТВЕРЖДАЮ
Зам. директора по реализации программ СПО
«____»_________ 20 __ г.
___________ О.К. Лозбенева
___________
Билеты к дифференцированному зачёту
по дисциплине «Дискретная математика»
специальность 230105.51 Программное обеспечение ВТ и АС
для студентов III курса 832 группы
Билет № 1
Логические операции. Формулы логики.
Найдите множество .
Дана булева функцияf (x1, x2, x3)=(10001010). Представьте данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.
Билет № 2
Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.
Дана подстановка = 1 5 3 4 2 . Найти
4 3 2 1 5
Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если
Билет № 3
Булевы функции. Способы задания булевых функций.
Определите следующие логические законы:
1) ав=ва;
2) ;
3)
3. Зашифруйте, используя теорию вычетов, сообщение «ДЕВА»
Билет № 4
Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)
Ориентированный граф. Основные понятия.
С помощью таблиц истинности проверьте эквивалентность формул и
Билет № 5
Совершенные дизъюнктивные нормальные формы (СДНФ).
Найдите множество .
Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа.
Билет № 6
Представление булевых функций в виде СДНФ.
Количество рёбёр графа G(V,X) равно 24. Найдите сумму степеней всех вершин графа.
Даны два множества А={4, 3, 6, 9, 11, 13, 15, 17} и
1. Операция двоичного сложения. Многочлен Жегалкина.
2. Найдите множество .
3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
Билет № 8
Понятие множества. Основные операции над множествами.
Сумма степеней всех вершин графа G(V,X) равна 42. Найдите количество рёбёр данного графа.
Дана булева функцияf (x1, x2, x3)=(01100110).
Необходимо:
· Представить данную булеву функцию тремя способами: аналитически, геометрически, с помощью таблицы истинности.
· Определить существенность и фиктивность переменных в булевой функции.
· Представить данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.
Билет № 9
1. Предикаты. Основные понятия.
Определите следующие логические законы:
1)а в в а
2) а(вс)=(ав)с
3)
В классе 40 человек. Играют в баскетбол 26 человек, занимаются плаванием 25, ходят на лыжах 27. Одновременно занимаются плаванием и баскетболом 15, баскетболом и лыжами 16, плаванием и лыжами 18 человек. Один из учащихся освобождён от занятий по физкультуре. Сколько человек занимается всеми указанными видами спорта?
Билет № 10
Логические и кванторные операции над предикатами.
Какой булевой функции соответствует геометрическая интерпретация?
Проверить принадлежность к классам S0, S1, S, L, M
функцию
Билет № 11
1. Бинарные отношения. Основные понятия. Примеры.
2. Какой булевой функции соответствует геометрическая интерпретация?
3. Зашифруйте, используя теорию вычетов, сообщение «САВА»
Билет № 12
1. Теория отображений. Основные понятия.
2. Переведите в символическую форму следующее сложное высказывание:
«Если ваза упадёт, то она разобьется. Ваза разбита, значит, она упала»
3. С помощью таблиц истинности проверьте эквивалентность формул
Билет № 13
1. Алгебра подстановок. Основные понятия, свойства.
2. Какой вид имеет логическая функция F( )=( )
3. Составить предикат функционального отношения:
при х=2 у=5;
при х=3 у=10;
при х=4 у=17.
Билет № 14
1. Основы алгебры вычетов.
2. Определите логические операции и оформите таблицу истинности для данных логических операций:
а) ; б)
в) ; г)
3. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
Билет № 15
1. Простейшие криптографические шифры.
2. Определите логические операции и оформите таблицу истинности для данных логических операций:
а)
б)
3. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
Билет № 16
Метод математической индукции.
Сколькими способами могут встать в очередь в билетную кассу 5 человек?
Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью треугольника Паскаля.
Билет № 17
1. Сочетание, размещение, перестановки.
2. Базовые множества и принцип работы автоматов.
3. Проверить является ли формула суммой ряда (Метод математической индукции)
Билет № 18
1. Метод включений и исключений
2. Дана подстановка = 1 5 2 4 3 . Найти
4 3 2 1 5
3. Доказать, что справедливо равенство: (Метод математической индукции)
Билет № 19
1. Неориентированный граф. Способы задания. Теорема о сумме степеней вершин
2. Какой вид имеет логическая функция F( )=
3. Даны два множества А={-2, -4, -6, -8, 2, 4, 6, 8} и
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью метода неопределенных
коэффициентов.
Билет № 21
1. Гамильтоновы графы. Плоские графы.
2. Какой вид имеет логическая функция F( )=
3. Даны два высказывания: А – спортсмен участвовал в авторалли; В – спортсмен разбил машину. Дайте словесную формулировку высказываний, соответствующих следующим логическим операциям:
а)
б)
Билет № 22
1. Ориентированный граф. Способы задания.
2. Перейти от ДНФ к КНФ:
3. Из110 студентов английский изучают 44 человека, немецкий-50 человек, французский-49, английский и немецкий-13, английский и французский-14, немецкий и французский-12, Все три языка изучают 5 учащихся. Сколько студентов изучают только один язык?
Билет № 23
1. Представление булевых функций в виде СКНФ.
2. Определите логические операции и оформите таблицу истинности для данных логических операций:
а) │Y
б)
3. Проверить принадлежность к классам S0, S1, S, L и М следующие
функции:
= , =
С помощью теоремы Поста проверить полноту системы .
Билет № 24
1. Правильный автомат (автомат Мура).
2. Переведите в символическую форму следующее сложное высказывание:
«Этот человек или джентльмен, или студент. Но он не джентльмен,
значит, он студент.»
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00111110) с помощью треугольника Паскаля.
Билет № 25
1. Алгоритм фронта волны в графе. Расстояние между вершинами в графе.
2. Дана подстановка = 1 5 3 4 2 . Найти
4 3 2 1 5
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00010011) с помощью метода неопределенных
коэффициентов.
Билет № 26
1. Булев вектор. Единичный N-мерный куб.
2. Найдите множество .
3. Проверить принадлежность к классам S0, S1, S, L и М следующие функции:
= , =
С помощью теоремы Поста проверить полноту системы .
Билет № 27
1. Полнота и замыкание множества функций. Классы Поста. Теорема Поста. Шефферовские функции.
2. Перейти от КНФ к ДНФ
3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
Билет № 28
1. Совершенные конъюнктивные нормальные формы (СКНФ).
2. Бином Ньютона и полиномиальная формула.
3. Зашифруйте, используя теорию вычетов, сообщение «БЕДА»
Билет № 1
Логические операции. Формулы логики.
Найдите множество .
Дана булева функцияf (x1, x2, x3)=(10001010). Представьте данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.
Преподаватель _______________
Билет № 2
Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.
Дана подстановка = 1 5 3 4 2 . Найти
4 3 2 1 5
Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если
Преподаватель _______________
Билет № 3
Булевы функции. Способы задания булевых функций.
Определите следующие логические законы:
1) ав=ва;
2) ;
3)
3. Зашифруйте, используя теорию вычетов, сообщение «ДЕВА»
Преподаватель _______________
Билет № 4
1. Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)
2. Ориентированный граф. Основные понятия.
3. С помощью таблиц истинности проверьте эквивалентность формул и
Преподаватель _______________
Билет № 5
1. Совершенные дизъюнктивные нормальные формы (СДНФ).
2. Найдите множество .
3. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа.
Преподаватель _______________
Билет № 6
Представление булевых функций в виде СДНФ.
Количество рёбёр графа G(V,X) равно 24. Найдите сумму степеней всех вершин графа.
Даны два множества А={4, 3, 6, 9, 11, 13, 15, 17} и
Билет № 7
1. Операция двоичного сложения. Многочлен Жегалкина.
2. Найдите множество .
3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
Преподаватель _______________
Билет № 8
Понятие множества. Основные операции над множествами.
Сумма степеней всех вершин графа G(V,X) равна 42. Найдите количество рёбёр данного графа.
Дана булева функцияf (x1, x2, x3)=(01100110).
Необходимо:
· Представить данную булеву функцию тремя способами: аналитически, геометрически, с помощью таблицы истинности.
· Определить существенность и фиктивность переменных в булевой функции.
· Представить данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.
Преподаватель _______________
Билет № 9
1. Предикаты. Основные понятия.
Определите следующие логические законы:
1)а в в а
2) а(вс)=(ав)с
3)
В классе 40 человек. Играют в баскетбол 26 человек, занимаются плаванием 25, ходят на лыжах 27. Одновременно занимаются плаванием и баскетболом 15, баскетболом и лыжами 16, плаванием и лыжами 18 человек. Один из учащихся освобождён от занятий по физкультуре. Сколько человек занимается всеми указанными видами спорта?
Преподаватель _______________
Билет № 10
Логические и кванторные операции над предикатами.
Какой булевой функции соответствует геометрическая интерпретация?
Проверить принадлежность к классам S0, S1, S, L, M
функцию
Преподаватель _______________
Билет № 11
1. Бинарные отношения. Основные понятия. Примеры.
2. Какой булевой функции соответствует геометрическая интерпретация?
3. Зашифруйте, используя теорию вычетов, сообщение «САВА»
Преподаватель _______________
Билет № 12
1. Теория отображений. Основные понятия.
2. Переведите в символическую форму следующее сложное высказывание:
«Если ваза упадёт, то она разобьется. Ваза разбита, значит, она упала»
3. С помощью таблиц истинности проверьте эквивалентность формул
Преподаватель _______________
Билет № 13
1. Алгебра подстановок. Основные понятия, свойства.
2. Какой вид имеет логическая функция F( )=( )
3. Составить предикат функционального отношения:
при х=2 у=5;
при х=3 у=10;
при х=4 у=17.
Преподаватель _______________
Билет № 14
1. Основы алгебры вычетов.
2. Определите логические операции и оформите таблицу истинности для данных логических операций: а) ; б) ; в) ; г)
3. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
Преподаватель _______________
Билет № 15
1. Простейшие криптографические шифры.
2. Определите логические операции и оформите таблицу истинности для данных логических операций: а) ; б)
3. Граф G задан диаграммой. Составьте для него матрицу смежности,
постройте матрицу инцидентности, укажите степени вершин графа.
Преподаватель _______________
Билет № 16
Метод математической индукции.
Сколькими способами могут встать в очередь в билетную кассу 5 человек?
Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью треугольника Паскаля.
Преподаватель _______________
Билет № 17
1. Сочетание, размещение, перестановки.
2. Базовые множества и принцип работы автоматов.
3. Проверить является ли формула суммой ряда (Метод математической индукции)
Преподаватель _______________
Билет № 18
1. Метод включений и исключений
2. Дана подстановка = 1 5 2 4 3 . Найти
4 3 2 1 5
3. Доказать, что справедливо равенство: (Метод математической индукции)
Преподаватель _______________
Билет № 19
1. Неориентированный граф. Способы задания. Теорема о сумме степеней вершин
2. Какой вид имеет логическая функция F( )=
3. Даны два множества А={-2, -4, -6, -8, 2, 4, 6, 8} и
В={-3, -4, 1, 2, 6, 15, 16, 20}. Найдите следующие множества:
, , А\В, В\А, А∆В.
Преподаватель _______________
Билет № 20
1. Двудольные графы. Изоморфные графы. Эйлеровы графы.
2. Дана подстановка = 1 3 4 5 2 . Найти
4 3 2 1 5
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(01110011) с помощью метода неопределенных
коэффициентов.
Преподаватель _______________
Билет № 21
1. Гамильтоновы графы. Плоские графы.
2. Какой вид имеет логическая функция F( )=
3. Даны два высказывания: А – спортсмен участвовал в авторалли; В – спортсмен разбил машину. Дайте словесную формулировку высказываний, соответствующих следующим логическим операциям:
а)
б)
Преподаватель _______________
Билет № 22
1. Ориентированный граф. Способы задания.
2. Перейти от ДНФ к КНФ:
3. Из110 студентов английский изучают 44 человека, немецкий-50 человек, французский-49, английский и немецкий-13, английский и французский-14, немецкий и французский-12, Все три языка изучают 5 учащихся. Сколько студентов изучают только один язык?
Преподаватель _______________
Билет № 23
1. Представление булевых функций в виде СКНФ.
2. Определите логические операции и оформите таблицу истинности для данных логических операций:
а) │Y
б)
3. Проверить принадлежность к классам S0, S1, S, L и М следующие
функции:
= , =
С помощью теоремы Поста проверить полноту системы .
Преподаватель _______________
Билет № 24
1. Правильный автомат (автомат Мура).
2. Переведите в символическую форму следующее сложное высказывание:
«Этот человек или джентльмен, или студент. Но он не джентльмен,
значит, он студент.»
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00111110) с помощью треугольника Паскаля.
Преподаватель _______________
Билет № 25
1. Алгоритм фронта волны в графе. Расстояние между вершинами в графе.
2. Дана подстановка = 1 5 3 4 2 . Найти
4 3 2 1 5
3. Построить полином Жигалкина для функции от трёх переменных
f (x1, x2, x3)=(00010011) с помощью метода неопределенных
коэффициентов.
Преподаватель _______________
Билет № 26
1. Булев вектор. Единичный N-мерный куб.
2. Найдите множество .
3. Проверить принадлежность к классам S0, S1, S, L и М следующие функции:
= , =
С помощью теоремы Поста проверить полноту системы .
Преподаватель _______________
Билет № 27
1. Полнота и замыкание множества функций. Классы Поста. Теорема Поста. Шефферовские функции.
2. Перейти от КНФ к ДНФ
3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму
этого графа, если
Преподаватель _______________
Билет № 28
1. Совершенные конъюнктивные нормальные формы (СКНФ).
2. Бином Ньютона и полиномиальная формула.
3. Зашифруйте, используя теорию вычетов, сообщение «БЕДА»
Преподаватель _______________
_______________
______
Билет № 28
4. Совершенные конъюнктивные нормальные формы (СКНФ).
5. Бином Ньютона и полиномиальная формула.
6. Зашифруйте, используя теорию вычетов, сообщение «БЕДА»
. 
Дана подстановка 
= 1 5 3 4 2 . Найти 
;
и 
.
, 
, А\В, В\А, А∆В.
.
в 
в 
)=( 
) 
суммой ряда 
(Метод математической индукции)
справедливо равенство: 
(Метод математической индукции)
Дана подстановка 
│Y
= 
, 
= 
.
f (x1, x2, x3)=(00111110) с помощью треугольника Паскаля
.
, 
Преподаватель _______________
3. Зашифруйте, используя теорию вычетов, сообщение «САВА»
Преподаватель _______________
Преподаватель _______________