Part I. 論理
桂田 祐史

katurada ＠ meiji.ac.jp (＠は ASCII の@), 910 号室2013 年 4 月 16 日, 2024 年 9 月 30 日
多分授業では、数理リテラシーそのもののイントロを含めて、4 回くらいで済ませる。

(本当は、論理を軽くやってから、集合を説明し、それから論理に戻ってきてしっかり説明
し直す、というのが適切な気がしている。つまり教科書 (中島 [1]) のやり方が良い。この講義
では、時間の節約のために、論理を最初にまとめて説明する。最初に記号化をしてしまう (やや強引)。)
注意: 数学を記述する際の論理の記号について、あまり統一されていない。論理のテキストで説明されている記号とも異なる、いわゆる独自表現を使うテキスト・人が少なくない。この授業で使われる記号が、他の講義科目中に現れる記号と違う、ということはありがちである。
学校 (高校まで、ということ) の数学ではそういうことはなかったはずなので、とまどうと思うが、慣れて欲しい。「色々なやり方で書かれたものを読めるが、書くときはそのとき適切な書き方を選択して書く、ことをめざす。」

目次
0

イントロ
0.1 数理リテラシーとは . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.2 論理についてのイントロ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
3

1

命題論理
1.1 命題とその真偽 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 否定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 かつ (論理積) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 または (論理和) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 かっこ, 論理演算の結合の優先順位 . . . . . . . . . . . . . . . . . . . . . . . .
1.6 同値, 真理値表による証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 同値変形による証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8 ならば . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9 misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9.1 逆、対偶、裏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9.2 必要条件、十分条件、必要十分条件 . . . . . . . . . . . . . . . . . . . .

4
4
6
7
8
8
10
14
17
18
18
18

1

2

述語論理
2.0 臨時講義: 数学で良く使う数の集合を表す記号 . . . . . . . . . . . . . . . . . .
2.1 述語 (命題関数, 条件) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 「すべての」,「任意の」, ∀ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 「存在する」,「ある」, ∃ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 複数の量称を含む命題 (工事中) . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 複数の変数を含む述語 . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 複数の変数を含む述語の読み方 . . . . . . . . . . . . . . . . . . . . . .
2.4.3 量称記号の順序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 量称を含む命題の証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 量称と論理の法則、特に否定命題 . . . . . . . . . . . . . . . . . . . . . . . . .

19
19
19
20
22
24
24
25
27
28
31

A 結合の優先順位

33

B トートロジー

33

C ユークリッドの原論 — 証明の起源

34

D 基本的な用語・言葉遣い
D.1 議論の中での記号の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.2 公理とは . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34
34
35

E 授業の進行

36

F 解答

36

(少し直したいと思っているのだけど、時間が取れない…)

この講義での約束ごと集合や数列を表す以外の目的で { } を使用しない。(普通の数学のテキストでは、その {}が集合を表しているのか、数列を表しているのか、演算の結合順を指定するためのカッコを表しているのか、読者が文脈から判断することを要求しているが、この講義では、そういうことはしない。)
命題や条件をカンマ , で区切って並べることはしない。必ず「かつ」, “and”, “∧” や、「または」, “or”, “∨” を書いて意味を明示する。(これも普通の数学のテキストでは、文脈から判断しなさい、という場合が少なくない。個人的には、それは悪い慣習だと考えている。ともあれ、この講義では数学の言葉として論理を学ぶので、なるべく省略や短縮化は抑えて書くという方針で記述する。)
数学のテキストでは、同じことを表すために色々な用語・記号が使われているのが普通である。どういう用語・記号が使われるか、ある程度まで紹介するが (色々なものが読めるようになるべきであるから)、以後はこの講義で選択した用語・記号を首尾一貫して用いる (相手に伝えるときは、用語・記号は統一する方が親切で、そうすべきである)。色々な文書を読んだり、話が聴けるようになるべきであるが、自分が書いたり話すときは、TPO で選んだやり方を首尾一貫して使うようにしよう。

2

0

イントロ

0.1

数理リテラシーとは

この講義の科目名である「数理リテラシー」は、一体何だろうか。辞書によると、リテラシーという言葉は、万人に必要な基礎的な読み書き能力のことである、と説明されている。この講義の科目名としての「数理リテラシー」は、数理 (ここでは数学という意味) に必要な (最低限度の) 読み書き能力である、という意味ととらえることにする。具体的には、論理、集合、写像という、現代数学を記述するための言語である。
なぜそれが大事か、今学ぶ必要があるかについて、私なりの考えを述べておく。高校までは「公式が主役の数学」をしていたが、大学以上では「定理が主役の数学」をする。定理は命題であり、命題を記述するための言葉・文法があり、それを用いて読み書きができる必要がある。
最近はあまり聞かれなくなったような気がするが、数学は計算が重要なので言葉はあまり重要ではなく、説明が下手でも数学ができるということはありえる、というようなことが言われていた。これは大きな誤解である。
(脱線: 以前は大学内で、入試から記述式の試験を追放しよう (マークシート形式で十分ではないか) という意見がかなり強かった。記述試験は採点作業に多大なコストがかかること、特に時間がかかるために合格発表スケジュールが後ろにずれることが学生確保に不利に働く、という意見もあった。これに対して、数学の教員は、採点作業の負荷が最も大きい立場にあったが、記述式試験は重要かつ必要であると、廃止には強く反対していた。最近は記述式試験の重要さは認められたようだが、そうなるまではずいぶんと嫌味のようなことも言われ続けたものである。)
一つ誤解されがちなことを注意しておく。言語は伝達手段であるが、実は思考のための必須の道具である。他人と対話せずに一人で考えている段階でも、言語を駆使することが必須なのである。
余談 0.1 シラバスで参考書にあげることにしている
新井紀子, 数学は言葉 ̶ math stories, 東京図書 (2009)
は、数学における言葉の重要性を上手に説明していると思う。新井先生は次の文章も書いている。

• 『「数は言葉」の対象は？』https://web.archive.org/web/20150916080120/http://
researchmap.jp/jo8s7ljcd-78/「言語教育の方法論で数学を教える」という言葉が印象に残った。
• 『数学の言葉への脱皮』https://tanemaki.iwanami.co.jp/posts/1360
脱皮はかなり難しいけれど大事である、がんばろう、という話。

0.2

論理についてのイントロ

数理リテラシーの 3 つの大きな話題 (論理、集合、写像) のうち、論理についての説明を始める (しかし例の中では集合を持ち出したりする…ちょっといいかげん1 )。
論理は数学の基礎と言えるが、論理をきちんと説明するのは案外難しい。大学の数学のテキストで論理を扱っているものは、実はあまり多くない2 。論理については高等学校までの数学
1

まあ、集合は高校で習っているから少しならいいか、というつもりです。
と書いたけれど、最近少しずつ増えてきているような気がする。コンピューター・サイエンス (情報科学) の影響があるような気がしている。気のせいかもしれないけれど。
2

3

で身についているものと考えているのか、集合から説明から始めているものが多い。数少ない論理を扱った本に初等的なものは少なく、内容も本ごとに大きく異なっている。
それでは高等学校の数学の教科書での論理の説明はしっかりしているかというと、そうは言いにくいところがある。ド・モルガンの法則はあっても論理の分配律はないなど、不思議な感
じのする内容である (率直に言って「一体どう考えているんだろう」と思う)。
この講義で採用した教科書 (中島 [1]) は、論理について相当な程度まで説明してある点で貴重であると思う。この本の最初の部分では、日常語の論理と数学での論理の違いの説明にページを割いている。それは意味のあることだし、興味深く感じられる人もいるようだが、授業でこなすのは、かなり時間が必要になるし、以後の必要な数学を展開するのに必須とは私には思えない。そこでこの講義では、以下のようにする。
まず数学で用いる論理を記号、式で表すことを目標とする。式で表すことで論理の法則が明確になる。それを確認することで先に進み、最後に (時間が残っていれば) 反省することにしよう (どちらかというと、教科書とは逆順に話を進める…最近は時間に余裕がなくて、反省はサボりがちになっている)。
教科書以外の読みやすい参考書を二三あげておく (どれもとてもお勧め)。中内 [2] 練習問題が多く、学習に便利だと思われる。新井 [3] は論理学の専門家による、初学者向けの分かりや
すい真面目な入門書である。金子 [4] も色々な情報があって良い (使っている記号の違いがやや大きい)。
少しずれるが、数学的な文章を分かりやすく書くにはどうすれば良いか論じた結城 [5] をあげておく。
実を言うと、講義をする立場としては、上に紹介した教科書や参考書の説明では、私自身がすっきりしないところがいくつかある。もう少し専門的な内容の本を何冊かめくってみて (例えば島内 [6], 前原 [7])、自分なりにすっきりした説明が出来ないか検討したが、今のところ解答が見つかっていない。

命題論理

1

命題と条件に関する論理演算 ¬ (〜でない), ∧ (かつ), ∨ (または), ⇒ (ならば) は、真理値を定めるルールによって特徴づけられる。見方によっては意味を考えずに (?) 定義出来る3 。
この節では、複数の命題が組み合わされた複合命題の真偽を問う命題論理を扱う (変数を含
む「条件 (述語)」については、次節「述語論理」で扱う)。

1.1

命題とその真偽(以下、用語の説明をするが、数学的な定義というわけではない。)
めいだい

正しいか正しくないか、数学的に判断できる主張 (文章や式) のことを命題 (proposition) と呼ぶ。
(注意: 正しい、正しくないとは、道徳的・倫理的・法律的な善悪を言っているのではない。
真理・事実に合致するか、ということである。)
例 1.1 「1 + 1 = 2.」は命題である。「円周率は有理数である。
」、「sin 1 は 1 より大きい。
」は命題である。
「1 億は大きい。」は命題でない。
3

いわゆる数の演算でも同様のことをしている。加える、引く、かける、割る、という量に関する演算が数の世界で形式的に定義されているわけだ。

4

命題のことを p, q, · · · , p1 , p2 , · · · のような文字や記号で表す。
しん

ある命題が正しいことを「その命題は真である (true)」、「その命題は成り立つ」
、
「その命題
しんりち

が成立する」、「その命題の真理値 (truth value) は T である」といい、命題が正しくないことぎを「その命題は偽である (false [fÓ:ls], 「フォールス」)」、「その命題は成り立たない」、「その命
題は成立しない」、「その命題の真理値は F である」という。つまり、ある命題の真理値とは、その命題が真であるか、偽であるかを T, F という記号で表したものである。T の代わりに 1,
F の代わりに 0 と書く流儀もある (実は 2 進数のコンピューターでの論理演算に対応する)。
例 1.2 以下の 4 つの命題

p1
p2
p3
p4

1 + 1 = 2.
円周率は有理数である。
e > 2.7. (ただし e は自然対数の底)
∞
X
1
= 1.
2n
n=1

の真理値は順に T, F, T, T.
命題が真であることを論理的に示すことを命題を証明する (prove) という (あるいはその操作を証明 (proof) と呼ぶ)。証明された命題のことを定理 (theorem) と呼ぶ。
数学の議論は定理をつないで行く作業である。


脱線: 証明の起源

証明は古代ギリシャで発明された。一気にすごい完成度の高いものが出来た。
アレクサンドリアのエウクレイデス (ユークリッド) により、その時期までの数学の集大成が「原論 (ストケイア)」という著作 [8] にまとめられた (B.C. 3C 頃, 全 13 巻)。公理 5(or 9), 公準 (5) から始めて 465 の命題が証明されている。それらの命題は、現在でもすべて正しい (証明には文句があったりするけれど) と考えられている。






