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

1、離散數(shù)學(xué)題庫與答案、選擇或填空(數(shù)理邏輯部分)1、下列哪些公式為永真蘊(yùn)含式？(A)(1)Q=>OP(2)Q=>P>QP=>PQ(4)P(PQ)=>P答：在第三章里面有公式(1)是附加律，(4)可以由第二章的蘊(yùn)含等值式求出(注意與吸收律區(qū)別)2、下列公式中哪些是永真式？()(1)(PQ)-(Q-R)(2)P-(QfQ)(3)(PQ)-P(4)P-(PQ)答：(2),(3),(4)可用蘊(yùn)含等值式證明3、設(shè)有下列公式，請問哪幾個是永真蘊(yùn)涵式？()P=>PQPQ=>PPQ=>PQ(4)P(P-Q)=>Q(5)(P-Q)=>P(6)P(PQ)=

2、>P答：(2)是第三章的化簡律，(3)類似附加律，(4)是假言推理，(3),(5),(6)都可以用蘊(yùn)含等值式來證明出是永真蘊(yùn)含式4、公式x(A(x)B(y,x)zC(y,z)D(x)中，自由變元是()，約束變元是()。答：x,y,x,z(考察定義在公式xA和xA中，稱x為指導(dǎo)變元，A為量詞的轄域。在xA和xA的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，即稱x為約束變元，A中不是約束出現(xiàn)的其他變項(xiàng)則稱為自由變元。于是A(x)、B(y,x)和zC(y,z)中y為自由變元，x和z為約束變元，在D(x)中x為自由變元)5、判斷下列語句是不是命題。若是，給出命題的真值。()(1)北京是中華人民共和國的首

3、都。(2)陜西師大是一座工廠。(3)你喜歡唱歌嗎？(4)若7+8>18,則三角形有4條邊。前進(jìn)！(6)給我一杯水吧！答：(1)是，T(2)是，F(xiàn)(3)不是(4)是，T(5)不是(6)不是(命題必須滿足是陳述何，不能是疑問句或者祈使旬。)6、命題“存在一些人是大學(xué)生”的否定是()，而命題“所有的人都是要死的”的否定是()。答：所有人都不是大學(xué)生，有些人不會死(命題的否定就是把命題前提中的量詞“換成存在，換成”，然后將命題的結(jié)論否定，“且變或或變且")7、設(shè)P:我生病，Q:我去學(xué)校，則下列命題可符號化為()。(1)只有在生病時，我才不去學(xué)校(2)若我生病，則我不去學(xué)校(3)當(dāng)且僅當(dāng)

4、我生病時，我才不去學(xué)校(4)若我不生病，則我一定去學(xué)校答：(1)QP(注意"只有才”和"除非就”兩者都是一個形式的)(2)PQ(3)PQ(4)PQ8、設(shè)個體域?yàn)檎麛?shù)集，則下列公式的意義是()。(1)xy(x+y=0)(2)yx(x+y=0)答：(1)對任一整數(shù)x存在整數(shù)y滿足x+y=0(2)存在整數(shù)y對任一整數(shù)x滿足x+y=09、設(shè)全體域D是正整數(shù)集合，確定下列命題的真值：(1)xy(xy=y)()(2)xy(x+y=y)()(3)xy(x+y=x)()(4)xy(y=2x)()答：(1)F(反證法：假若存在，則(x-1)*y=0對所有的x都成立，顯然這個與前提條件相矛盾)

