シェファー脳卒中

シェファーストローク
ナンド
意味
真理値表
論理ゲート
正規形
分離的
接続詞
ジェガルキン多項式
ポストの格子
0 保存	いいえ
1-保存	いいえ
単調	いいえ
アフィン	いいえ
自己双対	いいえ
	ヴ; t; e;

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

その双対はNOR 演算子(ピアースの矢印、クワインの短剣、またはウェッブ演算子とも呼ばれる)です。その双対と同様に、NAND は他の論理演算子なしで単独で使用して論理形式システムを構成できます(NAND は機能的に完全になります)。この特性により、NAND ゲートは現代のデジタルエレクトロニクスにとって重要であり、コンピュータープロセッサの設計での使用も含まれます。

意味

非論理積は、 2 つの論理値に対する論理演算です。命題の少なくとも 1 つが偽である場合にのみ、真値が生成されます。

真理値表

の真理値表は以下のとおりです。 $A\uparrow B$

論理的等価性

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

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

代替表記と名前

ピアースは非論理積の機能的完全性を示した最初の人物であるが（これをと表す）、その結果は公表しなかった。^[2]^[3]ピアースの編集者は非論理積に )を加えた^[^要出典^]。^[3] ${\overline {\curlywedge }}$ ${\overline {\curlywedge }}$

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

1913 年、シェファーは非論理和をを使用して記述し、その機能的完全性を示した。シェファーはまた、非論理和にを使用していた。 ^[^要出典^] 1917 年のニコドに始まり、ホワイトヘッド、ラッセル、その他多くの人々が、シェファーが非論理和をを使用して記述したと誤って考え、これをシェファーストロークと名付けた。 $\mid$ $\wedge$ $\mid$

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

1929年、Łukasiewiczはポーランド語の表記で非接続詞としてinを使用した。^[8] $D$ $Dpq$

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

歴史

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

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

プロパティ

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

機能の完全性

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

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

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

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

参照

参考文献

^ ab ハウソン、コリン (1997)。木を使った論理：記号論理学入門。ロンドン、ニューヨーク：ラウトレッジ。p. 43。ISBN 978-0-415-13342-5。
^ Peirce, CS (1933) [1880]. 「1つの定数を持つブール代数」。 Hartshorne, C.; Weiss, P. (編)。Charles Sanders Peirce 論文集、第4巻 The Simplest Mathematics。マサチューセッツ州: ハーバード大学出版局。 pp. 13–18。
^ ab Peirce, CS (1933) [1902]. 「最も単純な数学」。 Hartshorne, C.; Weiss, P. (編)。Charles Sanders Peirce 論文集、第 4 巻最も単純な数学。マサチューセッツ州: ハーバード大学出版局。 pp. 189–262。
^ ザック、R. (2023-02-18)。「シェファーの前のシェファーのストローク：エドワード・スタム」。2023 年 7 月 2 日に取得。
^ ab Stamm、エドワード・ブロニスワフ[ポーランド語] (1911)。「Beitrag zur Algebra der Logik」。Monatshefte für Mathematik und Physik (ドイツ語)。22 (1): 137–149。土井：10.1007/BF01742795。S2CID 119816758。
^ ヒルベルト、D.;アッカーマン、W. (1928)。Grundzügen der theoretischen Logik (ドイツ語) (第 1 版)。ベルリン: ジュリアス・シュプリンガーの広報。 p. 9.
^ Hilbert, D.; Ackermann, W. (1950). Luce, RE (ed.). Principles of Mathematical Logic . Hammond, LM; Leckie, GG; Steinhardt, F. 訳. ニューヨーク: Chelsea Publishing Company. p. 11.
^ Łukasiewicz、J. (1958) [1929]。Elementy logiki matematycznej (ポーランド語) (2 版)。ワルシャワ: パンストウェ・ヴィダウニクトゥ・ナウコウェ。
^ Quine, W. V (1981) [1940]. Mathematical Logic (改訂版). ケンブリッジ、ロンドン、ニューヨーク、ニューロシェル、メルボルン、シドニー: ハーバード大学出版局. p. 45.
^ Sheffer, Henry Maurice (1913). 「ブール代数の 5 つの独立した公準と論理定数への応用」.アメリカ数学会誌. 14 (4): 481–488. doi : 10.2307/1988701 . JSTOR 1988701.
^ ニコ、ジャン・ジョルジュ・ピエール（ 1917年）。「論理の基本命題の数の削減」ケンブリッジ哲学協会紀要。19 ：32-41。
^ チャーチ、アロンゾ(1956)。数理論理学入門。第1巻。プリンストン大学出版局。134ページ。
^ ラオ、G. シャンカー (2006)。コンピュータサイエンスの数学的基礎。IK インターナショナル Pvt Ltd. p. 21。ISBN 978-81-88237-49-4。
^ Weisstein, Eric W. 「命題計算」。mathworld.wolfram.com 。 2024年3月22日閲覧。
^ 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-03-22取得
^エミール・レオン・ポスト (1941)。 「数学論理の2値反復システム」。数学研究年報。第5巻。プリンストン：プリンストン大学出版局。doi :10.1515/ 9781400882366。ISBN 9781400882366。
^ abcde ハウソン、コリン（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

