17 статей
Сейчас мы познакомимся с шестью основными логическими операциями. Каждая из них имеет несколько названий и обозначений.
|
Названия операции |
Возможные обозначения |
|
Отрицание, инверсия. |
`-, ~|, not` |
|
Конъюнкция, логическое умножение, операция И, операция AND. |
`&, ^^, *,` по аналогии с алгебраическим умножением может никак не обозначаться
|
|
Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR. |
`|``, vv, +` |
|
Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`. |
`o+, Delta` |
|
Эквивалентность, эквиваленция, равенство, равнозначность. |
`iff, -=` |
|
Импликация, следование, следствие |
`=>, ->` |
Теперь для того чтобы строго определить эти логические операции, нам нужно для каждой из них выписать таблицу истинности. Все перечисленные операции кроме отрицания имеют два операнда. Знак операции в выражениях пишется между операндами (как в алгебре чисел). Операция отрицания имеет один операнд и в выражениях записывается либо в виде черты над операндом, либо в виде символа «приставка» слева от операнда.
Для того, чтобы не путаться и гарантированно перебрать все возможные комбинации значений операндов, принято записывать их в лексикографическом порядке (условно считается, что «ложь» `<` «истина»).
Таблица истинности для конъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb0` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для дизъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb1` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для строгой дизъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb1` |
|
`1` |
`1` |
`bb0` |
Таблица истинности для эквивалентности
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb1` |
|
`0` |
`1` |
`bb0` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для импликации
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb1` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для отрицания
|
Значение операнда |
Значение операции |
|
`0` |
`bb1` |
|
`1` |
`bb0` |
Теперь осталось лишь установить соответствие между логическими операциями и логическими связками в русском языке.
|
Логическая операция |
Логические связки в русском языке |
|
Отрицание |
Неверно что… |
|
Конъюнкция |
и, а, но, а также, при этом, одновременно с этим, хотя |
|
Дизъюнкция |
Или |
|
Строгая дизъюнкция |
или, либо |
|
Эквивалентность |
Тогда и только тогда когда, необходимо и достаточно чтобы |
|
Импликация |
если то, необходимо чтобы, достаточно чтобы |
Обратите внимание, что союз ИЛИ может означать, как строгую, так и нестрогую дизъюнкцию. Его интерпретация зависит от содержания (!!!) высказывания.
Рассмотрим высказывание: «Мы идём в кино в субботу или в воскресение». Здесь два простых высказывания: «Мы идём в кино в субботу» и «Мы идём в кино в воскресение». Между ними стоит союз ИЛИ, который можно интерпретировать двояко. В данном случае очевидно, что мы можем пойти в кино и в субботу, и в воскресение, поэтому дизъюнкция будет нестрогая. Возьмём две логические переменные – `p` и `q` и присвоим им простые высказывания. Тогда исходное высказывание в формализованном виде будет выглядеть, как `bb(pvvq)`.
Рассмотрим высказывание: «Я сейчас на севере Москвы или на юго-западе Москвы». Здесь тоже два простых высказывания, которые связаны союзом ИЛИ. Но в этом случае союз ИЛИ интерпретируется, как строгая дизъюнкция, поскольку нельзя одновременно находиться в двух местах. Таким образом, если снова взять логические переменные `p` и `q`, то получится следующая логическая формула: `bb(p"o+q)`.
Рассмотрим высказывание: «Для того чтобы четырёхугольник был квадратом, необходимо, чтобы все его стороны были равны». Здесь два простых высказывания: «Четырёхугольник является квадратом» и «Все стороны четырёхугольника равны». Присвоим их соответственно логическим переменным `p` и `q`. Логическая связка «необходимо, чтобы» - это импликация. Весь вопрос в том, что из чего следует. (Какая запись правильная: `bbp -> bbq` или `bbq ->bbp`?) Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.
1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.
2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).
3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.
4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.
Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)`.
Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.
Итак, мы познакомились с понятием логического выражения и увидели, каким образом его строить по высказыванию на русском языке. Следующий шаг – изучение преобразований логических выражений.
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.<
это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:
1) Законы поглощения констант
x `vv` 0 = x, x & 1 = x;
2) Законы поглощения переменных
x `vv` 1 = 1, x & 0 = 0;
3) Законы идемпотентности
x & x = х, x `vv` x = х;
4) Закон двойного отрицания
$$ \stackrel{=}{\mathrm{x}}$$ = x;
5) Закон противоречия
x & $$ \stackrel{-}{\mathrm{x}}$$ = 0;
6) Закон исключённого третьего
x `vv` $$ \stackrel{-}{\mathrm{x}}$$ = 1;
Приведённые законы ещё называют аксиомами алгебры логики. Истинность этих и всех последующих законов легко можно установить, построив таблицу истинности для левого и правого логического выражения.
Переходим к группе законов, которые практически аналогичны законам алгебры чисел.
7) Законы коммутативности
x & y = y & x,
x `vv` y = y `vv` x;
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
8) Законы ассоциативности
(x & y) & z = x & (y & z),
(x`vv`y) `vv` z = x `vv` (y `vv` z);
9) Законы дистрибутивности
x & (y `vv` z) = (x & y) `vv` (x & z),
x `vv` (y & z) = (x `vv` y) & (x `vv` z);
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.
10) Законы де Моргана
$$\style{font-family:'Courier New'}{\overline{\mathrm x\&\mathrm y}=\overline{\mathrm x}\vee\overline{\mathrm y},}$$
$$\style{font-family:'Courier New'}{\overline{\mathrm x\vee\mathrm y}=\overline{\mathrm x}\;\&\;\overline{\mathrm y};}$$
11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)
x `vv` (x & y) = x;
x & (x `vv` y) = x.
Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.
|
`x` |
`Y` |
`x&y` |
`bar(x&y)` |
`barx` | `bary` |
`barx vv bary` |
|
`0` |
`0` |
`0` |
`1` |
`1` |
`1` |
`1` |
|
`0` |
`1` |
`0` |
`1` |
`1` |
`0` |
`1` |
|
`1` |
`0` |
`0` |
`1` |
`0` |
`1` |
`1` |
|
`1` |
`1` |
`1` |
`0` |
`0` |
`0` |
`0` |
Так как результирующие столбцы совпали, то выражения, стоящие в левой и правой частях закона, равносильны.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Наше начальное выражение: x `vv` (x & y). Выносим `x` за скобки и получаем следующее выражение:
x &(1 `vv` y). Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x.
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
12) Закон преобразования импликации
`"x" -> "y" = bar("x") vv "y"`
Необходимо ещё отметить, что в сложных логических выражениях у операций есть порядок приоритетов.
1) Отрицание
2) Конъюнкция
3) Дизъюнкция, строгая дизъюнкция, эквивалентность
4) Импликация
