Содержание и значение математической символики (стр. 11 из 15)

4.1.1 Определения основных логических связок

а) Отрицание (знак ù ). Если а – высказывание, то ùа (читается: «не а») также высказывание; оно истинно или ложно в зависимости от того, ложно или истинно высказывание а.

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

a	ùa
и	л
л	и

Мы видим, что операция ù в теории высказываний вполне соответствует понятию отрицания в обыденном смысле слова. Если, например, а – высказывание «Число три делит число шесть», то отрицанием ùа этого высказывания будет «Число три не делит число шесть». Высказывание а при этом истинно, высказывание ùа, – ложно.

Если же в качестве высказывания а взять какое-нибудь ложное высказывание, например «Число три делит число пять», то его отрицание ùа будет высказывание «Число три не делит число пять» - истинное высказывание.

б) Конъюнкция. В качестве знака для конъюнкции мы будем употреблять знак Ù (можно также &).

Если а и b - высказывания, то а Ùb (читается: «а и b») – новое высказывание; оно истинно тогда и только тогда, когда а истинно и b истинно.

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

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

Значение истинности сложного высказывания а Ùb задается матрицей

ba	и	л
и	и	л
л	л	л

Как видно, определение операции конъюнкции вполне соответствует обыденному значению союза «и»:

в) Дизъюнкция. В качестве знака для дизъюнкции мы будем употреблять знак Ú.

Если а и b – высказывания, то а Úb (читается: «а или b») – новое высказывание, оно ложное, если а и b ложны; во всех остальных случаях а Úb истинно.

Таким образом, матрица истинности для операции дизъюнкции выглядит так:

ba	и	л
и	и	и
л	и	л

Операция дизъюнкции довольно хорошо соответствует обыденному значению союза «или».

Примеры.

«Три делит пять или три больше шести» ложно;

«Три делит шесть или три больше шести» истинно;

«Три делит шесть или три меньше шести» истинно.

г) Импликация. В качестве знака для импликации будем употреблять знак Þ.

Если а и b – два высказывания, то а Þb (читается: «а имплицирует b») – новое высказывание; оно всегда истинно, кроме того случая, когда а истинно, а b ложно.

Матрица истинности операции импликации следующая:

ba	и	л
и	и	л
л	и	и

В импликации а Þb первый член а называется антецедентом, второй b – консеквентом.

Операция Þ описывает в некоторой мере то, что в обыденной речи выражается словами «Если а, то b», «Из а следует b», «а – достаточное условие для b», но на этой аналогии не следует слишком настаивать. Действительно, учитывая определение импликации, данное выше, и интерпретируя выражение а Þb как «если а, то b», мы получаем: «Если дважды два – четыре, то трижды три – девять» – истинное высказывание; «Если дважды два – пять, то трижды три – восемь» – истинное высказывание и только высказывание типа «Если дважды два – четыре, то трижды три – восемь» ложно.

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

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

д) Эквиваленция. Для этой операции мы будем употреблять знак Û. Операция эквиваленции определяется так: если а и b – два высказывания, то а Ûb (читается: «а эквивалентно b»; Û соответствует словесному выражению «...тогда и только тогда, когда...») – новое высказывание, которое истинно, если либо оба высказывания истинны, либо оба – ложны.

Из этого определения связки Û следует, что ее матрица истинности выглядит так:

ba	и	л
и	и	л
л	л	и

Введенными пятью связками (ù, Ù, Ú, Þ, Û) мы ограничимся.

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

Отметим в этой связи, что так называемое нестрогое неравенство а £b (читается: a меньше или равно b») представляет собой дизъюнкцию (а < b) Ú (a = b); оно истинно, если истинно по меньшей мере одно из входящих в него простых высказываний. Хорошими примерами сложных высказываний, встречающихся в школьной практике, являются так называемые двойные неравенства. Так, формула а < b < с означает (а < b) Ù (b < с), а, например, а < b£c означает сложное высказывание (а < b) Ù ((b < c) Ú (b = c)).

Построение сложных высказываний делается аналогично тому, как в элементарной алгебре с помощью операций сложения, вычитания, умножения и деления строятся сколь угодно сложные рациональные выражения. А именно, предположим, что мы уже построили два каких-нибудь сложных высказывания, которые мы ради удобства сокращенно обозначим большими латинскими буквами А и В (при этом мы условимся, что элементарные высказывания следует рассматривать как частный случай сложных). Тогда новые высказывания можно получить, соединив А и В одним из знаков Ù, Ú, Þ, Û или же построив высказывание ùА и заключив результат в скобки. Сложными высказываниями будут, например, высказывания следующего вида:

((а Þb) Ù (с Ú а)); ((а Þb) Û (с Þùа)).

При этом предполагается, что встречающиеся здесь буквы являются сокращенными обозначениями каких-либо высказываний.

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

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

((bÚ с) Û (bÙa))

и пусть входящие в него элементарные высказывания имеют следующие значения истинности: а = л, b = и, с = и. Тогда bÚ с = и, bÙa = л, так что (( bÚ с) Û (bÙ а)), т. е. рассматриваемое высказывание ложно.

4.1.2 Высказывания и булевы функции

Одной из основных задач алгебры высказываний является установление значения истинности сложных высказываний в зависимости от значения истинности входящих в них простых высказываний. Для этого целесообразно рассматривать сложные высказывания как функции входящих в них простых высказываний. С другой стороны, так как значение истинности (и или л) сложного высказывания зависит по определению логических связок не от самих простых высказываний, а лишь от их значения истинности, то можно считать, что любое сложное высказывание определяет функцию, аргументы которой независимо друг от друга принимают значения и или л, а значение самой функции также принадлежит множеству {и, л} (конечно, существенно не то, что речь идет о функциях от нескольких аргументов из множества {и, л} в множество {и, л}, а лишь то, что данные множества двухэлементны. Эти множества зачастую обозначают не через {и, л}, а, например, через {0, 1}, считая, что 1 означает «истину», а 0 – «ложь»).

Такие функции называются булевыми функциями (по имени Д. Буля). Например, формула F (а, b, с) = (а Ùb) Þ (с Ù а) описывает, учитывая определение входящих в нее связок, булеву функцию, задаваемую следующей таблицей:

а	b	с	F(a, b, с)	а	b	с	F(a, b, с)
и	и	и	и	л	и	и	и
и	и	л	л	л	и	л	и
и	л	и	и	л	л	и	и
и	л	л	и	л	л	л	и

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

– Оно очень быстро растет с ростом n. Изучение свойств булевых функций имеет большее значение как для алгебры и математической логики, так и для их приложений в кибернетике и теории автоматов. Естественно распространить определение высказывательных связок, так как мы их определили выше, на булевы функции. Мы ограничимся рассмотрением лишь связок Ù, Ú, ù называемых булевыми связками (или булевыми операциями). Такое ограничение оправдано тем, что, как легко проверить, связки Þ и Û могут быть выражены через другие булевы связки. При помощи таблиц истинности, приведенных выше, легко проверяются следующие тождества: