電気通信大学 2016年度 I科 離散数学
ランク分け用の証明問題が難しかったり。
下記のすべての問いに答えよ。質問は認めない。疑問点がある場合には、その疑問点を指摘したうえで適当な仮定を設けて解答すること。整数集合を「Z」と記す。
１．
(1)α、βを命題変数とする。命題論理式 α∧β α∨β ¬α∧β ¬α∨β α→β の真理値表を作れ。
(2)命題論理式に関するドモルガン則を示せ。
(3)普遍集合を「Z」としたとき、以下の術語論理式が真であるか偽であるかを理由を付けて述べよ。
a) (∃x)(∃y)(x-y=0)
b) (∃x)(∀y)(x-y=0)
c) (∀x)(∃y)(x-y=0)
d) (∀x)(∀y)(x-y=0)
２．以下の各関係について、反射率、推移律、対称律、反対称律、非対称律のそれぞれを満たしているか否かを、満たす場合には○、満たさない場合には×で答えよ。
1) (「Z」,R1), R1={〈x,y〉|x-y≧0}
2) (「Z」,R2), R2={〈x,y〉|x-y＞0}
3) (「Z」,R3), R3={〈x,y〉|x-y＝0}
4) (「Z」,R4), R4={〈x,y〉|xy≧0}
5) (「Z」,R5), R5={〈x,y〉|xy≦0}
３．任意のグラフG＝(V,E) に対し、頂点数をn、辺数をmとする。辺(x,y)∈E は頂点x,yに接続するという。頂点v∈V に接続する辺の数を「vの次数」といい、deg(v)と書く。グラフは単純グラフとし、Gが平面グラフの場合にその面の数をfとする。
1)連結な平面グラフにおいて、n,m,f間に成立するオイラーの多面体公式を書け。
2)グラフ上の全頂点の次数の和(Σdeg(v))は、辺の数の2倍(2m)になることを証明せよ。
3)平面グラフにおいては 3f≦ 2m が成立する。以上より、任意の連結平面グラフには次数5以下の頂点が存在することを証明せよ。
P.S.(ページ管理者から)
疑問点は質問できないのでそのまま記述したが、おそらくこれが正しいと思う。
１．(2)示せ：単に書くのではなく証明する。
２．反射率：反射律が正しい。