Основи дискретної математики:Колоквіум

Матеріал з USIC Wiki

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

• Портал:Інформаційні науки

• Основи дискретної математики:Іспит

Зміст 1 Числення висловлювань. Операцiї над висловлюваннями. Синтаксис та семантика числення висловлювань. Поняття тавтологiї(тотожно-iстинної), тотожно-хибної, виконливої формул. Приклади тавтологiй. Еквiвалентнi формули, приклади. 2 Поняття логiчного наслiдку. Теорема про еквiвалентнiсть рiзних означень логiчного наслiдку.Основнi типи логiчних наслiдкiв: modus ponens, modus tallens, правило силогiзму, правило резолюцiй. 3 Алгебра висловлювань Основнi властивостi логiчних операцiй, зокрема закони дистрибутивностi та де Моргано. Принцип двоїстостi в численнi висловдювань. 4 Поняття про ДНФ та КНФ. Теорема про можливiсть зведення до них будь-якої формули. 5 Поняття про булевi функцiї. Теорема про зв'язок з формулами числення висловлювань, ДДНФ та ДКНФ форми. 6 Повнi системи логiчних зв'язок.Довести повноту однiєї з систем {}, , , та неповноту системи 7 Штрих Шефера i стрiлка Пiрса, як приклади повних систем зв'язок. 8 Висловлювальнi форми, iнтерпретацiї висловлювальних форм, предикати. Операцiї над висловлювальними формами. Синтаксис та семантика числення предикатiв. Поняття тотожноiстинної, тотожно-хибної, виконливої формул. Навести приклади таких формул з вiдповiдними доведеннями. 9 Еквiвалентнi формули в численнi предикатiв. Навести приклади з доведеннями. 10 Метод математичної iндукцiї з точки зору математичної логiки. Довести нерiвнiсть Кошi методом математичної iндукцiї. 11 Задачi, що приводять до рекурентних спiввiдношень. Задачi про Ханойську вежу та розрiзання пiцци. Розв'язання рекурентностей типу Фiбоначi. 12 Основнi поняття теорiї множин - елемент, пiдмножина, унiверсальна множина, порожня множина, характеристична функцiя. Парадокс Рассела та способи його подолання. 13 Операцiї над множинами - об'єднання, перетин, рiзниця, симетрична рiзниця, доповнення. Основнi властивостi цих операцiй. Узагальненi закони дистрибутивностi та де Моргано. 14 Декартiв добуток множин та його властивостi, приклади, узагальнення. Множини BA, 2A 15 Основнi принципи комбiнаторики. Задача про пiдрахунок кiлькостi функцiй визначених на скiнченних множинах та кiлькостi k - елементних розмiщень на множинi. 16 Комбiнацiї без повторень. Основнi властивостi коефiцiєнтiв (всi з доведенням). 17 Пiдрахунок кiлькостi розв'язкiв рiвняння x1 + x2 + ... + xk = n на N та N {0}. 18 Бiном Ньютона та наслiдки з нього. 19 Перестановки з повтореннями (перестановки типiв). Формула для кiлькостi перестановок. 20 Полiномiальнi коефiцiєнти, як коефiцiєнти в розкладi полiнома (x1 + x2 + ... + xk)n. 21 Формули включень та виключень. 22 Застосувавши формулу включень та виключень, вивести формулу для функцiї Ейлера. 23 Класична ймовiрнiсть та її властивостi, приклади задач.

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

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

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

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

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

Повнi системи логiчних зв'язок.Довести повноту однiєї з систем {}, , , та неповноту системи

Штрих Шефера i стрiлка Пiрса, як приклади повних систем зв'язок.

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

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

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

Задачi, що приводять до рекурентних спiввiдношень. Задачi про Ханойську вежу та розрiзання пiцци. Розв'язання рекурентностей типу Фiбоначi.

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

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

Декартiв добуток множин та його властивостi, приклади, узагальнення. Множини B^A, 2^A

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

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

Пiдрахунок кiлькостi розв'язкiв рiвняння x₁ + x₂ + ... + x_k = n на N та N {0}.

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

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

Полiномiальнi коефiцiєнти, як коефiцiєнти в розкладi полiнома (x₁ + x₂ + ... + x_k)ⁿ.

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

Застосувавши формулу включень та виключень, вивести формулу для функцiї Ейлера.

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