[:13-1] ハウソン、コリン (1997)。木を使った論理：記号論理学入門。ロンドン、ニューヨーク：ラウトレッジ。p. 43。ISBN 978-0-415-13342-5。

[peirce1880-2] Peirce, CS (1933) [1880]. 「1つの定数を持つブール代数」。 Hartshorne, C.; Weiss, P. (編)。Charles Sanders Peirce 論文集、第4巻 The Simplest Mathematics。マサチューセッツ州: ハーバード大学出版局。 pp. 13–18。

[peirce1902-3] Peirce, CS (1933) [1902]. 「最も単純な数学」。 Hartshorne, C.; Weiss, P. (編)。Charles Sanders Peirce 論文集、第 4 巻最も単純な数学。マサチューセッツ州: ハーバード大学出版局。 pp. 189–262。

[zach2023-4] ザック、R. (2023-02-18)。「シェファーの前のシェファーのストローク：エドワード・スタム」。2023 年 7 月 2 日に取得。

[Stamm_1911-5] Stamm、エドワード・ブロニスワフ[ポーランド語] (1911)。「Beitrag zur Algebra der Logik」。Monatshefte für Mathematik und Physik (ドイツ語)。22 (1): 137–149。土井：10.1007/BF01742795。S2CID 119816758。

[hilbert-ackermann1928-6] ヒルベルト、D.;アッカーマン、W. (1928)。Grundzügen der theoretischen Logik (ドイツ語) (第 1 版)。ベルリン: ジュリアス・シュプリンガーの広報。 p. 9.

[hilbert-ackermann1950-7] Hilbert, D.; Ackermann, W. (1950). Luce, RE (ed.). Principles of Mathematical Logic . Hammond, LM; Leckie, GG; Steinhardt, F. 訳. ニューヨーク: Chelsea Publishing Company. p. 11.

[lukasiewicz1929-8] Łukasiewicz、J. (1958) [1929]。Elementy logiki matematycznej (ポーランド語) (2 版)。ワルシャワ: パンストウェ・ヴィダウニクトゥ・ナウコウェ。

[quine1940-9] Quine, W. V (1981) [1940]. Mathematical Logic (改訂版). ケンブリッジ、ロンドン、ニューヨーク、ニューロシェル、メルボルン、シドニー: ハーバード大学出版局. p. 45.

[Sheffer_1913-10] Sheffer, Henry Maurice (1913). 「ブール代数の 5 つの独立した公準と論理定数への応用」.アメリカ数学会誌. 14 (4): 481–488. doi : 10.2307/1988701 . JSTOR 1988701.

[Nicod_1917-11] ニコ、ジャン・ジョルジュ・ピエール（ 1917年）。「論理の基本命題の数の削減」ケンブリッジ哲学協会紀要。19 ：32-41。

[Church_1956-12] チャーチ、アロンゾ(1956)。数理論理学入門。第1巻。プリンストン大学出版局。134ページ。

[13] ラオ、G. シャンカー (2006)。コンピュータサイエンスの数学的基礎。IK インターナショナル Pvt Ltd. p. 21。ISBN 978-81-88237-49-4。

[:18-14] Weisstein, Eric W. 「命題計算」。mathworld.wolfram.com 。 2024年3月22日閲覧。

[:2-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-03-22取得

[16] ^エミール・レオン・ポスト (1941)。 「数学論理の2値反復システム」。数学研究年報。第5巻。プリンストン：プリンストン大学出版局。doi :10.1515/ 9781400882366。ISBN 9781400882366。

[:132-17] ハウソン、コリン（1997）。木を使った論理：記号論理学入門。ロンドン、ニューヨーク：ラウトレッジ。pp.41-43。ISBN 978-0-415-13342-5。

意味