離散數(shù)學(xué)習(xí)題答案

1、#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100 typedef int ElemType;typedef struct ElemType dataMAX_STACK_SIZE; int top; Stack;void InitStack(Stack *S) S->top=-1; int Push(Stack *S,ElemType x) if(S->top=MAX_STACK_SIZE-1) printf("n Stack i

2、s full!"); return 0; S->top+; S->dataS->top=x; return 1; int Empty(Stack *S) return (S->top=-1); int Pop(Stack *S,ElemType *x) if(Empty(S) printf("n Stack is free!"); return 0; *x=S->dataS->top; S->top-; return 1; void conversion(int N) int e; Stack *S=(Stack*)mal

3、loc(sizeof(Stack); InitStack(S); while(N) Push(S,N%2); N=N/2; while(!Empty(S) Pop(S,&e); printf("%d ",e); void main() int n; printf("請(qǐng)輸入待轉(zhuǎn)換的值n：n"); scanf ("%d",&n); conversion(n);習(xí)題1.判斷下列語句是否是命題，為什么？若是命題，判斷是簡單命題還是復(fù)合命題？(1)離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門必修課。(2)李梅能歌善舞。(3)這朵花真美麗！(4)。

4、(5)只要我有時(shí)間，我就來看你。(6)x。(7)盡管他有病，但他仍堅(jiān)持工作。(8)太陽系外有宇宙人。(9)小王和小張是同桌。(10)不存在最大的素?cái)?shù)。解 在上述10個(gè)句子中，(3)是感嘆句，因此它不是命題。(6)雖然是陳述句，但它沒有確定的值，因此它也不是命題。其余語句都是可判斷真假的陳述句，所以都是命題。其中：(1)、(4) 、(8) 、(9) 、是簡單命題，、(2) 、(5) 、(7)、(10) 是復(fù)合命題。2.判斷下列各式是否是命題公式，為什么？(1)(P®(PQ)。(2)(ØP®Q)®(Q®P)。(3)(ØP®Q)&

5、#174;(Q®P)。(4)(Q®RS)。(5)(PQR)®S。(6)(R®(Q®R)®(P®Q)。解 (1)是命題公式。(2)不是命題公式，因?yàn)槔ㄌ?hào)不配對(duì)。(3)是命題公式。(4)是命題公式。(5)不是命題公式，因?yàn)镼R沒有意義。(6)不是命題公式，因?yàn)镽®(Q®R)®(P®Q) 沒有意義。3.將下列命題符號(hào)化：(1)我們不能既劃船又跑步。(2)我去新華書店，僅當(dāng)我有時(shí)間。(3)如果天下雨，我就不去新華書店。(4)除非天不下雨，我將去新華書店。(5)張明或王平都可以做這件事。(6)“

6、2或4是素?cái)?shù)，這是不對(duì)的”是不對(duì)的。(7)只有休息好，才能工作好。(8)只要努力學(xué)習(xí)，成績就會(huì)好的。(9)大雁北回，春天來了。(10)小張是山東人或河北人。解 (1)符號(hào)化為Ø(PQ)，其中，P：我們劃船，Q：我們跑步。(2)符號(hào)化為Q®R，其中，R：我有時(shí)間，Q：我去新華書店。(3)符號(hào)化為P®ØQ，其中，P：天下雨，Q：我去新華書店。(4)符號(hào)化為ØP®Q，其中，P：天下雨，Q：我去新華書店。(5)符號(hào)化為PQ，其中，P：張明可以做這件事，Q：王平可以做這件事。(6)符號(hào)化為Ø(Ø(PQ)，“2或4是素?cái)?shù)，這是

7、不對(duì)的”是不對(duì)的，其中，P：2是素?cái)?shù)，Q：4是素?cái)?shù)，。(7)符號(hào)化為Q®P，其中，P：休息好，Q：工作好。(8)符號(hào)化為P®Q，其中，P：努力學(xué)習(xí)，Q：成績就會(huì)好的。(9)符號(hào)化為P«Q，其中，P：大雁北回，Q：春天來了。(10)符號(hào)化為PÅQ，其中，P：小張是山東人，Q：小張是河北人。4.構(gòu)造下列命題公式的真值表，并據(jù)此說明哪些是其成真賦值，哪些是其成假賦值？(1)Ø(PØQ)。(2)P(QR)。(3)Ø(PQ)«(ØPØQ)。(4)ØP®(Q®P)。解 (1)P

