Русская Википедия:Дизъюнкция
Шаблон:Похожие буквы Шаблон:Булева функция Дизъю́нкция (от Шаблон:Lang-la — «разобщение»), логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу»[1].
Дизъюнкция может быть операцией как бинарной (имеющей два операнда), так и <math>n</math>-арной (имеющей <math>n</math> операндов) для произвольного <math>n</math>.
Запись может быть префиксной — знак операции стоит перед операндами (польская запись), инфиксной — знак операции стоит между операндами или постфиксной — знак операции стоит после операндов. При числе операндов более двух префиксная и постфиксная записи экономичнее.
Инверсией дизъюнкции является стрелка Пирса.
Обозначения
Наиболее часто встречаются следующие обозначения для операции дизъюнкции:
- <math>a \lor b, \; a</math> || <math>b, \; a</math> | <math>b, \; a~\mbox{OR}\,\,b</math><math>, \; \max(a,b).</math>
При этом обозначение <math>a \lor b</math>, рекомендованное международным стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логикеШаблон:Sfn. Появилось оно не сразу: Джордж Буль, положивший начало систематическому применению символического метода к логике, не работал с дизъюнкцией (используя вместо неё строгую дизъюнкцию, которую обозначал знаком Шаблон:Big), а Уильям Джевонс предложил для дизъюнкции знак ·|·. Эрнст Шрёдер и П. С. Порецкий вновь использовали знак Шаблон:Big, но уже применительно к обычной дизъюнкции[2]. Символ <math>\lor</math> как обозначение дизъюнкции впервые встречается в статье «Математическая логика, основанная на теории типов»[3] Бертрана Рассела (1908); он образован от Шаблон:Lang-la, что означает «или»[4]Шаблон:Sfn.
Обозначение ⋁ для дизъюнкции было использовано и в раннем языке программирования Алгол 60Шаблон:Sfn. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для дизъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .OR. и | (с возможностью замены последнего на ключевое слово OR)[5]; в языках Паскаль и Ада используется зарезервированное слово or[6][7]; в языках C и C++ применяются обозначения | для побитовой дизъюнкции и || для логической дизъюнкции[8]).
Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <math>0 < 1</math>), оказывается, что <math>(a \lor b)\,=\,\max(a,b).</math> Таким образом, дизъюнкция оказывается частным случаем операции вычисления максимума; это открывает наиболее естественный способ определить операцию дизъюнкции в системах многозначной логики[9][10].
Булева алгебра
Логическая функция MAX в двухзначной (двоичной) логике называется дизъюнкция (логи́ческое «ИЛИ», логи́ческое сложе́ние или просто «ИЛИ»). При этом результат равен наибольшему операнду.
В булевой алгебре дизъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Таким образом, результат равен <math>0</math>, если все операнды равны <math>0</math>; во всех остальных случаях результат равен <math>1</math>.
| Таблица истинности | ||
|---|---|---|
| <math>a</math> | <math>b</math> | <math>a \lor b</math> |
| <math>0</math> | <math>0</math> | <math>0</math> |
| <math>0</math> | <math>1</math> | <math>1</math> |
| <math>1</math> | <math>0</math> | <math>1</math> |
| <math>1</math> | <math>1</math> | <math>1</math> |
Таблица истинности для тернарной (трёхоперандной) дизъюнкции:
| <math>a</math> | <math>b</math> | <math>c</math> | <math>a \lor b\lor c</math> |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Многозначная логика
Операция, называемая в двоичной логике дизъюнкция, в многозначных логиках называется максимум: <math>max(a,b)</math>, где <math>a, b \in [0,...,n-1]</math>, а <math>n</math> — значность логики. Возможны и другие вариантыШаблон:Чего. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов <math>0, 1</math>.
Название этой операции максимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия дизъюнкция, логи́ческое «ИЛИ», логическое сложе́ние и просто «ИЛИ» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.
Классическая логика
В классическом исчислении высказываний свойства дизъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства дизъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для дизъюнкции:
- <math>a \to a \lor b</math>
- <math>b \to a \lor b</math>
- <math>(a \to c) \to ((b \to c) \to ((a \lor b) \to c))</math>
С помощью этих аксиом можно доказать другие формулы, содержащие операцию дизъюнкции. Обратите внимание, что в классическом исчислении высказываний не происходит вычисления результата по значениям операндов (как в булевой алгебре), а требуется доказать формулу как единое целое на основе аксиом и правил вывода.
Схемотехника
Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:
- «1» тогда и только тогда, когда хотя бы на одном входе есть «1»,
- «0» тогда и только тогда, когда на всех входах «0»
Теория множеств
С точки зрения теории множеств, дизъюнкция аналогична операции объединения.
Программирование
В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++/Perl/PHP логическое «ИЛИ» обозначается символом "||", а побитовое — символом "|". В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.
Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата <math>false</math> или <math>true</math>. Например:
if (a || b)
{
/* какие-то действия */
};
Результат будет равен <math>false</math>, если оба операнда равны <math>false</math> или <math>0</math>. В любом другом случае результат будет равен <math>true</math>.
При этом применяется стандартное соглашение: если значение левого операнда равно <math>true</math>, то значение правого операнда не вычисляется (вместо <math>b</math> может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую
{$B-}
или выключающую
{$B+}
подобное поведение. Например, если левый операнд проверяет необходимость вычисления правого операнда:
if (a == NULL || a->x == 0)
{
/* какие-то действия */
};
В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт разыменования нулевого указателя.
Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,
| если | |
| a = | <math>01100101_2</math> |
| b = | <math>00101001_2</math> |
| то | |
| a ИЛИ b = | <math>01101101_2</math> |
Связь с естественным языком
Часто указывают на сходство между дизъюнкцией и союзом «или» в естественном языке, когда он употребляется в смысле «или то, или то, или оба сразу». В юридических документах часто пишут: «и (или)», иногда «и/или», подразумевая «или то, или то, или оба сразу». Составное утверждение «A и/или B» считается ложным, когда ложны оба утверждения A и B, в противном случае составное утверждение истинно. Это в точности соответствует определению дизъюнкции в булевой алгебре, если «истину» обозначать как <math>1</math>, а «ложь» как <math>0</math>.
Неоднозначность естественного языка заключается в том, что союз «или» используется в двух значениях: то для обозначения дизъюнкции, то для другой операции — строгой дизъюнкции (исключающего «ИЛИ»).
См. также
- Идентичность
- Отрицание
- Конъюнкция
- Импликация
- Обратная импликация
- Штрих Шеффера
- Стрелка Пирса
- Условная дизъюнкция
- Таблица истинности
- Закон тождества
Примечания
Литература
- ↑ Шаблон:Книга — С. 14—16.
- ↑ Шаблон:Книга — С. 320, 349, 352, 368.
- ↑ Шаблон:Статья
- ↑ Шаблон:Cite web
- ↑ Шаблон:Книга — С. 352, 439.
- ↑ Шаблон:Книга — С. 51.
- ↑ Шаблон:Книга — С. 68.
- ↑ Шаблон:Книга — С. 65, 86—87.
- ↑ Шаблон:Книга — С. 9—10, 37.
- ↑ Шаблон:Книга — С. 38, 66.
Шаблон:Выбор языка Шаблон:Логические операции Шаблон:Логика
- Страницы, использующие устаревший тег source
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- Математическая логика
- Логика высказываний
- Теория множеств
- Логические элементы
- Бинарные операции
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии
