離散数学

同義語：discrete mathematics離散構造discrete structure

概要

前提知識: 集合, 写像, グラフ, 数学的帰納法

整数、有限集合、グラフの頂点と辺、文字の列、真と偽のように、一つひとつが切り離された対象と、その上の関係や操作を調べる数学を 離散数学 という。微分積分学は実数の連続性（どんなに近い 2 点の間にも別の点がある）を土台にするが、離散数学の対象は、隣の元がはっきり決まるばらばらの元からできている。離散数学の問いはおおよそ 4 種類に分かれる。条件を満たす対象はいくつあるか（数え上げ）、そのような対象は存在するか（存在）、最大・最小のものは何か（極値と最適化）、それを効率よく見つける手順はあるか（アルゴリズム）。
この記事では、離散構造の定義と分野の見取り図を示し、離散数学でよく使う 3 つの証明の型を、それぞれ定理を通して示す。有限性を使った帰納法による構成（thm-discm-linear-extension）、個数の比較による存在証明（thm-discm-short-formula）、極値の考え方と確率による存在証明（thm-discm-max-cut）である。後の 2 つには完全な証明をつける。

定義

離散構造と離散数学

集合 $X$ と、$X$ 上の有限個の関係 $R_1,\dots,R_r$（$R_i\subset X^{k_i}$）および有限個の写像 $F_1,\dots,F_s$（$F_j\colon X^{l_j}\to X$）の組
$$ \mathcal{X}=(X;R_1,\dots,R_r;F_1,\dots,F_s) $$
を構造という。台集合 $X$ が有限集合または可算集合であるとき、$\mathcal{X}$ を 離散構造（discrete structure）という。離散構造について、条件を満たすものの個数、存在、最大・最小、それを求める手順を調べる数学の分野を 離散数学（discrete mathematics）という。

代表的な離散構造を挙げる。

有限集合：関係も写像もない構造。部分集合・写像・分割の個数を数える。
グラフ $G=(V,E)$：頂点集合 $V$ 上の隣接関係（対称で非反射的な 2 項関係。どの頂点も自分自身とは隣接しない）を 1 つもつ構造（グラフの定義「グラフの定義」）。
半順序集合 $(P,\le)$：反射的・反対称的・推移的な 2 項関係を 1 つもつ構造（半順序集合）。
整数 $(\mathbb{Z};\le;+,\times)$：大小関係と 2 つの演算をもつ可算の構造。
文字列：有限集合 $\Sigma$（アルファベット）の元の有限列全体 $\Sigma^*$ は可算集合であり、連結（列をつなぐ操作）を写像としてもつ（形式言語）。
論理関数：写像 $f\colon\{\mathrm{T},\mathrm{F}\}^n\to\{\mathrm{T},\mathrm{F}\}$。真理値の組から真理値への対応であり、論理式の働きを表す（命題論理）。

「離散」の意味と離散位相

「離散」（discrete）はもともと「個々に切り離された」という意味の語である（Lev §0.1, p. 1）。位相空間では、すべての部分集合が開集合である位相を離散位相という（離散空間）。$\mathbb{R}$ の部分空間としての $\mathbb{Z}$ は離散空間である。各 $n\in\mathbb{Z}$ について $\{n\}=(n-\tfrac12,n+\tfrac12)\cap\mathbb{Z}$ が開集合だからである。一方、可算であっても離散空間になるとは限らない（ex-discm-rationals）。def-discm-structure は台集合の大きさで離散構造を定めており、位相の言葉は使わない。どこまでを離散数学に含めるかは文献によって幅があり、母関数のように解析学の道具を使う分野や、確率を使う分野も離散数学に含めることが多い（Lev §0.1–0.2, pp. 1–11 は集合・写像・数列・関係・グラフを主な離散構造として挙げている）。

直感

離散数学と連続の数学は、同じ問いを異なる道具で扱う。

観点	連続の数学	離散数学
基本の対象	実数、区間、連続関数	整数、有限集合、グラフ、文字列
変化の量	微分 $f'(x)$	差分 $f(n+1)-f(n)$（数列の和と差分）
足し合わせ	積分	有限和
存在の道具	中間値の定理、コンパクト性	鳩の巣原理、数え上げ、帰納法
最適化の道具	微分して $0$ とおく	有限個の比較、交換の議論、増加道

有限の対象については、原理的にはすべての場合を調べ尽くせば答えが出る。しかし場合の数はすぐに膨大になる。$n$ 個の変数の論理関数は $2^{2^n}$ 個あり、$n=6$ でも $2^{64}>10^{19}$ 個になる。$n$ 個の元の並べ方は $n!$ 通りある。離散数学の定理の多くは、調べ尽くさずに済ませるための構造を与える。

分野の見取り図

分野	主な対象	記事の例
数え上げ組合せ論	有限集合の個数、二項係数、母関数	数え上げ組合せ論、包除原理、母関数
グラフ理論	グラフ、有向グラフ	グラフ、平面グラフ、四色定理、Ramseyの定理
位相的グラフ理論	曲面に描いたグラフ	位相的グラフ理論
順序と束	半順序集合、Boole 代数	半順序集合、Dilworthの定理、Boole代数
離散確率と確率論的方法	有限確率空間、期待値	期待値の線形性と数え上げ
組合せ最適化	有限個の候補からの最適解	組合せ最適化、全域木、マッチング(グラフ理論)、マトロイド
論理と計算	論理式、オートマトン、計算機のモデル	命題論理、有限オートマトン、Turing機械
符号と暗号	有限体上のベクトル、合同式	誤り訂正符号、RSA暗号
初等整数論	整数、約数、合同	Euclidの互除法、鳩の巣原理

基本原理

次の原理は離散数学のどの分野でも使われる。証明はそれぞれの記事にある。

原理	主張	所在
和の法則・積の法則	互いに交わらない有限集合の和集合の元の個数は個数の和、直積の元の個数は個数の積	数え上げ組合せ論の命題「和の法則と積の法則」
鳩の巣原理	有限集合 $A,B$ が $\lvert A\rvert>\lvert B\rvert$ なら、写像 $A\to B$ は単射でない	鳩の巣原理の定理「鳩の巣原理の基本形」
二重数え上げ	有限集合の間の関係の元の個数を、行ごとと列ごとの 2 通りに数えると等しい	期待値の線形性と数え上げの命題「二重数え上げ」
握手補題	グラフの頂点の次数の総和は辺の本数の 2 倍	次数(グラフ) の定理「次数の総和と辺数」
包除原理	和集合の元の個数を共通部分の個数の交代和で表す	数え上げ組合せ論の定理「包除の等式」
数学的帰納法	自然数についての主張を $0$ と「$n$ から $n+1$」に分けて示す	数学的帰納法

以下の 3 つの節では、これらの原理を組み合わせて証明する定理を 1 つずつ示す。

帰納法による構成：半順序の線形拡大

課題の間に「$x$ は $y$ より先に済ませる」という制約がいくつかあるとき、すべての課題を一列に並べて、制約に従う順番を作れるだろうか。制約が半順序をなすなら、有限個の課題についてはいつでも作れる。

線形拡大

$(P,\le)$ を半順序集合とする。$P$ 上の全順序 $\preceq$ で、
$$ x\le y\implies x\preceq y\qquad(x,y\in P) $$
を満たすものを $(P,\le)$ の 線形拡大（linear extension）という（全順序の定理「順序拡大定理」。線形拡張ともいう）。$P=\{x_1,\dots,x_n\}$ が有限集合のとき、線形拡大は「$x_i< x_j$ なら $x_i$ が $x_j$ より前にある」ような $P$ の元の並べ方と同じものである（KT17 §6.4, p. 125）。

元 $m\in P$ が 極小元 であるとは、$x\le m$ となる $x\in P$ が $m$ 自身に限ることをいう。

有限半順序集合の極小元

空でない有限半順序集合 $(P,\le)$ は極小元をもつ。

極小元がないと仮定する。$x_1\in P$ をとる。$x_1$ は極小元でないので、$x_2< x_1$（$x_2\le x_1$ かつ $x_2\ne x_1$）となる $x_2\in P$ がある。同様にして $x_1>x_2>x_3>\cdots$ となる列が作れる。$i< j$ なら $x_j\neq x_i$ であることを示す。$j=i+1$ のときは作り方から明らかである。$j\ge i+2$ のときは、$x_j\le x_{j-1}\le\cdots\le x_{i+1}$ と推移律により $x_j\le x_{i+1}$ である。もし $x_j=x_i$ なら $x_i\le x_{i+1}$ と $x_{i+1}\le x_i$ がともに成り立ち、反対称律から $x_{i+1}=x_i$ となって $x_{i+1}\neq x_i$ に反する。よって $x_1,\dots,x_{\lvert P\rvert+1}$ は相異なる $\lvert P\rvert+1$ 個の元であり、$P$ の元の個数を超える。これは鳩の巣原理（写像 $i\mapsto x_i$ が単射になりえないこと）に反する。$\square$