定理、補題、命題、系
ほだい

数学のテキストや講義で、“正しい命題” という意味での定理を、定理 (theorem), 補題 (補けい助定理, lemma), 命題 (proposition), 系 (corollary) のように区別して呼ぶことがある。これは次のように使い分けられている。

• 全部定理にすると、数が多くなって、重要さの区別がつきにくいので、特に重要なものだけを「定理」と呼ぶ。
• 定理を証明する目的で用意される “小さめの定理” を「補題」と呼ぶ。
• 定理などからすぐに導かれる “小さめの定理” を「系」と呼ぶ。
• その他の “小さめの定理” を「命題」と呼ぶ。
注: 真な命題であるという意味では定理であるが、重要性がそれほどでもないので「命題」と呼ぶ、というやり方は、もしかすると古めかしいかもしれない。


余談 1.3 もう少し “文法” の説明をすべきかもしれない (採用している教科書がその辺を省略しているので…)。¬, ∧, ∨, ⇒, ⇔ を論理記号といい、命題を表す “変数” に相当する p, q, . . . ,5

p1 , p2 , . . . などを命題変項という。つねに T の真理値を持つ命題を表す記号 ⊤ とつねに F の真理値を持つ命題を表す記号 ⊥ を導入し (⊤, ⊥ の代わりに ⋎, ⋏ を使う本もある。どういう字を採用するかは複数の流儀があるようだ。)、命題定項という4 。論理記号、命題変項、命題
定項が語彙で、それらを適当なルールで組み合わせたもの全体を論理式と呼ぶ。
⊤, ⊥, ⋎, ⋏ は、TEX ではそれぞれ \top, \bot, \curlyvee, \curlywedge と入力する。

1.2

否定

命題 p について、「p でない」という命題を、p の否定 (negation) と呼び、¬p で表す。読
むときは「p でない」または「not p」という。
√
例えば「1 + 1 = 2」を p とするとき、¬p は「1 + 1 ̸= 2」である。また「 10 > π 」を p と√するとき、¬p は「 10 ≤ π 」である。(これはここに書くことではないような気もするが、集合の包含関係 A ⊂ B の否定は A ⊃ B ではなく、A ̸⊂ B である。)
p の否定を表すのに、p や ∼ p など、¬p 以外の記号を用いることも多い。この講義では首尾一貫して ¬p と表す。
(豆知識) ¬p は TEX では、\neg p あるいは \lnot p と入力する。
次の 2 つのことを仮定する (認めて議論する)。


はいちゅうりつ

排 中 律 (the principle of excluded middle)

すべての命題 p について、p または ¬p のどちらかが成り立つ。



むむじゅんりつ

無矛盾律 (the law of noncontradiction)

すべての命題 p について、p と ¬p が同時に成り立つことはない。










むじゅん

矛盾 (contradiction) とは、ある命題 p とその否定命題「p でない」が同時に真であることをいう。無矛盾律とは、矛盾が存在しない、ということである。
余談 1.4 (無矛盾律を矛盾律という人もいる) 以前の講義ノートでは、無矛盾律のことを矛盾律と呼んでいたが、排中律という言葉と並べるとおかしな感じがした。矛盾がないという意味なのだから、「排矛盾律」とか、矛盾を否定するような表現にすべきではないか。
「無矛盾性」という言葉は知っていたので、「無矛盾律」という言葉はあるのかな？と思ったら、ちゃんとそういう言葉があることが分かった (どちらも同じ意味で使われている、という変な状態)。というわけでこの講義では「無矛盾律」を使うことに改めた。
何か 1 つの命題 p について、p と ¬p が同時に成り立てば、すべての命題 p′ について、p′と ¬p′ が同時に真であることが証明出来る。もしそうなったらムチャクチャであり5 、まともな議論は一切出来ない。だから無矛盾律は絶対に必要であると考えられている。

1 + 1 = 2 や π > 4 のような命題 p については (真偽がすぐ分かるので)、p か ¬p のどちらかが成り立つことは自明だが、真偽が容易に判定できないような命題についてもどちらかが成り立つことを仮定するのが排中律である。このことに不賛成な数学者もいて、直観主義論理というのを考案したが (有名なのは Brouwer6 )、以下では排中律を仮定して議論を行う。
4

教科書では導入されていない。そのせいで、ちょっとやりにくくて困っている。
例えば、1 + 1 ̸= 2 も 1 + 1 = 3 も真であることになる。
6
Luitzen Egbertus Jan Brouwer (1881 年〜1966 年) は、直観主義数学の創始者としても有名だが、Brouwerの不動点定理などのトポロジーの分野でも多大な業績を残した。
5

6

背理法
命題 p が真であることを証明するために、p が成り立たない、つまり ¬p が成り立つと仮定しはいりほうて、矛盾が導かれることを示す、という方法がある。これを背理法(proof by contradiction— 直訳すると「矛盾による証明」) という。
(排中律により、p か ¬p のいずれかが成り立つ。¬p が成り立つと仮定すると矛盾が生じる
ならば、無矛盾律より ¬p は成り立たないことが導かれる。ゆえに p が成り立つ。)
真理値表
すべての命題 p について、¬p の真理値は、p の真理値が T であれば F, p の真理値が F であれば T である。このことを表 1 のような表形式で表したものを真理値表 (truth table, 真偽表) と呼ぶ。

¬p
F
T

p
T
F

表 1: p とその否定 ¬p の真理値表(念のため) 行ごとに読むわけである (p が T のとき ¬p は F, p が F のとき ¬p は T で
ある)。

1.3

かつ (論理積)2 つの命題 p と q に対して、「p であり、かつ q である」という命題を p ∧ q と表し、
「p か
つ q」
、
「p and q 」と読む。
れんげん

p と q の論理積 (logical conjunction)、連言(conjunction) と言う (これらの言葉はあまり使わないので、覚えなくても良いかもしれない)。
「そして」、「しかし」は良く出て来るが、どちらも「かつ」と同じである (日常語としては、それぞれ、順接、逆接で、ニュアンスは異なるが、2 つの事実が同時に成立しているという意
味では同じである)。
p ∧ q の真理値は、p と q の真理値がともに T であるときに T で、そうでないときは F である。
p と q はそれぞれが T, F という 2 つの真理値を取るので、その組 (p, q) の真理値は 4 つの場合がある。そこで p ∧ q の真理値は、表 2 のような真理値表で表せる。
p
T
T
F
F

p∧q
T
F
F
F

q
T
F
T
F

表 2: p, q とその論理積 p ∧ q の真理値表
注意 1.5 (順番について) 4 つの場合をどのように並べるかについては、「辞書式順序」を用いることを強く勧める (樹形図を使って素直に書くとそうなるはず)。

7

T の方が F より先、とすると、上の表の順番になる。F の方が T より先、とすると
p
F
F
T
T

p∧q
F
F
F
T

q
F
T
F
T

となる。

(豆知識) TEX では、p \wedge q あるいは p \land q と入力する。

1.4

または (論理和)

2 つの命題 p と q に対して、「p であるか、または q である」という命題を p ∨ q と表し、
「pまたは q 」、「p or q 」と読む。
せんげん

p と q の論理和 (logical disjunction)、選言(disjunction) と言う (これらの言葉も覚えなくても良いかも)。
p ∨ q の真理値は、次の表 3 のように定める。
p
T
T
F
F

p∨q
T
T
T
F

q
T
F
T
F

表 3: p, q とその論理和 p ∨ q の真理値表

2, 3, 4 行目は抵抗がないと思うが、1 行目、つまり p が T, q が T であるとき、p ∨ q は Tというのは、抵抗を感じる人がいるかもしれない。日常用語で「または」というのは、どちらはいたてきろんりわ

か一方だけが、という意味 (排他的論理和 (exclusive or) という) に使う場合もあるからである。数学で「または」というのは、少なくとも一方が、という意味で使う約束である (そうする理由は、そうした方が記述がシンプルになる場合が多いからである7 )。
繰り返しになるが、p と q がともに T であるとき p ∨ q は T というのは、数学的事実を主張しているというよりも、そういうように ∨ という論理演算を定義している (言葉の約束である)。

(豆知識) TEX では、p \vee q あるいは p \lor q と入力する。

1.5

かっこ, 論理演算の結合の優先順位

ここまでで、¬, ∧, ∨ を導入した。
数式と同様に複数の演算を組み合わせた式が登場する。
7

例えば、良く出て来る「ab = 0 は、a = 0 または b = 0 と同値」という内容を、排他的論理和の「または」で表現するとどう表現すれば良いか？また、「abc = 0 は、a = 0 または b = c または c = 0 と同値」についてはどうか？

8

演算の結合の順番を指示するため、かっこ () を用いる。これについては (学校数学での訓練で) 数式の場合に十分慣れていて、その経験が役立つだろう、練習も必要ないだろう、と考えている。そのため説明は省略させてもらう。

p ∨ (q ∧ r) と (p ∨ q) ∧ r は違う。
p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

r q ∧ r p ∨ (q ∧ r) p ∨ q (p ∨ q) ∧ r
T
T
T
T
T
F
F
T
T
F
T
F
T
T
T
F
F
T
T
F
T
T
T
T
T
F
F
F
T
F
T
F
F
F
F
F
F
F
F
F

第 5 列と第 7 列の真理値は違うことに注目。
第 1〜3 列の行の順番にも注目 (前回説明した辞書式順序)。

• 数式の場合、乗算 × は加算 + よりも優先するというルールを採用するのが普通で、(p × q) + r は単に p × q + r と書かれる。
しかし• ∧ と ∨ の場合、優先順位を定めないので、つねにかっこをつけて書く。
例 (p ∧ q) ∨ r を p ∧ q ∨ r と書いたりしない (かっこ省略はルール違反)。
(∧ を論理積, ∨ を論理和というけれど、∧ を ∨ より優先したりしない)。
一方• ¬ は、∧ や ∨ より優先的に結合する、と約束するのが普通。
例 1.6 (¬ の結合は ∧ や ∨ より強い) (¬p) ∨ q は、¬p ∨ q と書いて良い。
¬p ∨ q は、¬(p ∨ q) ではなく、必ず (¬p) ∨ q という意味である。
(¬p) ∨ (¬q) は、¬p ∨ ¬q と書いて良い。
この講義では、かっこは省略せず、(¬p) ∨ q と書くことが多い。この後、たくさんの記号が出て来て、それらについての順序の優先ルールを全部間違いなく覚えて使うのは、(練習時間があまり取れないので) 難しい、と考えるからである。(数式の場合は、小学校以来かなり長い練習時間があった。)
注意 1.7 (括弧の種類について) 数式の場合は、 ( ) (英語では parenthesis, 複数形は parentheses) だけでなく、中括弧 { } (英語では brace) や大括弧 [ ] (英語では (square) bracket)
も併用するのが普通だが、ここではなるべく丸括弧 ( ) だけを使うことにする。特に、大括
弧 [ ] を使う場合はあるが、中括弧 { } は使わないことにする。{ } は集合を表す時に必須で、混用すると式の意味が曖昧になる場合があるので、それを避けるためである。
演算の結合順を指定するために 1 つのカッコだけで済ませることについては、実はプログラ
ミング言語ではそうしている場合が多いので、以前よりは抵抗が生じにくいだろうか。
余談になるが、英語圏では、( ), [ ], { } の順に用いる。そのせいで、中括弧の使用頻度
は他の括弧と比べて低くなっている。集合を表すために { } が採用されているのはそれが理由ではないか、と個人的に考えている。

