2

集合と論理2007


  1. このページを御覧になるかたへ
  2. 参考(.ps .pdfファイルの開き方参考資料)
  3. オンラインレポートシステムについて質問について
  4. この講義について(目的・履修関係・内容など)
  5. Q&A
  6. 講義


このページを御覧になる方へ  
これは京都産業大学理学部コンピュータ科学科の講義資料です。
どなたでも自由に御覧いただいて参考にしていただいてけっこうですが、
あくまでもご自身の勉強または教育の参考に限ってください。
また、.ps file, /pdf file を含めて、このページの内容を出典を明記せずに
転記、利用などはしないでください。
著作権はこのページの作者にあります。


参考    
以下に参考になるページや
ファイルをリストしておきます。
ページのtopへ戻る
 
.psファイル、.pdfファイルの開き方  

Linuxでは.psファイル、 Windowsでは.pdfファイルが開くと思います。

 
参考ページ・
ファイル
 
ページのtopへ戻る


オンラインレポートシステムについて

授業登録が完了したころか ら、 いろいろな連絡や
課題提出をMoodleで行います。 後で詳しく説明しますが、
Moodleへの行き方だけ説明しておきます。
大学のHP─>「在学生と教職員の方へ」─>「教育システムMoodle」
そこで自分のユーザー名とパスワードを入力してログイン。
オンラインマニュアルがあるので読んでください。
直接Moodleに入りたいときは次のURLを入力してください。
https://ccwbt.kyoto-su.ac.jp/login/index.php

質問について

講義の間の質問は歓迎です。 講義の直後は私の時間はあいているので、皆さんの時間があれば 教室で質問してください。 時間がないときには、紙に 質問を書いて渡してくださ い。 次の講義のときに解 答します。
学科のブレークタイムでも質問できます。予定表を見て、きてください。
ブレークタイムでは皆さんと先生方が気楽に話ができます。
とくに用事がなくても遊びにきてください。

ページのtopへ戻る

この講義について
講義目的(要旨)

コンピュータは概念と論理の機械であるからコンピュータを理解するには 基本的な数学の知識が必要である。この講義は、情報系の分野を学ぶための論理数学基礎コースである。 内容としては 集合・写像・関係、命題論理などの初歩の概説である。集合・写像・関係は、特に 言葉と表記法に重点をおく。プログラム理論の理解のための第一歩である。命題論理は、ソフトウェア 科学の基礎となる。

授業内容・授業計画

�論理:文の記号化、命題 論理式、式の真理値、結合子の相互関係、恒真性。
�集合:集合も記法、部分集合、演算、直積、写像の定義、いろいろな写像、 写像のグラフ、関係の定義、関係と部分集合、同値関係、順序関係、辞書式順序、整礎関係。
 以上のトピックスを、一回ごとに区切って講義する。場合によっては、二つのトピックを一回で終了する。

履修上の注意

テキストを丁寧に復習すること。特に例題の理解が大切である。 各トピックが新しい概念を導入するので、そのつど理解しておくこと。

授業の到達目標

集合,命題などの表記法に慣れる。整礎関係など,新しい概念を理解する。 集合演算,命題論理の計算をマスターする。

評価方法

学期中の課題提出、および期末テストの総合点。

教科書:「情報系の数学入門」 林・八杉著 オーム社
まず第3章、次に1章。 残りの章や節も後で役にたつので教科書を保存しておくこと。

ページのtopへ戻る

Q&A

Q1:なぜ集合と論理が必要なの?


A1:論理は人がものごとを正確に考えるときの筋道です。それを整理して 互いに論理について話ができるようにしたものが、論理学です。 論理は数学や計算機科学、法律、日常生活、など、どんな場面でも 使っていますが、とくに記号などをきちんときめた記号論理学が必要なのは プログラミングおよびプログラム自体を研究する計算機科学あるいはプログラミングの科学です。 プログラムの書き方は論理にしたがっているものであり、プログラミング言語 にはたいてい論理演算が組み込まれています。 しかし論理学をもっと本質的に使う場面として、まず仕様記述があります。l どんな仕事をするプログラムを作成してほしいか、ということを厳密に書くには 文章の論理的な構造を正確に表さなくてはなりません。そのために記号論理学 が必要です。形式的仕様記述言語Zというのが開発されていて、実用化されています。 私の研究室での卒業研究でもZの応用をすることがあります。専門科目の 「論理とプログラム」でもZをとりあげます。さらに書いたプログラムが目的にあって いるか、というプログラム自体を科学するためにも論理は必要です。 また、皆さんは驚くかもしれませんが、数学の証明を論理を使ってきちんと書いておくと、 その証明から自動的にプログラムを引き出すことができます。 「うーん、プログラムを書くより数学の証明のほうが難しいや」というかもしれませんね。 でもときには証明は1ページくらいで済むけれど、自分でプログラムを書こうとすると膨大になるかもしれません。 そんなときには証明を書いておくほうが安全なのです。 とりあえずここでは一番基礎になる「命題論理」を学びます。 では集合はなぜ必要なの?集合といってもいろいろあって、ここでは集合の 演算と記法に重点をおきます。集合の演算はなにをするにも基本ですが、実は 論理と密接な関係があります。また仕様記述には集合の記法が一番基本なのです。 と、いうわけで、将来への投資だと思って、「集合と論理」を学んでください。

Q2:なぜ10 号館で、ウェブを使っての授業なのか?
    コンピュータで見るのは、かったるい。紙に印刷して配ってほしい。
  (2002年度授業評価アンケートの意見)


A2: 過去年度の授業評価のアンケートにこのような意見がありました。 その答えはこういうことです。以前は黒板で板書して、補足は紙に印刷して 渡していました。その問題点は、私の字が下手で読みにくいこと、 学生さんが筆記に忙しく、話を聞けないこと、板書が速過ぎる、と 苦情が出ること、などで、講義の能率が悪く、効果があがりにくい ということがありました。また、プリントをいつも持ってこなかったり 失くしてしまったり、で、役にたたないことが多かったのです。 ウェブの内容をプリントしたら、膨大な紙の量になります。 紙は教科書一冊で十分です。 基本はあくまでも教科書です。このページはサービスなのです。 ウェブに補足や進み具合などをおいておけば、ちょっと時間が あいたときにいつでも見れるし、プリントを失くす心配もしなくてすみます。 板書や筆記に時間をとられないので、皆さんの間をまわって個人的に 質問を受けるゆとりもできました。 モニタで私が内容を見せるだけでなく、各人が計算機を操作できれば 授業中に各人のペースで練習問題をしたり、例題を読むこともできます。 また、一昨年度からは、ウェブによる課題提出システムが使えるので 毎回かんたんな課題をその場で提出してもらうこともできます。

以上の理由により、私はこの講義形態を続けるつもりです。 皆さんもこの主旨を理解して、お互いに得るところが多いように 協力してください。
ただし、ノートは必ず持参してください。
コメントをメモしたり、 練習問題を解いたりするのに必要です。
また、学期の途中でも、講義やこのページについて意見や助言が あれば、指摘してください。 良い授業は皆さんと私の共同作業でできるのです。 できるだけ楽しく勉強しましょう。

Q3:大学とい うところは、できない学生は置いていかれるのか?
  (2003年度授業評価アンケートの意見)


A3: そんなことはありません。この科目に限らず先生たちは皆さんの質問に答える
用意はいつでもあります。上にも書いたようにいろいろな方法で質問できます。
私は授業中に演習の時間を多くとり、その間に質問を受けにまわっていきます。
このページも、教科書を補い、たくさん練習問題ができるための工夫です。
例題や練習問題をまず自分で考えて、それでわからないときには遠慮なく
質問してください。課題を何回も出すのも、課題を解こうとすると、自分が
何がわかって何がわからないか、が明らかになるので勉強しやすいから
なのです。私たちは教えることはできます。でも勉強するのは皆さん
各自なのです。手を動かし頭を使ってください。それは私が代って
あげられません。

Moodleに課題の解答を書く方法は後で!

ページのtopへ戻る


講義目次

講義本論4月10日4月17日
4月24日5月1日5月8日
5月15日5月22日5月29日
6月5日6月12日6月19日
6月26日 7月3日 7月10日

ページのtopへ戻る


講義本論
ここから本論です。テキストに沿って講義をすすめます。基本はテキストなので 、必ず持って来てください。このページにあるのはすべて皆さんの学習のための補足 です。テキストでしっかり話の筋道を理解してください。

