Операции
булевой алгебры

[предыдущая глава]  [оглавление]  [следующая глава]

Рассмотрим еще раз таблицу из предыдущей главы

A	B	~(A & B)
false	false	true
false	true	true
true	false	true
true	true	false

В правом столбце выписаны четыре константы: true, true, true, false (выделено желтым фоном). Эти константы определяют истинность некоторой формулы, записанной в верхнем правом углу таблицы (подкрашено зеленым).

Подобная таблица задает функцию от двух переменных (в данном случае - A и B). Всего возможно 2⁴ = 16 функций от двух переменных, которые отличаются друг от друга по своим результатам. Аналогично, возможно 2² = 4 функции от одной переменной и 2¹ = 2 функции от нуля переменных. Рассмотрим их по порядку.

Функции от нуля переменных не должны иметь столбцов с переменными. Остается только крайний правый столбец с двумя ячейками. В верхней ячейке будет название функции, а в нижней - ее значение. Поскольку эти простейшие функции всегда совпадают с одной из констант true и false, то в качестве обозначения таких функций удобно использовать те же самые константы:

true true

false false

Теперь рассмотрим функции от одной переменной. Всего их возможно 4:

Таблица истинности	Названия	Обозначения	Читается как...
A false false false true false	ложь	false	"ложь"
A true false true true true	истина	true	"истина"
A A false false true true	A	A	"A"
A ~A false true true false	отрицание инверсия обращение логическое 'НЕ'		"не"

Первая функция всегда дает false. Похоже на функцию false, рассмотренную чуть выше, но эта - функция от одной переменной. В обычной алгебре есть аналогичные функции-константы, например f(x) = 3. А здесь - f(A) = false. Вторая функция - тоже функция-константа от одной переменной f(A) = true. Поскольку значение этих функций всегда равно константе, то их можно обозначать этими самыми константами, ничего от этого не теряя.

В третьей таблице значение функции совпадает со значением переменной. Аналогичная функция в обычной алгебре: f(x) = x. А здесь - f(A) = A. Поскольку значение этой функции совпадает со значением переменной, то ее можно обозначать этой самой переменной.

И только последняя функция, как говорят математики, "нетривиальна". Она хоть что-то делает со значением переменной. В данном случае превращает ее в противоположное: true в false и обратно. Эта функция называется "отрицанием". Нечто похожее по свойствам есть в обычной алгебре - это функция f(x) = -x.

Для обозначения функции отрицания применяется значок "~" (и другие). В математике и программировании функции, которые обозначаются значками около переменных, часто называют Например, операция сложения "+". Значок "~" в формулах читается как "не". Действительно, употребление частицы "не" в обычном языке похоже на применение операции отрицания в логике. Переменные рядом с символом операции, называются "операндами". Если операндов два, то их называют "левым" и "правым" (или "первым" и "вторым").

Теперь перейдем к функциям от двух переменных. Их всего 16. Среди этих 16 найдется несколько функций, которые сводятся к тем, что мы уже рассмотрели выше, это f(A, B) = true, f(A, B) = false, f(A, B) = A, f(A, B) = B, f(A, B) = ~A, f(A, B) = ~B:

A B true false false true false true true true false true true true true		A B false false false false false true false true false false true true false		A B A false false false false true false true false true true true true
A B B false false false false true true true false false true true true		A B ~A false false true false true true true false false true true false		A B ~B false false true false true false true false true true true false

Итак, остается 10 "нетривиальных" функций от двух переменных. Расскажем о них по порядку. Для каждой функции приведем: таблицу истинности; значки, применяемые для ее обозначения; названия операции, применяемые в литературе и слово, которое используется при чтении значка.

