《離散數學》題庫答案

一、選挎或填空

(數理邏輯部分)

1、下列哪些公式為永真蘊含式？()

(1)-?Q=>Q-P(2)->Q=>PfQ(3)P=>P-Q(4)-1PA(PVQ)=>-IP

答：(1).(4)

2、下列公式中哪些是永真式？()

(1)(-1PAQ)-*(Q---iR)(2)Pf(Q-*Q)(3)(PAQ)-P(4)P-*(PvQ)

答：(2).(3),(4)

3、設有卜.列公式，請問哪幾種是永真蘊涵式？()

(1)P=>PAQ(2)P/\Q=>P(3)PAQ=>PVQ

⑷PA(P-Q)=>Q(5)-n(P-Q)=>P(6)-iPA(PVQ)=>iP

答：(2).(3),(4),<5),(G)

4、公式Bx((A(x)rB(y,X))A3ZC(y,z))fD(x)中，自由變元是()，約災變元是()。

答：x,y：x,z

5、判斷下列語句是不是命題。若是，給出命題的真值。()

(1)北京是中華人民共和國的首都。(2)陜西師大是一座工廠。

(3)你喜歡唱歌嗎？(4)若7+8>18,則三角形有4條邊。

(5)前進！(6)給我一杯水吧！

答：(1)是，T(2)是，F(3)不是

(4)是，T(5)不是(6)不是

6、命題“存在某些人是大學生”的否認是(),而命題“所有的人都走要死的”的否認是(

答：所有人都不是大學生，有人不會死

7、設匕我生病，Q：我去學校，則下列命題可苻號化為()o

(1)只有在生病時，我才不去學校(2)若我生病，則我不去學校

(3)當且僅當我生病時，我才不去學校(4)若我不生病，則我一定去學校

答：(1)-1QfP(2)Pf-iQ(3)P—->Q⑷-1PfQ

8、設個體域為整數集，則下列公式的意義是()。

3)Vx3y(x+y=0)(2)3yVx(x+y=0)

答：(1)對任一?整數x存在整數y滿足x+y=O(2)存在整數y對任一?整數x滿足x+y=O

9、設全體域D是正整數集合，確定下列命題的真值:

(1)Vx3y(xy=y)()(2)3xVy(x+y=y)()

(3)3xVy(x+y=x)()(4)Vx3y(y=2x)()

答：(1)F(2)F(3)F(4)T

10、設謂詞P(x)：x是奇數，Q(x)：x是偶數，謂詞公式孔(P(x)vQ(x))在哪個個體域中為真？()

(1)自然數(2)實數(3)夏數(4)(1)一(3)均成立

答：(1)

11、命題”2是偶數或-3是負數”的否認是()o

答：2不是偶數且-3不是負數。

12、永真式的否認是()

(1)永真式(2)永假式(3)可滿足式(4)(1)一(3)均有也許

答：(2)

13、公式(一?PAQ)V(―?PA―?Q)化簡為()，公式Q->(Pv(P八Q))可化簡為()?

答：，Q->P

14、謂詞公式Vx(P(x)v力R(y))fQ(x)中量詞Vx的轄域是()。

答：P(x)v3yR(y)

15、令K(x):x是實數，Q(x):x是有理數。則命題”并非每個實數都是有理數”的符號化表達為().

答：-nVx(R(x)->Q(x))

(集合論部分)

16、設A={a,{a}},下列命題錯誤的是(

⑴{a}GP(A)(2){a}CP(A)(3){{a}}GP(A)(4){{a}}CP(A)

答：⑵

17.在C()①之間寫上對的的符號.

(1)=(2)1(3)e⑷生

答：(4)

18、若集合S的基數|S|=5,則SII勺恭集H勺基數P(S)|=(

答：32

19、設「二a|?+1)244且x￡R),Q={x|5?x2+16且x￡R},則下列命題哪個對的()

(1)QUP(2)QCP(3)PUQ⑷P=Q

答：(3)