有限半順序集合の線形拡大の存在

有限半順序集合はいつも線形拡大をもつ。すなわち、$\lvert P\rvert=n$ の有限半順序集合 $(P,\le)$ の元を $x_1,x_2,\dots,x_n$ と並べて、$x_i< x_j$ ならば $i< j$ となるようにできる。

証明の所在と帰納法の形

これは全順序の定理「順序拡大定理」（任意の半順序集合は線形拡大をもつ）の有限の場合である。そこでの証明は Zorn の補題を使うが、有限の場合は選択公理を使わずに、元の個数についての帰納法で構成できる（全順序の注意「順序拡大定理について」）。帰納法の形はこうである。lem-discm-minimal により極小元 $m$ を 1 つとり、残りの $P\setminus\{m\}$ を帰納法の仮定で並べ、その先頭に $m$ を置く。$m$ より前に置くべき元がないことが、$m$ の極小性そのものである。この構成の完全な証明は位相的整列の命題「位相的整列と線形拡大」と定理「源点を取り除く手順の性質」にある。

この構成は、そのまま手順になっている。極小元を 1 つ取り出して先頭に置き、残りで同じことを繰り返す。計算機科学ではこの手順を位相的ソート（topological sort）とよび、得られる並びを位相的整列という（KT17 §6.4, p. 125）。

12 の約数の線形拡大

$P=\{1,2,3,4,6,12\}$ に「$a\le b\iff a$ が $b$ を割り切る」で半順序を入れる。どの線形拡大でも $1$ が最初、$12$ が最後である（$1$ はすべての元を割り切り、$12$ はすべての元で割り切られる）。残りの $2,3,4,6$ については、$2$ は $4$ と $6$ より前、$3$ は $6$ より前という制約だけが残る。先頭が $2$ なら残り $3,4,6$ の並べ方は $3$ が $6$ より前の 3 通り、先頭が $3$ なら次は $2$ で、その後 $4,6$ の 2 通りである。$4$ と $6$ は先頭になれない。よって線形拡大はちょうど $5$ 個ある。たとえば $1,2,3,4,6,12$ と $1,3,2,6,4,12$ である。

$n$ 元の反鎖（どの 2 元も比較できない半順序集合）の線形拡大は $n!$ 個、$n$ 元の鎖（全順序集合）の線形拡大はそれ自身の 1 個である。線形拡大の個数は、半順序の制約がどれだけ強いかを測る量になっている。台集合が無限のときは、極小元がないこともあり（ex-discm-integers）、上の帰納法は使えない（KT17 §6.4, p. 126 も無限の場合には別の考察が要ると注意している）。それでも線形拡大はいつも存在する。これが全順序の定理「順序拡大定理」で、証明には Zorn の補題を使う。

数え上げによる存在証明：短い論理式で表せない論理関数

命題論理の定理「選言標準形による関数的完全性」により、$n$ 個の変数の論理関数 $f\colon\{\mathrm{T},\mathrm{F}\}^n\to\{\mathrm{T},\mathrm{F}\}$ はどれも、命題変数 $p_1,\dots,p_n$ と結合子からなる論理式で表せる。ここでは、表すのに必要な論理式の長さを考える。論理式は記号の有限列なので（命題論理の定義「論理式」）、その長さを記号の個数とする。$p_1,\dots,p_n$ だけを命題変数に使う論理式は、
$$ \Sigma_n:=\{p_1,\dots,p_n,\ \lnot,\ \land,\ \lor,\ \to,\ (,\ )\} $$
の $n+6$ 個の記号の列である。論理式 $\varphi$ が表す論理関数を $f_\varphi$ と書く（$f_\varphi(a)$ は、$p_i$ に $a$ の第 $i$ 成分を割り当てたときの $\varphi$ の真理値）。
論理関数は全部で $2^{2^n}$ 個ある。$\{\mathrm{T},\mathrm{F}\}^n$ は積の法則により $2^n$ 個の元をもち、その各元に $\mathrm{T},\mathrm{F}$ の 2 通りの値を割り当てる写像の個数は、再び積の法則により $2^{2^n}$ だからである。一方、短い論理式は少ししかない。この個数の差から、次の定理が出る。

