asyan.org
добавить свой файл
1

Питання до колоквіуму з курсу «Основи дискретної математики»


Питання можна знайти за адресою http://math.ukrweb.net/ODM_coloq.doc

  1. Числення висловлювань. Операції над висловлюваннями. Синтаксис та семантика числення висловлювань. Поняття тавтології (тотожно-істинної), тотожно-хибної, виконливої формул. Приклади тавтологій. Еквівалентні формули, приклади.

  2. Поняття логічного наслідку. Теорема про еквівалентність різних означень логічного наслідку. Основні типи логічних наслідків: modus ponens, modus tallens, правило силогізму, правило резолюцій.

  3. Алгебра висловлювань. Основні властивості логічних операцій, зокрема закони дистрибутивності та де Моргано. Принцип двоїстості в численні висловлювань.

  4. Поняття про ДНФ та КНФ, ДДНФ та ДКНФ. Теорема про можливість зведення до них будь-якої формули.

  5. Поняття про булеві функції. Теорема про зв‘язок з формулами числення висловлювань, ДДНФ та ДКНФ форми.

  6. Повні системи логічних зв’язок. Довести повноту однієї з систем: , , , та неповноту системи .

  7. Штрих Шефера і стрілка Пірса, як приклади повних систем зв’язок.*

  8. Критерій Поста.*

  9. Висловлювальні форми, інтерпретації висловлювальних форм, предикати. Операції над висловлю вальними формами. Синтаксис та семантика числення предикатів. Поняття тотожно-істинної, тотожно-хибної, виконливої формул. Навести приклади таких формул з відповідними доведеннями.

  10. Еквівалентні формули в численні предикатів. Навести приклади з доведеннями.

  11. Метод математичної індукції з точки зору математичної логіки. Довести нерівність Коші методом математичної індукції.

  12. Послідовності, що задаються рекурентними співвідношеннями. Розв‘язання рекуретностей типу Фібоначі.

  13. Основні поняття теорії множин – елемент, підмножина, універсальна множина, порожня множина, характеристична функція. Парадокс Рассела та способи його подолання.

  14. Операції над множинами – об‘єднання, перетин, різниця, симетрична різниця, доповнення. Основні властивості цих операцій. Узагальнені закони дистрибутивності та де Моргано.

  15. Декарті добуток множин та його властивості, приклади, узагальнення. Множини .

  16. Основні принципи комбінаторики. Задача про підрахунок кількості функцій, визначених на скінчених множинах, та кількості k-елементних розміщень на множині.

  17. Комбінації без повторень. Основні властивості коефіцієнтів (з доведенням).

  18. Біном Ньютона та наслідки з нього.

  19. Підрахунок кількості розв‘язків рівняння в натуральних числах; в цілих невід‘ємних числах.

  20. Перестановки з повтореннями (перестановки типів). Формула для кількості перестановок.

  21. Поліноміальні коефіцієнти, як коефіцієнти в розкладі полінома .

  22. Формули включень та виключень.

  23. Класична ймовірність та її властивості, приклади задач.