§ 2. Логические операции. Формализация высказываний

Сейчас мы познакомимся с шестью основными логическими  операциями.  Каждая  из  них имеет несколько названий и обозначений. 

Названия операции

Возможные обозначения

Отрицание, инверсия.

`-, ~|, 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`

Теперь осталось лишь установить соответствие между логическими операциями и логическими связками в русском языке.

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

Логические связки в русском языке

Отрицание

Неверно что…

Конъюнкция

и, а, но,  а также, при этом,

одновременно с этим, хотя

Дизъюнкция

Или

Строгая дизъюнкция

или, либо

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

Тогда и только тогда когда,

необходимо и достаточно чтобы

Импликация

если то, необходимо чтобы, достаточно чтобы

Обратите внимание, что союз ИЛИ может означать, как строгую, так и нестрогую дизъюнкцию. Его интерпретация зависит от содержания (!!!) высказывания.

Пример 1

 Рассмотрим высказывание: «Мы идём в кино в субботу или в воскресение». Здесь два простых высказывания: «Мы идём в кино в субботу» и «Мы идём в кино в воскресение». Между ними стоит союз ИЛИ, который можно интерпретировать двояко. В данном случае очевидно, что мы можем пойти в кино и в субботу, и в воскресение, поэтому дизъюнкция будет нестрогая. Возьмём две логические переменные – `p` и `q` и присвоим им простые высказывания. Тогда исходное высказывание в формализованном виде будет выглядеть, как `bb(pvvq)`.

Пример 2

Рассмотрим высказывание: «Я сейчас на севере Москвы или на юго-западе Москвы». Здесь тоже два простых высказывания, которые связаны союзом ИЛИ. Но в этом случае союз ИЛИ интерпретируется, как строгая дизъюнкция, поскольку нельзя одновременно находиться в двух местах. Таким образом, если снова взять логические переменные `p` и `q`, то получится следующая логическая формула: `bb(p"o+q)`.


Пример 3

Рассмотрим высказывание: «Для того чтобы четырёхугольник был квадратом, необходимо, чтобы все его стороны были равны». Здесь два простых высказывания: «Четырёхугольник является квадратом» и «Все стороны четырёхугольника равны». Присвоим их соответственно логическим переменным `p` и `q`. Логическая связка «необходимо, чтобы» - это импликация. Весь вопрос в том, что из чего следует. (Какая запись правильная: `bbp -> bbq` или `bbq ->bbp`?)  Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.

1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.

2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).

3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.

4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.

Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)`.

Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.