Barra de Sheffer

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 $\bar{\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. Modelo:2-ary truth table

Equivalencias lóxicas

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

$P\uparrow Q$	$\iff$	$\mathrm{\neg }(P\wedge Q)$
	$\iff$	$\mathrm{\neg }$

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

$P\uparrow Q$	$\iff$	$\mathrm{\neg }P$	$\vee$	$\mathrm{\neg }Q$
	$\iff$		$\vee$

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\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 $\mathrm{\neg }A$ é equivalente como función de verdade a $A\uparrow A$. Logo, xa que $A\uparrow B$ é equivalente funcionalmente a $\mathrm{\neg }(A\wedge B)$, e $A\vee B$ é equivalente a $\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B)$, a barra de Sheffer abonda para definir o conxunto de conectivas $\{\wedge ,\vee ,\mathrm{\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:

$\mathrm{\neg }P$     $\iff$     $P$ $\uparrow$ $P$     $\iff$     $\uparrow$		$P\to Q$     $\iff$     $P$ $\uparrow$ $(Q\uparrow Q)$     $\iff$     $P$ $\uparrow$ $(P\uparrow Q)$     $\iff$     $\uparrow$     $\iff$     $\uparrow$		$P\leftrightarrow Q$     $\iff$     $(P\uparrow Q)$ $\uparrow$ $((P\uparrow P)\uparrow (Q\uparrow Q))$     $\iff$     $\uparrow$
$P\wedge Q$     $\iff$     $(P\uparrow Q)$ $\uparrow$ $(P\uparrow Q)$     $\iff$     $\uparrow$		$P\vee Q$     $\iff$     $(P\uparrow P)$ $\uparrow$ $(Q\uparrow Q)$     $\iff$     $\uparrow$

Véxase tamén

Bibliografía

• Modelo:Cita libro (NB. Editado e traducido do francés: Précis de logique mathématique)
• Modelo:Cita libro

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