1、離散數學題庫與答案、選擇或填空(數理邏輯部分)1、下列哪些公式為永真蘊含式()(1) Q=QP (2)Q=PQ P=PQ (4) P (P Q)= P答：在第三章里面有公式(1)是附加律，(4)可以由第二章的蘊含等值式求出(注 意與吸收律區別)2、下列公式中哪些是永真式()(1)( P Q)-(Q- R) (2)P -(QfQ) (3)(PQ)-P (4)P -(P Q)答：(2), (3), (4)可用蘊含等值式證明3、設有下列公式，請問哪幾個是永真蘊涵式()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、的化簡律，(3)類似附加律，(4)是假言推理，(3), (5), (6)都可 以用蘊含等值式來證明出是永真蘊含式4、公式 x(A(x) B(y, x) z C(y, z) D(x)中，自由變元是()， 約束變元是()。答：x,y, x,z(考察定義在公式x A和 x A中，稱x為指導變元，A為量詞的轄域。在 x A和x A的轄域中，x的所有出現都稱為約束出現，即稱 x 為約束變元，A中不是約束出現的其他變項則稱為自由變元。于是 A(x)、 B(y, x)和 z C(y , z)中y為自由變元，x和z為約束變元，在 D(x)中x 為自由變元)5、判斷下列語句是不是命題。若是，給出命題的真值。 (

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

4、病，則我不去學校(3)當且僅當我生病時，我才不去學校(4)若我不生病，則我一定去學校答：(1) Q P (注意只有才”和除非就”兩者都是一個形式的)(2) P Q(3) P Q(4) P Q8、設個體域為整數集，則下列公式的意義是 ()。(1) x y(x+y=0) (2) y x(x+y=0)答：(1)對任一整數x存在整數y滿足x+y=0(2)存在整數y對任一整數x滿足x+y=09、設全體域D是正整數集合，確定下列命題的真值：(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對所有的x都成立，顯然這個與 前提條件相矛盾)(2) F (同理)(3) F (同理) (4) T (對任一整數x存在整數y滿足條件y=2x很明顯是正確的)10、設謂詞P(x) : x是奇數，Q(x): x是偶數，謂詞公式x(P(x) Q(x)在哪個個體域中為真()(1)自然數 (2)實數 (3)復數 (4) (1)-(3) 均成立答：(1)(在某個體域中滿足不是奇數就是偶數，在整數域中才滿足條件，而自然數子整數的子集，當然滿足條件了)11、命題“ 2是偶數或-3是負數”的否定是()。答：2不是偶數且-3不是負數12、永真式的否定是()永真式(2)永假式(3)可滿足式(

6、4) (1)-(3) 均有可能答：(2)(這個記住就行了)13、公式(P Q) ( PQ)化簡為()，公式Q (P (P Q)可化簡為()。答：P , Q P (考查分配率和蘊含等值式知識的掌握)14、謂詞公式x(P(x) yR(y) Q(x)中量詞 x的轄域是()。答：P(x) yR(y)(一對括號就是一個轄域)15、令R(x):x是實數，Q(x):x是有理數。則命題“并非每個實數都是有理數”的符號化表示為()。答： x(R(x) Q(x)(集合論部分)16、設人=依,但,下列命題錯誤的是()。(1) a P(A) (2) a P(A) (3) a P(A) (4) a P(A) 答：(2)

7、 (a是P (A)的一個元素)17、在0 ()之間寫上正確的符號。(1) =(2)(3)(4)答：(4)(空集沒有任何元素，且是任何集合的子集)18、若集合S的基數|S|=5 ,則S的募集的基數|P(S)|=()。答：32 (2的5次方 考查募集的定義，即募集是集合 S的全體子集構成的集合)19、設 P=x(x+1) 2 4且 x R,Q=x|5 x2+16且 x R,則下列命題哪個正確() Q P (2) Q P (3) P Q (4) P=Q答：(3) (Q是集合R, P只是R中的一部分，所以P是Q的真子集)20、下列各集合中，哪幾個分別相等()。 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 (集合具有無序性、確定性和互異性)21、若A-B=，則下列哪個名論不可能正確()(1) A=(2) B= (3) A B (4) B A答：(4)(差集的定義)22、判斷下列命題哪個為真()A-B=B-A = A=B (2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一個元素屬于B,則A=B答：(1)(考查空集和差集的相關知識)23、判斷下列命題哪幾個為正確(), (2) 中, (3) (4)

9、 (5) a,b6 a,b,a,b答：(2), (4)24、判斷下列命題哪幾個正確()(1)所有空集都不相等(2) (4) 若A為非空集，則A A成立。答：(2)25、設 AA B=AH C, A A B=A A C,貝U B( )C。答:=(等于)26、判斷下列命題哪幾個正確()(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是三個集合，則下列哪幾個推理正確：(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很明顯結論不對)(二元關系部分)、一_ 一 ，一、，一228、設人=1,2,3,4,5,6 ,B=1,2,3，從 A到 B 的關系 R= x,y|x=y求(1)R (2) R -1答：(1) R=, (2) R1=,(考查二元關系的定義，R1 為 R的逆關系，即 R 1= | 6 R)29、舉出集合A上的既是等價關系又是偏序關系的一個例子。()答：A上的恒等關系30、集合A上的等價關系的三個性質是什么()答：自反性、對稱性和傳遞性31、集合A上的偏序關系的三個性質是什么()答：自反性、

11、反對稱性和傳遞性(題29, 30, 31全是考查定義)32、設 S= 1 , 2 , 3 , 4 , A上的關系區=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、設人=1, 2, 3, 4, 5, 6, R是A上的整除關系，求R=()R=,34、設人=1,2,3,4,5,6 ,B=1,2,3，從 A到 B 的關系 R= |x=2y ,求(1)R (2) R -1 。答：(1) R=, (2) R 1 =,(3635、設人=1,2,3,4,5,6 ,B=

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

13、）38、設A=3,6,9 , A上的二元運算*定義為：a*b=mina,b,則在獨異點 中，單位元是（），零元是（）；答：9， 3（半群與群部分）39、設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 （考查群的性質，即群滿足消去律）40、設a是12階群的生成元，則22是（）階元素，23是（）階元素c答： 6,441、代數系統是一個群，則G的等哥元是（）。答：單位元（由aA2=a,用歸納法可證aAn=a*aA（n-1）=a*a=a ,所以等幕元一定是幕等 元，反

14、之若aAn=a對一切N成立，則對n=2也成立，所以幕等元一定是等幕元，并且在 群 中 ， 除 幺 元 即 單 位 元 e 外 不 可 能 有 任 何 別 的 冪 等 元 ）42、設a是10階群的生成元，則24是（） 階元素，23是（） 階元素答：5, 10 （若一個群G的每一個元都是 G的某一個固定元 a的乘方，我們就把G叫做循環群；我們也說，G是由元a生成的，并且用符號 G=afe示，且稱a為一個生成元。并且一元素的階整除群的階）43、群G,*的等哥元是（），有（）個。答：單位元，1 （在群G,*中，除幺元即單位元e外不可能有任何別的幕 等元）44、素數階群一定是（） 群，它的生成元是（）。

15、答：循環群，任一非單位元（證明如下：任一元素的階整除群的階。現在群的階是素 數p,所以元素的階要么是1要么是p。G中只有一個單位元，其它元素的階都不等于1, 所以都是p。任取一個非單位元，它的階等于p,所以它生成的G的循環子群的階也是p, 從而等于整個群G所以G等于它的任一非單位元生成的循環群）45、設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（群的性質）46、H, 是6, 的子群的充分必要條件是（）。答：H,是群 或 a , bG,a bH,a-1H 或 a,bG,ab-1H

16、47、群 A,* 的等哥元有（）個，是（），零元有（）個。答：1,單位元，048、在一個群G,*中，若G中的元素a的階是k,則a1的階是（）。答：k49、在自然數集N上，下列哪種運算是可結合的（）(1) a*b=a-b(2) a*b=maxa,b(3) a*b=a+2b(4) a*b=|a-b|答：50、任意一個具有2個或以上元的半群,它（）。不可能是群（2）不一定是群一定是群（4）是交換群答：（1）51、6階有限群的任何子群一定不是（(1) 2 階 (2) 3 階 (3) 4 階 (4) 6 階答： (3)(格與布爾代數部分)52、下列哪個偏序集構成有界格()(1) ( N, )(2) (

17、Z, )(3) ( 2,3,4,6,12,| (整除關系)(4) (P(A),)答： (4) (考查冪集的定義)53、有限布爾代數的元素的個數一定等于() 。(1) 偶數 (2) 奇數 (3) 4 的倍數(4) 2 的正整數次冪答： (4)(圖論部分)54、設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， 101， 001，0011

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

19、，其結點度數之和是（）。答：2n-2 （結點度數的定義）63、下面給出的集合中，哪一個不是前綴碼（）。（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個結點的有向完全圖邊數是（），每個結點的度數是（）。答：n（n-1）,2n-265、一個無向圖有生成樹的充分必要條件是（）。答：它是連通圖66、設G是一棵樹，n,m分別表示頂點數和邊數，則 n=m m=n+1 （3） n=m +1 （4） 不能確定。答：（3）67、設T= 是一棵樹，若|V|1

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

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

22、叉)樹有2n-1 個頂點，則它()片樹葉。(1) n (2) 2n (3) n-1(4) 2答： ( 1)79、下列哪一種圖不一定是樹() 。(1) 無簡單回路的連通圖(2) 有 n 個頂點 n-1 條邊的連通圖(3) 每對頂點間都有通路的圖(4) 連通但刪去一條邊便不連通的圖答： ( 3)80、連通圖G是一棵樹當且僅當6中()。(1) 有些邊是割邊(2) 每條邊都是割邊(3) 所有邊都不是割邊(4) 圖中存在一條歐拉路徑答： ( 2)(數理邏輯部分)二、求下列各公式的主析取范式和主合取范式： 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)證明、列出兩個公式的真值表:PQP Q(PQ(QP)FFTTFTFFTFFFTTTT由定義可知，這兩個公式是等價的。18、 Q Pf (P Q)證明：設P一(P Q)為F,則P為T, P Q為F。所以P為T, Q為F ,從而P- Q也為F。所以 P一

41、Q P一 (P Q)。19、用先求主范式的方法證明（P-Q）(P-R)(P-Q R)證明：先求出左右兩個公式的主合取范式(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) )它們有一樣的主合取范式，所以它們等價。(PQ) (R)P Q (RP Q R)R)(PP Q R) (20、(PQ)(Q R)證明：設(P-Q)故4 QQ和P (QQ) R)R)Q R) (Q R)P Q R)Q R)所以它們等價。(Q R)為 T,則 4Q和(QR）都為ToR都為ToR）都為T

42、,即P-Q為T, Q和R都為Fo從而P也為F,即P 為T。從而(P-Q) (Q R)21、為慶祝九七香港回歸祖國，四支足球隊進行比賽，已知情況如下，問結論是否有效: (1)若A隊得第一，則B隊或C隊獲亞軍；(2)若C隊獲亞軍，則A隊不能獲冠軍；(3)若D隊獲亞軍，則B隊不能獲亞軍;(4)A 隊獲第一;結論 : （5） D 隊不是亞軍。證明：設A： A 隊得第一 ;B: B 隊獲亞軍 ;C: C 隊獲亞軍;D: D 隊獲亞軍 ; 則前提符號化為A (B C), CA, D B, A;結論符號化為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、用推理規則證明P Q, (Q R),P R不能同時為真。證明：(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)(集合論部分)四、設A, B, C是三個集合，證明：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設 A=B 貝U A B= (A-B)(B-A),B-A=設 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=證明：因為 B=A-B,所以 B=B B= (A-B)B=。從而 A=A-B=B=。11、A=(A-B) (A-C) A B C=證明：因為(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=。因為 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證明：因為(A-B)(A-C) =(AB) (A C) =A ( BC)=A BC = A-(BC),且(A-

47、B)(A-C)=,所以=A-(B C),故 A B Co 因為 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=證明：因為(A-B)(B-A尸A,所以 B-A A。但(B-A) A=,故 B-A=即B A,從而B= (否則A-B A,從而與(A-B)(B-A尸A矛盾)。因為B=,所以 人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 當且僅當B= 。證明：當 B= 時，因為(A-B)B=( A- )=A， ( A B) -B=( A ) -二A,所以(A-B)B= (A B) -Bo用反證法證明。假設 B