8、 QPØQØ(PØQ)0 0 0 1 1 0 1 110110100由真值表可知，公式Ø(PØQ)的成真賦值為：01，成假賦值為00、10、11。(2) P Q RQRP(QR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10111011100000111由真值表可知，公式P(QR)的成真賦值為：101、110、111，成假賦值為000、001、010、011、100。(3)P QØ( PQ)ØPØQØ(PQ)«(ØPØQ)0 0 0 1 1

9、 0 1 1100010001111由真值表可知，公式Ø(PQ)«(ØPØQ)的成真賦值為：00、01、10、11，沒有成假賦值。 (4)P QQ®PØP®(Q®P)0 0 0 1 1 0 1 110111011由真值表可知，公式ØP®(Q®P)的成真賦值為：00、10、11，成假賦值為：01。5.分別用真值表法和公式法判斷下列命題公式的類型：(1)(PQ)®(PQ)。(2)(PQ)®(PQ)。(3)(ØPQ)Ø(QØR)Ø(

10、RØPØQ)。(4)(PQ®R)®(PØRQ)。(5)(Q®P)(ØPQ)。(6)(ØP«Q)«Ø(P«Q)。(7)(PQ)Ø(PQ)。解 (1)真值表法：P QPQPQ(PQ)®(PQ)0 0 0 1 1 0 1 1011100011001由真值表可知，公式(PQ)®(PQ)為可滿足式。公式法：因?yàn)?PQ)®(PQ)ÛØ(PQ)(PQ)Û(ØPØQ)(PQ)，所以，公式(PQ)

11、4;(PQ)為可滿足式。(2)真值表法：P QPQPQ(PQ)®(PQ)0 0 0 1 1 0 1 1000101111111由真值表可知，公式(PQ)®(PQ)為重言式。公式法：因?yàn)?PQ)®(PQ)ÛØ(PQ)(PQ)ÛØPØQPQÛT，所以，公式(PQ)®(PQ)為重言式。(3)真值表法：P Q RØPQQØRRØPØQ(ØPQ)Ø(QØR)Ø(RØPØQ)0 0 00 0 10 1 00

12、1 11 0 01 0 11 1 01 1 111110011101110111111110100000000由真值表可知，公式(ØPQ)Ø(QØR)Ø(RØPØQ)為矛盾式。公式法：因?yàn)?ØPQ)Ø(QØR)Ø(RØPØQ)Û(ØPQ)ØQR(ØRPQ)ÛF，所以，公式(ØPQ)Ø(QØR)Ø(RØPØQ)為矛盾式。(4)真值表法：P Q RPQ®RP&#

13、216;RQ(PQ®R)®(PØRQ)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111111010000001000000010由真值表可知，公式(PQ®R)®(PØRQ)為可滿足式。公式法：因?yàn)?PQ®R)®(PØRQ)ÛØ(Ø( PQ)R)(PØRQ)Û( PQØR)(PØRQ)Û( PQØR)所以，公式(PQ®R)®(PØRQ)為可滿足式。(5

14、)真值表法：P QQ®PØPQ(Q®P)(ØPQ)0 0 0 1 1 0 1 1101101000000由真值表可知，公式(Q®P)(ØPQ)為可矛盾式。公式法：因?yàn)?Q®P)(ØPQ)Û(ØQP)(ØPQ)ÛØ(QØP)(ØPQ)ÛF，所以，公式為可矛盾式。(6)真值表法：P QØP«QØ(P«Q)(ØP«Q)«Ø(P«Q)0 0 0 1 1 0

15、 1 1011001101111由真值表可知，公式(ØP«Q)«Ø(P«Q)為永真式。公式法：因?yàn)?ØP«Q)«Ø(P«Q)Û(ØP®Q)(Q®ØP)«Ø(PQ)(ØPØQ)Û(PQ)(ØPØQ)«(ØPØQ)(PQ)ÛT所以，公式(ØP«Q)«Ø(P«Q)為永真式。(7)真值表法：P Q

