Дизъюнкция

Символы со сходным начертанием: V · v · Ѵ · ѵ · Ⅴ · ν

Дизъю́нкция (от лат. disjunctio — «разобщение»), логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».

Дизъюнкция
ИЛИ, OR
Диаграмма Венна
Определение	$x+y$$x+y$
Таблица истинности	$(0111)$$(0111)$
Логический вентиль
Нормальные формы
Дизъюнктивная	$x+y$$x+y$
Конъюнктивная	$x+y$$x+y$
Полином Жегалкина	$x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->xy$$x\oplus y\oplus xy$
Принадлежность предполным классам
Сохраняет 0	Да
Сохраняет 1	Да
Монотонна	Да
Линейна	Нет
Самодвойственна	Нет

Дизъюнкция может быть операцией как бинарной (имеющей два операнда), так и $n$$n$-арной (имеющей $n$$n$ операндов) для произвольного $n$$n$.

Запись может быть префиксной — знак операции стоит перед операндами (польская запись), инфиксной — знак операции стоит между операндами или постфиксной — знак операции стоит после операндов. При числе операндов более двух префиксная и постфиксная записи экономичнее.

ОбозначенияПравить

Наиболее часто встречаются следующие обозначения для операции дизъюнкции:

$a\vee <!--\; \vee \; -->b,a$$a\lor b,\;a$  || $b,a$$b,\;a$  | $b,a\text{OR}b$$b,\;a~{\mbox{OR}}\,\,b$ $,max(a,b).$$,\;\max(a,b).$ 

При этом обозначение $a\vee <!--\; \vee \; -->b$$a\lor b$ , рекомендованное международным стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике. Появилось оно не сразу: Джордж Буль, положивший начало систематическому применению символического метода к логике, не работал с дизъюнкцией (используя вместо неё строгую дизъюнкцию, которую обозначал знаком +), а Уильям Джевонс предложил для дизъюнкции знак ·|·. Эрнст Шрёдер и П. С. Порецкий вновь использовали знак +, но уже применительно к обычной дизъюнкции. Символ $\vee <!--\; \vee \; -->$$\lor$  как обозначение дизъюнкции впервые встречается в статье «Математическая логика, основанная на теории типов» Бертрана Рассела (1908); он образован от лат. vel, что означает «или».

Обозначение ⋁ для дизъюнкции было использовано и в раннем языке программирования Алгол 60. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для дизъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .OR. и | (с возможностью замены последнего на ключевое слово OR); в языках Паскаль и Ада используется зарезервированное слово or; в языках C и C++ применяются обозначения | для побитовой дизъюнкции и || для логической дизъюнкции).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что $0<1$ ), оказывается, что $(a\vee <!--\; \vee \; -->b)=max(a,b).$$(a\lor b)\,=\,\max(a,b).$  Таким образом, дизъюнкция оказывается частным случаем операции вычисления максимума; это открывает наиболее естественный способ определить операцию дизъюнкции в системах многозначной логики.

Булева алгебраПравить

Логическая функция MAX в двухзначной (двоичной) логике называется дизъюнкция (логи́ческое «ИЛИ», логи́ческое сложе́ние или просто «ИЛИ»). При этом результат равен наибольшему операнду.

В булевой алгебре дизъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Таким образом, результат равен $0$$0$ , если все операнды равны $0$$0$ ; во всех остальных случаях результат равен $1$$1$ .

Таблица истинности
$a$$a$	$b$$b$	$a\vee <!--\; \vee \; -->b$$a\lor b$
$0$$0$	$0$$0$	$0$$0$
$0$$0$	$1$$1$	$1$$1$
$1$$1$	$0$$0$	$1$$1$
$1$$1$	$1$$1$	$1$$1$

Таблица истинности для тернарной (трёхоперандной) дизъюнкции:

