シェファーストローク

シェファーストローク

ナンド
意味	${\displaystyle {\overline {x\cdot y}}}$
真理値表	${\displaystyle (0111)}$
論理ゲート
正規形
分離的	${\displaystyle {\overline {x}}+{\overline {y}}}$
接続詞	${\displaystyle {\overline {x}}+{\overline {y}}}$
ジェガルキン多項式	${\displaystyle 1\oplus xy}$
ポストの格子
0保存	いいえ
1保存	いいえ
単調	いいえ
アフィン	いいえ
自己双対	いいえ
v t e

ブール関数と命題計算において、シェファーストロークは、通常の言語では「両方ではない」と表現される、連言演算の否定に相当する論理演算を表す。これは、非連言、選択的否定（実質的には少なくとも一方のオペランドが偽であると述べているため）、またはNAND（「かつではない」）とも呼ばれる。^{[ 1 ]}デジタルエレクトロニクスでは、 NANDゲートに相当する。これはヘンリー・モーリス・シェファーにちなんで名付けられ、Łukasiewiczによってポーランド語表記でまたはまたは またはと表記される（ただし、選言を表すのによく使用される || とは表記されない）。 ${\displaystyle \mid}$ ${\displaystyle \uparrow}$ ${\displaystyle {\overline {\wedge}}}$ ${\displaystyle Dpq}$

その双対はNOR演算子（パースの矢、クワインの短剣、またはウェッブ演算子とも呼ばれる）である。その双対と同様に、NANDは他の論理演算子を必要とせずに単独で論理形式体系を構成できる（NANDは機能的に完全である）。この特性により、NANDゲートは現代のデジタルエレクトロニクスにおいて極めて重要であり、コンピュータプロセッサ設計への利用もその一つである。

意味

非論理積は、2つの論理値に対する論理演算です。命題の少なくとも一方が偽である場合にのみ、真という値を生成します。

真理値表

の真理値表は次のとおりです。 ${\displaystyle A\uparrow B}$

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

論理的同値性

と のシェファーストロークはそれらの接続詞の否定である ${\displaystyle P}$ ${\displaystyle Q}$

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

ド・モルガンの法則によれば、これはまた、とを否定する論理和と等しい。${\displaystyle P}$ ${\displaystyle Q}$

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

代替表記と名前

ピアースは非論理積の機能的完全性（これを と表す）を初めて示したが、その結果を公表しなかった。^{[ 2 ] [ 3 ]}ピアースの編集者は非論理積に ）を付け加えた。^{[ 3 ]}${\displaystyle {\overline {\curlywedge}}}$ ${\displaystyle {\overline {\curlywedge}}}$

1911年、シュタムは非論理積の完全性の証明を初めて発表し、これを（シュタムフック）^{[ 4 ]}と非論理和で表し、初めて印刷物でそれらの機能的完全性を示しました。^{[ 5 ]}${\displaystyle \sim}$

1913年、シェファーは非論理和を を用いて記述し、その機能的完全性を示した。シェファーはまた、非論理和に も用いた。^{[ 4 ]} 1917年のニコドに始まり、ホワイトヘッド、ラッセルなど多くの人々が、シェファーが非論理和を を用いて記述したと誤解し、この記号をシェファーストロークと名付けた。 ${\displaystyle \mid}$ ${\displaystyle \wedge}$ ${\displaystyle \mid}$

