根据R是循环的可以得到?c,a??R 而已经证明R是对称的，所以可以得到?a,c??R 即
?a,b??R??b,c??R??a,c??R 所以R是传递的，得证。
五、应用题（4分）
至少要2次称重，在天平秤上每次称重结果有三种可能性。所以称重序列的决策树是三元的在决策树里至少有8个树叶，这是因为有8种可能的结果（理论上每枚硬币都有可能是伪币）。确定伪币所需要的最大称重次数是决策树的高度。具体为：
第一次称重6枚硬币，再根据相应的结果调整第二次所需要称重的硬币。
华南农业大学期末考试试卷（ B 卷）
2008 学年第二学期 考试科目： 离散结构
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号 得分 评阅人 一 二 三 四 五 总分 林旭东 口 朱梅阶 口 2．试卷共五大题，满分100分
3．全部答案写在答题纸上，试卷纸上答题无效 ．．．．．．．．
注意事项：1．考试时间120分钟，闭卷考试
一、填空（每空2分，共30分）
1、___(P∧?Q)∨(?P∧Q )___ 2、_______传递的___________； 3、_{<4,5>,<1,1>,<3,3>}__； 4、_________0_____________； 5、_________2_____________； 6、________27__________； 7、_________边_____________； 8、________5_______________； 9、__________群____________； 10、_______0_________； 11、_______?x?yL(y,x)____； 12、________3______________； 13、_________ab?H_______； 14、_______<1,0>_______________； 15、___<1/a,-b>______________。
?1
46
二、选择题（每题2分，共30分）
1、 6、 11、 B D C 2、 7、 12、 C C A 3、 8、 13、 D D B 4、 9、 14、 B C C 5、 10、 15、 B A D
三、计算题（每题6分，共18分）
1、解：(1)写出R的关系矩阵MR ?0110 ?? M0010?R??? ?
?0001??0010??(2) 关系R的自反闭包r(R)的关系图
a b c d (3) 关系R的对称闭包r(R)的关系图
a b c d (4) 关系R的传递闭包r(R)的关系图
a b c d 2、
47
3、解：(1)将命题形式化
设p:派A去, q:派B去, r:派C去 则①p?r, ② q??r, ③?r?(p?q) 求下式的成真赋值
A=(p?r)?(q??r)?(?r?(p?q))
(2)求主析取范式
A=(p?r)?(q??r) ?(?r?(p?q))
? (?p?r)?(?q??r)?(r?p?q) (蕴涵等值式,双重否定律) ? (?p?q?r)?(?p??q?r) (矛盾律,分配律) ?(p??q??r)?(?p??q??r) (矛盾律,分配律) ?(p?q?r) (交换律) ?M4 ? M6 ? M3 ? M7 ? M0 ? ?(0,3,4,6,7) ? ?(1,2,5)
成真赋值:001,010,101
(3)结论: 方案1：派C去,A和B不去;
方案2：派B去, A和C不去;
方案3：派A和C去, B不去。
四、证明题（每题6分，共18分）
1、
证：由于T为非平凡树，则n>1，且任何顶点的度数都大于等于1；设T中m条边，k片树叶(顶点度数为1)，则其余n-k个分支点的度数均大于等于2，由握手定理与树的性质(m=n-1)有：
2m?2(n?1)?2n?2??d(vi)?k?2(n?k)，
显然k≥2，这说明T至少有两片树叶。
48
2、根据合成运算的定义以及关系的幂运算 利用证明关系的对称性的模式
3、证明0既是单位元，利用单位元的定义进行验证，再证明满足结合律，即证明
(a*b)*c?a*(b*c)
五、应用题（4分）
至少要2次称重，在天平秤上每次称重结果有三种可能性。所以称重序列的决策树是三元的在决策树里至少有8个树叶，这是因为有8种可能的结果（理论上每枚硬币都有可能是伪币）。确定伪币所需要的最大称重次数是决策树的高度。具体为：
第一次称重6枚硬币，再根据相应的结果调整第二次所需要称重的硬币。
华南农业大学期末考试试卷参考答案（ A 卷）
2008学年第二学期 考试科目： 离散数学
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号 得分 评阅人 一 二 三 四 五 总分 注意事项：1．考试时间120分钟，闭卷考试
2．试卷共五大题，满分100分
3．全部答案写在答题纸上，试卷纸上答题无效 ．．．．．．．．
一、填空（每空2分，共30分）
1、__(P∧?Q)∨(?P∧Q )____； 2、____?xP(x)∧?xQ(x)_____； 3、_________ 1____________； 4、__________传递_________； 5、_________ R2___________； 6、__________ R2 R3________； 7、_________ R2___________； 8、___{<1,3>,<2,2>,<2,3>}___； 9、_________27___________； 10、__________2____________； 11、_________8____________； 12、__________5____________；
49
13、________ 5____________； 14、_________连通__________； 15、________无回路________。
二、选择题（每题2分，共30分）
1、 6、 11、
三、计算题（5分+8分，共13分）
1、解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9,10 然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8+10=31
V2 2 V3 4 6 V5
2、解：(1)写出R的关系矩阵MR ?0110? ?0010? ?MR?? ?0001? ??0010??
(2) 关系R的自反闭包r(R)的关系图
V4 C D C 2、 7、 12、 A A B 3、 8、 13、 C C D 4、 9、 14、 C B A 5、 10、 15、 D C C 1 V1 8 V6 10 V7 a b c d (3) 关系R的对称闭包r(R)的关系图
a b c d (4) 关系R的传递闭包r(R)的关系图
50