Barra de Sheffer

Nas funcións booleanas e no cálculo proposicional, a barra de Sheffer, NAND ("non e") ou non conxunción ^[1], denota unha operación lóxica que é equivalente á negación da operación de conxunción, expresada en linguaxe común como "non ambas as dúas ao mesmo tempo". En electrónica dixital, corresponde á porta NAND. Leva o nome de Henry Maurice Sheffer e escríbese como ${\displaystyle \mid }$ ou como ${\displaystyle \uparrow }$ ou como ${\displaystyle {\overline {\wedge }}}$ ou como ${\displaystyle Dpq}$ en notación polaca por Łukasiewicz (pero non como ||, usado a miúdo para representar a disxunción).

Non conxunción
NAND

Outros nomes	Non E, Not AND
operador booleano	${\displaystyle \lnot (A\land B)}$
linguaxe natural	Non (A e B)
operador de conxuntos	${\displaystyle (A\cap B)^{C}}$
táboa de verdade	${\displaystyle {\begin{array}{c|c||c}A&B&A\uparrow B\\\hline V&V&F\\V&F&V\\F&V&V\\F&F&V\\\end{array}}}$
outros símbolos	${\displaystyle \uparrow }$, ${\displaystyle \mid }$, ${\displaystyle {\overline {\wedge }}}$
porta lóxica

O seu dual é o operador NOR.

Definición

A non conxunción é unha operación lóxica sobre dous valores lóxicos. Produce un valor de verdadeiro, se e só se, polo menos unha das proposicións é falsa.

Táboa de verdade

A táboa de verdade ${\displaystyle A\uparrow B}$ é a seguinte.

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\uparrow B}$
F	F	V
F	V	V
V	F	V
V	V	F

Equivalencias lóxicas

A barra de Sheffer de ${\displaystyle P}$ e ${\displaystyle Q}$ é a negación da súa conxunción

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg (P\land Q)}$
	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg }$

Segundo as leis de De Morgan, isto tamén é equivalente á disxunción das negacións de ${\displaystyle P}$ e ${\displaystyle Q}$

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg P}$	${\displaystyle \lor }$	${\displaystyle \neg Q}$
	${\displaystyle \Leftrightarrow }$		${\displaystyle \lor }$

Notacións e nomes alternativos

En 1913, Sheffer describiu o uso da non disxunción ${\displaystyle \mid }$ e mostrou a súa integridade funcional. Moitas persoas, comezando por Nicod en 1917, e seguidas por Whitehead, Russell e moitos outros, pensaron erróneamente que Sheffer describiu a non conxunción usando ${\displaystyle \mid }$, chamándoo barra de Sheffer.

En 1929, Łukasiewicz utilizou ${\displaystyle D}$ en ${\displaystyle Dpq}$ para non conxunción na súa notación polaca.^[2]

Unha notación alternativa para a non conxunción é ${\displaystyle \uparrow }$. Non está claro quen introduciu por primeira vez esta notación, aínda que a correspondente ${\displaystyle \downarrow }$ para a non disxunción foi usada por Quine en 1940.^[3]

Propiedades

NAND é conmutativa pero non asociativa, o que significa que ${\displaystyle P\uparrow Q\leftrightarrow Q\uparrow P}$ mais ${\displaystyle (P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)}$.^[4]

Completude funcional

A barra de Sheffer, tomada por si soa, é un conxunto funcionalmente completo de conectivas.^[5][6]

Pódes probar mostrando primeiro, cunha táboa de verdade, que ${\displaystyle \neg A}$ é equivalente como función de verdade a ${\displaystyle A\uparrow A}$.^[7] Logo, xa que ${\displaystyle A\uparrow B}$ é equivalente funcionalmente a ${\displaystyle \neg (A\land B)}$, ^[7] e ${\displaystyle A\lor B}$ é equivalente a ${\displaystyle \neg (\neg A\land \neg B)}$, ^[7] a barra de Sheffer abonda para definir o conxunto de conectivas ${\displaystyle \{\land ,\lor ,\neg \}}$, ^[7] que se mostra como verdadeiramente completa polo Teorema da forma normal disxuntiva.^[7]

Outras operacións booleanas en termos da barra de Sheffer

Expresado en termos de NAND ${\displaystyle \uparrow }$, os operadores habituais da lóxica proposicional son:

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle P}$ ${\displaystyle \uparrow }$ ${\displaystyle P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\leftrightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle ((P\uparrow P)\uparrow (Q\uparrow Q))}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow P)}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$