20.下歹J各集合中，哪幾種分別相等(晨

(1)Al={a,b}(2)A2={b,a)(3)A3={a,b,a}(4)A4={a,b,c}

(5)?\5={x|(x-a)(x-b)(x-c)=0}(6)A6={x|x'-(a+b)x+ab=0}

答：A1=A2=A3=A6,A4=A5

21、若A-B=6,則下列哪個結論不也許對H勺？()

(1)A=e(2)B=O>⑶AUB(4)BCA

答：(4)

22、判斷下列命題哪個為真？()

(I)A-B=B-A=>A=B(2)空集是任何集合的真子集

(3)空集只是非空集合附子集(4)若人的一種元素屬于B,則A=B

答：(1)

23、判斷下列命題哪幾種為對I向？()

⑴[①，{{中}}}⑵{①}q{①：{{6}}}⑶<l>e{{0}}

(4)中q{6}(5){a,b}G{a,b,{a},{b：}

答：(2),(4)

24、判斷下列命題哪幾種對的？()

(1)所有空集都不相等(2)(4)若A為非空集，則AUA成立。

答：(2)

25、設AnB=Anc,AnB=Anc,貝]B()C。

答：=(等于)

26、判斷下列命題哪兒種對的？()

(1)若AUB=AUC,則B=C(2){a,b}={b,a}

(3)P(AAB)NP(A)nP(B)(P(S)表達SI內吊集)

(4)若A為非空集，則A。AUA成立。

答：(2)

27、A,B,C是三個集合，則下列哪幾種推理對的：

(1)ACB,BCC=>ACC(2)ACB,BCC=>AeB(3)AeB,BGC=>AGC

答：⑴

(二元關系部分)

28.設4={1,2,3,4,5,6),B=(l,2,3),從人到已的關系R={<x,y)|x=y}求(1)R(2)Rl

答：(1)R={<1,1〉,〈4,2?(2)R-I=K1,1>,<2,4>}

29、舉出集合A上的既是等價關系又是偏序關系的一種例子。()

答：A上的恒等關系

30、集合A上的等價關系的三個性質是什么？()

答：自反性、對稱性和傳遞性

31、集合A上的偏序關系的三個性質是什么？()

答：自反性、反對稱性和傳遞性

32、設S={1,2,3,4},A上啊關系R={{1,2〉，《2,1〉，〈2,3〉,<3,4>)

求⑴RoR(2)求。

答：RoR={<1,1),〈1,3〉，〈2,2〉，〈2,4)}

R"={(2,1),(1,2),(3,2),(4,3))

33、設4={1,2,3,4,5,6},R是A上的整除關系，求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、設4={1,2,3,4,5,6},B={1,2,3},從A到Bl內關系R={<x,y>|x=2y：s求⑴R(2)Rl,

答：(1)R=f<l,1\<4,2>,<6,3>}(2)R-，=f<l,1>,<2,4>,(36>1

2

35、設八=11,2,3,4,5,6},B=(l,2t3),從A到Bl向關系R={<x,y)|x=y],求R和R”的關系矩陣。

loo

ooo

OOO100000

答：R的關系矩陣=R的關系矩陣=000100

010

000000

000

000

36、集合A={1,2,…,10}上的關系1^={＜%丫＞/+丫=10,%丫￡后,則R的性質為()。

(1)自反的(2)對稱的(3)傳遞的，對稱的(4)傳遞的

答：(2)

(代數構造部分)

37、設4={2,4,6),A上的二兀運算*定義為：a*b=max{a,b},則在獨異點＜A,*)中，單位兀是()，零兀是()?

答:2,6

38、設4={3,6,9},A上的二元運算*定義為:a*b=min{a,b},則在獨異點＜A,*＞中，單位元是（）,零元是（）;

答：9,3

（半群與群部分）

39、設（G,*）是一種群，則

（1）若a,b,xWG,a*x=b?則x=（）；

（2）若a,b,x￡G,a*x=a*b,則x=（）（.

答：（I）a-，*b（2）b

40、設a是12階群的J生成元，則求是（）階元素，@'是（）階元素。

答：6,4

41、代數系統《,*》是一種群，則G的等基元是（）,,

答：單位元

42、設a是10階群的生成元，則1是（）階元素，￡是（）階元素。

答：5,10

43、群倔*〉11勺等第元是（），有（）個。

答：單位元，1

44、素數階群一定是（）群，它的生成元是（）。

答：循環群，任一非單位元

