(6) Use the ordered rooted ((3*x-5*(y↑2))↑5)/(a*((b↑3)-4*c))
tree to represent the expression
4. Application of Discrete Mathematics. (4 x 6’ = 30’)
(1) Use inference to obtain conclusion from the premises.
All the people who like walking do not like driving. Every person likes driving or riding. Some people don’t like riding. Therefore, some people don’t like walking.
《 Discrete Mathematics 》试卷第 6 页 共 8 页
(2)Suppose R is a reflexive and transitive relation on A. T is also a relation on A, such that:
Prove that T is an equivalence relation.
(3) 6 people are supposed to accomplish 3 tasks in groups (2 people in one group). The people in the same group should cooperate with each other to accomplish the task. We now know each person could cooperate with at least other 3 people. Is that possible that all the tasks could be accomplished?
《 Discrete Mathematics 》试卷第 7 页 共 8 页
(4) The roads represented by this graph are all unpaved. The lengths of the roads between pairs of towns are represented by edge weights. Which roads should be paved so that there is path of paved roads between each pair of town so that a minimum road length is paved?
《 Discrete Mathematics 》试卷第 8 页 共 8 页