Математична логіка

Відповідальний лектор

Марченко Наталя Андріївна

1. Передмова.

1.1. Предмет навчальної дисципліни, її наукові і методичні основи, мета викладання і завдання дисципліни.

Курс «Математична логіка» ставить своєю ціллю ознайомлення студентів з основними розділами комп’ютерної математичної логіки, які широко використовуються в проектуванні та розробці математичного та програмного забезпечення сучасних ЕОМ.

Предметом дисципліни є типові та сучасні алгоритми математичної логіки та дискретної математики, а також методи та засоби їх реалізації та використання.

Науковою основою вивчення дисципліни є загальна математична підготовка студентів.

Методологічною основою викладання дисципліни є загальні методи розв’язування математичних задач, які поєднують лекційні та практичні заняття разом з самостійною роботою студента.

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

1.2. Що студент повинен знати, вміти і з чим бути ознайомленим в результаті вивчення дисципліни.

В результаті вивчення дисципліни студент повинен знати:

  • місце математичної логіки в загальній системі математичних знань;
  • предмет та об’єкти вивчення математичної логіки;
  • основні поняття теорії множин, алгебри логіки, комбінаторики та кодування;
  • основні методи розв’язання типових задач.

В результаті вивчення дисципліни студент повинен вміти:

  • встановити взаємозв’язки між математичною логікою та іншими навчальними дисциплінами спеціальності;
  • виконувати постановку і розв’язання задач синтезу та аналізу дискретних об’єктів;
  • знаходити ефективний для розв’язання конкретної задачі математичний апарат.

1.3. Організаційно-методичні вказівки щодо організації і методики проведення усіх видів навчальних занять, організації і виконання індивідуальних завдань.

Організаційно-методичними вказівками для організації і проведення занять є комплект з трьох методичних вказівок для проведення занять загальним обсягом 104 сторінки. Ці методичні вказівки також доступні студентам в електронному вигляді.

1.4. Система контролю якості навчання студентів.

Контроль якості навчання студентів здійснюється проведенням поточного контролю згідно з переліком контрольних робіт, виконанням студентами розрахункових завдань, складанням студентами вихідного іспиту.

1.5. Організація самостійної роботи.

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

2. Зміст дисципліни.

Вступ.

Введення до вивчення дисципліни. Предмет дисципліни. Мета викладання дисципліни. Завдання дисципліни.

Розділ 1. Теорія множин.

Тема 1. Поняття множини. Способи завдання множин. Підмножина. Надмножина. Пуста та універсальна множина.

Тема 2. Операції над множинами. Круги Ейлера, діаграми Венна.

Тема 3. Потужність множин. Рівняння потужностей.

Тема 4. Поняття булеана, декартового добутку множин. Степінь множини. Решітки і булеві алгебри.

Тема 5. Відношення. Операції над відношеннями. Фактор-множина, перетин.

Тема 6. Спеціальні класи бінарних відношень: відношення еквівалентності та порядку. Класи еквівалентності.

Розділ 2. Алгебра логіки.

Тема 1. Функції алгебри логіки та їх властивості. Основні співвідношення. Правила де Моргана.

Тема 2. Булеві функції багатьох змінних. Зв’язок булевих функцій і теорії множин.

Тема 3. Двоїстість булевих функцій. Нормальні форми. Досконалі нормальні форми.

Тема 4. Алгебра Жегалкіна. Способи побудови поліномів Жегалкіна.

Тема 5. Проблема повноти системи булевих функцій. Класи Поста. Критерій Поста.

Тема 6. Аналіз релейно-контактних схем.

Тема 7. Синтез контактних схем. Метод каскадів.

Тема 8. Мінімізація булевих функцій у класі ДДНФ. Карти Карно.

Тема 9. Синтез пристроїв з неповним набором значень на виході.

Тема 10. Скорочені, тупікові, мінімальні форми. Способи їх побудови. Алгоритм Квайна-МакКласкі-Петріка. Матриця імплікантних випробувань.

Тема 11. Схемна реалізація мінімізованих булевих функцій.

Тема 12. Мінімізація булевих функцій у класі ДКНФ. Складність булевих функцій у класі КНФ.

Розділ 3. Комбінаторика.

Тема 1. Основні комбінаторні схеми. Правила суми та добутку. Принцип включення та виключення.

Тема 2. Вибірки. Розміщення з повторенням. Розміщення без повторень.

Тема 3. Сполучення без повторювань. Властивості сполучень. Трикутник Паскаля. Біном Ньютона і поліноміальна формула. Сполучення з повторенням.

Тема 4. Перестановки без повторень. Субфакторіали. Перестановки з повтореннями.

Тема 5. Задача о розміщеннях. Розбивки. Числа Стирлінга другого роду. Числа Бела.

Тема 6. Розбивки на цикли. Числа Стирлинга першого роду. Розбивки числа на доданки. Арифметичний трикутник.

Розділ 4. Кодування.

Тема 1. Історія і основні положення теорії кодування.

Тема 2. Алфавітне кодування. Префікс і постфікс слова. Таблиця кодів. Роздільні та перекісні схеми кодування. Нерівність Макміллана.

Тема 3. Кодування з мінімальною надмірністю. Мінімізація довжини кода повідомлення. Ціна кодування.

Тема 4. Алгоритм кодування Шеннона-Фано. Оптимальне кодування. Алгоритм Хаффмена.

Тема 5. Перешкодостійке кодування. Кодування з виправленням помилок. Класифікація помилок.

Тема 6. Кодова відстань. Код Хемінга.