16、PQPQ(PQ)Ø(PQ)0 0 0 1 1 0 1 1000101110000由真值表可知，公式(PQ)Ø(PQ)為矛盾式。公式法：因?yàn)?PQ)Ø(PQ)Û(PQ)(ØPØQ)ÛF，所以，公式(PQ)Ø(PQ)為矛盾式。6.分別用真值表法和公式法證明下列各等價(jià)式：(1)(PQ)ØPÛØPQ。(2)Ø(PQ)(ØPQ)ÛØP。(3)(PQ)ØPÛØPQ。(4)P®(QR)Û(P®Q)(P

17、®R)。(5)(P®Q)(R®Q)Û(PR)®Q)。(6)(PQA®C)(A®PQC)Û(A(P«Q)®C。(7)Ø(P­Q)ÛØP¯ØQ。(8)Ø(P¯Q)ÛØP­ØQ。證明 (1)真值表法：P QPQ(PQ)ØPØPQ0 0 0 1 1 0 1 1011101000100由真值表可知，(PQ)ØPÛØPQ。公式法：(PQ)&

18、#216;PÛ(PØP)(QØP)ÛØPQ。(2)真值表法：P QØPQØ(PQ)(ØPQ)ØP0 0 0 1 1 0 1 1110011001100由真值表可知，Ø(PQ)(ØPQ)ÛØP。公式法：Ø(PQ)(ØPQ)Û(ØPØQ)(ØPQ)ÛØP(ØQQ)ÛØP。(3)真值表法：P QPQ(PQ)ØPØPQ0 0 0 1 1 0 1

19、1000111011101由真值表可知，(PQ)ØPÛØPQ。公式法：(PQ)ØPÛ(PØP)(QØP)ÛØPQ。(4)真值表法：P Q RP®QP®R(P®Q)(P®R)P®( QR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011111101011111000111110001由真值表可知，P®(QR)Û(P®Q)(P®R)。公式法：P®(QR)Û

20、;ØP(QR)Û(ØPQ)(ØPR)Û(P®Q)(P®R)。(5)真值表法：P Q RP®QR®Q(P®Q)(R®Q)( PR)®Q0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011101110111011001110110011由真值表可知，(P®Q)(R®Q)Û(PR)®Q)。公式法：(P®Q)(R®Q)Û(ØPQ)(ØRQ)Û

21、(ØPØR)QÛØ(PR)QÛ(PR)®Q)。(6)真值表法：P Q A CP«Q(PQA® C)(A® PQC)(A(P«Q)®C0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1111100000000111111011111111111011101111111111101由真值表可知，(PQA®C)

22、(A®PQC)Û(A(P«Q)®C。公式法：(PQA®C)(A®PQC)Û(ØPØQØAC)(ØAPQC)Û(ØPØQØAC)(ØAPQC)Û(ØPØQØA)(ØAPQ)CÛØ(PQA)(AØPØQ)CÛØ( A(PQ)(ØPØQ)CÛØ( A(P«Q)CÛ(A(P&#

23、171;Q)®C。(7)真值表法：P QP­QØ( P­Q)ØP¯ØQ0 0 0 1 1 0 1 1111000010001由真值表可知，Ø(P­Q)ÛØP¯ØQ。公式法：Ø(P­Q)ÛØ(Ø(PQ)ÛØ(ØPØQ)ÛØP¯ØQ。(8)真值表法：P QP¯QØ(P¯Q)ØP­ØQ

24、0 0 0 1 1 0 1 1100001110111由真值表可知，Ø(P¯Q)ÛØP­ØQ。公式法：Ø(P¯Q)ÛØ(Ø(PQ)ÛØ(ØPØQ)ÛØP­ØQ。7.設(shè)A、B、C為任意的三個(gè)命題公式，試問下面的結(jié)論是否正確？(1)若ACÛBC，則AÛB。(2)若ACÛBC，則AÛB。(3)若ØAÛØB，則AÛB。(4)若A

25、4;CÛB®C，則AÛB。(5)若A«CÛB«C，則AÛB。解 (1)不正確。例如，設(shè)有一賦值：AT，BF，CT，則ACÛBC，但AÛB不成立。(2)不正確。例如，設(shè)有一賦值：AT，BF，CF，則ACÛBC，但AÛB不成立。(3)正確。因?yàn)?#216;A«ØBÛ(ØA®ØB)(ØB®ØA)Û(AØB)(BØA)Û(B® A)(A®B)&#

26、219; A«B，所以，若ØAÛØB，則AÛB。(4)不正確。例如，設(shè)有一賦值：AT，BF，CT，則A®CÛB®C，但AÛB不成立。(5)正確。因?yàn)?，若A«CÛB«C，則A«C與B«C等值。當(dāng)A«C與B«C都為真時(shí)，A和C等值且B和C等值，從而A和B等值，此時(shí)AÛB；當(dāng)A«C與B«C都為假時(shí)，A和C不等值且B和C也不等值，從而A和B等值，此時(shí)AÛB?？傊?，若A«CÛB

27、1;C，則AÛB。8.試給出下列命題公式的對(duì)偶式：(1)(PQ)R。(2)T(PQ)。(3)(PQ)F。(4)Ø(PQ)(ØPQ)。解 (1)對(duì)偶式為(PQ)R。(2)對(duì)偶式為F(PQ)。(3)對(duì)偶式為(PQ)T。(4)對(duì)偶式為Ø(PQ)(ØPQ)。9.分別用真值表法、分析法和公式法證明下列蘊(yùn)涵式：(1)Ø(P®Q)ÞP。(2)(P®Q)®QÞPQ。(3)P®QÞP®(PQ)。(4)(P®Q)(Q®R)Þ(P®R)。

28、證明 (1)真值表法：P QP®QØ (P®Q)P0 0 0 1 1 0 1 1110100100011由真值表可知，Ø(P®Q)ÞP。分析法：若Ø(P®Q)為真，則P®Q為假，從而P為真，而Q為假。故Ø(P®Q)ÞP。公式法：因?yàn)?#216;(P®Q)®PÛ(ØPQ)PÛT，所以Ø(P®Q)ÞP。(2)真值表法：P QP®Q(P®Q)®QPQ0 0 0 1 1 0

29、1 1110101110111由真值表可知，(P®Q)®QÞPQ。分析法：若PQ為假，都P和Q為假，于是P®Q為真，從而(P®Q)®Q為假。故(P®Q)®QÞPQ。公式法：因?yàn)?P®Q)®Q)®(PQ)Û Ø(Ø(ØPQ)Q)(PQ)Û(ØPQ)ØQ)(PQ)Û(ØPØQ)(QØQ)(PQ)ÛØ(PQ)(PQ)ÛT所以，(P®Q

30、)®QÞPQ。(3)真值表法：P QPQP®QP®(PQ)0 0 0 1 1 0 1 1000111011101由真值表可知，P®QÞP®(PQ)。分析法：若P®(PQ)為假，則P為真且PQ為假，于是P為真且Q為假，從而P®Q為假。故P®QÞP®(PQ)。公式法：因?yàn)?P®Q)®(P®(PQ)ÛØ(ØPQ)(ØP(PQ)Û(PØQ)(ØP(PQ)Û(PØQ)

31、(ØPQ)Û(PØQ)Ø(PØQ)ÛT所以，P®QÞP®(PQ)。(4)真值表法：P Q RP®QQ®R(P®Q)(Q®R)P®R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011110111011101000111110101由真值表可知，(P®Q)(Q®R)Þ(P®R)。分析法：若P®R為假，則P為真而R為假。當(dāng)Q為真時(shí)，Q®R為假；當(dāng)Q為假時(shí)，P

32、®Q為假。從而不管Q取什么值，都有(P®Q)(Q®R)為假。故(P®Q)(Q®R)Þ(P®R)。公式法：因?yàn)?P®Q)(Q®R)®(P®R)ÛØ(ØPQ)(ØQR)(ØPR)Û(PØQ)(QØR)ØPRÛ(PØQ)(QØPR)(ØRØPR)Û(PØQ)(QØPR)Û(PQØPR)(ØQQ&

33、#216;PR)ÛT所以，(P®Q)(Q®R)Þ(P®R)。10.將下列命題公式化成與之等價(jià)的僅含聯(lián)結(jié)詞­或¯的公式：(1)P(Q®R)。(2)(P®(QR)P。 解 因?yàn)?#216;PÛØ(PP)ÛP­PPQÛØ(P­Q)Û(P­Q)­(P­Q)PQÛØ(ØPØQ)ÛØP­ØQÛ(P­P)

34、3;(Q­Q)ØPÛØ(PP)ÛP¯P PQÛØ(P¯Q)Û(P¯Q)¯(P¯Q) PQÛØP¯ØQÛ(P¯P)¯(Q¯Q)所以(1)P(Q®R)ÛP(ØQR)Û P(ØQ)­(ØQ)­(R­R)Û P(Q­Q)­( Q­Q)­(R­R)&

35、#219;(P­(Q­Q)­( Q­Q)­(R­R)­(P­(Q­Q)­( Q­Q)­(R­R)P(Q®R)Û P(ØQR)Û P(ØQ)P¯R)¯(ØQ)P¯R)Û P(Q¯Q)P¯R)¯( Q¯Q)P¯R)Û(P¯P)¯(Q¯Q)P¯R)¯( Q¯

36、;Q)P¯R)¯(Q¯Q)P¯R)¯( Q¯Q)P¯R)(2)(P®(QR)PÛ(ØP(QR)PÛ( P­P)(Q­R)­(Q­R)PÛ( P­P)(Q­R)­(Q­R)PÛ( P­P)­(P­P)­(Q­R)­(Q­R)­(Q­R)­(Q­R)PÛ( P­P

37、)­(P­P)­(Q­R)­(Q­R)­(Q­R)­(Q­R)­( P­P)­(P­P)­(Q­R)­(Q­R)­(Q­R)­(Q­R)­(P­P)(P®(QR)PÛ(ØP(QR)PÛ( P¯P)(Q¯Q)¯(R¯R)PÛ( P¯P)¯(Q¯

38、;Q)¯(R¯R)¯( P¯P)¯(Q¯Q)¯(R¯R)PÛ( P¯P)¯(Q¯Q)¯(R¯R)¯( P¯P)¯(Q¯Q)¯(R¯R)¯P)¯( P¯P)¯(Q¯Q)¯(R¯R)¯( P¯P)¯(Q¯Q)¯(R¯R)¯P)11.證明，和Ø都不是全功能

39、聯(lián)結(jié)詞組。證明 命題P經(jīng)聯(lián)結(jié)詞和反復(fù)運(yùn)算只能得出P，不能得出ØP，所以，不是全功能聯(lián)結(jié)詞組。命題P經(jīng)聯(lián)結(jié)詞反復(fù)運(yùn)算只能得出P，不能得出ØP，所以不是全功能聯(lián)結(jié)詞組。命題P經(jīng)聯(lián)結(jié)詞Ø反復(fù)運(yùn)算只能得出P和ØP，不能得出PQ，所以Ø不是全功能聯(lián)結(jié)詞組。12.證明Ø，是最小全功能聯(lián)結(jié)詞組。證明 因?yàn)镻QÛØ(ØPØQ)P®QÛØPQÛØ(PØQ)P«QÛ(P®Q)(Q®P)ÛØ(P&#

40、216;Q)Ø(QØP)所以，Ø，是最小全功能聯(lián)結(jié)詞組。13.完成定理1.8的證明。證明 設(shè)A為簡單析取式，其包含的所有命題變?cè)獮閜1、p2、pn。若A為永真式，但不同時(shí)含有某個(gè)命題變?cè)捌浞穸?，則不妨設(shè)Ap1p2piØpi1Øpn，于是當(dāng)p1、p2、pi的真值都是假，而pi1、pn的真值都是真時(shí)，A的真值為假，與A為永真式矛盾。反之，若A同時(shí)含有某個(gè)命題變?cè)捌浞穸ǎ@然有A為永真式。14.完成定理1.10的證明。證明 公式A為矛盾式當(dāng)且僅當(dāng)A的析取范式的每個(gè)簡單合取式都是矛盾式。由定理1.7可得，簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)有一個(gè)命題變

