トートロジー（論理）

数理論理学において、トートロジー（古代ギリシャ語：ταυτολογίαに由来）とは、構成要素の解釈に関わらず真となる式であり、論理定数のみが固定された意味を持つ。たとえば、「ボールは緑色か、またはボールは緑色ではない」という式は、ボールが何であるか、またその色に関わらず、常に真である。トートロジーは、常にではないが、通常は命題論理の有効な式を指すために使用される。

哲学者ルートヴィヒ・ヴィトゲンシュタインは、1921年に修辞学から借用して、この用語を命題論理の冗長性に初めて適用しました。修辞学では、トートロジーは反復的な文です。論理学では、式が満たされるのは、少なくとも1つの解釈の下で真である場合です。したがって、トートロジーは否定が満たされない式です。言い換えると、偽になることはできません。

否定と肯定の両方において満たされないステートメントは、正式には矛盾として知られています。トートロジーでも矛盾でもない式は、論理的に偶然であると言われます。そのような式は、命題変数に割り当てられた値に基づいて、真または偽にすることができます。

二重ターンスタイル記法は、 Sがトートロジーであることを示すために使用されます。トートロジーは「V pq」で、矛盾は「O pq」で表されます。ティー記号は、任意のトートロジーを表すために使用されることがあり、二重記号( falsum ) は任意の矛盾を表します。任意の記号では、トートロジーは、たとえば「1」で表されたように、真理値「 true 」の代わりに使用できます。 ^[1]${\displaystyle \vDash S}$${\displaystyle \top}$${\displaystyle \bot}$

トートロジーは命題論理における重要な概念であり、トートロジーは命題変数の可能なブール値の下で真である命題式として定義されます。^[2]命題論理におけるトートロジーの重要な特性は、与えられた式が常に満たされるかどうか（つまり、その否定が満たされないかどうか）をテストするための効果的な方法が存在することです。

トートロジーの定義は、述語論理の文にまで拡張することができ、述語論理の文には量指定子が含まれることがあります。これは命題論理の文には見られない特徴です。実際、命題論理では、トートロジーと論理的に有効な式の間に区別はありません。述語論理の文脈では、多くの著者がトートロジーを、命題論理のトートロジーを取り、各命題変数を一階述語式 (命題変数ごとに 1 つの式) に均一に置き換えることによって得られる文であると定義しています。このような式の集合は、述語論理の論理的に有効な文の集合の適切な部分集合です (つまり、すべてのモデルで真となる文)。

トートロジーという言葉は、古代ギリシャ人が、同じことを二度言うだけで真実であると主張される陳述を説明するために使用したもので、その軽蔑的な意味は今でも修辞的なトートロジーに使用されています。1800年から1940年の間に、この言葉は論理学において新しい意味を獲得し、現在では数学論理学において、元々持っていた軽蔑的な意味合いを除いて、ある種の命題式を表すために使用されています。

1800年、イマヌエル・カントは著書『論理学』の中でこう書いています。

分析的判断における概念の同一性は、明示的（explicita）または非明示的（implicita ）のいずれかである。前者の場合、分析命題はトートロジーである。

ここで、分析命題とは、分析真理、つまり、関係する用語のみに基づいて真となる自然言語のステートメント を指します。

1884 年、ゴットロープ・フレーゲは著書『理論哲学の基礎』の中で、論理を使って導き出せる真理はまさに分析的真理であると提唱しました。しかし、彼は分析的真理 (つまり、用語の意味のみに基づいた真理) とトートロジー (つまり、内容のない文) を区別していました。

ルートヴィヒ・ヴィトゲンシュタインは1921年の『論理哲学論考』で、論理的演繹によって演繹できる命題は分析的真理であると同時にトートロジー（意味をなさない）であると提唱した。アンリ・ポアンカレも1905年の『科学と仮説』で同様の発言をしている。バートランド・ラッセルは当初、ウィトゲンシュタインとポアンカレのこれらの発言に反論し、数学的真理は非トートロジーであるだけでなく総合的であると主張したが、後に1918年にそれらを支持する発言をした。

論理命題であるものはすべて、何らかの意味でトートロジーのようなものでなければなりません。それは、どのように定義したらよいかわかりませんが、論理命題には属するが他の命題には属さない、ある特異な性質を持つものでなければなりません。

