Контрольная работа №2

1. Определить истинность или ложность высказываний:

_,

,

_;

решить задачи 1, 2.

1. Определить истинность или ложность предложений

xÙy, yÙz, yÚx, xÚz, xÙ , .

2. Определить логическое значение формул

а) ((хÚу)Ùz)º((хÙz)Ú(yÙz));

в) (х®у)Ù(х®z) ®(x®yÙz).

2. Для произвольных высказываний () построить таблицу истинности для формул:

1) ® ; 2) .

3. Даны предикаты Р(х): “х – нечетное число” и Q(х): “х – делится на 10”. Найти область истинности предикатов Р(х)ÚQ(х) и Р(х)®Q(х), если исходные предикаты определены на множестве N.

4. Вычислить:

а) ;

в) .

5. В учебной группе студентов. Сколькими способами их можно разбить на бригады по Р₁ человек?

6. В оперативной группе имеется Р₁+Р₂+Р₃ солдат и 4 офицера. Сколькими способами можно назначить наряд, состоящий из 3 солдат и 1 офицера?

7. Сколькими способами можно составить (Р₁+Р₂) – значное число, в состав

которого входят две двойки и три шестерки?

8. На иномарке, скрывшейся с места ДТП, был Р₁ – значный номер, в котором имелось три четверки, а остальные цифры не повторялись. Сколько номеров необходимо проверить по картотеке ГИБДД, чтобы найти нарушителя?

9. Сколькими способами можно составить шеренгу из Р₁ рядовых, Р₂ лейтенантов и Р₃ прапорщиков?

10. Доказать, что формула тождественно равна 0 или 1.

11. Доказать, что формула тождественно равна 0 или 1.

12. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

13. Упростить формулу.

14. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

15. Упростить формулу.

16. В расположении командующего армией имеется Р₂ родов войск. Сколькими способами можно составить Р₃ соединений для проведения войсковой операции?

17. Сколькими способами можно упаковать (Р₁+Р₂+Р₃) различных книг в три ящика соответственно по Р₁, Р₂, Р₃ книги в каждом ящике?

18. Составить матрицы инцидентности, смежности и список ребер для графов:

1)

ВОПРОСЫ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ

(Дискретная математика)

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. Полиномиальная формула. Бином Ньютона. Свойства.

29. Определение графа. Виды. Свойства.

30. Способы задания графов.

31. Построение матрицы инцидентности, матрицы смежности и списка ребер.

32. Применение алгоритма Дейкстры.

33. Задача коммивояжера.

Литература

Теория множеств:

1. Александров П.С. Введение в общую теорию множеств, огл 3, гостех издат, 1948.

2. Фор Р., Кофман А., Дени-Папен М., Современная математика, Мир, М, 1966.

3. Портер У. Современные основания общей теории систем.

4. Нефедов В.Н., Осипова В.А., Курс дискретной математики, 1992.

Элементы математической логики:

1. Эдельман С. Л. Математическая логика. М.: Высшая школа, 1975.

2. Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. М.: Изд- во МГУ, 1982.

3. Нефедов В.Н., Осипова В. А. Курс дискретной математики. М.: Изд-во МАИ, 1992.

4. Новиков П. С. Элементы математической логики. М.: Наука, 1973.

Теория графов:

1. Москинова Г.И. Дискретная математика. М.: Логос. 2002.

2. О. Оре. Графы и их применение. М.: Мир. 1965.

3. К. Берж. Теория графов и ее применение. М.: Ин. литер. 1962.

4. Новиков Ф.А. Дискретная математика (для программистов). М.: Питер. 2000.

Не нашли, что искали? Воспользуйтесь поиском: