集合と論理２００3

このページをご覧になる方へ

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

以下に参考になるページやファイルをリストしておきます。

注意：.ps ファイルや.pdf ファイルも貼ってあります。
それらの開き方は次のとおりです。
(1) .ps ファイルの開き方（大学で）：
ウェッブから直接.ps ファイルを開きたいときには、 "ghostview"を選択して、"OK"をクリックする。
自分のホームに保存したいときには「保存」を選択し
OKとすると、自動的に各自のホームディレクトリに私がつけたファイル名
（拡張子.ps を含む）で保存されます。そこで
% ghostview file.ps
と入力しリターンを押せば、ファイルが開きます。（file.ps が保存されている
ファイル名です。）なお、これらをたくさん保存するとディスククオータがいっぱいに
なるでしょうから、適宜削除してください。必要なときにはいつでも私のページから
ダウンロードできますから。
(2) .pdf ファイルの開き方（パソコンで
Adobe Acrobatというソフト（フリーソフトがあります。）をダウンロードする。
このページの.pdf版のところをクリックすれば自動的に開く。
.ps ファイルでも、自動的に.pdfに変換されるかもしれません。
パソコンに保存してからクリックして試してみてください。
なお、このページでとくに指定がなかったら、.ps fileです。
.pdf file はそのように明記してあります。

京都大学高崎金久先生の論理学のページ
論理学一般についての講義内容が公開されています。高崎先生の
許可を得ていますので、参考にしてください。ただし無断引用
は厳禁です。あくまでも理解を助けるための参考です。

模擬授業０２

命題論理の真理値の計算（テキスト3.1[2]）については９５年度の卒業研究と９７年度の
卒業研究でLISPという言語を使ったプログラムがあります。（下の二つ）

和積標準形（3.2[3]）

真理値表とワンのアルゴリズム（3.5[1]）

真理値の等式(.ps版)（3.1[2]）
真理値の等式(.pdf版)（3.1[2]）

論理式作成と論理パズルの例題（3章全般に関係する）

＜お話・数学基礎論＞
図書館に入っています。
ここに説明あり

講義目的(要旨)
コンピュータは概念と論理の機械であるから,コンピュータを理解するには基本的な数学の知識
が必要である。この講義は,情報系の分野を学ぶための,論理数学基礎コースである。
内容としては・集合・写像・関係, 命題論理,などの初歩の概説である。　
集合・写像・関係は,特にことばと表記法に重点をおく。プログラム理論の理解のための第1歩である。
命題論理はソフトウェア科学の基礎になる。特にワンのアルゴリズムという恒真性の判定方法をとりあげる。

授業内容・授業計画
I 論理：文の記号化,命題論理の式,式の真理値,結合子の相互関係,恒真性,ワンのアルゴリズム。
II 集合：集合の記法,部分集合,演算,直積,写像の定義,いろいろな写像,
写像のグラフ,関係の定義,関係と部分集合,同値関係, 順序関係,辞書式順序,整礎関係。
以上のトピックスを, 一回ごとに区切って講義する。場合によっては,二つのトピックを一回で終了する。

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

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

評価方法
学期中のレポートまたは小テスト、および期末テストの総合点。

教科書　「情報系の数学入門」　林・八杉著　オーム社
まず第３章、次に１章。３章の最後と２章は３年の科目でも使うので教科書を保存しておくこと。

上記の参照項目のほかに、楽しく論理を学ぶための参考書：「論理パズルとパズルの論理」　林・八杉著　遊星社
図書館にあります。

なぜ集合と論理が必要なの？

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

オンラインレポートシステムについて
授業登録が完了したころから、オンラインレポートシステムによる
課題提出や小テストを実施します。そのときに詳しく説明します。
Education Support System （課題出題・提出システム）にはここをクリックして入れます。
直接には https://ccwbt.kyoto-su.ac.jp/login.html

質問について
講義の間の質問は歓迎です。
講義の直後は私の時間はあいているので、皆さんの時間があれば
教室で質問してください。
時間がないときには、紙に質問を書いて渡してください。
次の講義のときに解答します。
オフィスアワーは別途掲示します。（「講義関係」の冒頭に）

２００２年度授業評価アンケートの意見

なぜ１０号館で、ウェッブを使っての授業か？

コンピュータで見るのは、かったるい。紙に印刷して配ってほしい。

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

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

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

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

演習問題は提出するわけではありません。各自解いてみて力をつけてください。
パズルランドのようにパズルを解くことに応用すると、楽しく勉強できると思います。