5、(2)F(同理)(3)F(同理)(4)T(對任一整數(shù)x存在整數(shù)y滿足條件y=2x很明顯是正確的)10、設(shè)謂詞P(x):x是奇數(shù)，Q(x):x是偶數(shù)，謂詞公式x(P(x)Q(x)在哪個個體域中為真?()自然數(shù)(2)實(shí)數(shù)(3)復(fù)數(shù)(4)(1)-(3)均成立答：(1)(在某個體域中滿足不是奇數(shù)就是偶數(shù)，在整數(shù)域中才滿足條件，而自然數(shù)子整數(shù)的子集，當(dāng)然滿足條件了)11、命題“2是偶數(shù)或-3是負(fù)數(shù)”的否定是()。答：2不是偶數(shù)且-3不是負(fù)數(shù)。12、永真式的否定是()永真式(2)永假式(3)可滿足式(4)(1)-(3)均有可能答：(2)(這個記住就行了)13、公式(PQ)(PQ)化簡為()，公式Q(P(P

6、Q)可化簡為()。答：P,QP(考查分配率和蘊(yùn)含等值式知識的掌握)14、謂詞公式x(P(x)yR(y)Q(x)中量詞x的轄域是()c答：P(x)yR(y)(一對括號就是一個轄域)15、令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則命題“并非每個實(shí)數(shù)都是有理數(shù)”的符號化表示為()。答：x(R(x)Q(x)(集合論部分)16、設(shè)人=依,但,下列命題錯誤的是()。(1)aP(A)(2)aP(A)(3)aP(A)(4)aP(A)答：(2)(a是P(A)的一個元素)17、在0()之間寫上正確的符號。(1)=(2)(3)(4)答：(4)(空集沒有任何元素，且是任何集合的子集)18、若集合S的基數(shù)|S|=5

7、,則S的募集的基數(shù)|P(S)|=()。答：32(2的5次方考查募集的定義，即募集是集合S的全體子集構(gòu)成的集合)19、設(shè)P=x(x+1)24且xR,Q=x|5x2+16且xR,則下列命題哪個正確()QP(2)QP(3)PQ(4)P=Q答：(3)(Q是集合R,P只是R中的一部分，所以P是Q的真子集)20、下列各集合中，哪幾個分別相等()。A1=a,b(2)A2=b,a(3)A3=a,b,a(4)A4=a,b,c(5)A5=x|(x-a)(x-b)(x-c)=0(6)A6=x|x2-(a+b)x+ab=0答：A1=A2=A3=A6A4=A5(集合具有無序性、確定性和互異性)21、若A-B=，則下列哪

8、個結(jié)論不可能正確？()(1)A=(2)B=(3)AB(4)BA答：(4)(差集的定義)22、判斷下列命題哪個為真?()A-B=B-A=>A=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一個元素屬于B,則A=B答：(1)(考查空集和差集的相關(guān)知識)23、判斷下列命題哪幾個為正確？()£©,(2)中,(3)£©(4)(5)a,b6a,b,a,b答：(2),(4)24、判斷下列命題哪幾個正確？()(1)所有空集都不相等(2)(4)若A為非空集，則AA成立。答：(2)25、設(shè)AAB=AHC,AAB=AAC,貝UB()C。答：=(等

9、于)26、判斷下列命題哪幾個正確？(1)若AUB=AUC,則B=C(2)a,b=b,a(3)P(AAB)P(A)AP(B)(P(S)表示S的募集)(4)若A為非空集，則AAUA成立。答：(2)27、A,B,C是三個集合，則下列哪幾個推理正確:(1)AB,BC=>AC(2)AB,BC=>ASB(3)ASB,B6C=>ASC答：(1)(3)的反例C為0,1,0B為0,1,A為1很明顯結(jié)論不對)(二元關(guān)系部分)、一_一，一、，一228、設(shè)人=1,2,3,4,5,6,B=1,2,3，從A到B的關(guān)系R=x,y|x=y求(1)R(2)R-1答：(1)R=<1,1>,<4

10、,2>(2)R1=<1,1>,<2,4>(考查二元關(guān)系的定義，R1為R的逆關(guān)系，即R1=<x,y>|<y,x>6R)29、舉出集合A上的既是等價關(guān)系又是偏序關(guān)系的一個例子。()答：A上的恒等關(guān)系30、集合A上的等價關(guān)系的三個性質(zhì)是什么？()答：自反性、對稱性和傳遞性31、集合A上的偏序關(guān)系的三個性質(zhì)是什么？()答：自反性、反對稱性和傳遞性(題29,30,31全是考查定義)32、設(shè)S=1,2,3,4,A上的關(guān)系區(qū)=1,2，2,1，2,3，3,4求(1)RR(2)R-1。答：RR=1,1，1,3，2,2，2,4(考查FG=<x,y>

11、|t(<x,t>F<t,y>6G)R1=<2,1，1,2，3,2，4,333、設(shè)人=1,2,3,4,5,6,R是A上的整除關(guān)系，求R=()R=<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>34、設(shè)人=1,2,3,4,5,6,B=1,2,3，從A到B的關(guān)系R=<x,y>|

12、x=2y,求(1)R(2)R-1。答：(1)R=<1,1>,<4,2>,<6,3>(2)R1=<1,1>,<2,4>,(36>35、設(shè)人=1,2,3,4,5,6,B=1,2,3，從A到B的關(guān)系R=<x,y>|x=y2,求R和R1的關(guān)系矩陣。1001R 1 的關(guān)系矩陣= 00000000010000000000答：R的關(guān)系矩陣=00001000000036、集合A=1,2,-,10上的關(guān)系R=<x,y>|x+y=10,x,yA,則R的性質(zhì)為（）。(1) 自反的(2)對稱的(3)傳遞的，對稱的(4)傳遞的答：

13、(2)(考查自反對稱傳遞的定義)(代數(shù)系統(tǒng)部分)37、設(shè)A=2,4,6，A上的二元運(yùn)算*定義為：a*b=maxa,b，則在獨(dú)異點(diǎn)<A,*>中，單位元是()，零元是()。答：2,6(單位元和零元的定義，單位元：e。x=x零元：0ox=0)38、設(shè)A=3,6,9，A上的二元運(yùn)算*定義為：a*b=mina,b，則在獨(dú)異點(diǎn)<A,*>中，單位元是()，零元是()；答：9，3(半群與群部分)39、設(shè)G,*是一個群，則(1)若a,b,x6G,ax=b,則x=();(2)若a,b,x6G,ax=ab,則x=()。答：(1)a1b(2)b(考查群的性質(zhì)，即群滿足消去律)40、設(shè)a是12階

14、群的生成元，則a2是()階元素，a3是()階元素。答：6,441、代數(shù)系統(tǒng)<G,*>是一個群，則G的等哥元是()。答：單位元(由aA2=a,用歸納法可證aAn=a*aA(n-1)=a*a=a,所以等幕元一定是嘉等元，反之若aAn=a對一切N成立，則對n=2也成立，所以幕等元一定是等幕元，并且在群<G,*>中，除幺元即單位元e外不可能有任何別的冪等元)42、設(shè)a是10階群的生成元，則24是()階元素，23是()階元素答：5,10（若一個群G的每一個元都是G的某一個固定元a的乘方，我們就把G叫做循環(huán)群；我們也說，G是由元a生成的，并且用符號G=a表示，且稱a為一個生成元。并

15、且一元素的階整除群的階）43、群G,*的等哥元是（），有（）個。答：單位元，1（在群G,*中，除幺元即單位元e外不可能有任何別的幕等元）44、素數(shù)階群一定是（）群，它的生成元是（）。答：循環(huán)群，任一非單位元（證明如下：任一元素的階整除群的階?，F(xiàn)在群的階是素數(shù)p,所以元素的階要么是1要么是p。G中只有一個單位元，其它元素的階都不等于1,所以都是p。任取一個非單位元，它的階等于p,所以它生成的G的循環(huán)子群的階也是p,從而等于整個群Go所以G等于它的任一非單位元生成的循環(huán)群）45、設(shè)G,*是一個群，a,b,c6G,則（1）若ca=b,貝Uc=（）;（2）若ca=ba,貝Uc=（）。答：（1）ba1（

16、2）b（群的性質(zhì)）46、H,是6,的子群的充分必要條件是（）。答：H,是群或a,bG,abH,a-1H或a,bG,ab-1H47、群A,*的等哥元有（）個，是（），零元有（）個答：1,單位元，048、在一個群G,*中，若G中的元素a的階是k,則a1的階是（）答：k49、在自然數(shù)集N上，下列哪種運(yùn)算是可結(jié)合的？（）（1）a*b=a-b（2）a*b=maxa,b（3）a*b=a+2b（4）a*b=|a-b|答：（2）50、任意一個具有2個或以上元的半群，它（）。（1）不可能是群（2）不一*定是群（3）一定是群（4）是交換群答：（1）51、6階有限群的任何子群一定不是（）(1) 2 階答： (3)(

17、2) 3階(3)4階(4)6階(格與布爾代數(shù)部分)52、下列哪個偏序集構(gòu)成有界格()(1) (N,)(2)(Z,)(3) (2,3,4,6,12,|(整除關(guān)系)(4)(P(A),)答：(4)(考查冪集的定義)53、有限布爾代數(shù)的元素的個數(shù)一定等于()。(1)偶數(shù)(2)奇數(shù)(3)4的倍數(shù)(4)2的正整數(shù)次冪答：(4)(圖論部分)54、設(shè)G是一個哈密爾頓圖，則G一定是()(1)歐拉圖(2)樹(3)平面圖(4)連通圖答：(4)(考察圖的定義)55、下面給出的集合中，哪一個是前綴碼？()(1)0，10，110，101111(2)01，001，000，1(3)b，c，aa，ab，aba(4)1，11，1

18、01，001，0011答：(2)56、一個圖的哈密爾頓路是一條通過圖中()的路。入度deg- (v) 表示 ( )。答：所有結(jié)點(diǎn)一次且恰好一次57、在有向圖中，結(jié)點(diǎn)v的出度deg+(v)表示()答：以v為起點(diǎn)的邊的條數(shù)，以v為終點(diǎn)的邊的條數(shù)58、設(shè)G是一棵樹，則G的生成樹有()棵。(1)0(2)1(3)2(4)不能確定答：159、n階無向完全圖Kn的邊數(shù)是()，每個結(jié)點(diǎn)的度數(shù)是()答：n（J,n-1260、一棵無向樹的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是（）。答：m=n-161、一個圖的歐拉回路是一條通過圖中（）的回路。答：所有邊一次且恰好一次62、有n個結(jié)點(diǎn)的樹，其結(jié)點(diǎn)度數(shù)之和是（）。答：2n-2（結(jié)點(diǎn)度

19、數(shù)的定義）63、下面給出的集合中，哪一個不是前綴碼（）。（1）a,ab,110,albll（2）01,001,000,1（3）1,2,00,01,0210（4）12,11,101,002,0011答：（1）64、n個結(jié)點(diǎn)的有向完全圖邊數(shù)是（），每個結(jié)點(diǎn)的度數(shù)是（）。答：n（n-1）,2n-265、一個無向圖有生成樹的充分必要條件是（）。答：它是連通圖66、設(shè)G是一棵樹，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則n=mm=n+1（3）n=m+1（4）不能確定。答：（3）67、設(shè)丁=V,E是一棵樹，若|V|>1,則T中至少存在（）片樹葉。答：268、任何連通無向圖G至少有（）棵生成樹，當(dāng)且僅當(dāng)G是（），

20、G的生成樹只有一棵。答：1,樹69、設(shè)G是有n個結(jié)點(diǎn)m條邊的連通平面圖，且有k個面，則k等于：（1）m-n+2n-m-2n+m-2m+n+2答：（1）70、設(shè)T是一棵樹，則一棵樹，則T是一個連通且(答：無簡單回路71、設(shè)無向圖G有16條邊且每個頂點(diǎn)的度數(shù)都是2,則圖6有()個頂點(diǎn)。(1)10(2)4(3)8(4)16答：(4)72、設(shè)無向圖G有18條邊且每個頂點(diǎn)的度數(shù)都是3,則圖6有()個頂點(diǎn)。(1)10(2)4(3)8(4)12答：(4)73、設(shè)圖G=<V，E>，V=a，b，c，d，e，E=<a,b>,<a,c>,<b,c>,<c,d&g

21、t;,<d,e>,則G是有向圖還是無向圖？答：有向圖74、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有()個。答：偶數(shù)75、具有6個頂點(diǎn)，12條邊的連通簡單平面圖中，每個面都是由()條邊圍成？(1)2(2)4(3)3(4)5答：(3)76、在有n個頂點(diǎn)的連通圖中，其邊數(shù)()。(1)最多有n-1條(2)至少有n-1條(3)最多有n條(4)至少有n條答：(2)77、一棵樹有2個2度頂點(diǎn)，1個3度頂點(diǎn)，3個4度頂點(diǎn)，則其1度頂點(diǎn)為()。(1)5(2)7(3)8(4)9答：(4)78、若一棵完全二元(叉)樹有2n-1個頂點(diǎn)，則它()片樹葉。答：(1)79、下列哪一種圖不一定是樹()。(1)無簡單回路的

22、連通圖(2)有n個頂點(diǎn)n-1條邊的連通圖(3)每對頂點(diǎn)間都有通路的圖(4)連通但刪去一條邊便不連通的圖答：(3)80、連通圖G是一棵樹當(dāng)且僅當(dāng)6中()。(1)有些邊是割邊(2)每條邊都是割邊(3)所有邊都不是割邊(4)圖中存在一條歐拉路徑答：(2)(數(shù)理邏輯部分)二、求下列各公式的主析取范式和主合取范式：1、(PQ)R解：(P-Q)R(PR)(QR)(析取范式)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)(P-Q)R)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主析取范式)(P-Q)R(PQR)(PQR)

23、(PQR)(PQR)(PQR)(主合取范式)2、(PR)(QR)P解：(PR)(QR)P(析取范式)(P(QQ)R)(PP)QR)(P(QQ)(RR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)(PR)(QR)P)(PQR)(PQR)(原公式否定的主析取范式)(PR)(QR)P(PQR)(PQR)(主合取范式)3、(FQ)(RP)解：(P-Q)(RP)(PQ)(RP)(合取范式)(P Q (R R) (P (QQ) R)T ( 主合取范式)(P Q R) (P Q(P Q R) (P

24、QR)(PQR)(PQR)R)(PQR)(主合取范式)(P-Q)(RP)R)(PQR)(PQR)(PQR)(PQ(PQR)(原公式否定的主合取范式)(P-Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)4、CH(PR)解：QH(PR)QPR(主合取范式)(QH(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主合取范式)0->(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)5、P(P(QP)解：4(P(Q-P)P(P(QP)PP(PQ)(PQ)(PQ)(PQ)(主析取范式)6

25、、(P-Q)(RP)解： (P-Q) (R P)( P Q) (R P)(PQ)(RP)(析取范式)(PQ(RR)(P(QQ)R)(P Q R) (PQ R) (P Q R) (P Q R)(PQR)(PQR)(PQR)(主析取范式)(P-Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主析取范式)(P-Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)7、P(PQ)解：P(P-Q)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)(主析取范式)8、(RQ)P解：(R-Q)P(RQ)P(RP)(QP)(析取范式)(R(QQ

26、)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)(主析取范式)R)(R-Q)P)(PQR)(PQR)(PQ(PQR)(PQR)(原公式否定的主析取范式)(R-Q)P(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)9、PQ解：PfQPQ(主合取范式)(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(主析取范式)10、 PQ解：PQ(主合取范式)(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(主析取范式)11、 PQ解：PQ(主析取范式)(P(QQ)(PP)Q)(PQ)(PQ

27、)(PQ)(PQ)(PQ)(PQ)(PQ)(主合取范式)12、 (PR)Q解：(PR)Q(PR)Q(PR)Q(PQ)(RQ)(合取范式)( P Q (RR) ( P P) Q R)(PQR)(PQ(PQR)(PQ(PQR)(PQP R)Q( P Q R) ( PQ R)R)(PQR)(PQR)R)(PQR)(PQR)R)(PQR)(主合取范式)QR)(PQR)(PQR)(P(原公式否定的主析取范式)PR)Q(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)13、 (PQ)R解：(PQ)R(PQ)R(PQ)R(析取范式)(PQ(RR)(PP)(QQ)R)(PQR)(PQR)(PQR

28、)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)(PQ)R(PQ)R(PQ)R(析取范式)(PR)(QR)(合取范式)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)14、 (P(QR)(P(QR)解：(P(QR)(P(QR)(P(QR)(P(QR)(PQ)(PR)(PQ)(PR)(合取范式)(PQ(RR)(P(QQ)R)(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(

29、PQR)(主合取范式)(P(QR)(P(QR)(PQR)(PQR)(原公式否定的主合取范式)(P(QR)(P(QR)(PQR)(PQR)(主析取范式)15、 P(P(Q(QR)解：P(P(Q(QR)P(P(Q(QR)PQR（主合取范式）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)16、 (PQ)(PR)解、(PQ)(PR)Q) (P R） （ 合取范式 ）Q (RR) ( P (Q Q)R)Q R)P Q R)Q R) ( P Q R)Q

30、R)P Q R)Q R）（ 主合取范式）(PQ)(PR)( P Q) (R)P(QR)(合取范式)( P (Q Q)(R R) (P)Q R)( P Q R) (P Q R) (PQR) ( P Q R)( P Q R) (PQ R)( P Q R) ( PQ R) ( P Q R)( P Q R) (P Q R)（主析取范式）三、證明：1、PQ,QR,R,SP=>S證明：(1)R前提(2)QR前提(3)Q（1），（2）P-Q前提(5) P(3)，(4)(6) SP前提(7) S(5)，(6)2、A (BC), C ( D E),F7 (DE),A=>BF證明：(1) A前提(2)

31、 A-(B-C)前提(3) B-C(1),(2)(4) B附加前提(5) C(3)，(4)(6) C-(DE)前提(7) DE(5)，(6)(8) F-(DE)前提(9) F(7)，(8)(10) B-FCP(11) Q,PR,Q-S=>RS證明：(1) R附加前提(2) P-R前提(3) P(1)，(2)(4) PQ前提(5) Q(3)，(4)(6) Q-S前提(7) S(5)，(6)(8) RSCP，(1)，(8)4、(P-Q)(R-S),(Q-W)(S-X),(WX),PR=>P證明：(2) P-R前提(3) R(1)，(2)(4) (P-Q)(R-S)前提(5) P-Q(4

32、)(6) R-S(5)(7) Q(1)，(5)(8) S(3)，(6)(9) (Q->W)(S-X)前提(10) Q-W(11) S-X12) W13) X14) WX15) (WX)16) (WX)(W（ 9）（ 10）（ 7） ，（10）（ 8） ，（11）（ 12） ，（13）前提X）（14），（15）5、(UV)(MN),UP,P7(QS),QS=>M證明：( 1) QS附加前提( 2) P-(QS)前提( 3) P(1)，(2)( 4) UP前提( 5) U(3)，(4)( 6) UV(5)( 7) (UV)-(MN)前提( 8) MN(6),(7)( 9) M(8)6、

33、 BD,(EF)-D,E=>B證明：附加前提(1) B(2) BD前提(3) D(1)，(2)(4) (E-F)-D前提(5) (E-F)(3),(4)(6) EF(5)(7) E(6)(8) E前提(9) EE(7)，(8)7、P(QR),E(Q-S)=>P(QS)證明：(1) 1)P附加前提(2) 2)Q附加前提(3) P-(Q-R)前提(4) Q-R(1),(3)(5) 5)R(2)，(4)(6) R-(Q-S)前提(7) Q-S(5),(6)(8) 8)S(2)，(7)(9) Q-SCP,(2),(10) P-(Q-S)CP,(1),(9)8、PQ,6R,ES=>SQ

34、證明： 1) 1)S附加前提 2) R-S前提 3) 3)R(1)，(2) 4) P-R前提 5) 5)P(3)，(4) 6) P-Q前提 7) 7)Q(5)，(6) 8) S-QCP,(1),(7)9、P(Q-R)=>(P-Q)(PR)證明：(1) P-Q附加前提(2) P附加前提(3) Q(1),(2)(4) P-(Q-R)前提(5) Q-R,(4)(6) R(3),(5)(7) P-RCP,(2),(6)(8) (P-Q)-(P-R)CP,(1),(7)10、P-(CHR),CHP,SR,P=>S證明： 1) P前提 2) P-(QHR)前提 3) QHR(1), 4) Q-

