离散数学复习题B.doc

离散数学复习题B一. 有两个小题1分别说明联结词Ø、和«的名称，再分别说明它们在自然语言中表示什么含义。解：(1) Ø叫做否定 。 (2) 叫做合取。(3) 叫做析取。 (4) ®叫做蕴涵。 (5) « 叫做等价。“Ø”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“®”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“«”表示“当且仅当”、“充分且必要”。2分别列出ØP、PÙQ、PÚQ、P®Q、P«Q的真值表(填下表)。PQØPPÙQPÚQP®QP«Q解：PQØPPÙQPÚQP®QP«QFFTFFTTFTTFTTFTFFFTFFTTFTTTT二. 有三个问题1.先说明什么叫永真式(也叫重言式)。解：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是永真式。 三. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 "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(A)|2。 2. 计算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=<1,1>,<1,2>,<1,3>,<2,2>,<3,3> S=<1,1>,<1,2>,<2,1>,<2,2>,<3,3> T=<1,2>,<2,3>,<3,1> M=(空关系) N=A×A(完全关系（全域关系）) 1.写出关系R的矩阵；再画出上述各个关系的有向图。解：关系R的矩阵如下：下面是几个关系的有向图：。132MS。132。132R。132N。132T2.判断各个关系性质。用“”表示“是”，用“×”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTMN解：自反的反自反的对称的反对称的传递的R××S××T×××M×N××3.上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是A上函数？对等价关系，写出此等价关系的各个等价类。 对函数，指出它的类型。解：S和N是等价关系。 R是偏序关系。 A/S=1,2,3 A/N=1,2,3 T是函数。是双射的。4.分别求复合关系 RoS 以及R的逆关系Rc。解：RoS<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,3> Rc<1,1>,<2,1>,<3,1>,<2,2>,<3,3>六. R是实数集合，给出R上的运算：+、×、max、min、|x-y|,分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。1. 判断各个运算性质。用“”表示“是”，用“×”表示“否”，填下表：+×maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2.分别指出R对上面哪些运算是半群、独异点和群。3.如果有群，请说明它为什么是群。解:1.+×maxmin|x-y|有交换性×有结合性××有幂等性××××有幺元××××有零元×××××2. 构成半群的有：<R,>， <R,×>， <R,max>, <R,min>. 构成独异点的有： <R,>， <R,×>。 构成群的有： <R,>。3. <R,>是群的理由： (1) 在实数集合内满足封闭性。即 任何a,bR, 有R。 (2) 是可结合的。 (3) 0是运算的幺元。任何aR, 有0+a=a=a+0 . (4) 任何实数a, 都有逆元aR , 使得 (-a)+a=0=a+(-a) .所以<R,>是群。