Ver o código fonte de «Barra de Sheffer»

{{infobox
|title       = ''Non conxunción'' <br> NAND
|image = [[ficheiro:Diagrama de Venn 17.svg|230px]]
|label2 = Outros nomes
|data2 = Non E, Not AND
|label5=linguaxe formal 
|data5= <math>A \uparrow B</math>
|label4=linguaxe natural 
|data4= Non (A e B)
|label3 = operador booleano 
|data3 = <math>\lnot (A \land B)</math>
|label5=operador de conxuntos 
|data5= <math>(A \cap B)^C </math>
|label8=outros símbolos
|data8= <math>\uparrow</math>, <math>\mid</math>, <math>\overline{\wedge}</math> 
|label9=porta lóxica
|data9 = [[Ficheiro:NAND ANSI Labelled.svg]]
|label7 = táboa de verdade
|data7 = <math>
\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}
</math>
}}
{{Logical connectives sidebar}}

Nas [[Función booleana|funcións booleanas]] e [[Lóxica proposicional|no cálculo proposicional]], a '''barra de Sheffer''', '''NAND''' ("non e") ou '''non conxunción''' '''<ref name=":13">{{Cite book |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |url=https://archive.org/details/logicwithtreesin0000hows |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=Londres; Nova York |pages=[https://archive.org/details/logicwithtreesin0000hows/page/n58 43]}}</ref>''',  denota unha [[operación lóxica]] que é equivalente á [[Negación (lóxica)|negación]] da operación [[Conxunción lóxica|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 <math>\mid</math> ou como <math>\uparrow</math> ou como <math>\overline{\wedge}</math> ou como <math>Dpq</math> en [[notación polaca]] por Łukasiewicz (pero non como ||, usado a miúdo para representar [[Disxunción lóxica|a disxunción]]).

O seu [[Dualidade (matemáticas)|dual]] é o [[NOR lóxico|operador NOR]]. 

== Definición ==
A '''non conxunción''' é unha operación lóxica sobre dous [[Valor de verdade|valores lóxicos]]. Produce un valor de verdadeiro, se e só se,  polo menos unha das [[proposición (lóxica)|proposicións]] é falsa.

=== Táboa de verdade ===
A [[táboa de verdade]] <math>A \uparrow B</math> é a seguinte.
{{2-ary truth table|1|1|1|0|<math>A \uparrow B</math>}}

=== Equivalencias lóxicas ===
A barra de Sheffer de <math>P</math> e <math>Q</math> é a negación da súa conxunción
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \uparrow Q</math>
|&#x2003;&#x2003;<math>\Leftrightarrow</math>&#x2003;&#x2003;
|<math>\neg (P \land Q)</math>
|-
|[[Ficheiro:Venn1110.svg|50x50px]]
|&#x2003;&#x2003;<math>\Leftrightarrow</math>&#x2003;&#x2003;
|<math>\neg</math> [[Ficheiro:Venn0001.svg|50x50px]]
|}
Segundo as [[leis de De Morgan]], isto tamén é equivalente á disxunción das negacións de <math>P</math> e <math>Q</math>
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \uparrow Q</math>
|&#x2003;&#x2003;<math>\Leftrightarrow</math>&#x2003;&#x2003;
|<math>\neg P</math>
|<math>\lor</math>
|<math>\neg Q</math>
|-
|[[Ficheiro:Venn1110.svg|50x50px]]
|&#x2003;&#x2003;<math>\Leftrightarrow</math>&#x2003;&#x2003;
|[[Ficheiro:Venn1010.svg|50x50px]]
|<math>\lor</math>
|[[Ficheiro:Venn1100.svg|50x50px]]
|}

== Notacións e nomes alternativos ==

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

En 1929, Łukasiewicz utilizou <math>D</math> en <math>Dpq</math> para non conxunción na súa notación polaca.<ref name="lukasiewicz1929">{{cita libro|last1=Łukasiewicz |first1=J. |title=Elementy logiki matematycznej |date=1929|location=Warszawa |publisher=Państwowe Wydawnictwo Naukowe |edition=2}}</ref>

Unha notación alternativa para a non conxunción é <math>\uparrow</math>. Non está claro quen introduciu por primeira vez esta notación, aínda que a correspondente <math>\downarrow</math> para a non disxunción foi usada por Quine en 1940.<ref name="quine1940">{{cita libro |last1=Quine |first1=W. V |title=Mathematical Logic |date=1940 |publisher=Harvard University Press |location=Cambridge, Londres, Nova York, New Rochelle, Melbourne e Sydney |edition=Revised |page=45}}</ref>

== Propiedades ==
NAND é conmutativa pero non asociativa, o que significa que <math>P \uparrow Q \leftrightarrow Q \uparrow P</math> mais <math>(P \uparrow Q) \uparrow R \not\leftrightarrow P \uparrow (Q \uparrow R)</math>.<ref>{{Cita libro |last=Rao |first=G. Shanker |title=Mathematical Foundations of Computer Science |date=2006 |publisher=I. K. International Pvt Ltd |isbn=978-81-88237-49-4 |pages=21 }}</ref>