1928年、ヒルベルトとアッカーマンは演算子との非論理積を記述した。^{[ 6 ] [ 7 ]}${\displaystyle /$

1929年、ウカシェヴィチはポーランド語表記法で非接続詞としてinを使用した。^{[ 8 ]}${\displaystyle D}$ ${\displaystyle Dpq}$

非論理積の別の表記法は である。この表記法を最初に誰が導入したかは明らかではないが、非論理和に対応する表記法は1940年にクワインによって使用された。^{[ 9 ]}${\displaystyle \uparrow}$ ${\displaystyle \downarrow}$

歴史

ストロークは、ヘンリー・モーリス・シェファーにちなんで名付けられました。彼は1913年にアメリカ数学会誌^{[ 10 ]}に、ストロークを用いたブール代数の公理化を提示し、ハンチントンによる標準的な定式化と等価であることを、よく知られた命題論理の演算子（AND、OR、NOT ）を用いて証明しました。ブール代数の自己双対性のため、シェファーの公理は、ストロークの代わりにNANDまたはNOR演算のどちらにも等しく有効です。シェファーは、その論文の中で、ストロークを非論理和（NOR）の記号として解釈し、非論理和については脚注でのみ言及し、専用の記号は用いませんでした。 1917年の論文で、ジャン・ニコが初めてストロークを非論理和（NAND）の記号として使用し、これが現在も行われている方法となりました。^{[ 11 ] [ 12 ]}ラッセルとホワイトヘッドは、1927年に出版された『プリンキピア・マテマティカ』第2版でシェファーストロークを採用し、第1版の「OR」および「NOT」演算の代わりとして提案した。

チャールズ・サンダース・パース（1880）は、30年以上前にNAND演算子とNOR演算子の機能的完全性を発見し、アンフェック（「両方向を切る」という意味）という用語を用いていたが、その発見を公表することはなかった。シェファーの2年前、エドワード・スタムもNAND演算子とNOR演算子を記述し、他のブール演算もそれらで表現できることを示した。^{[ 5 ]}

プロパティ

NANDは可換だが結合的ではない。つまり、しかしである。^{[ 13 ]}${\displaystyle P\uparrow Q\leftrightarrow Q\uparrow P}$ ${\displaystyle (P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)}$

機能の完全性

シェファーストロークは、それ自体では機能的に完全な連結子の集合である。^{[ 14 ] [ 15 ]}これは、NAND が以下の 5 つの特性をいずれも備えていないという事実からわかる。これらの特性はそれぞれ機能的に完全な演算子の集合の少なくとも 1 つの要素には欠けていることが要求され、これらの特性がすべて欠けていても十分である。すなわち、真理値保存、偽値保存、線形性、単調性、自己双対性である。(演算子が真理値保存的であるとは、その引数がすべて真であるときにその値が真であり、偽値保存的であるとは、その引数がすべて偽であるときにその値が偽であることを意味する。) ^{[ 16 ]}

これは、まず真理値表を用いて、 が と真理関数的に同値であることを示すことによって証明することもできます。^{[ 17 ]}次に、 がと真理関数的に同値であるので、^{[ 17 ]}、 がと同値であるので、^{[ 17 ]}シェファーストロークは結合子の集合 を定義するのに十分であり、^{[ 17 ]}これは、選言正規形定理によって真理関数的に完全であることが示されます。^{[ 17 ]}${\displaystyle \neg A}$ ${\displaystyle A\uparrow A}$ ${\displaystyle A\uparrow B}$ ${\displaystyle \neg (A\land B)}$ ${\displaystyle A\lor B}$ ${\displaystyle \neg (\neg A\land \neg B)}$ ${\displaystyle \{\land ,\lor ,\neg \}}$

シェファーストロークに関するその他のブール演算

NAND で表現すると、命題論理の通常の演算子は次のようになります。 ${\displaystyle \uparrow}$

${\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}$

参照

• ブールドメイン
• CMOS
• ゲート当量（GE）
• 論理グラフ
• ブール代数の最小公理
• NANDフラッシュメモリ
• NANDロジック
• ピアースの法則
• ピアース矢印= NOR
• 唯一の十分なオペレータ

参考文献

1. ハウソン、コリン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. p. 43. ISBN 978-0-415-13342-5。
2. Peirce, CS (1933) [1880]. 「定数1つを持つブール代数」. Hartshorne, C.; Weiss, P. (編).チャールズ・サンダース・パース論文集 第4巻 『最も単純な数学』 . マサチューセッツ州: ハーバード大学出版局. pp.  13– 18.
3. Peirce, CS (1933) [1902]. 「最も単純な数学」. Hartshorne, C.; Weiss, P. (編).チャールズ・サンダース・パース論文集 第4巻 『最も単純な数学』 . マサチューセッツ州: ハーバード大学出版局. pp.  189– 262.
4. ザック、R. (2023-02-18)。「シェファーの前のシェファーのストローク：エドワード・スタム」。2023 年 7 月 2 日に取得。
5. Stamm、エドワード・ブロニスワフ[ポーランド語] (1911)。 「Beitrag zur Algebra der Logik」。Monatshefte für Mathematik und Physik (ドイツ語)。22 (1): 137–149。土井: 10.1007/BF01742795。S2CID 119816758。 
6. ヒルベルト、D.;アッカーマン、W. (1928)。Grundzügen der theoretischen Logik (ドイツ語) (第 1 版)。ベルリン: ジュリアス・シュプリンガーの広報。 p. 9.
7. Hilbert, D.; Ackermann, W. (1950). Luce, RE (ed.). Principles of Mathematical Logic . Hammond, LM; Leckie, GG; Steinhardt, F. 訳. ニューヨーク: Chelsea Publishing Company. p. 11.
8. Łukasiewicz、J. (1958) [1929]。Elementy logiki matematycznej (ポーランド語) (2 版)。ワルシャワ: パンストウェ・ヴィダウニクトゥ・ナウコウェ。
9. Quine, W. V (1981) [1940]. Mathematical Logic (Revised ed.). Cambridge, London, New York, New Rochelle, Melbourne and Sydney: Harvard University Press. p. 45.
10. シェファー、ヘンリー・モーリス(1913). 「ブール代数のための5つの独立公準と論理定数への応用」 .アメリカ数学会誌. 14 (4): 481– 488. doi : 10.2307/1988701 . JSTOR 1988701 . 
11. ニコド、ジャン・ジョルジュ・ピエール(1917). 「論理の基本命題の数の削減」.ケンブリッジ哲学協会紀要. 19 : 32–41 .
12. チャーチ、アロンゾ(1956).数理論理学入門. 第1巻.プリンストン大学出版局. p. 134.
13. Rao, G. Shanker (2006).コンピュータサイエンスの数学的基礎. IK International Pvt Ltd. p. 21. ISBN 978-81-88237-49-4。
14. Weisstein, Eric W. 「命題計算」 . mathworld.wolfram.com . 2024年3月22日閲覧。
15. Franks, Curtis (2023)、「Propositional Logic」、Zalta, Edward N.、Nodelman, Uri (eds.)、The Stanford Encyclopedia of Philosophy (Fall 2023 ed.)、Metaphysics Research Lab、Stanford University 、 2024年3月22日閲覧。
16. エミール・レオン・ポスト (1941).数学論理の2値反復システム. Annals of Mathematics studies. 第5巻. プリンストン: プリンストン大学出版局. doi : 10.1515/9781400882366 . ISBN 9781400882366。
17. ハウソン、コリン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. pp.  41– 43. ISBN 978-0-415-13342-5。

さらに読む

• ユゼフ・マリア・ボチェンスキー;メンネ、アルベルト・ハインリヒ[ドイツ語] (1960)数理論理学の正確さ。バード、オットー訳（改訂版）。オランダ、南ホラント州ドルドレヒト: D. ライデル。(注: フランス語版とドイツ語版から編集および翻訳: Précis de logique mathématique )
• パース、チャールズ・サンダース(1931–1935) [1880]. 「定数1つを持つブール代数」.ハーツホーン、チャールズ、ポール・ワイス編著.チャールズ・サンダース・パース論文集. 第4巻. ケンブリッジ:ハーバード大学出版局. pp.  12– 20.

外部リンク

• インターネット哲学百科事典のシェファー・ストロークの記事
• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• 2入力および4入力NANDゲートの実装
• ストローク関数によるいくつかの公理の証明 by Yasuo Setô @ Project Euclid