この講義では、論理や集合で使う、概念の定義、記法、例題、を重視します。 このページには多くの例題や演習問題(かんたんな解答つき)があります。 自分で解いてみてください。私の解答にまちがいがあれば、教えてください。 なお、記号の書き方について、論理結合子を書くのは大変なので、 書きやすいように変えてあります。たとえば「でない」、「かつ」、「または」、「ならば」は、 それぞれ not, and, or, => (あるいは ==>) と書いています。皆さんは、ノートに正しい記号で 写しかえてください。そういう作業は良い勉強になります。

なお、論理記号(論理結合子、命題結合子)を出力するには
∧は「あんど」、∨は「または」、¬は「ひてい」、⇒ は「ならば」を 入力して変換すると出ます。
演習問題は提出するわけではありません。各自解いてみて力をつけてください。 パズルランドのようにパズルを解くことに応用すると、楽しく勉強できると思います。


4月10日

3章 3・1 文の記号化(p.96) :文章の記号化とはどういうことか。
[1] 命題論理の式(p.96): 記号化した文章を(命題論理の)論理式、という。
その定義と例題については、 模 擬授業02が参考になります。

[例3・1] (p.97)
例 「雨が止んだらハイキングに行くし、雨が止まなければ映画に行くか読書をする」
(X==>Y) and (notX==>UorZ)

[例題]

かっこをはずす例 (3.1[1],p.97):
((X and Y) or (not Z)) は X and Y or not Z と同じ 逆に X and Y or not Z を見てかっこをつけてみよう and は or より結びつきが強いので、まず (X and Y) とかっこをつける。 not は or よりも結びつきが強いので、(not Z) とかっこをつける。 これにより (X and Y) or (not Z) となる。最後に全体にかっこをつける。 (これはつけなくてもよい。)

かっこをはずせない例:
((X or Y) and (not Z)): (not Z) のかっこははずせるが、(X or Y) のかっこをはずすと、 X or Y and not Z となる。ところが and のほうが or より結びつきが強いから、 かっこをつけると (X or (Y and (not Z))) となり、もとの論理式とは異なる。 したがってこの例では (X or Y) and not Z どまりである。

例:かっこをはずす:
(X => ((not Y) and X)) → X => not Y and X
(X => Y) and (X or (not Z)) → (X => Y) and (X or not Z)
かっこをつける: (X => Y) and X or not Z → ((X => Y) and X) or (not Z)
X => Y and X or not Z => X => ((Y and X) or (not Z))

[演習問題]
(論理式の作成とかっこ:3.1[1] p.97)

[演習問題 1](かっこをはずす問題):次の論理式から式の意味を変えないようにかっこをはずす。
(1)(((not X) or Y)==>X) and Z
(2)(not (X or Y))==>(X and Z)

[演習問題 2](かっこを加える問題):次の式に意味を変えないようにかっこをつけよ。
(1)not X and Y or Z ==>X (2)(X ==> not X) and Y or Z

[演習問題 3](文章の記号化):次の文章を論理式として表せ。
(1)アキは赤いドレスが似合うが、カズホはピンクのドレスが似合う。
(2)お片づけしたらケーキあげる。でもお片付けしなかったらケーキあげない。


解答 1
    (1) (not X or Y==>X) and Z (2) not(X or Y)==>X and Z
解答 2
  (1) ((((not X) and Y)or Z)==>X) (2) (((X==>(not X))and Y)or Z)
  (一番外のかっこはあってもなくてもよい)
解答 3
  (1) X: アキは赤いドレスが似合う  Y: カズホはピンクのドレスが似合う   とおくと、 X and Y
  (2) P: お片付けする Q: ケーキをあげる とおくと、(P==>Q)and(not P==>not Q)


講義目次へ戻る



新課題提出システムMoodle
開始のときには詳しく説明するので、心配しないでください。

課題は十分ゆとりをもって出しますので、一度早めに
解答しておいて、後で修正していくことを奨めます。
期限までは何度でも修正できますから。
そのかわり、期限を過ぎて「なんとかお願いします」は いっさい認めません。
提出日時は記録されます。
採点終了後には解答を出します。
最初は皆で練習します。 漢字変換は Shift+Space で可能になります。
論理記号もすべて変換できますが、うまくいかなかったら
代用記号でいいです。

4月17日
(3.1[2]pp.98-101 ) 論理式の真理値(真理値とは、真理値の与え 方、真理値表、真理値に関する等式)
講義目次へ戻る


4月24日
真理値の計算の続き:自分で真理値表の計算をしてみること
[演習問題]
(真理値の計算3/1[2]pp98-101)

[演習問題 4 ]:次の論理式の真理値を計算せよ。
まず v(X)=T, v(Y)=F, v(Z)=T として、次にv(X)=F,v(Y)=T, v(Z)=T として。
1) (X or Y)==>notZ
2) (X==>notY) and Z
3) Z and X or notY
4) notnotX and Y
5) X or Y and Z


解答4:最初の真理値の与え方による:
 1) v(X or Y)=T, v(not Z)=F, v((X or Y)==>not Z)=F  2) T (v(X => not Y)=T, v(Z)=T. ゆえにv(全体)=T.) 3) T
  4) F (v(Y)=Fより) 5) T
後の真理値による:
 1) F;  2) v(X==> not Y) =T, v((X ==> not Y) and Z) = T  3) F (v(Z and X)=F, v(not Y)=Fより);  4) F;  5) T



真理値計算の例
(X∨Y)⇒¬Z を C とおく。v(X)=F, v(Y)=T,v(Z)=Tのときに、v(C)を計算する。 まずv(X∨Y)は、v(Y)=TよりT。v(¬Z)は v(Z)=TよりF. X∨Y を A とおき、¬Z を B とおくと、C は A⇒B である。 v(A)=T, V(B)=F であるから、真理値表により、v(A⇒B)=F.

課題について

各回の点数は2ー3点なので、たまに休んでも、ちょっと失敗しても すぐに取り戻せるけれど、 「塵も積もれば山となる」ですから、注意してください。 なお、時間的ゆとりがあるので、早いうちにとりあえず解答しておい て 後で必要ならば修正することを勧めます。

以下に2003年度ー2005年度の問題と解答があります。
練習問題として、随時勉強してください。


課題2004-1:問題と解答

問題 1
次の論理式から、命題結合子の結びつきの強さの規則によって できるだけ括弧を除いてください。

((A∧B)⇒((¬A)∨(C⇒B)))

問題 2
次の文章を命題論理の論理式で表現してください。
基本文は各自適当な文字で表してください。

 「満開の桜を見逃したくなかったら、今日行ってみるべきです」

(基本文は「(あなたが)満開の桜を見逃したい」と
「(あなたが)今日行ってみるべきである」の二つです。)

課題2004-1の解答:

問題1  A∧B⇒¬A∨(C⇒B)
問題2 「 満開の桜を見逃したい」、「今日行ってみるべきである」を
それぞれ P, Q とすると、 ¬P⇒Q

補足(.ps file)
補足(.pdf file)


課題2004-2:問題と解答

問題1
論理式 A⇒¬A の真理値 v(A⇒¬A) をすべての場合
(すなわち、 v(A) が T の場合も F の場合も)について 求めよ。

問題2
v((A∧B)∨(A∧¬B)∨(¬A∧B)∨(¬A∧¬B)) はつねに T であることを示せ。

ヒント:「∨」の真理値の定義による。 v(A), v(B)  の値がそれぞれ  T, F である、4個の組み合わせについて、 
v(A∧B), v(A∧¬B), v(¬A∧B), v(¬A∧¬B)  
を、それぞれ計算する。

課題2004-2の解答:

1. v(A)=T のとき、v(¬A)=F; ゆえに、⇒の真理値表より v(A⇒¬A)=F
v(A)=Fのとき、v(¬A)=T; ゆえに、⇒の真理値表より v(A⇒¬A)=T
真理値の定義にしたがって考えてもよい。また、v(A⇒¬A)=v(¬A)に気がついて もよい。

2. v(A), v(B) がそれぞれT,F のどれかを値とする組み合わせによる場合わけ をする。
v(A)=T, v(B)=T のとき v(A∧B)=T; v(A)=T, v(B)=F のとき v(A∧¬ B)=T
v(A)=F, v(B)=T のとき v(¬A∧B)=T; v(A)=F, v(B)=F のとき v(¬A∧¬ B)=T
ゆえにすべての場合に、 v(A∧B), v(A∧¬B), v(¬A∧B), v(¬A∧¬B) のどれ かが
T。ゆえに∨の真理値の定義から、与えられた論理式の真理値はつねにT

講義目次へ戻る


5月1日
命題3.3(3.13.1[5]p103)の説明、応用

注: 命題3.3に次を加える。
(1) v(not not A)=v(A)
(2) v(A and A)=v(A); v(A or A)=v(A)