45、設（G,*）是一種群，a,b,cGG,則

（1）若c*a=b,則c=（）：（2）若c*a=b*a,則c=（）。

答：（1）b*rz-1（2）b

46、＜H,：*〉是＜。，*〉/、J子群口勺充足必要條件是（）o

1

答：＜H＞:*＞是群或Va,bEG,a*bGH,aGH或Da,bEG,a*b'GH

47、群＜A,*＞的等幫元々（）個，是（），零元杓（）個。

答：1,單位元，0

48、在一種群〈G,*〉中，若G中的元素a時階是k,則小的階是（）.

答：k

49、在白然數集N上，下列哪種運算是可結合的？（）

（1）a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=Ia-bI

答:(2)

50、任意一種具有2個或以上元的半群，它()。

(1)不也許是群(2)不一定是群

(3)一定是群(4)是互換群

答：⑴

51、6階有限群的任何子群一定不是()。

(D2階(2)3階(3)4階(4)6階

答：⑶

(格與布爾代數部分)

52、下列哪個偏序集構成有界格()

(1)(N：<)(2)(Z,>)

(3)({2,3,4,6,12}/(整除關系))(4)(P(A),C)

答：⑷

53、有限布爾代數的元素的個數一定等于(

(1)偶數⑵奇數(3)4的倍數⑷2的正整多次事

答：(4)

(圖論部分)

54、設G是種哈密爾頓圖，則G定是().

⑴歐亞圖⑵樹⑶平面圖⑷連通圖

答：⑷

55、下而給出的集合中，哪一種是前綴碼？()

(1)(0,10,110,101111)(2){01,001,000,1)

(3){b,c,aa,ab,aba}(4){1,11,101,00L0011}

答：(2)

56、一和圖的哈密爾頓路是一條通過圖中()1向路。

答：所有結點一次且恰好一次

57、在有向圖中，結點v的出度deg.(v)表達(),入度deg(v)表達()。

答：以Y為起點的邊的條數，以v為終點的邊的條數

58、設G是一棵樹，則G的生成樹和()保。

(1)0(2)1(3)2(4)不能確定

答：1

59.n階無向完全圖K,H勺邊數是()，每個給點的度數是(晨

少〃(〃T)

答：--------,n-l

2

60、一根無向樹的頂點數n與邊數m關系是()o

答：m=n-l

61、一和圖的歐拉回路是一條通過圖中()1向回路。

答：所有邊一次且恰好一次

62、有n個結點H勺樹，其結點度數之和是()o

答:2n-2

63、下面給出的集合中，哪一種不是前綴碼()。

(1){a,ab,110,albll}(2){01,001,000,1}

(3){1,2,00,01,0210}(4){12,11,101,002,0011)

答：⑴

64、n個結點的有向完全圖邊數是(),每個結點的度數是()。

答:n(n-l),2n-2

65、一和無向圖有生成樹的充足必要條件是()。

答：它是連通圖

66、設G是一棵樹，n,m分別表達頂點數和邊數，則

(1)n=m(2)m=n+l(3)n=m+l(4)不能確定。

答:(3)

67、設1=<V,E>是一棵樹，若則T中至少存在()片樹葉。

答：2

68、仟何連通無向圖G至少有()棵生成樹，當且僅當G是(),G的牛成樹只有一棵。

答：1,樹

69、設C是有n個結點m條邊的連通平面圖，且有k個面，則k等于：

(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。

答：(1)

70、設I是一棵樹，則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

答：⑷

73、設圖G=<V,E>,V={a,b,c,d,e),片{<&b>,<a,c>,<b,c>,<c,d〉,<d,e?,則G是有向圖還是無向圖?

答：有向圖

74、任一有向圖中，度數為奇數的結點有()個。

答：偶數

75、具有6個頂點，12條邊的連通簡樸平面圖中，每個面都是由()條邊隹成？

(1)2(2)4(3)3(4)5

答:(3)

76、在有n個頂點的連通圖中，其邊數()?

(1)最多有nT條⑵至少有n-1條

(3)最多有n條(4)至少有n條

答:(2)

77、一枳樹有2個2度頂點，1個3度頂點，3個4度頂點，則其1度頂點為：)。

(1)5(2)7(3)8(4)9

答：⑷

78、若一棵完全二元(又)樹有2nT個頂點，則它()片樹葉。

(1)n(2)2n(3)n-1(4)2

答：⑴

79、下到哪一種圖不一定是樹()o

(1)無同樸回路的連通圖(2)ffn個頂點n-1條邊的連通圖

(3)每對頂點間均有通路的圖(4)連通但刪去?條邊便不連通的圖

答：(3)

80、連通圖G是一棵樹當且僅當G中()0

(1)有些邊是割邊(2)每條邊都是割邊

(3)所有邊都不是割邊(4)圖中存在一條歐拉途徑

答:(2)

(數理邏輯部分)

二、求下列各公式的主析取范式和主合取范式：

1、(P-*Q)AR

解：(P-Q)AROJPVQ)/\R

<z>(-iPAR)V(QAR)(析取范式)

<z>(-!PA(V)AR)V((-1PVP)AQAR)

<z>(-iPAQAR)V(-iPA-1QAR)V(-IPAQAR)V(PAQ,\R)

^(-IPAQARJVC-IPA^QA^VCPAQAR)(主析取范式)

-1((P-Q)AR)<=>(-IPA-1QA-IR)V(-1PAQA-IR)V(PA-IQAR)

V(PAQA-IR)V(PA—IQA—IR)(原公式否認的主析取范式)

(P—Q)AR<z>(PVQVR)A(PV—IQVR)A(—IPVQV—IR)

A(-,PVIQVR)A(-1PVQVR)(主合取范式)

2、(PAR)V(QAR)V-nP

解：(PAR)V(QAR)V-1P(析取范式)

O(P/UV-I)AR)V((PV->P)AQAR)V(->PA(V->)A(RV-1R))

?(PAQAR)V(PA-IQAR)V(PAQAR)V(-IPAQAR)

V(-1PAQAR)v(-lPAQA-iK)V(-)PA-1QAR)V(-)PAIQA-)R)

