2021年度山東大學(xué)離散數(shù)學(xué)題庫(kù)及答案

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

一、選取或填空

(數(shù)理邏輯某些)

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

(1)->Q=>Q-P(2)->Q=〉P-Q(3)P=>P-Q(4)->PA(PVQ)=>-,P

答；(1),(4)

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

(1)(-1PAQ)-(Q--iR)(2)P~(Q-Q)(3)(PAQ)-P(4)P-(PVQ)

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

3、設(shè)有下列公式，請(qǐng)問哪幾種是永真蘊(yùn)涵式？()

(1)P=>PAQ(2)PAQ=>P(3)PAQ=>PVQ

(4)PA(PfQ)=>Q(5)-i(P-Q)=>P(6)-1PA(PVQ)=>「P

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

4、公式Vx((A(x)->B(y,X))A3ZC(y,z))->D(x)中，自由變?cè)?),約束變?cè)?

答：X,y,x,7.

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

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

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

⑸邁進(jìn)！(6)給我一杯水吧！

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

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

6、命題“存在某些人是大學(xué)生”否定是()，而命題“所有人都是要死”否定是()。

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

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

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

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

答：(1)-iQtP(2)P->->Q(3)Pc-iQ(4)hQ

8、設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式意義是()。

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

答：(1)對(duì)任一整數(shù)x存在整數(shù)y滿足x+y=O(2)存在整數(shù)y對(duì)任一整數(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)()

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

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

(1)自然數(shù)⑵實(shí)數(shù)⑶復(fù)數(shù)⑷⑴一⑶均成立

答：⑴

11、命題“2是偶數(shù)或-3是負(fù)數(shù)”否定是()。

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

12、永真式否定是()

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

答：(2)

