離散数学とは何ですか。

なめらかに変化する量ではなく、とびとびの数えられる対象を研究する数学の分野です。主な分野は論理、集合、数え上げ、グラフ、整数論、証明です。微分積分はものごとが連続的にどう変化するかを問い、離散数学はいくつあるか、どれか、ある命題が真かどうかを問います。

離散数学は難しいですか。

微分積分とは違う意味で難しい科目です。当てはめる公式は少なく、組み立てる議論が多く、多くの学生にとって証明を書くことを中心にした初めての授業になります。計算はふつう軽めです。難しいと感じる学生の多くは証明に慣れようとしているところで、小さな例で練習すればすぐに上達します。

離散数学は何に使われますか。

情報科学のほとんどすべてです。論理は回路や if 文の仕組みであり、集合はデータベースの問い合わせの土台であり、数え上げはアルゴリズムにかかる時間を教え、グラフはネットワークや地図を表し、整数論はオンライン決済を守る暗号の基礎です。

離散数学ではどんな分野を学びますか。

典型的な最初の授業では、命題論理と真理値表、集合とベン図、関数と関係、数学的帰納法を含む証明の技法、順列と組合せによる数え上げ、基礎的な確率、グラフと木、合同算術を扱います。漸化式やブール代数を加える授業もあります。

情報科学に離散数学は必要ですか。

はい。ほとんどすべての情報科学の学位課程で必修で、ふつうは1年目か2年目に学びます。アルゴリズム、データ構造、計算理論はどれもこれを前提にしているからです。プログラミングだけなら、なしで始められますが、論理、集合、数え上げは多くの人が思うより早く日々のコードに出てきます。

離散数学と連続数学の違いは何ですか。

離散数学は、整数、真と偽、ネットワークの節点のように、1つずつ並べられる値を扱います。微分積分のような連続数学は、時間、距離、温度のように、ある範囲のどんな値もとりうる量を扱います。

真理値表とは何ですか。

論理的な命題の入力について、真と偽のすべての組み合わせと、それぞれに対する命題の値を並べた表です。入力が p と q の2つなら4行になります。真理値表は2つの命題が同値であることを証明する方法です。すべての行で列が一致すれば、2つはつねに一致します。

離散数学

離散数学は、とびとびの数えられるものの数学です。真か偽か、集合に入るか入らないか、この道かあの道か。コンピュータが動いている数学であり、その入り口はオンとオフを切り替えられる論理です。

著者: Nethanel Bar, 共同創業者兼CEO

最終更新 2026年9月23日

離散数学は、とびとびの数えられるものの数学です。命題は真か偽か、要素は集合に入るか入らないか、ネットワークは2点の間につながりがあるかないか。その中間はなく、それが「離散」という言葉の意味であり、コンピュータが世界を見る見方そのものです。

最初の授業では6つの分野を扱います。論理、集合、数え上げ、グラフ、整数論、証明です。ほかのすべての分野が論理で書かれるので、論理が最初に来ます。下で論理演算子を選び、p と q を切り替えてみてください。

論理演算子

否定

p ∧ q の真理値表

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

p と q を切り替えるか、行をクリックしてください。強調された行が、いま選んでいる値の行です。

p を「x は A に入っている」、q を「x は B に入っている」と読みます。色のついた領域が命題の真になる場所で、点がいまの行です。

AND

p ∧ q

読み方 p かつ q

この値では、p ∧ q は真です。

p と q の両方が真のときだけ真。

集合で見ると AND は共通部分です。x が A ∩ B に入るのは、x が A に入り、かつ x が B に入るときとちょうど同じです。

論理: 命題と論理演算子

命題とは、「7 は素数である」や「雨が降っている」のように、真か偽のどちらかである文です。論理はいくつかの論理演算子で小さな命題から大きな命題を組み立て、真理値表は入力のすべての組み合わせについて結果がどうなるかを並べます。

記号	名前	読み方	真になるとき
∧	AND、論理積	「p かつ q」	両方が真
∨	OR、論理和	「p または q」	少なくとも一方が真
¬	NOT、否定	「p でない」	p が偽
⊕	XOR、排他的論理和	「p または q、ただし両方ではない」	ちょうど一方が真
→	IMPLIES、条件文(含意)	「p ならば q」	p が真で q が偽の場合を除くすべて
↔	IFF、同値	「p のとき、かつそのときに限り q」	p と q が同じ値

このうち2つは人を驚かせます。論理の OR は包含的です。日常の「紅茶かコーヒーか」と違い、「p または q」は両方が真のときも真です。排他的なほうには XOR という別の名前があります。

もう1つは IMPLIES です。p → q が偽になるのは、p が真で q が偽の1行だけです。約束だと考えてください。「雨が降ったら傘を持っていく」。この約束が破られるのは、雨が降って傘がないときだけです。晴れた日には、何を持っていても約束は破られていないので、この命題は真とみなされます。

同値な命題

2つの命題は、真理値表がすべての行で一致するとき同値です。ウィジェットで OR を選んで p を否定してください。¬p ∨ q の列は p → q の列と同じなので、2つは同じことを言っています。

いちばん役に立つ同値はド・モルガンの法則で、NOT が AND と OR をどう通り抜けるかを示します。

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

言葉にすると、「両方ではない」は「どちらか一方が偽」と同じで、「どちらでもない」は「両方とも偽」と同じです。プログラマーは「(ログイン済みかつ認証済み) でない」のような条件を書き換えるのに、これを毎日使っています。

論理と集合は1つの考え

