恒真式
概要
恒真式（tautology）とは、命題論理の論理式で、命題変数にどのような真理値を割り当てても真になるもののことで、$p\lor\lnot p$ や $p\to p$ のように論理の法則や正しい推論の形を表す。$\varphi$ が恒真式であることは $\lnot\varphi$ が充足不能であることと同値であり、命題変数が $n$ 個なら $2^n$ 通りの割り当てを調べる真理値表で有限の手順で判定できる。恒真式の命題変数に任意の論理式を一斉に代入したものも恒真式であり（代入定理）、共通の命題変数をもたない 2 つの論理式の選言が恒真式なら一方が恒真式である。恒真性は真理値を 2 つに限る古典的な意味論に依存し、3 値の意味論や直観主義論理では排中律が成り立たない。
「明日は雨が降るか、または降らない」は、天気がどうなっても正しい。正しさが「雨が降る」という部分の真偽によらず、「または」「でない」の組み立てだけで決まっているからである。このように、命題変数にどんな真理値を割り当てても真になる論理式を 恒真式（トートロジー）という。$p\lor\lnot p$、$p\to p$、$\lnot(p\land\lnot p)$ がその典型である。恒真式は命題論理の「法則」にあたり、数学の証明で無意識に使っている推論の形（対偶、背理法、場合分け）は、どれもある恒真式に支えられている。
恒真式かどうかは、命題変数が $n$ 個なら $2^n$ 通りの割り当てを調べれば有限の手順で判定できる。本記事では、恒真式の定義と判定の正しさ、恒真式の命題変数に論理式を一斉に代入しても恒真式であること（代入定理）、共通の命題変数をもたない 2 つの論理式の選言が恒真なら一方が恒真であることを証明し、真理値の意味論を変えると恒真でなくなる例を見る。なお、ベクトル束の トートロジカル直線束（トートロジー束）は名前が似ているが、本記事の恒真式とは関係がない。
論理式・付値の定め方は 命題論理 の記事の定義「論理式」「付値と真理値」にそろえる。命題変数は $p_0,p_1,p_2,\dots$（$p,q,r$ も使う）、結合子は $\lnot,\land,\lor,\to$、真理値は $\mathrm{T}$（真）と $\mathrm{F}$（偽）で書き、$\varphi\leftrightarrow\psi$ は $(\varphi\to\psi)\land(\psi\to\varphi)$ の略記とする。
定義
論理式 $\varphi$ が 恒真式（tautology）であるとは、すべての付値 $v$ について $v(\varphi)=\mathrm{T}$ となることをいう。これを $\vDash\varphi$ と書く。
また、$v(\varphi)=\mathrm{T}$ となる付値 $v$ があるとき $\varphi$ は 充足可能 であるといい、どの付値でも $v(\varphi)=\mathrm{F}$ となるとき $\varphi$ は 充足不能（または 恒偽式、矛盾式）であるという。
この定義は 命題論理 の記事の定義「恒真式・充足可能性・論理的帰結」の 1・2 と同じである（Gal15 Definition 3.3.4、p. 41、MBTZ25 §12.1、p. 85）。恒真式は「どの付値でも真」、充足可能は「ある付値で真」であり、恒真式は充足可能である（付値は少なくとも 1 つある）が、逆は成り立たない（ex-taut-counterexamples）。
恒真式は命題論理の論理式についての概念である。一階述語論理で「どの構造・どの割り当てでも真」となる論理式は 論理的妥当性 の記事が扱う 妥当式 であり、恒真式に一階の論理式を代入したものは妥当式になる（論理的妥当性 の記事の定理「恒真式の代入例は妥当」）が、妥当式がすべてその形をしているわけではない。
直感
恒真式は、骨組みだけで正しさが決まる命題である。「$p$ または $p$ でない」は $p$ の中身を一切見ずに正しいと分かる。その代わり、恒真式は世界について何も教えない。どの状況でも真ということは、状況を区別する力がないということでもある。数学で恒真式が役に立つのは、それが推論の形を保証するからである。$\varphi\to\psi$ が恒真式であることは「$\varphi$ から $\psi$ を結論してよい」ことと同じであり（含意 の記事の定理「意味論的な演繹定理」）、恒真式の一覧は正しい推論の形の一覧になっている。
例
次の論理式はどれも恒真式である。確かめ方は「偽になる付値があると仮定して矛盾を導く」のが速い。
- 排中律 $p\lor\lnot p$：$v(p)=\mathrm{T}$ なら左の項が、$v(p)=\mathrm{F}$ なら右の項が真である。
- 矛盾律 $\lnot(p\land\lnot p)$：$p\land\lnot p$ が真になるには $v(p)=\mathrm{T}$ と $v(p)=\mathrm{F}$ が同時に必要なので、$p\land\lnot p$ はつねに偽である。
- $p\to(q\to p)$：偽になるには $v(p)=\mathrm{T}$ かつ $q\to p$ が偽、すなわち $v(p)=\mathrm{F}$ が必要で、矛盾する。
- $(p\to(q\to r))\to((p\to q)\to(p\to r))$：偽になるには前件 $p\to(q\to r)$ が真で、後件が偽、すなわち $p\to q$ が真かつ $p\to r$ が偽でなければならない。最後の条件から $v(p)=\mathrm{T}$、$v(r)=\mathrm{F}$ であり、$p\to q$ が真なので $v(q)=\mathrm{T}$ である。すると $q\to r$ は偽で、$p\to(q\to r)$ も偽となり、前件が真であることに反する。
- $(\lnot p\to p)\to p$：偽になるには $v(p)=\mathrm{F}$ かつ $\lnot p\to p$ が真でなければならないが、$v(p)=\mathrm{F}$ なら $\lnot p\to p$ は $\mathrm{T}\to\mathrm{F}=\mathrm{F}$ である。
二重否定・対偶・De Morgan の法則の恒真式は 論理と命題 の記事の命題「基本的な恒真式」で、三段論法の形 $((p\to q)\land(q\to r))\to(p\to r)$ と Peirce の法則 $((p\to q)\to p)\to p$ は 命題論理 の記事の例「恒真式と論理的帰結」で確かめられている。
- $p$ は充足可能だが恒真式でない。$v(p)=\mathrm{F}$ で偽になる。
- $(p\to q)\to(q\to p)$ は恒真式でない。$v(p)=\mathrm{F}$、$v(q)=\mathrm{T}$ とすると前件が真、後件が偽である。$v(p)=v(q)$ の付値では真なので充足可能である。「含意が真ならその逆も真」という推論は正しくない。
- $p\land\lnot p$ は充足不能である（ex-taut-examples の 2）。その否定 $\lnot(p\land\lnot p)$ は恒真式である。
- $(p\lor q)\to p$ は恒真式でない。$v(p)=\mathrm{F}$、$v(q)=\mathrm{T}$ で偽になる。「$p$ または $q$」から $p$ は結論できない。
性質
真理値表による判定
$\varphi$ を論理式とする。
- $\varphi$ が恒真式であることと、$\lnot\varphi$ が充足不能であることは同値である。$\varphi$ が充足可能であることと、$\lnot\varphi$ が恒真式でないことも同値である。
- $\varphi$ に現れる命題変数が $q_1,\dots,q_n$ であるとき、$\varphi$ が恒真式であることと、$(a_1,\dots,a_n)\in\{\mathrm{T},\mathrm{F}\}^n$ の $2^n$ 通りそれぞれについて、$v(q_i)=a_i$（$1\le i\le n$）となる付値 $v$ を 1 つとって $v(\varphi)=\mathrm{T}$ となることは同値である。
- 恒真式どうしは論理的に同値であり、恒真式と論理的に同値な論理式は恒真式である。
1：各付値で $v(\lnot\varphi)=\mathrm{T}\iff v(\varphi)=\mathrm{F}$ である。よって「すべての $v$ で $v(\varphi)=\mathrm{T}$」と「すべての $v$ で $v(\lnot\varphi)=\mathrm{F}$」は同じことである。後半は前半の $\varphi$ を $\lnot\varphi$ に替え、$\lnot\lnot\varphi$ と $\varphi$ がどの付値でも同じ真理値をとることを使えば得られる。
2：恒真式なら、とくに各 $(a_1,\dots,a_n)$ について選んだ付値で真である。逆に、選んだ $2^n$ 個の付値で真だとし、任意の付値 $w$ をとる。$a_i:=w(q_i)$ とし、この組について選んだ付値を $v$ とすると、$v$ と $w$ は $\varphi$ に現れる命題変数で同じ値をとる。命題論理 の記事の補題「現れる変数だけで値が決まる」により $w(\varphi)=v(\varphi)=\mathrm{T}$ である。
3：$\varphi,\psi$ が恒真式なら、どの付値でも $v(\varphi)=v(\psi)=\mathrm{T}$ なので論理的に同値である。$\varphi$ が恒真式で $\psi$ が $\varphi$ と論理的に同値なら、どの付値でも $v(\psi)=v(\varphi)=\mathrm{T}$ である。$\square$
2 は 真理値表による判定 が正しく、有限の手順で終わることを述べている。命題変数のない論理式は考えていない（命題論理の記事の言語では、論理式には少なくとも 1 つの命題変数が現れる）。$n$ 個の命題変数の真理値表は $2^n$ 行あり、変数が増えると行数は急速に増える。恒真式かどうかを多項式時間で判定する方法が見つかれば P$=$NP が従うことが知られており、効率のよい判定法は知られていない（Gal15 §3.3.5、pp. 49–53）。3 により、恒真式は論理的同値の 1 つの類をなす。命題論理の記事の定理「論理式の同値類のなすBoole代数」の言葉では、恒真式の類は Boole 代数の最大元 $1$ である。
代入定理
排中律 $p\lor\lnot p$ が恒真式なら、$(q\to r)\lor\lnot(q\to r)$ も恒真式であるはずである。$p$ の真理値がどうであっても真なのだから、$p$ のところに何が入っても真である。これを正確に述べるために、代入を定める。
相異なる命題変数 $p_1,\dots,p_n$ と論理式 $\psi_1,\dots,\psi_n$ が与えられたとき、論理式 $\varphi$ の 代入 $\varphi[\psi_1/p_1,\dots,\psi_n/p_n]$（以下 $\varphi[\vec\psi/\vec p]$ と略す）を、論理式の組み立てに沿って次のように定める。
- $\varphi=p_i$ なら $\psi_i$。$\varphi$ が $p_1,\dots,p_n$ 以外の命題変数 $q$ なら $q$。
- $(\lnot\varphi)[\vec\psi/\vec p]:=\lnot(\varphi[\vec\psi/\vec p])$。
- $(\varphi\ast\chi)[\vec\psi/\vec p]:=(\varphi[\vec\psi/\vec p]\ast\chi[\vec\psi/\vec p])$（$\ast$ は $\land,\lor,\to$）。
すなわち $\varphi$ の中の $p_i$ の すべての出現を同時に $\psi_i$ に置き換えたものである。
命題論理 の記事の定理「一意読み取り」により、この定義は矛盾なく 1 つの論理式を定める。同時に置き換えるので、$\psi_1$ の中に $p_2$ が現れても、それをさらに $\psi_2$ に置き換えることはない。
付値 $v$ に対し、付値 $v'$ を、$v'(p_i):=v(\psi_i)$（$1\le i\le n$）、それ以外の命題変数 $q$ では $v'(q):=v(q)$ で定める。このとき、すべての論理式 $\varphi$ について
$$
v\bigl(\varphi[\vec\psi/\vec p]\bigr)=v'(\varphi)
$$
が成り立つ。
$\varphi$ の組み立てに沿った帰納法による。$\varphi=p_i$ なら左辺は $v(\psi_i)$、右辺は $v'(p_i)=v(\psi_i)$ である。$\varphi$ が $p_1,\dots,p_n$ 以外の命題変数 $q$ なら、両辺とも $v(q)$ である。
$\varphi=\lnot\chi$ なら、左辺は $v(\lnot(\chi[\vec\psi/\vec p]))$ で、$v(\chi[\vec\psi/\vec p])$ が $\mathrm{F}$ のときに限り $\mathrm{T}$ である。帰納法の仮定により $v(\chi[\vec\psi/\vec p])=v'(\chi)$ なので、これは $v'(\chi)=\mathrm{F}$、すなわち $v'(\lnot\chi)=\mathrm{T}$ と同値である。
$\varphi=\chi\ast\theta$ なら、$v(\varphi[\vec\psi/\vec p])$ は $v(\chi[\vec\psi/\vec p])$ と $v(\theta[\vec\psi/\vec p])$ から $\ast$ の真理値の規則で決まり、$v'(\varphi)$ は $v'(\chi)$ と $v'(\theta)$ から同じ規則で決まる。帰納法の仮定により成分の値がそれぞれ等しいので、両辺は等しい。$\square$
$\varphi$ が恒真式ならば、相異なる命題変数 $p_1,\dots,p_n$ と任意の論理式 $\psi_1,\dots,\psi_n$ について、$\varphi[\vec\psi/\vec p]$ も恒真式である。
任意の付値 $v$ をとり、lem-taut-substitution-valuation の付値 $v'$ を作る。$\varphi$ は恒真式なので $v'(\varphi)=\mathrm{T}$ であり、補題により $v(\varphi[\vec\psi/\vec p])=v'(\varphi)=\mathrm{T}$ である。$v$ は任意なので $\varphi[\vec\psi/\vec p]$ は恒真式である。$\square$
代入定理により、恒真式の一覧は「命題変数の形」で覚えておけばよい。たとえば ex-taut-examples の 4 の $p,q,r$ に任意の論理式を代入したものはすべて恒真式である。逆は成り立たない：$\varphi[\vec\psi/\vec p]$ が恒真式でも $\varphi$ が恒真式とは限らない。$\varphi=p$、$\psi=q\lor\lnot q$ とすると $\varphi[\psi/p]=q\lor\lnot q$ は恒真式だが、$p$ は恒真式でない。
代入を「同時に、すべての出現に」行うことは欠かせない。$p\lor\lnot p$ の最初の $p$ だけを $q$ に替えた $q\lor\lnot p$ は、$v(q)=\mathrm{F}$、$v(p)=\mathrm{T}$ で偽になる。
恒真式の閉じ方と選言
$\varphi,\psi$ を論理式とする。
- $\varphi$ と $\varphi\to\psi$ がともに恒真式ならば、$\psi$ も恒真式である。
- $\varphi\land\psi$ が恒真式であることと、$\varphi$ と $\psi$ がともに恒真式であることは同値である。
- $\varphi\to\psi$ が恒真式であることと、$\varphi$ を真にするすべての付値で $\psi$ も真であること（$\{\varphi\}\vDash\psi$）は同値である。
1：任意の付値 $v$ で $v(\varphi)=v(\varphi\to\psi)=\mathrm{T}$ である。$v(\psi)=\mathrm{F}$ なら $v(\varphi\to\psi)=\mathrm{F}$ となって矛盾するので、$v(\psi)=\mathrm{T}$ である。
2：各付値で $v(\varphi\land\psi)=\mathrm{T}\iff v(\varphi)=v(\psi)=\mathrm{T}$ であり、「すべての $v$ で両方が真」と「すべての $v$ で $\varphi$ が真、かつすべての $v$ で $\psi$ が真」は同じことである。
3：$\varphi\to\psi$ が偽になる付値は、$\varphi$ を真にし $\psi$ を偽にする付値と一致する。前者がないことと後者がないことは同じである。$\square$
3 は 含意 の記事の定理「意味論的な演繹定理」の $\Sigma=\emptyset$ の場合でもある。2 と対照的に、選言については「$\varphi\lor\psi$ が恒真式なら $\varphi$ か $\psi$ が恒真式」は成り立たない。$p\lor\lnot p$ は恒真式だが、$p$ も $\lnot p$ も恒真式でない。ところが、2 つの成分が命題変数を共有しなければ成り立つ。
論理式 $\varphi,\psi$ が共通の命題変数をもたないとする。$\varphi\lor\psi$ が恒真式ならば、$\varphi$ と $\psi$ の少なくとも一方は恒真式である。同じ仮定のもとで、$\varphi\to\psi$ が恒真式ならば、$\lnot\varphi$ と $\psi$ の少なくとも一方は恒真式である。
$\varphi$ も $\psi$ も恒真式でないと仮定して、$\varphi\lor\psi$ を偽にする付値を作る。$v_1(\varphi)=\mathrm{F}$ となる付値 $v_1$ と、$v_2(\psi)=\mathrm{F}$ となる付値 $v_2$ がある。付値 $v$ を、$\varphi$ に現れる命題変数 $q$ では $v(q):=v_1(q)$、それ以外の命題変数 $q$ では $v(q):=v_2(q)$ で定める。$\varphi$ と $\psi$ は共通の命題変数をもたないので、$\psi$ に現れる命題変数では $v=v_2$ である。命題論理 の記事の補題「現れる変数だけで値が決まる」により $v(\varphi)=v_1(\varphi)=\mathrm{F}$、$v(\psi)=v_2(\psi)=\mathrm{F}$ であり、$v(\varphi\lor\psi)=\mathrm{F}$ となって、$\varphi\lor\psi$ が恒真式であることに反する。
後半：$\varphi\to\psi$ と $\lnot\varphi\lor\psi$ はどの付値でも同じ真理値をとる（含意 の記事の命題「含意による言い換え」の 1）ので、$\lnot\varphi\lor\psi$ は恒真式である。$\lnot\varphi$ と $\psi$ も共通の命題変数をもたないので、前半から従う。$\square$
後半は、$\varphi\to\psi$ が恒真式で $\varphi,\psi$ が命題変数を共有しないなら、$\varphi$ が充足不能であるか $\psi$ が恒真式であるか、どちらかになるということである。記号を共有する場合に、$\varphi\to\psi$ が妥当なら、両方に共通の記号だけで書ける論理式 $\theta$ で $\varphi\to\theta$ と $\theta\to\psi$ がともに妥当になるものがとれるか、というのが補間の問題であり、一階述語論理でそのような $\theta$ がとれることを述べるのが Craigの補間定理 である（Gal15 §6.5、Theorem 6.5.1、pp. 275–279。この記事では証明しない）。
直観主義論理 には「$\varphi\lor\psi$ が証明できれば $\varphi$ か $\psi$ が証明できる」という選言特性がある（直観主義論理 の記事の定理「選言特性」）。古典論理の恒真式は、thm-taut-disjoint-disjunction の形の、変数を共有しない場合に限った弱い性質しかもたない。
恒真式と証明
恒真式は真理値で定めた概念だが、決まった規則で記号列を変形して導く「証明」の側からも捉えられる。命題論理の適切な証明体系では、証明できる論理式はちょうど恒真式である（命題論理 の記事の定理「健全性と完全性」）。健全性（証明できれば恒真）の中心は、規則が恒真性を保つことであり、prop-taut-closure の 1 と thm-taut-substitution はその典型である。
一方、規則を弱めた論理では、恒真式でも証明できないものがある。排中律 $p\lor\lnot p$、二重否定除去 $\lnot\lnot p\to p$、Peirce の法則は、直観主義論理では証明できない（古典論理 の記事の例「古典論理の恒真式」の表、直観主義論理 の記事の系「直観主義論理で証明できない式」）。
意味論を変えたときの反例
恒真式であることは、真理値が $\mathrm{T},\mathrm{F}$ の 2 つで、結合子が 命題論理 の記事の真理値の規則に従うことに依存している。また、上の定理はそれぞれの仮定を外すと成り立たない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 真理値が 2 つ（Kleene の強い 3 値にする） | すべての命題変数に値 $\tfrac12$ を割り当てる | 排中律 $p\lor\lnot p$ がつねに値 $1$（真）をとること |
| 真理値が 2 つ（3 元の Heyting 代数にする） | $\{0<\tfrac12<1\}$ で $v(p)=\tfrac12$ | $p\lor\lnot p$、$\lnot\lnot p\to p$ がつねに値 $1$ をとること |
| 代入は「すべての出現に同時に」 | $p\lor\lnot p$ の最初の $p$ だけを $q$ に替えた $q\lor\lnot p$ | 恒真性が代入で保たれること（thm-taut-substitution） |
| 2 つの成分が命題変数を共有しない | $p\lor\lnot p$ | 選言が恒真なら一方の成分が恒真であること（thm-taut-disjoint-disjunction） |
| すべての付値で真（「ある付値で真」に弱める） | $p$ | 否定が充足不能であること（prop-taut-decision の 1。$\lnot p$ は $v(p)=\mathrm{F}$ で真） |
1・2 行目の計算は 古典論理 の記事の例「反例：3 つの真理値」にある。Kleene の強い 3 値論理では $\lnot a=1-a$、$a\lor b=\max(a,b)$ と定めるので、$v(p)=\tfrac12$ のとき $p\lor\lnot p$ の値は $\max(\tfrac12,\tfrac12)=\tfrac12$ で、$1$ にならない。3 元の Heyting 代数では $\lnot\tfrac12=0$ なので $p\lor\lnot p$ の値は $\tfrac12$、$\lnot\lnot p\to p$ の値は $1\Rightarrow\tfrac12=\tfrac12$ である。どちらも、真理値を 2 つに限ったときに初めて恒真になる式の例である。
補足：恒真式と数学の推論
数学の証明でよく使う推論の形は、恒真式として書ける。場合分けは $((p\to r)\land(q\to r))\to((p\lor q)\to r)$、背理法は $(\lnot p\to(q\land\lnot q))\to p$、対偶による証明は $(\lnot q\to\lnot p)\to(p\to q)$ である。どれも「偽になる付値があると仮定して矛盾を導く」方法ですぐ確かめられる。たとえば場合分けの式が偽になるには、$v(r)=\mathrm{F}$ で、$p\lor q$ が真、$p\to r$ と $q\to r$ が真でなければならないが、$v(r)=\mathrm{F}$ のもとで後の 2 つが真なら $v(p)=v(q)=\mathrm{F}$ となり、$p\lor q$ が真であることに反する。代入定理により、$p,q,r$ に数学の具体的な主張をどう当てはめても、これらの推論は正しい。推論の形の正しさを個々の主張から切り離せることが、恒真式という概念の意義である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
