論理NOR

Binary operation that is true if and only if both operands are false

論理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つの命題の値）に対する論理演算であり、両方のオペランドが偽である場合にのみ真を返します。言い換えれば、少なくとも一方のオペランドが真である場合にのみ偽を返します。

真理値表

の真理値表は次のとおりです。 ${\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年、スタム [pl]は、非論理積（スタムフックを使用）と非論理和（スタムスターを使用）の両方の記述を初めて発表し、それらの機能的完全性を示しました。^{[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). 『月への旅：アポロ誘導コンピュータの歴史』レストン、バージニア州、アメリカ合衆国:アメリカ航空宇宙学会. p. 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は、Peirceの矢印とも呼ばれ、Webb演算としても知られています。(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. また、APL Wiki。
14. ラオ、G. シャンカー (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に関連するメディア

Retrieved from "https://en.wikipedia.org/w/index.php?title=Logical_NOR&oldid=1286995065"