論理和NOR

論理和NOR

NOR
定義	${\displaystyle {\overline {x+y}}}$
真理値表	${\displaystyle (0001)}$
論理ゲート
正規形
選言的	${\displaystyle {\overline {x}}\cdot {\overline {y}}}$
連言的	${\displaystyle {\overline {x}}\cdot {\overline {y}}}$
ジェガルキン多項式	${\displaystyle 1\oplus x\oplus y\oplus xy}$
ポスト格子
0保存	いいえ
1保存	いいえ
単調	いいえ
アフィン	いいえ
自己双対	いいえ
v t e

ブール論理において、論理和NOR ^{[ 1 ]} 、非論理和、または結合否定^{[ 1 ]}は、論理和ORの否定となる結果を生成する真理値関数演算子です。つまり、( p NOR q )という形式の文は、 pもqも真でないとき、つまりpとqの両方が偽であるときに真となります。これは論理的にandと同等であり、記号は論理否定、はOR、はANDを 表します${\displaystyle \neg (p\lor q)}$ ${\displaystyle \neg p\land \neg q}$ ${\displaystyle \neg}$ ${\displaystyle \lor}$ ${\displaystyle \land}$

非論理和は通常、 またはまたは(接頭辞) またはとして表されます。 ${\displaystyle \downarrow}$ ${\displaystyle {\overline {\vee}}}$ ${\displaystyle X}$ ${\displaystyle \operatorname {NOR} }$

双対の と同様に、NAND 演算子(シェファー ストロークとも呼ばれ、、またはと表記) は、他の論理演算子を使用せずに単独で使用して、論理形式システムを構成できます(NOR は機能的に完全になります)。 ${\displaystyle \uparrow}$ ${\displaystyle \mid}$ ${\displaystyle$

人類を初めて月に運んだ宇宙船で使用されたコンピュータ、アポロ誘導コンピュータは、 3つの入力を持つNORゲートのみを使用して構築されました。^{[ 2 ]}

定義

NOR演算は、2つの論理値（通常は2つの命題の値）に対する論理演算であり、両方のオペランドが偽の場合にのみ真の値を生成します。言い換えれば、少なくとも1つのオペランドが真の場合にのみ 偽の値を生成します

真理値表

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

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

論理的同値

論理和NORは、論理和の否定です ${\displaystyle \downarrow}$

${\displaystyle P\downarrow Q}$	${\displaystyle \Leftrightarrow}$	${\displaystyle \neg (P\lor Q)}$
	${\displaystyle \Leftrightarrow}$	${\displaystyle \neg}$

代替表記と名前

ピアースは非論理和の機能的完全性を示した最初の人物であるが、その結果は公表していない。^{[ 3 ] [ 4 ]}ピアースは非論理和に を、非論理和に を使用した（実際、ピアース自身が使用した は であり、ピアースの編集者がそのような曖昧さを解消した使用法を導入したが、彼は を導入しなかった）。^{[ 4 ]}ピアースは${\displaystyle {\overline {\curlywedge}}}$ ${\displaystyle \curlywedge}$ ${\displaystyle \curlywedge}$ ${\displaystyle {\overline {\curlywedge}}}$ ${\displaystyle \curlywedge}$ ampheck（古代ギリシャ語のἀμφήκης、 amphēkēs、「両方向に切る」から）。 ^{[ 4 ]}

1911年、スタムは非論理積（スタムフックを使用）と非論理和（スタムスターを使用）の両方の記述を初めて発表し、それらの機能的完全性を示しました。^{[ 5 ] [ 6 ]}の論理記法のほとんどの用法では、これを否定に使用していることに注意してください。 ${\displaystyle \sim}$ ${\displaystyle *}$ ${\displaystyle \sim}$

1913年、シェファーは非論理和を記述し、その機能的完全性を示しました。シェファーは非論理和に を、非論理和に を使用しました。 ${\displaystyle \mid}$ ${\displaystyle \wedge}$

1935年、ウェッブは- 値論理における非論理和とその演算子への応用について記述しました。そのため、ウェッブ演算子^{[ 7 ]}、ウェッブ演算^{[ 8 ]}、あるいはウェッブ関数^{[ 9 ]}と呼ばれることもあります。${\displaystyle n}$ ${\displaystyle \mid}$

1940年にクワインは非選言演算子とその用途についても説明した。^{[ 10 ]}そのため、この演算子をピアースの矢やクワインの短剣と呼ぶ人もいる。 ${\displaystyle \downarrow}$

1944年にチャーチは非選言と演算子の使用についても説明した。^{[ 11 ]}${\displaystyle {\overline {\vee}}}$

1954年、ボチェンスキはポーランド語表記における非論理和を表すためにを使用した。^{[ 12 ]}${\displaystyle X}$ ${\displaystyle Xpq}$

APLはaとaを⍱組み合わせたグリフを使用します。^{[ 13 ]}∨~

性質

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

機能的完全性

論理和NORは、それ自体では機能的に完全な結合子の集合である。^{[ 15 ]}これは、まず真理値表を用いて、が真理機能的に と同値であることを示すことによって証明できる。^{[ 16 ]}次に、が真理機能的に と同値であるため^{[ 16 ]}、が と同値であるため^{[ 16 ]}、論理和NORは結合子の集合 を定義するのに十分であり^{[ 16 ]}、これは選言正規形定理によって真理機能的に完全であることが示される。^{[ 16 ]}${\displaystyle \neg A}$ ${\displaystyle A\downarrow A}$ ${\displaystyle A\downarrow B}$ ${\displaystyle \neg (A\lor B)}$ ${\displaystyle A\lor B}$ ${\displaystyle \neg (\neg A\land \neg B)}$ ${\displaystyle \{\land ,\lor ,\neg \}}$

これは、論理 NOR が、機能的に完全な演算子のセットの少なくとも 1 つのメンバーに欠けていることが要求される5 つの特性 (真理値保存、偽値保存、線形、単調、自己双対) のいずれも備えていないという事実からもわかります。

論理NORによるその他のブール演算

NOR演算子には、他のすべての論理演算子をインターレースNOR演算で表現できるという興味深い特徴があります。論理NAND演算子にもこの機能があります。

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

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle P\downarrow P}$ ${\displaystyle \neg}$     ${\displaystyle \Leftrightarrow}$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}$ ${\displaystyle \downarrow}$ ${\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle \downarrow}$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle (P\downarrow P)}$ ${\displaystyle \downarrow}$ ${\displaystyle (Q\downarrow Q)}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle \downarrow}$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle (P\downarrow Q)}$ ${\displaystyle \downarrow}$ ${\displaystyle (P\downarrow Q)}$     ${\displaystyle \Leftrightarrow}$      ${\displaystyle \downarrow}$