Таблица истинности	Названия	Обозначения	Читается как...
A B A & B false false false false true false true false false true true true	конъюнкция логическое 'И' логическое умножение булево умножение		"и"
A B A B false false false false true true true false true true true true	дизъюнкция логическое 'ИЛИ' включающее 'ИЛИ'		"или" "vel" (латинск.)
A B A B false false false false true true true false true true true false	исключающее 'ИЛИ' сложение по модулю '2' булево сложение логическое сложение		"либо" "aut" (латинск.)
A B A B false false true false true false true false false true true true	равносильность эквивалентность равносильность равноистинность		"равноистинно" "равносильно" "эквивалентно"
A B A B false false true false true true true false false true true true	импликация материальная импликация следование необходимость		"имплицирует" "если ... то" "необходимо"
A B A B false false true false true false true false true true true true	достаточность		"достаточно"
A B A B false false true false true false true false false true true false	стрелка Пирса логическое 'И-НЕ'	A B	"не ... и не"
A B A | B false false true false true true true false true true true false	штрих Шеффера логическое 'ИЛИ-НЕ'	A | B	"не ... или не"
A B   false false false false true false true false true true true false	нет	A B	нет
A B   false false false false true true true false false true true false	нет	A B	нет

Примечания к таблицам.

Для двух последних операций даже не существует никаких общепринятых обозначений или названий, настолько они неинтересны. Мы все-таки назначили им два специфических значка, так как позднее они нам пару раз понадобятся.

Те слова, которые используются для чтения логических символов ("и", "или", "не") отражают сходство между логическими операциями и свойствами союзов и частиц естественного языка. Однако, строго говоря, это именно сходство, имеются и различия. Особенно опасно приравнивать операцию материальной импликации к условному выражению "если ... то ..." От этого получаются разнообразные казусы, которые называют "парадоксами материальной импликации". Например, фраза "Если Раскольников - негр, то он убийца" ложная, ведь быть негром - еще не значит быть убийцей. Если же посмотреть по таблице истинности функции "", то получается истина (утверждение "Раскольников - негр" - ложно, утверждение "он убийца" - истинно).

Для многих логических операций есть по нескольку названий и обозначений. Конечно, это вносит путаницу. Мы будем использовать то обозначение, которое приводится первым.

Название "равноистинность" не является общепринятым, а предлагается и используется в этом учебнике как наиболее точно отражающее смысл операции.

Коротко о свойствах некоторых операций.

Применение конъюнкции (логического 'И') дает "истину" (true) только когда оба опернда истинны. Если хотя бы один операнд ложен (или ложны оба), то результатом будет "ложь" (false).

Применение дизъюнкции (логического 'ИЛИ') дает "истину" (true) когда хотя бы один операнд истинный (или оба). Если оба операнда ложны, то результатом будет "ложь" (false).

Применение исключающего 'ИЛИ' дает "истину" (true) только тогда, когда операнды имеют разную истинность. Если оба операнда одновременно истинны или одновременно ложны, результат операции - "ложь" (false).

Применение операции "равноистинности" дает "истину" (true) только тогда, когда операнды имеют одинаковую истинность. Иначе результат операции - "ложь" (false).

Применение операции "материальной импликации" дает "ложь" (false) только в одном случае: когда первый (левый) операнд истинный (true), а второй (правый) - ложный (false).

Названия "конъюнкция" и "дизъюнкция" похожи и могут быть легко перепутаны. Чтобы этого избежать, обратите внимание на характерную черту: у символа "&" вправо торчат два хвостика в виде уголка. У первой буквы "к" в слове "конъюнкция" также вправо торчат два хвостика.

Вопросы и задания для самостоятельной работы

1. Выучите наизусть таблицы истинности для следующих операций: ~, &, , , ,
2. Что получится при вычислении A & B, если A = false и B = false?
   Посмотреть ответ

   false

3. Что получится при вычислении A B, если A = false и B = true?
   Посмотреть ответ

   true

4. Что получится при вычислении A B, если A = true и B = true?
   Посмотреть ответ

   false

5. Что получится при вычислении A B, если A = false и B = false?
   Посмотреть ответ

   true

6. Что получится при вычислении A B, если A = false и B = false?
   Посмотреть ответ

   true

7. Приведите еще один пример парадокса материальной импликации.
   Посмотреть ответ

   "Если в огороде бузина, то в Киеве дядька". Утверждение ложное, так как две части фразы: x = "в огороде бузина" и y = "в Киеве дядька" являются примером логически несвязанного текста. Тем не менее, если так окажется, что бузины в конкретном огороде нет (A = Tr(x) = false), а конкретный дядька действительно сейчас в Киеве (B = Tr(y) = true), то A B = true.