《離散數(shù)學(xué)》題庫(kù)及答案.doc

《《離散數(shù)學(xué)》題庫(kù)及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》題庫(kù)及答案.doc（69頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

2、（3）類似附加律，（4）是假言推理，（3），（5），（6）都可以用蘊(yùn)含等值式來(lái)證明出是永真蘊(yùn)含式4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由變?cè)? )，約束變?cè)? )。答：x,y, x,z（考察定義在公式x A和$x A中，稱x為指導(dǎo)變?cè)?，A為量詞的轄域。在x A和$x A的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，即稱x為約束變?cè)?，A中不是約束出現(xiàn)的其他變項(xiàng)則稱為自由變?cè)Ｓ谑茿(x)、B(y，x)和$z C(y，z)中y為自由變?cè)瑇和z為約束變?cè)?，在D(x)中x為自由變?cè)?、判斷下列語(yǔ)句是不是命題。若是，給出命題的真值。( )(1) 北京是中華人民共和國(guó)的首都。

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

4、) 若我生病，則我不去學(xué)校(3)當(dāng)且僅當(dāng)我生病時(shí)，我才不去學(xué)校(4) 若我不生病，則我一定去學(xué)校答：（1） （注意“只有才”和“除非就”兩者都是一個(gè)形式的） （2） （3） （4）8、設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)答：（1）對(duì)任一整數(shù)x存在整數(shù) y滿足x+y=0（2）存在整數(shù)y對(duì)任一整數(shù)x滿足x+y=09、設(shè)全體域D是正整數(shù)集合，確定下列命題的真值：(1) x$y (xy=y)()(2) $xy(x+y=y)()(3) $xy(x+y=x) ()(4) x$y(y=2x) ()答：（1） F (反證法：假若存在，則（x-

5、1）*y=0 對(duì)所有的x都成立，顯然這個(gè)與前提條件相矛盾) （2） F （同理） （3）F （同理） （4）T（對(duì)任一整數(shù)x存在整數(shù) y滿足條件 y=2x 很明顯是正確的）10、設(shè)謂詞P(x)：x是奇數(shù)，Q(x)：x是偶數(shù)，謂詞公式 $x(P(x)Q(x)在哪個(gè)個(gè)體域中為真?( )(1) 自然數(shù)(2) 實(shí)數(shù) (3) 復(fù)數(shù)(4) (1)-(3)均成立答：（1）（在某個(gè)體域中滿足不是奇數(shù)就是偶數(shù)，在整數(shù)域中才滿足條件，而自然數(shù)子整數(shù)的子集，當(dāng)然滿足條件了）11、命題“2是偶數(shù)或-3是負(fù)數(shù)”的否定是（ ）。答：2不是偶數(shù)且-3不是負(fù)數(shù)。12、永真式的否定是（ ）(1) 永真式(2) 永假式(3) 可

6、滿足式(4) (1)-(3)均有可能答：（2）（這個(gè)記住就行了）13、公式(PQ)(PQ)化簡(jiǎn)為（ ），公式 Q(P(PQ)可化簡(jiǎn)為（ ）。答：P ，QP（考查分配率和蘊(yùn)含等值式知識(shí)的掌握）14、謂詞公式x(P(x) $yR(y)Q(x)中量詞x的轄域是（ ）。答：P(x) $yR(y)（一對(duì)括號(hào)就是一個(gè)轄域）15、令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則命題“并非每個(gè)實(shí)數(shù)都是有理數(shù)”的符號(hào)化表示為（ ）。答：x(R(x)Q(x)（集合論部分）16、設(shè)A=a,a，下列命題錯(cuò)誤的是（ ）。(1) aP(A)(2) aP(A)(3) aP(A)(4) aP(A)答：(2) （a是P（A）的一

7、個(gè)元素）17、在0（ ）之間寫上正確的符號(hào)。(1) =(2) (3) (4) 答：(4)（空集沒有任何元素，且是任何集合的子集）18、若集合S的基數(shù)|S|=5，則S的冪集的基數(shù)|P(S)|=（ ）。答：32（2的5次方 考查冪集的定義，即冪集是集合S的全體子集構(gòu)成的集合）19、設(shè)P=x|(x+1)4且xR,Q=x|5x+16且xR,則下列命題哪個(gè)正確（ ） (1) QP(2) QP(3) PQ(4) P=Q答：（3）（Q是集合R，P只是R中的一部分，所以P是Q的真子集）20、下列各集合中，哪幾個(gè)分別相等( )。(1) A1=a,b (2) A2=b,a (3) A3=a,b,a (4) A4=

8、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=A6， A4=A5（集合具有無(wú)序性、確定性和互異性）21、若A-B=，則下列哪個(gè)結(jié)論不可能正確？( )(1) A= (2) B=(3) AB (4) BA答：（4）（差集的定義）22、判斷下列命題哪個(gè)為真?( )(1) A-B=B-A = A=B (2) 空集是任何集合的真子集(3) 空集只是非空集合的子集 (4) 若A的一個(gè)元素屬于B，則A=B答：（1）（考查空集和差集的相關(guān)知識(shí)）23、判斷下列命題哪幾個(gè)為正確？()(1) , (2) , (3) (4) (5)

9、 a,ba,b,a,b答：（2），（4）24、判斷下列命題哪幾個(gè)正確？()(1) 所有空集都不相等 (2) (4) 若A為非空集，則AA成立。答：（2）25、設(shè)AB=AC，B=C，則B()C。答：=（等于）26、判斷下列命題哪幾個(gè)正確？()(1) 若ABAC，則BC (2) a,b=b,a (3) P(AB)P(A)P(B) （P(S)表示S的冪集）(4) 若A為非空集，則AAA成立。答：（2） 27、，是三個(gè)集合，則下列哪幾個(gè)推理正確：(1) AB，BC= AC (2) AB，BC= AB (3) AB，BC= AC答：（1） （3）的反例 C為0，1，0 B為0，1，A為1 很明顯結(jié)論不對(duì)

10、）（二元關(guān)系部分）28、設(shè)1,2,3,4,5,6，B=1,2,3，從到B的關(guān)系x,y|x=y2求(1)R (2) R-1 答：（1）R=, (2) R=,（考查二元關(guān)系的定義，R為R的逆關(guān)系，即R=| R）29、舉出集合A上的既是等價(jià)關(guān)系又是偏序關(guān)系的一個(gè)例子。()答：A上的恒等關(guān)系30、集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是什么？( )答：自反性、對(duì)稱性和傳遞性31、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是什么？( )答：自反性、反對(duì)稱性和傳遞性(題29，30，31全是考查定義)32、設(shè)S=,，上的關(guān)系1,2，2,1，2,3，3,4求(1)RR (2) R-1 。答：RR =1,1，1,3，2,2，2,4（考

11、查FG =|$t(FG)）R-1 =2,1，1,2，3,2，4,333、設(shè)1，2，3，4，5，6，是A上的整除關(guān)系，求R= ()R=,34、設(shè)1,2,3,4,5,6，B=1,2,3，從到B的關(guān)系x,y|x=2y，求(1)R (2) R-1 。答：（1）R=, (2) R=,(3635、設(shè)1,2,3,4,5,6，B=1,2,3，從到B的關(guān)系x,y|x=y2，求R和R-1的關(guān)系矩陣。答：R的關(guān)系矩陣= R的關(guān)系矩陣=36、集合A=1,2,10上的關(guān)系R=|x+y=10,x,yA，則R 的性質(zhì)為（ ）。(1) 自反的(2) 對(duì)稱的 (3) 傳遞的，對(duì)稱的 (4) 傳遞的答：（2）（考查自反 對(duì)稱 傳

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

13、階元素。答： 6,441、代數(shù)系統(tǒng)是一個(gè)群，則G的等冪元是()。答：?jiǎn)挝辉ㄓ蒩2=a,用歸納法可證an=a*a(n-1)=a*a=a，所以等冪元一定是冪等元，反之若an=a對(duì)一切N成立，則對(duì)n=2也成立，所以冪等元一定是等冪元，并且在群中，除幺元即單位元e外不可能有任何別的冪等元）42、設(shè)a是10階群的生成元， 則a4是( )階元素，a3是( )階元素答：5，10（若一個(gè)群G的每一個(gè)元都是G的某一個(gè)固定元a的乘方，我們就把G叫做循環(huán)群；我們也說，G是由元a生成的，并且用符號(hào)G=表示，且稱a為一個(gè)生成元。并且一元素的階整除群的階）43、群的等冪元是()，有()個(gè)。答：?jiǎn)挝辉? （在群中，除幺

14、元即單位元e外不可能有任何別的冪等元）44、素?cái)?shù)階群一定是( )群, 它的生成元是( )。答：循環(huán)群，任一非單位元（證明如下：任一元素的階整除群的階?，F(xiàn)在群的階是素?cái)?shù)p，所以元素的階要么是1要么是p。G中只有一個(gè)單位元，其它元素的階都不等于1，所以都是p。任取一個(gè)非單位元，它的階等于p，所以它生成的G的循環(huán)子群的階也是p，從而等于整個(gè)群G。所以G等于它的任一非單位元生成的循環(huán)群）45、設(shè)G,*是一個(gè)群，a,b,cG，則(1) 若ca=b，則c=( )；(2) 若ca=ba，則c=( )。答：（1） b (2) b（群的性質(zhì)）46、是的子群的充分必要條件是( )。答：是群 或 a，b G， ab