41、元及其否定。因此，公式A為矛盾式當(dāng)且僅當(dāng)A的析取范式的每個(gè)簡單合取式至少同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?5.完成定理1.11的證明。證明 公式A為永真式當(dāng)且僅當(dāng)A的合取范式的每個(gè)簡單析取式都是永真式。由定理1.8可得，簡單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)有一個(gè)命題變?cè)捌浞穸?。因此，公式A為永真式當(dāng)且僅當(dāng)A的合取范式的每個(gè)簡單析取式至少同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?6.完成定理1.14的證明。證明 設(shè)A¢是A的合取范式，即AÛA¢。若A¢的某個(gè)簡單析取式Ai中不含命題變?cè)狿及其否定ØP，將Ai展成形式AiÛAiTÛAi(P&#

42、216;P)Û(AiP)(AiØP)，繼續(xù)這個(gè)過程，直到所有的簡單析取式成為大項(xiàng)。然后，消去重復(fù)的項(xiàng)及永真式之后，得到A的主合取范式。下面證明其惟一性。若A有兩個(gè)與之等價(jià)的主合取范式B和C，則BÛC。由B和C是A的不同的主合取范式，不妨設(shè)大項(xiàng)Mi只出現(xiàn)在B中而不在C中，于是i的二進(jìn)制為B的成假賦值，C的成真賦值，與BÛC矛盾。因而A的主合取范式是惟一的。17.完成定理1.15的證明。證明 設(shè)命題公式A的真值為F的賦值所對(duì)應(yīng)的大項(xiàng)為M1、M2、Mk，令BM1M2Mk。下證AÛB。若A為假，則其賦值所對(duì)應(yīng)的小項(xiàng)一定是M1、M2、Mk中的某一項(xiàng)，不妨

