https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Shefferscher_StrichShefferscher Strich - Versionsgeschichte2026-06-04T15:24:00ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Shefferscher_Strich&diff=621178&oldid=prev2003:D3:B715:CC29:FAF7:629D:D3DE:5972: Formatierung angepasst2025-05-09T19:57:56Z<p>Formatierung angepasst</p>
<p><b>Neue Seite</b></p><div>[[Datei:Venn1110.svg|mini|200px|[[Venn-Diagramm]] von <math>A\;\;\!\!|\;\;\!\!B</math><br />Die '''Sheffer-Funktion''' ist die Negation des logischen [[Konjunktion (Logik)|''und'']].<br />Im rot markierten Bereich ist die Funktion wahr, also genau da, wo ''und'' falsch ist.]]<br />
<br />
Der '''Sheffersche Strich''' (auch ''Sheffer-Strich'', ''Sheffer-Funktion'', ''Sheffer-Operator'' oder {{enS|Sheffer stroke}}; nach [[Henry Maurice Sheffer]] benannt) bzw. ''[[NAND-Gatter|NAND]]'' ({{enS|'''n'''ot '''and'''}} = nicht und), geschrieben als „|“, bezeichnet in der [[Boolesche Algebra|Booleschen Algebra]] und der [[Aussagenlogik]] einen [[Boolesche Operatoren|booleschen Operator]] bzw. [[Junktor]].<br />
<br />
Die damit begründete logische Operation ist äquivalent zur [[Negation]] der [[Konjunktion (Logik)|Konjunktion]]<br />
([[Und-Gatter|AND]]-Verknüpfung) zweier [[Boolesche Variable|boolescher Variablen]], umgangssprachlich entspricht dies dem „nicht beide“.<br />
<br />
== Definition ==<br />
=== Semantische Definition (Wahrheitstabelle) ===<br />
Der Sheffersche Strich, bezeichnet durch „|“ (oder manchmal auch als „↑“, „NAND“, „<math>\overline{\land}</math>“), ist ein zweistelliger [[Junktor]] der Aussagenlogik, der semantisch durch die folgende [[Wahrheitstabelle]] definiert wird (hierbei steht ''w'' für ''wahr'', ''f'' für ''falsch''):<br />
<br />
{| class="wikitable" style="margin-left:3em; text-align:center;"<br />
|+<br />
!style="width:35px;background:#AAAAAA;"| A<br />
!style="width:35px;background:#AAAAAA;"| B<br />
!style="width:60px"|A | B<br />
|-<br />
| w || w || f<br />
|-<br />
| w || f || w<br />
|-<br />
| f || w || w<br />
|-<br />
| f || f || w<br />
|}<br />
<br />
Die Gesamtaussage zweier durch den Shefferschen Strich verknüpften [[Logische Aussage|Aussagen]] ist wahr, wenn mindestens eine Aussage falsch ist, bzw. dann falsch, wenn beide wahr sind.<br />
<br />
=== Syntaktische Definition ===<br />
Der Sheffersche Strich kann durch die Negation der Konjunktion definiert werden:<br />
: <math>A\;\;\!\!|\;\;\!\!B := \neg (A \wedge B) \equiv \overline{A \wedge B}</math><br />
<br />
== Geschichte ==<br />
Der Sheffersche Strich ist nach [[Henry Maurice Sheffer]] benannt, der eine Menge von fünf unabhängigen Axiomen für boolesche Algebren angab, die von nur einem Junktor Gebrauch machen.<ref>H. M. Sheffer: ''A set of five independent postulates for Boolean algebras, with application to logical constants.'' In: ''Transactions of the American Mathematical Society.'' 14, 1913, S.&nbsp;481–488.</ref> Er selbst zog die Interpretation von <math>p\;\;\!\!|\;\;\!\!q</math> als ''weder <math>p</math> noch <math>q</math>'' in Betracht (wobei er darauf hinwies, dass auch die als ''nicht <math>p</math> oder nicht <math>q</math>'' möglich ist, was dem heutigen Gebrauch entspricht) und zeigte, dass durch diesen Junktor [[Negation]] und [[Logisches Oder|Disjunktion]] ausgedrückt werden können. [[Charles Sanders Peirce]] hatte mehr als dreißig Jahre vorher erkannt, dass sich alle Junktoren durch den Shefferschen Strich und den zu ihm dualen Operator, der [[NOR-Gatter|Peirce-Funktion]] (NOR), ausdrücken lassen.<br />
<br />
== Äquivalenzen ==<br />
Die üblichen Junktoren der Aussagenlogik lassen sich wie folgt durch den Shefferschen Strich ausdrücken:<br />
<br />
{|<br />
|-<br />
| [[Negation]] ([[Komplement-Gatter]]): <math> \neg A \equiv A\;\;\!\!|\;\;\!\!A, </math><br />
|-<br />
| [[Konjunktion (Logik)|Konjunktion]] ([[Und-Gatter]]): <math> A \wedge B \equiv (A\;\;\!\!|\;\;\!\!B)\;\;\!\!|\;\;\!\!(A\;\;\!\!|\;\;\!\!B), </math><br />
|-<br />
| [[Disjunktion]] ([[Oder-Gatter]]): <math> A \vee B \equiv (A\;\;\!\!|\;\;\!\!A)\;\;\!\!|\;\;\!\!(B\;\;\!\!|\;\;\!\!B), </math><br />
|-<br />
| materiale [[Implikation]], Konditional: <math> A \rightarrow B \equiv A\;\;\!\!|\;\;\!\!(B\;\;\!\!|\;\;\!\!B) \equiv A\;\;\!\!|\;\;\!\!(A\;\;\!\!|\;\;\!\!B)</math><br />
|-<br />
| materiale [[Logische Äquivalenz|Äquivalenz]], Bikonditional (XNOR, [[XNOR-Gatter]]): <math>A \leftrightarrow B \equiv (A\;\;\!\!|\;\;\!\!B)\;\;\!\!|\;\;\!\!((A\;\;\!\!|\;\;\!\!A)\;\;\!\!|\;\;\!\!(B\;\;\!\!|\;\;\!\!B))</math><br />
|-<br />
|[[Kontravalenz]], [[Antivalenz]], Alternative (XOR, [[Exklusiv-Oder-Gatter]]): <math>A\;\;\!\!\dot\lor\;\;\!\!B \equiv (A\;\;\!\!|\;\;\!\!(A\;\;\!\!|\;\;\!\!B))\;\;\!\!|\;\;\!\!(B\;\;\!\!|\;\;\!\!(A\;\;\!\!|\;\;\!\!B))</math><br />
|}<br />
<!-- == Formal system based on the Sheffer stroke ==<br />
The following is an example of a [[formal system]] based entirely on the Sheffer stroke, yet having the functional expressiveness of the [[propositional logic]]:<br />
<br />
=== Symbols ===<br />
''p<sub>n</sub>'' for natural numbers ''n'' <br /><br />
( | )<br />
<br />
The Sheffer stroke commutes but does not associate. Hence any formal system including the Sheffer stroke must also include a means of indicating grouping. We shall employ '(' and ')' to this effect.<br />
<br />
We also write ''p'', ''q'', ''r'', … instead of ''p''<sub>0</sub>, ''p''<sub>1</sub>, ''p''<sub>2</sub>.<br />
<br />
=== Syntax ===<br />
'''Construction Rule I:''' For each natural number ''n'', the symbol ''p<sub>n</sub>'' is a [[well-formed formula]] (wff), called an atom.<br />
<br />
'''Construction Rule II:''' If ''X'' and ''Y'' are wffs, then (''X''|''Y'') is a wff.<br />
<br />
'''Closure Rule:''' Any formulae which cannot be constructed by means of the first two Construction Rules are not wffs.<br />
<br />
The letters ''U'', ''V'', ''W'', ''X'', and ''Y'' are metavariables standing for wffs.<br />
<br />
A decision procedure for determining whether a formula is well-formed goes as follows: "deconstruct" the formula by applying the Construction Rules backwards, thereby breaking the formula into smaller subformulae. Then repeat this recursive deconstruction process to each of the subformulae. Eventually the formula should be reduced to its atoms, but if some subformula cannot be so reduced, then the formula is not a wff.<br />
<br />
=== Calculus ===<br />
All wffs of the form<br />
: ((''U''|(''V''|''W''))|((''Y''|(''Y''|''Y''))|((''X''|''V'')|((''U''|''X'')|(''U''|''X'')))))<br />
are axioms. Instances of<br />
: (''U''|(''V''|''W'')), ''U'' <math>\vdash</math> ''W''<br />
are inference rules.<br />
<br />
=== Simplification ===<br />
Since the only connective of this logic is |, the symbol | could be discarded altogether, leaving only the parentheses to group the letters. A pair of parentheses must always enclose a pair of ''wff''s. Examples of theorems in this simplified notation are<br />
<br />
: (''p''(''p''(''q''(''q''((''pq'')(''pq'')))))),<br />
<br />
: (''p''(''p''((''qq'')(''pp'')))).<br />
<br />
The notation can be simplified further, by letting<br />
: (''U'') := (''UU'')<br />
: ((''U'')) <math>\equiv</math> ''U''<br />
for any ''U''. This simplification causes the need to change some rules:<br />
# More than two letters are allowed within parentheses.<br />
# Letters or wffs within parentheses are allowed to commute.<br />
# Repeated letters or wffs within a same set of parentheses can be eliminated.<br />
The result is a parenthetical version of the Peirce [[existential graph]]s.<br />
<br />
Another way to simplify the notation is to eliminate parenthesis by using [[Polish Notation]]. For example, the earlier examples with only parenthesis could be rewritten using only strokes as follows<br />
<br />
: (''p''(''p''(''q''(''q''((''pq'')(''pq'')))))) becomes<br />
: |''p''|''p''|''q''|''q''||''pq''|''pq'', and<br />
<br />
: (''p''(''p''((''qq'')(''pp'')))) becomes,<br />
: |''p''|''p''||''qq''|''pp''.<br />
<br />
This follows the same rules as the parenthesis version, with opening parenthesis replaced with a Sheffer stroke and the (redundant) closing parenthesis removed.<br />
<br />
== See also ==<br />
* [[AND gate]]<br />
* [[Boolean domain]]<br />
* [[CMOS]]<br />
* [[Gate equivalent|Gate equivalent (GE)]]<br />
* [[Laws of Form]]<br />
* [[Logic gate]]<br />
* [[Logical graph]]<br />
* NAND [[Flash Memory]]<br />
* [[NAND logic]]<br />
* [[NOR gate]]<br />
* [[NOT gate]]<br />
* [[OR gate]]<br />
* [[Peirce's law]]<br />
* [[Peirce arrow|Peirce arrow = NOR]]<br />
* [[Propositional logic]]<br />
* [[Sole sufficient operator]]<br />
* [[XOR gate]]<br />
<br />
--><br />
== Eigenschaften und Besonderheiten ==<br />
Der Sheffersche Strich hat die Besonderheit, dass er allein, ohne weitere logische Operatoren, ein für die Aussagenlogik [[Vollständigkeit (Logik)#Funktionale Vollständigkeit von Junktorenmengen|funktional vollständiges]] Junktorensystem bildet. Diese Eigenschaft ist die Grundlage für die große Bedeutung des NAND in der modernen digitalen Elektronik.<br />
<br />
Die NAND-Verknüpfung sowie alle anderen logischen Verknüpfungen können durch [[NAND-Gatter]] respektive deren Verschaltung umgesetzt werden und gelten in der [[Digitaltechnik]] daher als Standardbaustein. Zudem werden NAND-Bausteine häufig benutzt, da sie die günstigsten digitalen Bausteine sind. So werden sehr platzsparend etwa Speicherbausteine wie [[NAND-Flash]]es aus NAND-Bausteinen aufgebaut.<br />
<br />
== Literatur ==<br />
* [[Charles Sanders Peirce]]: ''A Boolean Algebra with One Constant.'' In: C. Hartshorne, P. Weiss (Hrsg.): ''The Simplest Mathematics.'' Harvard University Press, 1880 (''[[Schriften von Charles Sanders Peirce|Collected Papers]].'' Band 4), S.&nbsp;12–20.<br />
* [[Henry Maurice Sheffer]]: ''A set of five independent postulates for Boolean algebras, with application to logical constants.'' In: ''Transactions of the American Mathematical Society.'' 14, 1913, S.&nbsp;481–488.<br />
<br />
== Weblinks ==<br />
* http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html<br />
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e77vlsi/lab3/ implementations of 2 and 4-input NAND gates]<br />
* [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ô.] Project Euclid<br />
* {{IEP|https://iep.utm.edu/sheffers/|The Sheffer Stroke|Odysseus Makridis}}<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
[[Kategorie:Aussagenlogik]]<br />
<br />
[[pt:NOU]]</div>2003:D3:B715:CC29:FAF7:629D:D3DE:5972