5795-1 (589824), страница 7

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

Текст из файла (страница 7)

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

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

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

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

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

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

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

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

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

Примеры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отметим в этой связи, что так называемое нестрогое неравенство а 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) (с а) описывает, учитывая определение входящих в нее связок, булеву функцию, задаваемую следующей таблицей:

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

a b ( a) b;

a b (a b) ( a b),

которые позволяют повсеместно заменить связки , на , , .

Если мы теперь имеем булевы функции {F (x_l, х₂, ..., х_n), G (х₁, х₂, ..., х_n)} от n переменных, то действие связок над ними определяется естественным образом:

F (x_l, x₂, ..., х_n) G (х₁, x₂, ..., х_n), F (x_l, x₂, ...,х_n) G (x_l, x₂, ..., х_n), F (x_l, x₂, ..., х_n) – это такие булевы функции, которые принимают значения, предписываемые соответствующими таблицами для каждого возможного значения аргументов. Кратко: булевы операции так переносятся на булевы функции, как действия арифметики переносятся на обычные функции числовых аргументов. Вообще имеет место далеко идущая аналогия между обычной алгеброй чисел и числовыми функциями, с одной стороны, и высказываниями и булевыми функциями – с другой. При этом можно отметить, что в одном определенном смысле алгебра булевых функций проще алгебры числовых функций: если рассматривать лишь функции некоторого конечного числа аргументов, то таких функций лишь конечное число. Поэтому выкладки с булевыми функциями вполне доступны пониманию школьников старших классов.

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

Выпишем законы булевой алгебры. Большими латинскими буквами А, В, ..., X, Y, Z мы обозначим объекты, над которыми осуществляются булевы операции , , . Для определенности будем считать, что эти объекты – булевы функции некоторого фиксированного числа переменных. Среди них есть два особых элемента: 1, 0. Это соответственно функции, принимающие для всех аргументов значения 0 и 1 (постоянные функции – нуль и единица). Тогда

А В = В А, A B = B A

A (В C) = (А В) C A (В C) = (А В) C

A A = A A A = A

A 1 = A A 1 = A

A 0 = 0 A 0 = A

(A B) = A B (A B) = A B

A (B C) = (A B) (A C) A (B C) = (A B) (A C)

A = A

Характеристики

Список файлов ВКР