离散数学复习

精品文档，仅供学习与交流，如有侵权请联系网站删除离散数学复习题B一. 有两个小题1分别说明联结词、和在自然语言中表示什么含义。解：“”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“”表示“当且仅当”、“充分且必要”。2分别列出PQ、 PQ、PQ 、PQ的真值表(填下表)。PQPQ PQPQPQ解：PQPQ PQPQPQFFTFTFFTFTTFTFFTFFTTTTTT二. 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) $xB(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 $xB(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计算AE解：因为AEA=1,2-1=2 AE2 1,2(21,2)(21,2)1,221五.给定集合A=1,2,3,定义A上的关系如下： R= AA(完全关系（全域关系）) S=, T=, M=, 1.写出关系S的矩阵；再画出上述各个关系的有向图。解：关系S的矩阵如下：下面是几个关系的有向图：T。132。132M。132R。132S2. 判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM解：自反的反自反的对称的反对称的传递的RSTM3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。解：T和R是等价关系。 M是偏序关系。 A/T=1,2,3 A/R=1,2,34.求复合关系SoT解：SoT,【精品文档】第 3 页