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

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

2、的化簡(jiǎn)律，(3)類(lèi)似附加律，(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中，稱(chēng)x為指導(dǎo)變?cè)珹為量詞的轄域。在 x A和x A的轄域中，x的所有出現(xiàn)都稱(chēng)為約束出現(xiàn)，即稱(chēng) x 為約束變?cè)珹中不是約束出現(xiàn)的其他變項(xiàng)則稱(chēng)為自由變?cè)?。于?A(x)、 B(y, x)和 z C(y , z)中y為自由變?cè)瑇和z為約束變?cè)?，?D(x)中x 為自由變?cè)?5、判斷下列語(yǔ)句是不是命題。若是，給出命題的真值。 (

3、)(1)北京是中華人民共和國(guó)的首都。(2)陜西師大是一座工廠。(3)你喜歡唱歌嗎 (4) 若7+8 18,則三角形有4條邊。 前進(jìn)！ (6)給我一杯水吧！答：(1)是，T(2)是，F(xiàn)(3)不是(4)是，T (5)不是 (6)不是(命題必須滿足是陳述何，不能是疑問(wèn)句或者祈使旬。)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) Q P (注意只有才”和除非就”兩者都是一個(gè)形式的)(2) P Q(3) P Q(4) P Q8、設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是 ()。(1) x y(x+y=0) (2) y x(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) x y(x+y=y) ()(3) x y(x+y=x) ()(4) x y(y=2x)()答：(1) F (反證法：假若存在，

5、則(x-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、永真式的否定是()永真式(2)永假式(3)可滿足式(

6、4) (1)-(3) 均有可能答：(2)(這個(gè)記住就行了)13、公式(P Q) ( PQ)化簡(jiǎn)為()，公式Q (P (P Q)可化簡(jiǎn)為()。答：P , Q P (考查分配率和蘊(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è)人=依,但,下列命題錯(cuò)誤的是()。(1) a P(A) (2) a P(A) (3) a P(A) (4) a P(A) 答：(2)

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

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

9、 (5) a,b6 a,b,a,b答：(2), (4)24、判斷下列命題哪幾個(gè)正確()(1)所有空集都不相等(2) (4) 若A為非空集，則A A成立。答：(2)25、設(shè) AA B=AH C, A A B=A A C,貝U B( )C。答:=(等于)26、判斷下列命題哪幾個(gè)正確()(1)若 AU B= AU C,則 B= C (2) a,b=b,a(3) P(A A B) P(A) A P(B) (P(S)表示 S 的募集)(4)若A為非空集，則A AU A成立。答：(2)27、A, B, C是三個(gè)集合，則下列哪幾個(gè)推理正確：(1) A B, B C= A C (2) AB, B C= AS

10、B (3) A SB, B6 C= AS C答：(1)(3)的反例C為 0, 1, 0 B為0, 1, A為1很明顯結(jié)論不對(duì))(二元關(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=, (2) R1=,(考查二元關(guān)系的定義，R1 為 R的逆關(guān)系，即 R 1= | 6 R)29、舉出集合A上的既是等價(jià)關(guān)系又是偏序關(guān)系的一個(gè)例子。()答：A上的恒等關(guān)系30、集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是什么()答：自反性、對(duì)稱(chēng)性和傳遞性31、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是什么()答：自反性、

11、反對(duì)稱(chēng)性和傳遞性(題29, 30, 31全是考查定義)32、設(shè) S= 1 , 2 , 3 , 4 , A上的關(guān)系區(qū)=1,2，2,1，2,3，3,4求(1)R R (2) R -1 。答：R R=1,1，1,3，2,2，2,4(考查 F G=|t( F 6 G)R1 = 2,1，1,2，3,2，4,333、設(shè)人=1, 2, 3, 4, 5, 6, R是A上的整除關(guān)系，求R=()R=,34、設(shè)人=1,2,3,4,5,6 ,B=1,2,3，從 A到 B 的關(guān)系 R= |x=2y ,求(1)R (2) R -1 。答：(1) R=, (2) R 1 =,(3635、設(shè)人=1,2,3,4,5,6 ,B=

12、1,2,3，從A 到 B 的關(guān)系 R= x,y|x=y 2,求R和R1的關(guān)系矩陣。100000:R的關(guān)系矩陣=0000100000001R 1 的關(guān)系矩陣= 0000000001000000036、集合A=1,2,/。上的關(guān)系R=|x+y=10,x,y A,則R的性質(zhì) 為（ ） 。（1） 自反的（2） 對(duì)稱(chēng)的（3） 傳遞的，對(duì)稱(chēng)的（4） 傳遞的答： （ 2） （考查自反對(duì)稱(chēng) 傳遞的定義）（代數(shù)系統(tǒng)部分）37、設(shè)A=2,4,6 , A上的二元運(yùn)算*定義為：a*b=maxa,b,則在獨(dú)異點(diǎn) 中，單位元是（），零元是（）。答：2,6 （單位元和零元的定義，單位元：e。x=x 零元：0 o x= 0

13、）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,x 6 G, a x=b,則 x=（）;（2）若 a,b,x 6 G, a x=a b,則 x=（）。答： （ 1） a 1 b （ 2） b （考查群的性質(zhì)，即群滿足消去律）40、設(shè)a是12階群的生成元，則22是（）階元素，23是（）階元素c答： 6,441、代數(shù)系統(tǒng)是一個(gè)群，則G的等哥元是（）。答：?jiǎn)挝辉ㄓ蒩A2=a,用歸納法可證aAn=a*aA（n-1）=a*a=a ,所以等幕元一定是幕等 元，反

14、之若aAn=a對(duì)一切N成立，則對(duì)n=2也成立，所以幕等元一定是等幕元，并且在 群 中 ， 除 幺 元 即 單 位 元 e 外 不 可 能 有 任 何 別 的 冪 等 元 ）42、設(shè)a是10階群的生成元，則24是（） 階元素，23是（） 階元素答：5, 10 （若一個(gè)群G的每一個(gè)元都是 G的某一個(gè)固定元 a的乘方，我們就把G叫做循環(huán)群；我們也說(shuō)，G是由元a生成的，并且用符號(hào) G=afe示，且稱(chēng)a為一個(gè)生成元。并且一元素的階整除群的階）43、群G,*的等哥元是（），有（）個(gè)。答：?jiǎn)挝辉? （在群G,*中，除幺元即單位元e外不可能有任何別的幕 等元）44、素?cái)?shù)階群一定是（） 群，它的生成元是（）。

15、答：循環(huán)群，任一非單位元（證明如下：任一元素的階整除群的階?，F(xiàn)在群的階是素 數(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,c 6 G,則（1） 若 c a=b,貝U c=（ ）; （2） 若 c a=b a,貝U c=（）。答：（1） b a 1 （2） b（群的性質(zhì)）46、H, 是6, 的子群的充分必要條件是（）。答：H,是群 或 a , bG,a bH,a-1H 或 a,bG,ab-1H

16、47、群 A,* 的等哥元有（）個(gè)，是（），零元有（）個(gè)。答：1,單位元，048、在一個(gè)群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|答：50、任意一個(gè)具有2個(gè)或以上元的半群,它（）。不可能是群（2）不一定是群一定是群（4）是交換群答：（1）51、6階有限群的任何子群一定不是（(1) 2 階 (2) 3 階 (3) 4 階 (4) 6 階答： (3)(格與布爾代數(shù)部分)52、下列哪個(gè)偏序集構(gòu)成有界格()(1) ( N, )(2) (

17、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) 樹(shù) (3) 平面圖 (4) 連通圖答： (4) (考察圖的定義)55、下面給出的集合中，哪一個(gè)是前綴碼()(1) 0 ，10， 110， 101111(2) 01 ， 001， 000， 1(3) b ，c，aa， ab， aba(4) 1， 11， 101， 001，0011

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

19、，其結(jié)點(diǎn)度數(shù)之和是（）。答：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ú)向圖有生成樹(shù)的充分必要條件是（）。答：它是連通圖66、設(shè)G是一棵樹(shù)，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則 n=m m=n+1 （3） n=m +1 （4） 不能確定。答：（3）67、設(shè)T= 是一棵樹(shù)，若|V|1

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

21、3、 設(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、一棵樹(shù)有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、若一棵完全二元(

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

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

24、) ( P Q R) (P Q R)(P Q R) (P Q R) ( P Q R) ( P Q R)( P Q R) ( P Q R) ( 主析取范式)(P R) (Q R)P)(P Q R) (P QR) (原公式否定的主析取范式)(P R) (Q R) P ( P Q R) ( P Q R)(主合取范式)3、(F Q) (R P)解：(P- Q) (R P)(P Q) (R P)(合取范式)(P Q (R R) (P (Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R)(P Q R) (P Q R) (P Q R)(主合取范式)(P- Q) (R P)(P Q

25、R) ( P Q R) ( P Q R) ( P Q R)(P Q R)(原公式否定的主合取范式)(P- Q) (R P)( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主析取范式）4、CH (PR)解：QH (PR)Q PR (主合取范式)(QH (PR)( P Q R) ( P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P Q R) (原公式否定的主合取范式)0- (PR)(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P QR) (主析取范式)5、P (P (QK

26、 P)解：4 (P (Q-P)P (P ( Q P)PPT ( 主合取范式)(P Q) ( P Q) (P Q) (P Q)(主析取范式)6、(P-Q) (R P)解： (P-Q) (R P) ( P Q) (R P)(P Q) (R P)(析取范式)(P Q (R R) (P ( Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R)(P Q R) (P Q R) (P Q R)(主析取范式)(P-Q) (R P) (PQ R) (P QR)( PQ R)(P Q R) ( P Q R)(原公式否定的主析取范式)(P-Q) (R P) (PQR) (PQR)(P QR)

27、(P Q R) (P Q R)(主合取范式)7、P (P Q)解：P (P-Q)P (P Q)(PP)QT(主合取范式)(PQ) (P Q)(PQ)(PQ)(主析取范式)8、(RQ) P解：(R-Q) P ( R Q ) P( R P) (Q P) (析取范式)( R (Q Q) P) ( R R) Q P)( R Q P) ( R Q P) ( R Q P) (R Q P)(P Q R) (P Q R) (P Q R)(主析取范式)(R - Q) P) ( P Q R) ( P QR)(P Q R)(P Q R) ( P Q R)(原公式否定的主析取范式)(R-Q) P (P Q R) (P

28、 Q R) ( P Q R)(P Q R) (P Q R)(主合取范式)9、P Q解：Pf QP Q (主合取范式)( P (Q Q) ( P P) Q)( P Q) ( P Q) ( P Q) (P Q)(P Q) ( P Q) (P Q)(主析取范式)10、 P Q解： P Q (主合取范式)(P ( Q Q) ( P P)Q)(P Q) (P Q) ( P Q) (PQ)(P Q) (P Q) ( P Q)(主析取范式)11、 P Q解：P Q （主析取范式）(P (Q Q) (P P) Q)(PQ) (P Q) (P Q) ( P Q)(PQ) (P Q) ( P Q)(主合取范式)1

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

30、(P P) (Q Q) R)(PQR)(PQR)(PQ R)(P Q R)( P Q R)( P Q R)(PQR)(PQR)(PQ R)(P Q R)( P Q R)( 主析取范式)( P Q)R( P Q) R(P Q) R(析取范式)(P R) ( Q R)(合取范式)(P (Q Q) R) (P P) Q R)(P Q R) (P Q R) (P Q R) ( P Q R)(P Q R) (P Q R) ( P Q R)( 主合取范式)14、 (P (Q R) (P(QR)解： (P (Q R)(P (QR)( P (Q R)(P(QR)(P Q)(P R)(P Q)(P R)(合取范

31、式)( P Q (R R) ( P (Q Q) R) (P Q (R R)(P (Q Q) R)( P Q R) ( P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P Q R) (P Q R)( P Q R) ( P Q R) ( P Q R) (P Q R)(P Q R) (P QR)(主合取范式)(P (QR)(P (Q R)(PQ R)(PQ R)( 原公式否定的主合取范式)(P (Q R) ( P ( Q R)(P Q R) ( P Q R)( 主析取范式)15、 P ( P (Q ( Q R)解： P ( P (Q ( Q R)P (P (Q (Q

32、 R)P Q R（主合取范式）(P Q R)(P Q R) (P Q R) (P Q R) ( P Q R)( P Q R) ( P Q R) ( P Q R)( 原公式否定的主合取范式)(P Q R)( P Q R) ( P Q R) ( P Q R) (P Q R)(P Q R) (P Q R) (P Q R)( 主析取范式)16、 (P Q) (P R)解、 (P Q) (P R)( P Q) ( P Q (R( P Q R)( P Q R)(P Q) (P R)( P Q) (PR)( 合取范式)R)(P (QQ)(PQR)(P(PQR)(PP R)R)Q R) ( P Q R)Q R

33、)( 主合取范式)P (Q R)( 合取范式)( 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、P QQ R,R,S P= S證明：（1） R前提（2） Q R 前提(3)1） ， （ 2）P - Q前提(5) P(3)，(4)(6) S P前提(7) S(5)，(6) 證明：2、A (BC), r( D E),F7 (DE),A=BF(1) A前提(2) A-(B-C)前提(3) B -C(1),

34、 (2)(4) B附加前提(5) C( 3) ， ( 4)(6) C - ( DE)前提(7) D E ( 5) ， ( 6)(8) F-(DE)前提(9) F( 7) ， ( 8)(10) B -F CP3、P Q,P R, Q-S = R S證明：(1) R 附加前提(2) P - R 前提(3) P ( 1) ， ( 2)(4) P Q 前提(5) Q(3)，(4)(6) Q - S前提(7) S(5)，(6)(8) R S CP ， ( 1) ， ( 8)4、(P - Q) (R-S), (Q-W) (S-X), (WX), P R =P證明：(2) P-R前提(3) R( 1) ，

35、( 2)(4) (P-Q) (R-S)前提(5) P -Q(4)(6) R-S(5)(7) Q(1)，(5)(8) S(3)，(6)(9) (Q-W) (S-X) 前提9）(10) Q-W(11) S-X12) W13) X14) W X15) (W X)16) (W X) (W（ 10）（ 7） ， （ 10）（ 8） ， （ 11）（ 12） ， （ 13）前提X） （ 14） ， （ 15）S =M（ 1）（ 2）（ 3）（ 4）（ 5）（ 6）（ 7）（ 8）（ 9）6、B D，證明：QSP- (Q S)PU PUU V(U V)(MM NM(E- F)-附加前提前提（ 1） ， （

36、2）前提（ 3） ， （ 4）（ 5）N） 前提（6）,（7）（ 8）D，E= B5、(U V)(M N), U P, P7(Q S), 證明：(1) B附加前提附加前提附加前提前提（ 1） ， （ 3）（ 2） ， （ 4）前提（ 5） ， （ 6）（ 2） ， （ 7）CP， （ 2） ， （ 8）CP ， （ 1） ， （ 9）E S =S Q附加前提前提（ 1） ， （ 2）前提（ 3） ， （ 4）前提(2) B D前提(3) D( 1) ，( 2)(4) (E - F)- D 前提(5) (E- F) (3), (4)(6) E F( 5)(7) E( 6)(8) E前提(9) E

37、 E( 7) ， ( 8)7、P (QR), RH(Q-S) = P(QS)證明： 1) 1)P 2) 2)Q 3) P - (Q-R) 4) Q-R 5) 5)R 6) R-(Q-S) QfS(8) 8)S(9) Q-S(10) P -(Q-S)8、P QP- R,證明：( 1) S(2) R- S(3) 3) R(4) P- R(5) 5)P(6) P - Q(7) 7)Q（5） ， （ 6）(8) S f Q CP , (1), (7)9、P (Q-R) = (P -Q)(PR)證明：(1) P - Q 附加前提(2) P附加前提(3) Q (1),(2)(4) P - (Q-R)前提(

38、5) Q -R ,(4)(6) R (3),(5)(7) P - R CP,(2),(6)(8) (P -Q) -(P-R) CP,(1),(7)10、P-( Q R), CH P,SR,P = S證明：前提1) P2) ) P -(QrR)前提3)4)5)6)7)8)QHR (1), (2)Q - P前提Q(1)，(4)R(3),(5)S - R前提S(6)，(7)11、A, Z B, AC, B (D- C)=證明：( 1) A前提(2) A-B前提(3) 3)B(1)，(2)(4) A fC前提(5) 5)C(1)，(4)(6) B-(D- C)前提(7) D- C (3), (6)(8

39、) D (5), (7)12、2 (C B), B A,八 C = AD證明：(1) A附加前提(2) A一 (C B)前提(3) C B(1), (2)(4) B-A前提(5) B(1),(4)(6) C(3), (5)(7) D-C前提(8) D(6), (7)(9) A-DCP ,(1),(8)13、(P Q)(RQ) (PR) Q證明、(P Q) (R Q)(P Q) ( R Q)(P R) Q (PR)Q(P R) Q14、P (Q P) P (P Q)證明、P (Q P)P ( Q P)(P) ( P Q)P (P Q)15、(P Q)(PR),(Q R), S P S證明、(P

40、Q)(PR)前提(2) P (Q R) (1)(3) (Q R)前提(4) P(2),(5) SP前提(6) S,(5)16、P Q證明、(1)(2)(3)(4)(5)(6 ) R (8)Q R RPP QQQ RRSRR RS P附加前提前提(1), (2)前提(3), (4)前提(6)(5),17、用真值表法證明PQ ( P Q) (Q P)證明、列出兩個(gè)公式的真值表:PQP Q(PQ(QP)FFTTFTFFTFFFTTTT由定義可知，這兩個(gè)公式是等價(jià)的。18、 Q Pf (P Q)證明：設(shè)P一(P Q)為F,則P為T(mén), P Q為F。所以P為T(mén), Q為F ,從而P- Q也為F。所以 P一

41、Q P一 (P Q)。19、用先求主范式的方法證明（P-Q）(P-R)(P-Q R)證明：先求出左右兩個(gè)公式的主合取范式(P-Q) (P-R) (P Q) (P R)( P Q (RR)P (QQ) R)PQR)(PR)P Q R) (Q R)PQR) (PQR)P Q R)(P- (QR) )R) )它們有一樣的主合取范式，所以它們等價(jià)。(PQ) (R)P Q (RP Q R)R)(PP Q R) (20、(PQ)(Q R)證明：設(shè)(P-Q)故4 QQ和P (QQ) R)R)Q R) (Q R)P Q R)Q R)所以它們等價(jià)。(Q R)為 T,則 4Q和(QR）都為T(mén)oR都為T(mén)oR）都為T(mén)

42、,即P-Q為T(mén), Q和R都為Fo從而P也為F,即P 為T(mén)。從而(P-Q) (Q R)21、為慶祝九七香港回歸祖國(guó)，四支足球隊(duì)進(jìn)行比賽，已知情況如下，問(wè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ì)獲亞軍 ; 則前提符號(hào)化為A (B C), CA, D B, A;結(jié)論符號(hào)化為D。本題即證明A(BQ),CA, DB, A D(1) A前提A (B C)前提(3) B C (1)

43、, (2)(4) C A 前提(5) C (1), (4)(6) B(3), (5)(7) D B 前提(8) D(6), (7)22、用推理規(guī)則證明P Q, (Q R),P R不能同時(shí)為真。證明：(1) P R 前提(2) P(1)(3) P Q 前提Q(2),(3)(5) (Q R) 前提(6) Q R (5)(7) Q (6)(8) Q Q ,(7)(集合論部分)四、設(shè)A, B, C是三個(gè)集合，證明：1、A (B -C)=(A B) (A C)證明：(A B)-(A C)= (A B) A C =(A B) (A C ) =(A B A) (A B C)= A B C =A (B C )

44、 =A (B-C)2、(A-B) (A C尸A (B C)證明：(A-B)(A-C)=(A B) (A C) =A ( B C)=A B C = A-(B C)3、A B=A C, A B=A C,貝 U C=B證明：B=B ( A A)=(B A) (B A)=(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 貝U A B= (A-B)(B-A),B-A=設(shè) A B=，則 A B= (A-B)(B-A)=。故 A-B=從而AB, BA,故A=B6、A B = A

45、 C, A B=A C,貝U C=B證明：B=B (A B)= B (A C)= (B A) (B C)=(A C) (B n C)= C (A B)=C (A C)=C7、A B=A C, A B=a C,貝 U C=B證明：B=B (AA)=(B A) (B A)=(C A) (C A)=C (A A)=C8、A- (B C)=(A-B)-C證明：A- (BC)= A B C=A (B C)=(A B) C=(A-B) C =(A-B)-C9、(AB) (A C尸A (B C)證明：(A-B) (A-C)=(A B) (A C)=(A A) ( B C)=A BC =A (B C)10、A

46、-B=B,貝U A=B=證明：因?yàn)?B=A-B,所以 B=B B= (A-B)B=。從而 A=A-B=B=。11、A=(A-B) (A-C) A B C=證明：因?yàn)?A-B)(A-C) =(A B) (A C) =A ( B C)=A BC = A-(B C),且 A=(A-B)(A-C),所以人=A-(B C),故 A B C=。因?yàn)?A B C=，所以 A-(B C尸A。而 A-(B C)= (A-B)(A-C),所以 A=(A-B)(A-C)。12、(A-B)(A-C)= ABC證明：因?yàn)?A-B)(A-C) =(AB) (A C) =A ( BC)=A BC = A-(BC),且(A-

47、B)(A-C)=,所以=A-(B C),故 A B Co 因?yàn)?A B C,所以 A-(B C尸A。而 A-(B C)= (A-B)(A-C),所以 A=(A-B)(A-C)。13、(A-B)(B-A)=A B=證明：因?yàn)?A-B)(B-A尸A,所以 B-A A。但(B-A) A=,故 B-A=即B A,從而B(niǎo)= (否則A-B A,從而與(A-B)(B-A尸A矛盾)。因?yàn)锽=,所以 人6=人且B-A= 0從而(A-B)(B-A尸A。14、 (A-B)-C A-(B-C)證明：X (A-B)-C ,有 x A-B 且 x C,即 x A, x B且 x C。從而 x A, x B-C,故 x A

48、-(B-C)。從而(A-B)-C A-(B-C)15、P(A) P(B) P(A B) (P(S)表示 S 的募集)證明：S P(A) P(B),有 S P(A)或 S P(B),所以 S A或 S B。從而 S A B,故 S P(A B)o 即 P(A) P(B) P(A B)16、P(A) P(B)=P(A B) (P(S)表示 S的募集)證明：S P(A) P(B),有 S P(A)且 S P(B),所以 S A且 S B。從而 S AB,故 S P(A B)o 即 P(A) P(B) P(A B)。S P(A B),有 S A B,所以 S A且 S B。從而 S P(A)且 S P(B),故 S P(A) P(B)0 即 P(A B) P(A) P(B)。故 P(A B)=P(A) P(B)17、 ( A-B)B=( A B) -B 當(dāng)且僅當(dāng)B= 。證明：當(dāng) B= 時(shí)，因?yàn)?A-B)B=( A- )=A， ( A B) -B=( A ) -二A,所以(A-B)B= (A B) -Bo用反證法證明。假設(shè) B