真理関数

論理学において、真理関数^{[ 1 ]}とは、真理値を入力として受け取り、一意の真理値を出力として生成する関数である。言い換えれば、真理関数の入力と出力はすべて真理値であり、真理関数は常に正確に1つの真理値を出力し、同じ真理値を入力すると常に同じ真理値が出力される。典型的な例は命題論理であり、論理結合子で接続された個々の命題を用いて複合命題が構成される。複合命題の真理値が構成要素となる命題の真理値によって完全に決定される場合、その複合命題は真理関数と呼ばれ、使用される論理結合子は真理関数的であると言われる。^{[ 2 ]}

古典的な命題論理は真理関数論理であり、^{[ 3 ]}すべての命題は真または偽のいずれかの真理値のみを持ち、すべての論理結合子は真理関数（対応する真理値表を持つ）であるため、すべての複合命題は真理関数である。^{[ 4 ]}一方、様相論理は真理関数ではない。

論理結合子は、複合文の真偽値がその部分文の真偽値の関数である場合に真理関数的である。結合子のクラスは、その各メンバーが真理関数的である場合に真理関数的である。たとえば、結合子「and」は真理関数的である。なぜなら、「リンゴは果物であり、ニンジンは野菜である」のような文は、その部分文「リンゴは果物である」と「ニンジンは野菜である」がそれぞれ真である場合に限り真であり、そうでない場合は偽だからである。英語などの自然言語の結合子の中には、真理関数的ではないものもある。

「xは…と信じている」という形式の接続詞は、真理関数ではない接続詞の典型的な例です。例えば、メアリーがアル・ゴアが2000年4月20日にアメリカ合衆国大統領だったと誤って信じているが、月が緑色のチーズでできているとは信じていない場合、次の文は真理関数ではありません。

「メアリーは、2000年4月20日にアル・ゴアがアメリカ合衆国大統領だったと信じている。」

真である一方

「メアリーは月が緑色のチーズでできていると信じている」

どちらの場合も、各構成要素文（つまり、「アル・ゴアは2000年4月20日にアメリカ合衆国大統領だった」と「月は緑色のチーズでできている」）は偽ですが、「メアリーは～と信じている」という句を接頭辞として形成した複合文はそれぞれ真偽値が異なります。つまり、「メアリーは～と信じている」という形式の文の真偽値は、構成要素文の真偽値のみによって決定されるわけではないため、（単項）結合子（単項なので単に演算子）は真偽関数ではありません。

論理式を構成する際に用いられる古典論理の結合子（例：&、→）は真理関数的である。これらの結合子の引数としての様々な真理値に対する値は、通常、真理値表によって与えられる。真理関数的命題論理は、その論理式が真または偽のいずれかとして解釈される形式体系である。

二値論理では、2つの入力PとQに対して、16種類の真理関数（ブール関数とも呼ばれる）が存在します。これらの関数はいずれも、古典論理における特定の論理結合子の真理値表に対応しており、引数の一方または両方に依存しない関数など、いくつかの特殊なケースも含まれます。以下の真理値表では、簡潔にするため、真理と偽をそれぞれ1と0で表します。

関数は合成として表現できるため、真理関数論理計算では、上述のすべての関数が機能的に完全であるために専用の記号を用意する必要はありません。これは命題論理では、特定の複合命題の論理的等価性として表現されます。例えば、古典論理では、¬ P ∨ QはP → Qと等価です。したがって、条件演算子 "→"は、すでに "¬" (否定) と "∨" (論理和) が使用されている古典論理に基づく論理システムでは不要です。

命題論理で表現可能なすべての命題を表現できる最小限の演算子の集合を、最小限の機能的に完全な集合と呼ぶ。最小限の機能的に完全な演算子の集合は、NAND演算子（↑）とNOR演算子（↓）のみによって実現される。

以下は、引数の数が 2 を超えない最小限の機能的に完全な演算子のセットです。^{[ 5 ]}

1つの要素

{↑}、{↓}。

2つの要素

