4.2. Принципи побудови формальних теорій . . . . . . . . . . . . . . . . 71

4.3. Числення висловлень. Аксіоми і правила виводу . . . . . . . . 73

4.4. Числення предикатів і теорії першого порядку . . . . . . . . . . . 74

4.5. Мови і грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.6. Формальні грамматики і їхні властивості . . . . . . . . . . . . . . . . 78

4.7. Контекстно - вільні грамматики . . . . . . . . . . . . . . . . . . . . . . . . 79

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Розділ 5. Основи комбінаторіки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.1. Комбінаторні конфігурації . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.2. Підстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.3. Біноміальні коефіцієнти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Предметний показчик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Вступ

При вивченні об'єктів виробничої, економічної й інших сфер діяльності людини з'ясовується, що точний опис таких об'єктів пов'язаний з необхідністю виміру великої кількості змінних або параметрів. У ряді випадків змінні, що беруть участь у системі контролю або керування такі, що безупинний вимір їх значення просто неможливий через величезну кількость даних, що обробляються.

Вихід із цієї ситуації полягає в переході до дискретних уявлень про вимірювані параметри. Це дозволяє виконувати виміри тільки в деякі фіксовані моменти часу. Такі вимірювання неминуче знижують точність представлення об'єкта дослідження й одночасно спрощує його модель. Правомірність переходу до дискретного представлення повинна бути старанно обгрунтована. Саме таке обгрунтування дає дискретна математика.

Основні об'єкти дискретної математики - множини, графи, функції логіки й автомати, формальні системи і комбінаторика.

Розділи, присвячені множинам, є основою для інших розділів дискретної математики. Розглядаються основні операції з множинами, поняття декартового добутку, відношення і їх властивості, а також відповідності відображення і функції. Більшість понять, що викладаються в розділі про графи, мають самостійне теоретичне і прикладне значення. Графи, завдяки своїй наочності й універсальності, стали однією із найбільш поширених моделей для задач керування. Саме дослідження з теорії графів призвели до поняття об'єктивно складних задач, тобто таких задач, складність яких не усувається ніяким збільшенням потужності обчислювальних систем.

Логіка й автомати - традиційні розділи курсу дискретної математики. Розглядаються основні закони математичної логіки і методики роботи з логічними виразами. Основи теорії автоматів подані для класу кінцевих автоматів. Докладно представлені питання синтезу і мінімізації автоматів. Формальні системи є центральним розділом курсу дискретної математики. Знання принципів організації формальних систем, пов'язаних з обчисленнями, стає важливим елементом математичної культури будь-якого дослідника, що має відношення до алгоритмізації процесів керування. По суті воно дає розуміння того, що можна і чого не можна зробити за допомогою обчислювальних машин. Елементи комбінаторики подані як необхідний елемент систем керування, пов'язаних із генеруванням варіантів прийняття рішень.

Посібник призначений для студентів напрямків "Комп'ютерні науки" та "Прикладна математика".