- •Введение
- •Тема 1. Логика высказываний
- •1.1. Понятие высказывания
- •1.2. Логические операции
- •1. Отрицание или инверсия ( – не)
- •Конъюнкция ( ,, ·, логическое и )
- •4. Импликация ( ) “если а, то b”
- •6. Сумма по модулю два
- •7. Штрих Шеффера ( , обратная конъюнкция и – не)
- •8. Стрелка Пирса ( , обратная дизъюнкция или – не )
- •1.3. Булевы функции
- •1.3.1. Некоторые определения из теории множеств
- •1.3.2. Булевы функции
- •1.4. Формулы
- •1.5. Равносильные формулы
- •1.6. Подстановка и замена
- •1.7. Формы представления высказываний
- •1.8. Минимизация сложных высказываний методом Квайна
- •1.9. Полные системы функций
- •1.9.1. Система функций { }
- •1.9.2. Замкнутые классы
- •1.9.3. Функциональная полнота
- •Тема 2. Логические исчисления
- •2.1. Интерпретация формул
- •2.2. Примеры тождественно истинных формул высказываний
- •2.3. Формальные теории
- •Выводимость.
- •2.5. Интерпретация формальных теорий
- •2.6. Исчисление высказываний.
- •2.7. Производные правила вывода
- •2.8. Дедукция
- •2.9. Некоторые теоремы теории £
- •Тема 3. Логика и исчисление предикатов
- •3.1. Предикаты
- •3.2. Исчисление предикатов
- •3.3. Интерпретация
- •3.4. Основные равносильности для предикатов
- •3.5. Приведенная форма представления предикатов
- •Тема 4. Автоматическое доказательство теорем
- •4.1. Постановка задачи
- •4.2. Доказательство от противного
- •4.3.Правило резолюции для исчисления высказываний
- •4.4. Правило резолюции для исчисления предикатов
- •4.5. Основные положения мр (выводы)
- •4.6. Логическое программирование
- •Тема 5. Теория алгоритмов
- •5.1. Интуитивное понятие алгоритма
- •5.2. Конкретизация понятия алгоритма
- •5.2.1. Машины Тьюринга
- •5.2.3. Рекурсивные функции
- •5.2.3. Нормальные алгорифмы Маркова
- •5.3. Алгоритмически неразрешимые проблемы
- •5.3.1. Проблема самоприменимости
- •5.3.1.1. Нумерация мт
- •5.3.1.2. Самоприменимость мт
- •5.3.2. Проблема останова
- •5.3.3. Разрешимые и неразрешимые задачи математики
- •5.4. Характеристики сложности вычислений
- •5.5. Классы сложности задач
- •5.5.1. Р задачи
- •5.5.2. Np задачи
2.2. Примеры тождественно истинных формул высказываний
Закон тождества. «Всякое высказывание является логическим следованием себя самого»
x->x
Доказательство сводится к построению таблиц истинности
x |
|
0 |
1 |
1 |
1 |
Закон противоречия. «Для всякого высказывания неверно, что истинно и высказывание х и его отрицание.
Доказательство сводится к построению таблиц истинности
x |
|
0 |
1 |
1 |
1 |
Закон исключенного третьего. «Для каждого высказывания х истинно или само высказывание, или его отрицание»
Доказательство сводится к построению таблиц истинности
x |
|
0 |
1 |
1 |
1 |
Закон двойного отрицания. Отрицание от любого высказывания равносильно самому высказыванию.
Добавление антцедента (истина из чего угодно). Если х – истина, то для любого у истинно, что y->x.
Из ложного что угодно.
Modus ponens. Если x->y – истинно и x – истинно, то согласно закону mp можно заключить, что истинно у.
Этот тип заключения очень часто используется при математических доказательствах.
Пример.
1. Все простые числа, большие 2 – нечетны.
2. 7 – простое число.
3. Следовательно, 7- нечетное число.
Здесь применяются 2 закона. Первый закон – закон заключения от общего к частному будет рассмотрен в логике предикатов.
На основании этого закона преобразуется первая посылка заключения: Для всех х, если х – простое число большее 2, то х – нечетно. Согласно заключению от общего к частному высказывание если 7 – простое число большее 2, то 7 – нечетно – истинно. (А)
7 – нечетно (В)
A->B – Истинно
А – истинно
Применяем mp, следовательно, высказывание 7-нечетно – истинно.
Modus tollens
Или
Этот закон применяется при доказательствах от противного. Он является двойственным к mp.
Закон силлогизма
Этот закон позволяет строить сколь угодно длинные цепочки рассуждений.
2.3. Формальные теории
Рассмотрим один из методов получения всех тождественно истинных формул логики высказываний. До сих пор мы рассматривали формулы как выражения для булевых функций. Теперь мы будем рассматривать формулы как последовательности символов, построенные по определенным правилам. Для этого нам сначала надо задать алфавит (латинские буквы, знаки логических операций и скобки). Затем определим понятие слова. Слово – конечная последовательность символов.
Формула – это
любая переменная (x,y,z,…)
Если слова A и B – формулы, то слова и т. д. – формулы.
Свойство формулы: Можно описать процедуру, которая устанавливает, является слово формулой или нет.
Для преобразования формул применяются правила, которые называются правилами вывода.
Правило подстановки.
правило mp.
Таким образом:
Формальная теория - это
Множество символов, образующих алфавит А.
Множество слов в этом алфавите, которые называются формулами ( ).
Подмножество формул, которые называются аксиомами( ).
Множество отношений между формулами, которые называются правилами вывода (R).
Алфавит может быть конечным или бесконечным. Алфавит и множество формул (А и Ф) образуют сигнатуру теории. Множество аксиом (B) также может быть конечным или бесконечным. Если множество аксиом бесконечно, то оно задается с помощью конечного множества схем аксиом и правил порождения конкретных аксиом из схем аксиом. Аксиомы делятся на два вида: логические (общие для целого класса формальных теорий) и нелогические (собственные) аксиомы, которые определяют специфику и содержание конкретной теории.
Множество правил вывода R – конечно.