9

ここまでのまとめと注意
ここまで、命題の真理値 T, F と、命題に関する 3 つの演算 ¬, ∧, ∨ を導入した。
以下、これらの演算を組み合わせた複雑な式が登場する。
普通の数に対する演算 ×, + については、「(カッコで指定していないならば) × を先に計算する」という約束をするが、∧, ∨ については特にそのような約束をしないのが普通である。
そのため、どちらを先に計算するかを指示するため、括弧を多用することになる。つまり数では、 p と q × r の和を p + q × r と書けるが、論理では、p と q ∧ r の論理和は p ∨ (q ∧ r) のように書かねばならない。(括弧を省略して p ∨ q ∧ r と書くと、(p ∨ q) ∧ r と区別が出来ない— なお、実際に両者が異なることは、後述の例 1.12 で確認する)。これは後で学ぶ集合の ∩,∪ についても同様で、A ∪ (B ∩ C) のように括弧を付けるのが普通である。
なお、¬ は ∧ や ∨ より優先的に結合する、と約束するのが普通である。例えば、(¬p) ∨ q
は ¬p ∨ q と書いて構わない。また、(¬p) ∨ (¬q) は ¬p ∨ ¬q と書いて構わない。
なお、付録の A「結合の優先順位」も参照することを勧める。

1.6

同値, 真理値表による証明

2 つの命題 p と q に対して、(その具体的な内容に関わらず、その真理値のみに注目して)
どうち

p と q の真理値が一致するとき、その 2 つの命題は同値 (equivalent) であるといい、p ≡ q で表す。
例えば、1 + 1 = 2 と sin 1 < 1 はどちらも真であるから
1+1=2

≡

sin 1 < 1.

すべての命題 p に対して

p
T
F

¬p
F
T

¬(¬p)
T
F

であるから、¬(¬p) (これは単に ¬¬p とも書く) と p は同値である。つまり(1)¬¬p ≡ p (反射律).

同様にして以下のことが証明できる。

(2) すべての命題 p について、p ∧ (¬p) は常に偽である (無矛盾律)。すべての命題 p につい
はいちゅうりつて、p ∨ (¬p) は常に真である ( 排 中 律 , law of excluded middle)。

(以下「すべての命題」と書くのをさぼらせてもらうが、そういう意味で書いてあることは忘れないで欲しい。)(3) p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p (交換律).
(4) p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r, p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r (結合律).
(5) p ∨ (q ∧ p) ≡ (p ∨ q) ∧ p ≡ p (吸収律).
(6) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) （分配律).
10

べきとうりつ(7) p ∨ p ≡ p, p ∧ p ≡ p (冪等律).
(8) ¬(p ∧ q) ≡ (¬p) ∨ (¬q), ¬(p ∨ q) ≡ (¬p) ∧ (¬q) (ド・モルガンの法則 (de Morgan の法則)).
そく(豆知識) 結合律、交換律、吸収律が成り立つ代数系を束 (lattice) と呼ぶ。さらにブール束と呼ばれる代数系もある (詳細は省略する)。その典型例になっている。
ここでは分配律の一つ、p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)(♠)

を証明しよう。これは次の真理値表から証明できる8 。

p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

r
T
F
T
F
T
F
T
F

q∨r
T
T
T
F
T
T
T
F

p ∧ (q ∨ r)
T
T
T
F
F
F
F
F

p∧q
T
T
F
F
F
F
F
F

p∧r
T
F
T
F
F
F
F
F

(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F

(書き方についての注意: 左 1,2,3 列に注目。23 = 8 個もれなく書くためには、樹形図を念頭におくと良い。すでに説明した辞書式順序ということである。)
真理値表の 5 列目と 8 列目の真理値が一致するので、(♠) が成り立つ。
問 1.

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)(♡)
を証明せよ (解答は p. 36)。

注意 1.8 (行と列) 上の例で「5 列目」、「8 列目」と書いたが、宿題などで「5 行目」、「8 行目」と書く人がいる。横書きの場合は、「行 (row)」は横にのびているもので、縦にのびているのは「列 (column)」というのが普通である (Cf. 線形代数の行列の行と列)。
問 2. ド・モルガンの法則を真理値表を使って証明せよ。
ド・モルガンの法則は、集合の演算に関する法則として高校で学んだ人が多いかも知れない。


集合に関するド・モルガンの法則 (高校流の表し方)

集合の補集合を上に

をつけて表すことにすると、A ∩ B = A ∪ B,

A ∪ B = A ∩ B.



これを ¬(p ∧ q) ≡ (¬p) ∨ (¬q), ¬(p ∨ q) ≡ (¬p) ∧ (¬q) と見比べてみよう。
例 1.9 p, q をそれぞれ「金の斧がもらえる」,「銀の斧がもらえる」という命題とする。
8

普通の数の演算規則の証明と異なり、場合の数が有限個しかないので、すべての場合について計算して確かめるという手段が有効である (その意味では普通の数の演算規則の証明よりも易しい)。

11

「金の斧がもらえる」かつ「銀の斧がもらえる」 (両方もらえる)の否定は「金の斧がもらえない」または「銀の斧がもらえない」(少なくとも一方はもらえない)である。
一方「金の斧がもらえる」または「銀の斧がもらえる」 (少なくとも片方はもらえる)の否定は「金の斧がもらえない」かつ「銀の斧がもらえない」(どちらももらえない)である。
「または」を「どちらか一方だけが成立するときに真」(排他的論理) でなく、「少なくとも一方が成立するときに真」と定義したことで、上のようなきれいな形の式になることに注意する。
余談 1.10 論理の説明をする際に、上のように日常語による例を使う場合があるが、本当は、こういうのは命題もどきで、その真偽を数学的に判定できるようなものではない。「金の斧」
がなんであるか、「もらえる」とはどういうことか、考え始めると、曖昧なことが分かる。
余談 1.11 (トートロジー) 命題変項を含む論理式が、すべての命題変項の可能な真理値に対して、常に真となるとき、その論理式をトートロジー (恒真式, tautology) と呼ぶ。例えば p∨(¬p)
はトートロジーである。
問 3. (p ⇒ q) ∧ (q ⇒ r) ⇒ (p ⇒ r) はトートロジーであることを示せ。
例 1.12 (念のため) p ∨ (q ∧ r) と (p ∨ q) ∧ r は同値でないことを確かめよう。

p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

r
T
F
T
F
T
F
T
F

q ∧ r p ∨ (q ∧ r) p ∨ q (p ∨ q) ∧ r
T
T
T
T
F
T
T
F
F
T
T
T
F
T
T
F
T
T
T
T
F
F
T
F
F
F
F
F
F
F
F
F

確かに第 5 列と第 7 列の真理値は違っている。

(おまけ) コンピューターで論理演算(ここはおそらく授業ではカットすることになる。)
コンピューターのプログラミング言語の C では、整数型データに対して論理演算が出来る。
少々変則的であるが、0 は F, 0 以外の整数は T として扱われる。
¬ は !, ∨ は ||, ∧ は && で計算できる (ビット演算子の |, & と混同しないように注意)。

12

logical.c#include <stdio.h>
int main(void){
int p,q;printf("p !p\n");for (p = 1; p >= 0; p--)printf("%d %d\n", p, !p);printf("p q p||q p&&q p->q\n");for (p = 1; p >= 0; p--)for (q = 1; q >= 0; q--)printf("%d %d %d%d%d\n", p, q, p||q, p&&q, !p||q);return 0;
}



実行結果

$ cc logical.c$ ./a.out
p !p
1 0
0 1
p q p||q p&&q p->q
1 1 1
1
1
1 0 1
0
0
0 1 1
0
1
0 0 0
0
1
$







結果を T, F で表すために軽くお化粧。
logical2.c#include <stdio.h>
int main(void){
int p,q;char TF[] = {’F’,’T’};
printf("p !p\n");for (p = 1; p >= 0; p--)printf("%c %c\n", TF[p], TF[!p]);printf("p q p||q p&&q p->q\n");for (p = 1; p >= 0; p--)for (q = 1; q >= 0; q--)printf("%c %c %c%c%c\n",
TF[p], TF[q], TF[p||q], TF[p&&q], TF[!p||q]);
return 0;
}




13



コンパイル＆実行結果$ gcc logical2.c ; ./a.out
p !p
T F
F T
p q p||q p&&q p->q
T T T
T
T
T F T
F
F
F T T
F
T
F F F
F
T
$


1.7





同値変形による証明

真理値表による証明は、「必ず出来る」という意味では強力である。しかし、例えば(♣)(p ∨ q) ∧ (r ∨ s) ≡ (p ∧ r) ∨ (p ∧ s) ∨ (q ∧ r) ∨ (q ∧ s)を証明せよ、と言われると面倒である9 。p, q, r, s と 4 つあるので、24 = 16 行必要になる。
期末試験でそれを実行した人がいるが、書くのも大変、読んでチェックする方も大変、間違えたときバツをつけるのは悲しい (16 行もあったら、どこかでミスをしても仕方がないので、やり方が悪いと考えるべきだろう)。
数に関する式の証明 (計算) と同様に、既に述べた基本的なルールと、次の 2 つの定理を用いれば、式変形により証明が出来る。
与えられた論理式をそれと同値な論理式で置き換えることを同値変形という。同値変形を続けて得られる論理式はもとの論理式と同値である。
余談 1.13 (同値変形について 3 点ほど) (1) ほとんどの人は、「同値変形」という言葉は既に聞いたことがある、と私は信じているのだけれど、本当のところはどうなのだろう。気になったので高校の数学の教科書 (数研出版) の中で検索したところ、発見できなかった。この講義で教科書指定した中島 [1] にも、普段頼りにしている数学英和・和英辞典 (小松 [9])にも、書いてない (それ以外も何冊か、論理のことが書いてある本で調べたけれど、発見できなかった。)。どういう言葉・記号を学ばせるべきかは、学習指導要領にでも書いておけば良いのに、と思うのだけど、学習指導要領は「同値変形」どころか「同値」という言葉も載っていない。…ちょっと脱線した。別の表現に置き換えるべきか、この言葉を講義外で使うときは気をつけようと注意するか、検討中である。

(2) 方程式を解く場合、与えられた条件 (方程式) を同値変形することが基本である、と高校生のときに教わった (そういうこともあって、「同値変形」は便利な言葉と思っているのだが…)。同値変形を続けた場合、最終的に得られた条件が解を示している。途中で一箇所でも同値でない変形 (「ゆえに…が成り立つ」) を入れてしまうと、最終的に得られたものが本当に解であるか、確認が必要になる。集合の言葉 (この講義では、この後に学ぶ) を使わせてもらうと、方程式を解くとは、その方程式の解の集合の簡単な表現を求めることである。その場合、同値変形は、集合の相等関係 (=) に対応していて、「ゆえに…が成り立つ」は、集合の包含関係 (⊂) に対応している。A = B = C = D ならば A = D が結論できるが、A = B ⊂ C = D ならば A ⊂ D は言えるが、A ⊃ D であるかは (別の手段で確認しないと) 分からない。
9数の場合の (p + q)(r + s) = pr + ps + qr + qs に対応している。

