- •Математическая логика и теория алгоритмов
- •Воронеж 2011
- •1. Логика высказываний
- •1.1. Алгебра высказываний
- •Операции над высказываниями
- •1.1.2. Правила записи сложных формул
- •1.1.3. Таблицы истинности
- •1.1.4. Равносильность формул
- •1.1.5. Дизъюнктивные и конъюнктивные нормальные формы
- •1.1.6. Логическое следствие
- •1.2. Исчисление высказываний
- •1.2.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2.2. Метод резолюций в исчислении высказываний
- •1.2.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •Выразим с помощью схемы примитивной рекурсии:
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
1.1.2. Правила записи сложных формул
При записи сложных высказываний следует обращать внимание, чтобы в формулах не было двух рядом стоящих логичеcких связок – они должны быть разъединены формулами либо вспомогательными символами и не было двух рядом стоящих формул – они должны быть разъединены логической связкой.
При записи сложных формул следует помнить, что
1) каждое вхождение логической связки относится к пропозициональной переменной или формуле, находящейся под знаком отрицания;
2) каждое вхождение логической связки после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие логическую связку;
3) каждое вхождение логической связки после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие эту связку и т.д.
При использовании этих правил к одной и той же формуле скобки следует расставлять постепенно, продвигаясь слева направо.
Логические связки по силе и значимости могут быть упорядочены так: , , , , . То есть самой сильной связкой является отрицание, затем конъюнкция, дизъюнкция, импликация и, наконец, эквиваленция. Зная правила о силе логических связок, можно опускать те пары скобок, без которых ясен порядок выполнения логических операций.
Пример. Пусть дана формула
F=(((X1( ))X3)X4).
Необходимо удалить скобки.
1) убрать внешние скобки для формулы, так как они не определяют старшинство никаких операций:
F=((X1( ))X3)X4;
2) убрать скобки, охватывающие формулу импликации, так как операция эквиваленции будет выполняться только после выполнения операции импликации:
F=(X1( ))X3X4;
3) убрать скобки, охватывающие формулу дизъюнкции, так как операция импликации будет выполняться только после выполнения операции дизъюнкции:
F=X1( )X3X4;
4) убрать скобки, охватывающие формулу отрицания, так как операция дизъюнкции будет выполняться только после выполнения операции отрицания:
F=X1 X3X4;
Итак, последовательность выполнения операций после задания значений пропозициональных переменных следующая: сначала необходимо определить значение формулы ( ), затем (X1( )) затем ((X1( ))X3) и, наконец,
(((X1( ))X3)X4).
Пример. Дана формула F=X1X2X3 X3X1. Необходимо расставить все скобки.
1) поставить скобки на формулу, реализующую операцию отрицания:
X1X2X3( )X3X1;
2) поставить скобки на формулу, реализующую операцию конъюнкции:
F=((X1X2) X3)( )X3X1;
3) поставить скобки на формулу, реализующую операцию дизъюнкции:
F=(((X1X2) X3)( ))X3X1;
4) поставить скобки на формулу, реализующую операцию импликации:
F=((((X1X2) X3)( ))X3)X1;
5) поставить скобки на формулу, реализующую операцию эквиваленции:
F=(((((X1X2X3)( ))X3)X1).
1.1.3. Таблицы истинности
Каждая пропозициональная переменная принимает значения 0 или 1, тогда ПФ в соответствии с определением логических операций также принимает значения 0 или 1, поэтому ее можно рассматривать как функцию, область значений и область определения которой совпадают и равны {0,1}. Такую функцию будем называть двоичной, булевой функцией или переключательной функцией.
Каждой ПФ, а значит и булевой функции, можно поставить в соответствие таблицу, называемую таблицей истинности, в которой перечислены все возможные значения входящих в нее переменных и значения ПФ или булевой функции на этих наборах. Каждый такой набор можно рассматривать как запись некоторого n-разрядного двоичного числа, при этом наибольшее двоичное число получим, составив набор из одних 1, а наименьшее – из одних 0. Таким образом, наибольшему числу соответствует десятичное число – 1, а наименьшему – 0; всем остальным возможным наборам числа, заключенные между 0 и –1. Это соответствие способствует упорядочению наборов аргументов булевой функции, которые заносятся в таблицу в порядке возрастания. Если функция зависит от n переменных, то таблица истинности содержит наборов значений переменных.
С помощью таблицы истинности определяются все логические операции над высказываниями:
X |
Y |
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Пример. Рассуждение «если инвестиции на текущий год не изменятся (A), то возрастет расходная часть бюджета (B) или возникнет безработица (C), а если возрастет расходная часть бюджета, то налоги не будут снижены (D) и, наконец, если налоги не будут снижены и инвестиции не изменятся, то безработица не возникнет».
В этом рассуждении есть четыре повествовательных предложения, которые следует заменить пропозициональными переменными и формально описать суждение. Тогда формула сложного рассуждения имеет вид:
F =(A(BC)) (BD) ((DA) ).
Для различных значений истинности пропозициональных переменных и подформул, построенных на логических связках, можно последовательно определить значение истинности формулы F. Ниже представлена таблица истинности для этого рассуждения.
A |
B |
C |
D |
C |
41 |
23 |
17 |
24 |
65 |
89 |
1110 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
Для удобства записи любой подформулы и формулы каждый столбец пронумерован и логические операции выполняются с индексами столбцов.
ПФ называется тождественно истинной, общезначимой или тавтологией, если она принимает значение 1 на всех наборах значений переменных. Для обозначения того, что ПФ F есть тавтология используют запись ├ F.
ПФ называется тождественно ложной или противоречием, если она принимает значение 0 на всех наборах значений переменных.
ПФ называется выполнимой или опровержимой, если на некоторых наборах значений переменных она принимает значение 1, а на остальных – 0.
Тип ПФ можно определить с помощью таблицы истинности.
Пример. Определить тип ПФ . Для определения типа ПФ составим таблицу истинности
X |
Y |
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
Как видно из таблицы истинности, данная ПФ является тождественно ложной, так как принимает значение 0 на всех наборах переменных.