13、公式(-1PAQ)V(-lPA[Q)化簡(jiǎn)為()，公式Qf(PV(P/\Q))可化簡(jiǎn)為(

答：一1P,QfP

14、謂詞公式Vx(P(x)v力“丫))一?(}3中量詞網(wǎng)轄域是()?

答：P(x)v3yR(y)

15、令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則命題“并非每個(gè)實(shí)數(shù)都是有理數(shù)”符號(hào)化表達(dá)為()?

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

(集合論某些)

16、設(shè)人={a,{a}},下列命題錯(cuò)誤是(

(1){a}6P(A)(2){a}CP(A)(3)({a}}GP(A)(4){(allCP(A)

答：⑵

17、在0()①之間寫上對(duì)的符號(hào)。

(1)=(2)[(3)€(4)0

答：(4)

18、若集合S基數(shù)|S|=5,則S嘉集基數(shù)|P(S)|=()?

答：32

19、設(shè)P={x|(x+l)244且x€R},Q={x|5Wx2+16且xCR},則下列命題哪個(gè)對(duì)的()

(1)QUP(2)QqP(3)PUQ(4)P=Q

答：⑶

20、下列各集合中，哪幾種分別相等()<.

(1)Al={a,b}(2)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=8,則下列哪個(gè)結(jié)論不也許對(duì)的？()

(1)A=6(2)B=0(3)ACB(4)BUA

答；(4)

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

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

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

答：(1)

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

⑴{8}e{Q,{{中}}}⑵{⑺口仲，{{中}}}⑶中門{中}}

(4)中q{中}(5){a,b}e(a,b,(a),1

答：(2),(4)

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

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

答：(2)

25、設(shè)AAB=Anc,AnB=Anc,則雙)c。

答：=(等于)

26、判斷下列命題哪幾種對(duì)的？()

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

(3)P(ACIB)HP(A)CP(B)(P(S)表達(dá)S募集)

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

答：(2)

27、A,B,C是三個(gè)集合，則下列哪幾種推理對(duì)的：

(1)ACB,B[C=〉A(chǔ)CC(2)A[B,BcC=>AGB(3)AGB,B￡C=>AGC

答：⑴

(二元關(guān)系某些)

28、設(shè)人={1,2,3,4,5,6},B={1,2,3),從A到B關(guān)系R={(x,y)|x=y2),求⑴R(2)R1?

答：(1)R={<1,1>,<4,2>}(2)R-1={<1,1>,<2,4>}

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

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

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

答：自反性、對(duì)稱性和傳遞性

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

答：自反性、反對(duì)稱性和傳遞性

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

求⑴RoR(2)R11,

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

R-'={〈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)R1.

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

35、設(shè)人={1,2,3,4,5,6),B={1,2,3),從A到B關(guān)系R={<x,y>|x=y2},求R和R」關(guān)系矩陣。

100

000

100000

000

答：R關(guān)系矩陣=R-I關(guān)系矩陣=000100

010

000000

000

000

36、集合A={1,2,…，10}上關(guān)系R={〈x,y＞|x+y=10,x,yGA},則R性質(zhì)為（）.

（1）自反⑵對(duì)稱（3）傳遞，對(duì)稱（4）傳遞

答:（2）

（代數(shù)構(gòu)造某些）

37、設(shè)人={2,4,6},A上二元運(yùn)算*定義為：a*b=max{a,b},則在獨(dú)異點(diǎn)＜A,*＞中，單位元是（）,零元是（）?

答：2,6

38、設(shè)人={3,6,9},A上二元運(yùn)算*定義為：a*b=min{a,b},則在獨(dú)異點(diǎn)＜A,*＞中，單位元是（），零元是（）；

答：9.3

（半群與群某些）

39、設(shè)＜G,*＞是一種群，則

（1）若a,b,x^G,a*x=b,則x=（）；

（2）若a,b,xGG,a*x=a*b,則x=（）?

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

40、設(shè)a是12階群生成元，則￡是（）階元素，2：'是（）階元素。

答：6,4

41、代數(shù)系統(tǒng)＜G,*＞是一種群，則G等哥元是（）。

答：?jiǎn)挝辉?/p>

42、設(shè)a是10階群生成元，則/是（）階元素，1是（）階元素。

答：5,10

43、群＜G,*＞等嘉元是（），有（）個(gè)。

答：?jiǎn)挝辉?

44、素?cái)?shù)階群一定是（）群，它生成元是（）。

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

45、設(shè)〈G,*〉是一種群，a,b,cEG,則

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

答：（1）b*a~'（2）b

46、〈H,,*＞是0,,*＞子群充分必要條件是（）。

答：〈H,,*＞是群或Va,bEG,a*b€H,a'GH或Va,bCG,a*b'eH

47、群＜A,*＞等某元有（）個(gè)，是（）,零元有（）個(gè)。

答：1,單位元，0

48、在一種群(G,*〉中，若G中元素a階是k,則a’階是()。

答：k

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

(1)a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=|a-b|

答：⑵

50、任意種具備2個(gè)或以上元半群,它()。

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

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

答：(1)

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

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

答：⑶

(格與布爾代數(shù)某些)

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

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

(3)({2,3,4,6,12},|(整除關(guān)系))(4)(P(A),C)

答：(4)

53、有限布爾代數(shù)元素個(gè)數(shù)一定等于().

(1)偶數(shù)(2)奇數(shù)(3)4倍數(shù)(4)2正整多次暴

答：(4)

(圖論某些)

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

⑴歐拉圖(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}

答：(2)

56、一種圖哈密爾頓路是一條通過圖中()路。

答：所有結(jié)點(diǎn)一次且正好一次

57、在有向圖中，結(jié)點(diǎn)v出度deg.(v)表達(dá)()，入度deg-(v)表達(dá)()。

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

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

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

答；1

59、n階無向完全圖K“邊數(shù)是(),每個(gè)結(jié)點(diǎn)度數(shù)是()。

會(huì)〃(〃T),

答：-------->n-l

2

60、一棵無向樹頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是()?

答：m=n-l

61、一種圖歐拉回路是一條通過圖中()回路。

答：所有邊?次且正好一次

62、有n個(gè)結(jié)點(diǎn)樹，其結(jié)點(diǎn)度數(shù)之和是()。

答：2n~2

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

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

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

答：⑴

64、n個(gè)結(jié)點(diǎn)有向完全圖邊數(shù)是(),每個(gè)結(jié)點(diǎn)度數(shù)是()。

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

65、一種無向圖有生成樹充分必要條件是()?

答：它是連通圖

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

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

答：⑶

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

答：2

68、任何連通無向圖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是一種連通且()圖。

答：無簡(jiǎn)樸回路

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

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

答：(4)

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

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

答：(4)

73、設(shè)圖設(shè)<V,E>,V={a,b,c,d,e},E={〈a,b>,<a,c>,<b,c〉,<c,d>,<d,e>},則G是有向圖還是無向圖？

答：有向圖

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

答：⑶

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

答：⑷

78、若一棵完全二元(叉)樹有2nT個(gè)頂點(diǎn)，則它()片樹葉。

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

答：(1)

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

(D無簡(jiǎn)樸回路連通圖(2)有n個(gè)頂點(diǎn)nT條邊連通圖

(3)每對(duì)頂點(diǎn)間均有通路圖(4)連通但刪去一條邊便不連通圖

答：⑶

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

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

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

答：(2)

(數(shù)理邏輯某些)

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

1、(P-Q)AR

解：(P-Q)AROJPVQ)AR

<=>(1PAR)V(QAR)(析取范式)

<^>(-1PA(QV-iQ)AR)V((—iPVP)AQAR)

(_1PAQAR)V(~iPA-1QAR)V(-1PAQAR)V(PAQAR)

<=>(-)PAQAR)V(-1PA-iQAR)V(PAQAR)(主析取范式)

—I((P->Q)AR)(―iPA-iQA—iR)V(―iPAQA-iR)V(PA-iQAR)

V(PAQA-IR)V(PA-1QA-iR)(原公式否定主析取范式)

(P~Q)ARO(PVQVR)A(PV—|QVR)A(—iPVQV—|R)

A(->PV-iQVR)A(-.PVQVR)(主合取范式)

2、(PAR)V(QAR)V->P

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

(PA(QV—?Q)AR)V((PV-iP)AQAR)V(—?PA(QV—?Q)A(RV—?R))

<=>(PAQAR)V(PA-!QAR)V(PAQAR)V(-iPAQAR)

V(-IPAQAR)V(-IPAQA-IR)V(-IPA—IQAR)V(-IPA—IQA—IR)

^(PAQARjvCPA-iQA^vC-iPAQARjvC-iPAQA-iR)V(-iPA-1QAR)V(-iPA-1QA-iR)(主

析取范式)

-1((PAR)V(QAR)V-nP)

0(PA-IQA-IIOVIPAQA^R)(原公式否定主析取范式)

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

3、(一>PfQ)A(RVP)

解：(一>P-Q)人(RVP)

O(PVQ)△(RVP)(合取范式)

<=>(PVQV(RA-iR))A(PV(QA-nQ))VR)

<=>(PVQVR)A(PVQV->R)A(PVQVR)A(PV-iQVR)

<=>(PVQVR)A(PVQV-.R)A(PV-nQVR)(主合取范式)

-1((-|P~Q)A(RVP))

(PV—iQV—?R)A(—?PVQVR)A(—?PV—?QVR)A(―?PVQV—?R)

A(-iPV->QV-iR)(原公式否定主合取范式)

(-1P-Q)A(RVP)

<=>(->PAQAR)V(PA-1QA->R)V(PAQA-iR)V(PA-1QAR)V(PAQAR)

(主析取范式)

4、Q-*(PV->R)

解：Q~(PV―?R)

O->QVPV-iR(主合取范式)

-1(Qf(PV-?R))

<=>(-tPV-1QV-iR)A(-iPV-iQVR)A(-iPVQV->R)A(-1PVQVR)

A(PV->QVR)A(PVQV-IR)A(PVQVR)(原公式否定主合取范式)

Q-(PV「R)

(PAQAR)V(PAQA-1R)v(PA-?QAR)V(PA-?QA-1R)V(-IPAQA-1R)

v(-1PA->QAR)V(—IPA—iQA—iR)(主析取范式)

5、P-(PA(Q-P))

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

<=>-IPV(PA(—1QVP))

<=>-nPVP

OT(主合取范式)

O(―IPA—iQ)V(-IPAQ)V(PA―iQ)V(PAQ)(主析取范式)

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

解：-1(P-Q)V(RAP)O-1(-1PVQ)V(RAP)

<=>(PAQ)V(RAP)(析取范式)

O(P八->QA(RV->R))V(PA(->QVQ)AR)

(PA-1QAR)V(PA-1QA-iR)V(PA-1QAR)V(PAQAR)

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

―I(—?(P-*Q)V(RAP))<=>(PAQA-iR)V(―iPAQAR)V(―iPA-iQAR)

V(->PA-IQA-IR)V(-IPAQA-1R)(原公式否定主析取范式)

一?(P-Q)V(RAP)爛)(—?PV—?QVR)A(PV—?QV—?R)A(PVQV-iR)