14



√
「 x + 1 = x を解け。」という問題を検討してみよう。

√

方程式の両辺を自乗して x + 1 = x2 . 2 次方程式の解の公式から x = 1±2 5 . もとの方√√
程式に代入して成り立つかチェックすると、x = 1+2 5 は確かに解であるが、x = 1−2 5√√は解ではない。ゆえに x + 1 = x の解は 1+2 5 である。(解答終)


A= x

√

x+1=x ,とおく (つまり A は(

B = x x+1=x

√

2

,

C=

√ )
√
1+ 5 1− 5
,
,
2
2

(
D=

√ )
1+ 5
2

x + 1 = x の解集合, B は x + 1 = x2 の解集合)。
A⊂B(実は A ̸= B),

B=Cであるから A ⊂ C である。C の要素が A に属するか調べて、A = D が発見できる。
(等式の両辺を自乗するのは、一般には同値変形でないので、解集合が等しくならな
いこともあるが、包含関係 A ⊂ B は成り立つ。それで与えられた方程式の解集合 Aを含む集合 C が得られ、それが大きくなければ (この場合はたった 2 つの要素しかない)、ほどほどの手間でもとの方程式の解集合 (の分かりやすい表現) D が求まる。候
補者を絞ってから２次試験をする、という感じ。
(3) レポートやテストで提出されたものの中に、数式の値が同じになることを「同値」と言っているケースが散見される。まあ、言いたいことは分かるので、それで減点したりはしな
いのだけれど、それは普通の表現ではなく、言葉の濫用でしょう。やめることを勧めます。


定理 1.14 すべての命題 p, q, r に対して

p≡q

かつ

q≡r

ならば

p ≡ r.

(数に関する等式についての「p = q かつ q = r ならば p = r」という定理の命題論理版である。)
証明 p ≡ q は、p と q の真偽が一致することを意味する。言い換えると、
p と q が両方とも真である、または p と q が両方とも偽であるということを表す。
それと同時に q ≡ r が成り立つので、3 つの命題 p, q, r がすべて真である、または 3 つの命題 p, q, r がすべて偽であるが成り立つ。特にp と r が両方とも真である、または p と r が両方とも偽であるが成り立つ。ゆえに p ≡ r.

15







定理 1.15 すべての命題 p, q, r に対して

p≡q
ならば、

(1) ¬p ≡ ¬q(2) p ∧ r ≡ q ∧ r(3) p ∨ r ≡ q ∨ rが成り立つ。


(数に関する等式ならば、等式の両辺に同じ数を足したり、かけたりしても、等式が得られる、という定理に相当する。その命題論理販である。
「代入ができる」という見方もできる。)
証明 (1) のみ証明する (他も同様にして証明できる)。
p ≡ q が成り立つことは (定義によって)p と q が両方とも真である、または p と q が両方とも偽であるということである。

(i) p と q が両方とも真であるとき、¬p と ¬q は両方とも偽である。
(ii) p と q が両方とも偽であるとき、¬p と ¬q は両方とも真である。
いずれの場合も、¬p と ¬q の真偽は一致する。ゆえに¬p ≡ ¬q.
例 1.16 (p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r) を証明せよ。
分配律は既に証明したと記憶しているかもしれないが、§1.6 に載せたのは、

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)であり、同じでないことに注意する。
一方、§1.6 で、∧ について交換律 p ∧ q ≡ q ∧ p が成り立つことは述べてある。
この 2 つを組み合わせれば良い。
(証明)(p ∨ q) ∧ r ≡ r ∧ (p ∨ q)
≡ (r ∧ p) ∨ (r ∧ q)
≡ (p ∧ r) ∨ (q ∧ r)
最初の ≡ で交換律 (と定理 1.15)、次の ≡ で結合律、次の ≡ で交換律 (と定理 1.15) を用いている。
ゆえに (定理 1.14 を用いて)(p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r).
問 4. (1) (♣) を証明せよ。(2) (♣) で ∧ と ∨ を入れ替えた式を証明せよ。

16

1.8

ならば

命題に関する新しい演算として「ならば (⇒)」を導入する。
2 つの命題 p と q に対して、「p ならば q である (If p, then q)」という命題を p ⇒ q と表す。その正確な意味は以下で定義する。

(本によっては、p ⇒ q のことを p → q と書くものがある。さらに、p → q の真理値が T であることを p ⇒ q と書いて区別して表すこともある。)
どのように定義するか。ここでは真理値表を用いて定義する (表 4)。

p
T
T
F
F

q
T
F
T
F

p⇒q
T
F
T
T

表 4: p ⇒ q の真理値表
例 1.17 「1 + 1 = 2 ⇒√

2 は無理数」は真である。「1 + 1 = 3 ⇒√2は有理数」も真である。

普通は p が真のときのことしか考えない (そのとき q が真になるかどうかが問題となる) よ
うな気がするが、p が偽のときも、表を埋めておくのである。


理解した気分になるための解読？

p ⇒ q が真であるためには、p が真であれば q が真であることが大事で、p が偽のときはq は真でも偽でもどちらでも良い (どちらでも p ⇒ q は真である)。一方、p が真であるのに、q が偽である場合は、p ⇒ q は偽である。







上の表の p ⇒ q の真理値は (¬p) ∨ q の真理値に一致する。そこで p ⇒ q とは、(¬p) ∨ q のことと定義することもある。(どちらでやっても良いはずだが、式で定義するのが扱いやすい
ためか、そうしてある本が多いような気がする。)
問 5. (¬p) ∨ q の真理値表を書け。
真理値表で定義するにしても、(¬p) ∨ q のこととして定義するにしても、p ⇒ q ≡ (¬p) ∨ q(2)である。これはぜひとも覚えておこう。
「p ならば q 」の否定が、次のようにド・モルガンの法則を用いて計算できる10 。

¬ (p ⇒ q) ≡ ¬ ((¬p) ∨ q)
≡ (¬¬p) ∧ (¬q)
≡ p ∧ (¬q).
ゆえに

(3)

¬(p ⇒ q) ≡ p ∧ (¬q).

もちろん真理値表を用いて証明することも出来る。いずれにしろ、重要な定理である。
10

これは有名な問題で、これが出来れば数理リテラシーのレベル 1 クリアと言えるかも。

17

余談 1.18 (p ∧ (¬q) をどう読むか) p ∧ (¬q) を言葉で表すには、英語ならば例えば「p and not
q 」とすれば良い。日本語の場合はどうすれば良いだろうか？単に「p かつ q でない」と言うと、¬(p ∧ q) のことを混同されてしまいそうである。「p かつ (q でない)」とかっこを使えば誤解の余地はなくなるが、かっこを使うのは苦し紛れ (そんなの日本語じゃない) と言われそうである。逆接を用いて「p であるのに q でない」とするのだろうか。式で書いたものを簡潔な言葉で誤解なく伝えるのは簡単でないことがある。
注意 1.19 後で出て来る “条件” (述語) に対してではなく、命題に対して ⇒ を用いることに違和感を持つ人が少なくないと想像する。まず「ならば」の前後に書いてあることは、何か共通のものに関係したことで、前者が原因、後者がその結果のように考えるのが普通であろう。
√
上のように定義すると、「1 + 1 = 2 ならば 2 は無理数」は真な命題となるが、真偽は別にし√て、異様な感じがするのではないか (1 + 1 = 2 であることと、 2 が無理数であることに関係があるのだろうか？)。高等学校の数学でも、以前は命題に対して「ならば」を扱っていたが、現在の高等学校の「数学 I」では、「ならば」は条件の場合に限定しているようである (問題を回避している)。

1.9

misc

(ここは高校生のときに学んでいるはずなので、授業ではスキップするかもしれない。)
1.9.1

逆、対偶、裏q ⇒ p を、命題 p ⇒ q の逆 (reverse) と呼ぶ。
たいぐう(¬q) ⇒ (¬p) を、命題 p ⇒ q の対偶 (contraposition) と呼ぶ。
うら(¬p) ⇒ (¬q) を、命題 p ⇒ q の裏と呼ぶ (らしい — 数学では滅多に使わない11 )。
命題 p ⇒ q が真であっても、その逆 q ⇒ p が真であるとは限らない (「逆は必ずしも真ならず」)。


定理 1.20 すべての命題 p と q に対して、命題 p ⇒ q とその対偶 (¬q) ⇒ (¬p) の真偽は一致する。
p ⇒ q ≡ (¬q) ⇒ (¬p).



証明





略 (真理値表を書けば分かる。⇒ を使わずに表して同値変形しても良い)。

なお、裏は逆の対偶であるから、裏と逆の真偽は一致する。
問 6. 定理 1.20 を証明せよ。

1.9.2

必要条件、十分条件、必要十分条件(この段階では、p, q は命題であり、条件ではないので、少しおかしい言葉遣いのような気がするが…§2「述語論理」に回すべきか？)
命題 p ⇒ q の真理値が T であるとき、p は q の十分条件 (p は q が成り立つための十分条件)、q は p の必要条件 (q は p が成り立つための必要条件) と呼ぶ。
11

余談であるが、先日気楽なマンガを読んでいたら、数学的に裏と言うのが適切な状況で、登場人物が「裏を返せば…」と言っていて、少々びっくりした。国語的には間違っているような気がしたのだけれど、国語辞典を読んでも判然としない。

18

命題 p ⇒ q と q ⇒ p の真理値がともに T であるとき、p は q の必要十分条件である (p はq が成り立つための必要十分条件である) と呼ぶ。このことを p ⇔ q で表す。
もちろん、p と q について対称なので、p と q を入れ替えても良い。

述語論理

2

ここから (やっと) 数学らしくなる (まともな内容のある命題が記述できる)。
ただ 1 つの数学的対象を扱う場合はそれほど多くなく、複数 (しばしば無限個) の数学的対象に対して何か言及するのが重要である。例えば「平面内のすべての三角形について、その 3
つの内角の和は 180◦ である」。そういうものを取り扱うのに述語論理が必要になる。
余談 2.1 「大学初年級の微積分で、極限を定義するために、ε-N 論法, ε-δ 論法というものがあり、そういうところで述語論理が必要になる」というような意味のことがしばしば言われる。私自身は長いこと知らなかったので、初めて聞いた時は「なるほど」と思ったのだが、良く考えてみると、ε-N 論法, ε-δ 論法に限った話ではないことがすぐに分かる。代数系の公理12などは、述語論理の良い実例で、以下でもたくさん出てくる。

2.0

臨時講義: 数学で良く使う数の集合を表す記号

集合については、論理の後で解説するが、例を書くために、使えると便利なので以下の記号を前倒しで紹介しておく。

x が集合 A の要素であることを x ∈ A, x が集合 A の要素でないことを x ̸∈ A と書く。
記号
N
Z
Q
R
C

意味
自然数全体の集合 N = {1, 2, · · · }
整数数全体の集合 Z = {0, ±1, ±2, · · · }有理数全体の集合
実数全体の集合
複素数全体の集合

由来
natural numbers (自然数)Zahl (ドイツ語: 数)
quotient (比)real numbers (実数)complex numbers (複素数)

図 1: 良く使う数の集合の記号(もともとは太字 (bold face) N, Z, Q, R, C を黒板に書くとき、文字の一部を二重線にする
ことで太字を書いたことにする習慣があって、それが一般化したということらしい。TEX では、\mathbb{N} のように入力するが、bb は blackboard bold の略だとか。直訳すると「黒板太字」ですね。)

