Рассмотрим еще раз таблицу из предыдущей главы
A | B | ~(A & B) |
false | false | true |
false | true | true |
true | false | true |
true | true | false |
В правом столбце выписаны четыре константы: true, true, true, false (выделено желтым фоном).
Эти константы определяют истинность некоторой формулы, записанной в верхнем правом углу таблицы
(подкрашено зеленым).
Подобная таблица задает функцию от двух переменных (в данном случае - A и B).
Всего возможно 24 = 16
функций от двух переменных, которые отличаются друг от друга по своим результатам. Аналогично, возможно
22 = 4 функции от одной переменной и 21 = 2 функции от нуля переменных.
Рассмотрим их по порядку.
Функции от нуля переменных не должны иметь столбцов с переменными. Остается только крайний правый столбец
с двумя ячейками. В верхней ячейке будет название функции, а в нижней - ее значение.
Поскольку эти простейшие функции всегда совпадают с одной из констант true и false, то в
качестве обозначения таких функций удобно использовать те же самые константы:
Теперь рассмотрим функции от одной переменной. Всего их возможно 4:
Таблица истинности |
Названия |
Обозначения |
Читается как... |
A | false |
false | false |
true | false |
|
ложь
|
false
|
"ложь"
|
A | true |
false | true |
true | 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).
Названия "конъюнкция" и "дизъюнкция" похожи и могут быть легко перепутаны. Чтобы этого избежать, обратите внимание
на характерную черту: у символа "&" вправо торчат два хвостика в виде уголка. У первой буквы "к"
в слове "конъюнкция" также вправо торчат два хвостика.
Вопросы и задания для самостоятельной работы
- Выучите наизусть таблицы истинности для следующих операций: ~, &, , , ,
- Что получится при вычислении A & B, если A = false и B = false?
- Что получится при вычислении A B, если A = false и B = true?
- Что получится при вычислении A B, если A = true и B = true?
- Что получится при вычислении A B, если A = false и B = false?
- Что получится при вычислении A B, если A = false и B = false?
- Приведите еще один пример парадокса материальной импликации.
"Если в огороде бузина, то в Киеве дядька". Утверждение ложное, так как две части фразы:
x = "в огороде бузина" и y = "в Киеве дядька"
являются примером логически несвязанного
текста. Тем не менее, если так окажется, что бузины в конкретном огороде нет (A = Tr(x) = false),
а конкретный дядька действительно сейчас в Киеве (B = Tr(y) = true), то A B = true.