43、設(shè)為Mi，因?yàn)镸i為假，而M1、M2、Mi1、Mi1、Mk都為真，故B也為假。若A為真，則其賦值所對(duì)應(yīng)的大項(xiàng)一定不是M1、M2、Mk中的某一項(xiàng)，此時(shí)M1、M2、Mk都為真，故B也為假。因此，AÛB。18.完成定理1.18的證明。證明 設(shè)A是含n個(gè)命題變?cè)拿}公式，則：(1)由定理1.13可知，A的真值為T的賦值所對(duì)應(yīng)的小項(xiàng)的析取即為此公式A的主析取范式，所以，A為永真式當(dāng)且僅當(dāng)A的主析取范式含有全部2n個(gè)小項(xiàng)。(2)由定理1.13可知，A的真值為F的賦值所對(duì)應(yīng)的大項(xiàng)的合取即為此公式的主合取范式，所以，A為矛盾式當(dāng)且僅當(dāng)A的主合取范式含有全部2n個(gè)大項(xiàng)。(3)由(1)、(2)即得。1

44、9.分別用真值表法和公式法求下面命題公式的主析取范式與主合取范式，判斷各公式的類型，并寫出其相應(yīng)的成真賦值和成假賦值。(1)P®(Q®R)。(2)(PQ)®R。(3)(P®(QR)(ØP(Q«R)。(4)(Ø(P®Q)Q)R。(5)(ØPØQ)®(P«ØQ)。(6)(P¯Q)®(PØ(QØR)。(7)Ø(P®Q)(R®P)Ø(R®ØQ)®ØP)。(

45、8)(P®(PQ)®(QR)«(ØPR)。解 (1)公式法：因?yàn)镻®(Q®R)ÛØPØQRÛÛ所以，公式P®(Q®R)為可滿足式，其相應(yīng)的成真賦值為000、001、010、011、100、101、111：成假賦值為：110。真值表法：P Q RQ®RP®(Q®R)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11101110111111101由真值表可知，公式P®(Q®R)為可滿足式，

46、其相應(yīng)的成真賦值為000、001、010、011、100、101、111：成假賦值為：110。(2)公式法：因?yàn)?PQ)®RÛØ(PQ)RÛ(ØPØQ)RÛ(ØP(QØQ)R)(PØP)ØQR)Û(ØPQR)(ØPØQR)(PØQR)(ØPØQR)ÛÛ 所以，公式(PQ)®R為可滿足式，其相應(yīng)的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。真值表法