2.1

述語 (命題関数, 条件)「x > 3」は (実数) x の値を定めると真偽が確定して命題になる。このような変数 x を含
じゅつご

む主張を、x についての条件 (condition)、述語 (predicate)、命題関数と呼ぶ。
(predicate は [prédik@t] と発音する。)
x についての条件を、p(x), q(x), · · · のように表す (既に慣れている数の集合上で定義された関数の記法と似ているので、あまり抵抗はないであろう)。
12

例えば、結合法則のような法則や、単位元や逆元の存在など。

19

前節で導入した命題に関する演算 ¬, ∧, ∨, ⇒ を、条件に関しても適用する。(¬, ∧ は別にして、∨ や ⇒ はそういうとき初めて、しっくり感じられるのではないだろうか？)
述語論理では、量称記号 (quantiﬁer, 限定記号ともいう) と呼ばれる記号 ∀, ∃ が重要である。

2.2「すべての」,「任意の」, ∀数学で出て来る命題の多くは、何かある一定の範囲のものについて、1 つの例外もなく何かが成立する、という形のものが多い。このような命題を全称命題 (universal proposition) という。典型的な表現は「すべての○○に対して〜が成り立つ」。
「すべての」は「任意の」と言い変えることもできる。
「任意の」は「その人の思いのままにすること」という意味だけれど、「その人」が誰かが重要である。
「任意の」は誤解を招く可能性が高い (∀x は誰かがその人の思いのままに x を与えてくれるということで、受け取る方にとっては、何が来るか分からない、自分では選べない、何でもあり、すべての可能性がある、ということになる。)。「すべての」の方が (日常語でもよく使うし) 誤解が生じにくく良い、と考えている。
一方、証明をする場合は、「x をすべての○○とすると」はおかしく、「x を任意の○○とす
ると」とすべきである。x は○○ではあるが、それ以外は何でもありだ (すべての可能性を排除しない)、ということである。
そういう意味で「∀」を必ず「任意の」と読むことにしているのは悪習である、と私は考えている。
「に対して」は「について」とも言い、「が成り立つ」は「が成立する」または「である」と13も言うし、省略されることもある 。
言葉で表すときは、「すべての」や「任意の」は省略されることも多い。
「(すべての、任意の) 三角形について、(その三角形の 3 つの) 内角の和は 2 直角である。
」
英語でも、“The sum of the interior angles of a triangle is 180 degrees.” とか。
「(すべての、任意の) 微分可能な関数は連続である。
」(これらは、よく知られた常識的な主張 (定理) だから、省略しても分かるだろう、と考えているのだと思われる。)
この講義では、原則として省略しないことにする。期末試験が終わるまでおつきあいください。
「任意の x に対して p(x) が成り立つ」という命題を∀x p(x)と表す。
∀ は、全称記号 (universal quantiﬁer) と呼ばれる。“All” の先頭の文字 ‘A’ を逆立ちさせて作った記号である。
(豆知識) TEX では \forall と入力すると ∀ が出る。
例えば「すべての x に対して、x が実数ならば x2 ≥ 0 が成り立つ」という命題を∀x x が実数 ⇒ x2 ≥ 0
13(ほぼ雑談) 例えば「1 + 1 = 2 である。」, 「1 + 1 = 2 が成り立つ」と言っても良いが、単に「1 + 1 = 2」とするのが普通であろう。もっとも英語では、“1 + 1 = 2” は “one plus one equals two.” あるいは “one plus one
is equal to two.” と読むので、1 + 1 = 2 それ自体が完全な文 (あるいは節) になっていると考えるべきであろう。
日本語でも、「1 + 1 = 2」を「いちたすいちはにである」と読むべきかもしれない。あるいは日本語ではもともと「である」は省略可能で「いちたすいちはに」で文とみなすべきかも。

20

と表す。
括弧 ( ), [ ] を適当に補って∀x (x が実数 ⇒ x2 ≥ 0),∀x [x が実数 ⇒ x2 ≥ 0]のようにも書く。かっこのつけ方は、使う人の好みというか、かなりいい加減である。




∀ まとめ

p(x) を x についての条件 (x を定めると p(x) が命題となる) とする。
“For all x, p(x) (holds)”, 「すべての x について p(x) (が成り立つ、である)」, 「任意のx に対して p(x) (が成り立つ、である)」という命題を∀x p(x) あるいは ∀x(p(x))
と書く。




上の例自体がそうであるように、数学で実際に現れる∀x p(x)の形の命題で、p(x) は多くの場合、p1 (x) ⇒ p2 (x) という形をしている。p1 (x) を「前提条件」,「付帯条件」のように考えて、(∀x : p1 (x)) p2 (x)と書くことがある。「p1 (x) が成り立つような任意の x に対して p2 (x) が成り立つ」のように
読む。
上の例では
(∀x : x は実数) x2 ≥ 0.
集合の記号を使うと、「x は実数」は「x ∈ R」と書ける。すると(∀x : x ∈ R) x2 ≥ 0となるわけだが、しばしば(∀x ∈ R) x2 ≥ 0と略記される。「実数であるような任意の x に対して x2 ≥ 0」、あるいは「任意の実数 x に対2
して x ≥ 0」と読む。
その場の議論の流れから、x ∈ R は当然の前提と考えて省略することもある。

(∀x) x2 ≥ 0(この講義では、なるべくこういう省略はしないことにするが、普通の数学の本では時々ある。)
似たケースとして(∀x : x > 0) x +

1
≥2
x

を

1
≥2
x
と書くこともある。「任意の (すべての) 正の数 x に対して x + x1 ≥ 2」(∀x > 0) x +もう一つくらい例をあげておく。

(∀∆ : ∆ は三角形) ∆ の 3 つの内角の和は 180◦ .
21

例 2.2 A = {1, 2, 3} とするとき(∀x ∈ A)P (x) ⇔ P (1) ∧ P (2) ∧ P (3).
(∃x ∈ A)P (x) ⇔ P (1) ∨ P (2) ∨ P (3).
注意 2.3 (受験生のいないテストは全員合格) 教科書には、「すべての」「任意の」の意味に疑問は生じないというようなことが書いてあるが、「○○の試験でのすべての受験生は合格した。
」(論理式に翻訳すると (∀x: x は◯◯の試験の受験生) x は合格した)という命題は、その試験を受験した人がいないとき、真であるか、それとも偽であるか。それほど明らかでない、と思う人が多いのではないだろうか。数学では受験した人がいない場合、上の主張は真であるとみなす。言い換えると、数学用語としての「すべて」「任意」はそういう意味であると約束する。
余談 2.4 (個人的な体験談から) 昔、ある (当時そこそこ有名だった) 定理の仮定すべてを満でくわたす対象が実は存在しないことが後から分かった、という「事件」に出会したことがある。定義でも定理でも、少なくとも一つ例をあげることが大事である、という良く言われる心得の大事さを痛感する出来事であった。論理について考察するための良い事例でもある。その定理の証明自体には間違いがなかった。要するに「仮定を満たす任意の x について、P (x)」という形の定理で、その証明は正しく、真な命題であった。間違いではないが、ナンセンスな (何の役にも立たない) 定理であった、というわけである。
余談 2.5 (ある年の期末試験) 条件 p(x) を満たす x 全体の集合というのを{x | p(x)},{x ; p(x)} ,{x : p(x)}等で表すと習ったせいか、(∀x | x > 0) x +1≥ 2 (これは変)xのように書く人が (複数) 現れたことがある ( | と : はいつでも同じように使えると勘違いしている？)。私は色々な数学書を読むけれど、こういう書き方をしている本を見たことはまだない。∀ の付帯条件を表すために | は使うべきではないと思う。

2.3「存在する」,「ある」, ∃「∼ を満たす (ような) ○○が存在する」、「ある○○が存在して、∼ が成り立つ」、「ある○○に対して、∼ が成り立つ」、「ある○○が ∼ を満たす」という形の命題 (意味はどれも同じ)も良く出て来る。
「x3 − x + 1 = 0 を満たす実数 x が存在する。」「ある実数 x が存在して、x3 − x + 1 = 0 が成り立つ。
」
3「ある実数 x に対して、x − x + 1 = 0 が成り立つ。
」
3「適当な実数 x を取れば、x − x + 1 = 0 が成り立つ。
」
このことを次のような式で表す。

∃x x ∈ R ∧ x3 − x + 1 = 0.
22

(この表現を推奨する。)

記号 ∃ は存在記号 (existential quantiﬁer) と呼ばれる。“exists” (「存在する」) の先頭の文
字 ‘E’ を裏返して作ったと言われている (鏡文字というやつ。プーさんに出て来る。)。

(豆知識) TEX では \exists と入力すると ∃ が出る。
E と書き間違える人が時々いる。日本人限定迷った時の思い出し方「∃ は片仮名のヨに似ている」。
次のように括弧をつけることが多い。

∃x (x ∈ R ∧ x3 − x + 1 = 0).
∃x [x ∈ R ∧ x3 − x + 1 = 0].


∃ まとめ



p(x) を x についての条件 (x を定めると p(x) が命題となる) とする。
“There exists x such that p(x) (holds)”, 「ある x が存在して、p(x) (が成り立つ, である)」, 「ある x に対して (について)、p(x) (が成り立つ, である)」, 「p(x) が成り立つような x が存在する」という命題を∃x p(x) あるいは ∃x(p(x)) あるいは ∃x [p(x)] あるいは ∃x s.t. p(x)
で表す。




上の例がそうであるように、数学で実際に現れる∃x p(x)の形の命題で、p(x) は多くの場合、p1 (x) ∧ p2 (x) という形をしていて、p1 (x) が x の考察の範囲 (例えば「x は実数である」, 「x ∈ R」など) を示している。そういうとき、∃x p1 (x) ∧ p2 (x)という命題を、「p1 (x) を満たす x で、p2 (x) が成り立つものが存在する」のように読むことがある (当然の前提 p1 (x) をそうでないものと分ける14 )。それに対応して(∃x : p1 (x)) p2 (x)のように書くことが多い。
上の例では(∃x : x ∈ R) x3 − x + 1 = 0となる。これをさらに(∃x ∈ R) x3 − x + 1 = 0と略記することが多い。「実数 x で x3 − x + 1 = 0 を満たすものが存在する」, 「ある実数 xが存在して、x3 − x + 1 = 0 が成り立つ」と読むとしっくりする。
同様に∃x (x > 0 ∧ x2 = 2)
を(∃x > 0) x2 = 2のように書くことが多い。
例えば上の例では、x ∈ R でないと x3 − x + 1 という式そのものがナンセンスということもあり、x ∈ R と
x − x + 1 = 0 が対等という感じはしないであろう。
14

3

23

注意 2.6 (s.t. について) ∃ を含む論理式で、∃ の直後に、しばしば “s.t. 〜” (「〜のような」,
such that の省略形) が使われる。例えば(∃x ∈ Q) x2 = 2を(∃x ∈ Q) s.t. x2 = 2と書く15 。英語を使う人は、“There exists x ∈ Q such that x2 = 2.” (「x2 = 2 が成り立つような x ∈ Q が存在する。」) と読むので、s.t. をつけるのがしっくり来るのであろう。s.t. はあってもなくても良い。この講義ではつけないことにする。
これについて一つ注意しておこう。「∃x ∈ Q s.t. x2 = 2」の否定命題を作るときなどに、
s.t. を残して∀x ∈ Q s.t. x2 ̸= 2とする人がたまにいるけれど、それははっきりと変である。(これは「すべての x ∈ Q に対して x2 ̸= 2 が成り立つ」と読む式で、「〜のような」とは読まない)。

