多値論理

多値論理（マルチバリュー論理または多重バリュー論理とも呼ばれる）は、 3 つ以上の真理値がある命題計算です。伝統的に、アリストテレスの論理計算では、任意の命題に対して2 つの値（つまり、trueとfalse）しかありませんでした。古典的な2 値論理は、n が2 より大きい場合のn値論理に拡張できます。文献で最もよく知られているのは、3 値論理（例えば、ŁukasiewiczやKleene の論理で、これらはtrue、false、およびunknown の値を受け入れます）、4 値論理、9 値論理、4 つ以上の値を持つ有限値論理（有限多値）、および無限値論理（ファジー論理や確率論理など）です。

歴史

「[二値]論理の父」アリストテレス^{[ 1 ]}は排中律を受け入れたが、二価性原理については重要な区別を行った。『解釈論』第9章[ ^{2 ]では}、未来の出来事に関する言明は必ずしも真か偽かを明確に決められるわけではないと論じた。しかし、彼はこの洞察を体系的な多値論理へと発展させることはなかった。それは彼の古典的な枠組みにおける特別な例外にとどまった。論理学者たちは20世紀までこのアリストテレス論理の伝統を踏襲し、排中律を一貫して用いながらも、未来の偶発事象に関するアリストテレスの懸念を認めていた。古典論理に代わる体系的な論理が登場したのは近代になってからである。

20 世紀には、多値論理の考え方が再び登場しました。ポーランドの論理学者で哲学者のヤン・ウカシェヴィチは1920 年に多値論理のシステムを作り始め、アリストテレスの海戦のパラドックスに対処するために、第 3 の値 (可能な) を使用しました。一方、アメリカの数学者エミール・L・ポスト(1921) も、 n  ≥ 2 ( nは真理値)の追加の真理度を定式化しました。後に、ヤン・ウカシェヴィチとアルフレッド・タルスキは共同で、 n ≥ 2の真理値の論理を定式化しました。1932 年、ハンス・ライヘンバッハは、 n →∞の多真理値の論理を定式化しました。1932年、クルト・ゲーデルは直観主義論理は有限多値論理ではないことを示し、古典論理と直観主義論理の中間のゲーデル論理システムを定義しました。このような論理は中間論理として知られています。

例

クリーネ（強力）K ₃とプリーストロジックP ₃

クリーネの「（強い）不確定性の論理」K ₃（時には）とプリーストの「パラドックスの論理」は、定義されていない、あるいは不確定な第三の真理値Iを追加します。否定（¬）、 連言（∧）、 選言（∨）、 含意（${\displaystyle K_{3}^{S}}$ →K）、および 双条件（↔K）は次のように与えられる：^{[ 3 ]}

¬   T F 私 私 F T

∧ T 私 F T T 私 F 私 私 私 F F F F F

∨ T 私 F T T T T 私 T 私 私 F T 私 F

→K T 私 F T T 私 F 私 T 私 私 F T T T

↔K T 私 F T T 私 F 私 私 私 私 F F 私 T

2つの論理の違いは、トートロジーの定義方法にあります_{。K 3}ではTのみが真理値として指定されますが、 P ₃ではTとIの両方が真理値として指定されます（論理式は、指定された真理値に評価される場合、トートロジーとみなされます）。クリーネの論理では、Iは真でも偽でもない、つまり不確定であると解釈できますが、プリーストの論理では、Iは真でも偽でもある、つまり過剰決定であると解釈できます。K 3にはトートロジーはありませんが、P 3には古典_的な2_値論理と同じトートロジーがあります。^{[ 4 ]}

ボフヴァルの内部三値論理

もう一つの論理は、ドミトリー・ボフヴァルの内部三値論理であり、クリーネの弱三値論理とも呼ばれる。否定と二条件式を除いて、その真理値表は上記のものと全て異なる。^{[ 5 ]}${\displaystyle B_{3}^{I}}$

∧+ T 私 F T T 私 F 私 私 私 私 F F 私 F

∨+ T 私 F T T 私 T 私 私 私 私 F T 私 F

→+ T 私 F T T 私 F 私 私 私 私 F T 私 T