47、：P Q RPQ(PQ)®R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10011111111010101由真值表可知，公式(PQ)®R為可滿足式，其相應(yīng)的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。(3)公式法：因?yàn)?P®(QR)(ØP(Q«R)Û(ØPQR)(ØP(QR)(ØQØR)Û(ØPQR)(ØPQ)(ØPR)(ØQØR)Û(ØPQ

48、R)(ØPQØQ)(ØPQØR)(ØPRØQ)(ØPRØR)Û(ØPQR)(ØPQØR)(ØPØQR)ÛÛ所以，公式(P®(QR)(ØP(Q«R)為可滿足式，其相應(yīng)的成真賦值為000、001、010、011、111：成假賦值為：100、101、110。真值表法：P Q RQ«RP®(QR)ØP(Q«R)(P®(QR)(ØP(Q«R)0 0

49、 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110011001111101111111100111110001由真值表可知，公式(P®(QR)(ØP(Q«R)為可滿足式，其相應(yīng)的成真賦值為000、001、010、011、111：成假賦值為：100、101、110。(4)公式法：因?yàn)?Ø(P®Q)Q)RÛ(Ø(ØPQ)Q)RÛ(PØQQ)RÛRÛ(QØQ)RÛ(QR)(ØQR)Û(PØP)QR)(P&

50、#216;P)ØQR)Û(PQR)(ØPQR)(PØQR)(ØPØQR)ÛÛ所以，公式(Ø(P®Q)Q)R為可滿足式，其相應(yīng)的成真賦值為001、011、101、111：成假賦值為：000、010、100、110。真值表法：P Q RP®QØ(P®Q)Q(Ø(P®Q)Q)R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100110000000001010101由真值表可知，公式(Ø(P®Q

51、)Q)R為可滿足式，其相應(yīng)的成真賦值為001、011、101、111：成假賦值為：000、010、100、110。(5)公式法：因?yàn)?ØPØQ)®(P«ØQ)ÛØ(ØPØQ)(PØQ)(ØPQ)Û(PQ)(PØQ)(ØPQ)ÛÛ所以，公式(ØPØQ)®(P«ØQ)為可滿足式，其相應(yīng)的成真賦值為01、10、11：成假賦值為：00。真值表法：P QØPØQP«&

52、#216;Q(ØPØQ)®(P«ØQ)0 0 0 1 1 0 1 1111001100111由真值表可知，公式(ØPØQ)®(P«ØQ)為可滿足式，其相應(yīng)的成真賦值為01、10、11：成假賦值為：00。(6)公式法：因?yàn)?P¯Q)®(PØ(QØR)ÛØ(Ø( PQ)(PØQR)Û(PQ)(PØQR)Û(PQP)(PQØQ)(PQR)Û(PQ)(PQR)Û(P

53、Q(RØR)(PQR)Û(PQR)(PQØR)(PQR)ÛÛ所以，公式(P¯Q)®(PØ(QØR)為可滿足式，其相應(yīng)的成真賦值為010、011、100、101、110、111：成假賦值為：000、001。真值表法：P Q RQØRPØ(QØR)P¯Q(P¯Q)®(PØ(QØR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110111011000010111100000000111111由真值表

54、可知，公式(P¯Q)®(PØ(QØR)為可滿足式，其相應(yīng)的成真賦值為010、011、100、101、110、111：成假賦值為：000、001。(7)公式法：因?yàn)?#216;(P®Q)(R®P)Ø(R®ØQ)®ØP)ÛØ(ØPQ)(ØRP)Ø(Ø(ØRØQ)ØP)ÛØ(ØPQ)Ø(ØRP)(ØRØQ)P)Û(P

55、6;Q)(RØP)(ØRP)(ØQP)Û(PØQ)(ØPR)(PØR)Û(PØQ(RØR)(ØP(QØQ)R)(P(QØQ)ØR)Û(PØQR)(PØQØR)(ØPQR)(ØPØQR)(PQØR)(PØQØR)Û(PØQR)(PØQØR)(ØPQR)(ØPØQR)(PQØR)&#

56、219;Û所以，公式Ø(P®Q)(R®P)Ø(R®ØQ)®ØP)為可滿足式，其相應(yīng)的成真賦值為001、011、100、101、110：成假賦值為：000、010、111。真值表法：P Q RØ(P®Q)(R®P)Ø(R®ØQ)®ØP)Ø(P®Q)(R®P)Ø(R®ØQ)®ØP)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01

57、 1 1010111000000111001011110由真值表可知，公式Ø(P®Q)(R®P)Ø(R®ØQ)®ØP)為可滿足式，其相應(yīng)的成真賦值為001、011、100、101、110：成假賦值為：000、010、111。(8)公式法：因?yàn)?P®(PQ)®(QR)«(ØPR)Û(ØPPQ)®(QR)«(ØPR)Û(QR)«(ØPR)Û(QR(ØPR)(Ø(QR)&#

58、216;(ØPR)Û(QRØP)(QRR)(ØQØR)PØR)Û(ØPQR)(QR)(ØQPØR)(ØRPØR)Û(ØPQR)(PQR)(ØPQR)(PØQØR)(PQØR)(PØQØR)Û(ØPQR)(PØQØR)(PQØR)(PQR)ÛÛ所以，公式(P®(PQ)®(QR)«(ØPR)為

59、可滿足式，其相應(yīng)的成真賦值為011、100、110、111：成假賦值為：000、001、010、101。真值表法：P Q RP®(PQ)(P®(PQ)®(QR)ØPR(P®(PQ)®(QR)«(ØPR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111111000100011111010100011011由真值表可知，公式(P®(PQ)®(QR)«(ØPR)為可滿足式，其相應(yīng)的成真賦值為011、100、110、111：成假賦值為：000

60、、001、010、101。20.使用將命題公式化為主范式的方法，證明下列各等價(jià)式：(1)(P®Q)®(PQ)Û(Q®P)(PQ)。(2)PQ(ØPQ)ÛØPØQ(PQ)。(3)Ø(P«Q)Û(PQ)Ø(PQ)。(4)(PQ)(ØPR)(QR)Û(PQ)(ØPR)。解 (1)因?yàn)?P®Q)®(PQ)ÛØ(ØPQ)(PQ)Û(PØQ)(PQ)(Q®P)(PQ)Û

61、(ØQP)(PQ)Û(PØQ)(ØQQ)(PP) (PQ)Û(PØQ)PÛ(PØQ)(P(QØQ)Û(PØQ)(PQ)(PØQ)Û(PØQ)(PQ) 所以，(P®Q)®(PQ)Û(Q®P)(PQ)。(2)因?yàn)镻Q(ØPQ)Û(P(QQ)(PP)Q)(ØPQ)Û(PQ)(PQ)(PQ)(PQ)(ØPQ)Û(PQ)(PQ)(PQ)(ØPQ)Ø

62、PØQ(PQ)Û(ØP(QQ)(PP)ØQ)(PQ)Û(ØPQ)(ØPQ)(PØQ)(PØQ)(PQ)Û(ØPQ)(ØPQ)(PØQ)(PQ)Û(PQ)(PQ)(PQ)(ØPQ)所以，PQ(ØPQ)ÛØPØQ(PQ)。(3)因?yàn)?#216;(P«Q)ÛØ(PQ)(ØPØQ) ÛØ(PQ)Ø(ØPØQ)

63、9;(ØPØQ)(PQ)Û(PQ)(ØPØQ)(PQ)Ø(PQ)Û(PQ)(ØPØQ)所以，Ø(P«Q)Û(PQ)Ø(PQ)。(4)(PQ)(ØPR)(QR)Û(PQ(RØR)(ØP(QØQ)R)(PØP)QR)Û(PQR)(PQØR)(ØPQR)(ØPØQR)(PQR)(ØPQR)Û(ØPØQR)(ØPQR

64、)(PQØR)(PQR)(PQ)(ØPR)Û(PQ(RØR)(ØP(QØQ)R)Û(PQR)(PQØR)(ØPQR)(ØPØQR)Û(ØPØQR)(ØPQR)(PQØR)(PQR)所以，(PQ)(ØPR)(QR)Û(PQ)(ØPR)。21.設(shè)計(jì)一盞電燈的開關(guān)電路，要求受3個(gè)開關(guān)A、B、C的控制：當(dāng)且僅當(dāng)A和C同時(shí)關(guān)閉或B和C同時(shí)關(guān)閉時(shí)燈亮。設(shè)F表示燈亮。(1)寫出F在全功能聯(lián)結(jié)詞組­中的命題公式。(2)寫出F的主析取范式與主合取范式。解 (1)設(shè)A：開關(guān)A關(guān)閉；B：開關(guān)B關(guān)閉；C：開關(guān)C關(guān)閉；F(AC)(BC)。在全功能聯(lián)結(jié)詞組­中：ØAÛØ(AA)ÛA­AACÛØØ( AC)ÛØ( A­C)Û(A­C)­(A­C) ABÛ