4月7日：上記の注意書の説明
３章　３・１　文の記号化(p.96) 文章の記号化とはどういうことか。
[1] 命題論理の式(p.96) 記号化した文章を（命題論理の）論理式、という。
その定義と例題
模擬授業０２を参照のこと

[例３・１] (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)

[演習問題] （論理式の作成とかっこ：3.1[1] p.97）
演習問題１（かっこをはずす問題）　：次の論理式から式の意味を変えないようにかっこをはずす。
（１）(((not X) or Y)==>X) and Z
（２）(not (X or Y))==>(X and Z)

解答 (1) (not X or Y==>X) and Z (2) not(X or Y)==>X and Z

演習問題　２（かっこを加える問題）：次の式に意味を変えないようにかっこをつけよ。
（１）not X and Y or Z ==>X
（２）(X ==> not X) and Y or Z

解答　(1) ((((not X) and Y)or Z)==>X) (2) (((X==>(not X))and Y)or Z
（一番外のかっこはあってもなくてもよい）

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

解答　(1) X: アキは赤いドレスが似合う　　Y: カズホはピンクのドレスが似合う
　とおくと、　X and Y

(2) P: お片付けする　Q: ケーキをあげる　とおくと、
(P==>Q)and(not P==>not Q)

４月１４日： (3.1[2]pp.98-100 ) 論理式の真理値（真理値とは、真理値の与え方、真理値表

４月２１日：真理値の計算の続き
自分で真理値表の計算をしてみること

[演習問題] ４(真理値の計算3/1[2]pp98-101）：次の論理式の真理値を計算せよ。
まず v(X)=T, v(Y)=F, v(Z)=T として、次にv(X)=F,v(Y)=T, v(Z)=T として。
１）　(X or Y)==>notZ
２）　(X==>notY) and Z
３）　Z and X or notY
４）　notnotX and Y
５）　X or Y and Z

解答　最初の真理値の与え方による：　１） v(X or Y)=T, v(not Z)=F, v((X or Y)==>not Z)=F
2) T 3) T 4) F 5) T
後の真理値による： 1) F; 2) v(X==> not Y) =T, v((X ==> not Y) and Z) = T
3) 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.

４月２８日には、初めての課題を出します。
課題解答の有無で、出欠記録に代えます。
初めてなので、今回のみ、２時限目と３時限目に解答できるようにしています。
次からは２時限目のみ解答可能にして、その時間で習ったことの
簡単な問題を出します。授業中よく聞いていてください。
多少複雑な課題は別途出します。それはあらかじめ知らせます。
なお、問題は一題１点です。たまに休んでも、ちょっと失敗しても
すぐに取り戻せるけれど、総合で２０点にしますので、
「塵も積もれば山となる」ですから、注意してください。

４月２８日：命題３．３(3.13.1[5]p103)の説明、応用

命題３・３に次を加える。
v(not not A)=v(A)

not not A のように否定が二つ続くことを「二重否定」という。
上の等式がなりたつことを「二重否定の除去」という。

命題３・３の証明を二つ示す。

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の真理値表と比較してみれば、完全に
一致することがわかる。

命題３・２や３・３のように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),v(B)の
例を考えてみてください。）この現象を「逆は必ずしも真ならず」という。

背理法は、対偶と二重否定の除去とde Morganの法則を使う。
すなわち、￢Ａ⇒X∧￢Xが示されたとする(すなわち、v(￢Ａ⇒X∧￢X)=T）。
（Aの否定から矛盾が生じた）
対偶により￢（X∧￢X）⇒￢￢A。de Morganの法則と二重否定の除去により

￢X∨X⇒A。￢X∨Xは排中律で、つねに成り立つ（値がT）ので、
v(￢X∨X⇒A)=T=v(A). ゆえに、Aがただしい。

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

演習問題　５（真理値に関する等式）

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

(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))

解答　(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) （命題３・３および３・１のド・モルガンの法則、分配律を使う）
v(￢A∨B⇒C)=v(￢(￢A∨B)∨C)=v(￢￢A∧￢B∨C)
=v(A∧￢B∨C)=v((A∨C)∧(￢B∨C))

演習問題　６（文章のいろいろな表現の仕方）
次の文を表す論理式を書き、命題３．３を使ってほかの論理結合子で表してみる。

（１）アキは赤いドレスが似合うが、カズホはピンクのドレスが似合う。

（２）お片づけしたらケーキあげる。でもお片付けしなかったらケーキあげない。

解答例 (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))=
v((K⇒C)∧(C⇒K))
最後の式を文章に戻すと、「お片づけしたらケーキをあげるし、
ケーキをあげたらお片づけする」となる。
なんだか変？

