Дизъюнкция

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

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

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

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

Инверсией дизъюнкции является стрелка Пирса.

Обозначения

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

a \lor b, a

||

b, a

|

b, a OR b

, max (a, b) .

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

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

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

Булева алгебра

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

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

Таблица истинности
$a$	$b$	$a \lor b$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$1$

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

$a$	$b$	$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

Многозначная логика

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

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

Классическая логика

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

$a \to a \lor b$
$b \to a \lor b$
$(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) — поразрядная.

Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата $f a l s e$ или $t r u e$ . Например:

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

Результат будет равен $f a l s e$ , если оба операнда равны $f a l s e$ или $0$ . В любом другом случае результат будет равен $t r u e$ .

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

{$B-}

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

{$B+}

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

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

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

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

если
a =	$0110010 1_{2}$
b =	$0010100 1_{2}$
то
a ИЛИ b =	$0110110 1_{2}$

Связь с естественным языком

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

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

См. также

Примечания

↑ Гутников В. С. . Интегральная электроника в измерительных приборах. — Л.: Энергия, 1974. — 144 с. — С. 14—16.
↑ Кондаков, 1975, с. 534.
↑ Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 320, 349, 352, 368.
↑ Russell B. Mathematical Logic as Based on the Theory of Types // American Journal of Mathematics. — 1908. — Vol. 30, no. 3. — P. 222—262. — JSTOR 2369948. Архивировано 4 апреля 2019 года.
↑ Earliest Uses of Symbols of Set Theory and Logic . // Website Jeff Miller Web Pages. Дата обращения: 5 февраля 2016. Архивировано 20 февраля 1999 года.
↑ Кондаков, 1975, с. 149—150.
↑ Кондаков, 1975, с. 30.
↑ Пратт Т. . Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
↑ Грогоно П. . Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
↑ Вегнер П. . Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
↑ Эллис М., Строуструп Б. . Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
↑ Яблонский С. В. . Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
↑ Рвачёв В. Л. . Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.

Литература

В Викисловаре есть статья «дизъюнкция»

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

[1] Гутников В. С. . Интегральная электроника в измерительных приборах. — Л.: Энергия, 1974. — 144 с. — С. 14—16.

[_40cb5d7f8bb907a6-2] Кондаков, 1975, с. 534.

[3] Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 320, 349, 352, 368.

[4] Russell B. Mathematical Logic as Based on the Theory of Types // American Journal of Mathematics. — 1908. — Vol. 30, no. 3. — P. 222—262. — JSTOR 2369948. Архивировано 4 апреля 2019 года.

[5] Earliest Uses of Symbols of Set Theory and Logic . // Website Jeff Miller Web Pages. Дата обращения: 5 февраля 2016. Архивировано 20 февраля 1999 года.

[_7190c3b666e893de-6] Кондаков, 1975, с. 149—150.

[_c2001532e79a92d3-7] Кондаков, 1975, с. 30.

[8] Пратт Т. . Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.

[9] Грогоно П. . Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.

[10] Вегнер П. . Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.

[11] Эллис М., Строуструп Б. . Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.

[12] Яблонский С. В. . Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.

[13] Рвачёв В. Л. . Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Ссылки на внешние ресурсы
Тематические сайты	MathWorld
Словари и энциклопедии	Большая датская Большая российская (научно-образовательный портал) Математическая Стэнфордская философская De Agostini PWN Treccani
В библиографических каталогах	GND: 4378735-6 J9U: 987007532489205171 LCCN: sh93005045