A(PVQVR)A(PV->QVR)(主合取范式)

7、PV(PfQ)

解：PV(P-Q)OPV(-.PVQ)O(PV-,P)vQ

OT(主合取范式)

<=>(-iPA-IQ)V(->PAQ)V(PA->Q)V(PAQ)(主析取范式)

8、(RfQ)AP

解：(R-Q)APO(->RVQ)AP

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

=(-IRA(QV-1Q)AP)V((-1RVR)AQAP)

(-1RAQAP)V(-1RA-IQAP)V(-1RAQAP)V(RAQAP)

U>(PAQA->R)v(PA-IQA->R)V(PAQAR)(主析取范式)

-1((R-*Q)AP)(—iPA—iQA-iR)V(—iPAQA-iR)V(PA-iQAR)V(—iPAQAR)V(—iPA—iQAR)(原公式否定

主析取范式)

(RfQ)APO(PVQVR)A(PV->QVR)A(-1PVQV-1R)

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

9、PfQ

解：P-QO-.PVQ(主合取范式)

<^>(―1P/\(QV―?Q))V((―?PVP)AQ)

—>PAQ)V(-1PA-1Q)V(-1PAQ)V(PAQ)

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

10、PV-.Q

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

<=>(PA(-1QVQ))V((—>PVP)A—|Q)