短い論理式で表せない論理関数の存在

$n\ge1$、$L\ge1$ を整数とし、$(n+6)^{L+1}\le2^{2^n}$ とする。このとき、$n$ 変数の論理関数 $f$ で、長さが $L$ 以下のどの論理式 $\varphi$ についても $f_\varphi\neq f$ となるものが存在する。

$a:=n+6\ge7$ とおく。$\Sigma_n$ の記号からなる長さ $k$ の列は $a^k$ 個あるので、長さ $1$ 以上 $L$ 以下の列の個数は
$$ \sum_{k=1}^{L}a^k=\frac{a^{L+1}-a}{a-1}< a^{L+1} $$
である（$a\ge2$ なので $a-1\ge1$）。長さ $L$ 以下の論理式はこれらの列の一部なので、その全体を $\Phi_L$ とすると $\lvert\Phi_L\rvert< a^{L+1}\le2^{2^n}$ である。写像 $\Phi_L\to\{\text{論理関数}\}$、$\varphi\mapsto f_\varphi$ の像の元の個数は $\lvert\Phi_L\rvert$ 以下で、論理関数全体の個数 $2^{2^n}$ より小さい。よってこの写像は全射でなく、像に入らない論理関数 $f$ がある。$\square$

必要な長さの下界

$n\ge1$ について、$n$ 変数の論理関数 $f$ で、$f$ を表すどの論理式も長さが
$$ \left\lfloor\frac{2^n}{\log_2(n+6)}\right\rfloor $$
以上であるものが存在する。

$N:=\lfloor 2^n/\log_2(n+6)\rfloor$ とおく。$N\le1$ なら、どの論理式も長さ $1$ 以上なので主張は明らかである。$N\ge2$ とし、$L:=N-1\ge1$ とおく。$L+1=N\le2^n/\log_2(n+6)$ なので
$$ (n+6)^{L+1}=2^{(L+1)\log_2(n+6)}\le2^{2^n} $$
であり、thm-discm-short-formula により長さ $L$ 以下の論理式では表せない $f$ がある。$f$ を表す論理式（選言標準形の定理により存在する）の長さは $L+1=N$ 以上である。$\square$

10 変数の場合

$n=10$ では $n+6=16=2^4$ なので $2^{10}/\log_2 16=1024/4=256$ であり、cor-discm-short-formula により、10 変数の論理関数で、表すのに長さ $256$ 以上の論理式が必要なものがある。実際 $16^{256}=2^{1024}=2^{2^{10}}$ であり、thm-discm-short-formula の仮定が $L=255$ で等号で成り立つ。

上界と比べておく。選言標準形は、$f$ が $\mathrm{T}$ を返す各 $a\in\{\mathrm{T},\mathrm{F}\}^n$ について、$p_i$ または $(\lnot p_i)$ を $n$ 個 $\land$ で結んだ式を作り、それらを $\lor$ で結んだものである。$(\lnot p_i)$ は 4 記号で、2 つの式を $(\ \land\ )$ で結ぶたびに 3 記号増えるので、各連言は $4n+3(n-1)$ 記号以下である。$\mathrm{T}$ を返す点は $2^n$ 個以下なので、選言標準形の長さは
$$ 2^n\bigl(4n+3(n-1)\bigr)+3(2^n-1)< 7n\cdot2^n $$
で抑えられる（$f$ がいつも $\mathrm{F}$ なら長さ $8$ の $(p_1\land(\lnot p_1))$ を使う。$8<7n\cdot2^n$ である）。こうして、最も表しにくい論理関数に必要な長さは、$2^n/\log_2(n+6)$ と $7n\cdot2^n$ の間にある。
同じ数え上げから、「ほとんどすべて」の論理関数が長い論理式を必要とすることもわかる。長さ $L$ 以下の論理式で表せる論理関数の割合は $(n+6)^{L+1}/2^{2^n}$ 未満であり、$L+1=2^{n-1}/\log_2(n+6)$ 以下なら、この割合は $2^{2^{n-1}}/2^{2^n}=2^{-2^{n-1}}$ 未満である。この論法は、どの関数が表しにくいかを具体的には教えない。存在だけを保証する証明である点は、鳩の巣原理と同じである。

極値の考え方と確率：辺の半分以上を横切る分割