もっと変なのを教えてあげましょう。
「叱られないと勉強しない」って、よく言われることですよね。
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
が反例になっています。

課題１（４月２８日）解答

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

（２）　論理式　((X∧(￢Y))⇒((Z∨X)∧Y)) から、意味を変えずに
括弧をできるだけ除いた論理式を書いてください。
答え　X∧￢Y⇒(Z∨X)∧Y
注：　Z∧Y∨X∧Y は、この問題の解答としては適当でない。
しかし、真理値としては同じなので、今回は正解としました。

（３）　v(X)=T, v(Y)=F のとき、v(X∧￢Y) は T ですか、 F ですか？
正しいほうを書いてください。
答え　T （理由：このときv(￢Y)=T,　したがって、∧の真理値の定義から
v(X∧￢Y)=T

解答は（（２）を上のように拡大解釈して）全員合っていました。安心しました。

第二回課題を出します。5月12日2時限目の終りに実行します。

課題のための練習問題：論理式　￢(￢X⇒Y)　を、X,Y,￢,∧ で表せ。
すなわち、X,Y,￢,∧ のみから作られる（真理値が恒に同じ）論理式を
求めよ。また、その理由を示せ。

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

Attention! 第二回課題で苦労して入力できない人が大勢いたようです。
今回に限り、来週類似の問題を出して、解答者は今日の出席とみなします。
したがって来週は課題が二つあります。
2時限目のみ公開、というのでは入力できない人が続出しそうなので
あきらめました。３時限目まで延長します。
なお、今日正解を出した人はボーナス点を出します。

今日の課題の解答（これをよく勉強して、次に備えてください。）
(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).

５月１２日：命題論理の意味論（p.106, ３・２[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, 例３・４の、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)=G
以上よりすべての場合に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(￢(∨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にはT, ￢XにはFを与えれば、その基本和の
真理値はFになる。
このようにして、和積標準形の恒真性は、リテラルの形を見れば判定できる。
和積標準形が恒真でないことの判定には、一つの基本和が恒真でないことを
示せばよい。

すべての論理式は和積標準形に通ず！
p.110,[4] 命題３・８　にその手続きがある。

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

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

解答　（例） 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)はなんでもよい。
また、第二の基本和の真理値を計算する必要がない。

演習問題８　次の標準形について（真理値を計算しないで）恒真性を判定せよ。
恒真でないときにはその式を偽（F）にするような変数の真理値を一組与えよ。
a）　上の問題の１）－３）の式。
b）　A_4: ((not Y) or Z or Y) and (Z or X or Y or (not X))
答え　a)　1) たとえば最初の基本和のリテラルが X と not Y で共通の文字がないので恒真でない。
v(X)=F, v(Y)=T とすれば偽。
2) 最初の基本和のリテラルが X と Y だから、恒真でない。上に例が与えられている。
b) 最初の基本和に not Y と Y があり、後の基本和に X と not X があるので、恒真。

第三回課題だします。１９日２、３時限目に公開。

５月１９日：和積標準形への変換（pp.110-111[4]）

演習問題９次の論理式の和積標準形を求め、恒真かどうか判定せよ。
恒真でなければ、その式を偽にするように変数に真理値を与えよ。
１） (A=>B)and (not(A and notB))
２） (X and notY)=>X
３） (X and (notY or Z)) or (notX and (notY or Z))
４）お父さんからの電話「今駅だけど、何か買って帰ろうか？」
お母さん「別にいいわよ、雨が降っているから、早く帰っていらっしゃい」
お父さん「それじゃ、晴れてXCXCたら、早く帰らなくていいんだね？」
お母さん「？」（「論理パズルとパズルの論理」より）
お父さんの発言は、お母さんの発言の正しい結論になっているでしょうか？
５）お母さん「お片付けしたらおやつにしましょう」
１０分後にお母さん「お片付けしてないじゃないの。おやつにできないわ」
伸くん「でもお母さん、お片付けしなければおやつにしないとはいわなかったよ」
伸君の言い分は正しいでしょうか？
答え　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 or not X or not Y or Z) and (not Y or Z or not X or not Y or Z)
v(X)=v(Z)=F, v(Y)=Tとすれば全体は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 とはいえない。４）と同じ状況である。

２００２年度第一回レポート課題（解答つき）がここにあります。

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

第三回課題解答

(1) 　基本和　L_1: X∨Y∨￢X , L_2: Y∨Z∨￢X , L_3: Y∨￢Z∨X∨Z のうちで、恒真なものはどれか？
答え：　L_1, L_3。 L_1 ではXと￢X というリテラルの対がある。
L_3 では￢Z　と　Z　というリテラルの対がある。L_2　では異なる変数しかない。

