Т. А. Сливина математическая логика и теория алгоритмов

§ 1. Логические операции над высказываниями

Над высказываниями можно выполнять логические операции, которые играют важную роль в математических доказательствах.

Отрицанием высказывания х называется новое высказывание, которое является истинным, если х – ложно и ложным, если х – истинно.
Обозначается и читается «не х».
Логические значения высказывания можно представить следующей таблицей, которую в дальнейшем будем называть таблицей истинности:

х
1	0
0	1

Если х – высказывание, то – тоже высказывание. Можно образовать отрицание высказывания т. е. которое называется двойным отрицанием. Значения и совпадают.

Коньюнкцией двух высказываний x и y (логическим умножением) называется новое высказывание, которое считается истинным, если оба высказывания x и y истинны, и ложным, если хотя бы одно из них ложно.
Обозначается символом x y или (x & y). Читается «x и y».
Логические значения коньюнкции описываются следующей таблицей истинности:

x	y	x y
1	1	1
1	0	0
0	1	0
0	0	0

Из определения операции коньюнкции и отрицания следует, что высказывание всегда ложно.

Дизьюнкцией двух высказываний x и y (логическим сложением) называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y – истинно, и ложным, если они оба – ложны.
Обозначается . Читается «x или y».
Логические значения описываются следующей таблицей истинности:

x	y
1	1	1
1	0	1
0	1	1
0	0	0

Из определения операции дизьюнкции и отрицания следует, что высказывание всегда истинно.

Импликацией двух высказываний x и y называется новое высказывание, которое считается ложным, если x – истинно, а y – ложно, и истинным, во всех остальных случаях.
Обозначается Читается «если x, то y» или «из x следует y».
Высказывание x называют условием, а y – следствием или заключением.
Логические значения этой операции описываются следующей таблицей истинности:

x	y
1	1	1
1	0	0
0	1	1
0	0	1

Импликация играет важную роль в математических доказательствах, так как многие теоремы в условной форме формулируются «если x, то y».

Эквиваленцией (или эквивалентностью) двух высказываний x и y называется новое высказывание, которое считается истинным, когда оба высказывания x и y либо одновременно истинны, либо одновременно ложны, и ложным, во всех остальных случаях.
Обозначается Читается «для того, чтобы x, необходимо и достаточно, чтобы y» или «x тогда и только тогда, когда y».
Логические значения этой операции описываются следующей таблицей истинности:

x	y
1	1	1
0	0	1
1	0	0
0	1	0

Логические операции играют важную роль в математических доказательствах, так как значительное число теорем формулируется в условной форме «если х, то у» или в форме необходимых и достаточных условий «для того чтобы x, необходимо и достаточно чтобы y».

§ 2. Формулы логики высказываний. Основные равносильности
и преобразования

Определим понятие формулы логики высказываний.

Алфавит логики высказываний состоит из трех групп символов: высказывательные переменные a, b, c, d, …, x, y, z; логические символы , , →, ↔, −; символы скобок ( , ). Словом в алфавите называется произвольная конечная последовательность символов.
Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:
1) любая высказывательная переменная – формула;
2) если А и В формулы, то слова , , , , – формулы;
3) только те слова являются формулами, для которых это следует из 1) и 2).


Например:
( ) или
Скобки указывают порядок выполнения действий.

Скобки в формулах можно опускать, придерживаясь следующего порядка выполнения действий: коньюнкция, дизьюнкция, импликация и эквиваленция.

Пример.
1) равносильно
2) равносильно .
Логическое значение формулы полностью определяется логическими значениями входящих в нее элементарных высказываний.
Пример.
При x = 1, y = 1, z = 0 формула
Логическое значение формулы изменяется в зависимости от изменений значений элементарных высказываний, входящих в формулу. Все возможные логические значения формулы могут быть описаны полностью с помощью таблицы истинности.
Пример.
Таблица истинности логических значений формулы будет следующая:

x	y
1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	1	0	0
0	0	1	1	1	0	0

Если формула содержит n элементарных высказываний, то она принимает 2ⁿ значений. Таблица истинности будет содержать 2ⁿ строк.

Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения на любом наборе значений, входящих в формулы элементарных высказываний.
Обозначается равносильность ≡, т. е. A ≡ B.
Пример.
Следующие формулы являются равносильными:



Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.
Пример.
Следующие формулы являются тавтологиями:

Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.
Пример.
Формула является тождественно ложной.
Отношение равносильности обладает следующими свойствами: оно рефлексивно, симметрично и транзитивно.
Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула – тавтология, и обратно, если формула – тавтология, то формулы А и В равносильны.
Равносильности алгебры логики используются для того, чтобы любую формулу алгебры логики можно заменить равносильной ей формулой.
Важнейшие равносильности алгебры логики можно разбить на три группы.