連言/選言の双対性

命題論理とブール代数では、連言と選言の間に双対性があり、^{[1] [2] [3]}双対性原理とも呼ばれます。^{[4] [5] [6]}これは論理における双対性の最もよく知られた例です。^{[1]この双対性は、以下の}メタ論理的定理から成ります。

• 古典的な命題論理では、連言と選言の接続詞は互いに定義することができ、その結果、そのうちの1つだけを原始的なものとして扱えばよい。^{[4] [1]}
• が、与えられた式 において、すべての連言を選言で、すべての選言を連言で（たとえば で、またはその逆で）置き換えた結果を示す表記として使用され、が のすべての文文字をその否定で（たとえばで）置き換える表記として使用され、記号 が意味的帰結に、⟚ が論理式間の意味的等価性に使用される場合、⟚ 、[4] [7] [6] であることが証明でき、 の場合、かつその場合に限り、 、[7] であることが証明でき 、 さらに^⟚の場合、⟚^である こと が 証明 できる。^[7]（この文脈では、は式 の双対と呼ばれる。）^{[4] [5]}${\displaystyle \varphi ^{D}}$ ${\displaystyle p\land q}$ ${\displaystyle q\lor p}$ ${\displaystyle \varphi }$ ${\displaystyle {\overline {\varphi }}}$ ${\displaystyle \varphi }$ ${\displaystyle p}$ ${\displaystyle \neg p}$ ${\displaystyle \models }$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \neg {\overline {\varphi }}}$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi ^{D}\models \varphi ^{D}}$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \psi ^{D}}$ ${\displaystyle {\overline {\varphi }}^{D}}$ ${\displaystyle \varphi }$

相互定義可能性

接続詞は、次のように相互に定義できます。

${\displaystyle \varphi \vee \psi :\equiv \neg (\neg \varphi \land \neg \psi ).}$ （1）

${\displaystyle \varphi \land \psi :\equiv \neg (\neg \varphi \vee \neg \psi ).}$ （2）

${\displaystyle \neg (\neg \varphi \vee \neg \psi )\equiv \neg \neg (\neg \neg \varphi \land \neg \neg \psi )\equiv \varphi \land \psi .}$ （3）

機能の完全性

選言正規形定理は、結合子の集合が機能的に完全であることを示しているため、これらの結果は、結合子の集合と自体も機能的に完全であることを示しています。 ${\displaystyle \{\land ,\vee ,\neg \}}$ ${\displaystyle \{\land ,\neg \}}$ ${\displaystyle \{\vee ,\neg \}}$

ド・モルガンの法則

ド・モルガンの法則は、これらの接続詞を互いに定義することで、どのような方向から定義しても導かれる。^[1]

${\displaystyle \neg (\varphi \vee \psi )\equiv \neg \varphi \land \neg \psi .}$ （4）

${\displaystyle \neg (\varphi \land \psi )\equiv \neg \varphi \vee \neg \psi .}$ （5）

双対性の性質

文の双対とは、 と のすべての出現を入れ替え、かつすべての命題定数を否定することで得られるものです。例えば、の双対はとなります。式の双対はと表記されます。双対性原理によれば、古典的な命題論理においては、任意の文はその双対の否定に等しいとされています。^{[4] [7]}${\textstyle \vee }$ ${\textstyle \land }$ ${\textstyle (A\land B\vee C)}$ ${\textstyle (\neg A\vee \neg B\land \neg C)}$ ${\textstyle \varphi }$ ${\textstyle \varphi ^{*}}$

双対性原理：すべての に対してが成り立つ。^{[4] [7]}${\textstyle \varphi }$ ${\textstyle \varphi =\neg (\varphi ^{*})}$

証明：複雑性に関する帰納法による。基本ケースとして、任意の原子文 を考える。その双対文は なので、その否定は となり、これは と等価である。帰納法のステップでは、任意の を考え、その結果がそれより複雑性が低いすべての文に当てはまると仮定する。3つのケース： ${\textstyle A}$ ${\textstyle \neg A}$ ${\textstyle \neg \neg A}$ ${\textstyle A}$ ${\textstyle \varphi }$

