集合と論理２０００年度

以下の項目を参照のこと。また、手渡ししたプリントの注意事項を良く読むこと。
論理を優しく学びたい人のために

５月９日まで
テキスト３章の以下の項目を終：3.1 の[1],[2],[5]、3.2の[1],[3],[4]
3.5[1]の説明まで。
「命題論理の論理式の例題」のプリントを配布。
レポートの作成のためのグループをつくっておくこと。

５月16日：レポート課題配布。問題練習
次回は１０号館１０２０２へ。

１０号館で講義科目のウエッブページをみる。とくに９９年度集合と論理の演習問題。

＊演習問題解答：９９年度の「集合と論理」の演習問題の答えをここに逐次書きます。
解答がまちがっていたり不備の場合には連絡をくださいね！

演習問題１：次の論理式から式の意味を変えないようにかっこをはずす。
（１）(((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)

演習問題４　（なぜか１から４へとぶ）変数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))
３）A_3: 自分で和積標準形を定義する。
答え（例） 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）にするような変数の真理値を一組与えよ。
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 があるので、恒真。

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

5月３０日：プリントの問題の練習、ワンのアルゴリズムの導入（次回に詳しくする）

6月6日：ワンのアルゴリズムの説明、演習問題

第一回レポート提出

注意！第一回小テスト：6月27日（火曜日３限）３０分程度
範囲は今日までのすべて（命題論理の式、真理値、和積標準形、ワンのアルゴリズム）
過去の小テストが参考になる。後日類似問題を書きます。

和積標準形と分解の木による解決の例

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

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

解答

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

小テスト（６月２７日）は、次のような問題を２題出します。このページの演習問題の
やさしい問題ができれば、だいじょうぶです。

２変数の論理式の和積標準形を作り、それが恒真かどうか
「判定し、恒真ならばその理由を述べ、恒真でなければ、その式を偽にする変数の
真理値を一組あたえる。」

6月２７日まで：集合と写像（テキストの１章、無限演算は除く）２７日：小テスト

小テストの解答はここ

7月4日：レポート２課題配布、前回と同じ要領で作成、提出（7月11日）
逆写像、写像の合成、写像のグラフ、半順序、全順序関係

＊　期末試験傾向と対策：写像の性質（単射など）、写像のグラフ、関係の種類（同値関係、半順序、整礎など）
簡単な例でこれらのことがわかればよい

９９年度の集合と論理の問題なども参考にしてください。

最後の時間には問題を解いたり質問を受けたりします。

質問ができるように勉強しておいてください。

試験はどうでしたか？後で正解をここ

に貼っておきます。それを見て、自分の大体の点数を計算してみてください。

とりあえず成績の算出方法を書いておきます。　2回のレポートと１回の小テストの総計が７０点、期末試験が３０点、

合計１００点。したがってそれぞれの成績の合計がそのまま最終成績になっています。結果として、レポートと試験を

すべて提出している人は合格、一つでも欠けると不合格になっています。なお、期末試験を受験しない場合は

欠席扱いになります。

全体として良いクラスだったと思います。何か感想があれば、メールをください。ccでyasugiあてでけっこうです。

秋学期は一年生の講義はもっていませんので、来年代数・幾何Ｂでお会いしましょう。

八杉　　Ｈ12年7月27日

Last modified: Sun Jul 30 00:46:32 JST 2000