Штрих Шефера

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

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

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

$A\;|\;B\equiv \lnot (A\land B)$

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

Історія

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

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

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

$A$	$B$	$A\uparrow B$
F	F	T
F	T	T
T	F	T
T	T	F

Властивості

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

$a\;|\;b\equiv b\;|\;a$

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

$\top \equiv (a\;|\;a)\;|\;a$

$a\equiv (a\;|\;a)\;|\;(a\;|\;b)$

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

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

$~\neg a\equiv a\;|\;a$

$a\land b\equiv (a\;|\;b)\;|\;(a\;|\;b)$

$a\lor b\equiv (a\;|\;a)\;|\;(b\;|\;b)$

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

$~a\rightarrow b\equiv a\;|\;(b\;|\;b)\equiv a\;|\;(a\;|\;b)$

Див. також

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

Джерела

• Дрозд Ю. А. (2005). Основи математичної логіки (PDF). Київ: РВЦ “Київський університет„. с. 96. (укр.)