- •Содержание
- •Введение
- •1) Парадокс Рассела
- •2) Парадокс Ришара
- •3) Парадокс Бери
- •4) Парадокс лжеца
- •1.3. Булева алгебра.
- •1. Алгебра логики (высказывания и предикаты).
- •1.1. Понятие алгебраической системы.
- •1.2. Примеры алгебраических систем.
- •1.4. Алгебра высказываний.
- •1.5. Алгебра предикатов.
- •1.6. Истинностное значение формулы.
- •1.7. Отношение следования.
- •1.8. Равносильность.
- •2. Булевы функции и нормальные формы.
- •2.1. Способы задания.
- •2.2. Унарные и бинарные операции.
- •2.3. Сведение к нескольким операциям.
- •2.4. Теорема Поста.
- •2.5. Нормальные формы.
- •2.6. Полиномы Жегалкина.
- •3. Исчисление высказываний.
- •3.1. Общее понятие о логическом исчислении.
- •3.2. Правила вывода исчисления высказываний.
- •3.3 Аксиомы.
- •3. 4. Доказуемость формул.
- •3.5. Выводимость формул.
- •3.6. Транзитивность секвенций.
- •3.7. Теорема дедукции.
- •3.8. Непротиворечивость исчисления высказываний.
- •3.9. Полнота исчисления высказываний.
- •4. Исчисление предикатов.
- •Правила вывода
- •4.1. Теорема дедукции.
- •4.2. Вспомогательные правила вывода. Структурные:
- •Логические:
- •4.3. Непротиворечивость исчисления предикатов.
- •4.4. Полнота исчисления предикатов.
- •4.5. Другие теоремы.
- •5. Алгоритмические модели.
- •5.1. Понятие алгоритма.
- •6. Машины Тьюринга.
- •6.1. Описание одноленточной машины Тьюринга.
- •6.2 Функции, вычислимые по Тьюрингу.
- •6.3. Свойства машин Тьюринга.
- •6.4. Тезис Тьюринга.
- •7. Частично-рекурсивные функции.
- •7.1. Определение частично-рекурсивных функций.
- •7.2. Примеры чрф.
- •7.3. Тезис Чёрча.
- •8. Соотношение между классами «т» и «ч».
- •8.1. Вычислимость по Тьюрингу чрф.
- •9. Нумерации наборов чисел и слов
- •9.1. Нумерация пар чисел.
- •9.2. Наборов из n чисел.
- •9. 4. Нумерация слов.
- •10. Нумерация алгоритмов. Невычислимые функции.
- •10.1 Нумерация машин Тьюринга
- •10.2. Невычислимые функции.
- •10.3. Универсальная функция.
- •11. Алгоритмически неразрешимые проблемы.
- •11.1. Понятие массовой и индивидуальной алгоритмической проблемы. Определение алгоритмически неразрешимой проблемы.
- •11.2. Способы доказательства алгоритмической неразрешимости.
- •1. Проблема самоприменимости мт
- •2.Метод сведения
- •11.3. Проблема «X Wx».
- •11.4. Полувычислимые и не полувычислимые алгоритмически разрешимые проблемы.
- •11.5. Другие неразрешимые проблемы из теории рекурсивных функций.
- •11.6. Различные примечательные неразрешимые проблемы математики.
- •12. Сложность вычислений.
- •12.1. Характеристики сложности.
- •12.2. Теорема об отсутствии верхней границы сложности вычислений.
- •12.3. Теорема Блюма о линейном ускорении.
- •13. Классы сложности.
- •13.1. Сложность массовой проблемы.
- •13.2. Примеры лёгкорешаемых и труднорешаемых задач.
- •13.3. Класс «np».
- •13.4. Как соотносятся классы p и np?
- •14. Труднорешаемые задачи.
- •14.1. Полиноминальная сводимость задач.
- •14.2 Класс «npc»
- •14.3. Основные np-полные задачи.
- •14.3.1. Теорема Кука (np-полнота задачи «вып»).
- •14.3.2. Примеры np-полных задач:
- •14.3.3. Псевдополиноминальные алгоритмы. Сильная np-полнота.
1.7. Отношение следования.
Определение 5: Следование формулы
В из формулы А будем обозначать:
1) Формула В следует из формулы А
если в любой интерпретации, в которой
формула А истинна, формула В также
истинна.
Пример
Чтобы в этом убедиться, необходимо построить таблицу истинности.
2) Формула А
следует из множества формул Г=
если во всех интерпретациях, в которых
формулы
истинны,
формула А также истинна.
,
…
И
(Здесь и
далее символ
будет соответствовать словесной
формулировке «если…, то…»)
Пример
Убедиться можно аналогично, построив таблицу истинности.
Теорема 1: Теорема о следовании и импликации.
(Здесь и
далее символ
будет соответствовать словесной
формулировке «тогда и только тогда»)
Необходимость:
т.к.
,
,
или
,
Достаточность:
Значит ,
Обобщение теоремы 1:
Г,
Г
,
где Г=
Следствие теоремы 1:
- формула B следует из
множества формул A тогда
и только тогда, когда формула A
– общезначима. Таким образом, следование
равнозначно, когда некая другая формула
является общезначимой.
1.8. Равносильность.
Определение 6: Равносильность формулы В формуле А будем обозначать АВ
Формула А
равносильна формуле В, если
в любой интерпретации I.
В случае логики высказываний формулы
равносильны, если их таблицы истинности
одинаковы, что используется для
доказательства равносильности.
Основные формулы равносильности:
1)А А – идемпотентность;
2)
,
– коммутативность;
3)
– ассоциативность;
4)
– дистрибутивность;
5)Законы де Моргана
Для алгебры предикатов необходимо добавить закон коммутативности для кванторов:
и законы де Моргана для кванторов
Теорема 2. Отношение равносильности связано с отношением следования:
А
B
Необходимость:
Пусть AB,
то
или
Достаточность:
(в
обратную сторону)
и
,
и когда
,
то и
AB.
Теорема 3. Связывает отношение равносильности с операцией эквивалентности:
AB
Следствие:
AB,
BC
(
,
)
Теорема 4. Теорема об эквивалентной замене:
Если AB и есть C, в которое A входит в качестве подформулы,
CB – формула, в которой все вхождения формулы А заменены на формулу В.
Эта теорема позволяет изменять цепочки формул без изменения их истинностного значения.
Пример:
2. Булевы функции и нормальные формы.
Логическими функциями называются функции от булевых переменных, значения которых есть булева величина. Логическое выражение: Bn B
2.1. Способы задания.
Задание логической функции с помощью таблицы.
Каждая логическая функция может быть задана с помощью таблицы.
Пример: Задана некая булева функция.
X |
Y |
Z |
F(x,y,z) |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Всего 2n логических наборов переменных (комбинаций).
Сколько
может быть различных булевых функций
от n переменных?
2n-количество различных упорядоченных наборов из n переменных. Логическая функция от n переменных может быть задана как 2n различных наборов, при этом каждому набору должно соответствовать одно из двух значений.
Таким образом, при n=1, получаем 22=4 логических функций f(x).
x |
x |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
При n=2 ,получаем 16 функций.
x |
y |
(x) |
(y) |
x |
y |
0 |
1 |
|
|
|
|
|
|
|
|
| |
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
(x)– константа х (y)– константа y
x – отрицание х y – отрицание y
0 – константа 0 1 – константа 1
- конъюнкция – Дизъюнкция
- Импликация - эквивалентность
- сравнение x>y - сравнение x<y
- исключающее или - обратная импликация
| - штрих Шеффера («И НЕ») - стрелка Пирса («ИЛИ НЕ»)
Задание логической функции с помощью формулы.
Логическую функцию можно задать с помощью формул и бинарных операций.
Пример:
У нас есть некая бинарная функция и.
Если вместо
одной из переменных поставить любую
бинарную функция, то получим функцию
от 3-х переменных.
Вывод: любая функция может быть задана как таблицей, так и формулой.
