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

一、選擇或填空

(數(shù)理邏輯部分)

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

⑴「Q=>QTP⑵[Q=>PTQ(3)P=>PTQ⑷「PA(PvQ)=>「P

答：(1),(4)

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

⑴(-1P人Q)T(QT「R)(2)PT(QTQ)⑶(PAQ)TP(4)PT(PVQ)

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

3、設(shè)有下列公式，請問哪幾個是永真蘊涵式？()

⑴P=>PAQ⑵PAQ=>P⑶PAQ=>PVQ

(4)PA(P->Q)=>Q(5)[(PTQ)=>P(6)「PA(PVQ)=>「P

答：(2),(3),(4),⑸，(6)

4、公式X/x((A(x)-B(y,x))A3ZC(y,z))-D(x)中，自由變元是(),

約束變元是()0

答：x,y,x,z

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

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

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

(5)前進(jìn)！⑹給我一杯水吧！

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

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

6、命題“存在一些人是大學(xué)生”的否認(rèn)是(),而命題“所有的人都

是要死的”的否認(rèn)是()0

答：所有人都不是大學(xué)生，有些人不會死

7、設(shè)P：我生病，Q：我去學(xué)校，則下列命題可符號化為()0

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

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

答：(1)「QfP(2)Pf「Q(3)Pc「Q(4)「PfQ

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

(1)Vx3y(x+y=O)(2)3yVx(x+y=O)

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

9、設(shè)全體域D是正整數(shù)集合，擬定下列命題的真值：

(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、設(shè)謂詞P(x)：x是奇數(shù),Q(x):x是偶數(shù)，謂詞公式3x(P(x)vQ(x))

在哪個個體域中為真？()

(1)自然數(shù)⑵實數(shù)(3)復(fù)數(shù)⑷(1)—(3)均成立

答：(1)

11、命題”2是偶數(shù)或-3是負(fù)數(shù)”的否認(rèn)是()0

答：2不是偶數(shù)且-3不是負(fù)數(shù)。

12、永真式的否認(rèn)是()

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

答：(2)

13、公式([PAQ)V(「PA「Q)化簡為()，公式Qf(Pv(P人Q))可化簡

為()。

答：「P,Q-P

14、謂詞公式Vx(P(x)vRR(y))-Q(x)中量詞Vx的轄域是()。

答：P(x)vByR(y)

15、令R(x)：x是實數(shù)，Q(x)：x是有理數(shù)。則命題“并非每個實數(shù)都是有理

數(shù)”的符號化表達(dá)為()o

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

(集合論部分)

16、設(shè)慶=匕，{a}},下列命題錯誤的是()0

(1){a}/(A)(2){a"P(A)(3){{a}}“(A)(4){{a}"P(A)

答：⑵

17、在0()①之間寫上對的的符號。

(1)=(2)o(3)e(4)生

答：(4)

18、若集合S的基數(shù)|S|=5,則S的森集的基數(shù)|P(S)|=()o

答：32

19、設(shè)P={x[&+1)2<4且)(€咫，0=儀|54*2+16且)<€田，則下歹1]命題哪個對

的()

(1)QuP(2)QcP(3)PuQ(4)P=Q

答：⑶

20、下列各集合中，哪幾個分別相等()0

(1)A1={a,b}⑵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=A6,A4=A5

21、若A-B=①，則下列哪個結(jié)論不也許對的？()

(1)A=①(2)B=0>(3)AuB(4)Bc=A

答：⑷

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

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

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

答：(1)

23、判斷下列命題哪幾個為對的？()

(1){①}￡(?，{{①}}}⑵{①"{①，{{①}}}(3)①￡{{①}}

(4)①之{①}(5){a,b}G{a,b,{a},}

答：(2),(4)

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

(1)所有空集都不相等(2)[甸力①(4)若A為非空集，則AuA成立。

答：⑵

25、設(shè)AAB=AAC,AAB=AAC,則8()C。

答：=(等于)

26、判斷下列命題哪幾個對的？()

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

(3)P(AAB)”(A)flP(B)(P(S)表達(dá)S的賽集)

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

答：⑵

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

(1)AcB,BqC=>AcC(2)AeB,B^C=>AGB(3)AeB,B￡C=>AeC

答：(1)

(二元關(guān)系部分)

28、設(shè)A={1,2,3,4,5,6},B={1,2,3},從A到B的關(guān)系R={〈x,y〉|x=y?},

求⑴R(2)R-1o

答:(1)R={<1,1>,<4,2>}(2)RT=K1,1>,<2,4>}

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

答：A上的恒等關(guān)系

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

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

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

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

32、設(shè)5={1,2,3,4},A上的關(guān)系^!={〈1,2〉，〈2,1〉，〈2,3〉，<3,4>}

求⑴R°R⑵R'1o

答：RoR={<1,1>,<1,3>,<2,2>,<2,4>}

b={〈2,1〉，<1,2>,<3,2>,<4,3>}

33、設(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〉|x=2y},

求⑴R(2)IT。

答：(1)R={<1,1>,<4,2>,<6,3>}(2)R-'={<1,1>,<2,4>,(36>J

35、設(shè)A={1,2,3,4,5,6},B={1,2,3},從A到B的關(guān)系R={〈x,y〉|x=y?},

求R和R-'的關(guān)系矩陣。

loo

ooo

oo100000'

RT的關(guān)系矩陣=000100

010

000000

000

36、集合A={1,2,…，10}上的關(guān)系R={<x,y>|x+y=10,x,yeA},則R的性質(zhì)

為（）。

（1）自反的（2）對稱的（3）傳遞的，對稱的（4）傳遞的

答：⑵

（代數(shù)結(jié)構(gòu)部分）

37、設(shè)人=[2,4,6},A上的二元運算*定義為：a*b=max{a,b},則在獨異點

<A,*>中，單位元是（）,零元是（）。

答：2,6

38、設(shè)4={3,6,9},A上的二元運算*定義為：a*b=min{a,b},則在獨異點

<A,*>中，單位元是（）,零元是（）；

答：9,3

（半群與群部分）

39、設(shè)〈G,*〉是一個群，則

（1）若a,b,x￡G,a*x-b,則x-（）;

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

答：（1）a-|*b（2）b

40、設(shè)a是12階群的生成元，則2?是（）階元素，才是（）階元素。

答：6,4

41、代數(shù)系統(tǒng)＜G,*＞是一個群，則G的等幕元是（）0

答：單位元

42、設(shè)a是10階群的生成元，則2“是（）階元素，才是（）階元素。

答：5,10

43、群4,*＞的等暴元是（），有（）個。

答：單位元，1

44、素數(shù)階群一定是（）群，它的生成元是（）0

答：循環(huán)群，任一非單位元

45、設(shè)＜G,*＞是一個群，a,b,cGG,則

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

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

46、＜比，*＞是4,，*＞的子群的充足必要條件是（）0

答：＜H,,*＞是群或Va,beG,a*beH,a'eH或Va,beG,a*b1eH

47、群VA,*＞的等森元有（）個，是（）,零元有（）個。

答：1,單位元，0

48、在一個群〈G,*〉中，若G中的元素a的階是k,則aT的階是（）。

答：k

49、在自然數(shù)集N上，下列哪種運算是可結(jié)合的？（）

（1）a*b-a-b（2）a*b-max{a,b}（3）a*b-a+2b（4）a*b-1a-b|

答：⑵

50、任意一個具有2個或以上元的半群，它（）。

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

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

答：⑴

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

(1)2階(2)3階(3)4階⑷6階

答：⑶

(格與布爾代數(shù)部分)

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

(1)(N,。(2)(Z,>)

(3)({2,3,4,6,12}"(整除關(guān)系))(zD(P(A)v)

答:(4)

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

(1)偶數(shù)(2)奇數(shù)(3)4的倍數(shù)(4)2的正整數(shù)次賽

答：(4)

(圖論部分)

54、設(shè)G是一個哈密爾頓圖，則G一定是()o

(1)歐拉圖⑵樹(3)平面圖⑷連通圖

答：(4)

55、下面給出的集合中，哪一個是前綴碼？?)

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

(3){b,c,aa,ab,aba}(4){1,11,101,001,0011}

答：⑵

56、一個圖的哈密爾頓路是一條通過圖中（）的路。

答：所有結(jié)點一次且恰好一次

57、在有向圖中，結(jié)點v的出度deg+（v）表達(dá)（），入度deg-（v）表達(dá)（）。

答：以v為起點的邊的條數(shù)，以v為終點的邊的條數(shù)

58、設(shè)G是一棵樹，則G的生成樹有（）棵。

（1）0（2）1（3）2（4）不能擬定

答：1

59、n階無向完全圖（的邊數(shù)是（），每個結(jié)點的度數(shù)是（）0

答：迎口，n-1

2

60、一棵無向樹的頂點數(shù)n與邊數(shù)m關(guān)系是（）。

答：m=n-1

61、一1個圖的歐拉回路是一1條通過圖中（）的回路。

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

62、有n個結(jié)點的樹，其結(jié)點度數(shù)之和是（）0

答：2n-2

63、下面給出的集合中，哪一個不是前綴碼（）0

（1）{a,ab,110,a1b11}（2）{01,001,000,1}

（3）{1,2,00,01,0210）（4）{12,11,101,002,0011}

答：⑴

64、n個結(jié)點的有向完全圖邊數(shù)是（）,每個結(jié)點的度數(shù)是（）0

答：n（n-1）,2n-2

65、一個無向圖有生成樹的充足必要條件是（）0

答：它是連通圖

66、設(shè)G是一棵樹，n,m分別表達(dá)頂點數(shù)和邊數(shù)，則

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

答：⑶

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

答：2

68、任何連通無向圖G至少有()棵生成樹，當(dāng)且僅當(dāng)6是(),

G的生成樹只有一棵。

答：1,樹

69>設(shè)G是有n個結(jié)點m條邊的連通平面圖，且有k個面，則k等于：

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

答：(1)

70、設(shè)T是一棵樹，則T是一個連通且()圖。

答：無簡樸回路

71、設(shè)無向圖G有16條邊且每個頂點的度數(shù)都是2,則圖G有()個頂點。

(1)10(2)4(3)8(4)16

答：(4)

72、設(shè)無向圖G有18條邊且每個頂點的度數(shù)都是3,則圖G有()個頂點。

(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>,<d,e>},

則G是有向圖還是無向圖？

答：有向圖

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

答：偶數(shù)

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

邊圍成？

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

答：(3)

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

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

⑶最多有n條⑷至少有n條

答：⑵

77、一棵樹有2個2度頂點，1個3度頂點，3個4度頂點，則其1度頂點

為()。

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

答：(4)

78、若一棵完全二元(叉)樹有2n-1個頂點，則它()片樹葉。

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

答：(1)

79、下列哪一種圖不一定是樹()0

(1)無簡樸回路的連通圖(2)有n個頂點nT條邊的連通圖

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

答：⑶

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

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

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

答：⑵

(數(shù)理邏輯部分)

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

1、(PTQ)AR

解：(PTQ)AROJPVQ)AR

<=>(-,PAR)v(QAR)(析取范式)

O(―iPA(Qv—iQ)AR)v((—,PvP)AQAR)

o(—iPAQAR)v(—iPA—iQAR)v(—iPAQAR)v(PAQAR)

<=>(-HPAQAR)v(^PA-,QAR)v(PAQAR)(主析取范式)

—i((P-*Q)AR)<^>(—>PA—>QA—IR)V(—IPAQA—>R)V(PA—>QAR)

v(PAQAIR)v(PA「QA「R)(原公式否認(rèn)的主析取范式)

(PTQ)AR<=>(PvQvR)A(Pv—iQvR)A(—>PVQV—>R)

A(-nPv^QvR)A(iPvQvR)(主合取范式)

2、(PAR)v(QAR)v-,P

解：(P人R)v(Q人R)v-1P(析取范式)

O(PA(QV—IQ)AR)v((Pv—iP)AQAR)v(—iPA(QV—,Q)A(RV—1R))

O(PAQAR)v(PA—IQAR)V(PAQAR)V(—IPAQAR)

v(-1PAQAR)v(-IPAQA-?R)v(-1PA―?QAR)v(-1PA—?QA—?R)

<=>(PAQAR)V(PA―IQAR)V(—?PAQAR)v(-IPAQA-1R)v

(」PA「QAR)v(RP/K「QA「R)(主析取范式)

」((PAR)v(QAR)V「P)

O(PA「QA「R)v(PAQA」R)(原公式否認(rèn)的主析取范式)

(PAR)v(QAR)V-,PO(「PVQVR)入(「PV「QVR)(主合取范式)

3、([PTQ)A(RVP)

解：([PTQ)A(RvP)

<=>(PvQ)A(RvP)(合取范式)

O(PvQv(RA—,R))A(Pv(QA-nQ))vR)

<=>(PvQvR)A(PvQv—?R)A(PvQvR)A(PV—,QVR)

o(PvQvR)A(PvQv「R)A(Pv「QvR)(主合取范式)

->((「PTQ)A(RvP))

<=>(Pv—,Qv—1R)A(—iPvQvR)A(—,Pv—iQvR)A(—,PVQV—,R)

A(「PV「QV「R)(原公式否認(rèn)的主合取范式)

JPTQ)A(RvP)

<=>(—]PAQAR)v(PA—,QA—,R)v(PAQA—>R)v(PA—>QAR)V(PAQAR)

(主析取范式)

4、QT(PV「R)

解：QT(Pv「R)

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

「(QT(Pv「R))

<=>(—1Pv—iQv—iR)A(—nPv—>QvR)A(—iPvQv—iR)A(—>PVQVR)

A(Pv「QvR)A(PvQv「R)A(PvQvR)(原公式否認(rèn)的主合取范式)

QT(Pv」R)

<=>(PAQAR)V(PAQA—>R)V(PA—IQAR)V(PA—IQA—iR)v(—IPAQA—iR)

v(「PA「QAR)v(「PA「Q/\「R)(主析取范式)

5、PT(PA(QTP))

解：PT(PA(QTP))

o—>Pv(PA(—,QvP))

o-.PvP

OT(主合取范式)

O(「PA「Q)v(-,PAQ)v(PA「Q)V(PAQ)(主析取范式)

6、(P->Q)v(RAP)

解：[(PTQ)v(RAP)([PvQ)v(RAP)

O(P/\[Q)V(RAP)(析取范式)

O(PA—IQA(Rv—iR))v(PA(—iQvQ)AR)

<=>(PA—nQAR)v(PA—iQA—1R)v(PA—!QAR)v(PAQAR)

O(PA「QAR)v(PA-,QA」R)V(PAQAR)(主析取范式)

—i(—i(PTQ)v(RAP))<=>(PAQA—iR)v(—iPAQAR)V(—,PA—,QAR)

v(-.PA「QA「R)v(「PAQA「R)(原公式否認(rèn)的主析取范式)

—?(PTQ)v(RAP)<=>(-1Pv—iQvR)A(Pv-)Qv—1R)A(PVQV—IR)

A(PvQvR)A(Pv^QvR)(主合取范式)

7、Pv(PTQ)

解：Pv(PTQ)oPV(「PvQ)。(PV「P)vQ

oT(主合取范式)

<=>(-,PA「Q)v(^PAQ)v(PA「Q)V(PAQ)(主析取范式)

8、(RTQ)AP

解：(R->Q)AP<=>(—>RvQ)AP

=(^RAP)v(QAP)(析取范式)

o(—iRA(Qv—iQ)AP)v((—iRvR)AQAP)

O(—iRAQAP)v(—IRA—IQAP)v(—iRAQAP)v(RAQAP)

<=>(PAQA-,R)v(PA」QA「R)V(PAQAR)(主析取范式)

—i((RTQ)AP)<=>(-,PA—IQA—iR)v(—iPAQA—iR)v(PA—>QAR)

v(-.PAQAR)V(-,PA^QAR)(原公式否認(rèn)的主析取范式)

(RTQ)APO(PvQvR)A(Pv—,QvR)A(—,PVQV—>R)

A(Pv「Qv」R)△(PvQv「R)(主合取范式)

9、PTQ

解：PTQo「PvQ(主合取范式)

O(-)PA(Qv—,Q))v((-iPvP)AQ)

(—IPAQ)v(―iPA—iQ)v(―iPAQ)V(PAQ)

^(IPAQ)V(-nPA-.Q)v(PAQ)(主析取范式)

10、Pv「Q

解：Pv「Q(主合取范式)

<=>(PA(—,QvQ))v((—,PvP)A—iQ)

O(PA「Q)v(PAQ)v(-iPA—1Q)v(PA—>Q)

(PA-,Q)v(PAQ)v(-,PA-,Q)(主析取范式)

11、PAQ

解：PAQ(主析取范式)(Pv(QA-nQ))A((PA-,P)VQ)

O(Pv—iQ)A(PvQ)A(PvQ)A(—,PvQ)

<=>(Pv^Q)A(PvQ)A(-,PvQ)(主合取范式)

12、(PvR).Q

解：(PvR)-Q

<=>—i(PvR)vQ

o(—,P人一1R)vQ

oJPvQ)入([RvQ)(合取范式)

O(—,PvQv(RA—,R))A((—,PAP)VQV—>R)

<=>(—,PvQvR)A(—iPvQv-nR)A(—iPvQv—IR)A(PVQV-nR)

O(—nPvQvR)A(—nPvQv—iR)A(—1PvQv—iR)A(PVQV—IR)

O(「PvQvR)八(「PvQv「R)A(PvQv「R)(主合取范式)

」(PvR)->Q

(-1Pv-1QvR)A(~?Pv―?Qv-1R)A(PvQvR)A(PV-iQvR)A(PV-1Qv-1R)

(原公式否認(rèn)的主析取范式)

(PvR)->Q

O(PAQA—>R)v(PAQAR)v(—iPA—>QA—,R)v(—,PAQA—>R)

v(-HPAQAR)(主析取范式)

13、(P-Q)-R

解：(P-Q)->R

O—i(—?PvQ)vR

O(PA^Q)vR(析取范式)

<=>(PA—iQA(Rv—?R))v((Pv-iP)A(Qv—?Q)AR)

O(PA—iQAR)v(PA—iQA—)R)v(PAQAR)V(PA-IQAR)V(—IPAQAR)

v(—iPA—)QAR)

<=>(PA—IQAR)v(PA-IQA-1R)v(PAQAR)v(—IPAQAR)

V(「PA「QAR)(主析取范式)

(PfQ)-R

O-i(—iPvQ)vR

O(PA「Q)vR(析取范式)

O(PvR)A(「QvR)(合取范式)

<=>(Pv(QA—?Q)vR)A((PA-iP)v—?QvR)

O(PvQvR)A(Pv—iQvR)A(Pv—>QvR)A(—IPV—IQVR)

O(PvQvR)A(Pv^QvR)A(「Pv「QvR)(主合取范式)

14、(P.(QAR))A(「P.(「Q/\]R))

解：(Pf(Q/\R))△(「P'(「Q/\]R))

oJPv(QAR))A(Pv(-iQA—iR))

O(-.PvQ)A(「PvR)A(Pv「Q)A(Pv「R)(合取范式)

o(-iPvQv(RA-iR))A(-iPv(QA—iQ)vR)A(PV—IQV(RA—?R))

A(PV(QA—)Q)V-1R)

O(—iPvQvR)A(-nPvQv-nR)A(—iPVQVR)A(—iPv—iQvR)

A(Pv—?QvR)A(Pv—?Qv?R)A(PvQv-?R)A(PV-?Qv-iR)

<=>(-1PvQvR)A(-?PvQv-?R)A(?Pv-1QvR)A(PV-■?QvR)

A(PvQv-iR)A(Pv「Qv「R)(主合取范式)

「(Pf(QAR))人(「Pf(「Q八」R))

o(「Pv「Qv「R)A(PvQvR)(原公式否認(rèn)的主合取范式)

(P->(QAR))A(「Pf(「QA「R))

O(PAQAR)v(-,PA-,QA「R)(主析取范式)

15、Pv(「P->(Qv(1Q-R)))

解：Pv(「Pf(Qv(「Q-R)))

OPv(Pv(Qv(QvR)))

=PvQvR(主合取范式)

—i(PvQvR)

<=>(Pv—)QvR)A(Pv—?Qv—iR)A(PvQv—IR)A(—,PVQVR)