p を「x は A に入っている」、q を「x は B に入っている」と読みます。すると AND は共通部分、OR は和集合、NOT は補集合になり、どの真理値表も色分けされたベン図になります。ウィジェットが表の隣にベン図を描くのはそのためです。ド・モルガンの法則は集合についての規則になります。

(A ∩ B)′ = A′ ∪ B′

集合の記号のページでは、クリックできる図でこれらをそれぞれ色分けします。

数え上げ

離散数学で数えるとは、書き並べずに数えることです。2つの規則がほとんどの仕事をします。

積の法則。 1つ目の選択が m 通り、2つ目の選択が n 通りあるなら、その組は m × n 通りです。4桁の暗証番号は各桁に 10 通りあるので、ありうる暗証番号は 10^4 = 10000 通りです。

組合せ。 n 個から順序を考えずに k 個を選ぶ方法の数を C(n, k) と書きます。8種類のトッピングから3つを選ぶなら:

C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56

分子は順序つきの選び方を数え、3 × 2 × 1 で割ることで、同じ3つのトッピングを選ぶ6通りの順序を取り除きます。

答えは 6 × 5 を 2 で割った 15 です。30 になったなら、各組をそれぞれの順序で1回ずつ、二度数えています。

グラフ

グラフとは、頂点と呼ばれる点の集まりを、辺と呼ばれる線で結んだものです。町を結ぶ道路、ソーシャルネットワークの友人関係、ウェブページ間のリンクなど、つながりでできたものなら何でも表せます。

最初の結果です。5人が互いに1回ずつ握手すると、握手は C(5, 2) = 10 回です。各人は4回握手するので手の数は 5 × 4 = 20 で、どの握手にも手が2つあるので 20 / 2 = 10 です。この議論が握手補題で、すべての頂点の次数の合計は辺の数の2倍になります。

整数論と証明

合同算術は時計の上の算術です。17 mod 5 は 2 で、17 を 5 で割った余りです。8時の9時間後は5時です。17 mod 12 が 5 だからです。同じ考えをとても大きな数で使うのが、安全なウェブサイトを支える RSA 暗号の仕組みです。

数学的帰納法は、ある命題がすべての自然数 n について成り立つことを2段階で示します。n = 1 で確かめ、ある n で成り立てば n + 1 でも成り立つことを示します。たとえば、次の式を試した値だけでなくすべての n について証明するのに使います。

1 + 2 + ... + n = n(n + 1) / 2

離散数学は何に使われるか

プログラミング: どの if 文も論理であり、ド・モルガンの法則で条件を書き換えます。
データベース: 表を結合したり絞り込んだりする問い合わせは集合演算です。
アルゴリズム: 数え上げは、入力が大きくなるにつれてプログラムが何ステップかかるかを教えます。
ネットワークと地図: 最短経路やソーシャルネットワークはグラフの問題です。
セキュリティ: 暗号は整数論と合同算術の上に成り立っています。
ハードウェア: プロセッサは論理ゲートでできていて、論理ゲートはシリコンでできた真理値表です。

離散数学は難しいか

代数や微分積分とは違う意味で難しい科目です。覚える公式は少なく、計算も小さいのですが、多くの問題が何かを計算するのではなく証明することを求め、説得力のある議論を書くのはほとんどの学生にとって新しい技能です。

いちばん助けになるのは、パターンを探す前に小さな場合を手で調べることです。ベン図を描き、真理値表を書き出し、すべての場合を並べます。記号は最初は重く見えますが、そのほとんどはこのページと集合の記号のページにある記号です。

よくある質問

離散数学とは何ですか。: なめらかに変化する量ではなく、とびとびの数えられる対象を研究する数学の分野です。主な分野は論理、集合、数え上げ、グラフ、整数論、証明です。微分積分はものごとが連続的にどう変化するかを問い、離散数学はいくつあるか、どれか、ある命題が真かどうかを問います。
離散数学は難しいですか。: 微分積分とは違う意味で難しい科目です。当てはめる公式は少なく、組み立てる議論が多く、多くの学生にとって証明を書くことを中心にした初めての授業になります。計算はふつう軽めです。難しいと感じる学生の多くは証明に慣れようとしているところで、小さな例で練習すればすぐに上達します。
離散数学は何に使われますか。: 情報科学のほとんどすべてです。論理は回路や if 文の仕組みであり、集合はデータベースの問い合わせの土台であり、数え上げはアルゴリズムにかかる時間を教え、グラフはネットワークや地図を表し、整数論はオンライン決済を守る暗号の基礎です。
離散数学ではどんな分野を学びますか。: 典型的な最初の授業では、命題論理と真理値表、集合とベン図、関数と関係、数学的帰納法を含む証明の技法、順列と組合せによる数え上げ、基礎的な確率、グラフと木、合同算術を扱います。漸化式やブール代数を加える授業もあります。
情報科学に離散数学は必要ですか。: はい。ほとんどすべての情報科学の学位課程で必修で、ふつうは1年目か2年目に学びます。アルゴリズム、データ構造、計算理論はどれもこれを前提にしているからです。プログラミングだけなら、なしで始められますが、論理、集合、数え上げは多くの人が思うより早く日々のコードに出てきます。
離散数学と連続数学の違いは何ですか。: 離散数学は、整数、真と偽、ネットワークの節点のように、1つずつ並べられる値を扱います。微分積分のような連続数学は、時間、距離、温度のように、ある範囲のどんな値もとりうる量を扱います。
真理値表とは何ですか。: 論理的な命題の入力について、真と偽のすべての組み合わせと、それぞれに対する命題の値を並べた表です。入力が p と q の2つなら4行になります。真理値表は2つの命題が同値であることを証明する方法です。すべての行で列が一致すれば、2つはつねに一致します。