15、H，a-1H 或 a,b G，ab-1H 47、群A,*的等冪元有()個(gè)，是()，零元有()個(gè)。答：1，單位元，048、在一個(gè)群G,*中，若G中的元素a的階是k，則a-1的階是( )。答：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、任意一個(gè)具有2個(gè)或以上元的半群，它（ ）。(1) 不可能是群(2) 不一定是群(3) 一定是群 (4) 是交換群答：(1)51、6階有限群的任何子群一定不是（ ）。(1) 2階(2) 3 階 (3) 4 階 (4) 6 階答：(3)（格與布

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

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

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

19、樹葉。答：268、任何連通無(wú)向圖G至少有( )棵生成樹，當(dāng)且僅當(dāng)G 是( )，G的生成樹只有一棵。答：1， 樹69、設(shè)G是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，且有k個(gè)面，則k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。答：（1）70、設(shè)T是一棵樹，則T是一個(gè)連通且( )圖。答：無(wú)簡(jiǎn)單回路71、設(shè)無(wú)向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖G有( )個(gè)頂點(diǎn)。 (1) 10 (2) 4 (3) 8 (4) 16答：（4）72、設(shè)無(wú)向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3，則圖G有( )個(gè)頂點(diǎn)。 (1) 10 (2) 4 (3) 8 (4) 12答：(4)73、