ボクヴァルの内部論理における中間真理値は、他の変数の値に関係なく式内で伝播するため、伝染性があると言える。 ^{[ 5 ]}

ベルナップ論理（B4 _）

ベルナップの論理B _{4 は}K ₃とP ₃を組み合わせたものである。ここでは、過剰決定された真理値をB、不十分決定された真理値をNと表記する。

f ¬   T F B B 北 北 F T

f∧​ T B 北 F T T B 北 F B B B F F 北 北 F 北 F F F F F F

f ∨ T B 北 F T T T T T B T B T B 北 T T 北 北 F T B 北 F

ゲーデル論理G _kとG _∞

1932年、ゲーデルは^{[ 6 ]}有限個の真理値を持つ多値論理の族を定義した。例えば、は真理値を持ち、 は真理値を持つ。同様に、彼は無限個の真理値を持つ論理 を定義した。この論理では、真理値は区間 内のすべての実数である。これらの論理における指定された真理値は1である。 ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{k-1}},{\tfrac {2}{k-1}},\ldots ,{\tfrac {k-2}{k-1}},1}$ ${\displaystyle G_{3}}$ ${\displaystyle 0,{\tfrac {1}{2}},1}$ ${\displaystyle G_{4}}$ ${\displaystyle 0,{\tfrac {1}{3}},{\tfrac {2}{3}},1}$ ${\displaystyle G_{\infty}}$ ${\displaystyle [0,1]}$

論理積と論理和は、それぞれオペランドの 最小値と最大値として定義されます。${\displaystyle \wedge}$ ${\displaystyle \vee}$

${\displaystyle {\begin{aligned}u\wedge v&:=\min\{u,v\}\\u\vee v&:=\max\{u,v\}\end{aligned}}}$

否定と含意は次のように定義されます。 ${\displaystyle \neg_{G}}$ ${\displaystyle {\xrightarrow[{G}]{}}}$

${\displaystyle {\begin{aligned}\neg _{G}u&={\begin{cases}1,&{\text{if }}u=0\\0,&{\text{if }}u>0\end{cases}}\\[3pt]u\mathrel {\xrightarrow[{G}]{}} v&={\begin{cases}1,&{\text{if }}u\leq v\\v,&{\text{if }}u>v\end{cases}}\end{aligned}}}$

ゲーデル論理は完全に公理化可能であり、つまり、すべてのトートロジーが証明可能な論理計算を定義することが可能である。上記の含意は、最大値と最小値の演算が無限分配法則を持つ完全格子を形成するという事実によって定義される唯一のハイティング含意であり、この格子上に唯一の完全ハイティング代数構造が定義される。

Łukasiewicz ロジックL _vおよびL _∞

含意と否定は、Jan Łukasiewiczによって次の機能を通じて定義されました。 ${\displaystyle {\xrightarrow[{L}]{}}}$ ${\displaystyle {\underset {L}{\neg }}}$

${\displaystyle {\begin{aligned}{\underset {L}{\neg }}u&:=1-u\\u\mathrel {\xrightarrow[{L}]{}} v&:=\min\{1,1-u+v\}\end{aligned}}}$

ウカシェヴィチは1920年にこれらの定義を、真理値 を持つ三値論理 に初めて用いた。1922年には、無限個の値を持つ論理を開発した。この論理では、真理値は区間 内の実数にまたがる。どちらの場合も、指定された真理値は1であった。^{[ 7 ]}${\displaystyle L_{3}}$ ${\displaystyle 0,{\frac {1}{2}},1}$ ${\displaystyle L_{\infty}}$ ${\displaystyle [0,1]}$

ゲーデル論理と同様に定義された真理値を採用することで、有限値論理族、すなわち前述の論理と 論理を作成することができます。これらの論理では、真理値は区間 内の有理数によって与えられます。とにおけるトートロジーの集合は同一です。 ${\displaystyle 0,{\tfrac {1}{v-1}},{\tfrac {2}{v-1}},\ldots ,{\tfrac {v-2}{v-1}},1}$ ${\displaystyle L_{v}}$ ${\displaystyle L_{\infty}}$ ${\displaystyle L_{\aleph _{0}}}$ ${\displaystyle [0,1]}$ ${\displaystyle L_{\infty}}$ ${\displaystyle L_{\aleph _{0}}}$