(2) 恒真でない基本和の真理値がFになるような各変数の真理値を求めよ。
変数そのものが現れているときにはF,￢がついているときにはTにすればよい。
恒真でないのはL_2であるから、v(X)=T, v(Y)=F, v(Z)=F.

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

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

５月２６日：パズルを解く練習

第四回課題解答

(1) G:　（Y⇒X)∨（Y∧￢X)　の和積標準形（→は、命題３・８による変形を示す）
G→（￢Y∨X)∨（Y∧￢X)　（⇒の除去、（３））→（￢Y∨X∨Y)∧（￢Y∨X∨ ￢X) （∨と∧の分配、（５））
後の変形は、Aを（￢Y∨X)、BをY、Cを￢X、とおいて（５）の変形を行う。

(2) 恒真である。なぜならば、二つの基本和にそれぞれ　￢YとY、Xと￢X　があるから。

パズルを解こう：和積標準形と分解の木による解決の例（ここでは和積標準形で考えてください）

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

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

解答

１　P: 加奈が風邪をひいている　
　加奈の発言： (P==>notP)==>P
和積標準形： P or P ゆえに恒真ではない
分解の木：（下から順に） P==>notP | P; notP | P | P,P; | P,P | P,P
少なくとも一つの最上シークエントが左右に同じ変数がない、ゆえに恒真ではない

このページの冒頭にあるパズルの例も解いてみてください。

第５回課題解答
「カナは天使」を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)と書く。

第一回レポート問題(.ps版)について
第一回レポート問題(.pdf版)について

教室でハードコピーを配布しますが、ここにもファイルをおいておきます。
これはできるだけ複数人数で共同で解答してください。したがって提出は
一グループ一枚でいいです。解答用紙は返却しませんから、余分の用紙に答えを
控えておいてください。後日解答をここにおきます。
複数で提出の理由は、共同で考えることは学習効果を高めるからです。
もちろん各自真剣に考えれば、ですよ！
なお、提出日の訂正があります。「６月２８日」はウソです！

正しい提出日は：　６月１６日

６月２日：ペーパーレポート配布（６月１６日提出）
第一章「集合・写像・関係」スタート。pp2-5, 1.1[1],[2]
テキストの内容とともに、ここの以下の説明もよく読んでください。

これから第１章の集合・写像・関係に入ります。

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

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

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

にもあります。

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

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

６月９日：部分集合と集合の演算（[3],pp.5-6, [4],[5],pp6-9）

集合の例題

Attention! 次回（６月１６日）は、Education Support Systemによる課題は無し！
そのかわり、ペーパーレポート提出

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

入力しにくい記号は、自分で決めて「・・・と表す」と明記して
使ってけっこうです。いくつか典型的な使い方を書いておきます。
和集合：cup （例 A cup B）、共通部分 : cap（例 A cap B）、補集合：例 A^c
「xがAの要素である」は xΕA、xεA などと表される。
Ε、ε はどちらも「いぷしろん」と入力して変換すれば
たいてい出てくる。それも無理なときには「x blongsto A」,
「x is an element of A」、「x は A の要素」などと書けばよい。
ほかにも、記号に困ったら知らせてください。

1.1[5]p.8 集合の演算に関する等式の補足
補足の補足

訂正：　２　問題　3. (1) (A cap B^c)^c =A^c cap B （誤）
正しい設問は　(A cap B^c)^c = A^c cup B です。

第六回課題解答
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}
3) 好きな集合の例（ほんとは好きでなくていいですよ！）
{xεR| x is in [-1,1]}, 仲よし={花子、梅子、桜子、松子、竹子}, {x|xは国、xの首都の人口が800万以上}などなど

第一回ペーパーレポート解答

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

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

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

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

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

月日：20ページー22ページ、[7]恒等写像、[9]写像のグラフ
多価写像は範囲外。この科目で「写像」といえば一価写像と考えてよい。
写像の「グラフ」は重要なので、よく理解すること。
例　sin x のグラフ= {＜x,sin x＞ | x in R}、ただし"x in R"は「xがR（実数の集合）の要素」を表す
14 ページ、例１・１０　の　（３）のグラフ={＜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,...}

[和積標準形についての注意]：和積標準形は「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 もみとめられることに注意。
したがって一つのリテラルも基本和である。極端な例では一つのリテラルは
和積標準形なのである！

２００２年度第二回レポート課題参考にしてください。

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