20、設(shè)圖G=，V=a，b，c，d，e，E=,則G是有向圖還是無(wú)向圖？答：有向圖74、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有()個(gè)。答：偶數(shù)75、具有6 個(gè)頂點(diǎn)，12條邊的連通簡(jiǎn)單平面圖中，每個(gè)面都是由()條邊圍成？(1) 2(2) 4(3) 3(4) 5答：（3）76、在有n個(gè)頂點(diǎn)的連通圖中，其邊數(shù)（ ）。(1) 最多有n-1條(2) 至少有n-1 條(3) 最多有n條 (4) 至少有n 條答：（2）77、一棵樹有2個(gè)2度頂點(diǎn)，1 個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，則其1度頂點(diǎn)為（ ）。(1) 5(2) 7 (3) 8 (4) 9答：（4）78、若一棵完全二元（叉）樹有2n-1個(gè)頂點(diǎn)，則它（ ）片樹葉。(1)

21、n(2) 2n (3) n-1 (4) 2答：（1）79、下列哪一種圖不一定是樹（ ）。(1) 無(wú)簡(jiǎn)單回路的連通圖(2) 有n個(gè)頂點(diǎn)n-1條邊的連通圖 (3) 每對(duì)頂點(diǎn)間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖答：（3）80、連通圖G是一棵樹當(dāng)且僅當(dāng)G中（ ）。(1) 有些邊是割邊(2) 每條邊都是割邊(3) 所有邊都不是割邊 (4) 圖中存在一條歐拉路徑答：（2）（數(shù)理邏輯部分）二、求下列各公式的主析取范式和主合取范式： 1、(PQ)R 解：(PQ)R(PQ )R(PR)(QR) （析取范式）(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)

