Логические операции

¬А, в языках программирования Паскаль и Бейсик — как not A, в языке Си — как !A.

Операцию “НЕ” можно задать в виде таблицы:

Операция «ИЛИ»

Высказывание «Сейчас идёт дождь или форточка открыта» истинно тогда, когда истинно хотя бы одно из входящих в него высказываний (в том числе когда истинны оба высказывания одновременно).

Операции «исключающее ИЛИ» соответствует русская пословица «Либо пан, либо пропал», где выполнение обоих условий одновременно невозможно. Операция «исключающее ИЛИ» в алгебре логики обозначается знаком

, в языке Паскаль — хог (А хог В), а в языке Си — знаком ^ (А ^ В). Эту операцию можно представить через базовые операции (НЕ, И, ИЛИ) следующим образом:

В = ¬ А •В+А •¬ В.

Пока мы не можем вывести это равенство, но можем доказать его (или опровергнуть, т. е. доказать, что оно неверное). Для этого достаточно для всех возможных комбинаций А и В вычислить значения выражения, стоящего в правой части равенства, и сравнить их со значениями выражения А

В для тех же исходных данных. Поскольку провести такие вычисления в уме достаточно сложно, сначала вычислим значения ¬А, ¬В, ¬А • В и А ¬ В, а потом уже ¬А • В+ А •¬В.

В таблице истинности появятся дополнительные столбцы для промежуточных результатов.

Легко видеть, что выражение ¬А • В + А •¬ В совпадает с А исключающее ИЛИ В для всех комбинаций значений. Это значит, что равенство доказано.

Операция «исключающее ИЛИ» иначе называется разделительной дизъюнкцией (это значит «один или другой, но не оба вместе») или сложением по модулю два. Второе название связано с тем, что её результат равен остатку от деления арифметической суммы А + В на 2

Здесь mod обозначает операцию взятия остатка от деления.

В = 1 тогда и только тогда, когда А В.

Операция «исключающее ИЛИ» обладает интересными свойствами. По таблице истинности несложно проверить, что

А

0 = А, А 1 = ¬А, А А = 0.

Для доказательства этих равенств можно просто подставить в них А = 0 и А = 1. Теперь докажем, что

(А

В) В = А. (1)

Подставляя в левую часть В = 0, получим (А

0) 0 = А 0 = А. Аналогично для В = 1 имеем (А 1) 1 = ¬А 1 = А. Это означает, что формула (1) справедлива для любых значений В. Отсюда следует важный вывод: если два раза применить операцию «исключающее ИЛИ» с одним и тем же значением переменной, мы восстановим исходное значение. В этом смысле «исключающее ИЛИ» — обратимая операция (кроме неё обратима также операция «НЕ» — если применить её дважды, мы вернёмся к исходному значению).

Формулу (1) можно использовать для шифрования данных. Пусть А и В — двоичные коды одинаковой длины. Чтобы зашифровать данные (А), используя ключ В, надо применить операцию «исключающее ИЛИ» отдельно для каждого разряда А и В. Для расшифровки ещё раз применяется «исключающее ИЛИ» с тем же ключом В. Нужно отметить, что такой метод шифрования очень нестойкий: для достаточно длинных текстов его легко «взломать» частотным анализом.

Импликация

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

В («если А, то В», «из А следует В»).

Таблица истинности операции импликации:

Разобраться с импликацией будет легче, если мы рассмотрим конкретное высказывание, например, такое: «Если хорошо работаешь, то получаешь большую зарплату». Обозначим буквами два простых высказывания: А — «Вы хорошо работаете» и В — «Вы получаете большую зарплату». Понятно, что если высказывание А

В истинно, то все, кто хорошо работают (А = 1), должны получать большую зарплату (В = 1). Если же кто-то работает хорошо (А = 1), а получает мало (В = 0), то высказывание А

В ложно.

Лодыри и бездельники (А = 0) могут получать как маленькую (В = 0), так и большую зарплату (В = 1), это не нарушает истинность высказывания А

В. Иногда, определяя импликацию, говорят так: из истины следует истина, а из лжи — что угодно. Это значит, что при ложном высказывании А высказывание В может быть как ложно, так и истинно.

Нужно обратить внимание на разницу между высказываниями вида «если А, то В» в обычной жизни и в алгебре логики. В быту мы чаще всего имеем в виду, что существует причинно-следственная связь между А и В, т. е. именно А вызывает В. Алгебра логики не устанавливает взаимосвязь явлений; истинность высказывания А

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

Импликация чаще всего используется при решении логических задач, так как формулировку вида «если А, то В» можно записать как А

В = 1.

Для импликации (в отличие от других изученных ранее операций с двумя переменными) не действует переместительный закон: если в записи А

В поменять местами А и В, то результат изменится: А

В В А. Внешне это видно по стрелке, которая указывает «направление».

Импликацию можно заменить на выражение, использующее только базовые операции (здесь — только «НЕ» и «ИЛИ»):

А

В = ¬А + В.

Доказать это равенство вы уже можете самостоятельно.

Эквивалентность

Эквивалентность (или эквиваленция, равносильность) — это логическая операция, которая соответствует связке «тогда и только тогда». Высказывание А

В истинно в том и только в том случае, когда А = В

Возможно, вы заметили, что эквивалентность — это обратная операция для операции «исключающее ИЛИ» (проверьте по таблицам истинности), т. е. А

В = ¬(А

В).

Здесь черта сверху, охватывающая всё выражение в правой части равенства, означает отрицание (инверсию), которое применяется к результату вычисления выражения А

В, а не к отдельным высказываниям.

Можно заменить эквивалентность выражением, которое включает только базовые логические операции:

А

В = ¬А •¬В + А •В.

Это равенство вы можете доказать (или опровергнуть) самостоятельно.

Другие логические операции

Таблицы истинности операций с двумя переменными содержат 4 строки и отличаются только значением последнего столбца. Поэтому любая новая комбинация нулей и единиц в этом столбце даёт новую логическую операцию (логическую функцию). Всего их, очевидно, столько, сколько существует четырёхразрядных двоичных чисел, т. е. 16 = 24. Из тех операций, которые мы ещё не рассматривали, наиболее интересны две — штрих Шеффера («И-НЕ», англ, nand — «not and»,):

А|В = ¬(А•В)

и стрелка Пирса («ИЛИ-HE», англ, nor — «not or»):

А

Особенность этих операций состоит в том, что с помощью любой одной из них можно записать произвольную логическую операцию. Например, операции «НЕ», «И» и «ИЛИ» (базовый набор) выражаются через штрих Шеффера так:

¬А = А | А, А• В = (А | В) | (A | В),

А + В = (А | A) | (В | В).

Эти равенства можно доказать через таблицы истинности.