Реферат: Булева алгебра

При использовании нескольких операций последовательно порядок выполнения отдельных операции обозначается скобками; например, ~(р) А q) (иногда скобки опускаются). Например, вместо выражения (7p)/\q пишется 7р /\ q при предварительном пояснении, что в случае появления выражения без скобок знак относится только к следующему знаку.

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

Любая логическая операция может быть выражена через операции от­рицания и конъюнкции.

НЕКОТОРЫЕ ДРУГИЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

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

В области одномерных логических операций фактический интерес пред­ставляет только отрицание.

дизъюнкция

Операция называется дизъюнкцией и обозначается символом «p\/q» (иначе ее называют альтернацией, адъюнкцией, логическим сложением), или «р + q». Дизъюнкция выражается с помощью операций конъюнкции и отрицания.

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

(Союз «или» в таком случае применяется в значении допущения, если допускается правильность обоих высказываний). Например: «выпал дождь или полили парк». Поэтому такое соединение двух высказываний также называется дизъюнкцией. (Символ «V» читается также как «или»).

Операция конъюнкция выражается с помощью операций дизъюнкции.

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

«ни-ни»

ИМПЛИКАЦИЯ

Операция «р влечёт q» и называется имплика­цией (с предварительным членом р и с последующим членом q).

Допустим, что если р = п, то значение выражения р влечёт q будет или п, или л в зависимости от того, является ли значение q п, или л. Это анало­гично тому, что высказывание типа «если А, то В», в котором первый член А является правильным, считается или правильным, или ложным в за­висимости от того, правильный или ложный второй его член В. Поэтому соединению типа «если А, то В» соответствует импликация в области ло­гических значений. Но в то же время при ложном высказывании А пред­ложение типа «если А, то В» может вообще не считаться высказыванием Например: если горит лампочка, то лифт работает.

Если высказывание «горит лампочка» правильно, то правильностью высказывания «лифт работает» однозначно решается правильность выше­приведенного предложения. Но если высказывание «горит лампочка» ложно, то ничего нельзя сказать о правильности вышеприведенного предложения. Можно сказать : надо подождать, пока лампочка загорится Приведем пример, в котором не будет даже возможности «подождать»:

Если 2 * 2 = 5, то Дунай является европейской рекой. Если принять то, что соединение типа «если . . .то» соответствует операции импликации, при соблюдении последнего тождества высказывание «если А, то В» вы­ражалось бы с помощью операций конъюнкции и отрицания в следующем виде : «неправильно, что : А и не В» (здесь присутствует выражение «не В» вместо выражения «неправильно, что В»; таким образом, ясно, что выражение «неправильно, что», расположенное в начале высказывания, относится не только к Л, но и к выражению «А и не В»). В соответствии с этим приведенные выше два предложения в примере могут быть пере­формулированы следующим образом:

а) Неправильно, что горит лампочка и лифт не работает.

б) Неправильно, что 2 * 2 = 5 и Дунай не является европейской рекой. Если выражение «горит лампочка» ложно, то ложно и выражение «лампочка горит и лифт не работает», а отрицание его — по а) — является правильным. Выражение. «2 * 2 = 5» ложно, ложно также и выражение «Дунай не является европейской рекой»; их конъюнкция — также ложна, а отрицание этой конъюнкции — по б) — является правильным. Здесь нет противоречия по сравнению с обычным пониманием вещей, так как обычно не обращают внимание на правильность сложного пред­ложения типа «если . . . то» в том случае, когда первый член соединения является ложным.

Выражения вида «если А, то В» можно считать синонимами выражений вида «неправильно, что: «А и не В»; они называются импликациями (с предварительным членом А, с последующим членом В); для их обо­значения применяется символ А влечёт В.

Представленное в области логических значений понятие импликации типа р влечёт q соответствует понятию вышеприведенной операции высказы­вания.

Операции на высказываниях, выражаемые с помощью союзов и частиц, сформулированы недостаточно точно ; в большинстве случаев, они до некоторой степени двусмысленны. По всей вероятности распознавание операций конъюнкции и отрицания наименее проблематично в их грамма­тической форме представления. Поэтому большое значение имеет воз­можность выражения любой логической операции через операции конъ­юнкции и отрицания. Как было показано выше, это позволило нам истолковать образование сложного предложения вида «если . . . то» как операцию.

Упоминаются еще некоторые грамматические синонимы операции «А влечёт В»: «В, если только Л», «Только тогда А, если В», «Достаточным условием В является А», «Необходимым условием А является В», «В если не А».

И конъюнкция и дизъюнкция выражаются с помощью операций импли­кации и отрицания.

Поэтому любая логическая операция может быть выражена с помощью операций отрицания и импликации.

ЭКВИВАЛЕНТНОСТЬ

Последний вид выражения операции эквивалентности.

Так как высказывание p эквивалентно q = n тогда и только тогда, когда p = q, то данная логическая операция соответствует образованию сложного предложения вида «А тогда и только тогда, когда В». Понимание и логи­ческое значение предложения такого характера, образованного из двух любых высказываний, иногда затруднительно для восприятия человека, как и понимание предложения вида «если . . . то». Например, «2 < 3 тогда и только тогда, если светит солнце».

Поэтому данное предложение понимается операцией калькуляции высказываний исключительно в том случае, если считать его синонимом высказываний вида «неправильно, что А и не В, и, неправильно, что не А и В». В этом случае данная операция «А влечёт В» и называется эквивалентностью.

Часто встречаются следующие синонимы данной операции: «Для А необходимо и достаточно б», «А именно тогда, когда В».