# Дизъюнкция

[править | править код]
Материал из Википедии — свободной энциклопедии
(перенаправлено с «Логическое сложение»)
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 13 июня 2023 года; проверки требуют 8 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 13 июня 2023 года; проверки требуют 8 правок.
Перейти к навигации Перейти к поиску

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

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

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

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

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

## Обозначения[править | править код]

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

  a ∨ b , a {\displaystyle a\lor b,\;a} || b , a {\displaystyle b,\;a} | b , a OR b {\displaystyle b,\;a~{\mbox{OR}}\,\,b} , max ( a , b ) . {\displaystyle ,\;\max(a,b).}

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

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

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

## Булева алгебра[править | править код]

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

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

Таблица истинности
a {\displaystyle a} | b {\displaystyle b} | a ∨ b {\displaystyle a\lor b}
0 {\displaystyle 0} | 0 {\displaystyle 0} | 0 {\displaystyle 0}
0 {\displaystyle 0} | 1 {\displaystyle 1} | 1 {\displaystyle 1}
1 {\displaystyle 1} | 0 {\displaystyle 0} | 1 {\displaystyle 1}
1 {\displaystyle 1} | 1 {\displaystyle 1} | 1 {\displaystyle 1}

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

a {\displaystyle a} | b {\displaystyle b} | c {\displaystyle c} | a ∨ b ∨ c {\displaystyle 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 ) {\displaystyle max(a,b)} , где a , b ∈ [ 0 , . . . , n − 1 ] {\displaystyle a,b\in [0,...,n-1]} , а n {\displaystyle n} — значность логики. Возможны и другие варианты
[чего?]. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов 0 , 1 {\displaystyle 0,1} .

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

## Классическая логика[править | править код]

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

- a → a ∨ b {\displaystyle a\to a\lor b}
- b → a ∨ b {\displaystyle b\to a\lor b}
- ( a → c ) → ( ( b → c ) → ( ( a ∨ b ) → c ) ) {\displaystyle (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 {\displaystyle false} или t r u e {\displaystyle true} . Например:

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

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

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

    {$B-}

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

    {$B+}

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

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

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

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

если
a = | 01100101 2 {\displaystyle 01100101_{2}}
b = | 00101001 2 {\displaystyle 00101001_{2}}
то
a ИЛИ b = | 01101101 2 {\displaystyle 01101101_{2}}

## Связь с естественным языком[править | править код]

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

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

## См. также[править | править код]

- Идентичность
- Отрицание
- Конъюнкция
- Импликация
- Обратная импликация
- Штрих Шеффера
- Стрелка Пирса
- Условная дизъюнкция
- Таблица истинности
- Закон тождества

## Примечания[править | править код]

1. ↑
   Гутников В. С. . Интегральная электроника в измерительных приборах. — Л.: Энергия, 1974. — 144 с. — С. 14—16.
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. Архивировано 4 апреля 2019 года.
5. ↑ Earliest Uses of Symbols of Set Theory and Logic (неопр.). // Website Jeff Miller Web Pages. Дата обращения: 5 февраля 2016. Архивировано 20 февраля 1999 года.
6. ↑ Кондаков, 1975, с. 149—150.
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.

## Литература[править | править код]

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

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

Источник — https://ru.wikipedia.org/w/index.php?title=Дизъюнкция&oldid=132363554
Категории:

- Математическая логика
- Логика высказываний
- Теория множеств
- Логические элементы
- Бинарные операции

Скрытые категории:

- Страницы, использующие устаревший тег source
- Википедия:Cite web (не указан язык)
- Страницы, использующие волшебные ссылки ISBN
- Википедия:Статьи, требующие конкретизации
- Википедия:Статьи с шаблонами недостатков по алфавиту
- Статьи со ссылками на Викисловарь
- Страницы, использующие математические теги в устаревшем формате