(PAQAR)V(PA-IQARJV(-IPAQAR)V(-IPAQA-IR)V(-IPA—IQAR)V(—IPA—IQA—IR)(主

析取范式)

-i((PAR)V(QAR)V-?P)

O(P八」QA-(R)v(PAQA-IR)(原公式否認的主析取范式)

(PAR)V(QAR)V->P<=>(-1PVQVR)A(-.PV-1QVR)(主合取范式)

3、(-1P-Q)A(RVP)

解：(-1P-*Q)A(RVP)

<=>(PVQ)A(RVP)(合取范式)

?(PVQV(RA-(R))A(pv(A-|))VR)

<z>(PVQVR)A(PVQV-1R)A(PVQVR)A(PV-!QVR)

<^>(PVQVR)A(PVQV—1R)A(PV->QVR)(主合取范式)

((ffQ)A(RVP))

<^>(PV-|QV—1R)A(-?PVQVR)A(-|PV—|QVR)A(—)PVQV—)R)

A(-,PV-,QV-,R)(原公式否認的主合取范式)

(「P-Q)A(RVP)

O(-1PAQAR)V(F?A-1QA-1R)V(PAQA—?R)V(PA-1QAR)V(PAQAR)

(主析取范式)

4、Q-*(PV-nR)

解：Q-(PV-iR)

<=>-.QVPV->R(主合取范式)

-n(Q-(PV-nR))

-iPV-1QV—?R)A(-1PV—?QVR)A(~iPVQV-iR)A(-1PVQVR)

A(PV-iQVR)A(PVQV-nR)A(PVQVR)(原公式否認的主合取范式)

Q-(PV-iR)

(PAQAR)v(PAQA-iR)v(PA—iQAR)v(PA-iQA-iR)v(—iPAQA-iR)

V(—iPA—iQAR)V(―iPA-iQA-iR)(主析取范式)

5、P-*(P八(Q-P))

解：P-(PA(Q-P))

<=>-iPV(PA(-iQVP))

<=>-iPVP

<=>T(主合取范式)

<=>(-?PA-iQ)V(->PAQ)V(P/X-iQ)V(PAQ)(主析取范式)

6,-I(P-Q)V(RAP)

解：-AP-Q)V(RAP)<=>-i(-iPVQ)V(RAP)

