Кон'юнкція

Кон'юнкція (від лат. conjunctio, яке використовувалося для позначення частин мови, що з'єднують слова, фрази або речення^[1]) (операція AND) — двомісна операція, що має значення «істина», якщо всі операнди мають значення «істина». Операція передбачає вживання сполучника «і» в логічних висловлюваннях.

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

Позначення

And зазвичай виражається з префіксним оператором ${\displaystyle K}$, або інфіксним оператором. У математичній логіці інфіксний оператор зазвичай ${\displaystyle \land }$, в електроніці ${\displaystyle \cdot }$, а в мовах програмування & або and.

Правила усунення

${\displaystyle A}$,

${\displaystyle B}$.

Отже, ${\displaystyle A}$ і ${\displaystyle B}$.

Або в позначенні логічного оператора:

${\displaystyle A}$,

${\displaystyle B}$

${\displaystyle \vdash A\land B}$

Приклад:

Петро любить яблука.

Петро любить сало.

Отже, Петро любить яблука і сало.

Кон'юктивне усунення є іншим класичним дійсним, простим аргументом форми. Інтуїтивно це дає змогу зробити висновок з будь-якої кон'юнкції або елемента цієї кон'юнкції.

${\displaystyle A}$ і ${\displaystyle B}$.

Отже, ${\displaystyle A}$.

...або навпаки,

${\displaystyle A}$ і ${\displaystyle B}$.

Отже, ${\displaystyle B}$.

У позначенні логічного оператора:

${\displaystyle A\land B}$

${\displaystyle \vdash A}$

...або навпаки,

${\displaystyle A\land B}$

${\displaystyle \vdash B}$

Визначення

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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\land B}$
0	0	0
0	1	0
1	0	0
1	1	1

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

Властивості

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

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

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

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

• дистрибутивність

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

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

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

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

${\displaystyle a\land a\equiv a}$

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

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

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

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

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

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

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

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

${\displaystyle a\downarrow b\equiv \lnot a\land \lnot b}$

Кон'юнкція в програмуванні

умовне позначення логічного вентиля І (AND)

У комп'ютерному програмуванні і цифровій електроніці високого рівня логічне множення широко представлене інфіксним оператором зазвичай ключовими словами або символами, такими як: AND, алгебраїчне множення, або символ &. Логічні зв'язки часто використовуються для бітових операцій, де 0 відповідає хибі та 1 відповідає істині:

• 0 AND 0  =  0,
• 0 AND 1  =  0,
• 1 AND 0  =  0,
• 1 AND 1  =  1.

Операція може бути застосована і до двох бінарних виразів рівної довжини, приймаючи побітове AND кожної пари бітів на відповідних позиціях. Наприклад:

• 11000110 AND 10100011  =  10000010.

Див. також

• Булева множина
• Правила де Моргана