2.4

複数の量称を含む命題 (工事中)

このところこの項の更新をサボっていたけれど、久しぶりに授業内容に近づけた (2022/8/23)。
まだ少し粗いところが残っている。

2.4.1

複数の変数を含む述語

2 つ以上の変数を含む述語 (条件) がある。
例 2.7 (2 変数 x, y についての述語) xy = x は、x と y に数を代入すると命題になる。
x = 0, y = 0 を代入すると 0 · 0 = 0 となり、真な命題である。
x = 1, y = 0 を代入すると 1 · 0 = 1 となり、偽な命題である。

2 変数 x, y を含む述語は、p(x, y) のように表せる。
2 変数 x, y を含む述語 p(x, y) に対して、∀yp(x, y) と ∃yp(x, y)は、どちらも x についての述語になる。
例 2.8

(4)

(∀y ∈ R) xy = x,(5)(∃y ∈ R) xy = x.

いずれも、変数 x についての述語である。例えば

15• (4) に x = 0 を代入すると (∀y ∈ R) 0 · y = 0

これは真な命題である。

• (4) に x = 1 を代入すると (∀y ∈ R) 1 · y = 1

これは偽な命題である。

• (5) に x = 0 を代入すると (∃y ∈ R) 0 · y = 0

これは真な命題である。

この命題は偽である。偽な命題を例にあげると、時々質問されたりするので、念のため。

24

• (5) に x = 1 を代入すると (∃y ∈ R) 1 · y = 1

これは真な命題である。

(∀y ∈ R) xy = x も、(∃y ∈ R) xy = x も、変数 x についての述語であるから、さらに ∀xあるいは ∃x をつけて命題となる、ということである。
2 つの変数を持つ述語については、∀x(∀y p(x, y)), ∃x(∀y p(x, y)), ∀x(∃y p(x, y)), ∃x(∀y p(x, y))という 4 つのパターンがあることになる。赤いカッコ ( ) は省略されることが多い。

2.4.2

複数の変数を含む述語の読み方式で書かれた複数の変数を含む述語をどう読むかを説明する。
まず量称が 2 つの場合を説明する。日本語の文を式に変換するときと異なり、式を日本語に直すやり方は色々ありうるが、私としては、次のように左から右に機械的に翻訳して読むことを勧める。

• ∀x ∀y p(x, y) 「任意の x と任意の y に対して p(x, y) が成り立つ16 」、「任意の x, y に対して p(x, y) が成り立つ」 — 論理式の方も (∀x, y)p(x, y) と略記することがある。
• ∀x ∃y p(x, y)「任意の x に対して、ある y が存在して p(x, y) が成り立つ」• ∃x ∀y p(x, y)「ある x が存在して、任意の y に対して p(x, y) が成り立つ」• ∃x ∃y p(x, y) 「ある x とある y が存在して p(x, y) が成り立つ17 」、「ある x, y が存在
して p(x, y) が成り立つ」 — 論理式の方も (∃x, y)p(x, y) と略記することがある。
要点は、左から右に順に式をたどり、∀ ○ があれば「任意の◯に対して」、∃ □ があれば「ある□が存在して」と機械的に読み下し、順番は決して入れ換えないことである。
このやり方は、英語では特に問題が生じないが、日本語では出来た文が不自然なものになりがちである。そのため、日本語として自然な文になるように工夫を試みる人がいるが、意味が曖昧な文になってしまったり、かえって読みにくくなったりするので、私としては、「機械的翻訳方針」をお勧めする。特に量称の個数が多い場合 (量称が 5 個以上ある論理式もごく普通に登場する)、読み方の工夫は手詰まりになりやすい。
以上、結論を天下りに述べたが、実例を題材にして説明しよう。まず次の 2 つの命題

(6)(∀x ∈ R)(∃y ∈ R) x < y,(7)(∃y ∈ R)(∀x ∈ R) x < yを考えてみよう。
機械的翻訳方針で読むと、それぞれ次のようになる。

(6a)「任意の実数 x に対して、ある実数 y が存在して x < y が成立する。
」(7a)「ある実数 y が存在して、任意の実数 x に対して x < y が成立する。
」(6a) は、どんな実数に対しても、それより大きい実数がある、ということで、これは真な命
題である (証明の書き方は後述する)。
16「任意の x に対して，任意の y に対して p(x, y) が成り立つ」と言っても間違いではないと思うが、そうする人は少ないようで、少し短くするのが普通のようである。
17「ある x が存在して、ある y が存在して p(x, y) が成り立つ」と言っても間違いではないと思うが、そうする人は少ないようで、少し短くするのが普通のようである。

25

一方、(6b) は、どんな実数よりも大きいような (チャンピオンの？) 実数があるという意味
で、これは偽な命題である。
「ある○○が存在して〜」という表現を嫌って、「〜となるような○○が存在する」を使おうとして、(6), (7) を次のように読む人もいる。

(6b)「任意の実数 x に対して、x < y が成り立つような実数 y が存在する。
」(7b)「任意の実数 x に対して x < y が成り立つような実数 y が存在する。
」

個人的な意見ということになるかもしれないが、(6b) と (7b) はとても紛らわしいと思う。
読点「、」を見落とさなければ大丈夫 (区別できる) という意見もあるけれど、それは聴いただ
けでは分からない。
機械的な翻訳方針を採用して、(6a) と (7a) のように読むことを勧める。
例 2.9 (∀x ∈ R) (∃y ∈ R) x > y「任意の実数 x に対して、ある実数 y が存在して x > y が成り立つ。
」
これは真な命題である。どんな x に対しても y = x − 1 とすれば…証明の書き方は後述する。
例 2.10 (∃y ∈ R) (∀x ∈ N) x > y「ある実数 y が存在して、任意の自然数 x に対して x > y が成り立つ。
」
これも真な命題である。y = −1 とすれば…
例 2.11 (∀ が連続する場合)(∀x ∈ R)(∀y ∈ R) x2 + y 2 ≥ 2xy
機械的に読むと「任意の実数 x に対して、任意の実数 y に対して x2 +y 2 ≥ 2xy.」となるが、日本語としてやや不自然な感じがする。普通は「任意の実数 x, 任意の実数 y に対して x2 +y 2 ≥ 2xy.」
あるいは「任意の実数 x, y に対して x2 + y 2 ≥ 2xy.」と読む。
例 2.12 (∃ が連続する場合) (∃x ∈ N) (∃y ∈ N) x2 + y 2 = 25.
「ある自然数 x, y が存在して x2 + y 2 = 25.」と読む。

3 つ以上の変数を持つ述語に対しても同様である。
例 2.13 (3 変数の場合、ピタゴラス数) 3 つでも同様で∃x∃y∃z(x ∈ N ∧ y ∈ N ∧ z ∈ N ∧ x2 + y 2 = z 2 )を次のように書く。

(∃x ∈ N)(∃y ∈ N)(∃z ∈ N) x2 + y 2 = z 2「ある自然数 x, y, z が存在して x2 + y 2 = z 2 」
この命題は真である。x = 3, y = 4, z = 5 とすると条件を満たす。
付帯条件がある量称の場合も同様である。 —- これはどこに入れよう？

26

例 2.14 (連続関数の定義) 関数 f が点 a で連続であるとは、条件「任意の正の数 ε に対して、十分小さな正の数 δ が存在して、|x − a| < δ を満たすすべての x に対して、|f (x) − f (a)| < ε」
が成り立つことと定義する。この (f と a に関する) 条件は(∀ε > 0)(∃δ > 0)(∀x : |x − a| < δ) |f (x) − f (a)| < εと書ける。 元々の流儀 (付帯条件を使わない) で書くのは、かなり面倒でわかりづらくなる(興味ある人は試してみるとよい)。
以下は雑談である。論理式の読み方をどうするかという問題は、初めて学んだときからずっと抱えているが、現時点での個人的な結論は次のようになっている。

• 機械的に翻訳し、それを読むことに慣れるのが、結局はコストが一番低い。
• 複雑な論理式は、無理に日本語に直さない。どうしても日本語に直す場合は、新しく言葉や記号を定義してそれを用いることで、短い論理式に書き直した上で、日本語に翻訳する。
この問題は、英語と日本語の違いに起因している面があるような気もする (英語ならば関係代名詞を使うと、式に書いた順を守った文が自然に出来る)。

2.4.3

量称記号の順序

量称記号の順序を交換するとどうなるだろうか。∀ 同士、∃ 同士は交換しても同値である。
すなわち(1) (∀x) (∀y) P (x, y) ≡ (∀y) (∀x) P (x, y)(2) (∃x) (∃y) P (x, y) ≡ (∃y) (∃x) P (x, y)∀ と ∃ を交換すると同値とは限らない。例えば (∃x) (∀y) P (x, y) が真ならば、(∀y) (∃x)
P (x, y) も真であるが、(∀y) (∃x) P (x, y) が真であっても、(∃x) (∀y) P (x, y) が真とは限らない。
例 2.15 「どんな数に対しても、それより大きな数がある」は(∀x ∈ R)(∃y ∈ R) y > xと表され、真な命題であるが、量称を入れ替えた(∃y ∈ R)(∀x ∈ R) y > x
は「どんな数よりも大きい数 (チャンピオンの数) がある」という強い意味になり、(そんなことはありえないので) 偽な命題である。


重要



∀ 同士、あるいは ∃ 同士は、順番を入れ換えても式の意味 (内容) は変わらないが、∀ と∃ の順番は入れ換えると意味が変わってしまう。
(§2.6 で見るように) 一般に “∃y∀xP (x) ⇒ ∀x∃yP (x, y)” が成り立つから、∃ が先に現れる方が強い主張である。




27

例 2.16 (じゃんけん) 3 点からなる集合 J = { ぐう, ちょき, ぱあ } に、次のような 2 項関係≻ を導入する。
ぐう ≻ ちょき, ちょき ≻ ぱあ, ぱあ ≻ ぐう
これ以外の場合は、≻ は不成立とする (要するに「じゃんけん」の勝ち負けの判定)。例えば、
ぱあ ̸≻ ちょき. こうすると、(∀t ∈ J)(∃k ∈ J) k ≻ t(どんな手 t に対しても、それに勝つ手 k がある) は真であるが、(∃k ∈ J)(∀t ∈ J) k ≻ t(どんな手 t に対しても勝ってしまう “必勝手” k がある) は偽である。
ア ル キ メ デ ス

例 2.17 (Archimedes の公理) 2 つの正の実数 a, b を取ったとき (b がどんなに大きくても、
あるいは a がどんなに小さくても)、a を十分たくさん足してやれば b を追い抜く。

