離散數(shù)學習題答案

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("請輸入待轉換的值n：n"); scanf ("%d",&n); conversion(n);習題1.判斷下列語句是否是命題，為什么？若是命題，判斷是簡單命題還是復合命題？(1)離散數(shù)學是計算機專業(yè)的一門必修課。(2)李梅能歌善舞。(3)這朵花真美麗！(4)。

4、(5)只要我有時間，我就來看你。(6)x。(7)盡管他有病，但他仍堅持工作。(8)太陽系外有宇宙人。(9)小王和小張是同桌。(10)不存在最大的素數(shù)。解 在上述10個句子中，(3)是感嘆句，因此它不是命題。(6)雖然是陳述句，但它沒有確定的值，因此它也不是命題。其余語句都是可判斷真假的陳述句，所以都是命題。其中：(1)、(4) 、(8) 、(9) 、是簡單命題，、(2) 、(5) 、(7)、(10) 是復合命題。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)不是命題公式，因為括號不配對。(3)是命題公式。(4)是命題公式。(5)不是命題公式，因為QR沒有意義。(6)不是命題公式，因為R®(Q®R)®(P®Q) 沒有意義。3.將下列命題符號化：(1)我們不能既劃船又跑步。(2)我去新華書店，僅當我有時間。(3)如果天下雨，我就不去新華書店。(4)除非天不下雨，我將去新華書店。(5)張明或王平都可以做這件事。(6)“

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

