中科院計算機技術研究所1999年碩士研究生入學考試試題 離散數學

中科院計算機技術研究所1999年碩士研究生入學考試試題離散數學

一.(8分)求與公式(x2 or not x1)->x3邏輯等值的主合取範式和主析取範式.

二.(8分)判斷下列各公式是: 1.永真式2.永假式3.其它

(1) (p->(q->r))->(q->(p->r))

(2) (not p or q)<->(p and(p and q))

(3) (not p or q)and not(q or not r)and not(r or not p or not q)

(4) (q and p)->(p or q)

三.(9分)問any x exist y P(x,y)->exist y any x P(x,y)是否謂詞演算的有效式?證明你的結論.

四.(9分)將下列推理符號化並給出形式證明:

鳥會飛,猴子不會飛;所以,猴子不是鳥.

五.(12分)令X={x1,x2,...,xm},Y={y1,y2,...,yn},問:

(1)有多少不同的由X到Y的關係?

(2)有多少不同的由X到Y的影射?

(3)有多少不同的由X到Y的單射，雙射?

六.(8分)設e是奇數階交換群G的單元位,試證:G的所有元素之積為e.

七.(15分)①是個群,H,K是其子群,在G上定義二元關係R:

any a,b in G,aRb <=>存在h,k in k,使得b=h*a*k,證明:R是G上的等價關係.

②在①中,若|H|=m,|K|=n,|G|=mn,m與n互素,且R的某個等價類在G的乘法

運算下構成G的一個子群,則R=G*G.

八.(8分)把平麵分成β個區域,每兩個區域都相鄰,問β最大為幾?

九.(11分)設G為非平凡有向圖,V(G)為G的結點集合,若對V(G)的任意非空子集S,

G中起始結點在S中,終止結點在V(G) S中的有向邊都至少有k條,則稱G是k邊

連通的.證明:非平凡有向圖G是強連通的充要條件是他是1邊連通的.

十.(12分)設G是一無向加權圖且各邊的權不相等,V,E分別是G的結點集合和邊的集合,

(V1,V2)是V的劃分,即V1 or V2 = V, V1 and V2=null,且V1!=null,V2!=null,則V1與V2

間的最短邊一定在G的最小生成樹上.

中科院計算機技術研究所1999年碩士研究生入學考試試題離散數學參考答案

一.主合取範式: (not x1 or not x2 or x3)and(x1 or not x2 or x3) and (x1 or x2 or x3)

主析取範式: (x1 and not x2 and not x3)or(x1 and x2 and x3)or(x1 and not x2 and

x3) or (not x1 and x2 and x3)or (not x
..............................