ここで、論理命題とは、論理の法則を使用して証明可能な命題を指します。

20世紀初頭の多くの論理学者は、命題論理の式であろうと述語論理の式であろうと、普遍的に有効な式に対して「トートロジー」という用語を使用していました。この広い意味では、トートロジーはすべての解釈で真である式、または矛盾の否定と論理的に同等である式です。タルスキとゲーデルはこの用法に従い、ルイスとラングフォードの教科書などにこの用語が登場します。^[3]この用語の広い用法は現在ではあまり一般的ではありませんが、一部の教科書では引き続き使用されています。^{[4] [5]}

現代の教科書では、「トートロジー」の使用を、命題論理の有効な文、または置換によって命題トートロジーに還元できる述語論理の有効な文に限定することが一般的です。^{[6] [7]}

命題論理は、具体的な命題を表す原子単位である命題変数から始まります。式は、論理接続子で接続された命題変数で構成され、各変数の真偽から式全体の真偽を推測できるように構築されます。評価は、各命題変数を T (真) または F (偽) に割り当てる関数です。したがって、命題変数AとB 、それぞれ選言と連言を表す二項接続子と、否定を表す一項接続子を使用すると、次の式が得られます。 ${\displaystyle \lor}$${\displaystyle \land}$${\displaystyle \lnot}$${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$

ここでの評価では、AとBのそれぞれにT または F を割り当てる必要があります。ただし、この割り当てがどのように行われたかに関係なく、全体の式は真になります。最初の論理和が特定の評価によって満たされない場合、AまたはBに F を割り当てる必要があり、次の論理和のいずれかに T が割り当てられることになります。自然言語では、A と B の両方が真であるか、少なくともどちらかが偽であるかのどちらかです。 ${\displaystyle (A\land B)}$

命題論理の式は、命題変数にどの値を使用するかに関係なく、式自体が常に真である場合にトートロジーになります。トートロジーは無限に存在します。

以下の例の多くでは、A は「オブジェクトXは綴じられている」という文を表し、 B は「オブジェクトXは本である」、 C は「オブジェクトXは棚の上にある」を表します。特定の参照オブジェクトXがない場合、 命題「綴じられているものはすべて本である」に対応します。 ${\displaystyle A\to B}$

• ${\displaystyle (A\or \lnot A)}$(「A か、それともAでないか」)、排中律。この式には命題変数Aが 1 つだけあります。この式の評価では、定義により、真理値trueまたはfalseの1つを Aに割り当て、もう 1 つの真理値をAに割り当てる必要があります。たとえば、「猫は黒か、猫は黒ではない」などです。${\displaystyle \lnot}$
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$（「もしA がB を意味するなら、BでないことはAでないことを意味する」、そしてその逆も同様）、これは対偶の法則を表現しています。例えば、「それが製本されていれば、それは本であり、それが本でなければ、それは製本されていない」、そしてその逆も同様です。
• ${\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}$（「AでないことがBとその否定であるBでないことを意味する場合、Aでないことは偽で、A は真でなければならない」）これは、背理法として知られる原理です。たとえば、「綴じられていなければ、それが本であることがわかります。綴じられていなければ、それが本ではないこともわかるので、綴じられています」。
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$（「AとB の両方でない場合は、AまたはB のいずれでもない」、そしてその逆も成り立つ）、これはド・モルガンの法則として知られています。「それが本ではなく、かつ製本されていない場合、それが本ではないか、製本されていないことが確実である」、そしてその逆も成り立ちます。
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}$（「A がB を意味し、B がC を意味する場合、A はC を意味する」）、これは仮説的三段論法として知られる原理です。「それが製本されているなら、それは本であり、それが本であるなら、それはその棚にあります。したがって、それが製本されているなら、それはその棚にあります」。
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$(「 AまたはBの少なくとも 1 つが真であり、それぞれがC を意味する場合、C も真である必要があります」)、これは事例による証明として知られる原理です。「製本された物と本はその棚にあります。それが本であるか青い場合は、その棚にあります。」

最小トートロジーとは、より短いトートロジーの例ではないトートロジーです。