積論理Π

積論理では、区間、連言、含意に真理値があり、以下のように定義される^{[ 8 ]}${\displaystyle [0,1]}$ ${\displaystyle \odot}$ ${\displaystyle {\xrightarrow[{\Pi }]{}}}$

${\displaystyle {\begin{aligned}u\odot v&:=uv\\u\mathrel {\xrightarrow[{\Pi }]{}} v&:={\begin{cases}1,&{\text{if }}u\leq v\\{\frac {v}{u}},&{\text{if }}u>v\end{cases}}\end{aligned}}}$

さらに、偽の概念を表す負の指定値があります。この値を通して、否定と追加の接続詞を以下のように定義することができます。 ${\displaystyle {\overline {0}}}$ ${\displaystyle {\underset {\Pi }{\neg }}}$ ${\displaystyle {\underset {\Pi }{\wedge }}}$

${\displaystyle {\begin{aligned}{\underset {\Pi }{\neg }}u&:=u\mathrel {\xrightarrow[{\Pi }]{}} {\overline {0}}\\u\mathbin {\underset {\Pi }{\wedge }} v&:=u\odot \left(u\mathrel {\xrightarrow[{\Pi }]{}} v\right)\end{整列}}}$

その後。 ${\displaystyle u\mathbin {\underset {\Pi }{\wedge }} v=\min\{u,v\}}$

ポストロジックP _m

1921年、ポストは（およびのように）真理値 を持つ論理の族を定義しました。否定、連言、および選言は 以下のように定義されます。 ${\displaystyle P_{m}}$ ${\displaystyle L_{v}}$ ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{m-1}},{\tfrac {2}{m-1}},\ldots ,{\tfrac {m-2}{m-1}},1}$ ${\displaystyle {\underset {P}{\neg }}}$ ${\displaystyle {\underset {P}{\wedge }}}$ ${\displaystyle {\underset {P}{\vee }}}$

${\displaystyle {\begin{aligned}{\underset {P}{\neg }}u&:={\begin{cases}1,&{\text{if }}u=0\\u-{\frac {1}{m-1}},&{\text{if }}u\not =0\end{cases}}\\[6pt]u\mathbin {\underset {P}{\wedge }} v&:=\min\{u,v\}\\[6pt]u\mathbin {\underset {P}{\vee }} v&:=\max\{u,v\}\end{aligned}}}$

ローズロジック

1951年、アラン・ローズは真理値が束を形成するシステムのための別の論理族を定義した。^{[ 9 ]}

古典論理との関係

論理学は通常、命題の意味的性質を変換を通して保存するための規則を体系化することを意図した体系です。古典論理においては、この性質は真理です。有効な議論においては、前提が共に真であれば、導出された命題の真理性は保証されます。なぜなら、有効な手順を適用することでこの性質が保存されるからです。しかし、この性質は真理の性質である必要はなく、他の概念であっても構いません。

多値論理は、指示性（または指示される）の性質を保持することを意図しています。真理値は2つ以上存在するため、推論規則は、（関連する意味で）真理に対応するものだけでなく、それ以上のものを保持することを意図する場合があります。例えば、3値論理では、最大の2つの真理値（例えば正の整数として表される場合）が指定され、推論規則はこれらの値を保持することがあります。正確には、妥当な議論とは、前提を合わせた値が常に結論以下となるような議論を指します。

たとえば、保存される特性は、直観主義論理の基本概念である正当化である可能性がある。したがって、命題は真でも偽でもなく、正当化されているか欠陥があるかである。この場合、正当化と真理の間の重要な違いは、排中律が成り立たないことである。欠陥のない命題は必ずしも正当化されるわけではなく、欠陥があることが証明されていないだけだ。重要な違いは、保存される特性の決定性である。つまり、 Pが正当化されていることを証明することも、Pに欠陥があることを証明することも、どちらも証明できないこともある。有効な議論は変換をまたいで正当化を保存するので、正当化された命題から導かれた命題は依然として正当化される。ただし、古典論理には排中律に依存する証明があり、その法則はこのスキームでは使用できないので、その方法では証明できない命題がある。