O(PA->Q)V(PAQ)V(-nPA-nQ)V(PA-iQ)

<=>(PA-IQ)v(PAQ)v(—iPA—?Q)(主析取范式)

11、PAQ

解：PAQ(主析取范式)<:>(PV(QA->Q))A((PA->p)VQ)

O(PV—iQ)A(PVQ)A(PVQ)A(-nPVQ)

<=>(PV->Q)A(PVQ)A(-iPVQ)(主合取范式)

12、(PVR)fQ

解：(PVR)->Q

<^>-i(PVR)VQ

<=>(-iPA-iR)VQ

O(-iPVQ)A(-iRVQ)(合取范式)

(—?PVQV(RA-iR))A((―iPAP)VQV-iR)

<=>(—iPVQVR)A(—iPVQV—)R)A(—)PVQV—.R)A(PVQV—?R)

O(-IPVQVR)A(-.PVQV-IR)A(-IPVQV-IR)A(PVQV-IR)

<Z>(-1PVQVR)A(-1PVQV-?R)A(PVQV-IR)(主合取范式)

-i(PVR)->Q

(-1PV-iQVR)A("?PV―?QV—?R)A(PVQVR)A(PV-iQVR)A(PV―iQV—iR)(原公式否定主析取范式)

(PVR)-Q

<^>(PAQA-iR)V(PAQAR)V(-iPA->QA-iR)V(-iPAQA-iR)

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

13、(P-?Q)fR

解：(PfQ)fR

<=>—)(-1PVQ)VR

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

