Дизъюнкция

Материал из Википедии — свободной энциклопедии

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

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

Это бинарная инфиксная операция, то есть, она имеет два операнда и ставится между ними. Чаще всего встречаются следующие варианты записи:
~a || ~b, ~a | ~b, a \lor b, a + b, ~a~\mbox{OR} ~b.

Содержание

[править] Булева алгебра

В булевой алгебре дизъюнкция - это функция двух переменных (они же - операнды операции). Переменные могут принимать значения из множества ~\{0, 1\}. Результат также принадлежит множеству ~\{0, 1\}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ~0, 1 может использоваться любая другая пара подходящих символов, например ~false, true или ~F, T или "ложь", "истина".

Правило: результат равен ~0, если оба операнда равны ~0; во всех остальных случаях результат равен ~1.

Таблица истинности:

~a ~b ~a \lor b
~0 ~0 ~0
~0 ~1 ~1
~1 ~0 ~1
~1 ~1 ~1

[править] Многозначная логика

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

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

[править] Программирование

В компьютерных языках используется два основных варианта дизъюнкции: логическое "ИЛИ" и побитовое "ИЛИ". Например, в языках C/C++ логическое "ИЛИ" обозначается символом "||", а побитовое - символом "|".

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

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

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

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

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

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

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

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

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

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

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

[править] См. также

Источник — «http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B7%D1%8A%D1%8E%D0%BD%D0%BA%D1%86%D0%B8%D1%8F»