Просмотр кода страницы Дизъюнкция

{{похожие буквы|V}}
{{Булева функция
| Название           = Дизъюнкция
| Другое название    = ИЛИ, OR
| Диаграмма Венна    = Venn0111.svg
| Определение        = <math>x+y</math>
| Таблица истинности = <math>(0111)</math>
| Логический вентиль = OR gate RU.svg
| ДНФ                = <math>x+y</math>
| КНФ                = <math>x+y</math>
| Полином Жегалкина  = <math>x \oplus y \oplus xy</math>
| Сохраняет 0        = Да
| Сохраняет 1        = Да
| Монотонна          = Да
| Линейна            = Нет
| Самодвойственна    = Нет
}}
'''Дизъю́нкция''' (от {{lang-la|disjunctio}} — «разобщение»), '''логи́ческое сложе́ние''', '''логи́ческое ИЛИ''', '''включа́ющее ИЛИ'''; иногда просто '''ИЛИ''' — [[логическая операция]], по своему применению максимально приближённая к союзу ''«или»'' в смысле ''«или то, или это, или оба сразу»''<ref>{{книга|автор=Гутников В. С. |заглавие=Интегральная электроника в измерительных приборах|место=Л.|издательство=[[Энергия (издательство)|Энергия]]|год=1974|страниц=144}} — С. 14—16.</ref>.