ススコの論文

多値論理の機能完全性

関数的完全性とは、有限論理および有限代数の特殊な性質を説明するために使用される用語である。論理の連結子の集合が関数的に完全または適切であるとは、その連結子の集合を用いてあらゆる可能な真理関数に対応する式を構成できる場合に限る。^{[ 10 ]}適切な代数とは、あらゆる有限変数の写像がその演算の何らかの組み合わせによって表現できる代数である。^{[ 11 ]}

古典論理：CL = ({0,1}, ¬ , →, ∨, ∧, ↔)は機能的に完全であるが、Łukasiewicz論理や無限値論理にはこの性質がない。^{[ 11 ] [ 12 ]}

有限多値論理はL _n ({1, 2, ..., n } ƒ ₁ , ..., ƒ _m )と定義できる。ここでn ≥ 2は与えられた自然数である。ポスト(1921)は、論理が任意のm^次モデルの関数を生成できると仮定すると、適切な論理L _nには、 m+1 次モデルを生成できる対応する結合子の組み合わせが存在することを証明した。^{[ 13 ]}

アプリケーション

多値論理の既知の応用は、大まかに2つのグループに分類できます。^{[ 14 ]}最初のグループは、多値論理を用いて2値問題をより効率的に解くものです。例えば、多出力ブール関数を表現するためのよく知られたアプローチは、その出力部分を単一の多値変数として扱い、それを単一出力の特性関数（具体的には指示関数）に変換することです。多値論理の他の応用としては、入力デコーダを備えたプログラマブルロジックアレイ（PLA）の設計、有限ステートマシンの最適化、テスト、検証などがあります。

2つ目のグループは、多値メモリ、演算回路、フィールドプログラマブルゲートアレイ（FPGA）など、2つ以上の離散信号レベルを用いる電子回路の設計を対象としています。多値回路は、標準的な2値回路に比べて多くの理論的な利点を持っています。例えば、回路内の信号レベルが2レベルではなく4レベル以上であれば、チップ内外の相互接続を削減できます。メモリ設計では、メモリセルあたり1ビットではなく2ビットの情報を格納することで、同じダイサイズでメモリ密度を2倍に高めることができます。演算回路を用いるアプリケーションでは、2値システムの代わりに、より効率的な方法を用いることでメリットが得られることがよくあります。例えば、剰余数システムや冗長数システム^{[ 15 ]}は、通常の2値加算や減算に伴うリップルスルーキャリーを削減または排除できるため、高速演算が可能になります。これらの数システムは、多値回路を用いて自然に実装できます。しかし、これらの潜在的な利点の実用性は、回路の実現可能性に大きく依存しており、その実現可能性は、現在の標準技術と互換性があるか、あるいは競合可能である必要があります。多値論理は、電子回路の設計を支援するだけでなく、回路の故障や欠陥をテストするためにも広く利用されています。デジタル回路のテストに使用される既知の自動テストパターン生成（ATG）アルゴリズムは、基本的にすべて、5値論理（0、1、x、D、D'）を解読できるシミュレータを必要とします。^{[ 16 ]}追加の値（x、D、D'）は、(1) 未知／初期化されていない値、(2) 1ではなく0、(3) 0ではなく1を表します。

研究会場

IEEE国際多値論理シンポジウム（ISMVL）は1970年から毎年開催されており、主にデジタル設計と検証のアプリケーションを対象としています。^{[ 17 ]}また、 「Journal of Multiple-Valued Logic and Soft Computing」という雑誌もあります。^{[ 18 ]}

参照

数理論理学

• 真実の度合い
• ファジー論理
• ゲーデル論理
• ジャイナ教の七値論理
• クリーネ論理
• クリーネ代数（反転を含む）
• ウカシェヴィチ論理
• MV代数
• ポストロジック
• 二価性の原理
• AN プライア
• 関連性ロジック

哲学的論理

• 偽のジレンマ
• ムー

デジタルロジック