not not A のように否定が二つ続くことを「二重否定」という。
上の等式(1)がなりたつことを「二重否定の除去」という。
(2)がなりたつことは、∧と∨が べき等であるという。
これらの記号については、同じ命題の繰り返しは 不要、ということである。
ただしv(A⇒A)は常に真であって、一般にv(A)と等しくはない!

命題3・3の証明を二つ示す。
 v(A or B)=v(not(not A and not B)) の証明

v(A or B)=T であるのは、A か B の少なくとも一方が真(T)のとき v(not(not A and not B)) が真であるのは、v(not A and not B)=Fのとき すなわちv(not A)=F または v(not B)=F。これはv(A)=T または v(B)=T すなわち左辺と右辺が真になるのは同値である。

v(A⇒B)=v(¬A∨B) の証明
v(A)=Fあるいはv(B)=Tのとき:v(¬A)=T. ゆえに 「v(¬A)とv(B)の少なくとも一方はT」. したがって∨の 真理値の定義によりv(¬A∨B)=T. v(A)=Tかつv(B)=Fのとき:v(¬A)=F. ゆえに、 「v(¬A)とv(B)の少なくとも一方はT」が成り立たない. したがって∨の真理値の定義によりv(¬A∨B)=F. 上記の真理値をA⇒Bの真理値表と比較してみれば、完全に 一致することがわかる。

命題3・2や3・3のようにv(D)=v(G)の等式がなりたつときには、 D と G を置き換えても論理式の真理値は変わらない。

例:v(A and (B=>C))=v(A and (not B or C))
真理値に関する等式については 「真理値の等式」も参考にしてください。

以上以外にもよく使われるいくつかの等式があります。
たとえば v(A⇒B)=v(¬B⇒¬A)(対偶)。
しかしv(A⇒B)=Tでもv(B⇒A)=Fのことがある。(v(A)=F, v(B)=T のと き。)
例: v(x>0⇒x>0∨x=0)=Tであるが、v(x>0∨x=0⇒x>0)=F.
この現象を「逆は必ずしも真ならず」という。

背理法: 「¬A から矛盾(たとえば X∧¬X )が導かれるならば、 A が成り立つ」
という論法のこと。
背理法によってある命題(論理式)が正しいことを示すには、
対偶と二重否定の除去とde Morganの 法則を使う:
¬A⇒X∧¬Xが示されたとする(すなわち、 v(¬A⇒X∧¬X)=T)。
対偶により ¬(X∧¬X)⇒¬¬A。de Morganの法則と二重否定の除去により
¬X∨X⇒A。¬X∨Xは排中律で、つねに成り立つ(値がT)ので、 v(¬X∨X⇒A)=T=v(A). ゆえに、Aが正しい。


[演習問題]
3.1全体に関する問題

[演習問題 5](真理値に関する等式)

命題3・3を使って、次のことを示せ。

 (1) v(not A or not B)=v(not(A and B))
 (2) v(not A => B)=v(A or B)
 (3) v(not (A or B)) = v(not A and not B)
 (4) v(not (A and B))=v(not A or not B)
 (5) v(¬A∨B⇒C)=v((A∨C)∧(¬B∨C))

[演習問題 6] (文章のいろいろな表現の仕方)
次の文を表す論理式を書き、命題3.3を使ってほかの論理結合子で表してみる。

(演習問題3の(1)と(2))
(1) アキは赤いドレスが似合うが、カズホはピンクのドレスが似合う。

(2)お片づけしたらケーキあげる。でもお片付けしなかったらケーキあげない。


解答 5:(1) v(not A or not B) = v(not (not not A and not not B)=v(not(A and B))
(2) v(not A => B)=v(not not A or B) = v(A or B)
(3) v(not (A or B)) = v(not (not(not A and not B)))= v(not not (not A and not B))=v(not A and not B)
(4)v(not (A and B))=v(not(not(not A or not B))) =v(not not (not A or not B))=v(not A or not B)
(5) (命題3・3および3・1のド・モルガンの法則、分配律を使う) v(¬A∨B⇒C)=v(¬(¬A∨B)∨C)=v(¬¬A∧¬B∨C) =v(A∧¬B∨C)=v((A∨C)∧(¬B∨C))

解答例 6:(1) P∧R; たとえば、v(P∧R)=v(¬(¬P∨¬R))
(2) (K⇒C)∧(¬K⇒¬C); たとえば、v((K⇒C)∧(¬K⇒¬C))= v((¬K∨C)∧(¬¬K∨¬C))=v((¬K∨C)∧(¬C∨K))

[メモ]

最後の式を文章に戻すと、「お片づけしたらケーキをあげるし、 ケーキをあげたらお片づけする」となる。
なんだか変?

もっと変なのを教えてあげましょう。
「叱られないと勉強しない」って、よく言われることですよね。 Maryはほんとにこの通りの少女なのです。親はいつもMaryについて こう言っています。 ところで親の発言の対偶をとると「勉強すると叱られる」になります。 親の発言が正しければ、その対偶も正しいはず。Maryが勉強しないのは 実は勉強すると叱られるから?
論理的に正しいはずなのに、なぜこんなことになるのでしょう?
ちょっと考えてみてください。


「例」と「反例」について


例の意味はわかると思います。論理式の例(たとえば A or not B=>C )とか、
v(A or not B=>C)=T となるような A,B,C の真理値の組の例(たとえば v(A)=v(C)=T, v(B)=F )、などというふうに使いますね。
反例というのは何かが成り立たない例のことです。 したがって「論理式の反例」 とはいいません。論理式でないものは単に論理式のつもりでまちがった、というだけです。 v(A or not B=>C)=F となるような A,B,C の真理値の組の例 をv(A or not B=>C)=T の反例といいます。=Tとならない例だからです。ここではたとえばv(A)=T, v(B)=F,v(C)=F が反例になっています。


[2003年課題1と解答]

(1) 文章 「タマが昼寝しているときは、(タマは)子猫のことを考えていない」を 論理式で表してください。ただし、「タマが昼寝している」を X 、 「(タマが子猫のことを考えている」を Y とおく。

答え X⇒¬Y

2) 論理式 ((X∧(¬Y))⇒((Z∨X)∧Y)) から、意味を変えずに 括弧をできるだけ除いた論理式を書いてください。

答え X∧¬Y⇒(Z∨X)∧Y
注: Z∧Y∨X∧Y は、この問題の解答としては適当でない。 しかし、真理値としては同じ

(3) v(X)=T, v(Y)=F のとき、v(X∧¬Y) は T ですか、 F ですか? 正しいほうを書いてください。

答え T (理由:このときv(¬Y)=T, したがって、∧の真理値の定義から v(X∧¬Y)=T

番外練習問題: 論理式 ¬(¬X⇒Y) を、X,Y,¬,∧ で表せ。
すなわち、X,Y,¬,∧ のみから作られる (真理値が¬(¬X⇒Y)と常に同じ) 論理式を 求めよ。また、その理由を示せ。

解答: ¬X∧¬Y
証明: v(¬(¬X⇒Y))=v(¬(¬¬X∨Y))=v(¬(X∨Y))=v(¬X∧¬Y)
それぞれの等号は命題3・3の⇒の変形、二重¬の除去、命題3・1の ド・モルガンの法則、によって得られる。

2003年課題2と解答

(1) 論理式 ¬X⇒¬(Y∧Z) (これをGと呼ぶ)を、∨と¬で表せ。

(2) 命題3.3のv(A∨B)=v(¬(¬A∧¬B))を示せ。

解答 (1) v(¬X⇒¬(Y∧Z))(⇒の変形)=v(¬¬X∨¬(Y∧Z))(二重¬の除去) =v(X∨¬(Y∧Z)) (ド・モルガンの法則)=v(X∨¬Y∨¬Z) ゆえに、答えは X∨¬Y∨¬Z
(2) v(¬(¬A∧¬B))(ド・モルガンの法則)=v(¬¬A∨¬¬B)(二重¬の除去) =v(A∨B).

講義目次へ戻る



課題2005-3の問題と解答

問題1: 論理式 AとB について、
v(A∧B) = v(¬(¬A∨¬B))  ・・・ (1)
が成り立つ(命題3・3、p.103)。
(1) を使って次の文章を「でない」と「または」を使って言い換えてください。
(p.103の例を参照してください。)
文章:カナは飛行機で札幌に行き、マナは新幹線で東京に行く。

問題2: 上の (1) と、二重否定の除去(v(¬¬X) = v(X))を使って
    v(¬X∧Y) = v(¬(X∨¬Y))
を示してください。((1)と二重¬の除去をどこで使うか 明記してください。)

解答:

1. カナが飛行機で札幌に行かないか、または、マナが新幹線で
東京に行かない、ということはない。

2. v(¬X∧Y)=(1) v(¬(¬¬X∨¬Y))=(二重否定の除去)v(¬(X∨¬Y))

5月8日

命題論理の意味論(p.106, 3・2[1])論理式の恒真性、充足可能性、矛盾。

恒真な式の例:X∨¬X; X⇒X; ¬¬X⇒X; X⇒¬¬X; X⇒(Y⇒ X);
X∧Y⇒¬(¬X∨¬Y)
矛盾する式の例: X∧¬X; ¬(X⇒X)
恒真でなく、充足可能な式の例: X; X∨Y;

和積標準形([3]式の標準形 pp.108-111)

和積標準形の定義、真理値、恒真性の判定、和積標準形への変形手続き。

p.107, 例3・4の、max, min を使わない解法

それぞれの論理式を G とおく。

(1) v(A)=T のとき: ∨の真理値の定義から v(G)=T
v(A)=F のとき: v(¬A)=T.
v(B)=T ならば v(B∧¬A)=T.ゆえにv(G)=T.
v(B)=F ならば、v(¬B)=T. ゆえにv(¬B∧¬A)=T.ゆえにv(G)=T
以上よりすべての場合にv(G)=T. したがって G は恒真

(2) v(A)=T ならば、⇒の真理値の定義(真理値表)により、 v(A∨B⇒ A)=T.
ゆえにv(¬(A∨B⇒A))=F. ゆえに G は恒真でない。
v(A)=T が G (またはv(G)の)反例。(v(B)は任意)
v(A)=F, v(B)=T のとき、v(A∨B)=T, ゆえに⇒の真理値表によりv(A∨B⇒ A)=F. ゆえにv(¬(A∨B⇒A))=T. ゆえに G は充足可能

(3) v(A)=Fのとき、∧の真理値の定義により v(A∧¬(A∨B))=F.
v(A)=T のとき、∨の真理値の定義により v(A∨B)=T.
ゆえに v(¬(A∨B))=F. ゆえに∧の真理値の定義によりv(G)=F.
以上より、v(G) は恒にF. ゆえにG は充足不可能。すなわち矛盾

[和積・積和標準形のまとめ]

和積標準形と積和標準形は、論理式の一種の規格品というべきものである。
リテラル:命題変数(たとえば X)とその否定(たとえば ¬X)をリテラルとよぶ。
基本和:いくつかのリテラル(たとえば L_1,L_2,...,L_k)を∨でつないだもの
(たとえば L_1∨L_2∨...∨L_k の形)を基本和とよぶ。
和積標準形:いくつかの基本和(たとえばS_1,S_2,...,S_m)を∧でつないだもの
(たとえば S_1∧S_2∧...∧S_mの形)を和積標準形とよぶ。 (正確には(S_1)∧(S_2)∧...∧(S_m)と書くべき) したがって一般に和積標準形は次の形をしている (L_{11}∨L_{12}∨...∨L_{1k_1})∧(L_{21}∨L_{22}∨...∨L_{2k_2})∧ ...(L_{m1}∨L_{m2}∨...∨L_{mk_m})

基本積、積和標準形は上の定義で∨と∧を入れ替えて得られるもの

和積標準形の真理値がTとなるのは、基本和S_1,S_2,...,S_mがすべてTのと きである(∧の意味から)。 基本和L_1∨L_2∨...∨L_k の真理値がTとなるのは、リテラルL_1,L_2,...,L_k  の うちの少なくとも一つの真理値がTとなるときである(∨の意味)。 基本和が恒真になるのは、少なくとも一組のリテラルについて、一方が命題変数、 他方がその否定になっているときである。すなわち、リテラルのなかにたとえば Xと ¬Xがあるときである。このとき恒真になるのは明らか。もしこのようなリテラルの組が なければ、各リテラルについて、変数Xが現れていれば, v(X)=Fとし、
¬Xが現れていれば、v(X)=Tとする。このときv(¬X)=Fとなる。
こうすれば、その基本和のすべてのリテラルの真理値はFとなり、したがって
その基本和の真理値はFになる。
このようにして、和積標準形の恒真性は、リテラルの形を見れば判定できる。 和積標準形が恒真でないことの判定には、一つの基本和が恒真でないことを 示せばよい。

では、和積標準形でない論理式はどうするか?実は
すべての論理式は和積標準形に通じる!
p.110,[4] 命題3・8 にその手続きがある。


[演習問題]
(和積標準形 3.2[3] pp.108-111)

[演習問題 7] 変数X,Y,Zに適当に真理値を与え、次の標準形の真理値を求めよ。
1)A_1: (X or (not Y)) and ((not X) or (not Y) or Z)
2)A_2: (X or Y) and (X or Z or (not X))

