- •Пермский Государственный Технический Университет
- •Тема 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задачи
4. Импликация () “если а, то b”
Действие операции определяется следующим образом: сложное высказывание аbложно только в том случае, когда а истинно, аb– ложно.
a |
b |
ab |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
А называется антецедентом, а b– консеквентом.
5. Эквивалентность (~)
Действие операции определяется следующим образом: сложное высказывание а~bистинно, если а истинно иbистинно, или если а ложно иbложно.
a |
b |
a~b |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Эквивалентность примерно соответствует употреблению выражения «тогда и только тогда».
6. Сумма по модулю два
a |
b |
ab |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
7. Штрих Шеффера ( , обратная конъюнкция и – не)
a |
b |
ab |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
8. Стрелка Пирса (, обратная дизъюнкция или – не )
a |
b |
ab |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Используя эти логические операции можно строить сколь угодно сложные высказывания.
Приоритет выполнения операций:
⌐ ~
Пример:Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим:
П – пропускаете занятия;
Y– успешно занимаетесь;
Х – сдадите экзамен хорошо,
тогда все высказывание запишется:
Значение истинности всего выражения будет зависеть от истинности переменных обозначающих простые высказывания.
Пример.
Пусть a=1, b=0, c=0, d=1.
Символы ⌐ ~называются пропозициональными связками,a,b,c, … и т. д. - пропозициональными переменными. Выражение, построенное из пропозициональных переменных с помощью пропозициональных связок, называется пропозициональной формой или формулой.
1.3. Булевы функции
1.3.1. Некоторые определения из теории множеств
Множество – фундаментальное неопределяемое понятие. Множество – это совокупность объектов, которые, с одной стороны, различны и отличимы друг от друга, а с другой стороны воспринимаются как единое целое.
Пусть А и В – два множества.
<a,b> - упорядоченная пара, где первый элемент, а второй элемент.
Декартово произведение - это множество пар
Бинарным отношением fиз множества А в множество В называется подмножество:
.
Функция - это такое отношение, что из иследует, чтоx=z, т. е. функциональность – это однозначность.
Пример.
А={1,2,3,4,5}
B={1,4,9,16,25}
={<1,1>, <1,4>, <1,9>, <1,16>, <1,25>, <2,1>, <2,4>, <2,9>, <2,16>, <2,25>,….<3,9>, …. ,<4,16>,…..<5,25>}
f={<1,1>, <2,4>, <3,9>, <4,16>, <5,25>} – это функция, гдеb=a2.
1.3.2. Булевы функции
Функция называется функцией алгебры логики.
y=f(x1,x2) – бинарная функция,
y=f(x1,x2,….,xn) –n- арная функция.
Пример.
Т. о. каждое элементарное высказывание может принимать значение либо 0, либо 1. Каждому набору значений a,b,cсоответствует одно значение всего сложного высказывания (0 или 1).
Булеву функцию от nпеременных можно задать таблицей истинности
x1 |
….. |
xn-1 |
xn |
f(x1, …,xn) |
0 |
|
0 |
0 |
|
0 |
|
0 |
1 |
|
|
|
|
|
|
1 |
|
1 |
1 |
|
Переменные, которые принимают значения 0 или 1 называются булевыми переменными.
Некоторые функции всегда принимают значение 1 (на любом наборе переменных). Такие функции называются тавтологиями. Некоторые функции всегда принимают значение 0 (на любом наборе переменных). Такие функции называются противоречиями.