真理関数

真理関数とは、真理値である$\{T,F\}^{n}$から$\{T,F\}$の真理値を返す関数のことを指す。またはブール関数 (boolean function) とも呼ぶ。そして、この取りうる変数の数によって、n変数真理関数とも呼ばれる。

例

選言$\lor$を考えてみよう。$\lor$は、$A\lor B$と書くことができる。Aを$x_{1}$, Bを$x_{2}$と見なし、関数fを定義すると、次のような真理表を書くことができる。

A	B	$f(x_{1},x_{2})$
真	真	真
真	偽	真
偽	真	真
偽	偽	偽

n変数関数における真理関数の組み合わせ数

真理関数fを定義したとき、それが取りうる変数をnとする場合、$f(x_{1},x_{2},x_{3},..,x_{n})$と表現できる。

このとき、それぞれが取りうる値は$\{T,F\}$の2種類なので、変数の組み合わせは$2^{n}$ある。この行数をmとした場合、その組み合わせに対し、それぞれ$\{T,F\}$のどちらかを取るわけだから、$2^{m}=2^{2^{n}}$の真理値の組み合わせが考えうることがわかる。

例えば、ここで2変数真理関数の場合を考えよう。2変数真理関数の場合、まず変数自体の組み合わせ数は

• $\{T,T\}$
• $\{T,F\}$
• $\{F,T\}$
• $\{F,F\}$

の$2^{2}=4$行である。この4行に対し、それぞれ$\{T,F\}$の組み合わせが考えうるのだから、$2^{4}=2^{2^{2}}=16$、種類の可能性を取りうることになる。言い換えれば、16種類の組み合わせを網羅することができれば、2変数真理関数で取りうる真理値の組み合わせ全てを網羅することが可能である。

従って、n変数真理関数における、変数とそれが取りうる真理値の組み合わせは$2^{2^{n}}$乗あることになる。

まがいものの関数

真理関数というからには、関数としてとらえることができる。なので、例えば次のような真理関数を考えることも可能だ。

$f:(x_{1},x_{2},x_{3})\mapsto x_{1}\land x_{2}$

しかし、この場合、$x_{3}$は使われていない。この3変数は原則的であるとは言いがたい。また、変数の数が一緒であったとしても、それを別の何らかの引数に入れ替えたとしても、結果が変わらない場合もまた、その変数が原則的であるとは言い難い。式に直すと下のような形である。

$f(x_{1},..,x_{i},..,x_{n})=f(x_{1},..,x'_{i},..,x_{n})$