Barra de Sheffer

Non conxunción
NAND

Outros nomes	Non E, Not AND
operador booleano	$\lnot (A\land B)$
linguaxe natural	Non (A e B)
operador de conxuntos	$(A\cap B)^{C}$
táboa de verdade	${\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	$\uparrow$, $\mid$, ${\overline {\wedge }}$
porta lóxica

Conectivas lóxicas
NOT (NON) $\neg A$, $-A$, ${\overline {A}}$, $\sim A$ AND (E) $A\land B$, $A\cdot B$, $AB$, $A\&B$, $A\&\&B$ NAND (NON E) $A{\overline {\land }}B$, $A\uparrow B$, $A\mid B$, ${\overline {A\cdot B}}$ OR (OU) $A\lor B$, $A+B$, $A\mid B$, $A\parallel B$ NOR (NON OU) $A{\overline {\lor }}B$, $A\downarrow B$, ${\overline {A+B}}$ XNOR (NON OU exclusivo) $A\ {\text{XNOR}}\ B$ └ equivalencia $A\equiv B$, $A\Leftrightarrow B$, $A\leftrightharpoons B$ XOR (OU exclusivo) $A{\underline {\lor }}B$, $A\oplus B$ └ non equivalencia $A\not \equiv B$, $A\not \Leftrightarrow B$, $A\nleftrightarrow B$ Implicación $A\Rightarrow B$, $A\supset B$, $A\rightarrow B$ Implicación recíproca $A\Leftarrow B$, $A\subset B$, $A\leftarrow B$

Nas funcións booleanas e no cálculo proposicional, a barra de Sheffer, NAND ("non e") ou non conxunción , 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 $\mid$ ou como $\uparrow$ ou como ${\overline {\wedge }}$ ou como $Dpq$ en notación polaca por Łukasiewicz (pero non como ||, usado a miúdo para representar a disxunción).

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 $A\uparrow B$ é a seguinte.

$A$	$B$	$A\uparrow B$
F	F	V
F	V	V
V	F	V
V	V	F

Equivalencias lóxicas

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

$P\uparrow Q$	$\Leftrightarrow$	$\neg (P\land Q)$
	$\Leftrightarrow$	$\neg$

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

$P\uparrow Q$	$\Leftrightarrow$	$\neg P$	$\lor$	$\neg Q$
	$\Leftrightarrow$		$\lor$

Notacións e nomes alternativos

En 1913, Sheffer describiu o uso da non disxunción $\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 $\mid$, chamándoo barra de Sheffer.

En 1929, Łukasiewicz utilizou $D$ en $Dpq$ para non conxunción na súa notación polaca.

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

Propiedades

NAND é conmutativa pero non asociativa, o que significa que $P\uparrow Q\leftrightarrow Q\uparrow P$ mais $(P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)$.

Completude funcional

A barra de Sheffer, tomada por si soa, é un conxunto funcionalmente completo de conectivas.

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

Outras operacións booleanas en termos da barra de Sheffer

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

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

Véxase tamén

Bibliografía

• Bocheński, Józef Maria; Menne, Albert Heinrich (1960). Precis of Mathematical Logic. Traducido por Bird, Otto (revised ed.). Dordrecht, South Holland, Netherlands: D. Reidel.  (NB. Editado e traducido do francés: Précis de logique mathématique)
• Peirce, Charles Sanders (1931–1935). "A Boolian Algebra with One Constant". En Hartshorne, Charles; Weiss, Paul. Collected Papers of Charles Sanders Peirce 4. Cambridge: Harvard University Press. pp. 12–20. 

Outros artigos

• Dominio booleano.
• Táboa de verdade

Ligazóns externas

• Sheffer Stroke artigo na Internet Encyclopedia of Philosophy
• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• Implementations of 2- and 4-input NAND gates
• Proofs of some axioms by Stroke function by Yasuo Setô @ Project Euclid