(∀a > 0)(∀b > 0)(∃n ∈ N) na > b.
これは公理というくらいで、真な命題であるが18 、(∀b > 0) と (∃n ∈ N) を入れ替えた(∀a > 0)(∃n ∈ N)(∀b > 0) na > bは偽である。
次の例は有名かつ重要である (残念ながら 1 年生の 5 月頃に持ち出す例としてはフライング
気味かもしれない)。
例 2.18 (連続性と一様連続性) I を R の区間、f : I → R を写像とする。f が I で連続であるということを論理記号で書くと(∀x ∈ I)(∀ε > 0)(∃δ > 0)(∀y ∈ I : |x − y| < δ) |f (x) − f (y)| < εとなる。また、f が I で一様連続であるということを、論理記号で書くと(∀ε > 0)(∃δ > 0)(∀x ∈ I)(∀y ∈ I : |x − y| < δ) |f (x) − f (y)| < εとなる。
連続性と一様連続性は異なる概念であるが、それが ∀, ∃ の順番の違いだけで表されている。

2.5

量称を含む命題の証明「次の命題を証明せよ」に対してフリーズする前に、ダメもとでやってみるべきことがある。それを 2 つ紹介する。
どんな (正しい) 命題も証明出来るような万能の方法はないが (そういうものがあれば、数学者は苦労しないのだけど)、ぜひ試すべきことがある (ほぼ繰り返しで、くどいかな)。


その 1



命題 (∀x: P1 (x)) P2 (x) を証明するには、まず「x は P1 (x) を満たす任意のモノとする」という意味のことをとにかく書いてしまう。それから P2 (x) であることが証明できないか
考えてみる。


18

実数全体の集合を構成する議論を行う場合は、証明可能な命題 (定理) となるが、それをさぼって、実数全体の集合が持ついくつかの性質を公理として認めて議論を始める立場では、公理とする必要がある (他の公理からは導かれない) ことのある命題である。

28

例 2.19(∀x ∈ R) x2 ≥ 0(8)を証明しようとする場合、まず「x を任意の実数とする」と書いてしまう。それから x2 ≥ 0
を導くことを目標として考える。
(証明) x を (任意の) 実数とする。x > 0, x = 0, x < 0 のいずれかが成り立つ。
x > 0 の場合、x2 = x · x > 0 (2 つの正の数の積は正).
x = 0 の場合、x2 = 02 = 0.
x < 0 の場合、−x > 0 であるから、x2 = (−x)2 > 0 (2 つの正の数の積は正).
いずれの場合も x2 ≥ 0 であるから、(8) が証明出来た。
注意 2.20 (「任意の」を書くのをサボるかサボらないか) 普通の数学書の証明では、「任意の」を省いて「x を実数とする」とだけ書いてあることが多い。他に何も書いていなければ、それ以外の条件は一切課さないという意味で「任意」であることが明らかである、ということであろう。特に上の証明では、証明の文章の先頭に書いてあるので、x がそこで初めて導入されたものであることがわかりやすい。そのため「任意の」がなくても誤解が生じる可能性はないであろう。
逆に言うと、文章の途中では、「任意の」を書いておいた方が、誤解が生じにくくて良い面がある。「任意の x」という表現は、x を導入する時にしか使えない表現であるので、それが書いてあると、x がすでに導入済みであるか調べるために文章をさかのぼって読み返す必要がなくなる (これは「ある x が存在して」についても同様である) 。
この講義では「任意の」を省略しないことにする。


その 2



命題 (∃x: P1 (x)) P2 (x) は、(∃x) P1 (x) ∧ P2 (x) という意味である。そこで P1 (x) と P2 (x)を同時に満たすような x を探す。もしも実際に見つけることができれば、それで証明はほぼ完了する。


例 2.21(∃x ∈ R) x2 − 3x + 2 = 0.

(9)(計算用紙に x2 − 3x + 2 = (x − 1)(x − 2) とか書いて、方程式の解が 1, 2 であることが分かれば、以下のような解答が書ける。)(証明) x = 1 とすると、x ∈ R, かつ
x2 − 3x + 2 = 12 − 3 · 1 + 2 = 1 − 3 + 2 = 0.
ゆえに (9) が成り立つ。
例 2.22(10)(∀x ∈ Z)(∃y ∈ Z) x + y = 0.

(証明) x を任意の整数とする。そのとき y = −x とおくと、y ∈ Z であり、
x + y = x + (−x) = 0.
ゆえに (10) が証明出来た。

29

例 2.23(∃x ∈ Z)(∀y ∈ Z) x + y = y.

(11)

先頭が ∃x であるから、x を具体的に見つけられれば良い。
「(∀y ∈ Z) x + y = y 」を満たすような整数 x というのが分かるだろうか。
(証明) x = 0 とすると、x ∈ Z であり、かつ任意の y ∈ Z に対して、

x + y = 0 + y = y.
ゆえに (11) が証明出来た。
もちろん、いつもそういう単純な話で済むわけでない。
例 2.24(∃x ∈ R) x3 − x + 1 = 0.

(12)

この方程式は具体的に解けないこともないが、少し難しい19 。

3

2

1

-2

1

-1

2

-1

-2

図 2: f (x) = x3 − x + 1 のグラフ

(証明) 関数 f : R → R を f (x) := x3 − x + 1 で定めると、f (x) は x の多項式であるから、fは連続関数で、
f (0) = 1 > 0, f (−2) = −8 − (−2) + 1 = −5 < 0.
中間値の定理により、ある x ∈ (−2, 0) が存在して f (x) = 0. このとき x は実数で x3 −x+1 = 0.
(ゆえに (12) が証明出来た。)

q √q
Cardano の公式を使うと、x = − 3 3 9−2√69 − 3 9−18 69 が実数解と分かる。これが x3 − x + 1 = 0 を満た()
すことの確認も一目ではわかりづらい。
19

30

2.6

量称と論理の法則、特に否定命題



定理 2.25 以下の公式 (1)〜(7) が (任意の述語 P (x), Q(x) について ) 成り立つ。

(1) ¬(∀xP (x)) ≡ (∃x)(¬P (x)).
(2) ¬(∃xP (x)) ≡ (∀x)(¬P (x)).
(3) ∀x(P (x) ∧ Q(x)) ≡ (∀xP (x)) ∧ (∀xQ(x)).
(4) ∃x(P (x) ∨ Q(x)) ≡ (∃xP (x)) ∨ (∃xQ(x)).
(5) ∀x∀yP (x, y) ≡ ∀y∀xP (x, y).
(6) ∃x∃yP (x, y) ≡ ∃y∃xP (x, y).
(7) ∃y∀xP (x, y) ⇒ ∀x∃yP (x, y).



注意 2.26 (反例) 最初の公式は、「任意の x に対して P (x) が成り立つ」の否定は「P (x) が成り立たないような x が存在する」ということで、高校数学で学んだ「反例」という言葉を思い出す人もいるであろう。∀x P (x) という形をしている命題に対して、反例というのは ¬P (x)を満たす具体的な x のことを指す。そういう x が発見できたとき、(∃x) ¬P (x) は真である。
つまり、反例を見つけることで否定命題を証明し、もとの命題が偽であることが証明できた、ということである。
注意 2.27 (3) で ∧ の代わりに ∨ としたもの∀x(P (x) ∨ Q(x)) ≡ (∀x P (x)) ∨ (∀x Q(x))(この式は正しくない)は成り立たない。例えば P (x) を「x が偶数である」, Q(x) を「x が奇数である」とするとき、左辺は真であるが、右辺は偽である。
また (4) で ∨ の代わりに ∧ としたもの∃x(P (x) ∧ Q(x)) ≡ (∃x P (x)) ∧ (∃x Q(x))(この式は正しくない)も成り立たない。
注意 2.28 (7) だけ ≡ でなく、⇒ であることに注意しよう。一言でまとめると ∀ 同士、∃ 同
士は順序を入れ換えてもよいが、∀ と ∃ を入れ換えることはできない (意味が変わってしまう)。
付帯条件付きの量称 (∀x : A(x)), (∃x : A(x)) に対しても、上と同様の公式が成り立つ。

31





系 2.29 (1) ¬(∃x : A(x))P (x) ≡ (∀x : A(x))(¬P (x)).

(2) ¬(∀x : A(x))P (x) ≡ (∃x : A(x))(¬P (x)).
(3) (∀x : A(x))(P (x) ∧ Q(x)) ≡ (∀x : A(x))P (x) ∧ (∀x : A(x))Q(x).
(4) (∃x : A(x))(P (x) ∨ Q(x)) ≡ (∃x : A(x))P (x) ∨ (∃x : A(x))Q(x).
(5) (∃x : A(x))(∃y : B(y))P (x, y) ≡ (∃y : B(y))(∃x : A(x))P (x, y).
(6) (∀x : A(x))(∀y : B(y))P (x, y) ≡ (∀y : B(y))(∀x : A(x))P (x, y).
(7) (∃y : B(y))(∀x : A(x))P (x, y) ⇒ (∀x : A(x))(∃y : B(y))P (x, y).



証明

最初の二つを確認する。

¬ ((∀x : A(x))P (x)) ≡ ¬ (∀xA(x) ⇒ P (x)) ≡ ¬ (∀x(¬A(x) ∨ P (x)))≡ ∃x¬(¬A(x) ∨ P (x)) ≡ ∃x (A(x) ∧ ¬P (x))≡ (∃x : A(x))¬P (x),¬ ((∃x : A(x))P (x)) ≡ ¬ (∃xA(x) ∧ P (x)) ≡ ∀x¬(A(x) ∧ P (x))≡ ∀x¬A(x) ∨ ¬P (x) ≡ ∀xA(x) ⇒ ¬P (x)≡ (∀x : A(x))¬P (x).
他も同様に証明できる。

32



付録
A

結合の優先順位

複数の論理記号が含まれる式を書くとき、結合の順番を表すためにカッコ ( ) を用いる。
例えば、p ∧ (q ∨ r) と (p ∧ q) ∨ r から括弧を取って p ∧ q ∨ r としてしまうと、意味が分からなくなる。
数の演算でそうしたように、論理式についても、カッコを減らすために、演算に優先順位を設けて、カッコを適度に省略する。以下の 1〜5 では、小さい番号の演算の優先順位が高い。

1. =, ∈
2. ¬, ∀x, ∃x
3. ∧, ∨
4. ⇒5. ⇔(⇒ と ⇔ の優先順位は同じ、という人もいる。)
例えば(p ⇒ q) ⇔ ((¬p) ∨ q)
はp ⇒ q ⇔ ¬p ∨ qと書くことが出来る。
上のルールにおいても、∧ と ∨ は同じ優先順位なので、∧ と ∨ が混じる式では、やはりカッコ () をつけることが必須であることを注意する必要がある。(∧ を論理積、∨ を論理と呼ぶせいか、数の演算との類推から ∧ を優先して、(p ∧ q) ∨ r を p ∧ q ∨ r と書ける、と誤解している人が多いような気がするが、そうではない。)

B

トートロジー

命題 P , Q, · · · を命題結合記号 (∨, ∧, ¬, ⇒, ⇔) を使って組み合わせた命題で、P , Q, · · ·がいかなる命題であっても、つねに真であるようなものを、トートロジー (tautology) または恒真命題と呼ぶ。
例として、P ∨ (¬P )
三段論法

(13)

