离散期中练习答案

1、1. 将下列命题符号化：(1) 要是明天不下雨且我有时间，那么我去步行街购物。解：令p：明天下雨，q：我有时间，r :我去步行街购物。(n pA q)f r(2) 如果小王和小张是一个组，那么这次英语竞赛一定取胜。解：令p：小王和小张是一个组，q：这次英语竞赛一定取胜。 pq(3) 除非天下雨，否则他不乘出租车上班。 解：令p：天下雨，q：他乘出租车上班q p(4) 明天既不是晴天也不是下雨天。解：令p：明天是晴天，q：明天是下雨天n pAn q2. 设命题公式G= (P (Q R)，则使公式G为真的解释有(1,0, 0), (1,0,1), (1,1, 0).3. 通过求主析取范式判断下列命

2、题公式是否等价：(1) G = (P A Q)V( PA QA R)(2) H = (P V (QA R) A (QV( PA R)解：G = (P A Q)V( PA QA R)=(P A QAR)V (P A QA R)V( PA QA R)=n6 Vm7Vm3二(3, 6, 7)H = (P V (QA R) A (QV( PA R)=(P A Q)V (QA R) V(PA QA R)=(PA QAR)V (P A QA R)V( PA QA R)V (P A QA R)V(PA QA R)=(P A QAR)V( PA QA R)V (P A QA R)=m6 Vm3 Vm74. 设

3、命题公式G =(PQ)V (QA( P R),求G的主析取范式。G =(PQ)V(QA(PR)=(PV Q)V (QA (P V R)=(P A Q)V (QA (P V R)=(P A Q)V (QA P) V (QA R)(P A QA R)V (P A QA R)V (P A QA R)V (P A QA R)V (P A QA R)V( PA Q R)=(P AQAR)V (P AQAR)V (P A QAR)V (P A QAR)V(PAQAR)=m3 Vm4Vm5 VimVm7 =(3, 4, 5, 6, 7)= n(0, 1, 2)5.公式p(q tr)在联结词全功能集n,A 中

4、等值形式之一为n(pA qAn r)6.构造下面推理的证明:前提:AV B,CT B, C td结论:ATD证明:(1) A附加前提引入AVB前提引入Ct析取三段论(1)(2)前提引入拒取式(3) (4)CTD前提引入(8) D假言推理(5) (6)由附加前提证明法可知，推理正确。7、设F(x) : x是鸟，G(x) : x会飞翔。则命题“鸟都会飞”符号化为 x(F(x)-G(x)8设谓词的定义域为a, b,将表达式 xR(x) t xS(x)中量词消除，写成与之对应的命题公式是 R(a) ? R(b) tS(a)? S(b) 9.设一阶逻辑公式：G= ( xP(x) V yQ(y) T xR

5、(x)，把G化成前束范式.x y z( P(x) ?Q(y) ? R(z)10 设集合 A,B,其中 A= 1,2,3,B=1,2, 则 A - B=P(A) - P(B)；3,1,3,2,3,1,2,3.11.设有限集 A, B , |A| = m, |B| = n, 则 | |P(A B)| =2.2m n12某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打 篮球和网球，还有2人会打这三种球。 而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：| A| = 12 ,|B|= 6,|C =

6、14,|AAC = 6, | BA C = 5, |AABAC = 2, |(AUC)nB|= 6。因为 |( au C) n B| = (An B) u(BnQ| =|( An b)| +1( Bn c)| -1 An baq = |( AnB)| +5-2 = 6,所以 |( AA B)| = 3。于是 | AU BU C| = 12+ 6 + 14-6 5-3+ 2= 20, |A B C | = 25- 20= 5。故，不会打这三种球的共5人。13.设集合A= 2, 3, 4, 5, 6, R是A上的整除，则R以集合形式(列举法)记为(2, 2),(2, 4),(2, 6),(3, 3

7、),(3, 6),(4, 4),(5, 5),(6, 6).14 设 A、B C 和 D 为任意集合，证明(A B) x C= (Ax C) - (Bx C)。证明：因为 (A- B) x C x (A- B) A y C(x AA xB) A y C(x AA y CA X B) V (X AA y CA y C(x AAy C A ( x BV yC(x AAy C A ( x BA y C (Ax C A (Bx C) (Ax C (Bx C)所以，(A B) xq= (Ax q- bx c。15.设集合 A= 1,2,3,4, A 上的关系 R = , R =, 贝 U Ri F2 =

8、 ,R 2 R1 =,R2 =, , , ; , .A且x y, 求16 设集合 A= 1,2, 3, 4, A上的关系 R= (x,y) | x, y(1) 画出R的关系图;(2) 写出R的关系矩阵.答：R = , , , , , , , , , .(1)0 0 0Mr1 0 01 1 01 1 117 设 S=1,2,3,4,R=,，贝U R具备哪些性质(自反，反自反，对称,反对称，传递)？对称、反对称、传递的18集合A=a, b, c, d, e上的一兀关系R为R=, , , ,(1)写出R的关系矩阵。(2)判断R疋不疋偏序关系，为什么？解(1) R的关系矩阵为：1111 10110 1

9、M (R)0010 10001 10000 1(2)由关系矩阵可知，对角线上所有元素全:为1，故R是自反的；rj + rjiw 1,故R是反对称的；可计算 rR对应的关系矩阵为：1111101101M (R2)00101 M (R)0001100001由以上矩阵可知 R是传递的。19.设 R是集合 A = a, b, c, d. R 是 A上的二元关系,R = , , , , 求出 r(R), s(R), t(R) ;(2)画出r(R), s(R), t(R) 的关系图.答.(1) r(R)= RUI a= , , , , , , ,1s(R) = RUR = , , , , ,234t(R)

10、 = RUR UR UR = , , , , , , , , ;关系图：20若S=1, 2, 3,19, 20，设R为S上的等价关系，且由x三y (mod5)所定义，即x ,y除5同余。写出由R导出的S的划分和商集S/R。r(R)s(R)S/R=1,6,11,16,2,7,12,17,3,8,13,18,4,9,14,19,5,10,15,2021 设集合 A= 1,2, 3, 4, 6, 8, 9, 12, R为整除关系。(1) 画出偏序集(A,R)的哈斯图；(2) 写出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界;(3) 写出A的最大元，最小元，极大元，极小元。(1)12423(2) B无上界，也无最小上界。下界1,3;最大下界是3.(3) A无最大兀，最小兀是1,极大兀8,12, 9; 极小兀是1.其中双射的是哪些？4= ( a,2), (b,1);(x) = 2x,(x)22设集合A = a, b, B = 1,2, 则从A到B的所有映射有哪些？1 = ( a,1), (b,1),2= ( a,2), ( b,2),3= ( a,1), ( b,2),3,4.23 R是实