离散数学复习题B.doc

《离散数学复习题B.doc》由会员分享，可在线阅读，更多相关《离散数学复习题B.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学复习题B一. 有两个小题1分别说明联结词、和的名称，再分别说明它们在自然语言中表示什么含义。解：(1) 叫做否定 。 (2) 叫做合取。(3) 叫做析取。 (4) 叫做蕴涵。 (5) 叫做等价。“”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“”表示“当且仅当”、“充分且必要”。2分别列出P、PQ、PQ、PQ、PQ的真值表(填下表)。PQPPQPQPQPQ解：PQPPQPQPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT二. 有三个问题1.先说

2、明什么叫永真式(也叫重言式)。解：A(P1,P2,Pn) 是含有命题变元P1,P2, Pn的命题公式，如不论对P1,P2, Pn作任何指派，都使得A(P1,P2,Pn) 为真，则称之为重言式，也称之为永真式。2.指出下面的命题公式中哪些是永真式(只写题号即可)。 (1). (PQ)P (2). P(PQ) (3). (P(PQ)Q (4). (PQ)Q 解:(2),(3),(4)为永真式。3.然后对上面的永真式任选其中一个给予证明(方法不限)。证明 (4). (PQ)Q 设前件(PQ)为真，则得Q为真。所以(PQ)Q是永真式。 三. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式

3、书写推理过程。 xC(x), $x(A(x)B(x), x(B(x)C(x) $xA(x)解： $x(A(x)B(x) P A(a)B(a) ES xC(x) P C(a) US x(B(x)C(x) P B(a)C(a) US B(a) T I A(a) T I $xA(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(

4、A)|2。 2. 计算AE解：因为AEA=1,2-1=2 AE2 1,2(21,2)(21,2)1,221 五. 给定集合A=1,2,3,定义A上的关系如下： R=, S=, T=, M=(空关系) N=AA(完全关系（全域关系）) 1.写出关系R的矩阵；再画出上述各个关系的有向图。解：关系R的矩阵如下：下面是几个关系的有向图：。132MS。132。132R。132N。132T2.判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTMN解：自反的反自反的对称的反对称的传递的RSTMN3.上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是A上

5、函数？对等价关系，写出此等价关系的各个等价类。 对函数，指出它的类型。解：S和N是等价关系。 R是偏序关系。 A/S=1,2,3 A/N=1,2,3 T是函数。是双射的。4.分别求复合关系 RoS 以及R的逆关系Rc。解：RoS, Rc,六. R是实数集合，给出R上的运算：+、max、min、|x-y|,分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。1. 判断各个运算性质。用“”表示“是”，用“”表示“否”，填下表：+maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2.分别指出R对上面哪些运算是半群、独异点和群。3.如果有群，请说明它为什么是群。解:1.+maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2. 构成半群的有：， ， , . 构成独异点的有： ， 。 构成群的有： 。3. 是群的理由： (1) 在实数集合内满足封闭性。即 任何a,bR, 有R。 (2) 是可结合的。 (3) 0是运算的幺元。任何aR, 有0+a=a=a+0 . (4) 任何实数a, 都有逆元aR , 使得 (-a)+a=0=a+(-a) .所以是群。