((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)

構成的仮言的三段論法(14)(P ∧ (P ⇒ Q)) ⇒ Q(15)((P ⇒ R) ∧ (Q ⇒ R)) ⇒ ((P ∨ Q) ⇒ R)
33

C

ユークリッドの原論 — 証明の起源

命題が真であることを論理的に示すことを「証明する (to prove)」という。またその論述を証明 (proof) と呼ぶ。
証明は、ギリシャ数学に起源があるとされている。「ヒポクラテスの三日月」で知られているキオスのヒポクラテス (B.C. 450–420) が証明の発明者であるという説が有力らしい (斎藤[10])。まとまった形で残っているものとしては、何と言っても「ユークリッド原論」[8] が有名である。
「ユークリッド原論」は、アレキサンドリアのエウクレイデス (Eυκλειδης, B. C. 3 世紀頃,
英語読みでは Euclid ユークリッド) が著したストケイア (Στ oιχεια, 英語では Elements, 日本
語では「原論」) という書物である。その当時まで得られていた数学の多く20 を集成したもの。
古い話のようだけれど、現代の数学の直接の祖先であり、現代の数学の骨格を決めているよ
うなところがある。そして学校数学 (高等学校までの数学) は、少なくとも見掛け上そうなっていないので、1 年生に話す価値 (もしかすると必要性かもしれない) は高い。
それに先立つ他の文化圏 (古代バビロニア、古代エジプト、古代中国、…) で証明が行われた形跡はなく、その後も再発見されたという話はないようである。(個々の事実は、歴史上何度も再発見されているのに、証明するという行為自体は再発見されなかった？)
原論は、全 13 巻からなる (平面図形, 面積の変形 (“幾何的代数”), 円の性質, 円に内接・外接す
る多角形, 比例論, 比例論の図形への応用, 数論 (3 巻), 無理量論, 立体図形, 面積・体積, 正多面体)。いくつかの定義 (23+2+11+7+18+4+22+0+0+(4+6+6)+29+0+0 = 132) と、5 (or9) つの公理、5 つの公準から、465 (= 48+14+37+16+25+33+39+27+36+115+39+18+18)
個の命題を証明した。
さすがに現代の観点からは、証明に色々な不備が認められるが、掲げられた命題自体に間違いはないと言われている。これは非常に驚くべきことである。

9 つの公理 (準備中)
5 つの公準 (準備中)
QED のルーツ 今でも証明の終わりに QED と書くことがあるが、これは原論のラテン語訳
で命題の証明の最後に書かれている “quod erat demonstrandum” (もとのギリシャ語ではπερ δει δεῖξαι. 英語で言うと “which had to be deomonstrated”, 「これが証明すべきことであった」という意味) の省略形である。

D

基本的な用語・言葉遣い

D.1

議論の中での記号の定義

1 つの数学的対象を、文字や文字を組み合わせたもの等の 1 つの記号で表すことが良く行われる。
「p を命題とする。」「x を任意の実数とする。」「A, B を集合とするとき、…」20

例えば、円錐曲線論は、ほかならぬエウクレイデスの著作があったらしいが、これは原論には含まれておらず、現在では残っていない (後から現れたアポロニオスの円錐曲線論に取って代わられたと言われている)。

34

特にこれまでの議論に現れた対象を用いた式で新しい対象を定義して、それを一つの記号で表すとき、「記号 = 式 とおく」または「記号 = 式 とする」と書く。例えば x, y が既に定義済みであるとして、「z = (x + y)2 とおく」のように書いたりする。
「a と b が等しい」という命題は、a = b と書いても b = a と書いても、どちらでも同じことだが、この定義の場合は z = (x + y)2 の方が普通で、(x + y)2 = z とは書くことは少ない。
日本語では、「z で (x + y)2 を表すことにする」よりは「(x + y)2 を z で表す」のが自然そうなので、ともすると「(x + y)2 = z とおく」(一般化すると「式 = 記号」) と書きそうになるが、それは普通でないとされる。英語では、例えば “Let z be (x + y)2 ” という表現になる
ので、z が先、(x + y)2 が後、というのを自然に感じるらしい。
(脱線になるが、BASIC というプログラミング言語では、A に B を代入する命令文を LET
A=B と書く。言語を作った人の頭の中で “Let A equal B” とか、“Let A be B” となっているのだろう。)
定義をするための等号は、単なる等式を構成するための等号とは異なると考えるべきかも知
def.
def.
れない。しばしば z = (x + y)2 のように = を使うことがある。それ以外に z := (x + y)2 という書き方もある (そういえば、Pascal のような ALGOL の子孫であるプログラミング言語
では、代入文は a:=b と書くのであった)。:= は右辺の式の表すものを左辺の記号で表すという意味を含んでいる。
しばしば (x + y)2 =: z という書き方も目にすることがある。(x + y)2 と z の語順が「普通」と逆になっているが、=: のせいで、左辺が式で、右辺が記号ということが明瞭である。

D.2

公理とは

公理とは何か。重要な用語なので国語辞典にも載っていて、多くは次の二つの意味が載っている (ここでは広辞苑から引用した) 。

(a) 証明不可能であるとともに、また証明を必要とせず直接に自明の真として承認され他の命題の前提となる根本命題。
(b) ある理論領域で仮定される基本前提。この場合、公理は自明な真理ではなく、公理系のとり方によって定まる。従ってある公理系で公理である命題も、他の公理系においては公理から証明される定理となることや、また偽となることがある。
ユークリッド原論における公理 (axiom, common notion) と、公準 (postulate) は (a) の意
味での公理である。Euclid 原論の公理は相等関係が満たすべきルールなどのいわゆる推論のための規則で、公準が幾何学のための「自明の真として承認される命題」である。

35

授業の進行E(ここは最近の事情に合わせて更新すべきである…ここ数年、論理の説明に授業 5 回近くの時間がかかっている。量称を含む命題の証明の仕方の説明など、内容的に増えているということもある。)
どういうペースで講義するかの参考にするため。
第 1 回 30〜40 分程度のガイダンスを行う (それはこの文書とは別の資料に基づく)。§1.3 か§1.4 まで進める。初回なので宿題はなし。
第 2 回 前回の続きから始め、§1.6, §1.7 が主な内容となる。宿題を出す (内容は真理値表による証明、もしかすると同値変形による証明も)。
第 3 回 宿題の解説。§1.8 あたりが残っている。続いて第 2 節「述語論理」に入る。§2.2, §2.3
を終わらせたい。宿題は量称を含む命題の翻訳 (文 ⇔ 式)。
第 4 回 宿題の解説。§2.4, §2.5, §2.6 結構ずっしり。(以前は「空集合の論理」という話をしていたが、今は集合について述べる Part II で話をする。) 宿題は、複数の量称を含む命
題、量称を含む命題の証明。後者は 1 回ではマスター出来ない人が多いが、まずは最初のトライアル。

解答F

解答 1. 真理値表は

p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

r
T
F
T
F
T
F
T
F

q∧r
T
F
F
F
T
F
F
F

p ∨ (q ∧ r)
T
T
T
T
T
F
F
F

p∨q
T
T
T
T
T
T
F
F

p∨r
T
T
T
T
T
F
T
F

(p ∨ q) ∧ (p ∨ r)
T
T
T
T
T
F
F
F

となる。5 列目と 8 列目の真理値が一致するので、(♡) が成り立つ。
解答 2. (これは自分でやってみよう。授業でどちらか一方を見せるはずであるから、その真似をしてもう一方を自分でやってみる、のが標準的な授業進行である。)
解答 3. 真理値表は

p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

r
T
F
T
F
T
F
T
F

p⇒q
T
T
F
F
T
T
T
T

q⇒r
T
F
T
T
T
F
T
T

p⇒r
T
F
T
F
T
T
T
T

(p ⇒ q) ∧ (q ⇒ r)
T
F
F
F
T
F
T
T
36

((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)
T
T
T
T
T
T
T
T

となる。真理値がつねに T であるから、((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r) はトートロジーである。
解答 4. (1) 最初に確認しておく。すでにp ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

(16)という分配律は述べてあり、交換律と同値変形により(p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r)(17)が成り立つことも分かっている。r ∨ s を M とおくと、(p ∨ q) ∧ (r ∨ s) ≡ (p ∨ q) ∧ M≡ (p ∧ M ) ∨ (q ∧ M )≡ (p ∧ (r ∨ s)) ∨ (q ∧ (r ∨ s))≡ ((p ∧ r) ∨ (p ∧ s)) ∨ ((q ∧ r) ∨ (q ∧ s))≡ (p ∧ r) ∨ (p ∧ s) ∨ (q ∧ r) ∨ (q ∧ s).
解答 5.

p q ¬p (¬p) ∨ q
T T F
T
T F F
F
F T T
T
F F T
T
((¬p) ∨ q の真理値表)
解答 6. 同値変形によって証明する。p ⇒ q ≡ (¬p) ∨ q の p, q に、それぞれ ¬q, ¬p を代入すると(¬q) ⇒ (¬p) ≡ (¬(¬q)) ∨ (¬p)
≡ q ∨ (¬p)
≡ (¬p) ∨ q≡ p ⇒ q.
ゆえに p ⇒ q ≡ (¬q) ⇒ (¬p).

参考文献[1] 中島匠一：集合・写像・論理 — 数学の基本を学ぶ, 共立出版 (2012/2/27).
[2] 中内伸光：ろんりの練習帳, 共立出版 (2002).
[3] 新井紀子：数学は言葉 — math stories, 東京図書 (2009), 数理論理の専門家によって書かれた本であり、 とても参考になる。
[4] 金子晃：数学基礎論講義 — 論理・集合・位相 —, サイエンス社 (2010/6/10).
37

[5] 結城浩：数学文章作法 基礎編, ちくま学芸文庫, 筑摩書房 (2013).
[6] 島内剛一：数学の基礎, 日本評論社 (1971).
[7] 前原昭二：数理論理学序説, 共立出版 (1966, 2010).
[8] ユークリッド：ユークリッド原論, 共立出版 (1971, 2011/5/25 (追補版)), 中村幸四郎, 寺
阪英孝, 伊藤俊太郎, 池田美恵 訳・解説.
[9] 小松 勇作編：数学 英和・和英辞典 増補版, 共立出版 (1979/7/16, 2016/2/25), 丸善 eBookに入っている。明治大学の学生は https://elib.maruzen.co.jp/elib/html/Viewer/
Id/3000033529 で閲覧できる。
[10] 斎藤憲：キオスのヒポクラテスと論証数学の発明, 第 17 回ギリシャ哲学セミナー講演,
http://greek-philosophy.org/ja/files/2013/03/Saito2013.pdf — こういうものを公開していただけるのはとてもありがたい (2013).

38

索引
conjunction, 7
corollary, 5
disjunction, 8

対偶, 18定理, 5でない, 6

negation, 6

トートロジー, 12
同値, 10
同値変形, 14
ド・モルガンの法則, 11

proposition, 4, 5

ならば, 17

quantiﬁer, 20

排他的論理和, 8
排中律, 6, 10
背理法, 7
反射律, 10existential quantiﬁer, 23
lemma, 5tautology, 12
truth value, 5
universal quantiﬁer, 20
裏, 18
かつ, 7
偽, 5
逆, 18
吸収律, 10系, 5結合律, 10
限定記号, 20
交換律, 10
恒真式, 12
十分条件, 18
述語, 19条件, 19証明, 5証明する, 5
真, 5
真理値, 5
真理値表, 7

必要十分条件, 19
必要条件, 18
否定, 6
ブール束, 11
分配律, 10冪等律, 11
補題, 5
または, 8矛盾, 6
無矛盾律, 6, 10
命題, 4
命題関数, 19
量称記号, 20
連言, 7
論理積, 7
論理和, 8

選言, 8
全称記号, 20
全称命題, 20束, 11
存在記号, 2339