7、不對的”是不對的，其中，P：2是素數(shù)，Q：4是素數(shù)，。(7)符號化為Q®P，其中，P：休息好，Q：工作好。(8)符號化為P®Q，其中，P：努力學習，Q：成績就會好的。(9)符號化為P«Q，其中，P：大雁北回，Q：春天來了。(10)符號化為PÅQ，其中，P：小張是山東人，Q：小張是河北人。4.構造下列命題公式的真值表，并據(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)為可滿足式。公式法：因為(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)為重言式。公式法：因為(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)為矛盾式。公式法：因為(Ø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)為可滿足式。公式法：因為(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)為可矛盾式。公式法：因為(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)為永真式。公式法：因為(Ø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)為矛盾式。公式法：因為(PQ)Ø(PQ)Û(PQ)(ØPØQ)ÛF，所以，公式(PQ)Ø(PQ)為矛盾式。6.分別用真值表法和公式法證明下列各等價式：(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.設A、B、C為任意的三個命題公式，試問下面的結論是否正確？(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)不正確。例如，設有一賦值：AT，BF，CT，則ACÛBC，但AÛB不成立。(2)不正確。例如，設有一賦值：AT，BF，CF，則ACÛBC，但AÛB不成立。(3)正確。因為ØA«ØBÛ(ØA®ØB)(ØB®ØA)Û(AØB)(BØA)Û(B® A)(A®B)&#

26、219; A«B，所以，若ØAÛØB，則AÛB。(4)不正確。例如，設有一賦值：AT，BF，CT，則A®CÛB®C，但AÛB不成立。(5)正確。因為，若A«CÛB«C，則A«C與B«C等值。當A«C與B«C都為真時，A和C等值且B和C等值，從而A和B等值，此時AÛB；當A«C與B«C都為假時，A和C不等值且B和C也不等值，從而A和B等值，此時AÛB。總之有，若A«CÛB

27、1;C，則AÛB。8.試給出下列命題公式的對偶式：(1)(PQ)R。(2)T(PQ)。(3)(PQ)F。(4)Ø(PQ)(ØPQ)。解 (1)對偶式為(PQ)R。(2)對偶式為F(PQ)。(3)對偶式為(PQ)T。(4)對偶式為Ø(PQ)(ØPQ)。9.分別用真值表法、分析法和公式法證明下列蘊涵式：(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。公式法：因為Ø(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。公式法：因為(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)。公式法：因為(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為假。當Q為真時，Q®R為假；當Q為假時，P

32、®Q為假。從而不管Q取什么值，都有(P®Q)(Q®R)為假。故(P®Q)(Q®R)Þ(P®R)。公式法：因為(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.將下列命題公式化成與之等價的僅含聯(lián)結詞­或¯的公式：(1)P(Q®R)。(2)(P®(QR)P。 解 因為Ø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)結詞組。證明 命題P經聯(lián)結詞和反復運算只能得出P，不能得出ØP，所以，不是全功能聯(lián)結詞組。命題P經聯(lián)結詞反復運算只能得出P，不能得出ØP，所以不是全功能聯(lián)結詞組。命題P經聯(lián)結詞Ø反復運算只能得出P和ØP，不能得出PQ，所以Ø不是全功能聯(lián)結詞組。12.證明Ø，是最小全功能聯(lián)結詞組。證明 因為PQÛØ(ØPØQ)P®QÛØPQÛØ(PØQ)P«QÛ(P®Q)(Q®P)ÛØ(P&#

40、216;Q)Ø(QØP)所以，Ø，是最小全功能聯(lián)結詞組。13.完成定理1.8的證明。證明 設A為簡單析取式，其包含的所有命題變元為p1、p2、pn。若A為永真式，但不同時含有某個命題變元及其否定，則不妨設Ap1p2piØpi1Øpn，于是當p1、p2、pi的真值都是假，而pi1、pn的真值都是真時，A的真值為假，與A為永真式矛盾。反之，若A同時含有某個命題變元及其否定，顯然有A為永真式。14.完成定理1.10的證明。證明 公式A為矛盾式當且僅當A的析取范式的每個簡單合取式都是矛盾式。由定理1.7可得，簡單合取式是矛盾式當且僅當它同時有一個命題變

41、元及其否定。因此，公式A為矛盾式當且僅當A的析取范式的每個簡單合取式至少同時含有一個命題變元及其否定。15.完成定理1.11的證明。證明 公式A為永真式當且僅當A的合取范式的每個簡單析取式都是永真式。由定理1.8可得，簡單析取式是永真式當且僅當它同時有一個命題變元及其否定。因此，公式A為永真式當且僅當A的合取范式的每個簡單析取式至少同時含有一個命題變元及其否定。16.完成定理1.14的證明。證明 設A¢是A的合取范式，即AÛA¢。若A¢的某個簡單析取式Ai中不含命題變元P及其否定ØP，將Ai展成形式AiÛAiTÛAi(P&#

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

43、設為Mi，因為Mi為假，而M1、M2、Mi1、Mi1、Mk都為真，故B也為假。若A為真，則其賦值所對應的大項一定不是M1、M2、Mk中的某一項，此時M1、M2、Mk都為真，故B也為假。因此，AÛB。18.完成定理1.18的證明。證明 設A是含n個命題變元的命題公式，則：(1)由定理1.13可知，A的真值為T的賦值所對應的小項的析取即為此公式A的主析取范式，所以，A為永真式當且僅當A的主析取范式含有全部2n個小項。(2)由定理1.13可知，A的真值為F的賦值所對應的大項的合取即為此公式的主合取范式，所以，A為矛盾式當且僅當A的主合取范式含有全部2n個大項。(3)由(1)、(2)即得。1

44、9.分別用真值表法和公式法求下面命題公式的主析取范式與主合取范式，判斷各公式的類型，并寫出其相應的成真賦值和成假賦值。(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)公式法：因為P®(Q®R)ÛØPØQRÛÛ所以，公式P®(Q®R)為可滿足式，其相應的成真賦值為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、其相應的成真賦值為000、001、010、011、100、101、111：成假賦值為：110。(2)公式法：因為(PQ)®RÛØ(PQ)RÛ(ØPØQ)RÛ(ØP(QØQ)R)(PØP)ØQR)Û(ØPQR)(ØPØQR)(PØQR)(ØPØQR)ÛÛ 所以，公式(PQ)®R為可滿足式，其相應的成真賦值為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為可滿足式，其相應的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。(3)公式法：因為(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)為可滿足式，其相應的成真賦值為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)為可滿足式，其相應的成真賦值為000、001、010、011、111：成假賦值為：100、101、110。(4)公式法：因為(Ø(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為可滿足式，其相應的成真賦值為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為可滿足式，其相應的成真賦值為001、011、101、111：成假賦值為：000、010、100、110。(5)公式法：因為(ØPØQ)®(P«ØQ)ÛØ(ØPØQ)(PØQ)(ØPQ)Û(PQ)(PØQ)(ØPQ)ÛÛ所以，公式(ØPØQ)®(P«ØQ)為可滿足式，其相應的成真賦值為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)為可滿足式，其相應的成真賦值為01、10、11：成假賦值為：00。(6)公式法：因為(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)為可滿足式，其相應的成真賦值為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)為可滿足式，其相應的成真賦值為010、011、100、101、110、111：成假賦值為：000、001。(7)公式法：因為Ø(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)為可滿足式，其相應的成真賦值為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)為可滿足式，其相應的成真賦值為001、011、100、101、110：成假賦值為：000、010、111。(8)公式法：因為(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、可滿足式，其相應的成真賦值為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)為可滿足式，其相應的成真賦值為011、100、110、111：成假賦值為：000

60、、001、010、101。20.使用將命題公式化為主范式的方法，證明下列各等價式：(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)因為(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)因為PQ(Ø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)因為Ø(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.設計一盞電燈的開關電路，要求受3個開關A、B、C的控制：當且僅當A和C同時關閉或B和C同時關閉時燈亮。設F表示燈亮。(1)寫出F在全功能聯(lián)結詞組­中的命題公式。(2)寫出F的主析取范式與主合取范式。解 (1)設A：開關A關閉；B：開關B關閉；C：開關C關閉；F(AC)(BC)。在全功能聯(lián)結詞組­中：ØAÛØ(AA)ÛA­AACÛØØ( AC)ÛØ( A­C)Û(A­C)­(A­C) ABÛ