离散数学复习题(共3页).doc
精选优质文档-倾情为你奉上离散数学复习题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）若AB 且BC，则AC。解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不正确，举一个反例即可。4.设A，B 是两个集合，问在什么条件下有A×BA 成立？等号能成立吗？解：当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 上共有2mn 个二元关系。本题中A×B 的全部子集，(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),(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)(Q¬P)(R¬S)d) (P(Q(R¬P)(Q¬S)10画出命题公式(P®Q)ÙØ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®(Q®R)Û Q ®( P ®R)12写出G=ØPÚ(ØQÙR)的对偶式G*13求出下列命题公式的的主析取范式和主合取范式.(1) P(PQ)¬(¬Q¬P)=¬P(¬PQ) QP)=¬P(QP)=(¬P (Q¬Q) (QP)=(¬P Q) (¬P¬Q) (QP) (主析取范式)=¬P(QP)=(¬PQ) (¬PP)=¬PQ （主合取范式）(2) P(¬P(Q(¬QR)=P(P(Q(QR)=P(PQR)=PQR =(P(Q¬ Q) (R¬R) (Q(P¬ P) (R¬R) (R(P¬ P) (Q¬Q)=(PQR)(P¬QR) (PQ¬R) (P¬Q¬R) (QPR) (Q¬PR) (QP¬R) (Q¬P¬R) (RPQ) (R¬PQ) (RP¬Q) (R¬P¬Q)=(PQR)(P¬QR) (PQ¬R) (P¬Q¬R) (Q¬PR) (Q¬P¬R) (R¬P¬Q)=(PQR)(P¬QR) (PQ¬R) (P¬Q¬R) (¬PQR) (¬PQ¬R) (¬P¬Q R)14判断下列命题公式的类型（1）(P(QR)(¬P(¬Q¬R)；（可满足）（2）P(P(QP)；（恒真）（3） (QP)(¬PQ)；（恒假）（4）(¬P¬Q)(P¬Q)。（可满足）15.构造法证明:CD，(CD)¬H，¬H(A¬B)，(A¬B)(RS)共同蕴涵RS。证明：1) CD 规则P2) (CD)¬H 规则P3) ¬H 规则T(1),2)4) ¬H(A¬B) 规则P5) (A¬B) 规则T( 3),4)6) (A¬B)(RS) 规则P7) RS 规则T( 5),6)¬PQ，¬QR，RS共同蕴涵PS。证明：1) ¬PQ 规则12) 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) x¬P(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）x¬P(x)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，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) )专心-专注-专业