Дизъюнкция может быть операцией как [[бинарная операция|бинарной]] (имеющей два операнда), так и [[арность|<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|Кондаков|1975|с=534}}. Появилось оно не сразу: [[Буль, Джордж|Джордж Буль]], положивший начало систематическому применению символического метода к логике, не работал с дизъюнкцией (используя вместо неё [[строгая дизъюнкция|строгую дизъюнкцию]], которую обозначал знаком {{big|+}}), а [[Джевонс, Уильям Стенли|Уильям Джевонс]] предложил для дизъюнкции знак <code>·|·</code>. [[Шрёдер, Эрнст|Эрнст Шрёдер]] и [[Порецкий, Платон Сергеевич|П. С. Порецкий]] вновь использовали знак {{big|+}}, но уже применительно к обычной дизъюнкции<ref>{{книга|автор=Стяжкин Н. И. |заглавие=Формирование математической логики|место=М.|издательство=[[Наука (издательство)|Наука]]|год=1967|страниц=508}} — С. 320, 349, 352, 368.</ref>. Символ <math>\lor</math> как обозначение дизъюнкции впервые встречается в статье «Математическая логика, основанная на теории типов»<ref>{{статья|автор=[[Рассел, Бертран|Russell B.]] |заглавие=Mathematical Logic as Based on the Theory of Types|jstor=2369948|издание=[[American Journal of Mathematics]]|год=1908|volume=30, no. 3|pages=222—262|archivedate=2019-04-04|archiveurl=https://web.archive.org/web/20190404184453/https://www.jstor.org/stable/2369948}}</ref> [[Рассел, Бертран|Бертрана Рассела]] (1908); он образован от {{lang-la|vel}}, что означает «или»<ref>{{cite web|url=http://jeff560.tripod.com/set.html|title=Earliest Uses of Symbols of Set Theory and Logic|publisher=// Website ''Jeff Miller Web Pages''|accessdate=2016-02-05|archive-date=1999-02-20|archive-url=https://web.archive.org/web/19990220115724/http://members.aol.com/jeff570/set.html|deadlink=no}}</ref>{{sfn|Кондаков|1975|с=149—150}}.

Обозначение <code>⋁</code> для дизъюнкции было использовано и в раннем [[язык программирования|языке программирования]] [[Алгол 60]]{{sfn|Кондаков|1975|с=30}}. Однако из-за отсутствия соответствующего символа в стандартных [[набор символов|наборах символов]] (например, в [[ASCII]] или [[EBCDIC]]), применявшихся на большинстве [[компьютер]]ов, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для дизъюнкции. Так, в [[Фортран|Фортране IV]] и [[PL/I]] применялись соответственно обозначения <code>.OR.</code> и <code>|</code> (с возможностью замены последнего на [[зарезервированное слово|ключевое слово]] <code>OR</code>)<ref>{{книга|автор=Пратт Т. |заглавие=Языки программирования: разработка и реализация|место=М.|издательство=[[Мир (издательство)|Мир]]|год=1979|страниц=574}} — С. 352, 439.</ref>; в языках [[Паскаль (язык программирования)|Паскаль]] и [[Ада (язык программирования)|Ада]] используется зарезервированное слово <code>or</code><ref>{{книга|автор=Грогоно П. |заглавие=Программирование на языке Паскаль|место=М.|издательство=[[Мир (издательство)|Мир]]|год=1982|страниц=384}} — С. 51.</ref><ref>{{книга|автор=Вегнер П. |заглавие=Программирование на языке Ада|место=М.|издательство=[[Мир (издательство)|Мир]]|год=1983|страниц=240}} — С. 68.</ref>; в языках [[Си (язык программирования)|C]] и [[C++]] применяются обозначения <code>|</code> для побитовой дизъюнкции и <code>||</code> для логической дизъюнкции<ref>{{книга|автор=[[:en:Margaret A. Ellis|Эллис М.]], [[Страуструп, Бьёрн|Строуструп Б.]] |заглавие=Справочное руководство по языку программирования C++ с комментариями|ссылка=https://archive.org/details/isbn_5-03-002868-4|место=М.|издательство=[[Мир (издательство)|Мир]]|год=1992|страниц=445|isbn=5-03-002868-4}} — С. 65, 86—87.</ref>).

Наконец, при естественном упорядочении [[истинностное значение|значений истинности]] [[булева функция|двузначной логики]] (когда полагают, что <math>0 < 1</math>), оказывается, что <math>(a \lor b)\,=\,\max(a,b).</math> Таким образом, дизъюнкция оказывается частным случаем операции вычисления [[максимальный элемент|максимума]]; это открывает наиболее естественный способ определить операцию дизъюнкции в системах [[многозначная логика|многозначной логики]]<ref>{{книга|автор=[[Яблонский, Сергей Всеволодович|Яблонский С. В.]] |заглавие=Введение в дискретную математику|место=М.|издательство=[[Наука (издательство)|Наука]]|год=1979|страниц=272}} — С. 9—10, 37.</ref><ref>{{книга|автор=[[Рвачёв, Владимир Логвинович|Рвачёв В. Л.]] |заглавие=Теория ''R-''функций и некоторые её приложения|место=Киев|издательство=[[Наукова думка]]|год=1982|страниц=552}} — С. 38, 66.</ref>.

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

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

{| class="wikitable" style="text-align: center;"
 ! colspan="3" | Таблица истинности
 |-
 |width="33%"|<math>a</math>
 |width="33%"|<math>b</math>
 |width="33%"|<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>
 |}
Таблица истинности для тернарной (трёхоперандной) дизъюнкции:
{| class = "wikitable"
  !<math>a</math>||<math>b</math>||<math>c</math>|| <math>a \lor b\lor c</math>
  |-
  |0||0||0|| align = "center" |0
  |-
  |0||0||1|| align = "center" |1
  |-
  |0||1||0|| align = "center" |1
  |-
  |0||1||1|| align = "center" |1
  |-
  |1||0||0|| align = "center" |1
  |-
  |1||0||1|| align = "center" |1
  |-
  |1||1||0|| align = "center" |1
  |-
  |1||1||1|| align = "center" |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>

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

== Схемотехника ==
{{Основная статья|Логические элементы#Дизъюнкция (логическое сложение). Операция ИЛИ}}
[[Файл:OR gate RU.svg|thumb|right|100px|Логический элемент 2ИЛИ]]
Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:
* «1» тогда и только тогда, когда '''''хотя бы на одном''''' входе есть «1»,
* «0» тогда и только тогда, когда на '''''всех''''' входах «0»
{{clear}}

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

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

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

<source lang="c">
if (a || b)
{
    /* какие-то действия */
};
</source>

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

При этом применяется стандартное соглашение: если значение левого операнда равно <math>true</math>, то значение правого операнда не вычисляется (вместо <math>b</math> может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую <source lang="delphi">{$B-}</source> или выключающую <source lang="delphi">{$B+}</source> подобное поведение. Например, если левый операнд проверяет необходимость вычисления правого операнда:

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

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

Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,
{|
 |если
 |-
 |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>.

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

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

== Примечания ==
{{примечания|2}}

== Литература ==
{{Викисловарь|дизъюнкция}}
* {{книга|автор=Кондаков Н. И. |заглавие=Логический словарь-справочник. 2-е изд|ссылка=http://www.runivers.ru/upload/iblock/443/logichesky%20slovar.pdf|место=М.|издательство=[[Наука (издательство)|Наука]]|год=1975|страниц=720|ref=Кондаков}}
{{Внешние ссылки}}
{{Логические операции}}
{{Логика}}

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