同義反復（論理学）

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

哲学者ルートヴィヒ・ヴィトゲンシュタインは、1921年に命題論理の冗長性に対してこの用語を初めて適用した。これは修辞学におけるトートロジー（同義反復）の概念を借用したものである。論理学において、論理式は少なくとも一つの解釈の下で真である場合に充足可能であるとされ、したがってトートロジーとは、その否定が充足不可能な論理式のことである。言い換えれば、偽にはなり得ない。

否定と肯定のどちらによっても満たされない命題は、正式には矛盾と呼ばれます。同義反復でも矛盾でもない論理式は、論理的に偶然的であると言われます。このような論理式は、命題変数に割り当てられる値に基づいて、真にも偽にもなり得ます。

二重回転式改札機の表記${\displaystyle \vDash S}$Sが同義反復であることを示すために使用されます。同義反復は「V pq」で、矛盾は「O pq」で象徴されることがあります。${\displaystyle \top }$は、双対記号を持つ任意の同義反復を表すために使われることがある。${\displaystyle \bot }$（偽）恣意的な矛盾を表す。あらゆる記号体系において、例えば「1」で表されるように、真理値「真」の代わりにトートロジーを代用することができる。 ^{[ 1 ]}

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

トートロジーの定義は、量化子を含む可能性のある述語論理の文にも拡張できます。これは命題論理の文には見られない特徴です。実際、命題論理では、トートロジーと論理的に妥当な式との間に区別はありません。述語論理の文脈では、多くの著者は、命題論理のトートロジーを取り、各命題変数を一律に一階述語論理式（命題変数ごとに一階述語論理式）に置き換えることによって得られる文をトートロジーと定義しています。このような式の集合は、述語論理の論理的に妥当な文の集合（つまり、すべてのモデルで真となる文）の真部分集合です。

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

1800年、イマヌエル・カントは著書『論理学』の中で次のように記した。

分析判断における概念の同一性は、明示的（明示的）な場合と非明示的（暗黙的）な場合がある。前者の場合、分析命題はトートロジーとなる。

ここでいう分析命題とは、分析的真理、すなわち、含まれる用語のみによって真となる自然言語による記述を指す。

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のいずれかを割り当てる必要があります。しかし、この割り当てがどのように行われたとしても、全体の式は真になります。なぜなら、最初の選言が${\displaystyle (A\land B)}$特定の評価では満たされない場合、AまたはBに F が割り当てられなければならず、これにより次の選言のいずれかに T が割り当てられます。自然言語では、A と B の両方が真であるか、少なくともどちらか一方が偽であるかのどちらかです。

命題論理の式は、命題変数にどのような評価方法を用いても、その式自体が常に真である場合、トートロジーと呼ばれる。トートロジーは無限に存在する。

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

• ${\displaystyle (A\or \lnot A)}$（「AまたはAでない」）、排中律。この式には命題変数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の少なくとも一方が真であり、それぞれが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」が表示されているため、問題の文は同義反復であることが確認された。

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

式Rが式Sをトートロジー的に含意するとは、 Rを真にするすべての評価がSも真にする場合をいう。この状況は次のように表される。${\displaystyle R\models S}$これは次の式と同等です。${\displaystyle R\to S}$これは同義反復である（クリーネ 1967、p.27  ）。

例えば、${\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を​${\displaystyle C\lor D}$そしてS _Bを${\displaystyle C\to E}$。

置換規則から、次の文が導かれる。

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

これも同義反復である。

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

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

上述の真理値表を用いた方法は、証明可能な正しさを持つ。恒真式の真理値表は、 Tのみを含む列で終わるのに対し、恒真式ではない文の真理値表は、最終列がFである行を含み、その行に対応する評価値は、テスト対象の文を満たさない評価値となる。この恒真式検証方法は、有効な手続きである。つまり、計算資源が無制限であれば、常にこの方法を用いて、文が恒真式であるかどうかを機械的に判定できる。これは特に、固定された有限または可算アルファベット上の恒真式の集合が、決定可能な集合であることを意味する。

しかしながら、真理値表は効率的な手法であるものの、検証すべき評価値の数が式中の変数の数 k^に比例して増加するという制約がある。計算長が指数関数的に増加するため、現代のコンピュータハードウェアでは実行可能な時間内にアルゴリズムを実行できず、数千もの命題変数を含む式に対して真理値表法は役に立たない。

論理式を真にする評価が存在するかどうかを判定する問題は、ブール充足可能性問題である。トートロジーをチェックする問題は、この問題と同等である。なぜなら、文Sがトートロジーであることを検証することは、それを満たす評価が存在しないことを検証することと同等だからである。${\displaystyle \lnot S}$ブール充足可能性問題はNP完全問題であり、したがってトートロジーはco-NP完全問題である。一般的に、（すべてのNP完全問題と同様に）充足可能性問題を解く多項式時間アルゴリズムは存在しないと考えられているが、一部のアルゴリズムは特定のクラスの論理式に対しては優れた性能を発揮し、多くのインスタンスで迅速に終了する。^{[ 8 ]}

トートロジーの基本的な定義は命題論理の文脈にある。しかし、その定義は一階述語論理の文にも拡張できる。^{[ 9 ]}これらの文は、命題論理の文とは異なり、量化子を含むことができる。一階述語論理の文脈では、論理的妥当性（すべてのモデルで真となる文）とトートロジー（またはトートロジー的妥当性）（一階述語論理的妥当性の真部分集合）との区別が維持されている。命題論理の文脈では、これら2つの用語は一致する。

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

${\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 \neg \neg A\to A}$

• Bocheński, JM (1959) Précis of Mathematical Logic、フランス語版とドイツ語版からの翻訳、Otto Bird、ドルトレヒト、南ホラント：D. Reidel。
• エンダートン、HB（2002）『論理学への数学的入門』ハーコート／アカデミック・プレス、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年]