Диз'юнкція (логіка)

Диз'юнкція (лат. disjunctio — розділення) (операція OR) — двомісна логічна операція, що має значення «істина», якщо хоча б один з операндів має значення «істина». Операція відображає вживання сполучника «або» в логічних висловлюваннях. Диз'юнкція є бінарною операцією, тобто має два операнди. Запис може бути префіксним (знак операції стоїть перед операндами), інфіксним (знак операції стоїть між операндами) або постфіксним (знак операції стоїть після операндів). За кількості операндів понад 2 префіксний і постфіксний записи економніші.^[1][2]

OR
Визначення	${\displaystyle a+b}$
Таблиця істинності	${\displaystyle (1110)}$
Логічний вентиль
Нормальні форми
Диз'юнктивна	${\displaystyle a+b}$
Кон'юнктивна	${\displaystyle a+b}$
Алгебрична	${\displaystyle a\oplus b\oplus ab}$
Ґратка Поста
${\displaystyle P_{0}}$ (зберігає 0)	Так
${\displaystyle P_{1}}$ (зберігає 1)	Так
${\displaystyle M}$ (монотонна)	Так
${\displaystyle L}$ (лінійна)	✗
${\displaystyle S}$ (само-двоїста)	✗

Позначається: в математиці та логіці як ${\displaystyle \lor }$, у програмуванні як | чи or.

Найчастіше трапляються такі варіанти запису: a||b, a|b, a${\displaystyle \lor }$b, a+b, a or b.^[3]

У техніці операцію диз'юнкції втілює логічний вентиль АБО.

Визначення

У булевій алгебрі диз'юнкція — це функція двох, трьох або більшої кількості змінних (вони ж — операнди операції, вони ж — аргументи функції).

Правило: результат дорівнює 0, якщо всі операнди дорівнюють 0; у всіх інших випадках результат дорівнює 1.

Таблиця істинності виглядає таким чином:

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\lor B}$
F	F	F
F	T	T
T	F	T
T	T	T

Відповідною операцією в теорії множин є об'єднання множин.

Властивості

• асоціативність

${\displaystyle a\lor (b\lor c)\equiv (a\lor b)\lor c}$

• комутативність

${\displaystyle a\lor b\equiv b\lor a}$

• дистрибутивність^[4]

${\displaystyle a\land (b\lor c)\equiv (a\land b)\lor (a\land c)}$

${\displaystyle a\lor (b\land c)\equiv (a\lor b)\land (a\lor c)}$

${\displaystyle a\lor (b\leftrightarrow c)\equiv (a\lor b)\leftrightarrow (a\lor c)}$

• ідемпотентність

${\displaystyle a\lor a\equiv a}$

• монотонність

${\displaystyle (a\rightarrow b)\rightarrow ((a\lor c)\rightarrow (b\lor c))}$

Функціональна повнота

Множина операцій ${\displaystyle \{\lor ,\lnot \}}$ є функціонально повною:

${\displaystyle a\land b\equiv \lnot (\lnot a\lor \lnot b)}$

${\displaystyle a\rightarrow b\equiv \lnot a\lor b}$

${\displaystyle a\;|\;b\equiv \lnot a\lor \lnot b}$

${\displaystyle a\downarrow b\equiv \lnot (a\lor b)}$

Двійкові операції

Диз'юнкція часто використовується для двійкових операцій. Наприклад:

Логічний елемент 2АБО AB f (A B)

• 0 ${\displaystyle \lor }$ 0 = 0
• 0 ${\displaystyle \lor }$ 1 = 1
• 1 ${\displaystyle \lor }$ 0 = 1
• 1 ${\displaystyle \lor }$ 1 = 1
• 1010 ${\displaystyle \lor }$ 1110 = 1110

Мнемонічне правило для диз'юнкції з будь-якою кількістю входів звучить так: На виході буде: «1» тоді й тільки тоді, коли хоча б на одному вході є «1», «0» тоді й тільки тоді, коли на всіх входах «0».

Багатозначна логіка

У багатозначній логіці операція диз'юнкції може визначатися іншими способами. Найчастіше застосовують схему: a${\displaystyle \lor }$b= max(a, b), де a, b € [0,1]. Можливі й інші варіанти. Як правило, намагаються зберегти сумісність із булевою алгеброю для значень операндів 0, 1.

Програмування

У комп'ютерних мовах використовують два основні варіанти диз'юнкції: логічне «АБО» і побітове «АБО». Наприклад, у мовах C / C++ логічне «АБО» позначається символом "||", а побітове — символом "|". У мовах Pascal / Delphi обидва види диз'юнкції позначають із використанням ключового слова «or», а результат дії визначається типом операндів. Якщо операнди мають логічний тип (наприклад, Boolean), то виконується логічна операція; якщо цілочисельний (наприклад, Byte) — порозрядне.

Логічне «АБО» застосовується в операторах умовного переходу або в аналогічних випадках, коли потрібне отримання результату false або true. Наприклад:

if  (a || b) {/* певні дії */}; 

Результат буде дорівнювати false, якщо обидва операнди рівні false або 0. За будь-яких інших умов результат буде дорівнювати true.

При цьому справедлива стандартна умова: якщо значення лівого операнда є true, то значення правого операнда не обчислюється (замість b може стояти будь-яка складна формула). Це прискорює виконання програми й стає у пригоді за деяких обставин.

Побітове «АБО» виконує звичайну операцію булевої алгебри для всіх бітів лівого і правого операнда попарно. Наприклад, якщо a = 01100101 b = 00101001, то a АБО b = 01101101

Див. також

• Булева множина
• Закони де Моргана
• Умовна диз'юнкція
• Виключна диз'юнкція