<z>(PA-)Q)v(RAP)(析取范式)

(PA-iQA(KV—>R))V(PA(—iV)AR)

<^>(PA—iQAR)V(PA-iQA-iR)V(PA—iQAR)V(PAQAR)

<=>(PA-1QAR)V(PA->QA-(R)V(PAQAR)(主析取范式1

—i(―?(P-Q)V(RAP))U>(PAQA―?R)V(—iPAQAR)V(—iP/\—iQAR)

V(—IPA—>QA-IR)V(—IPAQA-IR)(原公式否認向主析取范式)

―?(P-*0)V(RAP)(-1PV—?0VR)A(PV—10V—?R)A(PVQv―?R)

A(PVQVR)A(PViQVR)(主合取范式)

7、PV(P-Q)

解：PV(P-Q)OPV(—1PVQ)O(PV->P)VQ

<=>T(主合取范式)

<=>(-IPA-nQ)V(IPAQ)V(PA-IQ)V(PAQ)(主析取范式)

8、(RfQ)AP

解：(R-Q)AP<=>(-iRVQ)AP

<=>(-1RAP)V(QAP)(析取范式)

<=>(-1RA(V-I)AF)V((-IRVR)AQAP)

<2>(-IRAQAP)V(-1RA->QAP)V(-1RAQAP)V(RAQAP)

<z>(PAQA-nR)V(PA-IQA-1R)V(PAQAR)(主析取范式)

-1((K-Q)AP)<=>(-1PA-1QA-1R)V(-1PAQA-1R)V(PA-1QAR)V(IP/\QAR)V(「PA-1QAR)(原公式否認

的主析取范式)

(R-*Q)AP<=>(PVQVK)A(PV-iQVR)A(「PVQV-iR)

A(PV-|QV-.R)A(PVQV-.R)(主合取范式)

9、P-Q

解：PfQO-1PVQ(主合取范式)

<z>(-iPA(V->))V((-iPVP)AQ)

<=>(-I?AQ)V(-)PA-IQ)V(-iPAQ)V(PAQ)

<=>(-iPAQ)V(iPA-iQ)V(PAQ)(主析取范式)

10、PV-nQ

解：PV-.Q(主合取范式)

<=>(PA(->V))V((-)PVP)A-.Q)

O(PA-iQ)V(PAQ)V(-iPA-iQ)V(PA-iQ)

O(PA-iQ)V(PAQ)V(-iPA-iQ)(主析取范式)

11、PAQ

解：PAQ(主析取范式)<=>(PV(A-I))A((PA-)P)VQ)

<=>(PV-iQ)A(PVQ)A(PVQ)A(-iPVQ)

<=>(PViQ)A(PVQ)A(-.PVQ)(主合取范式)

12、(PVR)->Q

解：(PVR)-Q

=(PVR)VQ

OjP人-iR)VQ

<=>(-iPVQ)A(-.RVQ)(合取范式)

=(->PVQV(RArR))A((-)PAP)VQV-nR)

<=>(->PVQVR)A(-?PVQV-IE)A(-)PVQV-)R)A(PVQV-iR)

O(-iPVQVR)A(iPVQV-nE)A(iBVQViR)A(PVQV-iK)

O(-1PVQVR)A(-iPVQV-nE)A(PvQVR)(主合取范式)

-i(PVR)fQ

<=X-IPV-1QVR)A(-1PV-IQV-IR)A(PVQVR)A(PV-1QVR)A(PV-IQV-1R)(原公式否認的主析取范式)

(PVR)->Q

OCPAQA-nRjvCPAQA^VC^PA-iQA-i^VC-nPAQA-nR)

V(-iPAQAR)(主析取范式)

13、(P->Q)->R

解：(P->Q)->R

<z>-i(-iPVQ)VR

<=>(PA-iQ)VR(析取范式)

<z>(PA-iQA(RV-(R))V((PV-.P)A(V-i)AK)

<=>(PA—iQAR)V(PA—iQA—iR)V(PAQAR)V(PA—?QAR)V(—)PAQAR)

V(—?PA—?QAR)

<z>(PA-iQAR)V(PA-?QA-1R)V(PAQAR)V(-1rAQAR)