[演習問題 8] 次の標準形について(真理値を計算しないで)恒真性を判定せよ。
恒真でないときにはその式を偽(F)にするような変数の真理値を一組 与えよ。
(反例を与える、といってもよい)
a) 上の問題の式A_1とA_2。
b) A_3: ((not Y) or Z or Y) and (Z or X or Y or (not X))

解答 7(例) 1) v(X)=T, v(Y)=F, v(Z)=F とすると、v(A_1)=T
これは一例にすぎない。まずこの例で確かめて、後に自分で 好きな真理値を与えてみること。
2) v(X)=F, v(Y)=F とすると、 v(X or Y)=F。ゆえに、v(A_2)=F
このとき、第一の基本和が F になるので、v(Z)はなんでもよい。 また、第二の基本和の真理値を計算する必要がない。

解答 8 a) A1 たとえば最初の基本和のリテラルが X と not Y で共通の文字がないので恒真でない。 v(X)=F, v(Y)=T とすれば偽。
A2 最初の基本和のリテラルが X と Y だから、恒真でない。上に例が与えられている。
b) 最初の基本和に not Y と Y があり、後の基本和に X と not X があるので、恒真。



*****
講義目次へ戻る



課題2004-4の問題と解答

問題1. 恒真な論理式を一つ挙げてください。

(論理式だけ書けばいいです。証明は不要)
問題2. 次の論理式(Aと呼ぶ) の真理値を T にする変数の真理値の組と、
Aの真理値を F にする変数の真理値の組を、
それぞれ一組ずつ 与えてください:  X∨Y⇒¬X∨(Y∧Z)

解答の仕方の例:たとえば  A: X∧Y⇒¬X のとき、v(A)=T にするには、v(X)=F または v(Y)=F であればよい。 (このうちの一方を書けばよい)
v(A)=Fにするには、v(X)=T, v(Y)=T。

解答:

1. 以下はほんの一例です。X∨¬X, X⇒X, X∧Y⇒(Z⇒Y),
(P∨(Q∧¬P)∨ (¬Q∧¬P))
2. v(A)=T であるためには、v(X)=F (v(Y), v(Z) は何でもよい)または
v(Y)=v(Z)=T
v(A)=F であるためには、v(X)=T, v(Z)=F または v(X)=T, v(Y)=F

5月15日

和積標準形への変換(pp.110-111[4])


[演習問題]

[演習問題 9] 次の論理式の和積標準形を求め、恒真かどうか判定せよ。 恒真でなければ、反例を与えよ。 (その式を偽にするように変数に真理値を与える、ということ。)
1) (A=>B)and (not(A and notB))
2) (X and notY)=>X
3) (X and (notY or Z)) or (notX and (notY or Z))
4)お父さんからの電話「今駅だけど、何か買って帰ろうか?」
お母さん「別にいいわよ、雨が降っているから、早く帰っていらっしゃい」
お父さん「それじゃ、晴れたら、早く帰らなくていいんだね?」
お母さん「?」(「論理パズルとパズルの論理」より)
お父さんの発言は、お母さんの発言の正しい結論になっているでしょうか?
5)お母さん「ノブ君、お片付けしたらおやつにしましょう」
10分後にお母さん「お片付けしてないじゃないの。おやつにできないわ」
伸くん「でもお母さん、お片付けしなければおやつにしないとはいわなかったよ」
伸君の言い分は正しいでしょうか?

