- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
15.2. Логическое следование. Проверка правильности логических выводов
Когда говорят, что из высказывание P1 следует P2 (т.е. P1P2), подразумевают, что всякий раз, когда истинно высказывание P1, истинно и высказывание P2.
Импликация P1P2≡1 является общезначимой формулой (т.е. формула тождественно истинна).
«Я работаю в фирме» «Я работаю в фирме или в корпорации».
A(AB) – соответствующая формула является тавтологией.
Предложение 1. «Если студент много занимается, то он успешно сдает экзамен по математической логике», AB.
Предложение 2. «Если студент «провалился» на экзамене по математической логике, то он не занимался» .
Следует ли из первого предложения второе?
.
Здесь мы использовали формулы равносильных преобразований из дискретной математики.
Таким образом, из первого предложения следует второе предложение, – и это закон контрапозиции. Логический вывод подразумевает наличие посылок или гипотез и вывода или заключения.
Для проверки правильности логических выводов необходимо убедиться, что из конъюнкции посылок следует заключение.
15.3. Силлогизмы в логике высказываний
Если силлогизм условный, то одна из его посылок условная.
Если одна из посылок условная, а вторая посылка и вывод категоричное высказывание, то такой силлогизм условно-категоричный.
Если обе посылки и вывод условные высказывания, то такой силлогизм – условный.
Если одна из посылок условное высказывание, а другая разделительное («или-или»), то это условно-разделительный силлогизм.
Условно-категоричные силлогизмы.
Импликация отражает ту сущность нашего мира, когда следствие может иметь несколько причин.
Мир допускает переход от причины к следствию, но не обратно. (ПС).
Имеются четыре модуса условно-категоричных силлогизмов:
Такая запись в виде посылок и заключения называется аргументом. Для проверки аргумента необходимо проверить, чтобы из конъюнкций посылок следовало заключение. Такая проверка может быть проверкой правильности логического вывода.
Проверим аргумент по первому модусу условного силлогизма:
Проверим аргумент по второму модусу условного силлогизма:
Разделительно-категоричные силлогизмы.
AB – разделительное «или», или сумма по модулю 2 (или A, или B).
Альтернативы должны исключать друг друга. Должны быть перечислены все альтернативы
Условный силлогизм.
Условный силлогизм: обе посылки и вывод – условные суждения.
Условно-разделительный силлогизм.
Условно-разделительный силлогизм: одна из посылок – условное суждение, а другая – разделительное суждение.
В зависимости от числа альтернатив различают:
дилемму – 2 альтернативы;
трилемму – 3 альтернативы;
тетралемму – 4 альтернативы.
Конструктивная дилемма:
Совокупность произвольных посылок и произвольных заключений называется аргументом. Проверка правильности аргументов – это проверка следования из конъюнкции посылок заключения.
15.4. Получение следствий из данных посылок
Получение следствий из данных посылок можно осуществить, получив СКНФ данных посылок, тогда все возможные сочетания элементарных конъюнкций и будут всевозможными следствиями из данных посылок. Например:
Следствия данных посылок:
Нужно получить СКНФ и перебрать все возможные комбинации конъюнкций (в данном случае у нас, их 7), т.е. получается булеан от членов СКНФ без одного элемента (пустого множества).
15.5. Метод резолюций
Если имеются два высказывания: которые имеют контрарные или инверсные () литералы, то следствием из этих посылок является (BC). Проверим это утверждение:
Такие следствия называются резольвентами (это дизъюнкция членов при контрарных литералах).
Метод основан на получении резольвент. Последовательно получаем резольвенты исходного множества формул, доказательство невыполнимости которого мы ведем, до тех пор, пока не получится (пустое следствие). Здесь доказательство ведется от противного.
Для применения этого метода необходимо использовать КНФ. Например, для modus ponens:
Получили дерево доказательства. Взяты две посылки и отрицание заключения в КНФ. Следствием посылок является резольвентаB, а следствием является пустое множество. Это признак невыполнимости исходного множества членов КНФ. А т.к. доказательство проводилось от противного, стало быть, мы и доказали следование B из посылок AB,A.