• MVCML、多値電流モードロジック
• IEEE 1164 VHDLの9つの値を持つ標準
• IEEE 1364 はVerilogの 4 値標準です
• 3状態論理
• ノイズベースのロジック

参考文献

1. ハーレー、パトリック.論理学簡潔入門、第9版. (2006).
2. ジュール・ヴュイユマン「必然か偶然か」 CSLI講義ノート第56号、スタンフォード大学、1996年、133-167頁
3. (ゴットワルド 2005、19ページ)
4. ハンバーストーン、ロイド (2011). 『The Connectives』 マサチューセッツ州ケンブリッジ: MIT Press. pp.  201. ISBN 978-0-262-01654-4。
5. （バーグマン 2008、p.80）
6. ゲーデル、クルト (1932)。 「Zum intuitionistischen Aussagenkalkül」。ウィーンのアカデミー・デア・ヴィッセンシャフテン(69): 65f。
7. クライザー、ローター;ゴットヴァルト、ジークフリート。ステルツナー、ヴェルナー (1990)。Nichtklassische Logik。アイネ・アインフュールング。ベルリン：Akademie-Verlag。41ページ以降～ 45ページ以降 。ISBN 978-3-05-000274-3。
8. Hajek, Petr:ファジー論理. Edward N. Zalta:スタンフォード哲学百科事典, 2009年春. ( [1] )
9. ローズ、アラン（1951年12月）「真理値が束を形成する論理体系」『数学年報』123 : 152–165 . doi : 10.1007/BF02054946 . S2CID 119735870 . 
10. スミス、ニコラス（2012年）『論理：真理の法則』プリンストン大学出版局、124頁。
11. マリノフスキー、グジェゴシュ (1993).多値論理. クラレンドン・プレス. pp.  26– 27.
12. チャーチ、アロンゾ（1996年）『数理論理学入門』プリンストン大学出版局、ISBN 978-0-691-02906-1。
13. ポスト, エミール・L. (1921). 「基本命題の一般理論入門」.アメリカ数学ジャーナル. 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN 0002-9327 . JSTOR 2370324 .  
14. Dubrova, Elena (2002).「Multiple-Valued Logic Synthesis and Optimization」 , Hassoun S. and Sasao T. 編, Logic Synthesis and Verification , Kluwer Academic Publishers, pp. 89-114
15. Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (2008年8月22日). 「50 Years of CORDIC: Algorithms, Architectures and Applications」(PDF) . IEEE Transactions on Circuits & Systems I: Regular Papers . 56 (9) (2009年9月9日発行): 1893– 1907. doi : 10.1109/TCSI.2009.2025803 . S2CID 5465045. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) . 2016年1月3日閲覧。 
16. ; Breuer, Melvin A.; Friedman, Arthur D. (1994).デジタルシステムのテストとテスト可能な設計. ニューヨーク: Computer Science Press. p.  183. ISBN 978-0-7803-1062-9。
17. 「IEEE International Symposium on Multiple-Valued Logic (ISMVL)」 . www.informatik.uni-trier.de/~ley . 2011年4月20日時点のオリジナルよりアーカイブ。 2011年4月16日閲覧。
18. “MVLSC home” . 2014年3月15日時点のオリジナルよりアーカイブ。2011年8月12日閲覧。

さらに読む

一般的な

• アウグスト、ルイス・M. (2017). 『多値論理：数学と計算入門』ロンドン: カレッジ出版. 340ページ. ISBN 978-1-84890-250-3。ウェブページ
• Béziau J.-Y. (1997)「多値論理とは何か？第27回国際多値論理シンポジウムの議事録」 IEEEコンピュータ協会、ロサンゼルスアラミトス、pp. 117–121。
• マリノフスキー、グレゴルツ（2001）、多値論理、ゴブル、ルー編、『ブラックウェル哲学論理ガイド』、ブラックウェル。
• バーグマン、メリー（2008）、多値論理とファジー論理入門：意味論、代数、導出システム、ケンブリッジ大学出版局、ISBN 978-0-521-88128-9
• Cignoli、RLO、D'Ottaviano、I、ML、Mundici、D.、(2000)。多値推論の代数的基礎。クルーワー。
• マリノフスキー、グジェゴシュ（1993）『多値論理』クラレンドン・プレス、ISBN 978-0-19-853787-8。
• S. Gottwald , 『多値論理に関する論文』、論理と計算の研究、第9巻、Research Studies Press: Baldock, Hertfordshire, England, 2001年。
• ゴットヴァルト、ジークフリート (2005). 「多値論理」(PDF) . 2016年3月3日時点のオリジナルよりアーカイブ。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
• ミラー、D. マイケル; ソーントン、ミッチェル A. (2008).多値論理：概念と表現. デジタル回路とシステムに関するシンセシス講義. 第12巻. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2。
• Hájek P. , (1998),ファジー論理のメタ数学. Kluwer. （ファジー論理は、独自の多値論理として理解される。）

