Дизъюнкция

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Дизъюнкция
ИЛИ
OR gate RU.svg
Основная информация
Определение x+y
Классы
T0
T1
M
L
S
 Да   Да   Да   Нет   Нет 
ДНФ x+y
КНФ x+y
Полином Жегалкина x \oplus y \oplus xy
Таблица истинности (0111)

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

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

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

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

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

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

При этом обозначение a \lor b наиболее широко распространено в современной математике и математической логике[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

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

X Y Z X \lor Y \lor Z
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), где ~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ИЛИ
 A  B  f(AB)
0 0 0
1 0 1
0 1 1
1 1 1

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

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


Теория множеств[править | править вики-текст]

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

Программирование[править | править вики-текст]

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

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

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

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

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

{$B-}

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

{$B+}

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

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

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

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

если
a = ~01100101_2
b = ~00101001_2
то
a ИЛИ b = ~01101101_2

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

Часто указывают на сходство между дизъюнкцией и союзом «или» в естественном языке, когда он употребляется в смысле «или то, или то, или оба сразу». В юридических документах часто пишут: «и (или)», иногда «и/или», подразумевая «или то, или то, или оба сразу». Составное утверждение «A и/или B» считается ложным, когда ложны оба утверждения A и B, в противном случае составное утверждение истинно. Это в точности соответствует определению дизъюнкции в булевой алгебре, если «истину» обозначать как 1, а «ложь» как 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.
  5. Earliest Uses of Symbols of Set Theory and Logic. // Website Jeff Miller Web Pages. Проверено 5 февраля 2016.
  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.

Литература[править | править вики-текст]