35、P 5) 5)Q 6) 6)RSfR 8) 8)S11、A,ZB,AC,證明：(1)A前提(1) ，(4)(3),(5)前提(6)，(7)Bf(D-C)=>D前提(2) A-B前提(3) B(1)，(2)(4) AfC前提(5) C(1)，(4)(6)B-(D-C)前提C(3),(6)(8)D(5),(7)12、卜(CB),BA,八C=>AD證明：附加前提前提(1), (2)前提(1), (4)(3), (5)前提(6),CP , (1), (8)(P R) QR Q)QQ(P Q)(DA(2) A一(CB)(3) CB(4) B-A(5) B(6) C(7) D-C(8) D(9

36、) A-D13、(PQ)(RQ)證明、(PQ)(RQ)(PQ)(PR)(PR)(PR)Q14、P(QP)P證明、P(QP)P(QP)(P)(PP(PQ)15、(PQ)(PR)證明、Q)(QR),SPS(PQ)(PR)前提(2) P(QR)(1)(3) (QR)前提(4) P(2),(5) SP前提(6) S,(5)16、PQ, Q證明、(1) P(2) P(3)(4) Q(5)(6) ) R(7) R(8) RR, R S P附加前提Q前提Q(1), (2)R前提R(3), (4)S 前提(6)R(5),17、用真值表法證明PQ ( P Q) (Q P)證明、列出兩個公式的真值表:PQPQ(P

37、Q(QP)FFTTFTFFTFFFTTTT由定義可知，這兩個公式是等價的。18、QPf(PQ)證明：設(shè)P一(PQ)為F,則P為T,PQ為F。所以P為T,Q為F,從而P-Q也為F。所以P-QP-(PQ)。19、用先求主范式的方法證明（P-Q）(P-R)(P-QR)證明：先求出左右兩個公式的主合取范式(P-Q)(P-R)(PQ)(PR)(PQ(RR)P(QQ)R)PQR)(PR)PQR)(QR)PQR)(PQR)PQR)(P-(QR)R)(PQ)(R)它們有一樣的主合取范式，所以它們等價。PQ(RPQR)R)(PPQR)(20、(PQ)(QR)證明：設(shè)(P-Q)故4QQ和P(QQ)R)R)QR)(

38、QR)PQR)QR)所以它們等價。(QR)為T,則4Q和(QR）都為ToR都為ToR）都為T,即4Q為T,Q和R都為F。從而P也為F,即P為T。從而(P-Q)(QR)21、為慶祝九七香港回歸祖國，四支足球隊(duì)進(jìn)行比賽，已知情況如下，問結(jié)論是否有效?:(1)若A隊(duì)得第一，則B隊(duì)或C隊(duì)獲亞軍;(2)若C隊(duì)獲亞軍，則A隊(duì)不能獲冠軍;(3)若D隊(duì)獲亞軍，則B隊(duì)不能獲亞軍;(4)A隊(duì)獲第一;結(jié)論:（5）D隊(duì)不是亞軍。證明：設(shè)A：A隊(duì)得第一;B:B隊(duì)獲亞軍;C:C隊(duì)獲亞軍;D:D隊(duì)獲亞軍;則前提符號化為A(BC),CA,DB,A;結(jié)論符號化為D。本題即證明A(BQ),CA,DB,AD(1)A前提A(BC)前

39、提(3) BC(1),(2)(4) CA前提(5) C(1),(4)(6) B(3),(5)(7) DB前提(8) D(6),(7)22、用推理規(guī)則證明PQ,(QR),PR不能同時為真。證明：(1) PR前提(2) P(1)(3) PQ前提Q(2),(3)(5) (QR)前提(6) QR(5)(7) Q(6)(8) QQ,(7)(集合論部分)四、設(shè)A,B,C是三個集合，證明：1、A(B-C)=(AB)(AC)證明：(AB)-(AC)=(AB)AC=(AB)(AC)=(ABA)(ABC)=ABC=A(BC)=A(B-C)2、(A-B)(AC尸A(BC)證明：(A-B)(A-C)=(AB)(AC)

40、=A(BC)=ABC=A-(BC)3、AB=AC,AB=AC,貝UC=B證明：B=B(AA)=(BA)(BA)=(C A) (C4、A B=A (B-A)證明：A(B-A尸A (B=(A B) U= A5、A=B A B=證明：A)=C ( A A)=CA)=(AB) (A A)B設(shè)A=B貝UAB=(A-B)(B-A)設(shè)AB=，則AB=(A-B)(B-A)=。故A-B=,B-A=從而AB,BA,故A=B6、AB=AC,AB=AC,貝UC=B證明：B=B(AB)=B(AC)=(BA)(BC)=(AC)(BnC)=C(AB)=C(AC)=C7、AB=AC,AB=aC,貝UC=B證明：B=B(AA)

41、=(BA)(BA)=(CA)(CA)=C(AA)=C8、A-(BC)=(A-B)-C證明：A-(BC)=ABC=A(BC)=(AB)C=(A-B)C=(A-B)-C9、(AB)(AC尸A(BC)證明：(A-B)(A-C)=(AB)(AC)=(AA)(BC)=ABC=A(BC)10、A-B=B,貝UA=B=證明：因?yàn)锽=A-B,所以B=BB=(A-B)B=。從而A=A-B=B=。11、A=(A-B)(A-C)ABC=證明：因?yàn)?A-B)(A-C)=(AB)(AC)=A(BC)=ABC=A-(BC),且A=(A-B)(A-C),所以人=A-(BC),故ABC=。因?yàn)锳BC=，所以A-(BC尸A。而

42、A-(BC)=(A-B)(A-C),所以A=(A-B)(A-C)。12、(A-B)(A-C)=ABC證明：因?yàn)?A-B)(A-C)=(AB)(AC)=A(BC)=ABC=A-(BC),且(A-B)(A-C)=,所以=A-(BC),故ABCo因?yàn)锳BC,所以A-(BC尸A。而A-(BC)=(A-B)(A-C),所以A=(A-B)(A-C)。13、(A-B)(B-A)=AB=證明：因?yàn)?A-B)(B-A尸A,所以B-AA。但(B-A)A=,故B-A=即BA,從而B=(否則A-BA,從而與(A-B)(B-A尸A矛盾)。因?yàn)锽=，所以A-B=A且B-A=。從而(A-B)(B-A)=A。14、(A-B)

43、-CA-(B-C)證明：X(A-B)-C,有xA-B且xC,即xA,xB且xC。從而xA,xB-C,故xA-(B-C)。從而(A-B)-CA-(B-C)15、P(A)P(B)P(AB)(P(S)表示S的募集)證明：SP(A)P(B),有SP(A)或SP(B),所以SA或SB。從而SAB,故SP(AB)o即P(A)P(B)P(AB)16、P(A)P(B)=P(AB)(P(S)表示S的募集)證明：SP(A)P(B),有SP(A)且SP(B),所以SA且SB。從而SAB,故SP(AB)o即P(A)P(B)P(AB)。SP(AB),有SAB,所以SA且SB。從而SP(A)且SP(B),故SP(A)P(

44、B)0即P(AB)P(A)P(B)。故P(AB)=P(A)P(B)17、(A-B)B=(AB)-B當(dāng)且僅當(dāng)B=。證明：當(dāng)B=時，因?yàn)?A-B)B=(A-)=A，(AB)-B=(A)-二A,所以(A-B)B=(AB)-Bo用反證法證明。假設(shè)B,則存在bB。因?yàn)閎B且bAB,所以b(AB)-Bo而顯然b(A-B)B。故這與已知(A-B)B=(AB)-B矛盾。五、證明或解答：(數(shù)理邏輯、集合論與二元關(guān)系部分)1 、設(shè)個體域是自然數(shù)，將下列各式翻譯成自然語言：(1) xy(xy=1);(2)xy(xy=1);(3)xy(xy=0);(4)xy(xy=0);(5)xy(xy=x);(6)xy(xy=x)

