16 статей
Сейчас мы познакомимся с шестью основными логическими операциями. Каждая из них имеет несколько названий и обозначений.
|
Названия операции |
Возможные обозначения |
|
Отрицание, инверсия. |
`-, ~|, 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)`.
Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.