参照

• ビットNOR
• ブール代数
• ブール領域
• ブール関数
• 機能的完全性
• NORゲート
• 命題論理
• 唯一の十分な演算子
• 論理NANDの記号としてのシェファーストローク

参考文献

1. コリン・ハウソン（1997年）『木による論理：記号論理入門』ロンドン、ニューヨーク：ラウトレッジ、p.43、ISBN 978-0-415-13342-5。
2. ホール、エルドン・C. (1996).月への旅：アポロ誘導コンピュータの歴史. レストン、バージニア州、米国：アメリカ航空宇宙学会. 196ページ. ISBN 1-56347-185-X。
3. Peirce, CS (1933) [1880]. 「定数1つを持つブール代数」. Hartshorne, C.; Weiss, P. (編).チャールズ・サンダース・パース論文集 第4巻 『最も単純な数学』 . マサチューセッツ州: ハーバード大学出版局. pp.  13– 18.
4. Peirce, CS (1933) [1902]. 「最も単純な数学」. Hartshorne, C.; Weiss, P. (編).チャールズ・サンダース・パース論文集 第4巻 『最も単純な数学』 . マサチューセッツ州: ハーバード大学出版局. pp.  189– 262.
5. スタム、エドワード・ブロニスワフ[ポーランド語] (1911)。 「Beitrag zur Algebra der Logik」。Monatshefte für Mathematik und Physik (ドイツ語)。22 (1): 137–149。土井: 10.1007/BF01742795。S2CID 119816758。 
6. ザック、R. (2023-02-18)。「シェファーの前のシェファーのストローク：エドワード・スタム」。2023 年 7 月 2 日に取得。
7. Webb, Donald Loomis (1935年5月). 「1回の二項演算による任意のn値論理の生成」 . Proceedings of the National Academy of Sciences . 21 (5). USA: National Academy of Sciences : 252– 254. Bibcode : 1935PNAS...21..252W . doi : 10.1073/pnas.21.5.252 . PMC 1076579 . PMID 16577665 .  
8. Vasyukevich, Vadim O. (2011). 「1.10 ベンジャンクション特性（基本公式）」. ラトビア、リガにて執筆.非同期式逐次論理演算子：ベンジャンクションとシーケンション — デジタル回路の解析と設計. 電気工学講義ノート (LNEE). 第101巻（第1版）. ベルリン/ハイデルベルク、ドイツ: Springer-Verlag . p. 20. doi : 10.1007/978-3-642-21611-4 . ISBN 978-3-642-21610-7. ISSN  1876-1100 . LCCN  2011929655 . p. 20:歴史的背景 […] 論理演算子NORは、パース矢印と呼ばれ、ウェッブ演算としても知られています(xiii+1+123+7 ページ) (注: この本の裏表紙には第 4 巻と誤って記載されていますが、実際は第 101 巻です。)
9. Freimann, Michael; Renfro, Dave L.; Webb, Norman (2018-05-24) [2017-02-10]. 「ドナルド・L・ウェッブとは誰か？」科学と数学の歴史. Stack Exchange . 2023年5月18日時点のオリジナルよりアーカイブ。 2023年5月18日閲覧。
10. Quine, W. V (1981) [1940]. Mathematical Logic (Revised ed.). Cambridge, London, New York, New Rochelle, Melbourne and Sydney: Harvard University Press. p. 45.
11. Church, A. (1996) [1944].数学論理学入門. ニュージャージー州: プリンストン大学出版局. p. 37.
12. JM ボチェンスキー (1954)。Précis de logique mathématique (フランス語)。オランダ：FGクルーンダー、ブッスム、ペイバス。 p. 11.
13. Nor、 APL Wiki。
14. Rao, G. Shanker (2006).コンピュータサイエンスの数学的基礎. IK International Pvt Ltd. p. 22. ISBN 978-81-88237-49-4。
15. スマリヤン、レイモンド・M. (1995).一階述語論理. ニューヨーク：ドーバー. pp. 5, 11, 14. ISBN 978-0-486-68370-6。
16. コリン・ハウソン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. pp.  41– 43. ISBN 978-0-415-13342-5。

外部リンク

• ウィキメディア・コモンズにおける論理NOR関連メディア