45、;(7) xyz(x-y=z)答：( 1)存在自然數(shù)x，對任意自然數(shù)y滿足xy=1;( 2)對每個自然數(shù)x，存在自然數(shù)y滿足xy=1;( 3)對每個自然數(shù)x，存在自然數(shù)y滿足xy=0;( 4)存在自然數(shù)x，對任意自然數(shù)y滿足xy=1;( 5)對每個自然數(shù)x,存在自然數(shù)y滿足xy=x;( 6)存在自然數(shù)x，對任意自然數(shù)y滿足xy=x;( 7)對任意自然數(shù)x,y，存在自然數(shù)z滿足x-y=z。2、設(shè)A(x,y,z):x+y=z,M(x,y,z):xy=z,L(x,y):x<y,G(x,y):x>y個體域?yàn)樽匀粩?shù)。將下列命題符號化：(1)沒有小于0的自然數(shù);(2)x<z是x<y

46、且y<z的必要條件;(3)若x<y,則存在某些z,使z<0,xz>yz;(4)存在x,對任意y使得xy=y;(5)對任意x，存在y使x+y=x。答：( 1) x(G(x,0)M(0,0,x)或xL(x,0)( 2) xyz(L(x,y)L(y,z)L(x,z)( 3) xy(L(x,y)z(L(z,0)G(xz,yz)( 4) xyM(x,y,y)( 5) xyA(x,y,x)3、列出下列二元關(guān)系的所有元素：(1)A=0,1,2，B=0,2,4，R=<x,y>|x,yAB;(2) A=1,2,3,4,5,B=1,2,R=<x,y>|2x+y4且x

47、A且yB;(3) A=1,2,3 , B=-3,-2,-1,0,1),R=<x,y>|x|=|y| 且 x A且 y B;解：(1)R=<0,0>,<0,2>,<2,0>,<2,2>(2)R=<1,1>,<1,2>,<2,1>,<2,2>,<3,1>(3) R=<1,1>,<1,-1>,<2,-2>,<3,-3>。4、對任意集合A,B,證明：若AA=BB,則B=B證明：若B=，則BB=o從而AA=。故A=o從而B=A若B，則BB

48、o從而AAo對xB,<x,x>BB。因?yàn)锳A=BB,則<x,x>AA。從而xA。故BA。同理可證，ABo故B=A5、對任意集合A,B,證明：若A,AB=AC,則B=G證明：若B=，則A B=若B ，則A B對x B,因?yàn)锳<y,x> A C。從而 xo從而A C = o因?yàn)锳o從而A C o,所以存在y A,使<y,x> 故B C。,所以C= o即B=GA B。因?yàn)锳 B=A C,則同理可證，CBo故B=G6、設(shè)A=a,b,B=c。求下列集合：(1)A0,1B;(2)B2A;(3) (AB)2;(4)P(A)A解：(1) A0,1B=<a,

