- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
21
Л. Кэрролл (Приключения Алисы в стране чудес)1
§ 5. Равносильность пропозициональных форм
Пропозициональные формы А и В называются равносильными, если при каждой совокупности значений всех пропозициональных букв, входящих в А и В, эти формы принимают одинаковые истинностные значения.
Например, форма А В равносильна форме А В, в чем легко убедиться
с помощью таблиц истинности: |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
A |
|
B |
|
A |
|
B |
|
И |
Л |
И |
Л |
|
Л |
И |
Л |
|
И |
Л |
И |
И |
|
Л |
И |
И |
|
Л |
И |
Л |
Л |
|
И |
Л |
Л |
|
Л |
И |
И |
И |
|
И |
И |
И |
В этих таблицах результирующие столбцы совпадают, т.е. при одинаковых значениях букв А и В значения форм А В и А В равны, следовательно, эти формы равносильны. Далее, форма А А&В равносильна А. Действительно, имеем следующую таблицу:
A |
|
A |
& |
B |
|
A |
Л |
Л |
Л |
Л |
Л |
|
Л |
Л |
Л |
Л |
Л |
И |
|
Л |
И |
И |
И |
Л |
Л |
|
И |
И |
И |
И |
И |
И |
|
И |
Также, очевидно, А А равносильно В В.
При определении равносильности двух форм не обязательно предполагать, что они содержат одни и те же пропозициональные буквы. Так, в последних примерах имеем случаи, когда в равносильные формы входят разные буквы. При этом, если какая-нибудь пропозициональная буква входит только в одну из двух равносильных форм, то эта форма при всех значениях этой буквы принимает одно и то же значение, если значения других фиксированы. Следовательно, хотя эта буква и входит в форму, но истинностная функция, определенная формой, от этой буквы не зависит.
Высказывание "А равносильно В" будем обозначать следующим образом: А ~ B.
1 Здесь и далее, цитаты из произведений Л. Кэрролла приводятся по переводу с английского, выполненного Н. Димуровой, в котором приведены стихи в переводах С. Маршака, Д. Орловской и О. Седаковой.
22
Пусть А, В, C - произвольные пропозициональные формы. Отношение равносильности пропозициональных форм, как легко видеть, обладает следующими свойствами:
1)А ~ А - рефлексивность;
2)если А ~ В, то В ~ А - симметричность;
3)если А ~ В и В ~ C , то А ~ C - транзитивность.
Следовательно, отношение равносильности является отношением эквивалентности и порождает разбиение множества пропозициональных форм на непересекающиеся классы. В каждый класс попадают равносильные между собой пропозициональные формы. Докажем теорему.
Теорема 1.3. Пропозициональные формы А и В равносильны тогда и только тогда, когда А≡В является тавтологией.
Доказательство. Необходимость. Пусть А и В равносильны, следовательно, они при каждой совокупности значений всех пропозициональных букв, входящих в них, принимают одинаковые истинностные значения, тогда по определению связки ≡ форма А≡В всегда принимает значение И, т.е. является тавтологией.
Достаточность. Пусть А≡В тавтология, т.е. принимает всегда значение И. Это означает, что А и В имеют всегда одинаковые истинностные значения, т.е. они равносильны. Теорема доказана.
В природе существует внутренне присущая ей скрытая гармония, отражающаяся в наших умах в виде простых математических знаков.
Г. Вейль
§ 6. Важнейшие пары равносильных пропозициональных форм
Пусть А, В, С - пропозициональные буквы, Т- тавтология и П - противоречие. Используя таблицу истинности, легко показать, что
1) ( А) равносильно А.
Если под А понимать обозначение некоторого высказывания, то получаем, что двойное отрицание высказывания А означает то же, что и высказывание А. Полученное соотношение между ( А) и А называют
законом двойного отрицания.
Аналогичным образом можно показать, что имеют место следующие законы.
2)A & B ~ B & A;
законы коммутативности;
3)A B ~ B A;
23
4)(A & B) & C ~ A &(B & C);
законы ассоциативности;
5)(A B) C ~ A ( B C );
6)А&(В С) ~ А&В А&С - первый закон дистрибутивности;
7)А В&С ~ (А В)&(А С) - второй закон дистрибутивности;
8)(А&В) ~ А В, законы де Моргана;
9) (А В) ~ А& В,
10)А&А ~ А, законы идемпотентности;
11)А А ~ А,
12)А А ~ Т - закон исключенного третьего;
13)А& А ~ П - закон противоречия;
14)А&Т ~ А;
15)А Т ~ Т;
16)А&П ~ П; свойство операций с Т и с П;
17)А П ~ А;
18)А А&В ~ А;
19)А&(А В) ~ А; законы поглощения;
20) А В ~ В А - закон контропозиции.
Как уже замечено выше, соотношения 1) - 20) доказываются с помощью таблиц истинности.
Можно показать, что соотношения 1) - 20) будут иметь место и тогда, когда вместо пропозициональных букв А, В и С будут подставлены произвольные пропозициональные формы. Соотношения 1) - 20) позволяют находить для заданных пропозициональных форм равносильные упрощенные формы или равносильные формы, имеющие более удобный с некоторых позиций вид. Из этих же соотношений видно, что над пропозициональными формами можно производить преобразования: раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя.
Из соотношений 2) - 6) видно, что операция & напоминает умножение (обладает некоторыми свойствами умножения), а - сложение, поэтому часто конъюнкцию двух высказываний называют (логическим) произведением их, а дизъюнкцию - (логической) суммой.
Битый – правду говорит Молвь людей простых – Стоит двух, кто не был бит, Грамотей – троих.
П.-Ж. Беранже
§ 7. Зависимости между пропозициональными связками
24
Связки , &, , =>, ≡ не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются равносильные пропозициональные формы.
Например, связка ≡ может быть выражена через связки и & на
основании соотношения |
|
(1.1) |
|||||||||||
|
≡ |
|
|
|
|
|
В) & (В |
|
А). |
||||
А В ~ (А |
|
|
|
||||||||||
Для доказательства (1.1) достаточно составить таблицы истинности и |
|||||||||||||
убедиться, что результирующие столбцы этих таблиц совпадают. |
|||||||||||||
Для импликации имеем: |
(1.2) |
||||||||||||
А |
|
В ~ |
|
А |
|
В. |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|||||
Таким образом, связку ≡ можно выразить через , & и : |
|||||||||||||
А |
≡ |
|
|
|
|
|
|
|
(1.3) |
||||
|
В ~ ( А В) & ( В А). |
|
|||||||||||
Так |
как |
|
|
А равносильно ( А), |
то А&В равносильно ( А)& ( В), а |
||||||||
последнее |
|
согласно |
закону де |
Моргана равносильно ( А В), |
|||||||||
следовательно, |
|
|
|
|
|
|
(1.4) |
||||||
А&В ~ |
|
|
|
|
|
|
В). |
|
|
||||
|
( А |
|
|
|
|
||||||||
Из (1.4) видно, что & можно выразить через и . Покажем, что |
|||||||||||||
можно выразить через |
и &. Действительно, так как А равносильно ( А), то |
А В равносильно ( А) ( В), последнее по закону де Моргана равносильно
( А& В). Итак, |
|
(1.5) |
||
|
|
|
||
А В ~ |
|
( А & В). |
|
|
Из соотношения (1.2) заменой А на А получаем, что |
(1.6) |
|||
|
|
|
В. |
|
А В ~ |
|
А |
|
Т.е. можно выразить через и .
Изложенное показывает, что одни связки могут быть выражены через другие. Имеют место следующие теоремы.
Теорема 1.4. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая только связки , &, , причем связка относится только к пропозициональным буквам.
Доказательство. Связки и ≡ можно исключить согласно соотношениям (1.2) и (1.3). При этом останутся только связки , &, . Если пропозициональная связка стоит перед некоторой скобкой, например,(А&В С В), то на основании законов де Моргана можно внести под скобки, при этом связка & меняется на , а на &, а связки и ≡ нигде не появляются. Внеся под скобки, перед которыми они стоят, добьемся, чтобыотносилась только к пропозициональным буквам. Теорема доказана.
Теорема 1.5. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая либо только связки , &, либо только ,, либо только , .
25
Доказательство. Покажем, что можно оставить только связки и &. Связки и ≡ можно исключить (если они есть) на основании соотношений (1.2) и (1.3), а затем по (1.5) исключим . В результате останутся только и &. Остальные случаи доказываются аналогичным образом на основании соотношений (1.1) - (1.6).
Будем рассматривать пропозициональные формы, содержащие только связки , &, . Как уже установлено выше, всякая пропозициональная форма может быть приведена преобразованиями равносильности к такому виду.
Будем говорить, что связка & двойственна связке , и наоборот. Пропозициональные формы А и А* называются двойственными, если
одна получается из другой заменой каждой связки & и на двойственную. Например, если А =(А В)&С, то А* =(А & В) С.
Отношение двойственности взаимно: если А двойственно А*, то А* двойственно А. Следующую теорему считают законом двойственности.
Теорема 1.6. Если пропозициональные формы А и В равносильны, то и двойственные им формы А* и В* также равносильны.
Доказательство. Пусть А и В равносильны, а А1,А2,...,Аn - буквы, входящие в А или В. Будем считать, что А1,А2,...,Аn входят и в А, и в В. Если бы это было не так, например, В не содержала бы Аk(1≤k≤n), входящего в А,
то В можно заменить равносильной |
формой В Аk& Аk, содержащей эту |
букву. Таким образом, всегда можем добиться, чтобы А и B содержали все |
|
буквы А1,А2,...,Аn. |
|
По условию |
|
А(А1,А2,...,Аn) ~ В(А1,А2,...,Аn). |
(1.7) |
Если формы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (1.7) получим, что
А(А1,А2,...,Аn ) ~ В(А1,А2,...,Аn). |
(1.8) |
В пропозициональных формах соотношения (1.8) добьемся, чтобы относилась только к буквам. При этом согласно законам де Моргана связки & и поменяются на двойственные. Следовательно, получим
А* ( А1, А2,..., An) ~ |
B* ( А1, А2,..., An ) |
форм |
(1.9) |
||
По |
определению |
равносильности |
равносильность |
||
А*( А1, А2,..., An) и |
B*( А1, А2,..., An) означает, что |
они принимают |
одинаковые значения при любых совокупностях значений букв А1,А2,...,An. Поэтому, если вместо букв А1,А2,...,An подставить А1, А2,..., An, то формы останутся равносильными. Учитывая, что А равносильно А, из (1.9) получим А*( А1,А2,...,Аn ) ~ B*(А1,А2,...,Аn), что и требовалось доказать.
Каких цветов в саду весеннем нет! В. Шекспир