Відмінності між версіями «Зміст курсу "Навчальний курс "Математична логіка", ФМФ"»
Матеріал з Вікі ЦДУ
(→Тема 1. Назва теми) |
|||
| (не показано 16 проміжних версій цього учасника) | |||
| Рядок 13: | Рядок 13: | ||
}} | }} | ||
| − | + | ||
| − | + | =Змістовий модуль І = | |
| − | + | ==Тема 1. Алгебра висловлень== | |
| + | |||
* 1.1 Вступ. Предмет математичної логіки. Історична довідка. | * 1.1 Вступ. Предмет математичної логіки. Історична довідка. | ||
| − | * 1.2 | + | * 1.2 Побудова алгебри висловлень: висловлення та операції над ними. Алфавіт алгебри висловлень. |
| − | * 1. | + | * 1.3 Формули алгебри висловлень. типи формул. Тавтології. Способи побудови. |
| − | * 1. | + | * 1.4 Відношення рівносильності в алгебрі висловлень. Рівносильні формули. Основні рівносильності. Теорема про заміну. Двоїсті операції. Двоїсті формули. Закон двоїстості. |
| − | + | * 1.5 Проблема вирішення в алгебрі висловлень. Способи її розв’язання. | |
| − | == | + | * 1.6 Нормальні форми формул алгебри висловлень. Досконалі ДНФ та КНФ. |
| − | + | * 1.7 Відношення логічного наслідку в алгебрі висловлень. Логічність міркувань. Критерії логічного наслідку. | |
| − | + | * 1.8 Основні схеми логічних висновків. Знаходження логічних наслідків заданих гіпотез. | |
| − | + | ==Тема 2. Булеві функції== | |
| − | + | * 2.1 Булеві змінні, булеві вектори та їх кількість. Булеві функції від n змінних. | |
| − | + | * 2.2 Булеві функції однієї та двох змінних. | |
| − | + | * 2.3 Зв’язок булевих функцій з формулами алгебри висловлень. | |
| − | == | + | * 2.4 Функціональна повнота системи булевих функцій. |
| − | + | * 2.5 Алгебра Жегалкіна. Способи побудови поліномів Жегалкіна. | |
| + | * 2.6 Двоїсті функції та формули. Класи булевих функцій: T0, T1, M, L, S та їх замкнутість. Теорема Поста. | ||
| + | * 2.7 Застосування булевих функцій до побудови релейно-контактних схем. Аналіз та синтез РК-схем. | ||
| + | * 2.8 Застосування алгебри висловлень в шкільному курсі математики. Логічний квадрат. | ||
| + | ==Тема 3. Числення висловлень== | ||
| + | * 3.1.Схема формалізації змістовної теорії. Аксіоматична побудова числення висловлень. | ||
| + | * 3.2 Поняття теореми та формального доведення. Приклади виводу формул. | ||
| + | * 3.3 Виведення із припущень. Метатеорема дедукції. Похідні правила виведення, приклади виводу теорем. | ||
| + | * 3.4 Несуперечливість, повнота і розв’язність числення висловлень. Незалежність аксіом числення висловлень. | ||
| + | * 3.5 Різні аксіоматики числення висловлень. | ||
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | ===Теоретичний матеріал=== |
| + | [https://owncloud.kspu.kr.ua/index.php/s/HxoiWUjdYxa46Kt Лекція №1] | ||
| − | + | [https://owncloud.kspu.kr.ua/index.php/s/viZnMpSC0ujrqoB Лекція №2] | |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/wGyVEmSJhpKbStG Лекція №3] |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/hOkEXM48kwy6zsD Лекція №4] |
| − | + | [https://owncloud.kspu.kr.ua/index.php/s/eyXGGlEf13WvzJW Лекція №5] | |
| − | + | ||
| − | + | ||
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | ===Практичні завдання=== |
| + | [https://owncloud.kspu.kr.ua/index.php/s/T4tAG3U7Wdijl6k Практична №1] | ||
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/QBnUksfvYd3rHEv Практична №2] |
| − | + | [https://owncloud.kspu.kr.ua/index.php/s/ELKSgTZp32aNB3k Практична №3] | |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/HM9gJl5KNtYoKoC Практична №4] |
| − | + | [https://owncloud.kspu.kr.ua/index.php/s/KqewvtMzlqBvM3f Практична №5] | |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/zclPiYnhKb7ZDmJ Практична №6] |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/VQeHyjSyQ5poG7Z Практична №7] |
| − | == | + | ===Самостійна робота=== |
| − | == | + | |
| − | + | ||
| − | + | ||
| − | [ | + | [[Самостійна робота до модуля "Алгебра висловлень"]] |
| − | [https://owncloud.kspu.kr.ua/index.php/s/ | + | [https://owncloud.kspu.kr.ua/index.php/s/quEwxE6HB2qWsHT Індивідуальна робота №1] |
| − | ==== | + | =Змістовий модуль ІІ. = |
| − | + | ==Тема 1. Логіка предикатів== | |
| + | * 1.1 Поняття предикату, область істинності предиката, типи предикатів. Операції над предикатами. Квантори загальності та існування. Формули логіки предикатів. Вільні і зв’язані змінні. | ||
| + | * 1.2 Інтерпретація формул. Типи формул. Модель множини формул. Виконувані та загальнозначущі формули. Основні логічно загальнозначущі формули. | ||
| + | * 1.3 Приклад формули виконуваної в нескінченній області і не виконуваної в жодній скінченній області інтерпретації. | ||
| + | * 1.4 Відношення рівносильності в логіці предикатів. Основні рівносильності. Рівносильні перетворення формул. Зведена та пренексна (випереджена) нормальні форми. | ||
| + | * 1.5 Відношення логічного наслідку в логіці предикатів. Основні правила слідування. | ||
| + | * 1.6 Проблема розв’язності в логіці предикатів. | ||
| + | * 1.7 Застосування мови логіки предикатів для запису математичних тверджень, означень, побудови заперечень тверджень. | ||
| + | ==Тема 2. Математичні теорії першого порядку== | ||
| + | * 2.1 Мова першого порядку. Терми і формули. Логічні і спеціальні системи аксіом. Правила виведення. Приклади математичних теорій. Доведення в теорії. Похідні правила виводу. Приклади доведень. Теорема дедукції. | ||
| + | * 2.2 Проблеми несуперечливості, повноти, розв’язності теорій. Несуперечливість числення предикатів. Інтерпретація мови теорії. Модель теорії. Ізоморфізм. Категоричність теорії. Теорема повноти. | ||
| + | * 2.3 Формальна арифметика - теорія натуральних чисел. Мова. Спеціальні аксіоми. Теорема Геделя про неповноту. | ||
| + | ==Тема 3. Теорія алгоритмів== | ||
| + | * 3.1 Поняття алгоритму та необхідність його уточнення. Алфавітні оператори та алгоритми. Алгоритмічна система. | ||
| + | * 3.2 Нормальні алгоритми Маркова. Приклади. Гіпотеза Маркова. Поняття про універсальний нормальний алгоритм. | ||
| + | * 3.3 Обчислювальні функції. Уточнення поняття алгоритму за допомогою рекурсивних функцій. Розв’язні і перераховані множини | ||
| + | * 3.4 Машини Тьюрінга і Поста. | ||
| + | * 3.5 Поняття про алгоритмічно нерозв’язні проблеми, їх приклади. Методологічна суть алгоритмічної нерозв’язності математичних проблем. | ||
| − | |||
| − | === | + | ===Теоретичний матеріал=== |
| − | + | ===Практичні завдання=== | |
| − | + | ===Самостійна робота=== | |
Поточна версія на 11:31, 6 листопада 2015
Зміст курсу
Змістовий модуль І
Тема 1. Алгебра висловлень
- 1.1 Вступ. Предмет математичної логіки. Історична довідка.
- 1.2 Побудова алгебри висловлень: висловлення та операції над ними. Алфавіт алгебри висловлень.
- 1.3 Формули алгебри висловлень. типи формул. Тавтології. Способи побудови.
- 1.4 Відношення рівносильності в алгебрі висловлень. Рівносильні формули. Основні рівносильності. Теорема про заміну. Двоїсті операції. Двоїсті формули. Закон двоїстості.
- 1.5 Проблема вирішення в алгебрі висловлень. Способи її розв’язання.
- 1.6 Нормальні форми формул алгебри висловлень. Досконалі ДНФ та КНФ.
- 1.7 Відношення логічного наслідку в алгебрі висловлень. Логічність міркувань. Критерії логічного наслідку.
- 1.8 Основні схеми логічних висновків. Знаходження логічних наслідків заданих гіпотез.
Тема 2. Булеві функції
- 2.1 Булеві змінні, булеві вектори та їх кількість. Булеві функції від n змінних.
- 2.2 Булеві функції однієї та двох змінних.
- 2.3 Зв’язок булевих функцій з формулами алгебри висловлень.
- 2.4 Функціональна повнота системи булевих функцій.
- 2.5 Алгебра Жегалкіна. Способи побудови поліномів Жегалкіна.
- 2.6 Двоїсті функції та формули. Класи булевих функцій: T0, T1, M, L, S та їх замкнутість. Теорема Поста.
- 2.7 Застосування булевих функцій до побудови релейно-контактних схем. Аналіз та синтез РК-схем.
- 2.8 Застосування алгебри висловлень в шкільному курсі математики. Логічний квадрат.
Тема 3. Числення висловлень
- 3.1.Схема формалізації змістовної теорії. Аксіоматична побудова числення висловлень.
- 3.2 Поняття теореми та формального доведення. Приклади виводу формул.
- 3.3 Виведення із припущень. Метатеорема дедукції. Похідні правила виведення, приклади виводу теорем.
- 3.4 Несуперечливість, повнота і розв’язність числення висловлень. Незалежність аксіом числення висловлень.
- 3.5 Різні аксіоматики числення висловлень.
Теоретичний матеріал
Практичні завдання
Самостійна робота
Самостійна робота до модуля "Алгебра висловлень"
Змістовий модуль ІІ.
Тема 1. Логіка предикатів
- 1.1 Поняття предикату, область істинності предиката, типи предикатів. Операції над предикатами. Квантори загальності та існування. Формули логіки предикатів. Вільні і зв’язані змінні.
- 1.2 Інтерпретація формул. Типи формул. Модель множини формул. Виконувані та загальнозначущі формули. Основні логічно загальнозначущі формули.
- 1.3 Приклад формули виконуваної в нескінченній області і не виконуваної в жодній скінченній області інтерпретації.
- 1.4 Відношення рівносильності в логіці предикатів. Основні рівносильності. Рівносильні перетворення формул. Зведена та пренексна (випереджена) нормальні форми.
- 1.5 Відношення логічного наслідку в логіці предикатів. Основні правила слідування.
- 1.6 Проблема розв’язності в логіці предикатів.
- 1.7 Застосування мови логіки предикатів для запису математичних тверджень, означень, побудови заперечень тверджень.
Тема 2. Математичні теорії першого порядку
- 2.1 Мова першого порядку. Терми і формули. Логічні і спеціальні системи аксіом. Правила виведення. Приклади математичних теорій. Доведення в теорії. Похідні правила виводу. Приклади доведень. Теорема дедукції.
- 2.2 Проблеми несуперечливості, повноти, розв’язності теорій. Несуперечливість числення предикатів. Інтерпретація мови теорії. Модель теорії. Ізоморфізм. Категоричність теорії. Теорема повноти.
- 2.3 Формальна арифметика - теорія натуральних чисел. Мова. Спеціальні аксіоми. Теорема Геделя про неповноту.
Тема 3. Теорія алгоритмів
- 3.1 Поняття алгоритму та необхідність його уточнення. Алфавітні оператори та алгоритми. Алгоритмічна система.
- 3.2 Нормальні алгоритми Маркова. Приклади. Гіпотеза Маркова. Поняття про універсальний нормальний алгоритм.
- 3.3 Обчислювальні функції. Уточнення поняття алгоритму за допомогою рекурсивних функцій. Розв’язні і перераховані множини
- 3.4 Машини Тьюрінга і Поста.
- 3.5 Поняття про алгоритмічно нерозв’язні проблеми, їх приклади. Методологічна суть алгоритмічної нерозв’язності математичних проблем.