有限単純グラフ $G=(V,E)$ の頂点集合を 2 つに分ける分割 $V=A\sqcup B$ について、一方の端点が $A$、他方の端点が $B$ にある辺の本数を $e(A,B)$ と書く。$e(A,B)$ の辺だけを残すと二部グラフになるので、$e(A,B)$ が大きい分割を見つけることは、辺の多い二部部分グラフを見つけることと同じである。次の定理は、どんなグラフでも辺の半分は残せることを示す。2 通りの証明を与える。

辺の半分以上を横切る分割

辺の本数が $m$ の有限単純グラフ $G=(V,E)$ には、$e(A,B)\ge m/2$ となる分割 $V=A\sqcup B$ がある。

極値の考え方を使う

$V$ の分割は $2^{\lvert V\rvert}$ 個しかないので、$e(A,B)$ を最大にする分割 $(A,B)$ がとれる。頂点 $v\in A$ について、$v$ の隣接頂点のうち $A$ にあるものの個数を $d_A(v)$、$B$ にあるものの個数を $d_B(v)$ とする。もし $d_A(v)>d_B(v)$ なら、$v$ を $B$ へ移した分割 $(A\setminus\{v\},B\cup\{v\})$ では、$v$ に接続する辺のうち横切るものが $d_B(v)$ 本から $d_A(v)$ 本に変わり、ほかの辺は変わらないので、横切る辺が増える。これは最大性に反するので $d_B(v)\ge d_A(v)$、すなわち $d_B(v)\ge\deg v/2$ である。$v\in B$ についても同様に、$v$ から $A$ への辺は $\deg v/2$ 本以上ある。
横切る辺を、端点ごとに数えて足すと、各辺は両端で 1 回ずつ、合わせて 2 回数えられる。よって握手補題（次数(グラフ) の定理「次数の総和と辺数」）により
$$ 2\,e(A,B)=\sum_{v\in A}d_B(v)+\sum_{v\in B}d_A(v)\ge\sum_{v\in V}\frac{\deg v}{2}=m $$
である。$\square$

確率を使う

各頂点を、独立に確率 $\tfrac12$ ずつで $A$ または $B$ に入れる。これは $2^{\lvert V\rvert}$ 個の分割それぞれに確率 $2^{-\lvert V\rvert}$ を与える有限確率空間である。辺 $e=\{u,v\}$ について、$e$ が横切るという事象の確率は、$(u,v)$ の入り方 4 通りのうち $(A,B)$ と $(B,A)$ の 2 通りなので $\tfrac12$ である。$X_e$ をこの事象の指示関数とすると $e(A,B)=\sum_{e\in E}X_e$ なので、期待値の線形性（期待値の線形性と数え上げの定理「期待値の線形性」）により
$$ \mathbb{E}[e(A,B)]=\sum_{e\in E}\mathbb{E}[X_e]=\frac m2 $$
である。確率変数がいつも平均より小さいことはないので、$e(A,B)\ge m/2$ となる分割が少なくとも 1 つある。$\square$

1 つ目の証明は手順にもなる。適当な分割から始めて、「動かすと横切る辺が増える頂点」がある限りそれを動かす。動かすたびに $e(A,B)$ は 1 以上増え、$m$ を超えないので、高々 $m$ 回で止まる。止まった分割では、証明と同じ理由で $e(A,B)\ge m/2$ である。止まった分割が最大とは限らないが、最大値の半分以上は保証される。これは、組合せ最適化でいう近似の考え方の最も簡単な例である。

定数 1/2 は改良できない

完全グラフ $K_{2k}$ では $m=k(2k-1)$ である。分割 $(A,B)$ で横切る辺はちょうど $\lvert A\rvert\lvert B\rvert$ 本で、$\lvert A\rvert+\lvert B\rvert=2k$ のもとで積は $\lvert A\rvert=\lvert B\rvert=k$ のとき最大の $k^2$ になる。よって横切る辺の割合の最大値は
$$ \frac{k^2}{k(2k-1)}=\frac{k}{2k-1} $$
であり、$k\to\infty$ で $\tfrac12$ に近づく。どんな $c>\tfrac12$ についても「どのグラフにも $e(A,B)\ge cm$ となる分割がある」は成り立たない。三角形 $K_3$ でも、最大値は $2$ で $m=3$ の $\tfrac23$ である。

反例：条件を外すと崩れること

