結合子の定義不可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/25 04:07 UTC 版)
「直観主義論理」の記事における「結合子の定義不可能性」の解説
古典命題論理において、論理積、論理和または実質含意を基本的なものとすれば、他は否定を用いてウカシェヴィッチの命題論理のようにして定義できる。またこれら4つをパースの矢印（NOR）やシェファーの棒（NAND）のようなただひとつの論理結合子を用いて定義することもできる。同様に、古典一階述語論理において、一方の量化子は他方と否定を用いて定義できる。 これらは全ての結合子はブール関数であるという二値原理からの基本的な帰結である。二値原理は直観主義論理においては成り立たない。ただ無矛盾律だけが成り立つ。結果として、いかなる結合子も不要ではなく、上に述べたどの公理も必要であることが分かる。古典論理において成立する同値性は、直観主義論理においては、幾つかは成り立つけれども、多くは一方の含意だけが成り立つ。次のようなものがある： 論理積と論理和： ( ϕ ∧ ψ ) → ¬ ( ¬ ϕ ∨ ¬ ψ ) {\displaystyle (\phi \wedge \psi )\to \neg (\neg \phi \vee \neg \psi )} ( ϕ ∨ ψ ) → ¬ ( ¬ ϕ ∧ ¬ ψ ) {\displaystyle (\phi \vee \psi )\to \neg (\neg \phi \wedge \neg \psi )} ( ¬ ϕ ∨ ¬ ψ ) → ¬ ( ϕ ∧ ψ ) {\displaystyle (\neg \phi \vee \neg \psi )\to \neg (\phi \wedge \psi )} ( ¬ ϕ ∧ ¬ ψ ) ↔ ¬ ( ϕ ∨ ψ ) {\displaystyle (\neg \phi \wedge \neg \psi )\leftrightarrow \neg (\phi \vee \psi )} 論理積と含意： ( ϕ ∧ ψ ) → ¬ ( ϕ → ¬ ψ ) {\displaystyle (\phi \wedge \psi )\to \neg (\phi \to \neg \psi )} ( ϕ → ψ ) → ¬ ( ϕ ∧ ¬ ψ ) {\displaystyle (\phi \to \psi )\to \neg (\phi \wedge \neg \psi )} ( ϕ ∧ ¬ ψ ) → ¬ ( ϕ → ψ ) {\displaystyle (\phi \wedge \neg \psi )\to \neg (\phi \to \psi )} ( ϕ → ¬ ψ ) ↔ ¬ ( ϕ ∧ ψ ) {\displaystyle (\phi \to \neg \psi )\leftrightarrow \neg (\phi \wedge \psi )} 論理和と含意： ( ϕ ∨ ψ ) → ( ¬ ϕ → ψ ) {\displaystyle (\phi \vee \psi )\to (\neg \phi \to \psi )} ( ¬ ϕ ∨ ψ ) → ( ϕ → ψ ) {\displaystyle (\neg \phi \vee \psi )\to (\phi \to \psi )} 全称量化と存在量化： ( ∀ x ϕ ( x ) ) → ¬ ( ∃ x ¬ ϕ ( x ) ) {\displaystyle (\forall x\ \phi (x))\to \neg (\exists x\ \neg \phi (x))} ( ∃ x ϕ ( x ) ) → ¬ ( ∀ x ¬ ϕ ( x ) ) {\displaystyle (\exists x\ \phi (x))\to \neg (\forall x\ \neg \phi (x))} ( ∃ x ¬ ϕ ( x ) ) → ¬ ( ∀ x ϕ ( x ) ) {\displaystyle (\exists x\ \neg \phi (x))\to \neg (\forall x\ \phi (x))} ( ∀ x ¬ ϕ ( x ) ) ↔ ¬ ( ∃ x ϕ ( x ) ) {\displaystyle (\forall x\ \neg \phi (x))\leftrightarrow \neg (\exists x\ \phi (x))} すると、例えば、 "a or b" は "if not a, then b" よりも強い主張となる。これは古典論理において同値であることと対照的である。他方で "not (a or b)" と "not a, and also not b" は同値となる。 同値を結合子のリストに入れるならば、いくつかの結合子は他から定義できる： ( ϕ ↔ ψ ) ↔ ( ( ϕ → ψ ) ∧ ( ψ → ϕ ) ) {\displaystyle (\phi \leftrightarrow \psi )\leftrightarrow ((\phi \to \psi )\land (\psi \to \phi ))} ( ϕ → ψ ) ↔ ( ( ϕ ∨ ψ ) ↔ ψ ) {\displaystyle (\phi \to \psi )\leftrightarrow ((\phi \lor \psi )\leftrightarrow \psi )} ( ϕ → ψ ) ↔ ( ( ϕ ∧ ψ ) ↔ ϕ ) {\displaystyle (\phi \to \psi )\leftrightarrow ((\phi \land \psi )\leftrightarrow \phi )} ( ϕ ∧ ψ ) ↔ ( ( ϕ → ψ ) ↔ ϕ ) {\displaystyle (\phi \land \psi )\leftrightarrow ((\phi \to \psi )\leftrightarrow \phi )} ( ϕ ∧ ψ ) ↔ ( ( ( ϕ ∨ ψ ) ↔ ψ ) ↔ ϕ ) {\displaystyle (\phi \land \psi )\leftrightarrow (((\phi \lor \psi )\leftrightarrow \psi )\leftrightarrow \phi )} とりわけ { ∨ , ↔ ⊥ } {\displaystyle \{\vee ,\leftrightarrow \bot \}} と { ∨ , ↔ ¬ } {\displaystyle \{\vee ,\leftrightarrow \neg \}} は直観主義的結合子の完全な基底となる。
※この「結合子の定義不可能性」の解説は、「直観主義論理」の解説の一部です。
「結合子の定義不可能性」を含む「直観主義論理」の記事については、「直観主義論理」の概要を参照ください。
- 結合子の定義不可能性のページへのリンク