A(—iPvQv—,R)A(—iPv—iQvR)A(—,Pv—,Qv—1R)

(原公式否認(rèn)的主合取范式)

(PvQvR)

<=>(—]PAQA—iR)v(—>PAQAR)V(—IPA—IQAR)V(PA-1QA-IR)

v(PA「QAR)V(PAQA「R)V(PAQAR)(主析取范式)

16、(P.Q)A(P-R)

解、(P—Q)A(P-R)

O([PvQ)A(「PvR)(合取范式)

<=>(—>PvQv(RA—>R)A(-1Pv(-!QAQ)vR)

<=>(—iPvQvR)A"PvQv-iR)A(—iPv-nQvR)A(-nPvQvR)

o(「PvQvR)A(「PvQv「R)△(「Pv「QvR)(主合取范式)

(PfQ)A(P-R)

o(—iPvQ)A(—,PvR)

(QAR)(合取范式)

O(—IPA(Qv—iQ)A(Rv—iR))v((—iPvP)AQAR)

(―iPAQAR)V(―iPA—iQAR)V(—iPAQA―iR)V(—iPA―iQ―iR)

v(—iPAQAR)v(PAQAR)

(―iPAQAR)V(-iPA-iQAR)V(-iPAQA-iR)v(—iPA—iQ-iv(PAQAR)

（主析取范式）

三、證明*

1、PTQ,―?QvR,―?R,—,SvP->—)S

證明：

(1)「R前提

(2)―?QvR前提

(3)「Q⑴，（2）

(4)PTQ前提

(5)「P(3),(4)

(6)-nSvP前提

(7)「S(5),(6)

2、AT（BTC),CT(「DvE),「FT(D.E),A=>BTF

證明：

(1)A前提

(2)AT(BTC)前提

(3)BTC(1),(2)

(4)B附加前提

(5)C⑶，（4）

(6)CT(—iDvE）前提

(7)-,DvE(5),(6)

(8)「FT(DA[E）前提

(9)F(7),(8)

(10)BTFCP

3、PvQ,PTR,Q->S=>RvS

證明：

(1)「R附加前提

(2)PTR前提

(3)「P(1),(2)

(4)PvQ前提

(5)Q(3),(4)

(6)QTS前提

(7)S(5),(6)

(8)RvSCP,(1),(8)

4、(PTQ)A(RTS)，，(QTW)A(STX),(WAX),PTR=>「P

證明：

(1)p假設(shè)前提

(2)PTR前提

(3)R(1),(2)

(4)(PTQ)A(RTS)前提

(5)PTQ(4)

(6)RTS(5)

(7)Q(1),(5)

(8)S(3),(6)

(9)(QTW)A(STX)前提

(10)QTW(9)

(11)STX(10)

(12)w(7),(10)

(13)X(8),(11)

(14)WAX(12),(13)

(15)(WAX)前提

(16)「(WAX)A(WAX)(14),(15)

5、(UvV)->(MAN),UVP,PT(QVS),「Q八「s=>M

證明：

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

(2)PT(QvS)前提

(3)「P(1),(2)

(4)UvP前提

(5)U⑶，（4）

(6)UvV(5)

(7)(UvV)T(MAN)前提

(8)MAN(6),(7)

(9)M(8)

6、—.BvD,(ET「F)T「D,「E=＞「B

證明：

(1)B附加前提

(2)—iBvD前提

(3)D(1),(2)

(4)(E-」F)f「D前提

(5)「（E-」F）(3),(4)

(6)EA「F(5)

(7)E(6)

(8)「E前提

(9)EA—IE(7),(8)

7、PT(QTR),RT(QTS)=>PT(QTS)

證明:

(1)p附加前提

(2)Q附加前提

(3)PT(QTR)前提

(4)QTR(1),(3)

(5)R(2),(4)

(6)RT(QTS)前提

(7)QTS(5),(6)

(8)S(2),(7)

(9)QTSCP,(2),(8)

(10)PT(QTS)CP,(1),(9)

8、PT「Q,「PTR,R-?->S=>ST->Q

證明：

(1)S附加前提

(2)RT「S前提

(3)(1),(2)

(4)「PTR前提

(5)P(3),(4)

(6)PT「Q前提

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

(8)ST「QCP,(1),(7)

9、PT(QTR)=>(PTQ)T(PTR)

證明:

(1)PTQ附加前提

⑵P附加前提

⑶Q(1),(2)

(4)PT(QTR)前提

(5)QTR(2),(4)

(6)R(3),(5)

(7)PTRCP,(2),(6)

(8)(PTQ)T(PTR)CP,(1),(7)

10、PT(「QT「R),QT「P,STR,P=＞「S

證明:

(1)P前提

(2)PT"QT「R）前提

(3)—iQT—iR(1),(2)

(4)QT「P前提

(5)「Q(1),(4)

(6)「R(3),(5)

(7)STR前提

(8)(6),(7)

11、A,ATB,A-?C,BT(DT「C)=＞「D

證明:

(1)A前提

(2)ATB前提

(3)B(1),(2)

(4)ATC前提

(5)C(1),(4)

(6)BT(DT「C)前提

(7)DT「C(3),(6)

(8)「2(5),(7)

12、AT(CvB),BT「A,DT「C=＞AT「D

證明:

(1)A附加前提

(2)AT(CvB)前提

(3)CvB(1),(2)

前提

(4)BT-1A

(5)「B(1),(4)

(6)C(3),(5)

(7)DT「C前提

(8)「D(6),(7)

(9)AT「DCP,(1),(8)

13、(P-Q)A(R-Q)o(PvR)—>Q

證明、

(PfQ)A(RfQ)

<=>(-1PvQ)A(—?RvQ)

(—iPA—iR)vQ

o->(PvR)vQ

<=>(PvR)-Q

14、P->(Q-P)=-,P->(P.1Q)

證明、

P-?(QfP)

<=>—iPv(—iQvP)

——?(—iP)v(—>Pv—iQ)

~?P->(P->-1Q)

15、(P.Q)A(P.R),(QAR),SvP=>S

證明、

(1)(P-Q)A(P-R)前提

(2)P-?(QAR)⑴

(3)」(QAR)前提

(4)「P(2),(3)

(5)SvP前提

(6)S(4),(5)

16、P-「Q,Qv—?R,RA-1S>=>

證明、

(1)P附加前提

(2)P->前提

(3)Q(1),(2)

(4)Qv-1R前提

(5)"?R(3),(4)

(6)RA-iS前提

(7)R(6)

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

17、用真值表法證明PcQO(PFQ)A(Q-P)

證明、

列出兩個公式的真值表：

PQPcQ(PfQ)A(QfP)

FFTT

FTFF

TFFF

TTTT

由定義可知，這兩個公式是等價的。

18、PTQnPT(P八Q)

證明、

設(shè)PT(PAQ)為F,則P為T,PAQ為Fo所以P為T,Q為F,從而P—Q也為F。

所以PTQnPT(PAQ)O

19、用先求主范式的方法證明(PTQ)A(PTR)=(PT(QAR)

證明、

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

(PTQ)A(PTR)oJPvQ)A(「PvR)

<=>(—iPvQv(RA—iR)))A(—?Pv(QA—iQ)vR)

O(—iPvQvR)A(—iPvQv—iR)A(—iPv0vR)A(—?PV—,QVR)

O(—,PvQv—>R)A(—iPvQvR)A(—iPv—iQvR)

(PT(QAR))oJPv(QAR))

<=>(—iPvQ)A(—>PvR)

O(—iPvQv(RA—iR))A(—iPv(QA—>Q)vR)

(-1PvQvR)A(―?PvQv―?R)A(―?PvQvR)A(―?Pv—iQvR)

O(—iPvQv—iR)A(—iPvQvR)A(—iPv—iQvR)

它們有同樣的主合取范式，所以它們等價。

20、(PTQ)/x「(QvR)

證明、

設(shè)(PTQ)八「(QvR)為T,則PTQ和「(QvR)都為T。即PTQ和」Q/\「R都為T。

故PTQ,「Q和「R)都為T,即PTQ為T,Q和R都為F。從而P也為F,即「P為T。

從而(PTQ)A-1(QvR)

21、為慶祝九七杳港回歸祖國，四支足球隊進(jìn)行比賽，已知情況如下，問

結(jié)論是否有效？

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

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

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

(4)A隊獲第一；

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

證明、

設(shè)A:A隊得第一；B:B隊獲亞軍；C:C隊獲亞軍；D:D隊獲亞軍；則前提符號化為

Af(BvC),Cf「A,D-「B,A;結(jié)論符號化為「D。

本題即證明Af(BvC),C-＞「A,Df「B,A=＞「D。

(1)A前提

(2)Af(BvC)前提

(3)BvC(1),⑵

(4)C—＞—?A前"提

(5)-iC(1),⑷

(6)B(3),(5)

(7)Df「B前提

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

22、用推理規(guī)則證明PfQ,「(QVR),PAR不能同時為真。

證明、

(1)PAR前提

(2)P(1)

(3)PfQ前提

(4)Q(2),(3)

(5)」(QvR)前提

(6)-?QA-1R(5)

(7)「Q(6)

(8)-nQAQ(4),(7)

(集合論部分)

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

1、Ac(B-C)=(AnB)-(AnC)

證明：

(AcB)—(AcC)=(AnB)cAcC=(AcB)c(AuC)

=(AnBnA)u(AnBnC)=AnBnC=Ac(BeC)

=Ac(B-C)

2、(A-B)u(A—C)-A—(BnC)

證明：

(A-B)u(A-C)=(Ac后)u(Ac3)=Ac(BuC)

=AcBcC=A-(BnC)

3、AuB=AuC,AUC,則C=B

證明：

B=Bu(AcA)=(BuA)c(BuA)

=(CuA)c(CuA)=Cu(AcA)=C

4、AuB=Au(B-A)

證明：

Au(B-A)=Au(BeA)=(AuB)n(AuA)

=(AuB)cU=AuB

5、A=B6A?B=o

證明：

=設(shè)人=8,貝i)A十B=(A-B)o(B-A)=(Du①=①。

u設(shè)A十B=<!>,則AaB=(A-B)u(B-A)=①。故A-B=d>,B-A=O>,

從而AqB,BqA,故A-Bo

6、AnB=AcC,AuB=AuC,則C=B

證明:

B=Bc(AuB)=Be(AuC)=(BcA)u(BcC)

二(AnC)u(BAC)=Cc(AuB)

=Cc(AuC)

二C

7、AcB二AcC,AnB=7nC,則C=B

證明：

B=Bc(AoA)=(BcA)u(BeA)