Для группы 31 пи

1. Что называется высказыванием? Перечислите виды логических операций над высказываниями и сформу­лируйте их определение. Приведите примеры высказываний.

2. Какие связки простейшие? Назовите другие связки. Что такое таблица истинности высказывания и как она строится?

3. Какие существуют логические отношения между высказываниями?

Перечислите варианты импликации.

4. Сформулируйте основные законы алгебры высказываний. Как их дока­зать?

5. Что такое булева функция? Как строится таблица истинности для булевых функций?

6. Основные свойства элементарных булевых функций. Приведите примеры.

7. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. (ДНФ и КНФ). Алгоритм построения ДНФ и КНФ.

8. Определение совершенного одночлена. Совершенная дизъюнктивная и совершенная

конъюнктивная нормальные формы. Алгоритм построения СДНФ и СКНФ.

9. Дайте определение многочлена Жегалкина и сформулируйте теорему Жегалкина.

Метод неопределенных коэффициентов для построения многочлена Жегалкина.

10.. Многочлен Жегалкина. Сформулируйте 1-метод построения многочлена Жегалкина.

11.. Многочлен Жегалкина. Сформулируйте 2-метод построения многочлена Жегалкина.

Метод неопределенных коэффициентов.

12. Понятие множества. Основные символы. Обозначение множеств. Способы задания

множества. Что такое подмножество? Универсальное множество. Приведите примеры.

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

14. Что такое диаграмма Эйлера—Венна? Проиллюстрируйте с помощью диаграммы

Эйлера—Венна объединение и пересечение трех множеств.

15. Что называется кортежем. Что такое: декартово произведение множеств. Приведите примеры.

16. Назовите основные свойства бинарных отношений. Какое отношение называется рефлексивным, симметричным, антисимметричным, транзитивным? Какое отношение называется отношением эквивалентности?

17. Отображение множеств. Какие отображения называются сюръективными, инъективными

и биективными? Что такое мощность множества?

18. Понятие функции. Какие функции называются сюръективными, инъективными

и биективными?

19. Понятие сложной функции. Понятие обратной функции.

20. Что такое комбинаторика и для чего она нужна.

21. Что называется перестановкой n-элементного множества;

22 Что называется размещением n-элементного множества;

23 Что называется сочетанием n-элементного множества;

24. Элементы теории графов. Основные понятия. Полный граф. Дополнение графа.

25. Степень вершины графов. Приведите примеры.

26. Путь (маршрут) в графе.

27. Связность графа. Приведите примеры.

28. Циклы. Приведите примеры.

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

30. Операции над графами. Приведите примеры.

32. Способы задания графов. (аналитический, геометрический и матричный).

33. Какие два графа называются изоморфными? Алгоритм изоморфизма двух графов.

34.Типы графов. Эйлеровы графы. Алгоритм построения эйлерова цикла.

35.Типы графов. Гамильтоновы графы.