离散复习题doc.doc

一、将下列命题或谓词符号化1、老王是山东人或河北人。2、若地球上没有树木，则人类不能生存。3、224当且仅当336。4、有的人登上过月球。5、有的人用左手写字。1、pq，其中，p：老王是山东人，q：老王是河北人。2、pq，其中，p：地球上有树木，q：人类能生存。3、pq，其中，p：224，q：336，真值为1。4、令M(x):x为人，G(x):x登上过月球。命题(2)的符号化形式为：x(M(x)G(x)5、令M(x):x是人，G(x):x用左手写字；符号化为：x(M(x)G(x)二、计算与说明题1、用等值演算法判断(pq)rp的类型2、求pq的主合取范式3、已知 = ，求x和y。4、B=a，b，求P(B) 5、R=，；求R-1 6、无向树T有1个2度顶点，3个3度顶点，4个4度顶点，1个5度顶点，其余的都是树叶，则T有几片树叶？7、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，求其树叶数。8、求的主析取范式和成真赋值；9、设表达式为1）求表达式树；2）前序遍历该表达式树；3）后序遍历该表达式树；答案1、 (pq)rp (pq)qr p(qq)r p0r 0 它为矛盾式。2、pqpq M2 3、由有序对相等的充要条件有x-2=4，x-y=6 3分 解得x=6，y=04、P(B)，a，b，a，b 5、R-1=，6、设T有x片树叶，由定理16.1和握手定理，有 1*2+3*3+4*4+1*5+x=2(1+3+4+1+x-1) 解得 x=16 7、设树叶数为， 树枝数为， 由握手定理有： 故 8、 成真赋值：001、011、100、111 1）表达式树：2）前序遍历： 3）后序遍历： 三、A=1，2，3, R=|x，yA且x+3y8，S=， 1、R的集合表达式；2、R-13、RS，R3；答案1、R=,；2、R-1=,3、RS=, R3=,；四、为群，其中，为模加法；1）求幺元（单位元）；2）求；3）计算；解：1）； 2）； 3） 五、证明题1、在自然推理系统P中构造下面推理的证明前提：pq, rq ,rs 结论：ps证明： pq 前提引入 pq 置换 rq 前提引入 qr 置换 pr 假言三段论 rs 前提引入 ps 假言三段论2、设是自然数集，定义上的二元关系，则是等价关系。证： 是偶数，故自反； 若即是偶数，则也是偶数，故对称； 若，即，是偶数，则 是偶数，故传递； 综上所述，是等价关系下列3）六、A=1，2，3，4上的关系R的关系矩阵，求：1、R2、R的关系图G；3、图G的邻接矩阵A；4、顶点2到顶点3长度为3的通路有几条？说明理由。5、对于有向图来说，其关系矩阵和邻接矩阵在什么条件下相等，在什么条件下不等？答案1、 R=，； A=2、G： 4、有一条。 由，得 5、当有向图中没有平行边时关系矩阵与邻接矩阵相等；有平行边时关系矩阵与邻接矩阵不相等。 七、设 A=1, 2, , 8, 如下定义 A上的关系R=| x,yAxy (mod 3)（1）证明R 是 A上的等价关系；（2）求A关于R 的商集, 记做 A/R解：（1）须证明满足自反性、对称性、传递性自反性: xA, 有xx(mod 3)对称性: x,yA, 若xy(mod 3), 则有yx(mod 3) 传递性: x,y,zA, 若xy(mod 3), yz(mod 3), 则有 xz(mod 3)（2） 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6A/R= 1,4,7，2,5,8，3,6 A=0, 1, B=a, b, c AB=, BA =, EA = | xA yA=AA IA= | xA例如, A=1,2, 则 EA =, IA =, A=a, b, c, d, R=,R的关系矩阵 和关系图 如下： 设R=, , , S=, , , , 则RS = , , 求 A (pq)(pqr)r的主析取范式解 (1) pq (pqr)(pqr) m2 m3 pqr m1 r (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7主析取范式: m1 m2 m3 m5 m7 求(pq) r 的主析取范式与主合取范式解 (pq) r (pq) r pq (pqr)(pqr) m4m5 r (pqr)(pqr)(pqr)(pqr) m0m2m4m6 主析取范式为 m0 m2 m4 m5 m6主合取范式为 M1M3M7用得较多的基本等值式蕴涵等值式 ABAB零律 A11, A00 同一律 A0A, A1A排中律 AA1矛盾律 AA0等价等值式 AB(AB)(BA)证明 p(qr) (pq)r证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式）用等值演算法判断下列公式的类型(1) q (pq) 解 q (pq) q (pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1该式为重言式.用得较多的推理规则:A (AB) 附加(AB) A 化简(AB) , A B 假言推理(AB), B A 拒取式(AB) , B A 析取三段论(AB), (BC) (AC) 假言三段论A, B AB 合取在自然推理系统P中构造下面推理的证明:前提: pq, qr, ps, s结论: r(pq)证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq) 合取推理正确, r(pq)是有效结论构造推理的证明: 若明天是星期一或星期三, 我就有课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课前提: (pq)r, rs, s结论: pq 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换结论有效, 即明天不是星期一和星期三构造下面推理的证明:前提: pq, qr, rs结论: ps证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理推理正确, ps是有效结论构造下面推理的证明前提: (pq)r, rs, s, p结论: q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取推理正确, q是有效结论思考题一、将下列命题或谓词符号化1、刘晓月跑得快，跳得高。2、因为天气冷，所以我穿了羽绒服。3、224的充要条件是336。4、所有的人都长着黑头发。5、兔子比乌龟跑得快。二、计算1、化简并判断公式 (pq)(qp)的类型2、求pq的主析取范式3、已知 = ，求x和y。4、A=1，2，3，求P(A)5、A=1,2,8，R=|x，yAxy(mod 3)；求A的等价类和A/R。6、设A=a，b，c，d，R1，R2为A上的关系，其中R1=，；R2=，。求R1-1，R1R2，R237、无向树T有3个3度顶点，2个4度顶点，其余的都是树叶，则T有几片树叶？三、设A=1，2，3，4，A上的关系R=|（1）用列元素法表示R；（2）用关系图表示R；（3）用关系矩阵表示R。 四、代数系统，其中，为模加法1）运算是否满足结合律和交换律？说明理由。2）求幺元；3），求；4）计算，和；5）解方程。6) 求所有生成元五、证明题1、在自然推理系统P中构造下面推理