V(—iPA—?QAR)(主析取范式)

(P->Q)->R

—i(―iPVQ)VK

<z>(PA」Q)VR(析取范式)

<=>(PVR)A(「QVR)(合取范式)

O(PV(A-!)VR)A((PA-IP)V-!QVR)

<=>(PVQVR)A(PV-iQVR)A(PV-iQVR)A(-iPV-iQVR)

<z>(PVQVR)△(PV-iQVR)△(-1PV「QVR)(主合取范式)

14、(P—>(QAR))A(—iP—>(—iQA—iR))

解：(P->(QAR))A(IP->-iR))

<=>(-.Pv(QAR))A(PV(-1QA-?R))

<=>(-,PVQ)A(-,PVR)A(PV-,Q)A(PV-,R)(合取范式)

O(-1PVQV(R/\rR))八(一|PV(A-))VR)A(PV->QV(RA-)R))

A(PV(A—i)V—iR)

<=>(-1PVQVR)A(-iPVQV-IR)A(-IPVQVR)A(—)PV-iQVR)

A(PV-iQVR)A(PV-nQV-iR)A(PVQV-iR)A(PV-iQV-nR)

<=>(—>PVQVR)A(-iPVQV—1R)A(-)PV—(QVR)A(PV—iQVR)

A(PVQV-iR)A(PV-iQV「R)(主合取范式)

—?(P—>(QAR))A(—?P—>(―?QA—?R)J

0(-1PV-.QV-.R)八(PVQVR)(原公式否認的主合取范式)

(P->(QAR))A(「P->(-IQA-IR))

<=>(PAQAR)V(「PA-nQA」iO(主析取范式)

15、PV(f(QV(「QfR)))

解：PV(-iPf(QV(」QfR)))

<=>pv(PV(Qv(QvR)))

<=>PVQVRC主合取范式)

-i(PVQVR)

O(PV-iQVR)A(PV-iQV->E)A(PVQV-?R)A(-iPVQVR)

A(―iPVQV-iR)A(—iPV—?QVR)A(—iPV—iQV-iR)

(原公式否認IKJ主合取范式)

(PVQVR)

O(-nPAQ八一!R)V(-IPAQAE)V(-1PA-iQAlOx/TA-nQ八1R)

V(P△-iQ八R)V(PAQ△rR)V(P△QAR)(主析取范式)

16、(PfQ)A(P->R)

解、(PfQ)A(PfR)

<=>(-.PVQ)A(-iPVR)(合取范式)

(―IPVQV(RA-iR)A(—iPV(―iA)VR)

<=>(-1PVQVR)A(-1PVQViR)A(-iPViQVR)A(-1PVQVR)

Q(「PVQVR)人(一1PVQV-!4)人(-1PVrQVR)(主合取范式)

(PfQ)/\(PfR)

<=>(-?P\/Q)入(「PVR)

a-1PV(Q人R)(合取范式)

<=>(-1PA(V-I)A(RV-|R))V((-)PVP)AQAR)

<=>(-)PAQAR)V(-iPA-1QAR)V(-1PAQA-,R)V(-iPA-1Q-1R)

V(-iPAQAR)V(PAQAR)

O(-.PAQAR)V(->PA-iQAR)V(-iPAQA-IR)V(-IPA-1Q-1R)V(PAQAR)

(主析取范式)

三、證明：

1、P—Q,-1QVR,―iR,-nSVP^-nS

證明：

(li-iR前提

(2)->QVR前提

?3)—iQ(1),(2)

14)P~Q前提

?5)-iP⑶，(4)

(6)->SVP前提

(7)―?s(5),(6)

2、A-*(B-*C),C-*(-iDvE),-nF-*(DAiE),A=>B-*F

證明:

(I)A前提

?2)A7B-C)前提

⑶B-C(1),(2)

(4iB附加前提

i：5)C(3),(4)

?6)C-*(-.DVE)前提

i：7)-iDvE(5),(6)

?8)—iF-*(DA—IE)前提

(9)F(7),(8)

(10)BTCP

3、PVQ,P-*R,QT=>RVS

證明:

⑴-1R附加前提

⑵I」R前提

⑶-1P(1),(2)

⑷PVQ前提

