多値論理の弱関数的完全性
大森仁 (Hitoshi Omori) · 佐野勝彦 (Katsuhiko Sano)
日本学術振興会 特別研究員 PD(神戸大学) · 北陸先端科学技術大学院大学
Frege によって構築された古典論理は、その意味論において二つの真理値をもつ。
これに対して、哲学的・数学的動機に基づいて三つ以上の真理値をもつ多値論理がL! ukasiewicz と Post とによって独立に提案された。本発表の主題となる関数的完全性は、Post によって導入された概念である。まず、関数的完全性の二つの基本的な結果を振り返る (cf. [1]) 。n ≥ 2 なる自然数に対し、En = {1, 2, . . . , n} とおき、代数 (En , F)を Un とおく。ただし、F は En 上の有限引数の演算からなる集合とする。
定理 1 (Post, [3]) m ≥ 2 に対し、Un が高々m-引数に関して関数的完全ならば、高々m + 1-引数に関しても関数的完全である。
定理 2 (S!lupecki, [5]) Un が関数的完全であるのは、Un のすべての一項演算が定義でき、さらに全射な二項演算の少なくとも一つが定義できるときそのときに限る。
これらの結果に対し、本発表では関数的完全性を弱めた（あるいは一般化した）概念を考える。このとき対象とする代数は、特に n = 4 の場合を考え、さらに E = P({0, 1})とする。以下では、∅, {0}, {1}, {0, 1} をそれぞれ n, f , t, b と書く。関数的完全性を一般化する理由の一つは、Belnap-Dunn の 4 値論理の意味論において特徴的な条項の扱いを反映させることにある。具体的には、4 つの真理値 n, f , t, b をそのまま扱うのではなく、4 つの真理値の構成要素である 0, 1 の振る舞いを、1 の振る舞いに関する正条項と 0 の振る舞いに関する負条項とに分けて考えるのである。これが Belnap-Dunn の4 値論理の意味論を条項から見たときの特徴であり、値をいわば「分解」して、その意味を明らかにしているのである。この条項による値の「分解」を関数的完全性の概念にも適用する、というのが本発表の動機である。
本発表で具体的に扱うのは、以下の真理値表から定まる次の代数である。
x∧ytbnfttbnfbbbffnnfnffffffx∨ytbnftttttbtbtbnttnnftbnfxtbnf∼xfbnt◦xtfft%xttff

このとき、代数 (E, {∧, ∨, ∼}) を BD-代数と呼ぶ。さらに、BD-代数の ◦, ' による拡張を、BD◦-代数、BD'-代数と呼ぶ (cf. [2, 4])。以下では演算からなる集合 F は{∧, ∨, ∼} ⊆ F を満たすとし、代数 (E, F) を単に F と書くことにする。
ところで、上で真理値表によって与えた演算は、それらの正条項・負条項を書くことができる。例えば ∧, ∼, ' は以下のようになる。
1∈x∧y
1 ∈∼ x1 ∈ 'x⇐⇒⇐⇒⇐⇒

1 ∈ x かつ 1 ∈ y,0 ∈ x,
1 ∈ x,0∈x∧y0 ∈∼ x0 ∈ 'x

1⇐⇒⇐⇒⇐⇒0 ∈ x または 0 ∈ y;
1 ∈ x;
1∈/ x.

これらは、比較的容易に正条項・負条項を書き下せるが、一般に真理値表によって与えられた演算の場合はどうだろうか。このとき、演算の意味を明らかにするためには、その演算の正条項・負条項を求めることは有効かつ重要であるが、機械的にそれを求めることができるかは明らかでない。以下の弱関数的完全性の特徴づけの「副産物」として，機械手続きを構成できる．
まず正条項・負条項に着目して弱定義可能性を以下のように定める。f を任意の k
項演算 (k ：有限) とし、g, h を F の元の合成とする。
def.

g が F で f を正定義する ⇐⇒ ∀!x ∈ E k (1 ∈ f (!x) ⇐⇒ 1 ∈ g(!x)).
def.

h が F で f を負定義する ⇐⇒ ∀!x ∈ E k (0 ∈ f (!x) ⇐⇒ 1 ∈ h(!x)).
このもとで、対 (g, h) が F で f を弱定義するのは、g, h が F で f をそれぞれ正定義、負定義する場合とする。すると、g が F で f を定義することは、対 (g, ∼ g) が F でf を弱定義することとして捉えられる。そして、F が弱関数的完全であるのは、どんな k 項演算 (k ：有限) も F で弱定義可能である場合とする。
以上の定義を踏まえると、Post と S!lupecki の結果に対応する以下の結果が得られる。
定理 3 m ≥ 2 に対し F が高々m-引数に関して弱関数的完全であるならば、高々m+1引数に関しても弱関数的完全である。
定理 4 i ∈ P({0, 1}) に対し δi (x) = t (x = i の場合 ); f ( それ以外 ), とせよ。F が弱関数的完全であるのは、δt , δb , δn , δf が F で正定義できるときそのときに限る。
この定理 4 の証明法から、E 上の任意の k-項演算が 4 値の真理値表によって与えられたとき、その演算の正条項・負条項を求める機械的手続きを構成できる．さらに、定理 4 の系として、BD'-代数が弱関数的完全であり、BD-代数・BD◦-代数は弱関数的完全でないことが示される。したがって、BD'-代数が関数的完全でないことと合わせると、BD'-代数は弱関数的完全と関数的完全性が異なることを示している。
参考文献[1] G. Malinowski. Many-valued logics. In L. Goble, editor, The Blackwell Guide to PhilosophicalLogic, pages 309–335. Blackwell Publishing, 2001.
[2] H. Omori and T. Waragai. Some observations on the systems LFI1 and LFI1∗ . In Proceedings of Twenty-Second International Workshop on Database and Expert Systems Applications(DEXA2011), pages 320–324, 2011.
[3] E. Post. Introduction to a general theory of elementary propositions. American Journal ofMathematics, 43(3):163–185, 1921.
[4] K. Sano and H. Omori. An expansion of first-order Belnap-Dunn logic. In Petr Cintula, ShierJun, and Martin Vita, editors, Volume of Abstracts of Non-classical Modal and Predicate Logics,
pages 111–119, 2011.
[5] J. S!lupecki. A criterion of fullness of many-valued systems of propositional logic. Studia Logica,
30:153–157, 1972. English translation of “Kryterium penoci wielowartociowych systemw logikizda”, Comptes Rendus des Sances de la Socit des Sciences et des Lettres de Varsovie, Cl. III, 3,
102-109, 1939.

2