- •Математическая логика и теория алгоритмов
- •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 Варианты контрольных заданий по дисциплине «Математическая логика»
14.6. Формы представления формул логики высказываний
Скобочная форма, образуется непосредственно после формализации высказывания.
Дизъюнктивная нормальная форма – дизъюнкция элементарных конъюнкций.
Конъюнктивная нормальная форма – конъюнкция элементарных дизъюнкций.
КНФ также называют клаузальной формой.
Клауза – элементарная дизъюнкция.
Литера, литерал – элементарное высказывание или его отрицание.
Дизъюнкт – дизъюнкция конечного числа литералов.
Хорновский дизъюнкт имеет не более одной не инверсной литеры.
Пример.
.
Хорновские дизъюнкты используются в языке ПРОЛОГ (PROLOG, от PROgramming in LOGic – программирование в логике; разработан в 1972 г. Аланом Колмари) для описания правил типа «Если, то». Кстати, в ПРОЛОГЕ с помощью импликации записываются и так называемые факты: .
.
Т.е. факт – это утверждение истинности некой формулы.
Преобразование в КНФ обычно производится при помощи распределительного закона.
СКНФ получают из КНФ путём добавления к каждому дизъюнкту тождественно ложной литеры.
14.7. Проблема дедукции в логике высказываний
Помимо равносильности в логике широко используется отношение следования. Говорят, что формула S является следствием множества формул H (записывается так: H├S) если при всех интерпретациях, при которых истинны все формулы из H, истинна также и формула S [32].
Таким образом, тавтология – следствие из пустого множества формул. Записывается так: ├T, т.е. слева от знака ├ нет символа, но он подразумевается равным константе 0, – как в факте.
S является следствием из H тогда и только тогда, когда их импликация истинна H→S≡1:
(H├S)↔[(H→S)≡1];
├(H→S).
Если рассматривается множество формул или гипотез H1,H2,…,Hn, то (H1,H2,…,Hn)├S↔├(H1×H2×…×Hn)→S – т.е. подразумевается импликация из конъюнкций этих формул, которая общезначима. Таким образом, из множества формул выводима формула S (├S).
Фундаментальная проблема логики: определить является ли S следствием из множества формул H (проблема дедукции).
Проблема описывается так: необходимо установить общезначимость следования H→S.
Доказательство может быть проведено следующим образом:
,
или, наоборот, путем доказательства невыполнимости:
.
Во втором случае говорят, что доказывают невыполнимости объединения формулы H и формулы S.
15. Проверка правильности логических выводов. Метод резолюций
15.1. Закон контрапозиции
На основе данного сложного высказывания АВ можно сформулировать обратное ему высказывание BA. Нетрудно убедиться, что оно не равносильно исходному.
Для всякого сложного высказывания AB можно сформулировать противоположное . Нетрудно убедиться, что оно не равносильно исходному.
Высказывание типа называетсяобратно – противоположным.
Нетрудно убедиться, что оно равносильно исходному:
.
Такая равносильность называется законом контрапозиции [25].
Согласно этому закону:
высказывания AB и одновременно истинны либо одновременно ложны;
высказывание, которое является обратно противоположной данной теореме AB также является теоремой (здесь сложное высказывание называется теоремой);
вместо данной теоремы можно доказать обратно противоположную ей теорему.
Кроме того, если высказывание AB – теорема, то A есть достаточное условие B, а B – необходимое условие A.
Если оба высказывания являются теоремами (AB, BA; т.е. AB), то A – необходимое и достаточное условие B, а B – необходимое и достаточное условие A.
Если AB – теорема, а BA не теорема, то A – достаточное, но не необходимое условие B, а B – необходимое, но не достаточное условие A.