$a$$a$	$b$$b$	$c$$c$	$a\vee <!--\; \vee \; -->b\vee <!--\; \vee \; -->c$$a\lor b\lor c$
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

Многозначная логикаПравить

Операция, называемая в двоичной логике дизъюнкция, в многозначных логиках называется максимум: $max(a,b)$$max(a,b)$ , где $a,b\in <!--\; \in \; -->[0,...,n-<!--\; -\; -->1]$$a,b\in [0,...,n-1]$ , а $n$$n$  — значность логики. Возможны и другие варианты^[чего?]. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов $0,1$$0,1$ .

Название этой операции максимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия дизъюнкция, логи́ческое «ИЛИ», логическое сложе́ние и просто «ИЛИ» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.

Классическая логикаПравить

В классическом исчислении высказываний свойства дизъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства дизъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для дизъюнкции:

• $a\to <!--\; \to \; -->a\vee <!--\; \vee \; -->b$$a\to a\lor b$ 
• $b\to <!--\; \to \; -->a\vee <!--\; \vee \; -->b$$b\to a\lor b$ 
• $(a\to <!--\; \to \; -->c)\to <!--\; \to \; -->((b\to <!--\; \to \; -->c)\to <!--\; \to \; -->((a\vee <!--\; \vee \; -->b)\to <!--\; \to \; -->c))$$(a\to c)\to ((b\to c)\to ((a\lor b)\to c))$ 

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

СхемотехникаПравить

Основная статья: Логические элементы § Дизъюнкция (логическое сложение). Операция ИЛИ

 

Логический элемент 2ИЛИ

Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:

• «1» тогда и только тогда, когда хотя бы на одном входе есть «1»,
• «0» тогда и только тогда, когда на всех входах «0»

Теория множествПравить

С точки зрения теории множеств, дизъюнкция аналогична операции объединения.

ПрограммированиеПравить

В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++/Perl/PHP логическое «ИЛИ» обозначается символом "||", а побитовое — символом "|". В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.

Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата $false$$false$  или $true$$true$ . Например:

if (a || b)
{
    /* какие-то действия */
};

Результат будет равен $false$$false$ , если оба операнда равны $false$$false$  или $0$$0$ . В любом другом случае результат будет равен $true$$true$ .

При этом применяется стандартное соглашение: если значение левого операнда равно $true$$true$ , то значение правого операнда не вычисляется (вместо $b$$b$  может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

{$B-}

или выключающую

{$B+}

подобное поведение. Например, если левый операнд проверяет необходимость вычисления правого операнда:

if (a == NULL || a->x == 0)
{
    /* какие-то действия */
};

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт разыменования нулевого указателя.

Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,

если
a =	${01100101}_2$$01100101_{2}$
b =	${00101001}_2$$00101001_{2}$
то
a ИЛИ b =	${01101101}_2$$01101101_{2}$

Связь с естественным языкомПравить

Часто указывают на сходство между дизъюнкцией и союзом «или» в естественном языке, когда он употребляется в смысле «или то, или то, или оба сразу». В юридических документах часто пишут: «и (или)», иногда «и/или», подразумевая «или то, или то, или оба сразу». Составное утверждение «A и/или B» считается ложным, когда ложны оба утверждения A и B, в противном случае составное утверждение истинно. Это в точности соответствует определению дизъюнкции в булевой алгебре, если «истину» обозначать как $1$$1$ , а «ложь» как $0$$0$ .

Неоднозначность естественного языка заключается в том, что союз «или» используется в двух значениях: то для обозначения дизъюнкции, то для другой операции — строгой дизъюнкции (исключающего «ИЛИ»).

См. такжеПравить

• Конъюнкция
• Исключающее «или»
• Импликация
• Эквиваленция
• Штрих Шеффера
• Стрелка Пирса
• Отрицание

ЛитератураПравить

• Кондаков Н. И. . Логический словарь-справочник. 2-е изд. — М.: Наука, 1975. — 720 с.