数学 Wiki
Advertisement

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

証明

2変数真理関数

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

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

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

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

  • のとき、Fを返す
  • のとき、Tを返す

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

が考えられうる。このとき、, という組み合わせと定義したとき、可能性は4つの組み合わせが考えられうる。

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

とすると、の真理値がF、 の真理値が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.
Advertisement