49、0,c>,<a,1,c>,<b,0,c>,<b,1,c>(2) B2A=<c,c,a>,<c,c,b>/C、，Af、2(3) (AB)=<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>,b>,<a,a>,<a,b>,<b,a>,<b,b>(4) P(A)A=<,a>,<,<A,a>,<A,b>o7、設(shè)全集U=a,b,c,d,e,A=a,d,B=a,b,c,C

50、=b,d。求下列各集合：(1)ABC;(2)ABC；(3)(AB)C；(4) P(A)-P(B);(A-B)(B-C);(6)(AB)C;解：(1) ABC=a;(2)ABC=a,b,c,d,e;(3) (AB)C=b,d;(4)P(A)-P(B尸d,a,d;(5) (A-B)(B-C尸d,c,a;(6)(AB)C=b,d。8、設(shè)A,B,C是任意集合，證明或否定下列斷言：(1)若AB,且BC,則AC;(2)若AB,且BC,則AC;(3)若AB,且BC,則AC;(4)若AB,且BC,則AC;證明：(1) 成立。對xA,因?yàn)锳B,所以xBo又因?yàn)锽C,所以xC。即AC=(2) 不成立。反例如下：A

51、=a,B=a,b,C=a,b,c。雖然AB,且BC,但ACo(3) 不成立。反例如下：A=a,B=a,b,C=a,b,c。雖然AB,且BC,但ACo(4) 成立。因?yàn)锳B,且BC,所以AC9、A上的任一良序關(guān)系一定是A上的全序關(guān)系。證明：a,bCA,則a,b是A的一個非空子集。W是A上的良序關(guān)系，a,b有最小元。若最小元為a,則a<b;否則b<a0從而W為A上的的全序關(guān)系。10、若R和S都是非空集A上的等價關(guān)系，則RS是A上的等價關(guān)系。證明：aCA,因?yàn)镽和S都是A上的等價關(guān)系，所以xRx且xSx。故xRSx。從而RS是自反的a,bCA,aRSb,即aRb且aSbo因?yàn)镽和S都是A

