Государственное бюджетное образовательное учреждение

среднего профессионального образования

Сергиевский губернский техникум

Рассмотрено на заседании ПЦК

Протокол №_____

от «____»_________ 20 __ г.

Председатель ПЦК_________

УТВЕРЖДАЮ

Зам. директора по реализации программ СПО

«____»_________ 20 __ г.

___________ О.К. Лозбенева

Дифференцированный зачёт

по дисциплине «Дискретная математика»

специальности 230105.51 Программное обеспечение ВТ и АС

Сергиевск

2012

Рассмотрено

на заседании ПЦК

Протокол №_____

от «____»_________ 20 __ г.

Председатель ПЦК

_

__________

______________________

Вопросы

Дифференцированного зачёта

по дисциплине «Дискретная математика»

специальность 230105.51 Программное обеспечение ВТ и АС

для студентов III курса 832 группы

Теоретическая часть

1. Логические операции. Формулы логики.

2. Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.

3. Булевы функции. Способы задания булевых функций.

4. Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ

5. Ориентированный граф. Основные понятия.

6. Совершенные дизъюнктивные нормальные формы (СДНФ).

7. Представление булевых функций в виде СДНФ.

8. Операция двоичного сложения. Многочлен Жегалкина.

9. Понятие множества. Основные операции над множествами.

10. Предикаты. Основные понятия.

11. Логические и кванторные операции над предикатами.

12. Бинарные отношения. Основные понятия. Примеры.

13. Теория отображений. Основные понятия.

14. Алгебра подстановок. Основные понятия, свойства.

15. Основы алгебры вычетов.

16. Простейшие криптографические шифры.

17. Метод математической индукции.

18. Сочетание, размещение, перестановки.

19. Базовые множества и принцип работы автоматов.

20. Метод включений и исключений

21. Неориентированный граф. Способы задания. Теорема о сумме степеней вершин

22. Двудольные графы. Изоморфные графы. Эйлеровы графы.

23. Гамильтоновы графы. Плоские графы.

24. Ориентированный граф. Способы задания.

25. Представление булевых функций в виде СКНФ.

26. Правильный автомат (автомат Мура).

27. Алгоритм фронта волны в графе. Расстояние между вершинами в графе.

28. Булев вектор. Единичный N-мерный куб.

29. Полнота и замыкание множества функций. Классы Поста. Теорема Поста. Шефферовские функции Совершенные конъюнктивные нормальные формы (СКНФ).

30. Бином Ньютона и полиномиальная формула.

Практическая часть

1. Найдите множество .

2. Дана булева функция f (x₁, x₂, x₃)=(10001010). Представьте данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.

3. Д ана подстановка = 1 5 3 4 2 . Найти

4 3 2 1 5

4. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

5. Определите следующие логические законы:

1)ав=ва;

2) ;

3)

6. Зашифруйте, используя теорию вычетов, сообщение «ДЕВА»

7. С помощью таблиц истинности проверьте эквивалентность формул и

8. Найдите множество .

9. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа.

6. Количество рёбёр графа G(V,X) равно 24. Найдите сумму степеней всех вершин графа.

6. Даны два множества А={4, 3, 6, 9, 11, 13, 15, 17} и

В={0, -5, 9, 12, 13, 21, 30, 34}. Найдите следующие множества:

, , А\В, В\А, А∆В.

6. Найдите множество .

7. Пусть граф G задан матрицей инцидентности В. Построить диаграмму

этого графа, если

6. Сумма степеней всех вершин графа G(V,X) равна 42. Найдите количество рёбёр данного графа.

7. Дана булева функция f (x₁, x₂, x₃)=(01100110). Необходимо:

- представить данную булеву функцию тремя способами: аналитически, геометрически, с помощью таблицы истинности.

- определить существенность и фиктивность переменных в булевой

функции.

-представить данную булеву функцию в виде СДНФ и СКНФ с

помощью таблицы истинности.

6. Определите следующие логические законы:

1)а в в а

2) а(вс)=(ав)с

3)

6. В классе 40 человек. Играют в баскетбол 26 человек, занимаются плаванием 25, ходят на лыжах 27. Одновременно занимаются плаванием и баскетболом 15, баскетболом и лыжами 16, плаванием и лыжами 18 человек. Один из учащихся освобождён от занятий по физкультуре. Сколько человек занимается всеми указанными видами спорта?

7. Какой булевой функции соответствует геометрическая интерпретация?

   1. 

8. Проверить принадлежность к классам S₀, S₁, S, L, M функцию

9. Какой булевой функции соответствует геометрическая интерпретация?

6. Зашифруйте, используя теорию вычетов, сообщение «САВА»

6. Переведите в символическую форму следующее сложное высказывание:

«Если ваза упадёт, то она разобьется. Ваза разбита, значит, она упала»

6. Какой вид имеет логическая функция F( )=( )

7. Составить предикат функционального отношения:

при х=2 у=5;

при х=3 у=10;

при х=4 у=17.

6. С помощью таблиц истинности проверьте эквивалентность формул

6. Определите логические операции и оформите таблицу истинности для

данных логических операций:

а)

б)

в)

г)

6. Граф G задан диаграммой. Составьте для него матрицу смежности,

постройте матрицу инцидентности, укажите степени вершин графа.

6. Определите логические операции и оформите таблицу истинности для данных логических операций:

а)

б)

6. Граф G задан диаграммой. Составьте для него матрицу смежности,

постройте матрицу инцидентности, укажите степени вершин графа.

6. Сколькими способами могут встать в очередь в билетную кассу 5 человек?

7. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(01110011) с помощью треугольника Паскаля.

6. Проверить является ли формула суммой ряда (Метод математической индукции)

7. Д ана подстановка = 1 5 2 4 3 . Найти

4 3 2 1 5

6. Доказать, что справедливо равенство: (Метод математической индукции)

7. Какой вид имеет логическая функция F( )=

8. Даны два множества А={-2, -4, -6, -8, 2, 4, 6, 8} и

В={-3, -4, 1, 2, 6, 15, 16, 20}. Найдите следующие множества:

, , А\В, В\А, А∆В.

6. Д ана подстановка = 1 3 4 5 2 . Найти

4 3 2 1 5

6. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(01110011) с помощью метода неопределенных

коэффициентов.

6. Даны два высказывания: А – спортсмен участвовал в авторалли; В – спортсмен разбил машину. Дайте словесную формулировку высказываний, соответствующих следующим логическим операциям:

а)

б)

6. Перейти от ДНФ к КНФ:

7. Из 110 студентов английский изучают 44 человека, немецкий-50 человек, французский-49, английский и немецкий-13, английский и французский-14, немецкий и французский-12, Все три языка изучают 5 учащихся. Сколько студентов изучают только один язык?

8. Определите логические операции и оформите таблицу истинности для данных логических операций:

а) │Y

б)

6. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(00111110) с помощью треугольника Паскаля.

6. Переведите в символическую форму следующее сложное высказывание: «Этот человек или джентльмен, или студент. Но он не джентльмен, значит, он студент».

7. Проверить принадлежность к классам S₀, S₁, S, L и М следующие

функции: = , =

С помощью теоремы Поста проверить полноту системы .

6. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(00111110) с помощью треугольника Паскаля

6. Д ана подстановка = 1 5 3 4 2 . Найти

4 3 2 1 5

6. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(00010011) с помощью метода неопределенных

коэффициентов.