O(PA-.QA(RV-1R))V((PV-1P)A(QV-iQ)AR)

O(PR)V(PA-IQAIICPAQAICP/KIQAQVJPAQAR)

V(—?PA-iQAR)

(PA―iQAR)V(PA―?QA—?R)V(PAQAR)V(—iPAQAR)

V(-1PA「Q/\R)(主析取范式)

(P->Q)->R

?-i(~~iPVQ)VR

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

<=>(PVR)A(-iQVR)(合取范式)

(PV(QA-iQ)VR)A((PA―iP)V—iQVR)

O(PVQVR)A(PV—?QVR)A(PV—iQvR)A(—iPV—iQVR)

O(PVQVR)A(PV-nQVR)A(-iPV「QVR)(主合取范式)

14、(P-(QAR))A(―?P—>(―?QA―?R))

解：(Pf(QAR))A(-iP-(-)QA-iR))

<^>(-1PV(QAR))A(PV(-iQA―iR))

<=>(-?PVQ)A(「PVR)A(PViQ)A(PV-|R)(合取范式)

(-iPVQV(RA-.R))A(-iPV(QA->Q)VR)A(PV->QV(RA-iR))

A(PV(QA―iQ)V—?R)

<^>(-iPVQVR)A(-1PVQV-1R)A(-iPVQVR)A(-1PV-iQVR)

A(PV-1QVR)A(PV-IQV-IR)A(PVQV-IR)A(PV-IQV-IR)

<=>(-IPVQVR)A(-IPVQV-IR)A(-IPV-1QVR)A(PV-IQVR)

A(PVQV-iR)A(PV->QV->R)(主合取范式)

—i(P->(QAR))A(―?P―>(―?QA—?R))

O(-1PV-1QV-,R)A(PVQVR)(原公式否定主合取范式)

(P->(QAR))A(-1P->(-1QA-?R))

O(P/\QAR)V(-1PA->QA->R)(主析取范式)

15、PV(-1Pf(QV(->Q-R)))

解：PV(―iP—>(QV(―?Q—>R)))

<=>PV(PV(QV(QVR)))

OPVQVR(主合取范式)

—i(PVQVR)

(PV―?QVR)A(PV-iQV-iR)A(PVQV-iR)A(―iPVQVR)

A(-1PVQV-1R)A(-1PV-1QVR)A(-1PV-1QV-1R)

(原公式否定主合取范式)

(PVQVR)

(-1PAQA-iR)V(-1PAQAR)V(-1PA-1QAR)V(PA-1QA-1R)

V(PA—>QAR)V(PAQA—>R)V(P/\Q/\R)(主析取范式)

16、(P-Q)A(PfR)

解、(PfQ)A(P-?R)

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

(-iPVQV(RA-iR)A(—iPV(―iQAQ)VR)

?>(->PVQVR)A(-1PVQV-tR)A(-1PV-1QVR)A(-1PVQVR)

O(->PVQVR)A(-1PVQV-,R)A(->PV->QVR)(主合取范式)

(PfQ)A(HR)

O(-1PVQ)A(-.PVR)

O->PV(Q/\R)(合取范式)

<=>(-IPA(QV-1Q)A(RV->R))V((-IPVP)AQAR)

S—(—iPAQAR)V(-1PA-1QAR)V(—?PAQA-1R)V(―iPA-iQ-\R)

V(-IPAQAR)V(PAQAR)

<^>(-1PAQAR)V(-1PA->QAR)V(-iPAQA-lR)V(-)PA-iQ-1R)V(PAQAR)

