- •Пермский Государственный Технический Университет
- •Тема 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.9. Некоторые теоремы теории £
Множество теорем теории £ бесконечно. Рассмотрим некоторые из них.
1. (закон двойного отрицания).
2. (закон двойного отрицания).
3. (из ложного что угодно).
4. (закон де Моргана)
5. (закон де Моргана)
и т. д.
(Вывод законов см. Ф.А. Новиков “Дискретная математика для программистов”, стр.114).
Теорема. Теоремами теории £ являются только общезначимые формулы.
Следствие.Теория £ формально непротиворечива.
Выводы.
1. Можно задать некоторые правила преобразования формул, которые обладают свойством: при применении к общезначимым формулам они дают в результате общезначимые формулы. Такими правилами являются правила вывода.
2. Можно задать конечное число общезначимых формул таких, что любая общезначимая формула может быть получена из них с помощью правил вывода.
Тема 3. Логика и исчисление предикатов
Логика высказываний – очень узкая логическая теория. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках логики высказываний. Например:
1. Всякий друг Ивана есть друг Петра. Павел не друг Ивана, следовательно, Павел не друг Петра.
2. Простое число 2 – четное, следовательно, существуют четные простые числа.
Корректность таких выводов базируется не только на истинности соответствующих предложений, но и на смысле слов «всякий» и «существуют». Чтобы сделать более понятной структуру сложных высказываний используют специальный язык – язык предикатов первого порядка.
3.1. Предикаты
Рассмотрим предложения, зависящие от параметров:
Х – четное число.
X<Y
X+Y=Z
X,Y– братья.
Если заменить переменные X,Y,Zнекоторыми конкретными значениями, то мы получим определенные высказывания, которые могут быть истинными или ложными.
Например:
3 – четное число.
2<5
2+3=5
Иван и Павел – братья.
Предложения такого рода называются предикатами.
Предикат Р(х1,…,хn) – функция, переменные которой принимают значения из некоторого множестваM, а сама функция принимает значение истина (1) или ложь (0).
Р(х1,…,хn) :Mn{0,1}
Высказывания - это 0-местные предикаты. Над предикатами выполняются логические операции, в результате чего получаются новые предикаты.
С каждым предикатом связано число, которое называется местностью или арностью предиката (количество переменных).
Язык предикатов – наиболее приближенный к естественным языкам формальный математический язык.
Примеры:
1. Р(х) – х делится на 2
Q(x) –xделится на 3
P(x)&Q(x) –xделится на 2 и 3, т. е. определен предикат делимости на 6.
2. S(x,y) – x равно y.
S(x,y)&S(y,z)S(x,z)
Кроме операций логики высказываний, к предикатам можно применять операции связывания кванторами.
1. Квантор общности ().
- высказывание истинное для каждого, т. е. это высказывание не зависит отxi.
2. Квантор существования ().
- высказывание истинно, если существует, для которого это высказывание истинно.
Для конечных множеств операции навешивания кванторов можно выразить через операции & и .
Пусть
На языке предикатов можно составить более сложные высказывания, чем на языке логики высказываний.
3.2. Исчисление предикатов
Исчисление предикатов первого порядка – это формальная теория K, в которой определены :
1. Алфавит:
Связки: (основные), & ,( дополнительные).
Служебные символы: (,).
Кванторы ,.
Предметные константы a,b,c,….
Предметные переменные x,y,z,….
Символы предикатов P,Q,R,….
Символы функций f,g,h,….
Константы, переменные, функторы – называются термами.
2. Формулы. Слово называется формулой, если оно имеет следующий синтаксис:
1) Р(х1,…,хn) – атомарная формула (А).
Вхождения переменных в атомарную формулу называются свободными.
2) Если А – формула, то - тоже формула.
3) Если А и В – формулы, то - формулы.
4) Если А – формула, содержащая свободную переменную х, то - формулы.
Слово является формулой, если это следует из 1-4.
Вхождения переменных в формулах называются связанными, переменные не равные х остаются свободными.
Пример
- х – свободная переменная, у – связанная переменная.
Формула, не содержащая свободных переменных, называется замкнутой.
3. Аксиомы (логические).
1) Любая система аксиом исчисления высказываний.
А1:
А2:
А3:
2) Собственные аксиомы.
P1:,
P2:,
где t– терм.
4. Правила вывода.
1. ,
2. - введение квантора общности,
3. - введение квантора существования.
Исчисление предикатов, в котором кванторы могут связывать только предметные переменные и не могут связывать функторы или предикаты называется исчислением первого порядка.