22、(PQR)（主析取范式）(PQ)R)(PQR)(PQR)(PQR) (PQR)( PQR)（原公式否定的主析取范式）(PQ)R(PQR)(PQR)(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、(PQ)(

23、RP)解：(PQ)(RP)(PQ)(RP)（合取范式）(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主合取范式） (PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主合取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）4、Q(PR) 解：Q(PR)QPR（主合取范式）（Q(PR)）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（原公式否定的主合取范式）Q(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（主析取范式）5

24、、P(P(QP) 解：P(P(QP)P(P(QP)PP T (主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）6、(PQ)(RP)解： (PQ)(RP)(PQ)(RP)(PQ)(RP)（析取范式）(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）7、P(PQ) 解：P(PQ)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范

25、式）8、(RQ)P解：(RQ)P(RQ )P(RP)(QP) （析取范式）(R(QQ)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）(RQ)P)(PQR)(PQR）(PQR) (PQR)(PQR)（原公式否定的主析取范式）(RQ)P(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）9、PQ 解：PQPQ（主合取范式）(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)

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

27、Q(RR)(PP)(QQ)R)(PQR)(PQR)(PQR)(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)(PQ

28、R)(PQR)(PQR)(PQR)(PQR)(PQR)(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)(PQ)(PR) (合取范式)(PQ(RR)(P(QQ)R)(P

29、QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、證明：1、PQ，QR，R，SP=S證明：(1) R 前提(2) QR 前提(3) Q （1），（2）(4) PQ 前提(5) P （3），（4）(6) SP 前提(7) S （5），（6）2、A(BC)，C(DE)，F(xiàn)(DE),A=BF證明： (1) A 前提(2) A(BC) 前提 (3) BC （1

30、），（2）(4) B 附加前提(5) C （3），（4）(6) C(DE) 前提(7) DE （5），（6）(8) F(DE) 前提(9) F （7），（8）(10) BF CP 3、PQ， PR, QS = RS證明：(1) R 附加前提(2) PR 前提(3) P （1），（2）(4) PQ 前提(5) Q （3），（4）(6) QS 前提(7) S （5），（6）(8) RS CP，（1），（8）4、(PQ)(RS)，(QW)(SX)，(WX)，PR = P證明： （1） P 假設(shè)前提（2） PR 前提（3） R （1），（2）（4） (PQ)(RS) 前提（5） PQ （4）（6） R

31、S （5）（7） Q （1），（5）（8） S （3），（6）（9） (QW)(SX) 前提（10） QW （9）（11） SX （10）（12） W （7），（10）（13） X （8），（11）（14） WX （12），（13）（15） (WX) 前提（16） (WX)(WX) （14），（15）5、(UV)(MN), UP, P(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、BD，(EF)D

32、，E=B證明：(1) B 附加前提(2) BD 前提 (3) D （1），（2）(4) (EF)D 前提(5) (EF) （3），（4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7），（8）7、P(QR)，R(QS) = P(QS)證明：（1） P 附加前提（2） Q 附加前提（3） P(QR) 前提（4） QR （1），（3）（5） R （2），（4）（6） R(QS) 前提（7） QS （5），（6）（8） S （2），（7）（9） QS CP，（2），（8）（10） P(QS) CP，（1），（9）8、PQ，PR，RS =SQ 證明：（1） S 附加前提（2）

33、 RS 前提（3） R （1），（2）（4） PR 前提（5） P （3），（4）（6） PQ 前提（7） Q (5），（6）（8） SQ CP，（1），（7）9、P(QR) = (PQ)(PR)證明：(1) PQ 附加前提(2) P 附加前提(3) Q (1),(2)(4) P(QR) 前提(5) QR (2),(4)(6) R (3),(5)(7) PR CP,(2),(6)(8) (PQ) (PR) CP,(1),(7)10、P(QR)，QP,SR,P =S證明：（1） P 前提（2） P(QR) 前提（3） QR (1)，(2)（4） QP 前提（5） Q (1)，(4)（6） R (

34、3),(5)（7） SR 前提（8） S (6)，(7)11、A，AB， AC， B(DC) = D證明：（1） A 前提（2） AB 前提（3） B (1)，(2)（4） AC 前提（5） C (1)，(4)（6） B(DC) 前提（7） DC (3)，(6)（8） D (5)，(7)12、A(CB)，BA，DC = AD證明：（1） A 附加前提(2) A(CB) 前提 (3) CB （1），（2）(4) BA 前提(5) B （1），（4）(6) C （3），（5）(7) DC 前提(8) D （6），（7）(9) AD CP，（1），（8）13、(PQ)(RQ) （PR）Q證明、(PQ

35、)(RQ) (PQ)(RQ)(PR)Q （PR）Q(PR)Q14、P(QP)P(PQ)證明、P(QP)P(QP)(P)(PQ)P(PQ)15、（PQ）（PR），(QR)，SPS證明、(1) （PQ）（PR） 前提 （2） P (QR) (1) （3） (QR) 前提 （4） P （2），(3) (5) SP 前提 (6) S (4),(5)16、PQ，QR，RS P證明、(1) P 附加前提 （2） PQ 前提 （3） Q （1），（2） （4） QR 前提 (5) R （3），（4） (6 ) RS 前提 （7） R （6） （8） RR （5），（7）17、用真值表法證明 ()()證明、列

36、出兩個(gè)公式的真值表：P Q PQ （PQ）（QP） F FF TT FT TT TF FF FT T由定義可知，這兩個(gè)公式是等價(jià)的。18、PQP(PQ)證明：設(shè)P(PQ)為F，則P為T，PQ為F。所以P為T，Q為F ，從而PQ也為F。所以PQP(PQ)。19、用先求主范式的方法證明(PQ)(PR) (P（QR）證明：先求出左右兩個(gè)公式 的主合取范式(PQ)(PR) (PQ)(PR)(PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (P（QR）) (P（QR）) (PQ)(PR)(PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)

37、(PQR) (PQR)(PQR)(PQR)它們有一樣的主合取范式，所以它們等價(jià)。20、(PQ)(QR) P證明：設(shè)(PQ)(QR)為T，則PQ和(QR)都為T。即PQ和QR都為T。故PQ，Q和R)都為T，即PQ為T，Q和R都為F。從而P也為F，即P為T。從而(PQ)(QR) P21、為慶祝九七香港回歸祖國(guó)，四支足球隊(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ì)獲亞軍;

38、D: D隊(duì)獲亞軍;則前提符號(hào)化為A（BC），CA，DB，A；結(jié)論符號(hào)化為 D。 本題即證明 A（BC），CA，DB，AD（1） A 前提 （2） A（BC）前提 （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不能同時(shí)為真。證明： (1) PR 前提 (2) P (1) (3) PQ 前提 (4) Q (2),(3) (5) (QR) 前提 (6) QR (5) (7) Q (6) (8) QQ (4),(7)(集合論部分)四、設(shè)，是三個(gè)集合，證明：

39、1、A (BC)(AB)(AC) 證明：(AB)(AC)= (AB) =(AB) （）=(AB)(AB)= AB=A（B）=A（B-C）2、(AB)(AC)=A(BC)證明：(A-B)(A-C)=(A)(A) =A ()=A= A-(BC)3、AB=AC，B=C，則C=B證明：B=B(A)=(B) (BA)=(C) (CA)=C(A)=C 4、AB=A(B-A)證明： A(B-A)=A(B)=(AB)(A)=(AB)U= AB5、A=B AB= 證明：設(shè)A=B，則AB=（A-B）（B-A）=。設(shè)AB=，則AB=（A-B）（B-A）=。故A-B=，B-A=，從而AB，BA，故A=B。6、AB =

40、 AC，AB=AC，則C=B證明：B=B(AB)= B(AC)= (BA)(BC)= (AC)(BC)= C(AB)= C(AC)=C7、AB=AC，B=C，則C=B 證明：B=B(A)=(BA)(B)=(CA)(C)=C(A)=C8、A(BC)(AB)C證明：A(BC)= A=A()=(A)=(A-B)=(A-B)-C9、(AB)(AC)=A(BC)證明：(A-B)(AC)=(A)(A)=(AA)()=A=A(BC)10、A-B=B，則A=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) =

41、(A)(A) =A()=A= A-(BC)，且A=(A-B)(A-C)， 所以A= A-(BC)，故ABC=。 因?yàn)锳BC=，所以A-(BC)=A。而A-(BC)= (A-B)(A-C)， 所以A=(A-B)(A-C)。12、(A-B)(A-C)=ABC證明： 因?yàn)?A-B)(A-C) =(A)(A) =A()=A= A-(BC)，且(A-B)(A-C)=， 所以= A-(BC)，故ABC。 因?yàn)锳BC，所以A-(BC)=A。而A-(BC)= (A-B)(A-C)， 所以A=(A-B)(A-C)。13、(A-B)(B-A)=A B=證明： 因?yàn)?A-B)(B-A)=A，所以B-AA。但(B-A

42、)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)-CA-(B-C)證明：x(A-B)-C，有A-B且xC，即A，xB且xC。從而A，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)。即P(A)P(B)P(AB) 16、P(A)P(B)=P(AB) （P(S)表示S的冪集）證明：SP(A)P(B)，有SP

43、(A)且SP(B)，所以SA且SB。從而SAB，故SP(AB)。即P(A)P(B)P(AB)。SP(AB)，有SAB，所以SA且SB。從而SP(A)且SP(B)，故SP(A)P(B)。即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=時(shí)，因?yàn)椋ˋ-B）B=（A-）=A，（AB）-B=（A）- =A，所以（A-B）B=（AB）-B。用反證法證明。假設(shè)B，則存在bB。因?yàn)閎B且b AB，所以b（AB）-B。而顯然b（A-B）B。故這與已知（A-B）B=（AB）-B矛盾。五、證明或解答：（數(shù)理邏輯、集合論與二元關(guān)系部分）1、設(shè)個(gè)體

44、域是自然數(shù)，將下列各式翻譯成自然語(yǔ)言：(1) xy（xy=1）; (2) xy(xy=1);(3) xy (xy=0); (4) xy（xy=0）;(5) xy (xy=x); (6) xy（xy=x）;(7) xyz (x-y=z)答：（1）存在自然數(shù)x，對(duì)任意自然數(shù)y滿足xy=1;（2）對(duì)每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=1;（3）對(duì)每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=0;（4）存在自然數(shù)x，對(duì)任意自然數(shù)y滿足xy=1;（5）對(duì)每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=x;（6）存在自然數(shù)x，對(duì)任意自然數(shù)y滿足xy=x;（7）對(duì)任意自然數(shù)x,y，存在自然數(shù)z滿足x-y=z。2、設(shè)A(x,y,z

45、): x+y=z, M（x,y,z）: xy=z, L(x,y): xy， 個(gè)體域?yàn)樽匀粩?shù)。將下列命題符號(hào)化：（1）沒有小于0的自然數(shù);（2）xz是xy且yz的必要條件;（3）若xy，則存在某些z，使zyz;（4）存在x，對(duì)任意y 使得xy=y;（5）對(duì)任意x，存在y使x+y=x。答：（1）x（G(x,0)M（0,0,x） 或x L(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;（2）A=

46、1,2,3,4,5，B=1,2，R=|2x+y4且x且yB;（3）A=1,2,3，B=-3,-2,-1,0,1，R=|x|=|y|且x且yB;解：(1) R=,(2) R=,;(3) R=,。4、對(duì)任意集合A,B，證明：若AA=BB，則B=B。證明：若B=，則BB=。從而AA =。故A=。從而B=A。 若B，則BB。從而AA。對(duì), BB。因?yàn)锳A=BB，則A。從而xA。故BA。同理可證，AB。故B=A。5、對(duì)任意集合A,B，證明：若A，AB=AC，則B=C。證明：若B=，則AB=。從而AC =。因?yàn)锳，所以C=。即B=C。 若B，則AB。從而AC。對(duì),因?yàn)锳，所以存在yA, 使B。因?yàn)锳B=A