⑸Q(3),(4)

(6)Q-*S前提

⑺S(5),(6)

⑻RVSCP,(1),(8)

4、(P-Q)A(RfS),(Q-*W)A(S-*X),(WAX),P-*R=>-1P

證明：

(1)P假設前提

(2)P-*R前提

(3)R⑴，(2)

(4)(P-*Q)A(R-S)前提

(5)P-Q(4)

(6)R-S(5)

(7)Q(1),(5)

(8)S(3),(6)

⑼(QfW)A(S-X)前提

(10)Q-W<9)

(11)s-*x(10)

U2)w⑺，(1C)

(13)X(8),(11)

(14)WAX(12),(13)

(15)-1(WAX)前提

(16)-1(WAX)A(WAX)(14),(15)

5、(UW)-*(MAN),UVP,P-*(QVS),-nQA-)S=>M

證明:

(1.1-1QA—?S附加前提

⑵P-(QVS)前提

(3)-1P(1),(2)

(4)UVP前提

(5)U(3),(4)

(6)UVV(5)

(7)(UVV)-*(MAN)前提

(8)MAN(6),(7)

(9)M⑻

6、一?BVD(E-*-iF)-*-iD,E=>->B

證明：

?1)B附加前提

?2)—iBVD前提

⑶D(1),(2)

⑷(E-*—iF)-*—?D前提

⑸—i(E—?—iF)(3),(4)

?6)EA-nF(5)

?7)E(6)

?8)-iE前提

?9)EA-iE(7),(3)

7、P-(Q-R),R-(Q-S)=>P-(Q-S)

證明：

(1)P附加前提

(2)Q附加前提

(3)P-(Q-R)前提

(4)Q~R(1),(3)

(5)R(2),(4)

(6)Rf(QfS)前提

(7)Q-S(5),(6)

(8)S(2),(7)

(9)Q-SCP,(2),(8)

(10)P~(QT)CP,⑴，(9)

8、P-----!Q,IP~R,K-----1s=>S----->Q

證明：

(1)S附加前提

(2)R-*―?S前提

⑶-iR(1),(2)

(4)-iP~R前提

(5)P(3),(4)

?6)P--IQ前提

(7)—iQ(5),(6)

(8)S-----iQCP,(1),(7)

9、P?(Q-R)=>(r-Q)?(P-R)

證明:

(1)P-Q附加前提

(2)P附加前提

(3)Q(1),(2)

(4)P-*(QfR)前提

(5)Q-R(2),(4)

(6)R(3),(5)

(7)P-RCP,⑵，⑹

(8)(P-Q)-YPfR)CP,(1),(7)

10、PT-nQ—iR),Q-->P,S-R,P=>-iS

證明：

(1)P前提

⑵前提

⑶-iQ-*—.R⑴，(2)

(4)Q-----iP前提

⑸—1Q⑴，(4)

⑹-iR(3),(5)

(7)S-R前提

(8)—?S⑹，⑺

11、A,A-B,A-*C?B-*(D-----iC)=>-iD

證明:

(1)A前提

(2)A-B前提

(3)B⑴，(2)

(4)A-C前提

(5)C⑴，(4)

?6)B-*(D-*—iC)前提

?7)D-----iC(3),(6)

(8)->D(5),(7)

12、A>(CVD),Ba-iA,I)?―iC=>A?-―?D

證明:

⑴A附加前提

(2)A-(CVB)前提

(3)CVB(1),(2)

(4)Bf->.A前提

(5)-nB(1),(4)

(6)C(3),(5)

(7)D--1C前提

(8)-iD(6),(7)

(9)A--1DCP,(1),(8)

13、(P->Q)A(RfQ)<=>(PVR)->Q

證明、

(P-?Q)A(RfQ)

<=>(-iPVQ)A(-iRVQ)

<z>(-iPA-iR)VQ

(PVR)VQ

<=>(PVR)fQ

14、PT(QfP)<=>「Pf(Pf-iQ)

證明，

Pf(QfP)

<=>-iPV(-iQVP)

<z>-i(-iP)V(iPV-iQ)

<=>-iP->(Pf-iQ)

15、(P->Q)A(PfR),-i(QAR),svp=>s

證明、

(1)(PfQ)A(P->R)前提

