离散数学复习题(共3页).doc

《离散数学复习题(共3页).doc》由会员分享，可在线阅读，更多相关《离散数学复习题(共3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上离散数学复习题1.设S = 2，a，3，4，R =a，3，4，1，指出下面的写法哪些是对的，哪些是错的？aS,aR,a,4,3S,a,1,3,4R,R=S,aS,aR,R,aRE,S,R,3,4。2 写出下面集合的幂集合a，b，1，X，Y，Z解： 设A=a，b，则(A)= ，a，b，a，b；设B=1，则(B)= ，1，1，；设C=X，Y，Z，则(C)= ，X，Y，Z，X，Y ，X，Z ， Y， Z ，X，Y，Z；3.设A,B,C 为任意三个集合，下列各式对否？并证明你的结论。（1）若AB 且BC，则AC；（2）若AB 且BC，则AC；（3）若AB 且BC，则AC；（4

2、）若AB 且BC，则AC。解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不正确，举一个反例即可。4.设A，B 是两个集合，问在什么条件下有ABA 成立？等号能成立吗？解：当A 或B 为空集时能够成立；当A 为空集时等号能够成立。5计算:a,b,a一个班有50个学生，在第一次考试中得95分的学生有26人，在第二次考试中得95分的人有21人，如果两次考试中没有得95分的学生有17人，那么两次考试都得95分的学生有多少人？6.设A 是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A=a，b，B=1， 2，试写出A 到B 上的全部二元关系。解：A 到B

3、 上共有2mn 个二元关系。本题中AB 的全部子集，(a,1)，(a,2)，(b,1)，(b,2)， (a,1),(a,2)，(a,1),(b,1)，(a,1),(b,2)，(a,1),(b,2)，(a,2),(b,1)，(a,2),(b,2)，(a,1),(a,2),(b,1)，(a,1),(a,2),(b,2)，(a,1),(b,1),(b,2)，(a,2),(b,1),(b,2)，(a,1),(a,2),(b,1),(b,2)为A 到B 的全部二元关系。7映射的乘法是否满足结合律；举例说明：映射的乘法不满足交换律。8计算:设R1、R2是集合A=a,b,c,d上的二元关系，R1=(a,a)

4、,(a,b),(b,d)，R2=(a,d),(b,c),(b,d), (c,d),，求R1oR2,R2oR1 9. 给P 和Q 指派真值1，给R 和S 指派真值0，求出下面命题的真值：a) (P(QR)(PQ)(RS)b) (PQ)R)(PQ)R)S)c) (PQ)R)(QP)(RS)d) (P(Q(RP)(QS)10画出命题公式(PQ)R的真值表,并求出其成真指派和成假指派.11证明命题公式等价(1) (P(QR)(QR)(PR)=R(2) P(QP)=P(PQ)(3) P(QR)=(PQ)(PR)(4) (PQ)(RQ)=(PR)Q(5) P(QR) Q ( P R)12写出G=P(QR)

5、的对偶式G*13求出下列命题公式的的主析取范式和主合取范式.(1) P(PQ)(QP)=P(PQ) QP)=P(QP)=(P (QQ) (QP)=(P Q) (PQ) (QP) (主析取范式)=P(QP)=(PQ) (PP)=PQ （主合取范式）(2) P(P(Q(QR)=P(P(Q(QR)=P(PQR)=PQR =(P(Q Q) (RR) (Q(P P) (RR) (R(P P) (QQ)=(PQR)(PQR) (PQR) (PQR) (QPR) (QPR) (QPR) (QPR) (RPQ) (RPQ) (RPQ) (RPQ)=(PQR)(PQR) (PQR) (PQR) (QPR) (Q

6、PR) (RPQ)=(PQR)(PQR) (PQR) (PQR) (PQR) (PQR) (PQ R)14判断下列命题公式的类型（1）(P(QR)(P(QR)；（可满足）（2）P(P(QP)；（恒真）（3） (QP)(PQ)；（恒假）（4）(PQ)(PQ)。（可满足）15.构造法证明:CD，(CD)H，H(AB)，(AB)(RS)共同蕴涵RS。证明：1) CD 规则P2) (CD)H 规则P3) H 规则T(1),2)4) H(AB) 规则P5) (AB) 规则T( 3),4)6) (AB)(RS) 规则P7) RS 规则T( 5),6)PQ，QR，RS共同蕴涵PS。证明：1) PQ 规则12

7、) P 规则3（附加前提）3)Q 规则2，根据1),2)4) QR 规则15)R 规则2，根据3),4)6) RS 规则17)S 规则2，根据5),6)8) PS 规则3，根据2),7)16.设下面所有谓词的定义域都是a，b，c。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1) xR(x)xS(x)(2) x(P(x)Q(x)(3) xP(x)xP(x)解： （1） xR(x)xS(x)等价的命题公式为：R(a) R(b) R(c) ( S(a) S(b) S(c)（2） x(P(x)Q(x)等价的命题公式为：(P(a)Q(a) (P(b)Q(b) (P(c)Q(c)（3）xP(x

8、)xP(x)等价的命题公式为：(P (a) P (b) P (b) (P (a) P (b) P (b)17指出下列表达式中的自由变量和约束变量，并指明量词的作用域：（1）(xP(x)xQ(x)(xP(x)Q(y)（2）xy(P(x)Q(y)zR(z)（3）A(z)(xyB(x，y，a)（4）x A(x)yB(x，y)（5）(xF(x)yG(x，y，z)zH(x，y，z)解： （1）中的自由变量是Q(y)中的y，约束变量是P(x)、Q(x)和P(x)中的x，第一个量词x 的作用域是P(x)，第2 个量词x 的作用域是Q(x)，第三个量词x 的作用域是P(x)。（2）此式中没有自由变量，x，y，

9、z 都是约束变量，x 和y 的作用域都是(P(x)Q(y)zR(z)，而z 的作用域是R(z)。（3）z 是自由变量，x 和y 是约束变量，xy 的作用域是B(x，y，a)。（4）x 是自由变量，x 和y 是约束变量，x 的作用域是A(x)，y 的作用域是B(x，y)。（5）x，y 和z 是自由变量并且x，y 和z 又是约束变量，x 的作用域是F(x)，y 的作用域是G(x，y，z)，z 的作用域是H(x，y，z)。18.试将下列公式化成等价的前束范式：(1)x(P(x)yQ(x，y)；=x(P(x) y Q(x，y)=xy(P(x) Q(x，y)(2)x(yP(x，y)(zQ(z)R(x)；=x(yP(x，y) (zQ(z) R(x)=x(yP(x，y) (zQ(z) R(x)=x(yP(x，y) (z (Q(z) R(x)=xy (P(x，y) (z (Q(z) R(x)=xyz (P(x，y) Q(z) R(x) )专心-专注-专业