1. が何らかの に対して の形をとる場合、その双対は となり、したがってその双対の否定は となる。さて、は よりも複雑ではないので、帰納法の仮定より となる。これを代入すると となり、つまり はその双対の否定と等価である。${\textstyle \varphi }$ ${\textstyle \neg \psi }$ ${\textstyle \psi }$ ${\textstyle \neg (\psi ^{*})}$ ${\textstyle \neg \neg (\psi ^{*})}$ ${\textstyle \psi }$ ${\textstyle \varphi }$ ${\textstyle \psi =\neg (\psi ^{*})}$ ${\textstyle \varphi =\neg \neg (\psi ^{*})}$ ${\textstyle \varphi }$
2. が何らかのおよびに対して の形である場合、その双対は となり、したがってその双対の否定は となります。さて、と はよりも複雑ではないため、帰納法の仮定により および となります。代入により が得られ、ド・モルガンの法則によりが得られます。そして、これは再び がその双対の否定と等しいと言っているだけです。${\textstyle \varphi }$ ${\textstyle (\psi \vee \chi )}$ ${\textstyle \psi }$ ${\textstyle \chi }$ ${\textstyle (\psi ^{*}\land \chi ^{*})}$ ${\textstyle \neg (\psi ^{*}\land \chi ^{*})}$ ${\textstyle \psi }$ ${\textstyle \chi }$ ${\textstyle \varphi }$ ${\textstyle \psi =\neg (\psi ^{*})}$ ${\textstyle \chi =\neg (\chi ^{*})}$ ${\textstyle \varphi =\neg (\psi ^{*})\vee \neg (\chi ^{*})}$ ${\textstyle \varphi =\neg (\psi ^{*}\land \chi ^{*})}$ ${\textstyle \varphi }$
3. が の形式である場合、同様の推論により結果が導かれます。${\textstyle \varphi }$ ${\textstyle \psi \vee \chi }$

さらなる双対定理

を仮定する。すると、をに対して一様に代入することにより、が成り立つ。したがって、対偶により となる。したがって最終的に、 という性質により、 が 成り立ち 、これは上で証明した通りである。^[7]また であるため、の場合には、かつ の場合に限り、も成り立つ。^[7]そして系として、の場合には となる。^[7]${\displaystyle \varphi \models \psi }$ ${\displaystyle {\overline {\varphi }}\models {\overline {\psi }}}$ ${\displaystyle \neg P_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle \neg \psi \models \neg \varphi }$ ${\displaystyle \psi ^{D}\models \varphi ^{D}}$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \neg {\overline {\varphi }}}$ ${\displaystyle \varphi ^{DD}=\varphi }$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi ^{D}\models \varphi ^{D}}$ ${\displaystyle \varphi \models \neg \psi }$ ${\displaystyle \varphi ^{D}\models \neg \psi ^{D}}$

連言正規形と選言正規形

選言標準形の式の場合、式は連言標準形になり、 § 否定が双対と意味的に等価であるという結果が与えられると、 は と意味的に等価になります。^{[8] [9]}これは、連言標準形と選言標準形の間で変換する手順を提供します。^[10]選言標準形定理は、命題論理のすべての式が選言標準形で表現可能であることを示しているため、すべての式は、その双対への変換を実行することによって、連言標準形でも表現できます。^[9]${\displaystyle \varphi }$ ${\displaystyle {\overline {\varphi }}^{D}}$ ${\displaystyle \neg \varphi }$

参考文献

^{[11] [12]}

1. 「論理と言語の二重性 | インターネット哲学百科事典」 。 2024年6月10日閲覧。
2. 「1.1 論理演算」www.whitman.edu . 2024年6月10日閲覧。
3. Look, Brandon C. (2014年9月25日). The Bloomsbury Companion to Leibniz. Bloomsbury Publishing. p. 127. ISBN 978-1-4725-2485-0。
4. ハウソン、コリン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. pp. 41, 44– 45. ISBN 978-0-415-13342-5。
5. 「ブール代数 パート1 | Review ICS 241」. courses.ics.hawaii.edu . 2024年6月10日閲覧。
6. Kurki-Suonio, R. (2005-07-20). 「リアクティブシステムの実践理論：動的挙動の漸進的モデリング」Springer Science & Business Media. pp.  80– 81. ISBN 978-3-540-27348-6。
7. ボストック、デイヴィッド (1997). 『中間論理学』 オックスフォード：ニューヨーク：クラレンドン・プレス；オックスフォード大学出版局. pp.  62– 65. ISBN 978-0-19-875141-0。
8. Robinson, Alan JA; Voronkov, Andrei (2001-06-21). 自動推論ハンドブック. Gulf Professional Publishing. p. 306. ISBN 978-0-444-82949-8。
9. Polkowski, Lech T. (2023-10-03). 『Logic: Reference Book for Computer Scientists: The 2nd Revised, Modified, Enlarged Edition for "Logics for Computer and Data Sciences, and Artificial Intelligence". Springer Nature. p. 70. ISBN 978-3-031-42034-4。
10. Bagdasar, Ovidiu (2013-10-28). Concise Computer Mathematics: Tutorials on Theory and Problems. Springer Science & Business Media. p. 36. ISBN 978-3-319-01751-8。
11. マクリディス『オデュッセウス』（2022年）『記号論理学』『Palgrave philosophy today』、スイス、シャム：Palgrave Macmillan、133ページ。ISBN 978-3-030-67395-6。
12. ライオンズ、ジョン (1977-06-02). セマンティクス：第1巻. ケンブリッジ大学出版局. p. 145. ISBN 978-0-521-29165-1。