离散数学复习.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流离散数学复习.精品文档.离散数学复习题B一. 有两个小题1分别说明联结词Ø、和«在自然语言中表示什么含义。解：“Ø”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“®”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“«”表示“当且仅当”、“充分且必要”。2分别列出P«Q、 PÚQ、P®Q 、PÙQ的真值表(填下表)。PQP«Q PÚQP®QPÙQ解：PQP«Q PÚQP®QPÙQFFTFTFFTFTTFTFFTFFTTTTTT二. 1.指出下面的命题公式中哪些是永真式(只写题号即可)。 (1). (P(PQ)Q (2). P(PQ) (3). (PQ)Q (4). (PQ)P解:(1),(2),(3)为永真式。2.然后对上面的永真式任选其中一个给予证明(方法不限)。证明 (3). (PQ)Q 设前件(PQ)为真，则得Q为真。所以(PQ)Q是永真式。 3.上面哪个不是永真式（找出一个即可），请说明它为什么不是永真式。解：(4). (PQ)P 不是永真式。因为如果前件PQ为真，后件P不一定为真。所以(PQ)P 不是永真式。三.用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 "x(B(x)®ØC(x), $xA(x), "x(ØA(x)ÚC(x) Þ $xØB(x)解： $xA(x) P A(a) ES "x(ØA(x)Ú C(x) P ØA(a)ÚC(a) US C(a) T I " x(B(x)®ØC(x) P B(a)®ØC(a) US ØB(a) T I $xØB(x) EG 四令全集E=1,2,A=1, P(A)表示集合A的幂集。（注意：要求有计算过程，不能直接写出计算结果！）1. 指出 P(E)和P(A)各有多少个元素。即求|P(E)|和|P(A)|。解：因为P(E),1,2, 1,2 所以P(E)有4个元素。即|P(E)|4。P(A),1 所以P(A)有2个元素。即|P(A)|2。 2. 计算 P(E)P(A)解： P(E)P(A),1,2,1,2,1 2, 1,23计算AÅE解：因为AEA=1,2-1=2 AÅE2 Å1,2(2È1,2)(2Ç1,2)1,221五.给定集合A=1,2,3,定义A上的关系如下： R= A×A(完全关系（全域关系）) S=<1,2>,<2,3>,<3,1> T=<1,1>,<1,2>,<2,1>,<2,2>,<3,3> M=<1,1>,<1,2>,<1,3>,<2,2>,<3,3> 1.写出关系S的矩阵；再画出上述各个关系的有向图。解：关系S的矩阵如下：下面是几个关系的有向图：T。132。132M。132R。132S2. 判断各个关系性质。用“”表示“是”，用“×”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM解：自反的反自反的对称的反对称的传递的R××S×××T××M××3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。解：T和R是等价关系。 M是偏序关系。 A/T=1,2,3 A/R=1,2,34.求复合关系SoT解：SoT<1,1>,<1,2>,<2,3>,<3,1>,<3,2>