答え 1) (not A or B) and (not A or B) すなわち not A or B。 恒真でない。反例はv(A)=T, v(B)=F
2) not X or Y or X (一つの基本和)恒真
3) (X∨¬X)∧(X∨¬Y∨Z)∧(¬Y∨Z∨¬X)∧(¬Y∨Z)
v(X)=v(Z)=F, v(Y)=Tとすれば第2基本和がFになり、したがって全体はF
4) P: 「雨が降っている」 Q: 「早く帰る」とすると、 母:P==>Q であり、 父:not P==>not Q である。
母の発言から父の発言が導かれるならば (P==>Q)==>(not P==>not Q) が恒真のはず。
和積標準形を作ると (P or P or not Q) and (not Q or P or not Q)で ある。
v(P)=F, v(Q)=Tとすればこれは恒真でないことがわかる。
なお、これは、対偶を使えば、 (P==>Q)==>(Q==>P)と同じで、これが成り立たないことを「逆は必ずしも真ならず」という。
5) P: お片付けをする Q: おやつにする(おやつをあげる) 母の第一発言:P==>Q 母の第二発言:not P==>not Q 伸くんの言い分:P==>Q だからといって not P==>not Q とはいえない。
4)と同じ状況である。ゆえに伸君は正しい。


2002年度第一回レポート課題(解答つき)が ここにあります。

演習問題として参考にしてください。
訂正:問題1の(2)で変数 Z の真理値の条件が抜けていました。v(Z)=T を加えてください。


[2003年度第三回課題と解答]

(1)  基本和 L_1: X∨Y∨¬X , L_2: Y∨Z∨¬X , L_3: Y∨¬Z∨X∨Z のうちで、恒真なものはどれか?
(2) 恒真でない基本和の真理値がFになるような各変数の真理値を求めよ。

解答 (1): L_1, L_3。 L_1 ではXと¬X というリテラルの対がある。
 L_3 では ¬Z と Z というリテラルの対がある。L_2 では異なる変数しかない。
解答 (2):変数そのものが現れているときにはF,¬がついているときにはTにすればよい。
 恒真でないのはL_2であるから、v(X)=T, v(Y)=F, v(Z)=F.

和積標準形への変形と恒真性判定の演習問題 和積標準形が ここにあります。

訂正: 例1の「X or X」は「X or not X」の間違いです。二箇所あります。


課題2004-5の問題と解答

命題変数 X, Y, Z を含む論理式で、次のものをそれぞれ1個ずつ書いて ください。

1. 和積標準形になっているもの。
2. 和積標準形になっていないもの。

解答・・・といっても、模範解答があるわけではありません。
1 の例: (X∨¬Y∨Z)∧(Y∨¬Z)∧¬X 2 の例: (X∧¬Y∧Z)∨(Y⇒Z)∧X

講義目次へ戻る


5月22日

パズルを解く練習


[2003年度第四回課題と解答]

(1) G: (Y⇒X)∨(Y∧¬X) の和積標準形を求めよ。
解答:(→は、命題3・8による変形を示す) G→(¬Y∨X)∨(Y∧¬X) (⇒の除去、(3))→(¬Y∨X∨Y)∧(¬Y∨X∨ ¬X) (∨と∧の分配、(5)) 後の変形は、Aを(¬Y∨X)、BをY、Cを¬X、とおいて(5)の変形を行う。

(2) Gは恒真か?
解答:恒真である。なぜならば、二つの基本和にそれぞれ ¬YとY、Xと ¬X が あるから。


[和積標準形についての注意]

和積標準形は 「A_1 and A_2 and ... and A_n の形、 ただし各A_i は基本和、ここで n=1,2,3,...」. n=1 も認めていることに注意。 このときA_1はひとつの基本和で、and は含んでいないが、和積標準形の 特殊な形として認められる。また、基本和は「B_1 or B_2 or ... or B_m、 各 B_j はリテラル、ここでm=1,2,3,...」 m=1 もみとめられることに注意。 したがって一つのリテラルも基本和である。極端な例では一つのリテラルは 和積標準形なのである!

[演習問題10:パズルを解こう]
和積標準形による解決の例(ここでは和積標準形で考えてください)

例 1加奈はいいました:
「私が風邪をひいているならば、私は風邪をひいていない」とすれば、
私は風邪をひいている。
加奈の発言は正しい?

2 佳織はいいました:
「私が風邪をひいているならば、私は風邪をひいていない」とすれは、
私は風邪をひいていない。
佳織の発言は正しい?

解答

1 P: 加奈が風邪をひいている 
 加奈の発言: (P==>notP)==>P
 和積標準形: P or P ゆえに恒真ではない
2 X: 香織が風邪をひいている
 香織の発言: (X==>notX)==>notX
 和積標準形: X or notX ゆえに恒真


もっとパズルを解きたい人は、「パズルランド」(このサイトの最初に ある),
「論理パズルとパズルの論理」 (図書館にある)の問題、などを見てください。


[2003年度第5回課題と解答]

カナ「私が天使ならば,マナは女神よ」
アヤ「それならば、カナが天使でマナが女神でない、ってことはないわ ね」
マナ「それって変」
リサ「私はアヤが正しいと思う」
マナとリサとどちらが正しい?

「カナは天使」をX、「マナは女神」をYとおくと、カナの発言は、X⇒Y.
アヤの発言は、(X⇒Y)⇒¬(X∧¬Y)
(カナの発言を受けて、「それならば・・・ってことはない」と言っているので、 カナの発言を前提にする。)和積標準形に変形するには、まず⇒を変形して、¬(¬X∨Y)∨¬(X∧¬Y) ド・モルガンの法則と二重¬の除去で、(X∧¬Y)∨(¬X∨Y)。 ∧が∨の中にあるので、分配して、(X∨¬X∨Y)∧(¬Y∨¬X∨Y)を得る。 各基本和にそれぞれXと¬X,¬YとY,があるので、恒真。したがってリサが正しい。 和積標準形の練習としては、以上が正統な解法である。 ほかに、たとえば、カナの発言を変形して、¬X∨Y、アヤの結論を変形して、¬ X∨Y したがってアヤの発言は¬X∨Y⇒¬X∨Yとなり、⇒の前提と結論が同じになるので 恒真、という解法もある。
注意: 「X⇒Yを変形して¬X∨Y」を「X⇒Y=¬X∨Y」とは書かないこと! その場合には、v(X⇒Y)=v(¬X∨Y)と書く。

2003年度第一回レポート問題(.ps版)
2003年度第一回レポート問題(.pdf版)


課題2004-6の問題と解答

ハナ「私が風邪ひいてないならば、私は風邪ひいてるの」
カナ「それだったら、ハナは風邪ひいてるわね」
ナナ「カナの言うことおかしいよ」
マナ「私はカナが正しいと思う」

問題: ナナとマナの、どちらが正しい?

次の手続きにしたがって解答してください。

1. パズルの問題を論理式で表す。
2. その論理式を和積標準形に変形する。(途中経過も書く)
3. その和積標準形が恒真であるかどうか判定する。
4. 正しいのはナナかマナか、述べる。
(恒真ならばマナ、そうでなければナナが正しい)。

解答
「ハナが風邪をひいている」 を X とおく。
ハナ: ¬X⇒X; カナはこれを受けて発言しているので、 (¬X⇒X)⇒X
1.  (¬X⇒X)⇒X が恒真か?
2. ¬(¬¬X∨X)∨X → ¬(X∨X)∨X → (¬X∧¬X)∨X → ¬X∨ X
3. 基本和 ¬X∨X にリテラル ¬X と X があるので、恒真。
4. カナの発言が恒真なので、マナが正しい。

注: 2では正確に変形手続きにしたがって和積標準形を求めた。
慣れると恒真かどうか問うためには簡単な方法がある。たとえばもとの論理式を
まず(¬¬X∨X)⇒X と変形し、二重¬を除去すると(X∨X)⇒Xを得る。これは
X⇒Xと同値であり、X⇒Xは恒真なので、もとの式も恒真。

4で「カナが正しい」と答えた人がいます。それは間違いではないですが、
4の問題は「マナとナナのどちらが正しいか?」なので、4の答えは「マナ」で す。
今回は減点しませんでしたが、題意の正確な理解は重要なことです。
また、「ハナが風邪をひいている」という答えもありました。そんなことはこの
状況ではいえません。そもそも論理パズル(ある論理式が恒真か)は
事実がどうであるか、は、全く関係ありません。

講義目次へ戻る


5月29日
第一章「集合・写像・関係」スタート。pp2-5, 1.1[1],[2]
テキストの内容とともに、ここの以下の説明もよく読んでください。
これから第1章の集合・写像・関係に入ります。

集合についての基礎知識はもっているでしょう。ここではまずその おさらいをします。写像は広い意味の関数です。関係は文字どおり、 個体どうしの間の関係です。とくに一つの個体の関係とは、その個体の 性質のことです。写像も関係も集合で表すことができます。