(2)P->(QAR)(1)

(3)-I(QAR)前提

(4)-iP(2),(3)

(5)SVP前提

(6)s(4),(5)

16、PT-iQ,QV「R,RA_1S=>「P

證明、

(1)P附加前提

(2)P->-iQ前提

(3)-iQ(1),(2)

(4)QV-iR前提

(5)-iR(3),(4)

(6)RA—)S前提

(7)R(6)

(8)RA-iR(5),(7)

17、用真值表法證明PCQO(PfQ)A(QfP)

證明、

列出兩個公式的真值表：

PQp—q(PfQ)A(Q->P)

FFTT

FTFF

TFFF

TTTT

山定義可知，這兩個公式是等介的。

18、P-QnP->(P/\Q)

證明、

設P-(PAQ)為F,則P為T,PAQ為F。因此P為T,Q為F,從而P-Q也為F。因此P-Q=>P-(P八Q)。

19、用先求主范式的措施證明(P-Q)A(P-R)<=>(P-*(QAR)

證明，

先求出左右兩個公式的主合取范式

(P-Q)A(P-R)<Z>(-!PVQ)A(-)PVR)

(—?PVQV(RA―?R)))/\(―?PV(A—?)VR)

(-?PvQvR)/\(-1PvQv-1R)人(-1PvQvR)/\(-1Pv-1QvR)

<=>(—iPvQv-iR)A(—iPvQvR)A(—iPv—iQvR)

(P-*(QAR))<=>(-iPv(QAR)?

<z>(-1PVQ)A(「PVR)

OC^PVQV(RA-,R))A(-iPv(A-,)VR)

O(-1PVQVR)A(-1BVQV-1R)A(->PVQVR)A(->PV-1QVK)

O(「PVQV-)R)A(「PVQVR)入([PV-iQx/R)

它們有同樣口勺主合取范式，因此它們等價。

20、(P-Q)A-I(QVR)=>-)P

證明、

設(P-*Q)△-1(QVR)為T,則P-Q和一i(QvR)都為T。即P-*Q和一iQA「R都為T。故P-*Q.~iQ和一iR)都為T,即P-*Q

為T,Q和R都為F。從而P也為F,即一iP為T。從而(P-Q)八一?(QvR)=>-iP

21.為慶祝九七吞港回歸祖國，四支足球隊進行比賽，已知狀況如下，問給論4否有效？

前提：(I)若A隊得第一，則B隊或C隊獲亞軍；

(2)若C隊獲亞軍，則A隊不能獲冠軍；

(3)若D隊獲亞軍，則B隊不能獲亞軍；

(4)A隊獲第一；

結論：(5)D隊不是亞軍。

證明、

設飛A隊得第一;B:B隊獲亞軍;C:C隊獲亞軍;D:D隊獲亞軍；則前提符號化為Af(BvC),Cf「A,Of->B,A；結論

符號化為「及

本題即i正明A—>(BVC)?C—>―?A?D—>—?B,=y>―iD。

(1)A前提

(2)Af(BVC)前提

(3)BVC(1),(2)

(4)C—>-iA前提

(5)-iC(1),(4)

(6)B(3),(5)

(7)D->-iB前提

(8)-iD(6),(7)

22、用推理規則證明P-Q,->(QVR),P八R不能同步為真。

證明、

(1)PAR前提

⑵P(1)

⑶P->Q前提

(4)Q⑵，⑶

⑸-i(QVR)前提

(6)―>QA-iR(5)

(7)->Q(6)

(8)-iA(4),(7)

(集合論部分)

四、設A,B,C是三個集合，證明：

1、AC(B-C)=(ACH)-(ACC)

證明：

(AnB)-(AAC)=(AC1B)CACC=(ACB)C(4UC)

=(ACBCA)u(AnBnC)=AHBnC=AC(BnC)

=AC(B-C)

2,(A-B)O(A-C)=A-(BnC)

證明:

(A-B)U(A-C)=(ACB)5ACC)=AC(BOC)

=ACBcC=A-(Bnc)

3、AUB=ADC,ADB=AUC,則C=B

證明：

B=BU(ACA)=(BDA)C(BUA)

=(cuA)n(cuA)=CU(A