Дизъюнкция

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

Дизъюнкция может быть бинарной операцией, то есть, иметь два операнда, тринарной операцией, то есть иметь три операнда или n-арной операцией, то есть иметь n операндов.
Запись может быть префиксной — знак операции стоит перед операндами (польская запись), инфиксной — знак операции стоит между операндами или постфиксной — знак операции стоит после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее.
Чаще всего встречаются следующие варианты записи:
<math>~a</math> || <math>~b, ~a</math> | <math>~b, a \lor b, a + b, ~a~\mbox{OR} ~b</math>.

Содержание

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

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

Таблица истинности
<math>~a</math> <math>~b</math> <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>

Бинарной дизъюнкции соответствует бинарная функция f(10,1,1110)2(x, y)=f(2,1,14)10(x, y).
Таблица истинности для тринарной (трёхоперандной) дизъюнкции:

XYZ X <math>\lor</math> Y <math>\lor</math> Z
000 0
100 1
010 1
110 1
001 1
101 1
011 1
111 1

Тринарной дизъюнкции соответствует тринарная функция f(11,1,11111110)2(x, y)=f(3,1,254)10(x, y).

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

В многозначной логике операция дизъюнкции может определяться другими способами. Чаще всего применяется схема: <math>a \lor b = max(a, b)</math>, где <math>~a, b \in [0, 1]</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>

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

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

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

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

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

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

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

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

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

если
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>.

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

См. также

Личные инструменты

Served in 0.265 secs.