(主析取范式)

三、證明：

1、P—Q,-1QVR,-1R>~?SVP=>->S

證明：

(1)-1R前提

(2)-iQVR前提

⑶一IQ(1),(2)

(4)P-Q前提

(5)-IP(3),(4)

(6)-1SVP前提

(7)?—is(5),(6)

2、A~(B~C),C~(->DVE),->F~(DA->E),A=>BfF

證明：

(1)A前提

(2)A—(B-C)前提

(3)B-*C(1),(2)

(4)B附加前提

(5)C(3),(4)

(6)C-*(-iDVE)前提

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

(8)—?F-*(DA―?E)前提

(9)F(7),(8)

(10)B-*FCP

3、PVQ,PTQ-S=>RVS

證明：

(1)-iR附加前提

(2)P-R前提

(3)-iP(1),(2)

(4)PVQ前提

(5)Q(3),(4)

(6)Q-S前提

(7)S(5),(6)

(8)RVSCP,(1),(8)

4、(P-Q)A(RfS),(QfW)A(SfX),-!(WAX),P-R=>->P

證明：

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

(2)P-*R前提

(3)R(1),(2)

(4)(PfQ)A(R-S)前提

(5)PfQ(4)

(6)RfS(5)

(7)Q(1),(5)

(8)S(3),(6)

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

(10)QT(9)

(11)ST(10)

(12)W(7),(10)

(13)X(8),(11)

(14)WAX(12),(13)

(15)-1(WAX)前提

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

5、(UVV)-*(MAN),UVP,Pf(QVS),-nQA-?S=>M

證明:

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

(2)P-(QVS)前提

(3)-iP(1),(2)

(4)uvp前提

(5)U(3),(4)

(6)uvv(5)

(7)(UVV)f(MAN)前提

(8)MAN(6),(7)

(9)M(8)

6、一?BVD,(E-*--1F)f-?D,?E=>-1B

證明：

(1)B附加前提

(2)-iBVD前提

(3)D(1),(2)

(4)(E-*-iF)->―?D前提

(5)―?(Ef-iF)(3),(4)

(6)EA-iF(5)

(7)E(6)

(8)-iE前提

(9)EA-iE(7),(8)

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

證明：

(1)p附加前提

(2)Q附加前提

(3)P-(QfR)前提

(4)QfR(1),(3)

(5)R(2),(4)

(6)Rf(QfS)前提

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

(8)S(2),(7)

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

(10)Pf9-S)CP,(1),(9)

8、P-—?Q,-.P—R,Rf--iS=>S_*-1Q

證明：

(1)S附加前提

(2)Rf-iS前提

(3)-?R(1),(2)

(4)-nP-*R前提

(5)P(3),(4)

(6)P-----iQ前提

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

(8)S-「QCP,(1),(7)

9、pf(QfR)=>(P—Q)TYPfR)

證明:

(1)PfQ附加前提

(2)P附加前提

(3)Q(1).(2)

(4)Pf(Q-R)前提

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

(6)R(3),(5)

(7)PfRCP,(2),(6)

(8)(P_Q)-*(P-R)CP,(1),(7)

10、P—jQf-iR),Q~-iP,S~R,P=>-iS

證明:

(1)P前提

(2)Pf(-1Q->->R)前提

(3)「CH->R(1),(2)

(4)Qf-iP前提

(5)-iQ⑴，(4)

(6)-iR(3),(5)

(7)SfR前提

(8)-?S(6),(7)

11、A,A-B,A-C,Bf(D-*-1C)=〉一?D

證明:

(1)A前提

(2)AfB前提

(3)B(1),(2)

(4)A-C前提

(5)C(1),(4)

(6)Bf(D-,?—?C)前提

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

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

