离散数学复习题

• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值

为 。

• 只要4不是素数，3就是素数，用谓语表达式符号化为 。 • D=｛｝，则幂集ρ(D)= • A={a,{b}}，B=｛｝，则A×B=

• 若集合A，B的元素个数分别为|A|=m,|B|=n,则A到B有 种不同二元关系。 • 设A=｛1,2,3,4｝，B=｛4,5，6,7｝，R=｛<1,4>，<1,6><2,4>，<3,5>，<3,6>｝是由A

到B的二元关系，则domR= ，ranR=

• I A是集合A上的恒等关系，A上的关系R具有 性当且仅当IAR。 • 二元关系R是等价关系，当且仅当的R是 ， ，

。

9.设K4是有4个点的无向完全图，则K4有 条边。 10.无向图G是欧拉图当且仅当 。

11.在任何无向图这，所有顶点的度数之和等于边数的 倍。 12.设K5是有5个点的无向完全图，则K5有 条边。 13.无向图G是欧拉图当且仅当 。 计算题

• 求公式（PQ）→（QR）的主析取范式

• 集合A=｛a,b,c｝,R={,,,}是集合A上的二元关系，求R的自反

闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算)，并画出各闭包的关系图。 • 设图G

• 写出G的邻接矩阵 • 求各结点的初度，入度 • 求V3到V2长度是3的路的数目

• 设集合A=｛1,2，3,4,6,8，12｝，R是A上的整除关系，

• 画出偏序图的哈斯图； 证明题

• 在自然推理系统p中构造下面推理的证明 前提：﹁r，﹁pr，（q）→p 结论：q→﹁

• 在自然系统p中构造下面推理的证明 前提：pq,p→r,q→s 结论：sr