1. ８ページの命題１・２の等式。
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

直積は１１ページの定義以外にはとくにいうことはないですが、とても大事なものです。
次のそれぞれ二つの集合の直積を記述し、それから作れる表を考えてください。
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才の年齢を表す。

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

[写像の勉強の仕方]：まずテキストの例題をよく読んで、基本的な性質
（全域的、部分的、単射、全射、逆写像）の例を理解してください。
それらのうち理解できない例があれば質問してください。
次に自分で写像を定義してみてください。数学における関数でも日常生活における対応でもいいです。
＊写像のグラフについて、数行のレポートを書いてみてください。
写像に対応する集合、ある性質をもつ集合から定義される写像、例、など。
これは成績には関係なく、強制ではありませんが、書いて提出したら見てあげます。

第8回課題解答

（１）　(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) のそれぞれは、命題１・２の等式の
どれを使っているか、等式の名称を書いてください。

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

（２）　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)も順序対です。ふつうはこの記法を使います。

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

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

６月３０日：写像の性質（単射、全射）、逆写像、写像の合成、恒等写像、
写像のグラフ、写像のグラフと直積集合の部分集合の関係。

写像の問題
次の写像について、全域的、部分的、単射、全射、のうち当てはまるのはどれか？
1. f:R→R, f(x) = 1/x; 2. f: X={x| x>0} →R,　 f(x)=1/x; 3. f: R→R,　ｆ（ｘ）＝√(1-x);
4. P = 人々の集合, N={1,2,3,...}, C={x| x は国}, psprt: P →　CxN （Cと Nの直積集合）,
P(person) = , 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. 部分、単；　２．　全域、単；　３．　部分、単；　４．　部分、単；　５．　部分、　（単射としてもよいが、
複数の国の旅券保持者もいるので、事実上は単射でない）；　６．部分、全；　７．　全域、単

期末試験について

テキストの1章、3章のうち、実際に講義をした個所（このページに書いてある）
全体から出題する。集合の演算、写像のいろいろな性質とグラフ、
関係の基本的な性質、命題論理の基本（論理パズルと標準形）
などです。今までの課題、レポート程度なので、これらの正解を
よく理解しておくこと。また、過去の問題がこのページにあるので、
解いてみるといい。「皆さんの問題」も良い勉強になります。
配点は、（課題＋レポート）/期末試験＝ 30/70 です。

第九回課題解答：この課題は写像の書き方と基本的な性質の理解を問うものです。

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

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

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

２００２年度小テスト解答つき。参考にしてください。

去年の経験では、和積標準形を覚えたら、真理値を忘れた人がいるようです。
どちらも大事です。

[関係について]：関係は一般に異なる集合の直積の上で定義される。
たとえば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 は（平面内の）３点で三角形を形成する

演習問題１０(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

第１章全体について：「集合・写像・関係」の間の関係（わかりにくいね！）

写像によって定義されるグラフの例：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を値としてとる関数

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

第十回課題解答

(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版) 第二回ペーパレポート解答つき(.pdf版)

期末試験のための質問の時間

7月22日（火） 3:30pm->4:30pm
この時間帯に都合つかない場合にはメールで連絡くささい。
yasugi@cc
なお、最後の課題、ペーパレポート結果および今までの総合点も
このときに見れます。解答は後でここに書きます。

第１１回課題解答つき

１．　次に挙げるのはすべて２項関係である。
(1) R_1(a,b): a と b は正整数で、同じ素数で割り切れる。
(2) R_2(a,b): a と b は正整数で、a-b が３で割り切れる。
(3) R_3(a,b): a と b は正整数で、a は b を割り切る。
（自分を割り切ることも認める。また１はすべての数を割り切るものとする。）
(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＝ｂ　のとき、R_6(a,b)は成り立たないものとする。）
以上のうち、次に相当する関係の番号を記入してください。
（一項目に複数の番号が相当するかもしれないし、一つも相当しないかもしれない。）
関係の性質と解答が同時に書いてある。 (b) 半順序関係であって、全順序関係でない: (3)
(c) 厳密な意味での全順序関係: (6)
(d) 整礎関係: (6)

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

合否について
この科目の最終的な合否結果は、ウェッブページの”科目合否”
（八杉のHP→講義関係→科目合否）に、「不合格者」の学籍番号のみを
掲載します（７月終わりから９月末まで）ので、早めに知りたい人はそこで確認
してください。個々の問い合わせには応じかねます。

期末試験解答について
９月半ば頃にここに掲載します。

Last modified: Sun Feb 1 12:20:58 JST 2004