多値論理

多値論理（マルチバリュー論理または多重バリュー論理とも呼ばれる）は、 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]

ベルナップ論理 (B ₄)

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

f ¬   T F B B N N F T

f ∧ T B N F T T B N F B B B F F N N F N F F F F F F

f ∨ T B N F T T T T T B T B T B N T T N N F T B N 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}}}$

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

ウカシェヴィチ論理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{aligned}}}$

その後。 ${\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]

参照

• 哲学ポータル
• 心理学ポータル

数理論理学

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

哲学的論理

• 偽のジレンマ
• Mu

デジタルロジック

• 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 出版局. pp. 201. ISBN 978-0-262-01654-4。
5. (Bergmann 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. ペトル・ハジェク著『ファジー論理』。エドワード・N・ザルタ著『スタンフォード哲学百科事典』 2009年春。([1])
9. ローズ、アラン（1951年12月）「真理値が束を形成する論理体系」『数学年報』123 : 152–165 . doi :10.1007/BF02054946. S2CID  119735870.
10. スミス、ニコラス（2012年）『論理：真理の法則』プリンストン大学出版局、124頁。
11. Malinowski, Grzegorz (1993).多値論理. Clarendon Press. 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). 多値論理合成と最適化, Hassoun S. および 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. アブラモビチ, ミロン; ブリューアー, メルビン A.; フリードマン, アーサー D. (1994).デジタルシステムのテストとテスト可能な設計. ニューヨーク: コンピュータサイエンスプレス. 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日閲覧。

さらに詳しい参考文献

一般

• Augusto, Luis M. (2017).多値論理：数学的および計算的入門.ロンドン：College Publications. 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).多値推論の代数的基礎. Kluwer
• マリノフスキー、グジェゴシュ（1993）『多値論理』クラレンドン・プレス、ISBN 978-0-19-853787-8。
• S. ゴットワルド著、『多値論理に関する論文』。論理と計算の研究、第9巻、リサーチ・スタディーズ・プレス：バルドック、ハートフォードシャー、イギリス、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。ハイェクの伝統に則り、多値論理の証明論も扱っています
• ヘンレ、ライナー（1993）『多値論理における自動演繹』クラレンドン・プレス、ISBN 978-0-19-853989-6。
• アゼベド、フランシスコ（2003）。多値論理における制約解決：デジタル回路への応用。IOS Press。ISBN 978-1-58603-304-0。
• ボルク、レナード、ボロウィック、ピオトル (2003).多値論理2：自動推論と実用的応用. シュプリンガー. ISBN 978-3-540-64507-8。
• スタンコビッチ、ラドミール・S.；アストラ、ヤッコ・T.；モラガ、クラウディオ (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。