gdou离散数学B及答案.doc

广东海洋大学2010——2011学年第一学期 《离散数学》课程试题 一、将下列命题或谓词符号化（每题1分，共5分） 1、老王是山东人或河北人。若地球上没有树木，则人类不能生存。2＋2＝4当且仅当3＋3＝6。有的人登上过月球。有的人用左手写字。用等值演算法判断┐(p→q)∧r∧p的类型求p→q的主合取范式已知x-2，6 = 4，x-y，求x和yP(B) 5、A＝{{ab，c},{a，c，d},{a，e，f}}；求∩AR={a，d，b，c，b，d，c，b}；求R1 7、说明以下三个关系的性质： 8、已知A={2，3，4，5，6，7，8，9，10，12，20}，R为A上的整除关系，求 偏序集AR的哈斯图无向树T有1个2度顶点3个3度顶点4个4度顶点1个5度顶点其余的都是树叶则T有几片树叶A={1，2，3}, R={x，y|x，y∈A且x+3y8}，S={23，4，2} 1、R的集合表达式；2、R-1 3、RS，R3；，其中，为对称差运算： 1、运算是否满足结合律和交换律？请说明理由； 2、求幺元； 3、，求； 4、计算，和； 5、解方程。 五、证明题 1、在自然推理系统P中构造下面推理的证明前提：┐pq, r∨┐q ,r→s 结论：p→s(R1∩R2)-1=R1-1∩R2-1 六、（14分）A={1，2，3，4}上的关系R的关系矩阵，求： 1、R 2、R的关系图G； 3、图G的邻接矩阵关系矩阵邻接矩阵2010——2011学年第一学期 《离散数学》B标准答案 一、（每题1分，共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)) 二、（每小题5分，共45分） 1、 ┐(p→q)∧r∧p ┐(┐p∨q)∧q∧r p∧(┐q∧q)∧r p∧0∧r 0 它为矛盾式。各1分 2、p→q┐p∨q 3分 ?M2 2分 3、由有序对相等的充要条件有 x-2=4，x-y=6 3分 解得x=6，y=0。2分 4、P(B)＝{，{a}，{b}，{a，b}} 5分 5、∩A＝{a}。 5分 6、R-1={d,a，c,b，d,b，b,c}5分 7、（1）该关系是对称的，不是自反的、反自反的和传递的。2分 （2）该关系是反自反的、反对称和，传递的不是自反的、对称的。2分 （3）该关系是自反的和反对称的，不是反自反的、对称的和传递的。1分 8、A，R的哈斯图：5分 9、设T有x片树叶，由定理16.1和握手定理，有 1*2+3*3+4*4+1*5+x=2(1+3+4+1+x-1) 4分 解得 x=16 1分 三、（6分） 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}； 各2分 四、（15分） 1、满足。 1分 因为，有 1分 1分 2、由，得 3分 3、 3分 4、，；由可得 各1分 5、 3分 五、（7+8=15分）证明题 1、证明： ① ┐p∨q? ??前提引入 ② p→q ?????①置换 ③ r∨┐q? ??前提引入 ④ q→r ?????③置换 ⑤ p→r ?????②④假言三段论 ⑥ r→s ?????前提引入 ⑦ p→s ?????⑤⑥假言三段论 各1分 2、(R1∩R2)-1=R1-1∩R2-1 任取x，y x，y∈(R1∩R2)-1 y，x∈(R1∩R2) y，x∈R1∧(y，x)∈R2) x，y∈R1-1∧x，y∈R2-1 x，y∈R1-1∧R2-1 所以(R1∪R2)-1=R1-1∩R2-1 各2分 六、（14分） 1、 R={1，1，1，2，2，3，2，4，4，2}； 2分 2、G：