シェファーストローク

シェファーストローク
ナンド
意味
真理値表
論理ゲート
正規形
分離的
接続詞
ジェガルキン多項式
ポストの格子
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 は、機能的に完全な演算子の集合の少なくとも 1 つのメンバーには欠けていることが要求され、これらすべてが欠けていても十分である以下の 5 つのプロパティを備えていません: 真理値保存、偽りの保存、線形性、単調性、自己双対性。(演算子は、その引数がすべて真である場合にその値が真である場合に真理値保存であり、引数がすべて偽である場合にその値が偽である場合に偽りの保存です。) ^[13]したがって、{NAND} は機能的に完全な集合です。

これは次のようにも実現できます。機能的に完全な集合 {AND、OR、NOT} の 3 つの要素はすべて、NAND のみを使用して構築できます。したがって、集合 {NAND} も機能的に完全である必要があります。

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

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

機能の完全性

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

参照

参考文献

^ 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。
^ Zach, R. (2023-02-18). 「Shefferの前のShefferのストローク：エドワード・スタム」。 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ページ。
^エミール・レオン・ポスト (1941)。 「数学論理の2値反復システム」。数学研究年報。第5巻。プリンストン：プリンストン大学出版局。doi :10.1515/ 9781400882366。ISBN 9781400882366。
^ 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取得
^ abcde ハウソン、コリン（1997）。木を使った論理：記号論理学入門。ロンドン、ニューヨーク：ラウトレッジ。pp.41-43。ISBN 978-0-415-13342-5。

さらに読む

Bocheński, Józef Maria ; Menne, Albert Heinrich [ドイツ語] (1960)。『数学論理学要旨』。Bird, Otto (改訂版) 訳。オランダ、南ホラント州ドルドレヒト: D. Reidel。(注: フランス語版とドイツ語版から編集および翻訳: 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] Zach, R. (2023-02-18). 「Shefferの前のShefferのストローク：エドワード・スタム」。 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] ^エミール・レオン・ポスト (1941)。 「数学論理の2値反復システム」。数学研究年報。第5巻。プリンストン：プリンストン大学出版局。doi :10.1515/ 9781400882366。ISBN 9781400882366。

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

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