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

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

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

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

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

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

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

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

5.1. Основні принципи комбінаторіки . . . . . . . . . . . . . . . .

5.2. Розбиття на групи . . . . . . . . . . . . . . . . . . . . . . . . .

5.3. Сполучення з повтореннями . . . . . . . . . . . . . . . . . . .

5.4. Біном Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

Вступ

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

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

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

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

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

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