[集合]  集合とは個体の集まりです。計算機科学では集合の記法が大事です。 それはプログラムの仕様を書く基本になるからです。したがってこの科目では 集合の記法(pp1-2,[1]), 集合の基本性質(pp3-6,[2],[3])、基本演算(pp68,[4])、 演算に関する基本的性質(pp8-9,[5])、直積(pp11-12)を重視します。無限演算と 個数については簡単にふれます。とくに演算に関する性質(p.8,命題1・2)は 記号を論理記号で読み替えると、命題論理の真理値に関する等式(p.100, 命題3・1) とまったく同じ形の等式であることがわかります。これは偶然ではなくて、 きちんと示すことができます。(詳しい証明は省略) この章では例題(反例を含む)による簡単な演算と記法に重点がおかれています。 テキストの例題をよく理解してください。ここにも例をおきます。


1] 集合の記法: 記法はいろいろありますが、基本は中括弧の中に集合の要素を 書くことです。かならず中括弧の中に書いてください。 要素の書き方は、実際にそれぞれの要素を並べる;いくつか典型的な要素を並べて その後に・・・をつけ、以後の要素を推測させる;「これこれの性質をみたす個体」という 条件を書いて、それをみたす個体の集合、という書き方をする、などがあります。 そのときどきに都合のよい書き方をします。 集合の例については、集合の性質([2])の記法が先決です。それと集合の記法の例は([1],[2]に対応。説明の補足もある) ここ(.ps) (.pdf) にもあります。

集合・集合の記法のキーワード:要素、属す、中括弧、全体集合(領域)、 集合の定義(なまえづけ)、2集合の同一性、空集合。

注:全体集合とは、プログラム言語における「型」のようなもの。
例:整数型、実数型。仕様記述ではさまざまな型を使う。

集合に関する例題が次回の項目の[例題]にあります。

課題2004-7:論理パズルを出してください!

解答は下のファイルに、「皆さんのパズル」としてまとめてあります。
パズルらしくするために、多少手直しをしました。
また、全く同じパターンのパズルは、一つの例にしました。
皆さんのパズル04(.ps) (.pdf)

講義目次へ戻る


6月5日

部分集合と集合の演算([3],pp.5-6, [4],[5],pp6-9)


集合の例題(.ps file)

集合の例題(.pdf file)

集合に関する記号の入力について

入力しにくい記号は、自分で決めて「・・・と表す」と明記して 使ってけっこうです。いくつか典型的な使い方を書いておきます。 和集合:cup (例 A cup B)、 共通部分 : cap(例 A cap B)、補集合:例 A^c 「xがAの要素である」は xΕA、x∈A などと表される。
∈, 、∩、 ∪、⊆、⊇、⊂、⊃、などの記号 は「数学」と入力して
変換できることがあります。試してみてください。
xがAに属する、 は 「イプシロン」と入力すると ε が出るので、xεAで代用してもよい。
それも無理なときには「x blongsto A」, 「x in A」、 「x is an element of A」、「x は A の要素」などと書けばよい。 ほかにも、記号に困ったら知らせてください。


1.1[5]p.8 集合の演算に関する 等式の補足(.ps)(.pdf)
補足の補足(.ps) (.pdf)
補足その2(.ps file) (.pdf file)
訂正: 2 問題 3. (1) (A cap B^c)^c =A^c cap B (誤)
正しい設問は (A cap B^c)^c = A^c cup B です。

[6月7日分例題]

1) N={1,2,3,...} で考える。
3の倍数の集合Threesを定義せよ。
Threes = {n| n=3m, mεN}={3n| nεN}={3,6,9,...}

2) Nの中の空集合を定義せよ。
たとえば、{nεN| n=-1}, {nεN| n < 0}, {nεN| n=2n+1}

3) 好きな集合の例(ほんとは好きでなくていいですよ!)
{xεR| x is in [-1,1]}, 仲よし={花子、梅子、桜子、松子、竹子}, {x|xは国、xの首都の人口が800万以上}などなど


2003年度第一回ペーパーレポー ト解答(.ps) (.pdf)


2003年度皆さんの問題(.ps file)
2003年度皆さんの問題 (.pdf file)
2003年度第一回ペーパーレポート解答の「皆さんの問題」集です。
問題らしくするために、ほんの少し変えた個所もありますが、
大体もとのままです。まず、皆さんで解いてみてください。
その後で 皆さんの問題解答 編(.ps file)を見てください。
問題解答編(.pdf file)

6月28日に、[集合の勉強の仕方]という項目があります。
集合の演算についての演習問題になるので、実行してみてください。

講義目次へ戻る


6月12日

1・2写像(p12→) [1]写像の定義、[2]写像の記法、[3]写像の考え方、 [4]単射と全射[5]逆写像 写像は関数と実質同じであるが、考え方としてもう少し一般的に「対応規則」という抽象的な概念である。 この科目では写像の定義、書き方、例題に重点をおく。

[一口メモ]
ラジオで聞こえた話です。

あるお医者さんの発言:「(ガンの)早期発見できた人は幸いである」を強調しすぎるのは困る。 なぜなら、このことは「早期発見できなかった人は不幸である」を意味するので 手遅れだった人が自分は不幸であると思ってしまう。

医学的なことはさておいて、これって正しい? 命題論理に慣れている皆さんは、すぐわかりますよね?

講義目次へ戻る


6月19日
20ページー22ページ

[7]恒等写像、[9]写像のグラフ 多価写像は範囲外。この科目で「写像」といえば一価写像と考えてよい。 写像の「グラフ」は重要なので、よく理解すること。
例 sin x のグラフ= {<x,sin x> | x in R}、ただし"x in R"は「x がR(実数の集合)の要素」を表す。 14 ページ、例1・10 の (3)のグラフ={<m,P_i>| m=i14 or m=i37, i=1,2,...,9, P_i は i 番目の景品} 数列 {a_n}, ただしa_n =2n+1,のグラフは {<n,2n+1>|, n =1,2,3,...}


課題2004-8の問題と解答

1. あなたの好きな魚(食べ物としての)の集合を書いてください。
  ただし、要素の個数は3以上5以下にしてください。
   集合の名前は各自つけてください。
  (魚のなまえは、仮名でも漢字でもローマ字でも英語でもいいです)

  2. 15で割り切れる正の整数の集合を書いてください。
集合のなまえは各自つけてください。
   ただし正の整数全体の集合をNと呼ぶことにする。

解答

1.の 解答例  Y = {いわし、さんま、はも、いか}
2.の解答例   Fifteens = {n∈N|あるm∈Nによって、 n = 15m と書ける} ={15n| n∈N}


2002年度第二回レポート課題 参考にしてください。
[集合の勉強の仕方]

(1) 自分で集合をいくつか定義してください。どのような定義の仕方でもかまいません。 それらをA,B,C,...などとおいて、次の等式が成り立つことをチェックしてください。 合っていれば(たいてい!)集合の演算を正しく行っていると考えていいでしょう。 なお、cup, cap, empty, X^c はそれぞれ和集合、共通部分、空集合、Xの補集合を表す。

1. 8ページの命題1・2の等式。
2. A cap (B-A) = empty;
3. (A cup B)^c cap C = (A^c cap C) cap (B^c cap C)
4. (A cap B^c ) cup D = (A cup D) cap (B^c cup D)
5. (A cup B) cap (C cup D)=(A cap C) cup (A cap d) cup (B cap C) cup (B cap D)
6. (A cap A^c) cup D=D;
7. (A-B)cap (B-A)=empty
8. (A-B)cup (A cap B) cup (B-A)=A cup B

(2) 次のそれぞれ二つの集合の直積を記述し、それから作れる表を考えてください。
1. A:={T,F}, B:={T,F}、ここでT,Fは真理値。
2. A:=都道府県全体, B={[n,n+5]| n=0,6,11,16,21,...116}, [n,n+5]はn才から n+5才の年齢を表す。

(2) の解答例:1. Aを縦に、Bを横に書けば、A とBの真理値の対に対す る"and"の真理値表を作れる。
2. 各都道府県における5才ごとの人口 表を作れる。

注: 直積は11ページの定義以外にはとくにいうことはありません。
定義はとても簡単ですね。でも、直積はとても大事なものです。 直積の理解のために、表を思い浮かべてください。上の例の真理値表は まさにそれです。Aが都道府県名の集合、Bが{10n| n=0,1,2,...}として Aの要素を縦に、Bの要素を横に並べて、ますめを作ると、たとえば Aの要素である京都とBの要素である10の交差点となるますめができます。 AxBは、このようなますめ全体です。都道府県の各10n代の人口をこれらの ますめに記入していくと、日本の都道府県の年代別人口表ができます。


[写像の勉強の仕方]

