離散數(shù)學(xué)復(fù)習(xí)題B

離散數(shù)學(xué)復(fù)習(xí)題B一.有兩個小題1．分別說明聯(lián)結(jié)詞?、∧、∨、→和?的名稱，再分別說明它們在自然語言中表示什么含義。解：(1)?叫做否定。(2)∧叫做合取。(3)∨叫做析取。(4)?叫做蘊(yùn)涵。(5)?叫做等價?！?”表示“…不成立”，“不…”。“∧”表示“并且”、“不但…而且...”、“既…又...”等?！啊拧北硎尽盎蛘摺?，是可兼取的或?！?”表示如果…，則…；只要…，就…；只有…,才…；僅當(dāng)…?！?”表示“當(dāng)且僅當(dāng)”、“充分且必要”。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設(shè)前件(P∧Q)為真，則得Q為真。所以(P∧Q)→Q是永真式。三.用謂詞邏輯推理的方法證明下面推理的有效性。要求按照推理的格式書寫推理過程。"xC(x),$x(A(x)úB(x)),"x(B(x)??C(x))T$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的冪集。（注意：要求要有計算過程，不能直接寫出計算結(jié)果?。?.指出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上的關(guān)系如下：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=Ф(空關(guān)系)N=A×A(完全關(guān)系（全域關(guān)系）)1.寫出關(guān)系R的矩陣；再畫出上述各個關(guān)系的有向圖。解：關(guān)系R的矩陣如下：下面是幾個關(guān)系的有向圖：。。。。132MS。。。132。。。132R。。132N。。。。132T2.判斷各個關(guān)系性質(zhì)。用“√”表示“是”，用“×”表示“否”，填下表：自反的反自反的對稱的反對稱的傳遞的RSTMN解：自反的反自反的對稱的反對稱的傳遞的R√××√√S√×√×√T×√×√×M×√√√√N(yùn)√×√×√3.上述五個關(guān)系中，哪些是等價關(guān)系？哪些是偏序關(guān)系？哪些是A上函數(shù)？對等價關(guān)系，寫出此等價關(guān)系的各個等價類。對函數(shù)，指出它的類型。解：S和N是等價關(guān)系。R是偏序關(guān)系。A/S={{1,2},{3}}A/N={{1,2,3}}T是函數(shù)。是雙射的。4.分別求復(fù)合關(guān)系RoS以及R的逆關(guān)系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是實數(shù)集合，給出R上的運算：+、－、×、max、min、|x-y|,分別表示加法、減法、乘法、兩個數(shù)中取最大的、兩個數(shù)中取最小的、x-y的絕對值運算。1.判斷各個運算性質(zhì)。用“√”表示“是”，用“×”表示“否”，填下表：+－×maxmin|x-y|有交換性有結(jié)合性有冪等性有幺元有零元2.分別指出R對上面哪些運算是半群、獨異點和群。3.如果有群，請說明它為什么是群。解:1.+－×maxmin|x-y|有交換性√×√√√√有結(jié)合性√×√√√×有冪等性×××√√×有幺元√×√×××有零元××√×××2.構(gòu)成半群的有：<R,＋>，<R,×>，<R,max>,<R,min>.構(gòu)成獨異點的有：<R,＋>，<R,×>。構(gòu)成群的有：<R,＋>。3.<R,＋>是群的理由：(1)＋在實數(shù)集合內(nèi)滿足封閉性。即