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

Существует 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}$ строк.