52、上的等價關(guān)系，所以bRa且bSa。故bRSa。從而RS是對稱的。a,b,cCA,aRSb且bRSc,即aRb,aSb,bRc且bSc。因?yàn)镽和S都是A上的等價關(guān)系，所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價關(guān)系。11、設(shè)RAXA,則R自反IaR。證明：xA,R是自反的，xRx。IP<x,x>R,故IaR。xA,IaR,<x,x>R。即xRx,故R是自反的。12、設(shè)A是集合，RAXA,則R是對稱的R=R1。證明：<x,y>R,R是對稱的，yRx01P<y,x>R,故<乂,丫>R1。從而RR1。反之<y,x

53、>R1i（J<x,y>R。R是對稱的，yRx。即<丫叢>R,R-1R。故R=R-1。x,yA,若<乂,丫>R,即<y,x>R1。R=R-1,<y,x>R。即yRx,故R是對稱的。13、設(shè)A,B,C和D均是集合，RAXB,SBXC,TCXD,則(1) R(ST)=(RS)(RT)；(2) R(ST)(RS)(RT)；證明：(1) <x,z>R(ST),則由合成關(guān)系的定義知yB,使得<乂，y>R且<y,z>STo從而<x,y>R且<y,z>$或<乂，y>R且&l

54、t;y,z>T,1P<x,z>RS或<x，z>RT。故<x，z>(RS)(RT)。從而R(ST)(RS)(RT)。同理可證(RS)(RT)R(ST)。故R(ST)=(RS)(RT)。(2) <x,z>R(ST),則由合成關(guān)系的定義知yB,使得<x,y>R且<y,z>STo從而<x,y>R且<y,z>$且<丫，z>T,1P<x,z>R$且<乂，z>RT。故<x，z>(RS)(RT)。從而R(ST)(RS)(RT)。14、設(shè)A,w為偏序集，BA,若B有最大（?。┰⑸希ㄏ拢┐_界，則它們是惟一的證明：是A上的偏序關(guān)設(shè)a,b都是B的最大元，則由最大元的定義ab,ba。系，a=b