《 离散数学》期末练习三.doc

《 离散数学》期末练习三 填空 设 f，g是自然数集N上的函数， 则 。 设A={a，b，c}，A上二元关系R={ a, a , a, b , a, c , c, c} , 则s（R）= 。 A={1，2，3，4，5，6}，A上二元关系，则用列举法 T= ； T的关系图为 ； T具有 性质。 集合的幂集 = 。 P，Q真值为0 ；R，S真值为1。则的真值为 。 的主合取范式为 。 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 。 选择 下述命题公式中，是重言式的为（ ）。 A、； B、； C、； D、。 的主析取范式中含小项的个数为（ ）。 A 、2； B、 3； C、5； D、0； E、 8 。 设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}， S5={3，5}，在条件下X与（ ）集合相等。 X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 设R和S是P上的关系，P是所有人的集合，，则表示关系 （ ）。 A、； B、； C、 ； D、。 下面函数（ ）是单射而非满射。 A、； B、； C、； D、。 其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。 设S={1，2，3}，R为S上的关系，其关系图为 则R具有（ ）的性质。 自反、对称、传递； B、什么性质也没有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 设，则有（ ）。 A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。 A、23 ； B、32 ； C、； D、。 10、全体小项合取式为（ ）。 A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。 用CP规则证明 1、 四、 集合X={1,2, 3,4, 5,6,… }，R={x1,y1,x2,y2|x1+y2 = x2+y1} 。 证明R是X上的等价关系。 五、 设集合A={ a ,b , c , d }上关系R={ a, b , b , a , b , c , c , d } 要求 写出R的关系矩阵和关系图。 六、 设f和g是函数，证明也是函数。 答案： 填空 1、2(x+1)；2、； 3、； ； 反对称性、反自反性； 4、；5、1； 6、； 7、任意x，如果x是素数则存在一个y，y是奇数且y整除x ； 选择 题目 1 2 3 4 5 6 7 8 9 10 答案 C C C C A B D A D C 证明 1、 ① P（附加前提） ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 证明： 自反性： 对称性： 传递性： 即 由（1）（2）（3）知：R是X上的先等价关系。 2、X/R= 关系矩阵： ； 关系图 六、 证明： （1） （2） 。