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

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

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. 
    Класична ймовірність та її властивості, приклади задач.