まずテキストの例題をよく読んで、基本的な性質 (全域的、部分的、単射、全射、逆写像)の例を理解してください。 それらのうち理解できない例があれば質問してください。 次に自分で写像を定義してみてください。数学における関数でも日常生活における対応でもいいです。 写像のグラフについて、数行のレポートを書いてみてください。 写像に対応する集合、ある性質をもつ集合から定義される写像、例、など。

集合と写像の問題(.ps) (.pdf)
問題の一部は2003年度の課題の問題です。
下に解答があるので、参考にして ください。


[第2003-8回課題解答]

(1) (A cup (B cap C))^c = A^c cap (B cap C)^c (i)
= A^c cap (B^c cup C^c) (ii)
= (A^c cap B^c) cup (A^c cap C^c) (iii)
上の集合の等式の (i),(ii),(iii) のそれぞれは、 命題1・2の等式の どれを使っているか、 等式の名称を書いてください。

答え (i) , (ii) ド・モルガンの法則; (iii) 分配律

(2) A は二人の子供の名前の集合、 B は二人に着せたい帽子の色の集合とする。
すなわち、A={Mary, John}, B={Red, White} 。
二人の子供と帽子の色の組み合わせすべての集合は A x B (AとBの直積集合)である。

 A x B を(要素の集合として)表してください。

答え A x B ={<x,y>|x ε A, y εB} が、直積の定義である。 これを答えにしても正しいので、正解にしてますが、「要素の集合として」 と書いた意図は、実際の要素を書いてほしかったのです。すなわち、 A x B = {<M,R>,<M,W>,<J,R>,<J,W>}. <M,R>は、(MとRの)順序つきの対です。集合{M,R}は順序は無関係です。 (M,R)も順序対です。ふつうはこの記法を使います。

3) (2)のA のべき集合 P(A) を (要素の集合として) 表してください。

答え P(A)={φ,{M},{J},A}


2003年度試験問題の解法の訂正です。(ファイルはこれより後にあります。)
最初の論理式の和積標準形を求める問題です。

(A⇒M)⇒(¬A⇒¬M); ¬(¬A∨M)∨(¬¬A∨¬M);
(¬¬A∧¬M)∨(A∨¬M); (A∧¬M)∨(A∨¬M);
(A∨A∨¬M)∧(¬M∨A∨¬M); A∨¬M

講義目次へ戻る


6月26日

写像の性質(単射、全射)、逆写像、写像の合成、恒等写像、 写像のグラフ、写像のグラフと直積集合の部分集合の関係。

[写像の問題]

次の写像について、全域的、部分的、単射、全射、のうち当てはまるのはどれか?
1. f:R→R, f(x) = 1/x;
2. f: X={x| x>0} →R,  f(x)=1/x;
3. f: R→R, f(x)=√(1-x);
4. P = 人々の集合, N={1,2,3,...}, C={x| x は国}, psprt: P → CxN (Cと Nの直積集合), psprt(person) = <c,n>, ただし、c は person が国籍をもつ国名、
n は person に c が発行した旅券番号
5. 4 と同様の記号で、H: CxN→P, H()=person, は国名と数の対、 personは c国が発行した番号nの旅券の保持者。
6. tan: R→R (三角関数tangent);
7. log: {x| x>0}→R

問題解答
1. 部分、単; 2. 全域、単; 3. 部分、単; 4. 部分、 単;
 5. 部分、 一応単射としておく。 (複数の国の旅券保持者もいるので、事実上は単射でない); 6.部分、 全; 7. 全域、単


課題2004-9の問題と解答

全体集合 U を平面の点全体とする。すなわち、
U={<x,y>| x,y∈ R} (R は実数全体の集合)

1. 関数 y=x^2 、x-軸、x=1 の直線 で囲まれる図形の点の集合 X を
数学の式を使って書いてください。(図形の周囲も含む)

2. 集合 X の、(U における)補集合と 関数 y=√x より下にある
平面の点集合 Y の共通部分、すなわち X^c ∩Y を
  集合の記法で書いてください。 (周囲も含む)

解答

1. X={<x,y>∈U| 0≦y≦x^2∧0≦x≦1}
∧ は , でもよい。