12、A~(CVB),Bf-nA,D-*-1C=〉A(chǔ)->-1D

證明

(1)A附加前提

(2)A-(CVB)前提

(3)CVB(1),(2)

(4)B-----iA前提

(5)-1B⑴，(4)

(6)C(3),(5)

(7)D->-iC前提

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

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

13、(PfQ)A(R->Q)O(PVR)fQ

證明、

(PfQ)A(RfQ)

<=>(-IPVQ)A(-1RVQ)

。(一1P八-nR)VQ

O(PVR)VQ

O(PVR)->Q

14、P->(Q->P)Of(Pf->Q)

證明、

Pf(QfP)

?>->PV(->QVP)

O->(->P)V(->PV-iQ)

O->Pf(Pf->Q)

15、(P-?Q)A(PfR),-i(QAR),SVP=S

證明、

(1)(PfQ)A(PfR)前提

(2)Pf(QAR)(1)

(3)-1(QAR)前提

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

(5)SVP前提

(6)s(4),(5)

16、P—>-1Q,QV—iR,RA—iS=>-iP

證明、

(1)P附加前提

(2)Pf-iQ前提

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

(4)QV-iR前提

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

(6)RA-iS前提

(7)R(6)

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

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

證明、

列出兩個(gè)公式真值表：

PQP3Q(P->Q)A(QfP)

FFTT

FTFF

TFFF

TTTT

由定義可知，這兩個(gè)公式是等價(jià)。

18、PfQ=>Pf(PAQ)

證明、

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

19、用先求主范式辦法證明(P-Q)A(P-R)<=>(P-(QAR)

證明、

先求出左右兩個(gè)公式主合取范式

(P-Q)A(P-R)O(-iPvQ)A(->PVR)

<=>(->PvQV(RA-,R)))A(->PV(QA->Q)VR)

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

<^>(-1VQV-iR)A(―?PvQVR)A(—iPv—?QvR)

(P-(QAR))O([Pv(QAR))

<z>(-iPVQ)A(-1PVR)

<=>(-<PvQV(RA-iR))A(-1PV(QA-iQ)vR)

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

O(-)PVQV-iR)A(-)PVQVR)A(-iPv-iQvR)

它們有同樣主合取范式，因此它們等價(jià)。

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

證明、

設(shè)(P-Q)△-i(QVR)為T,則P-Q和一?(QVR)都為T。即P-Q和一iQA-iR都為T。故P-Q,-iQ和一iR)都為T,即P-Q

為T,Q和R都為F。從而P也為F,即一1P為T。從而(P~Q)A-i(QvR)=>-iP

21、為慶祝九七香港回歸祖國(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ì)獲亞軍;D：D隊(duì)獲亞軍;則前提符號(hào)化為A->(BvC),C->->A,Df->B,A；結(jié)論

符號(hào)化為「及

本題即證明A->(BVC)>C->—?A,D->—?B,A二^―?D。

(1)A前提

(2)A->(BVC)前提

(3)BVC(1),(2)

(4)C->—?A前提

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

(6)B(3),(5)

(7)D->->B前提

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

22、用推理規(guī)則證明P7Q,-i。丫1?)『人口不能同步為真。

證明、

(1)PAR前提

(2)P(1)

(3)PfQ前提

(4)Q(2),(3)

(5)-?(QVR)前提

(6)?QA—?R(5)

(7)-iQ(6)

(8)-iQAQ(4),(7)

(集合論某些)

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

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

證明：

(ACB)—(ACC)=(ACB)CACC=(ACB)C(AUC)

=(ACBCA)U(ACBCC)=ACBCC=AC(BAC)

=AC(B-C)

2、(A-B)U(A-C)=A-(BnO

證明：

(A-B)U(A-C)=(AAB)U(ACC)=AC(BUC)

=ACBcC=A-(BCC)

3,AUB=AUC,AkJB=AUC,則C=B

證明：

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