FANDOM


シェーファー関数 (Sheffer function) とは、一つで十全であるような真理関数のことを指す。そのような1変数真理関数は存在せず、2変数真理関数は否定論理積および否定論理和だけである。そのことは、Charles Sanders Peirce が1880年頃に発見したが論文として公表されず、Henry M. Sheffer が1913年に独自に再発見したとされる[1]

証明

2変数真理関数

2変数真理関数の場合、真理表は$ 2^2 = 4 $行となる。この4行に対して、如何なる条件であれば十全になるかを検証すればよい。

十全の項目を見ればわかるように、十全になる条件として、$ \lnot $が真理関数として表現できなければならない。$ \lnot $$ \{T, T\} $のとき、Fを返し、$ \{F, F\} $のときは、Tを返さなければならない。本来、$ \lnot $は1変数関数だが、同じ論理式か、原子式を入れることで、$ \lnot $と同じことを表現できる。

ここで、$ \lnot $ではない場合の真理表を、導入して検証してみよう。例として、$ \{T, T\} $のさいにF、$ \{F, F\} $のさいにFが返ってくる関数fを考える。そして、原子式Aを考える。このとき、AがTである場合の$ f(A, A) $はFである。この結果を$ A' $と表現し、$ f(A', A') $にすると、これもまたFになる。言い換えれば、$ \{T, T\} $のとき、Fを返し、$ \{F, F\} $のときはTを返さなければ、ある論理式の真理値であるFをTに変換し、また同様にある論理式の真理値であるTをFに変換することができないため、表現できない論理式が発生する。

従って、まず下の条件が決定する。

  • $ \{T, T\} $のとき、Fを返す
  • $ \{F, F\} $のとき、Tを返す

さて、この組み合わせの他に、

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

が考えられうる。このとき、$ \alpha = \{T, F\} $, $ \beta = \{F, T\} $という組み合わせと定義したとき、可能性は4つの組み合わせが考えられうる。

そこで、$ \alpha $の真理値がT, $ \beta $の真理値がFと考える。このときの真理値は、AがTであるか、そうではないかということになる。そうすると、この組み合わせはAか、Bか、または$ \lnot A $$ \lnot B $しか表現できない。すると、これはAでありB、あるいはAまたはBのような場合が表現できない。つまり、真理値を組み合わせることができないので、全ての真理値を表現することができない。これは逆にしても成り立つ。

とすると、$ \alpha $の真理値がF、 $ \beta $の真理値がFと考えた場合、上記に加え、「AとBの両方がTのとき」が作れるようになる。これは否定論理積を参照すれば、十全になることがわかる。同様に、両方がTであったとしても、十全になる。

従って、否定論理積および否定論理和だけが2変数真理関数の中で十全である。

出典

  1. Scharle, T.W. (1965), "Axiomatization of propositional calculus with Sheffer functors", Notre Dame J. Formal Logic 6 (3): 209–217, doi:10.1305/ndjfl/1093958259.