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

Существует 5 логических операций:

Отрицание высказывания $X$

Обозначается $\bar { X } $, читается как "не $X$" или "неверно, что $X$". Логические значения высказывания $\bar { X } $ можно описать с помощью таблицы

$x$	$\bar { x } $
1	0
0	1

Таблицы такого вида принято называть таблицами истинности.

Конъюнкция высказываний $X$ и $Y$

Конъюнкцией двух высказываний $X$, $Y$ называется высказывание, которое считается истинным, если оба высказывания $X$, $Y$ истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний $X$, $Y$ обозначается символом $X$&$Y$ или $X$$\wedge$$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$ обозначается символом $X$$\vee$$Y$, читается «$X$ или $Y$», где «или» используется в неразделительной форме. Высказывания $X$ и $Y$ называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

$x$	$y$	$x\vee y$
1	1	1
1	0	1
0	1	1
0	0	0

Например, высказывание «В треугольнике $DFE$ угол $D$ или угол $E$ острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике $DFE$ угол $D$ острый», «В треугольнике $DFE$ угол $E$ острый».

Импликация высказываний $X$ и $Y$

Импликацией двух высказываний $X$ и $Y$ называется высказывание, которое считается ложным, если $X$ истинно, а $Y$ - ложно, и истинным во всех остальных случаях.

Импликация высказываний $X$ и $Y$ обозначается символом $X \rightarrow Y$, читается «если $X$, то $Y$» или «из $X$ следует $Y$». Высказывание $X$ называют посылкой, высказывание $Y$ – заключением.

Логические значения операции импликации описываются следующей таблицей истинности:

$x$	$y$	$x\rightarrow y$
1	1	1
1	0	0
0	1	1
0	0	1

Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если ..., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание $X$ ложно, то высказывание «Если $X$, то $Y$» вообще не имеет смысла. Кроме того, строя предложение вида «если $X$, то $Y$» в обыденной речи, мы всегда подразумеваем, что предложение $Y$ вытекает из предложения $X$.

Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

Эквиваленция высказываний $X$ и $Y$

Эквиваленцией { или эквивалентностью } двух высказываний $X$ и $Y$ называется высказывание, которое считается истинным, когда оба высказывания $X$, $Y$ либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний $X$, $Y$ обозначается символом $X$$\leftrightarrow $$Y$, читается «для того, чтобы $X$, необходимо и достаточно, чтобы $Y$» или «$X$ тогда и только тогда, когда $Y$». Высказывания $X$, $Y$ называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:

$x$	$y$	$x\leftrightarrow y$
1	1	1
1	0	0
0	1	0
0	0	1

Например, эквиваленция «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный тогда и только тогда, когда $\angle P = \angle Q$» является истинной, так как высказывания «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный» и «В треугольнике $SPQ$ с вершиной $S$ и основанием $PQ$ $\angle P = \angle Q$» либо одновременно истинны, либо одновременно ложны.

Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.

Операция «Штрих Шеффера»

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом $X|Y$ и определяется следующей таблицей истинности:

$x$	$y$	$x|y$
1	1	0
1	0	1
0	1	1
0	0	1

Штрих Шеффера - функция, принимающая значение ложь, если $X$ – истинно и $Y$ – истинно. Очевидно, имеют место равносильности:

1) $\overline { X } \equiv X|X$

2) $X\wedge Y \equiv (X|Y)|(X|Y)$

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

Отметим, что $X|Y\equiv\overline { X\wedge Y } $.

Стрелка Пирса { функция Вебба }

Стрелка Пирса { функция Вебба } $X \downarrow Y$ – функция, принимающая значение истина, когда $X$ – ложно и $Y$ – ложно.

$x$	$y$	$x\downarrow y$
1	1	0
1	0	0
0	1	0
0	0	1

Отметим, что $X\downarrow Y = \overline { X } \wedge \overline { Y } = \overline { X \vee Y } $

Cумма Жегалкина

Функция сложение по модулю 2 { функция разноименности, или сумма Жегалкина } $X\oplus Y$ - функция, принимающая значение истинно, когда $X$ и $Y$ принимают противоположные значения.

$x$	$y$	$x\oplus y$
1	1	0
1	0	1
0	1	1
0	0	0

Отметим, что $X\oplus Y = (\overline { X } \wedge Y)\vee (X\wedge\overline { Y } )$

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

$ \neg$− не;

$\And $, $\wedge $− и;

$\vee $− или;

$\rightarrow $− влечет;

$\sim $, $\leftrightarrow $− эквивалентно;

$\oplus $− либо, либо.

Практика

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний $X, Y, Z$ можно построить высказывания

$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline { Y\vee (X\wedge Z) } )$

Первое из них есть дизъюнкция конъюнкции $X, Y$ и отрицания выказывания $Z$, а второе высказывание есть импликация, посылкой которой является высказывание $X$, а заключением - отрицание дизъюнкции высказывания $Y$ и конъюнкции высказываний $X, Z$.

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

Высказывания обозначаются большими буквами латинского алфавита $A, B, C, …$

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

1. Для отрицания скобки опускаются;

2. $\And $ имеет приоритет перед $\vee , \rightarrow, \equiv $;

3. $\vee $ имеет приоритет перед $\rightarrow, \equiv $;

В связи с этим формулы

$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline { Y\vee (X\wedge Z) } )$

могут быть записаны так:

$X\wedge Y\vee Z$ и $X\rightarrow \overline { Y\vee X\wedge Z } $

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы $\overline { X\wedge Z } \vee \overline { Z } $ в случае, если $X = 1, Y = 1, Z=0$ будет истина, то есть $\overline { X\wedge Y } \vee \overline { Z } = 1$.

Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Эта таблица будет содержать $2^n$ строк, где $n$ – количество переменных.

Например, для формулы $\overline { X } \vee Y\rightarrow X\wedge \overline { Y } $ таблица истинности имеет вид:

$x$	$y$	$\bar { x } $	$\bar { y } $	$\bar { x } \vee y$	$x\wedge \bar { y } $	$\bar { x } \vee y \rightarrow x \wedge \bar { 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^ { n } $ значений, состоящих из нулей и единиц, или, что тоже, таблица содержит $2^ { n } $ строк.