离散数学复习题B

离散数学复习题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).(P∨Q)→P(2).P→(P∨Q)(3).(P∧(P→Q))→Q(4).(P∧Q)→Q解:(2),(3),(4)为永真式。3.然后对上面的永真式任选其中一个给予证明(方法不限)。证明(4).(P∧Q)→Q设前件(P∧Q)为真，则得Q为真。所以(P∧Q)→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解：因为～A＝E－A={1,2}-{1}={2}～AÅE＝{2}Å{1,2}＝({2}È{1,2})－({2}Ç{1,2})＝{1,2}－{2}＝{1}五.给定集合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)＋在实数集合内满足封闭性。即