Штрих Шефера

Штрих Шеффера (операція NAND) — двомісна логічна операція, яка є запереченням кон'юнкції; тому значення «хибно» одержується тоді й тільки тоді, коли обидва операнди мають значення «істина».

Названа на честь американського логіка Генрі Шеффера. Зазвичай позначається символом ${\displaystyle ~|}$ чи ${\displaystyle ~\uparrow }$.

${\displaystyle A\;|\;B\equiv \lnot (A\land B)}$

У алгебрі логіки та цифровій електроніці має назву «операція NAND» від англ. not and, або «операція І-НЕ». Виконує цю операцію логічний вентиль І-НЕ.

Історія

Штрих було названо на честь Генрі Шеффера, який 1913 року запровадив аксіоматизацію булевої алгебри, застосовуючи лише одну операцію. Він довів еквівалентність своєї теорії стандартним формулюванням , застосовуючи відомі оператори логіки висловлювань («та», «або», «не»). Через самодвоїстість булевої алгебри, аксіоми Шеффера справедливі як для операції NAND («not and»), так і для операції NOR («not or»). Шеффер у своїх роботах визначав штрих як позначку для операції, що протилежна диз'юнкції (NOR), згадуючи про операцію «не кон'юнкції» (NAND) лише у виносках та без якоїсь особливої позначки для неї. Першим вжив позначку штриха для позначення «не кон'юнкції» Жан Нікод (1917 року)^[], і відтоді таке позначення вважається усталеним. Операція «не диз'юнкції», вживана самим Шеффером, також є однією з визначених операцій у булевій алгебрі, але має назву стрілка Пірса або (в деякій літературі^[]) стрілка Пірса-Вебба.

Таблиця істинності в булевій алгебрі

Діаграма Венна для операції ${\displaystyle A|B}$

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

${\displaystyle ~A}$	${\displaystyle ~B}$	${\displaystyle ~A|B}$
0	0	1
0	1	1
1	0	1
1	1	0

Властивості

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

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

• тотожності:

${\displaystyle \top \equiv (a\;|\;a)\;|\;a}$

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

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

Штрих Шеффера є функціонально повною операцією, тобто, усі інші булеві функції може бути побудовано, вживаючи лише одну цю операцію:

${\displaystyle ~\neg a\equiv a\;|\;a}$

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

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

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

${\displaystyle ~a\rightarrow b\equiv a\;|\;(b\;|\;b)\equiv a\;|\;(a\;|\;b)}$

Див. також

• Булева множина
• Закони де Моргана
• Стрілка Пірса
• І-НЕ (логічний вентиль)