${\displaystyle \{\vee ,\neg \}}$、${\displaystyle \{\wedge ,\neg \}}$、${\displaystyle \{\to ,\neg \}}$、${\displaystyle \{\gets ,\neg \}}$、${\displaystyle \{\to ,\bot \}}$、${\displaystyle \{\gets ,\bot \}}$、${\displaystyle \{\to ,\nleftrightarrow \}}$、${\displaystyle \{\gets ,\nleftrightarrow \}}$、${\displaystyle \{\to ,\nrightarrow \}}$、${\displaystyle \{\to ,\nleftarrow \}}$、${\displaystyle \{\gets ,\nrightarrow \}}$、${\displaystyle \{\gets ,\nleftarrow \}}$、${\displaystyle \{\nrightarrow ,\neg \}}$、${\displaystyle \{\nleftarrow ,\neg \}}$、${\displaystyle \{\nrightarrow ,\top \}}$、${\displaystyle \{\nleftarrow ,\top \}}$、${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$、${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$。

3つの要素

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$、${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$。

真理関数の中には、対応する論理結合子を含む定理で表現できる性質を持つものがある。二項真理関数（または対応する論理結合子）が持ちうる性質には、次のようなものがある。

• 結合法則：同じ結合子が連続して2つ以上含まれる式の中では、被演算子の順序が変わらない限り、演算の順序は関係ありません。
• 可換性：論理結合子のオペランドを入れ替えても、式の真偽値は変わりません。
• 分配性：· で表される結合子は、+ で表される別の結合子に対して分配的である。すべての被演算子a、 b、 cに対してa · ( b + c ) = ( a · b ) + ( a · c ) が成り立つ場合。
• 冪等性：演算の被演算項が同じ場合、結合子は被演算項を結果として返します。言い換えれば、この演算は真偽保存性と偽偽保存性の両方を備えています（下記参照）。
• 吸収：一対の接続詞${\displaystyle \land ,\lor }$吸収法則を満たすのは、${\displaystyle a\land (a\lor b)=a\lor (a\land b)=​​a}$すべてのオペランドa、bについて。

真理関数の集合が機能的に完全であるのは、以下の5つの性質のそれぞれについて、その性質を持たない要素が少なくとも1つ含まれている場合に限る。

• 単調: a ₁ ≤ b 1 、 a ₂ ≤ b ₂、 ...、 a _n ≤ b nを満たすすべてのa 1 _、 ...、 a _n、 b ₁、 ...、 b _n ∈ {0,1} に対してf ( a ₁、、 a n ) ≤ f _{( b} 1、_... 、_b n )が_成り立つ場合。例:${\displaystyle \vee ,\wedge ,\top ,\bot }$。
• アフィン: 各変数について、その値を変更すると、他のすべての変数の固定値に対して、演算の真偽値が常に変化するか、決して変化しないかのいずれかになります。例:${\displaystyle \neg ,\leftrightarrow }$、 ${\displaystyle \not \leftrightarrow ,\top ,\bot }$。
• 自己双対: 真理値表で演算の真理値割り当てを上から下に読むことは、それを下から上に読むことの補数を取ることと同じです。言い換えれば、f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ) です。例:${\displaystyle \neg }$。
• 真理値保持: すべての変数に真という真理値が割り当てられる解釈では、これらの操作の結果として真という真理値が生成されます。例:${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$（有効性を参照）
• 偽値保持: すべての変数に偽の真偽値を割り当てる解釈では、これらの操作の結果として偽の真偽値が生成されます。例:${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$（有効性を参照）

真理値表を用いる代わりに、論理結合記号は、意味の構成性の原理で詳述されているように、解釈関数と機能的に完全な真理関数の集合（Gamut 1991）によって解釈することができる。Iを解釈関数とし、Φ、Ψ を任意の 2 つの文とし、真理関数f _nandを次のように定義する。

• f _nand (T,T) = F; f _nand (T,F) = f _nand (F,T) = f _nand (F,F) = T

次に、便宜上、f _not、f _or f_{およびなどについては、} f _nandによって定義されます。

• f _not ( x ) = f _nand ( x , x )
• f_または( x、y ) = f _nand ( f _not ( x ) 、f _not ( y ))
• f_かつ( x , y ) = f_でなく( f _nand ( x , y ))

または、f _not、f_またはf_などといったものが直接定義されます。

• f _not (T) = F; f _not (F) = T;
• f_または(T,T) = f_または(T,F) = f_または(F,T) = T; f_または(F,F) = F
• f_かつ(T,T) = T; f_かつ(T,F) = f_かつ(F,T) = f_かつ(F,F) = F

それから

等

したがって、S が論理結合子を表す論理記号v ₁ ... v _nと非論理記号c ₁ ... c _nからなる記号列である文である場合、f _{nand (またはその他の関数的完全真理関数の集合})によってv _{1 を}v _nに解釈するI ( v ₁ ) ... I ( v _n )が提供されている場合に限り、 の真理値は⁠${\displaystyle I(s)}$は、 c ₁ ... c _nの真偽値、すなわちI ( c ₁ )... I ( c _n )によって完全に決定されます。言い換えれば、予想どおり、また要求どおり、 S は、そのすべての非論理記号の解釈の下でのみ真または偽となります。

上記で定義した関数を用いることで、命題の真理関数の形式的な定義を与えることができる。^{[ 6 ]}

PROPをすべての命題変数の集合とする。

${\displaystyle PROP=\{p_{1},p_{2},\dots \}}$

真理値割り当てを任意の関数と定義する${\displaystyle \phi :PROP\to \{T,F\}}$したがって、真理値の割り当てとは、各命題変数と特定の真理値を関連付けることである。これは実質的に、命題の真理値表の特定の行と同じである。

真理の割り当てについては、${\displaystyle \phi }$拡張真理値割り当てを定義します。${\displaystyle {\overline {\phi }}}$以下のように拡張します。${\displaystyle \phi }$新しい機能へ${\displaystyle {\overline {\phi }}}$定義域はすべての命題論理式の集合に等しい。${\displaystyle {\overline {\phi }}}$まだ${\displaystyle \{T,F\}}$。

1. もし${\displaystyle A\in PROP}$それから${\displaystyle {\overline {\phi }}(A)=\phi (A)}$。
2. AとBが任意の命題論理式である場合、
   1. ${\displaystyle {\overline {\phi }}(\neg A)=f_{\text{not}}({\overline {\phi }}(A))}$。
   2. ${\displaystyle {\overline {\phi }}(A\land B)=f_{\text{and}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$。
   3. ${\displaystyle {\overline {\phi }}(A\lor B)=f_{\text{or}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$。
   4. ${\displaystyle {\overline {\phi }}(A\to B)={\overline {\phi }}(\neg A\lor B)}$。
   5. ${\displaystyle {\overline {\phi }}(A\leftrightarrow B)={\overline {\phi }}((A\to B)\land (B\to A))}$。

最後に、拡張真理割り当てを定義したので、これを使用して命題の真理関数を定義できます。命題Aの真理関数は、${\displaystyle f_{A}}$は、すべての真理値の集合に等しいドメインを持ち、値域は${\displaystyle \{T,F\}}$。

各真理値割り当てについて定義される。${\displaystyle \phi }$、 による${\displaystyle f_{A}(\phi )={\overline {\phi }}(A)}$値${\displaystyle {\overline {\phi }}(A)}$これは、 Aの真理値表の最終列に表示されているものと同じで、次の行に表示されています。${\displaystyle \phi }$。

論理演算子は、デジタル回路では論理ゲートとして実装されます。事実上すべてのデジタル回路（主な例外はDRAM ）は、 NAND、NOR、NOT、および伝送ゲートで構成されています。通常の2入力ではなく3入力以上のNANDゲートとNORゲートはかなり一般的ですが、これらは論理的には2入力ゲートのカスケード接続と同等です。その他のすべての演算子は、上記の論理ゲートのうち2つ以上を論理的に同等な組み合わせに分解することで実装されます。

「NAND 単独」、「NOR 単独」、「NOT と AND」の「論理的等価性」は、チューリング等価性に似ています。

すべての真理関数がNORだけで表現できるという事実は、アポロ誘導コンピュータによって実証されている。

• この記事は、 PlanetMathの TruthFunction の資料を組み込んでおり、クリエイティブ・コモンズ表示-継承ライセンスの下でライセンスされています。

• Józef Maria Bocheński (1959)、数学論理学概論、フランス語版およびドイツ語版からの翻訳、Otto Bird、ドルトレヒト、南ホラント州：D. Reidel。
• アロンゾ・チャーチ（1944）『数理論理学入門』プリンストン大学出版局、プリンストン、ニュージャージー州。真理関数概念の歴史については、序論を参照のこと。