2. X_1 ={<x,y>∈U| x^2 X_3 ={<x,y>∈U| x>1∧y≦√x}, X^c ∩Y =X_1 X_2 X_3


あるいは、X^c ∩Y ={<x,y>∈| ¬<x,y>∈X∧y≦√x}


課題2004-10の問題と解答

1.次の集合を、「補集合」をとる操作を一番中に入れ、(A^c)^c =A を使って、
書き換えてください。
例: (A∩B^c)^c =A^c ∪(B^c)^c = A^c∪B

問題: (A^c∩B)^c 

2. 次の写像について、全域的か部分的か、単射かそうでないか、
全射かそうでないか、それぞれ答えてください。(答えだけでよい)
Aはある会社の従業員の集合、Bはその会社の内線番号の集合、とする。
写像 f: A → B は次のようなものである。
 fは各従業員に、その人が使える内線番号を対応させる写像である。
 全従業員にそれぞれ一つの番号を割り振ってあるが、
 同じ番号を複数の人が共有している場合もある。
 使われていない番号もある。

解答: 1.(A^c∩B)^c =(A^c)^c ∪(B^c) = A∪(B^c)

2. 全域的、単射でない、全射でない。
解説:f は「次のようなものである」として、いくつかの条件が書いてある。
これらの条件はすべて写像 f が満たすべきものである。
「全従業員に番号が割り振られる」のだから、A のすべての要素に対して
写像は定義されている。したがって「全域的」である。
一つの番号を複数の人が使うことがある、すなわち、一つの番号 n に
対して、異なる二人の a, b について f(a)=f(b)=n となることがある。
したがって単射ではない。
使われない番号 n がある、ということは、n=f(a) となる人 a が「ない」、
すなわち、n は f の値域に入っていない。したがって全射ではない。
三つの条件をそれぞれ別の写像の性質だと思った人がいました。
それは題意を理解していないことになります。それでも部分的に合っている
こともあります。たとえば、最初の条件から「全域的」はいえます。
しかし、単射でない、とか全射でない、というのはそれだけでは決まりません。


課題2004-11の問題と解答

次の関係について、
同値関係、半順序、全順序、辞書式順序、整礎関係、
のどれに当たるか、記入してください。
(番号と関係の名称のみ記入してください。また、
どれも当てはまらない場合には、空欄にしてください。)

1.P_1(a,b): a と b はいとこ である。(人と人との関係とする)
2.P_2(a,b): a と b の差が3の倍数である。(整数間の関係とする)
3.P_3(a,b): a は b の真の約数である。
  (正整数の間の関係とする。真の約数、とは、
   a が b を割り切り、aは1でもbでもない、こと。)

解答

1. 空欄 (自分自身をいとこ、としても、3人の人a,b,c について、
aがbのいとこ、bがcのいとこ、である場合に、
aとcがいとことはかぎらない。したがって同値関係でも半順序でもない。
自分は自分のいとこではない、としても、aとbがいとこならば、
bとaがいとこで、この交換は いくらでも繰り返される。
したがって整礎ではない。全順序でも辞書式順序でもない ことは明らか。)
2. 同値関係 (a-b=3n と書けること。これが同値関係になるのは、算数の問 題)
3. 整礎関係 (1<a<b で、a が b を割り切り、さらに1<c<a でc が a を割 り切るとする。
このような関係は 1<c<a<b であり、b から始めて減少する正の整数の列は
どこかで止まるので、整礎関係。)

注:今回は提出も出来も悪かったです。それぞれの関係の定義を
よく読めば、あとは簡単な事実か数学の問題なのですが。

もし試験前に質問があったら、メールで受け付けます。具体的な問題で
何が疑問なのか整理して書いてください。


期末試験について:2002、2003、2004年度の問題と、類型の問題 です。
過去の問題(解答つき)は、もう少し下に載っています。
課題と同じ範囲・程度の問題です。課題ができなかった人は、このページの解答 を
よく読んで理解してください。また、範囲はこのページに、テキストの関係項目 が
詳しく出ていますから、見直してください。
今まで多くの例題や問題があったので、もう慣れたでしょう?
「関係」が最後になってので、多少集中的に勉強してください。
このページの例題を理解できれば大丈夫です。
[2003年度第九回課題解答]
この課題は写像の書き方と基本的な性質の理解を問うものです。

(i) h:S→T
要するに写像の書き方(h が集合SからTへの写像である、ということの表記法) の定義そのものです。
(ii) (b), (c)
h は5000人のうちの当たりくじを引いた2000人の各人に対して渡されるチケット番号を 対応させる写像である。たとえば花子が1053番のチケットをもらったら、h (花子)=1053. 残りの3000人はチケットをもらえないから、h による対応はない。すなわち、 h の定義域は 当たりくじを引いた2000人だけである。したがって、全域的ではない。 一枚のチケットを複数の人が共有できないから、単射である。チケットは完売だから、 チケットの各番号 n に対して、それをもらう人がいる。したがって h は全射である。

注:写像はとくにていねいにテキストを読むこと。目新しい記法やことばが多いが、 定義をよく理解すれば、難しいことは何もないのです。

講義目次へ戻る


7月3日
1.3 関係 (23ページから)に入りました。

[1] 関係とは:ふつうに「誰と誰はどういう関係にある」とか 「x と y の大小関係」という のと同じです。それを数式や論理式で記述するだけです。例題をよく読んでください。 関係は論理式などで表されますが、直積集合の部分であるともいえます。([2] 関係と部分集合) すべて例題でまず理解してください。命題1・5などは n=2,3 くらいで書き直してみてください。 [3] 関係の合成、[4] 逆関係、[5] 関係の和と共通部分、など、関数や集合の演算と同じことが 関係でも可能です。これらも例題で理解してください。詳しいことは省略です。 [6] 同値関係(28ページ) これは大事です。定義と例題をていねいに読んでください。 同値関係 R について R(a,b) が成り立つときに、 「a と b は R に関して同値である」という。 同値な要素どうしを集めると、 R によって要素が分類されます。それを同値類といいます。 同値な要素どうしは R に関しては区別しないもの、として扱えるので、一つの要素について なにか言っておけばほかの要素についてもいえる、という意味で便利なのです。


2002年度小テスト (.ps) (.pdf) 解答つき。参考にしてください。
和積標準形を覚えたら、真理値を忘れる人がいるようです。 どちらも大事です。


[関係について]
関係は一般に異なる集合の直積の上で定義される。

たとえばHave(a,b)を、「aさんがbという本を持っている」を 表すとすると、aは人の集合(Peopleと書こう)の要素であり、 bは本の集合(Bookと書こう)の要素である。したがってRは 直積集合People x Bookの上で定義されている。このようなときには 同値性とか順序とかは考えることはできない。 同値性や次に考える順序の場合には同じ集合(たとえばS)の直積 S x S の上で定義される。
なお、関係を表す文字または文字列は何を使っても良い。実用では 内容を表す文字列を使うと便利である。また、個体変数にも 何を使ってもよい。プログラム言語ではある程度指定されている。


関係の例(1.3[1]p23)
1. B(a,b): a は b の兄である
2. BS(x,y): x と y はきょうだいである。
3. Cityof(x,y): x は y の都市である。
4. Country(z): z は国である。(個体についての性質は一引数の関係)
5. Sequence(n,a): a は n 番目の要素である(n は正整数 、 a は実数、Sequence は数列の番号と要素の関係を表す)
6. Triangle(A,B,C): A,B,C は(平面内の)3点で三角形を形成する


[演習問題]

演習問題10:(1.3[2][6],1.1[7])
(1) 上の例題のそれぞれの関係が定義される直積集合を表せ。(各集合は適当な文字で表す)
(2) 上の例題のうち、同値関係はどれか?
(3) 自分でいろいろな関係を定義して(同値なものやそうでないもの)、 それが定義される直積集合を求めよ。

解答(1)(たとえば)1,2: People x People 3. City x Country 4. A (ただし A は地図帳にある地名の集合)5. N x R
6. Points x Points x Points (Points は平面の点)

(2) 2, 6


[第1章全体について]
「集合・写像・関係」の間の関係(わかりにくいね!)

写像によって定義されるグラフの例:f(x)=1/(x-1)
実数の集合R 上で定義されるとする。x=1では定義されないので 部分的関数。G_f = {<x,1/(x-1)>| x>1 or x<1}. R x R の部分集合 x が都市名として、countryof(x)=x がある国名 G_countryof={<x,y>| x は都市名で、y という国にある}

集合によって定義される写像の例:S = {<x,x^2 +1>|x はRの要素} f_S \(x)=x^2 +1 C={<x,y>| x は都市名で、y という国にある}とすれば、 f_C(x)はcountryof(x)と同じ関数になる。

関係によって定義される写像の例:Countryof(x,y)が 「x は都市名で x は 国 y にある」を表すとすると、f_Countryof(x)は Countryof(x,y)という関係を満たす(ちょうど一つの)yを値としてとる関数

各自いろいろな例をみつけてみてください。

[2003年度第十回課題解答]

1)expの値域は (0,∞)または{y|y>0}
(2) exp^{-1}(x)=log_e x
(3) G_exp = {<x,e^x>|xεR}
注:(1)は「値域は何か?」という問なので、実際にどのような集合か、 を答える。書き方は上のどちらでもよいが、{exp(x)|xεR}は、「値域の 表し方」なので、間違いともいえないが、△にして、配点しなかった。 また、y>0とだけ書いても、数学では通用するが、計算機科学では表記法が 重要なので、配点しなかった。
(2)はほとんどできていた。log_e xでもlog x でも ln xでもよい。 部分的写像を認めているので、とくにx>0と断らなくてもよい。
(3) ほとんどできていた。この問題は「どのように表されるか」だから 皆さんが書いたように{<x,exp(x)>|xεR}でよい。

[命題論理の論理式に関するいろいろな関係]
例と反例

1. Eq(A,B) ←→ v(A)=v(B) (が恒に成り立つ):同値関係
2. Imp(A,B) ←→ v(A)=T ならば v(B)=T: 半順序関係で全順序でない
注:Imp(A,B)は「A⇒B が恒真」ということと同じ。
3. Less(A,B) ←→ A⇒B が恒真であり、B⇒A が恒真でない:この節のどの関係でもない


2002年度期末試 験解答つき(.ps file)
(.pdf file)
注:問題3の「ノゾミの発言」が P∨P∨P となっています。
真理値でいえばこれでいいのですが、形式的に計算すると
(P∨P)∧(P∨P)、真理値的には P∨P と同じです。
2003年度第二回ペーパレポート解答つき (.ps版)
2003年度第二回ペーパレポート解答つき (.pdf版)
2003年度期末試験解答つき(.ps file) (.pdf file)

2004年度期末試験解答つき(.ps file) (.pdf file)


[2003年度第11回課題解答つき]

1. 次に挙げるのはすべて2項関係である。
(1) R_1(a,b): a と b は正整数で、同じ素数で割り切れる。
(2) R_2(a,b): a と b は正整数で、a-b が3で割り切れる。
(3) R_3(a,b): a と b は正整数で、a は b を割り切る。
(自分を割り切ることも認める。また 1 はすべての数を割り切るものと する。)
(4) R_4(a,b): a さんと b さんは、同じ町内に住んでいる。
(5) R_5(a,b): a と b は 実数で、小数部分が同じである。
(6) R_6(a,b): a さんと b さんは K 大学の学生で、それぞれ 現在のセメスター数 n と学籍番号 m の対 (n,m) で順序が ついている。すなわち、R_6(a,b) が成り立つのは、a さんのセメスター数が b さんのセメスター数より小さいか、もし同じならば、学籍番号が小さい。
(a=b のとき、R_6(a,b)は成り立たないものとする。)
以上のうち、次に相当する関係の番号を記入してください。 (一項目に複数の番号が相当するかもしれないし、一つも相当しないかもしれない。) 関係の性質と解答が同時に書いてある。 (b) 半順序関係であって、全順序関係でない: (3) (c) 厳密な意味での全順序関係: (6)
(d) 整礎関係: (6)

2. 二つの英単語 X, Y で、X と Y は3文字以上で一致し、辞書式順序で X なるものを一組書いてください。(テキストにないもの)
例: comfort < company
com と、最初の3文字が一致。 f < p だから、上の順序になる。 なお、英単語、ということなので、単語として辞書の項目に現れるものが好まし い。 たとえばwalked < walking ではあるが、walked は動詞変化である。 walker < walking などのほうがよい。

講義目次へ戻る


科目合否について

期末試験範囲:期末試験は前年度までと大体同じ難易度です。
命題論理、集合・写像・関係全体です。

成績評価基準:課題/期末試験 の割合を 20/80 にします。

この科目の最終的な合否結果は、Moodelの評価の合計をみてください。
8月初旬に確定します。(素点がそのまま成績になります。)
合否結果に関する疑問等は理学部事務室を通してください。
期末試験解答も8月までにはアップします。


2005おさらい(.ps), 2005おさらい(.pdf)

講義目次へ戻る