=== Completude funcional ===
A barra de Sheffer, tomada por si soa, é un conxunto [[Completude funcional|funcionalmente completo]] de conectivas.<ref name=":18">{{Cita web |last=Weisstein |first=Eric W. |title=Propositional Calculus |url=https://mathworld.wolfram.com/ |access-date=2024-03-22 |website=mathworld.wolfram.com |language=en}}</ref><ref name=":2">{{Cita libro |last=Franks |first=Curtis |title=Propositional Logic |date=2023 |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/archives/fall2023/entries/logic-propositional/ |access-date=2024-03-22 |edition=Fall 2023 |publisher=Metaphysics Research Lab, Stanford University |editor2-last=Nodelman |editor2-first=Uri |encyclopedia=The Stanford Encyclopedia of Philosophy}}</ref>

Pódes probar mostrando primeiro, cunha [[táboa de verdade]], que <math>\neg A</math> é equivalente como función de verdade a <math>A \uparrow A</math>.<ref name=":132">{{Cita libro |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |url=https://archive.org/details/logicwithtreesin0000hows |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=Londres; Nova York |pages=[https://archive.org/details/logicwithtreesin0000hows/page/n56 41]–43}}</ref> Logo, xa que <math>A \uparrow B</math> é equivalente funcionalmente a <math>\neg (A \land B)</math>, <ref name=":132" /> e <math>A \lor B</math> é equivalente a <math>\neg(\neg A \land \neg B)</math>, <ref name=":132" /> a barra de Sheffer abonda para definir o conxunto de conectivas <math>\{\land, \lor, \neg\}</math>, <ref name=":132" /> que se mostra como verdadeiramente completa polo [[Teorema da forma normal disxuntiva]].<ref name=":132" />

== Outras operacións booleanas en termos da barra de Sheffer ==
Expresado en termos de NAND <math>\uparrow</math>, os operadores habituais da lóxica proposicional son:
{|
|
{| style="text-align: center; border: 1px solid darkgray;"
|<math>\neg P</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>P</math>
|<math>\uparrow</math>
|<math>P</math>
|-
|[[Ficheiro:Venn10.svg|36x36px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn01.svg|36x36px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn01.svg|36x36px]]
|}
|   
|
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \rightarrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>~P</math>
|<math>\uparrow</math>
|<math>(Q \uparrow Q)</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>~P</math>
|<math>\uparrow</math>
|<math>(P \uparrow Q)</math>
|-
|[[Ficheiro:Venn1011.svg|50x50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn0101.svg|50x50px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn1100.svg|50x50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn0101.svg|50x50px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn1110.svg|50x50px]]
|}
|   
|
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \leftrightarrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \uparrow Q)</math>
|<math>\uparrow</math>
|<math>((P \uparrow P) \uparrow (Q \uparrow Q))</math>
|-
|[[Ficheiro:Venn1001.svg|50x50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn1110.svg|50x50px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn0111.svg|50x50px]]
|}
|-
| 
|-
|
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \land Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \uparrow Q)</math>
|<math>\uparrow</math>
|<math>(P \uparrow Q)</math>
|-
|[[Ficheiro:Venn0001.svg|50x50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn1110.svg|50x50px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn1110.svg|50x50px]]
|}
|   
|
{| style="text-align: center; border: 1px solid darkgray;"
|<math>P \lor Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \uparrow P)</math>
|<math>\uparrow</math>
|<math>(Q \uparrow Q)</math>
|-
|[[Ficheiro:Venn0111.svg|50x50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[Ficheiro:Venn1010.svg|50x50px]]
|<math>\uparrow</math>
|[[Ficheiro:Venn1100.svg|50x50px]]
|}
|}

== Notas ==
{{reflist|30em}} 

== Véxase tamén ==
{{Commonscat}} 
=== Bibliografía ===
* {{cita libro |author-first1=Józef Maria |author-last1=Bocheński |author-link1=Józef Maria Bocheński |date=1960 |title=Precis of Mathematical Logic |author-first2=Albert Heinrich |author-last2=Menne |author-link2=:de:Albert Heinrich Menne |edition=revised |translator-first=Otto |translator-last=Bird |publisher=[[D. Reidel]] |publication-place=Dordrecht, South Holland, Netherlands}} (NB. Editado e traducido do francés: [[Précis de logique mathématique]])
* {{cita libro |chapter=A Boolian<!-- sic! --> Algebra with One Constant |author-first=Charles Sanders |author-last=Peirce |author-link=Charles Sanders Peirce |date=1880 |title=Collected Papers of Charles Sanders Peirce |title-link=Charles Sanders Peirce bibliography#CP |volume=4 |pages=12–20 |publication-place=Cambridge |publisher=[[Harvard University Press]] |editor-first1=Charles |editor-last1=Hartshorne |editor-link1=Charles Hartshorne |editor-first2=Paul |editor-last2=Weiss |editor-link2=Paul Weiss (philosopher) |date=1931–1935}}
=== Outros artigos ===
* [[Dominio booleano]].
* [[Táboa de verdade]]
=== Ligazóns externas ===
* [http://www.iep.utm.edu/Sheffer_stroke/ Sheffer Stroke] artigo na ''[[Internet Encyclopedia of Philosophy]]''
* http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e77vlsi/lab3/ Implementations of 2- and 4-input NAND gates]
* [https://web.archive.org/web/20090526075041/http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.pja/1195520940&page=record Proofs of some axioms by Stroke function by Yasuo Setô] @ [http://projecteuclid.org Project Euclid]

{{control de autoridades}}
[[Categoría:Lóxica]]