离散复习题doc

《离散复习题doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、将下列命题或谓词符号化1、老王是山东人或河北人。2、若地球上没有树木，则人类不能生存。3、2＋2＝4当且仅当3＋3＝6。4、有的人登上过月球。5、有的人用左手写字。1、p∨q，其中，p：老王是山东人，q：老王是河北人。2、┐p→┐q，其中，p：地球上有树木，q：人类能生存。3、pq，其中，p：2＋2＝4，q：3＋3＝6，真值为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、用等值演算法判断┐(

2、p→q)∧r∧p的类型2、求p→q的主合取范式3、已知=<4，x-y>，求x和y。4、B={a，b}，求P(B)5、R={，，，}；求R-16、无向树T有1个2度顶点，3个3度顶点，4个4度顶点，1个5度顶点，其余的都是树叶，则T有几片树叶？7、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，求其树叶数。8、求的主析取范式和成真赋值；9、设表达式为1）求表达式树；2）前序遍历该表达式树；3）后序遍历该表达式树；答案1、┐(p→q)∧r∧p┐(┐p∨q)∧q∧rp∧(┐q∧q)∧rp∧0∧r0它为矛盾

3、式。2、p→q┐p∨q      M23、由有序对相等的充要条件有x-2=4，x-y=63分解得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=167、设树叶数为，树枝数为，由握手定理有：故8、成真赋值：001、011、100、1111）表达式树：2）前序遍历：3）后序遍历：三、A={1，2，3},R={

4、x，y∈A且x+3y<8}，S={<2，

5、3>，<4，2>}1、R的集合表达式；2、R-13、RS，R3；答案1、R={<1,1>,<1,2>,<2,1>,<3,1>}；2、R-1={<1,1>,<2,1>,<1,2>,<1,3>},3、RS={<1,3>},R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}；四、为群，其中，为模加法；1）求幺元（单位元）；2）求；3）计算；解：1）；2）；3）五、证明题1、在自然推理系统P中构造下面推理的证明前提：┐p∨q,r∨┐q,r→s结论：p→s证明：①┐p∨q   前提引入②p→q     ①置换③r∨┐q   前提引入④

6、q→r     ③置换⑤p→r     ②④假言三段论⑥r→s     前提引入⑦p→s     ⑤⑥假言三段论2、设是自然数集，定义上的二元关系，则是等价关系。证：①是偶数，，故自反；②若即是偶数，则也是偶数，，故对称；③若，即，是偶数，则是偶数，，故传递；综上所述，是等价关系下列3）六、A={1，2，3，4

7、}上的关系R的关系矩阵，求：1、R2、R的关系图G；3、图G的邻接矩阵A；4、顶点2到顶点3长度为3的通路有几条？说明理由。5、对于有向图来说，其关系矩阵和邻接矩阵在什么条件下相等，在什么条件下不等？答案1、R={<1，1>，<1，2>，<2，3>，<2，4>，<4，2>}；A=2、G：4、有一条。由，得5、当有向图中没有平行边时关系矩阵与邻接矩阵相等；有平行边时关系矩阵与邻接矩阵不相等。七、设A={1,2,…,8},如下定义A上的关系R={

8、x,y∈A∧x≡y(mod3)}（1）证明R是A上的等价关系；（2）求A关于R的商集,记做A/R解：（

9、1）须证明满足自反性、对称性、传递性自反性:"x∈A,有x≡x(mod3)对称性:"x,y∈A,若x≡y(mod3),则有y≡x(mod3)传递性:"x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)（2）[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}A/R={{1,4,7}，{2,5,8}，{3,6}}A={0,1},B={a,b,c}A´B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}B´A={,,,

10、1>,,}EA={

11、x∈AÙy∈A}=A×AIA=