47、C，則C。從而xC。故BC。同理可證，CB。故B=C。6、設(shè)A=a,b, B=c。求下列集合：(1) A0,1B； (2) B2A；(3) (AB)2; (4) P(A)A。解：（1） A0,1B=,;（2） B2A=,;（3） (AB)2=,;（4） P(A)A=,。7、設(shè)全集U=a,b,c,d,e, A=a,d, B=a,b,c, C=b,d。求下列各集合：（1）AB； （2）；（3）(A)C; （4）P(A)-P(B); （5）(A-B)(B-C); （6）(AB)C; 解 ：(1) AB=a; (2) =a,b,c,d,e;(3) （A）C=b,d; (4) P(A)-P(B)=d,a

48、,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) 成立。對(duì)xA, 因?yàn)锳B，所以xB。又因?yàn)锽C，所以xC。即AC。(2) 不成立。反例如下：A=a, B=a,b,C=a,b,c。雖然AB，且BC，但AC。(3) 不成立。反例如下：A=a, B=a,b,C=a,b,c。雖然AB，且BC，但AC。(4) 成立。因?yàn)锳B, 且BC，所以AC。9、A上的任一良序關(guān)系一定是A上的全序關(guān)系。證明

49、：a，bA，則a,b是A的一個(gè)非空子集。是A上的良序關(guān)系，a,b有最小元。若最小元為a，則ab；否則ba。從而為A上的的全序關(guān)系。10、若R和S都是非空集A上的等價(jià)關(guān)系，則RS是A上的等價(jià)關(guān)系。證明：aA，因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以xRx且xSx。故xRSx。從而RS是自反的。a,bA，aRSb，即aRb且aSb。因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以bRa且bSa。故bRSa。從而RS是對(duì)稱的。a,b,cA，aRSb且bRSc，即aRb，aSb,bRc且bSc。因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價(jià)關(guān)系。11、設(shè)RAA，則R自反 IAR。證明：xA，R是自反的，xRx。即R，故IAR。xA，IAR，R。即xRx，故R是自反的。12、設(shè)A是集合，RAA，則R是對(duì)稱的RR1。證明：R ，R是對(duì)稱的，yRx。即