• ${\displaystyle (A\lor B)\to (A\lor B)}$はトートロジーですが、 のインスタンス化であるため、最小限のトートロジーではありません。${\displaystyle C\to C}$

式がトートロジーであるかどうかを判断する問題は、命題論理の基本的な問題です。式にn個の変数がある場合、式には 2 ⁿ通りの異なる値があります。したがって、式がトートロジーであるかどうかを判断する作業は有限かつ機械的な作業です。つまり、式の真理値を、その可能な値ごとに評価するだけでよいのです。すべての値で式が真となることを検証するアルゴリズム的方法の 1 つは、すべての可能な値を含む真理値表を作成することです。^[2]

例えば、次の式を考えてみましょう

${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).}$

命題変数A、B、Cには 8 つの可能な値があり、次の表の最初の 3 つの列で表されます。残りの列は、上記の式の部分式の真理値を示し、最後に各値のもとでの元の式の真理値を示す列が表示されます。

最後の列の各行にT が表示されるため、問題の文はトートロジーであることが検証されます。

命題論理の演繹システム（つまり証明システム）を、一階述語論理に用いられる演繹システムのより単純な変形として定義することもできる（そのようなシステムの 1 つについては、Kleene 1967、Sec 1.9 を参照）。適切な演繹システムによるトートロジーの証明は、完全な真理値表よりもはるかに短くなる可能性がある（n個の命題変数を持つ式には 2 ⁿ行の真理値表が必要であるが、 n が増加するとすぐに実行不可能になる）。証明システムは、排中律が仮定されていないため真理値表の方法を使用できない 直観主義命題論理の研究にも必要である。

式R が真となるすべての値付けが式Sも真となる場合、式 R は式Sをトートロジー的に意味するといいます。この状況は と表記されます。これは式がトートロジーであることと同等です(Kleene 1967 p. 27)。 ${\displaystyle R\models S}$${\displaystyle R\to S}$

たとえば、 を とします。このときはトートロジーではありません。なぜなら、 を偽にする評価はすべて偽になるからです。しかし、 を真にする評価はすべて真になります。なぜなら、はトートロジーだからです。を式とします。このとき です。なぜなら、 を満たす評価はすべて真になるからです。したがって は真になります。 ${\displaystyle S}$${\displaystyle A\land (B\lor \lnot B)}$${\displaystyle S}$${\displaystyle A}$${\displaystyle S}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B\lor \lnot B}$${\displaystyle R}$${\displaystyle A\land C}$${\displaystyle R\models S}$${\displaystyle R}$${\displaystyle A}$${\displaystyle S}$

定義から、もし式が矛盾であるならば、が真となる真理値付けは存在せず、したがって同義的含意の定義は自明に満たされるので、あらゆる式はトートロジー的に含意されるということになります。同様に、 がトートロジーであるならば、 はあらゆる式によってトートロジー的に含意されます。 ${\displaystyle R}$${\displaystyle R}$${\displaystyle R}$${\displaystyle S}$${\displaystyle S}$

一般的な手順、つまり置換規則があり、これを使用すると、与えられたトートロジーから追加のトートロジーを構築できます (Kleene 1967 sec. 3)。S がトートロジーであり、S 内の各命題変数 A に対して固定文 S A が選択されているとします。すると、 S内の各_変数Aを対応する文S _Aに置き換えて得られる文もトートロジーになります。

たとえば、S をトートロジーとします。

${\displaystyle (A\land B)\lor \lnot A\lor \lnot B}$。

S _Aを、S _{B を}とします。 ${\displaystyle C\lor D}$${\displaystyle C\to E}$

置換規則から次の文が成り立ちます。

${\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}$

これもトートロジーです。

すべてのトートロジーが定理（公理から導出可能）である場合、公理体系は完全です。すべての定理がトートロジーである場合、 公理体系は健全です。

多数の命題変数を含む文がトートロジーであるかどうかを判断するための実用的なアルゴリズムを構築する問題は、自動定理証明の分野における現代の研究分野です。