特定の

• アレクサンドル・ジノヴィエフ『多値論理の哲学的問題』D.ライデル出版社、169ページ、1963年。
• プライア・A. 1957年、『時間と様相』、オックスフォード大学出版局、1956年のジョン・ロック講義に基づく
• Goguen JA 1968/69、「不正確な概念の論理」、Synthese、19、325–373。
• Chang CCとKeisler HJ 1966.連続モデル理論、プリンストン、プリンストン大学出版局。
• Gerla G. 2001、「ファジー論理：近似推論のための数学的ツール」、Kluwer Academic Publishers、ドルドレヒト。
• Novák, V.、Perfilieva, I.、Močkoř, J.、(1999)、ファジー論理の数学的原理。ボストン、クルーワー。
• Pavelka J. 1979、「ファジー論理について I: 多値推論規則」、Zeitschr. f. math. Logik und Grundlagen d. Math.、25、45–52。
• メトカーフ、ジョージ、オリベッティ、ニコラ、ドヴ・M・ギャベイ(2008). 『ファジィ論理の証明理論』 シュプリンガー. ISBN 978-1-4020-9408-8。Hájek の伝統に従って、多値論理の証明理論もカバーしています。
• ヘンレ、ライナー（1993）『多値論理における自動演繹』クラレンドン・プレス、ISBN 978-0-19-853989-6。
• アゼベド、フランシスコ（2003）『多値論理における制約解決：デジタル回路への応用』 IOS Press. ISBN 978-1-58603-304-0。
• ボルク、レナード、ボロウィック、ピオトル (2003). 『多値論理2：自動推論と実用的応用』 シュプリンガー. ISBN 978-3-540-64507-8。
• Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012).多値論理関数の表現. Morgan & Claypool Publishers. doi : 10.2200/S00420ED1V01Y201205DCS037 . ISBN 978-1-60845-942-1。
• アブラモビッチ、ミロン、ブリューアー、メルビン・A、フリードマン、アーサー・D (1994).『デジタルシステムのテストとテスト可能な設計』ニューヨーク：コンピュータサイエンス・プレス. ISBN 978-0-7803-1062-9。

外部リンク

• ゴットヴァルト、ジークフリート (2022). 「多値論理」 . ザルタ、エドワード・N. (編). 『スタンフォード哲学百科事典』（2022年夏版） .
• ヤロスラフ・シュラムコ、ハインリッヒ・ワンシング（2021年）「真理値」。エドワード・N・ザルタ編『スタンフォード哲学百科事典』（2021年冬版）所収。
• IEEEコンピュータ協会の多値論理に関する技術委員会
• ライナー・ヘンレ著『多値論理のためのリソース』 （チャルマース大学）
• 多値ロジック W3 サーバー(アーカイブ)
• ヤロスラフ・シュラムコ、ハインリヒ・ヴァンシング（2020年）「シュシュコのテーゼ」スタンフォード哲学百科事典。
• Carlos Caleiro、Walter Carnielli、Marcelo E. Coniglio、João Marcos、「Two's company: "The humbug of many logic values"」 、 Wayback Machineにて2014年9月29日アーカイブ、 Jean-Yves Beziau編 (2007). Logica Universalis: Towards a General Theory of Logic (2nd ed.). Springer Science & Business Media. pp.  174– 194. ISBN 978-3-7643-8354-1。