Логические операции над высказываниями
Существует 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, …$
Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются:
-
Для отрицания скобки опускаются;
-
$\And $ имеет приоритет перед $\vee , \rightarrow, \equiv $;
-
$\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 } $ строк.
Далее:
Класс Te . Теорема о замкнутости Te
Решение задач с помощью алгебры высказываний
Вычисление объёмов
Вычисление криволинейного интеграла первого рода. Примеры
Критерий полноты {формулировка}. Лемма о нелинейной функции
Класс $S$. Теорема о замкнyтости класса $S$
Упрощение логических функций
Теорема о заведомо полныx системаx
Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе
Формула Гаусса - Остроградского
Соленоидальное векторное поле
Частные случаи векторных полей
Определение тройного интеграла. Теорема существования тройного интеграла
Свойства тройного интеграла
Огравление $\Rightarrow $
Комментарии ()