离散数学期末试题2

A-1一二三四五六七八总分标准分10153015105510100得分一、利用求主范式的方法判定下列公式的属性（每小题5分共10分）（1）()()(())PQQRPQR（2）(P∧Q)∨(⌐P∧Q∧R)二、推理题（其中第(1)小题8分第(2)小题7分共15分）（1）假定个体域是所有人组成的集合，首先将下列命题符号化，然后使用推理的方法进行证明（8分）每一个去北京旅游的人，或者参观故宫，或者参观颐和园，或者去登长城；凡是去北京旅游的人，如果爬香山就不参观颐和园；有的到北京的旅游者既不参观故宫也不去登长城。因此，有的去北京旅游的人不爬香山。建议使用下列参考谓词：BJ(x):x是去北京旅游的人GG(x):x是参观故宫的人YY(x):x是参观颐和园的人CC(x):x是去登长城的人XS(x):x是去爬香山的人（2）使用CP规则，构造下列推理的证明（7分）()(()()),()()(()())()xAxxQxFxxBxxQxxAxBxxFx三、简答题（每小题3分共30分）（1）通过什么途径确定具有n个元素的集合构成不同等价关系的数量？装订线A-2（2）是等价关系一定是相容关系吗？说明原因。（3）是覆盖一定是划分吗？说明原因。（4）高级语言和目标语言之间的关系是哪两个关系的复合？（5）写出偏序关系的形式化定义。（6）设集合X有n个元素问集合X上可构成多少个2元运算？（7）正则图一定是完全图吗？说明原因。（8）完全图一定是正则图吗？说明原因。（9）叶加权最优二叉树一定是最小生成树吗？说明原因。（10）图的邻接矩阵中行上1的个数，列上1的个数的含义各是什么？四、给定S={1,2,3,4,5,6}的划分为A={{1,2,3},{4,5},{6}}（15分，每小题3分）（1）试求出与该划分相对应的等价关系（2）画出其关系图（3）求出其关系矩阵（4）给出其可传递闭包（5）给出其对称闭包五、证明n阶二叉树有(n+1)/2片叶子（10分）六、设*是整数集合上的二元运算，其定义为x*y=x。证明*不是可交换的，但是可以结合的（5分）七、证明如果群＜G,*＞中的每一个元素a都满足a2=e，e是幺元，则G是阿贝尔群（可交换群）(5分)A-3八、选择填空（每空2分共10分）（1）命题逻辑中的极大项一定是（）A：基本积B：基本和（2）二元树的先序遍历顺序是（）A：左、根、右B：根、左、右（3）把一个图转换成树的方法是（）A：求生成子图B：求生成树（4）给定代数系统U=＜A，*＞，其中A={a,b,c,d}*的运算表为：*abcdabcdabdacbcadbcdbadc以下子系统谁是U的子代数系统（）A：U1=＜{a,b,c},*＞B:U2=＜{a,b,c,d},*＞（5）对下面的有向图和可达集表示正确的是（）A:d(v1)=d(v2)B:d(v3)=d(v4)v1v2v4v3