外す条件	反例	成り立たなくなること
台集合の有限性	$(\mathbb{Z},\le)$	極小元の存在（lem-discm-minimal）
推移律	3 元 $a,b,c$ 上の反射的・反対称的な関係で、$a\le b$、$b\le c$、$c\le a$ を含むもの	この関係を含む全順序の存在（thm-discm-linear-extension）
有限性	写像 $\mathbb{N}\to\mathbb{N}$、$n\mapsto n+1$	有限集合では「自分自身への単射は全射」
「可算なら離散」という推論	$\mathbb{R}$ の部分空間 $\mathbb{Q}$	部分空間が離散空間であること
結合子の選び方	$\land,\lor,\to$ だけの論理式	どの論理関数も表せること

反例：整数全体の半順序

$(\mathbb{Z},\le)$ は半順序集合（全順序集合）で、どの $n$ についても $n-1< n$ なので極小元がない。lem-discm-minimal の結論は、台集合が無限だと成り立たない。破れているのは「有限である」という仮定で、証明の中で鳩の巣原理を使った所が成り立たない。ただし $(\mathbb{Z},\le)$ 自身は全順序なので線形拡大をもつ（自分自身）。崩れるのは補題であり、線形拡大の存在そのものではない。

反例：循環する制約

3 元集合 $\{a,b,c\}$ 上の関係
$$ R=\{(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)\} $$
を考え、$(x,y)\in R$ を $x\le y$ と書く。これは「$a$ は $b$ より前、$b$ は $c$ より前、$c$ は $a$ より前」という循環する制約である。$R$ は反射的で、相異なる 2 元 $x,y$ について $x\le y$ と $y\le x$ が同時に成り立つことはないので反対称的である。しかし $a\le b$、$b\le c$ なのに $a\le c$ でないので、推移律だけを破る。
$R$ を含む全順序 $\preceq$ はない。あったとすると、推移律により $a\preceq b\preceq c$ から $a\preceq c$、一方 $c\le a$ から $c\preceq a$ となり、反対称律により $a=c$ となって矛盾する。言い換えると、$a,b,c$ をどう並べても 3 つの制約を同時には満たせない。なお $R$ の推移閉包をとると $a\le c$ と $c\le a$ がともに入り、今度は反対称律が破れる。thm-discm-linear-extension の仮定「半順序」のうち推移律は外せない。

反例：有限性を外した鳩の巣原理

有限集合 $A$ からそれ自身への単射は全射である（鳩の巣原理の命題「同じ個数の有限集合の間の写像」）。$\mathbb{N}$ では $n\mapsto n+1$ が単射だが、$0$ が像に入らないので全射でない。満たす性質は「単射」、満たさない性質は「全射」で、破れる含意は「自分自身への単射 $\Rightarrow$ 全射」である（鳩の巣原理の例「反例：無限集合では「真部分集合への単射」がありうる」）。

反例：可算だが離散空間でない

$\mathbb{Q}$ は可算集合だが、$\mathbb{R}$ の部分空間として離散空間でない。$\{0\}$ が開集合なら、ある $\varepsilon>0$ で $(-\varepsilon,\varepsilon)\cap\mathbb{Q}=\{0\}$ となるはずだが、$1/k< \varepsilon$ となる正の整数 $k$ について $1/k$ もこの集合に入る。満たす性質は「可算」、満たさない性質は「離散空間」である。def-discm-structure が台集合の大きさだけで離散構造を定め、位相を使わないのはこのためでもある。$\mathbb{Q}$ を大小関係と演算をもつ構造とみれば離散構造であるが、$\mathbb{Q}$ の稠密性を使う議論（どの 2 数の間にも別の数がある）は、連続の数学に近い。

結合子の選び方の反例は命題論理の例「反例：否定のない結合子だけでは足りない」にある。$\land,\lor,\to$ だけの論理式は、すべての変数を真にする付値でいつも真になるので、$\lnot p_1$ を表せない。

補足：離散と連続の往来

離散数学の問題を解くために連続の道具を使うことは多い。数列を冪級数の係数とみる母関数は解析学を使い、確率による証明（prf-discm-max-cut-probabilistic）は確率論の言葉を使う。逆に、連続の対象を離散の対象で調べることもある。曲面に描いたグラフの頂点・辺・面を数えると曲面の Euler 標数がわかる（位相的グラフ理論）。有限個の候補から最良のものを選ぶ問題は、線形計画のような連続の最適化と結びつく（組合せ最適化）。