Базовые операции: НЕ, И, ИЛИ

3.2

О чём этот урок

Отдельное высказывание сообщает мало. Настоящие условия почти всегда составные: «вход разрешён, если пароль верный и подтверждён код из SMS», «войти можно по почте или по номеру телефона», «файл скачается, если ссылка рабочая и файл не удалён». Чтобы такие условия можно было считать, а не только проговаривать, нужны операции над истинностью – как сложение и умножение над числами.

Разминка. В интернет-магазине вы ищете наушники: беспроводные, с шумоподавлением. Фильтр можно настроить двумя способами – показать товары, у которых есть оба свойства, или те, у которых есть хотя бы одно. Какой список получится длиннее и почему? К концу урока вы сможете объяснить разницу таблицей из четырёх строк.

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

Отрицание НЕ

Отрицание – унарная (одноместная) операция, которая меняет истинность высказывания на противоположную.

Обозначения: $\lnot A$, Ā, not A. В этом курсе – $\lnot A$. Напомним договорённость: истину записываем как 1, ложь – как 0.

Таблица истинности:

A	$\lnot A$
1	0
0	1

Пример: A = «Сегодня понедельник» (1, если сегодня действительно понедельник). $\lnot A$ = «Сегодня не понедельник» – обязано принять противоположное значение.

Забавное свойство, к которому вернёмся в уроке про законы логики (3.4): двойное отрицание возвращает исходное значение – $\lnot (\lnot A)$ равносильно A.

Конъюнкция И

Конъюнкция – бинарная операция, истинная (1) только тогда, когда оба операнда истинны одновременно.

Обозначения: $A \land B$, $A \cdot B$, иногда просто AB.

Таблица истинности:

A	B	$A \land B$
1	1	1
1	0	0
0	1	0
0	0	0

Конъюнкцию удобно представлять как цепь: если хотя бы одно звено (один из операндов) равно 0 – рвётся вся цепь, результат 0. Пример: «Тест сдан, если решены задача 1 И задача 2» – если хоть одна не решена, тест не сдан.

Дизъюнкция ИЛИ

Дизъюнкция – бинарная операция, истинная (1), если истинен хотя бы один из операндов, в том числе если истинны оба.

Обозначения: $A \lor B$, иногда A+B.

Таблица истинности:

A	B	$A \lor B$
1	1	1
1	0	1
0	1	1
0	0	0

Теперь ответ на разминку. У конъюнкции единица стоит в одной строке из четырёх, у дизъюнкции – в трёх; поэтому фильтр «хотя бы одно свойство» и выдаёт список длиннее, чем «оба свойства сразу».

Обратите внимание на первую строку таблицы: логическое ИЛИ нестрогое («включающее»), оно допускает 1 у обоих операндов сразу – наушники, у которых есть и то и другое, из выдачи не выпадают.

То самое исключающее «или» («одно из двух, но не оба») в логике тоже существует – это отдельная операция XOR, до неё доберёмся в блоке про побитовые операции (6.1).

Порядок действий в формулах

Когда в одном выражении несколько операций, нужен порядок вычисления – как в арифметике, где умножение выполняется раньше сложения. Для логики порядок такой:

Приоритет	Операция
1 (выполняется первой)	$\lnot$ отрицание
2	$\land$ конъюнкция
3 (выполняется последней)	$\lor$ дизъюнкция

Скобки, как обычно, меняют порядок явно.

Например, запись $\lnot A \land B \lor C$ без скобок читается как $(\lnot A \land B) \lor C$, а не как $\lnot (A \land B) \lor C$ или $\lnot (A \land (B \lor C))$ – сначала отрицание, потом умножение-«И», и только потом сложение-«ИЛИ». Это частый источник ошибок: если хотелось отрицать всю конъюнкцию целиком, скобки обязательны.

Запись без скобок и её настоящий смысл

\[ \lnot A \land B \lor C \equiv (\lnot A \land B) \lor C \]

Три базовые операции алгебры логики: НЕ инвертирует, И требует выполнения обоих условий, ИЛИ – хотя бы одного.

Коротко

Отрицание $\lnot A$ – меняет значение на противоположное; операция унарная, у неё один операнд.
Конъюнкция $A \land B$ – истинна, только когда истинны оба операнда.
Дизъюнкция $A \lor B$ – истинна, когда истинен хотя бы один операнд; при обоих истинных она тоже истинна.
Логическое ИЛИ нестрогое: «одно из двух, но не оба» – это другая операция (XOR, блок 6).
Порядок действий без скобок: сначала $\lnot$, потом $\land$, потом $\lor$. Чтобы отрицать конъюнкцию целиком, скобки обязательны.

Проверь себя

Короткие вопросы по теме урока. Попыток сколько угодно, на прохождение блока они не влияют – это проверка для себя.

Проверь себя

Самопроверка: базовые операции НЕ, И, ИЛИ

Решать →

← Что такое логическое высказывание? Сложные операции: импликация и эквивалентность →