一.(8分)求与公式(x2ornotx1)->x3逻辑等值的主合取范式和主析取范式.

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

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

(2)(notporq)<->(pand(pandq))

(3)(notporq)andnot(qornotr)andnot(rornotpornotq)

(4)(qandp)->(porq)

三.(9分)问anyxexistyP(x,y)->existyanyxP(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:

anya,binG,aRb<=>存在h,kink,使得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的划分,即V1orV2=V,V1andV2=null,且V1!=null,V2!=null,则V1与V2

间的最短边一定在G的最小生成树上.

以上是：1999年中科院计算机技术研究所硕士生入学试题（离散数学），希望对考生有所帮助。