上で示した真理値表の方法は、証明可能に正しい。つまり、トートロジーの真理値表はTのみの列で終わり、トートロジーでない文の真理値表には最終列がFである行が含まれ、その行に対応する値は、テストされている文を満たさない値である。トートロジーを検証するこの方法は効果的な手順であり、無制限の計算リソースがあれば、文がトートロジーであるかどうかを機械的に判断するために常に使用できることを意味する。これは特に、固定された有限または可算なアルファベット上のトートロジーの集合が決定可能な集合であることを意味する。

しかし、効率的な手順として、真理値表は、チェックする必要がある評価の数が 2 ^kずつ増加するという制約を受けます。ここで、kは式内の変数の数です。この計算時間の指数関数的な増加により、真理値表方式は数千の命題変数を含む式では役に立たなくなります。これは、現代のコンピューティング ハードウェアでは、実現可能な時間内にアルゴリズムを実行できないためです。

式を真にする値が存在するかどうかを決定する問題は、ブール充足可能性問題である。トートロジーをチェックする問題はこの問題と同等である。なぜなら、文Sがトートロジーであることを検証することは、 を満たす値がないことを検証することと同等だからである。ブール充足可能性問題はNP 完全であり、したがって、トートロジーは共 NP 完全である。広く信じられているように、(すべての NP 完全問題に対して同等に)多項式時間アルゴリズムでは充足可能性問題を解決できないが、いくつかのアルゴリズムは特別なクラスの式に対してうまく機能したり、多くのインスタンスですぐに終了したりする。^[8]${\displaystyle \lnot S}$

トートロジーの基本的な定義は、命題論理の文脈におけるものである。しかし、その定義は一階述語論理の文にまで拡張することができる。^[9]これらの文は、命題論理の文とは異なり、量指定子を含むことができる。一階述語論理の文脈では、論理的妥当性（あらゆるモデルで真となる文）とトートロジー（またはトートロジー妥当性）（一階論理的妥当性の適切なサブセット）が区別されている。命題論理の文脈では、これら2つの用語は同じ意味である。

一階述語論理におけるトートロジーとは、命題論理のトートロジーの各命題変数を一階述語論理式（命題変数ごとに 1 つの式）に均一に置き換えることによって得られる文です。たとえば、は命題論理のトートロジーなので、は一階述語論理のトートロジーです。同様に、単項関係記号R、S、Tを持つ一階述語言語では、次の文はトートロジーです。 ${\displaystyle A\lor \lnot A}$${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$

${\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx)).}$

これは、命題トートロジー内でを、を、を に置き換えることによって得られます。 ${\displaystyle A}$${\displaystyle \exists xRx}$${\displaystyle B}$${\displaystyle \lnot \exists xSx}$${\displaystyle C}$${\displaystyle \forall xTx}$${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}$

すべての論理的妥当性が一階述語論理におけるトートロジーであるわけではありません。たとえば、次の文:

${\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx}$

はどの一階解釈でも真であるが、命題論理のトートロジーではない命題文に対応する。 ${\displaystyle A\to B}$

与えられた式がトートロジーであるかどうかは、使用されている論理の形式体系によって異なります。たとえば、次の式は古典論理のトートロジーですが、直観論理のトートロジーではありません。

${\displaystyle \neg \neg A\to A}$

• 代数正規形
• 連言標準形
• 選言正規形
• ロジックの最適化

• Bocheński, JM (1959) Précis of Mathematical Logic、フランス語版とドイツ語版からの翻訳、Otto Bird、ドルドレヒト、南ホラント州: D. Reidel。
• エンダートン、HB (2002)論理への数学入門、Harcourt / Academic Press、ISBN 0-12-238452-0。 
• Kleene, SC (1967) Mathematical Logic、2002年に再版、Dover Publications、ISBN 0-486-42533-9。 
• ライヘンバッハ、H. (1947)。『記号論理学の要素』、1980年再版、ドーバー、ISBN 0-486-24004-5 
• ウィトゲンシュタイン、L. (1921)。 「Logisch-philosophiche Abhandlung」、Annalen der Naturphilosophie (Leipzig)、v. 14、pp. 185–262、 Tractatuslogico-philosophicusとして英語訳で再版、ニューヨーク市およびロンドン、1922 年。

• 「トートロジー」、数学百科事典、EMS Press、2001 [1994]