- •ВВЕДЕНИЕ
- •Глава 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)
- •Ответы к тестам самоконтроля
113
Благо везде и повсюду зависит от соблюдения двух условий: 1) правильного установления конечной цели и 2) отыскания соответственных средств, ведущих к цели.
Аристотель
Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
§ 1. Понятие об эффективных и полуэффективных процессах (методах)
Пусть имеем элементы некоторого класса M, часть из которых может обладать некоторым свойством U. Будем считать, что задан эффективный процесс (метод) если: 1) есть предписание, определяющее последовательность преобразований которые надо применять одно за другим к элементу из M; 2) если элемент х из M задан, предписание однозначно определяет такую последовательность преобразований, что за конечное число шагов выясняем, обладает х свойством U или нет.
Таким образом, если задан эффективный процесс, то для любого элемента из M за конечное число шагов выясняем, обладает заданный элемент свойством
Uили нет.
Вотличие от эффективного процесса полуэффективным процессом считается некоторая процедура, которая не всегда позволяет для произвольного элемента х из M за конечное число шагов выяснить, обладает х свойством U или
нет. Точнее будем считать, что задан полуэффективный процесс (метод) если выполняется вышеуказанное условие 1), а вместо 2) следующее условие: если элемент х из M задан, предписание однозначно определяет такую последовательность преобразований, что если х обладает свойством U, то за конечное число шагов это выясняем, если же х не обладает свойством U, то, возможно, мы не сможем это выяснить за конечное число шагов.
Пример эффективной процедуры. Пусть M={0,1,2,3,...} . Число n может быть квадратом какого-либо числа из M, назовем это свойством U. Эффективной процедурой для выяснения обладает ли элемент х из M свойством U может быть следующая. Берем числа 1,...,x-1 и возводя их в квадраты смотрим равны они х либо нет. Очевидно, что таким образом мы всегда сможем выяснить для любого х за конечное число шагов обладает х свойством U либо нет.
Теперь рассмотрим пример полуэффективной процедуры.
Рассмотрим известный процесс извлечения квадратного корня из положительных действительных чисел:
114
328 = 18,1… 1 ___
|
|
|
|
|
|
|
28 |
228 |
|
||||
|
8 |
224 |
|
|
||
361 |
|
400 |
|
|||
1 |
|
361 |
|
|||
|
|
...... |
|
|
||
Ясно, что если для заданного числа а число |
a является рациональным, |
|||||
то рано или поздно заметим период. Если же a |
не является рациональным |
числом, то, сколько бы долго ни продолжались эти вычисления, мы не сможем на основе этих вычислений сказать, будет когда-нибудь период или нет, т.е.
является a рациональным или нет. Таким образом, эта процедура будет полуэффективной процедурой для выяснения рациональности a .
Отыщи всему начало, и ты много поймешь. Козьма Прутков
§ 2. Дедуктивные теории
Дедукция (от латинского deductic - выведение) - форма мышления, когда заключение выводится чисто логическим путем (т.е. по правилам логики) из некоторых данных посылок.
Индукция (от латинского inductio - наведение) - форма мышления, посредством которой от некоторых фактов или истинных высказываний переходят к некоторой гипотезе (общему утверждению).
Примеры дедуктивных рассуждений.
1.Все люди смертны. Сократ – человек. Следовательно, Сократ смертен.
2.5> 3, 3 >1, следовательно, 5 >1.
Примеры индуктивных рассуждений.
1.График функции y=2x+3 прямая, график функции y=3x+1 прямая, следовательно, функции вида y=kx+b имеют графиком прямую. Полученная здесь гипотеза оказывается истинной.
2.Рассмотрим предположение Ферма, что число р= 22n +1 является простым для всех n. При n=0,1,2,3,4 получим, что р равно 3, 5, 17, 257, 65537 и все они простые числа. Но Эйлер показал, что для n=5 р= 4 294 967 297 и это число является составным (делится на 641). Следовательно, это предположение Ферма не верно.
2.Возьмем формулу Эйлера N=x2+x+41. При каждом x=1,2,3,...,39 число N является простым, следовательно, числа N, указанного вида, являются просты-
ми. Сформулированная здесь гипотеза неверна, например, при х=40 число N=412, следовательно, оно не является простым.
115
Таким образом, заключение, полученное дедуктивным способом, уже не нуждается в доказательстве. Заключение, полученное индуктивным способом, требует доказательства его истинности. Будем рассматривать дедуктивные методы. Введем понятие дедуктивной теории.
Дедуктивная теория считается заданной, если задан язык этой теории и из множества правильно построенных выражений (предложений, называемых формулами) языка выделено дедуктивным образом множество теорем. Подробнее, дедуктивная теория считается заданной, если:
1). Задан алфавит и правила образования выражений (слов) в этом алфавите.
2). Заданы правила образования формул (правильно построенных выражений) языка.
3). Из множества всех формул языка выделено некоторым дедуктивным способом (который будет описан ниже) подмножество Т, элементы которого будем называть теоремами. В зависимости от того, как задано это подмножество Т, будем различать получающиеся при этом дедуктивные теории.
Подмножество Т может задаваться одним из следующих способов. I. Задаются аксиомы и конечное число правил выводов, т.е.
а) из множества формул (правильно построенных выражений) выделяется подмножество А, элементы которого называются аксиомами (аксиом может быть как конечное число, так и бесконечное),
б) задается конечное число правил выводов, используя которые, и только их, из аксиом можно некоторым образом получать теоремы (подробнее этот вопрос будет изучаться в следующих параграфах).
Если теоремы заданы указанным образом, т.е. заданием аксиом и конечного числа правил вывода, то эта дедуктивная теория называется формальной аксиоматической теорией или формальным (логическим) исчислением.
Особо отметим, что аксиомы лишь задаются, поэтому их часто называют скрытыми определениями. Бытующее мнение, согласно которому аксиомы принимаются без доказательств, не совсем точно передает суть дела.
Аксиомы не доказываются не потому, что могут не доказываться, а потому, что не могут быть доказаны.
II. Задаются только аксиомы, а правила вывода считаются известными,
т.е.:
а) из множества формул (правильно построенных выражений) выделяется подмножество А, элементы которого называются аксиомами (аксиом может быть как конечное число, так и бесконечное),
б) правила вывода (методы доказательства) теорем считаются известными из опыта изучения математики.
При таком задании теорем дедуктивной теории, говорим, что задана по-
луформальная аксиоматическая теория.
116
III. Аксиом нет, а задается только конечное число правил выводов, с помощью которых и получают теоремы. Такую дедуктивную теорию называют
теорией естественного вывода.
Случай, когда нет аксиом и нет правил вывода, не рассматривается в логике.
Применяя один из указанных выше способов задания теорем, будем получать множества теорем Т1, Т2 и Т3 соответственно. Сразу возникают вопросы: когда эти множества Т1, Т2, и Т3 совпадают? Когда некоторые из Т1, или Т2, или Т3 дедуктивной теории B совпадают или покрывают класс "истинных" формул теории B1, при условии совпадения для B и B1, алфавитов и формул. Эти вопросы оказываются не всегда простыми и в рамках этого курса затрагиваются незначительно .
Разве может леопард избавиться от пятен. Английская пословица
§ 3. Свойства дедуктивных теорий
Выберем один из трех способов задания теорем дедуктивной теории. Изменяя аксиомы или правила вывода (в случае, когда они задаются), можно получать различные множества теорем Т. Это множество Т - множество теорем (множество доказуемых формул) является существенной характеристикой дедуктивной теории.
Может оказаться, что множество теорем Т покрывает все множество формул (правильно построенных выражений) теории. Иначе, это означает, что доказуема любая формула (правильно построенное выражение) и если в теории есть отрицание, то из доказуемости какой-то формулы тут же следует доказуемость ее отрицания. Следовательно, в этом случае доказуем какой-то факт и его отрицание. Ясно, что теории, в которых можно доказать, что угодно, не представляют интерес с многих позиций.
Дедуктивные теории, в которых множество теорем покрывает все множество формул (правильно построенных выражений) называются противоречивыми, в противном случае – непротиворечивыми. Выяснение непротиворечивости дедуктивной теории является одной из важнейших проблем. К сожалению, эта проблема оказывается и одной из очень сложных.
Пусть множество теорем Т является частью, не совпадающей со всем множеством формул (правильно построенных выражений) Ф, т.е. наша дедуктивная теория непротиворечива. Тогда можно уже интересоваться, а какую часть Ф занимают теоремы. Для этого вводят свойство полноты теории. Свойство полноты дедуктивной теории характеризует достаточность теорем для ка- ких-то целей. В зависимости от того, для каких целей должно быть достаточно теорем, будем в дальнейшем вводить различные понятия полноты.