命題邏輯公理系統(tǒng)

1、計(jì)算機(jī)學(xué)院1計(jì)算機(jī)學(xué)院1主要內(nèi)容主要內(nèi)容 概述概述 命題邏輯公理系統(tǒng)命題邏輯公理系統(tǒng) 謂詞邏輯公理系統(tǒng)謂詞邏輯公理系統(tǒng) 公理系統(tǒng)性質(zhì)公理系統(tǒng)性質(zhì) 理論與模型理論與模型 判定問題判定問題 總結(jié)總結(jié)計(jì)算機(jī)學(xué)院2計(jì)算機(jī)學(xué)院2邏輯公理系統(tǒng)邏輯公理系統(tǒng) 公理系統(tǒng)公理系統(tǒng) 從一些從一些公理公理出發(fā)，根據(jù)出發(fā)，根據(jù)演繹法演繹法，推導(dǎo)出一系列，推導(dǎo)出一系列定理定理，形成的演繹，形成的演繹體系叫作體系叫作公理系統(tǒng)公理系統(tǒng)。 公理系統(tǒng)的組成：公理系統(tǒng)的組成： 符號集；符號集； 公式集公式集公式是用于表達(dá)命題的符號串；公式是用于表達(dá)命題的符號串； 公理集公理集公理是用于表達(dá)推理由之出發(fā)的初始肯定命題；公理是用于表達(dá)

2、推理由之出發(fā)的初始肯定命題； 推理規(guī)則集推理規(guī)則集推理規(guī)則是由公理及已證定理得出新定理的規(guī)則；推理規(guī)則是由公理及已證定理得出新定理的規(guī)則； 定理集定理集表達(dá)了肯定的所有命題。表達(dá)了肯定的所有命題。計(jì)算機(jī)學(xué)院3計(jì)算機(jī)學(xué)院3命題邏輯的公理系統(tǒng)命題邏輯的公理系統(tǒng) 定義定義3.1 3.1 命題邏輯的公理系統(tǒng)定義命題邏輯的公理系統(tǒng)定義: : 符號符號 命題變元命題變元p p1 1,p ,p2 2, ,p pn n 聯(lián)結(jié)詞符號聯(lián)結(jié)詞符號，; ; 括號括號(,)(,) 合式公式合式公式 命題變元是合式公式；命題變元是合式公式； 若若Q Q是公式，則是公式，則( (Q)是合式公式；是合式公式； 若若Q,RQ,

3、R是公式，則是公式，則(Q(QR)R)是合式公式。是合式公式。定義了所有合式公式定義了所有合式公式計(jì)算機(jī)學(xué)院4計(jì)算機(jī)學(xué)院4命題邏輯的公理系統(tǒng)命題邏輯的公理系統(tǒng) 有以下三個(gè)公理模式，其中有以下三個(gè)公理模式，其中P,Q,RP,Q,R可為任意公式可為任意公式 公理模式公理模式A1Q Q (RQ) 公理模式公理模式A2(P(P (QR) (PQ) (PR) 公理模式公理模式A3( (Q R) (RQ) 推理規(guī)則推理規(guī)則( (分離規(guī)則分離規(guī)則,MP,MP規(guī)則規(guī)則) ) 從從Q Q和和Q QR R推出推出R RQ Q和和Q QR R稱為前提稱為前提R R稱為結(jié)論稱為結(jié)論計(jì)算機(jī)學(xué)院5計(jì)算機(jī)學(xué)院5公理系統(tǒng)公理

4、系統(tǒng) 羅素公理系統(tǒng)羅素公理系統(tǒng) Q Q Q Q Q Q Q QQ Q R R Q Q R RR R Q Q (P(PQ)Q)(P(P R RQ Q R)R) 弗雷格公理系統(tǒng)弗雷格公理系統(tǒng) Q(RQ) (P(QR) (PQ) (PR) (P(QR) (Q(PR) (QR) (RQ) QQ QQ 盧卡西維茨公理系統(tǒng)盧卡西維茨公理系統(tǒng) Q(RQ) (P(QR) (PQ) (PR) (QR) (R Q)計(jì)算機(jī)學(xué)院6計(jì)算機(jī)學(xué)院6縮寫公式縮寫公式 QR=(QR) QR= (QR) QR=(QR) (RQ) QR= (QR)計(jì)算機(jī)學(xué)院7計(jì)算機(jī)學(xué)院7公式復(fù)雜度公式復(fù)雜度 公式公式Q的復(fù)雜度表示為的復(fù)雜度表示為

5、FC(Q) 命題變元復(fù)雜度為命題變元復(fù)雜度為0 0，如果，如果Q是命題變元，則是命題變元，則FC (Q)=0。 如果公式如果公式Q= R，則，則FC (Q)=FC(R)+1。 如果公式如果公式Q=R1R2，則，則FC (Q)=maxFC(R1), FC(R2)+1。計(jì)算機(jī)學(xué)院8計(jì)算機(jī)學(xué)院8推理序列推理序列 已知已知Q成立成立， 證明證明RQ成立成立 A1= Q (RQ) A A1 A2= Q Q A3= RQ 推理序列推理序列 =Q，公式集，公式集前提前提A A1 1、A A2 2、A A3 3 推理序列推理序列A A3 3 結(jié)論結(jié)論計(jì)算機(jī)學(xué)院9計(jì)算機(jī)學(xué)院9演繹與推理序列演繹與推理序列 定義定

6、義3.2 3.2 設(shè)設(shè)是合式公式集是合式公式集, , Q Q是是合式公式，有推理步驟合式公式，有推理步驟A A1 1,A,A2 2, ,A An n，公式序列公式序列 1 1, , 2 2, , n n ，其中，其中A A1 1=1 1A A2 2=2 2. .A An n=n n ( ( n n =Q=Q) ) 每個(gè)每個(gè) k k滿足以下條件之一，滿足以下條件之一， (1) (1) 是公理；是公理； (2) (2) k k ； (3) (3) 有有i,jk i,jk k k= = i i j j由由 i i, , j j用用MPMP規(guī)則規(guī)則推出。推出。 則稱它為則稱它為Q Q的從的從的一個(gè)的一

7、個(gè)推演推演( (演演繹繹) ), ,記為記為 Q Q。 稱為推演的稱為推演的前提集前提集，稱稱為為結(jié)論結(jié)論 推理序列推理序列 如果推理步驟序列如果推理步驟序列是是A A1 1,A,A2 2, ,A An n，則推則推理序列長度理序列長度n n。 推論：推論： 如果如果Q Q是公理或是公理或 Q ，則則 Q計(jì)算機(jī)學(xué)院10計(jì)算機(jī)學(xué)院10證明與定理證明與定理 如果存在從如果存在從推演出推演出Q，則記為，則記為Q 。 Q1,Q2,QnQ簡記為簡記為 Q1,Q2,Qn Q 如果如果為空集為空集 ，則記為，則記為Q。 如果如果Q，并且有推理步驟，并且有推理步驟A1,A2,An，則則A1,A2,An稱為的一

8、個(gè)稱為的一個(gè)證明證明。 如果如果Q ，則，則Q稱為稱為定理定理。計(jì)算機(jī)學(xué)院11計(jì)算機(jī)學(xué)院11 P, Q(PR)QR A1= P A1 A2=P (QP) A1 A1 A3=QP A2 = A1 A3 A4= Q(PR) A4 A5= (Q(PR)(QP)(QR) A2 A2 A6= (QP)(QR) A5 = A4A6 A7= (QR) A6 = A3A7 計(jì)算機(jī)學(xué)院12計(jì)算機(jī)學(xué)院12 例：例：(QR) (QQ) A1=Q (RQ) A A1 1 A2= (Q (RQ) (QR) (QQ) A A2 2 A3= (QR) (QQ) A2=A1A3計(jì)算機(jī)學(xué)院13計(jì)算機(jī)學(xué)院13重要定律重要定律 三

9、段論：三段論：Q, QR R 傳遞律：傳遞律：PQ,QRPR 反證律反證律：如果如果, Q R, , Q R,則則 Q 歸謬律歸謬律：如果如果, Q R, , Q R，則，則 Q計(jì)算機(jī)學(xué)院14計(jì)算機(jī)學(xué)院14重要定理重要定理 (P(QR) (Q(PR) (Q R)(PQ)(PR) (P Q)(QR)(PR) QQ QQ QQ (QR)(QR) Q(QR) R) (QR)( RQ) ( QR)( RQ) (Q R )(RQ) Q(Q R) ( QQ)(RQ) ( QQ)Q 計(jì)算機(jī)學(xué)院15計(jì)算機(jī)學(xué)院15三段論三段論 Q, QR R A1= QR A1 A2= Q A2 A3= R A1=A2 A3

10、計(jì)算機(jī)學(xué)院16計(jì)算機(jī)學(xué)院16傳遞律傳遞律 PQ,QRPR A1=(QR) (P (QR) A1 A1 A2=QR A2 A3=P (QR) A1=A2 A3 A4=(P (QR) (PQ) (PR) A2A2 A5=(PQ) (PR) A4=A3 A5 A6=(PQ) A6 A7=(PR) A5=A6A7計(jì)算機(jī)學(xué)院17計(jì)算機(jī)學(xué)院17 (P(QR)(Q(PR)A A1 1=(P =(P (Q (Q R) R) ( P ( P Q)Q)(P (P R) R) A A 2 2A A2 2= = ( P ( P Q)Q)(P (P R)R)(Q(Q( P ( P Q)Q)(P (P R) ) R) )

11、 A A 1 1A A3 3=(=(Q Q( P ( P Q)Q)(P (P R) R) ( Q( Q( P ( P Q) Q) (Q(Q(P (P R) R) A A 2 2A A4 4= (P = (P (Q (Q R) R) ( Q( Q( P ( P Q) Q) (Q(Q(P (P R) AR) A1 1, , A A2 2, , A A3 3 A A4 4A A5 5= =(P (P (Q (Q R) R) ( Q( Q( P ( P Q) Q) (Q(Q(P (P R)R) ( (P ( (P (Q (Q R) R) ( Q( Q( P ( P Q)Q) (P (P (Q (Q R

12、) R) (Q (Q (P (P R) R) A A 2 2A A6 6= =(P (P (Q (Q R)R)(Q(Q(P(PQ)Q)(P(P(Q (Q R)R)(Q(Q(P(PR) AR) A5 5=A=A4 4 A A6 6A A7 7= Q= Q(P(PQ) Q) A A 1 1A A8 8= (Q= (Q( P ( P Q) Q) ( (P ( (P (Q (Q R) R) ( Q( Q( P ( P Q) Q) A A 1 1A A9 9= (P = (P (Q (Q R) R) ( Q( Q( P ( P Q) AQ) A8 8=A=A7 7 A A9 9A A1010=(P =(

13、P (Q (Q R) R) (Q (Q (P (P R) AR) A6 6=A=A9 9 A A1010計(jì)算機(jī)學(xué)院18計(jì)算機(jī)學(xué)院18 (Q R)(P Q) (PR) A1= (Q R) (P (Q R) A1 A1 A2= (P(Q R) (P Q) (P R) A2 A2 A3= (Q R)(P Q)(P R) A1, A2 A3計(jì)算機(jī)學(xué)院19計(jì)算機(jī)學(xué)院19(PQ)(QR)(PR) A1=(Q R) (P Q) (P R) (Q R)(P Q) (PR) A2=(Q R) (P Q) (P R) (P Q)(Q R) (P R) (P(QR) (Q(PR) A3=(P Q)(QR)(PR)

14、A A2 2= =A A1 1 A A3 3計(jì)算機(jī)學(xué)院20計(jì)算機(jī)學(xué)院20 QQ A1=(Q (QQ)Q)(Q(QQ)(QQ) A A2 2 A2=Q (QQ) Q) A1A1 A3=(Q (QQ) (QQ) A1=A2A3 A4=Q (QQ) A1A1 A5=QQ A3=A4A5計(jì)算機(jī)學(xué)院21計(jì)算機(jī)學(xué)院21 QQ A1=Q (QQ) A1A1 A2= (QQ) ( QQ) A3A3 A3=( QQ) (QQ) A3A3 A4= Q (QQ) A1, A2, A3 A4 A5=(Q (QQ) (Q Q) (Q Q) A2A2 A6=(Q Q) (Q Q) A5=A4 A6 A7=(Q Q) Q

15、Q A8=Q Q A6=A7 A8 計(jì)算機(jī)學(xué)院22計(jì)算機(jī)學(xué)院22 Q Q A1= (Q Q)(QQ) A3 A3 A2= (Q Q) QQ A3= (QQ) (QQ ) A3 A3 A4= QQ A3=A2 A4 計(jì)算機(jī)學(xué)院23計(jì)算機(jī)學(xué)院23 (Q(QR)R)( (Q QR) R) A A1 1= R= RR R Q QQ Q A A2 2=(R=(RR)R)( (Q Q(R(RR) R) A A 1 1 A A3 3= =Q Q(R(RR) AR) A2 2=A=A1 1 A A3 3 A A4 4=(=(Q Q(R(RR)R)( ( (Q QR)R)( (Q QR)R) ) A A 2 2

16、 A A5 5= (= (Q QR)R)( (Q QR) AR) A4 4=A=A3 3 A A5 5 A A6 6= = Q Q Q Q Q QQ Q A A7 7=(=(Q Q Q)Q)(Q(QR)R)( (Q Q R) R) (P(P Q)Q)(Q (Q R)R)(P (P R)R) A A8 8=(Q=(QR)R)( (Q Q R) AR) A7 7=A=A6 6 A A8 8 A A9 9=(Q=(QR)R)( (Q QR) AR) A8 8, A, A5 5A A9 9計(jì)算機(jī)學(xué)院24計(jì)算機(jī)學(xué)院24 Q(QR) R)A A1 1=(Q=(QR)R)(Q(QR) R) Q QQ QA

17、A2 2=(Q=(QR)R)(Q(QR)R)( (Q Q( (Q QR R) )R) R) (P (P(Q(QR)R)(Q(Q(P(PR)R)A A3 3= Q= Q(Q(QR)R)R) R) A A2 2= =A A1 1 A A3 3計(jì)算機(jī)學(xué)院25計(jì)算機(jī)學(xué)院25(QR) ( R Q)A1 1= (QR)(QR) (Q(QR)R)( (Q QR) R) A2 2= ( Q R) ( R Q) A3A3A3 3= (QR)( Q R) A A2 2= =A A1 1 A A3 3 計(jì)算機(jī)學(xué)院26計(jì)算機(jī)學(xué)院26 ( Q R )( RQ)A1 1= ( QR)( RQ) (QR) ( R Q)A2

18、 2= QQ QQA3 3= (Q Q)( RQ)( RQ) (Q R)(P Q) (PR) A4 4= ( RQ)( RQ) A A3 3= =A A2 2 A A4 4A5 5= ( QR) ( RQ) A1, A4 A5計(jì)算機(jī)學(xué)院27計(jì)算機(jī)學(xué)院27 (Q R )(RQ) A1 1= (Q R )(RQ) A3A3 A2 2= (Q Q) (Q R ) (QR ) (PQ)(QR)(PR) A3 3= (Q Q) (Q Q) A4 4= (Q R ) (QR ) A A2 2= =A A3 3 A A4 4 A5 5= (Q R ) (RQ) A4, A1 A5計(jì)算機(jī)學(xué)院28計(jì)算機(jī)學(xué)院28

19、 Q(Q R)(涵義涵義) A1= Q(RQ) A1A1 A2= ( RQ) (QR) A3A3 A3= Q(QR) A1， A2 A3 計(jì)算機(jī)學(xué)院29計(jì)算機(jī)學(xué)院29 ( ( Q QQ)Q)(R(RQ)Q) A A1 1= = Q Q( (R RQ) Q) A1A1 A A2 2=(=(R RQ)Q)(Q(QR R) ) A3A3 A A3 3= = Q Q (Q(QR R) ) A A1 1, A, A2 2A A3 3 A A4 4=(=( Q Q(Q(QR)R) ( ( Q QQ)Q)( ( Q QR) R) A2A2 A A5 5=( =( Q Q Q) Q) ( ( Q Q R) A

20、R) A4 4=A=A3 3 A A5 5 A A6 6= (= ( Q Q R) R) (R(RQ) Q) A 3A 3 A A7 7=(=( Q QQ)Q)(R(RQ) AQ) A5 5, A, A6 6A A7 7計(jì)算機(jī)學(xué)院30計(jì)算機(jī)學(xué)院30 ( ( Q QQ)Q)Q Q A A1 1=(=( Q QQ)Q)( ( Q QQ)Q)Q) Q) ( ( Q QQ)Q)(R(RQ)Q) A A2 2=(=( Q QQ)Q)( ( Q QQ)Q)Q)Q) ( Q QQ)Q)( ( Q QQ) Q) ( ( Q QQ)Q)Q) Q) A2A2 A A3 3=(=( Q QQ)Q)( ( Q QQ)

21、Q)( ( Q QQ)Q)Q) AQ) A2 2=A=A1 1 A A3 3 A A4 4= (= ( Q QQ)Q) ( ( Q QQ) Q) A 1A 1 A A5 5=(=( Q QQ)Q)Q AQ A3 3=A=A4 4 A A5 5計(jì)算機(jī)學(xué)院31計(jì)算機(jī)學(xué)院31 QRQ A1= Q(RQ) A1A1 A2= QRQ QR=(QR)計(jì)算機(jī)學(xué)院32計(jì)算機(jī)學(xué)院32 QR RQA1 1= =(R(RQ)Q)(Q (Q R) R) (R(RQ)Q)(Q (Q R) R) A2 2=(=(R(RQ)Q)(Q (Q R)R) ( ( (Q(QR)R)(R(RQ)Q) (RQ)( Q R) A3 3=

22、 = (Q(QR)R)(R(RQ) Q) Q R = (QR)A4 4= = Q Q R R R R Q Q計(jì)算機(jī)學(xué)院33計(jì)算機(jī)學(xué)院33 QRQA1 1= Q(R Q) A1A1 A2 2= (RQ)(QR) (QR)(RQ)A3 3= = Q(Q R) A A1 1, A, A2 2A A3 3A4 4=(Q(Q R) ) (Q R)Q) (QR)(RQ)A5 5= = (Q R)Q A A4 4=A=A3 3 A A5 5A6 6= QR Q QR =(QR)計(jì)算機(jī)學(xué)院34計(jì)算機(jī)學(xué)院34 例：若例：若R，則則QR。 A1=C1 Ak-1=Ck-1 Ak=R R Ak+1= R (QR) A

23、1 Ak+2= QR Ak+1=Ak Ak+2 QR計(jì)算機(jī)學(xué)院35計(jì)算機(jī)學(xué)院35例：若例：若 PQ ， P (QR) ，則則 PR。A1=D1Am-1=Dm-1Am= PQ PQ Am+1=Dm+1Am+n-1=Dm+n-1Am+n= P (QR) P (QR) Am+n+1=(P(QR) ) (PQ) (PR) A A2 2Am+n+2=(PQ) (PR) Am+n+1=Am+nAm+n+2Am+n+3=PR Am+n+2=AmAm+n+3計(jì)算機(jī)學(xué)院36計(jì)算機(jī)學(xué)院36演繹定理演繹定理 Q R 當(dāng)且當(dāng)且 僅當(dāng)僅當(dāng) QR 歸納基礎(chǔ)：歸納基礎(chǔ)：用關(guān)于用關(guān)于Q到到R的推演長度的推演長度n作歸納證明。

24、作歸納證明。 當(dāng)當(dāng)n=1時(shí)，時(shí)，R或?yàn)楣?，或?qū)儆诨驗(yàn)楣?，或?qū)儆?，或，或R是是Q。 若若R是公理，則是公理，則 A1=R A2= R(QR) A3= (QR) 所以所以 QR，從而從而 QR 若若 R ，則，則 A1=R A2= R(QR) A3= (QR) 有有 QR 若若R=Q，則，則 Q Q 所以所以 QQ計(jì)算機(jī)學(xué)院37計(jì)算機(jī)學(xué)院37演繹定理演繹定理(2)(2) 歸納假設(shè)：歸納假設(shè)：假設(shè)假設(shè)Q到到R的推演長度小于的推演長度小于n定理成立。定理成立。 歸納證明：當(dāng)歸納證明：當(dāng)Q到到R的推演長度等于的推演長度等于n時(shí)，有時(shí)，有 Q R A1=Q1 A2=Q2 Ai= PR Aj=P An

25、=R 從從的推演的推演 A1=D1 Am= QP Ak= Q (PR) Ak+1= Q (PR) (QP) (Q R) Ak+2= (QP)(Q R) Ak+3= (Q R) 因?yàn)橐驗(yàn)閕,jn,有所以有所以 Q P QP Q PR Q (PR)計(jì)算機(jī)學(xué)院38計(jì)算機(jī)學(xué)院38演繹定理演繹定理(3)(3) 到到QR 的推演的推演 由由 QR可知，有推理序列可知，有推理序列A1, A2, Am， 使得使得Am= QR 。 證明有證明有Q R 。因?yàn)?。因?yàn)?有推理序列有推理序列A1, A2, Am，其中，其中 Am= QR Am+1= Q Am+2= R計(jì)算機(jī)學(xué)院39計(jì)算機(jī)學(xué)院39 (Q(QR) (QR

26、) 根據(jù)演繹規(guī)則根據(jù)演繹規(guī)則 (Q (Q R) Q R (Q (Q R) ,Q R A1= Q (Q R) A2= Q A3= Q R A4=R計(jì)算機(jī)學(xué)院40計(jì)算機(jī)學(xué)院40再看傳遞律再看傳遞律 PQ,QRPR (Q R) (P Q) (P R) (P Q) (Q R) (P R)計(jì)算機(jī)學(xué)院41計(jì)算機(jī)學(xué)院41 (P(QR) (Q(PR) 根據(jù)演繹規(guī)則根據(jù)演繹規(guī)則 P (Q R) Q (P R) P (Q R) ,Q P R P (Q R) ,Q, P R A1= P(Q R) A2= P A3= Q R A4=Q A5=R計(jì)算機(jī)學(xué)院42計(jì)算機(jī)學(xué)院42反證律反證律 如果如果, Q R, , Q R

27、,則 QA1 1= = Q RA2 2= = Q RA3 3= (= ( QR)(R Q )A4 4= = RQ A5 5= = QQA6 6= = (Q Q)QA7 7= = Q 計(jì)算機(jī)學(xué)院43計(jì)算機(jī)學(xué)院43歸謬律歸謬律 如果如果, Q R, , Q R，則，則 QA1 1= = Q RA2 2= = Q RA3 3= = RQA4 4= = Q Q A5 5= = = QQA6 6= = = Q QA7 7= = ( Q Q) QA8 8= = Q 計(jì)算機(jī)學(xué)院44計(jì)算機(jī)學(xué)院44 P,QP Q P,Q, (P Q)Q， P,Q, (P Q) Q A1 1= PA2 2= Q A3 3= (P

28、 Q)A4 4= (P Q) (P Q) A5 5= P QA6 6= Q 所以有所以有P,Q (P Q)，即，即P,Q P Q計(jì)算機(jī)學(xué)院45計(jì)算機(jī)學(xué)院45 (PQ) (PR) (PQ R)演繹定理：演繹定理：(PQ) (PR) ，P Q RA1 1= ( PQ) (PR)A2 2= PA3 3= ( PQ) (PR) ( PQ) A4 4= PQA5 5= QA6 6= ( PQ) (PR) ( PR)A7 7= PRA9 9= RA1010= Q R計(jì)算機(jī)學(xué)院46計(jì)算機(jī)學(xué)院46主要內(nèi)容主要內(nèi)容 概述概述 命題邏輯公理系統(tǒng)命題邏輯公理系統(tǒng) 謂詞邏輯公理系統(tǒng)謂詞邏輯公理系統(tǒng) 公理系統(tǒng)性質(zhì)公理系

29、統(tǒng)性質(zhì) 理論與模型理論與模型 判定問題判定問題 總結(jié)總結(jié)計(jì)算機(jī)學(xué)院47計(jì)算機(jī)學(xué)院47謂詞邏輯的公理系統(tǒng)謂詞邏輯的公理系統(tǒng) 定義定義3.4 3.4 謂詞邏輯的公理系統(tǒng)定義如下：謂詞邏輯的公理系統(tǒng)定義如下： (1) (1) 符號：符號： 個(gè)體變元個(gè)體變元x x1 1,x ,x2 2 , , 個(gè)體常元個(gè)體常元a a1 1,a ,a2 2 , , 對每個(gè)正整數(shù)對每個(gè)正整數(shù)n n，n n元函數(shù)符號元函數(shù)符號f f1 1,f ,f2 2 , , 對每個(gè)正整數(shù)對每個(gè)正整數(shù)m m，m m元謂詞符號元謂詞符號P P1 1,P ,P2 2 , , 聯(lián)結(jié)詞符號聯(lián)結(jié)詞符號 ， 量詞符號量詞符號 逗號，逗號， 括號括號

30、(,)(,)計(jì)算機(jī)學(xué)院48計(jì)算機(jī)學(xué)院48 (2) (2) 項(xiàng)定義如下：項(xiàng)定義如下： 個(gè)體常元是項(xiàng)；個(gè)體常元是項(xiàng)； 個(gè)體變元是項(xiàng)；個(gè)體變元是項(xiàng)； 若是若是t t1 1,t,tn n項(xiàng)，則是項(xiàng)，則是f fi i(t (t1 1,t,tn n) )項(xiàng)。項(xiàng)。 (3) (3) 公式定義如下：公式定義如下： 若是若是t t1 1,t,tn n項(xiàng)，則項(xiàng)，則P Pi i(t (t1 1,t,tn n) )是公式。是公式。 若若A A是公式，則（是公式，則（A A）是公式；）是公式； 若若A,BA,B是公式，則（是公式，則（A AB B）是公式；）是公式； 若若A A是公式，則（是公式，則（xA A）是公式。）

31、是公式。計(jì)算機(jī)學(xué)院49計(jì)算機(jī)學(xué)院49 公理公理 公理模式公理模式A A1 1A A (BA) 公理模式公理模式A A2 2(A(A (BR) (AB) (AR) 公理模式公理模式A A3( (A B) (BA) 公理模式公理模式A A4 4 xAAtx 其中項(xiàng)其中項(xiàng)t t對于對于A A中的中的x x可代入可代入 公理模式公理模式A A5 5 x( ( AB) (A xB)其中其中x不是不是A A中自由變元中自由變元 公理模式公理模式A A4 4說明說明 如果公式如果公式A A對于一對于一切切x x成立，則公式成立，則公式A A對于任意對于任意t t成立。成立。 但是，但是， 項(xiàng)項(xiàng)t t中沒有中

32、沒有約束變元約束變元 在自然數(shù)論域在自然數(shù)論域xy(xy) y(yy)計(jì)算機(jī)學(xué)院50計(jì)算機(jī)學(xué)院50 5) 5) 推理規(guī)則：推理規(guī)則： 分離規(guī)則（簡稱分離規(guī)則（簡稱MPMP規(guī)則）：規(guī)則）： 從從A A和和A AB B推出推出B B。 概括規(guī)則（簡稱概括規(guī)則（簡稱UGUG規(guī)則）：規(guī)則）： 從從A A推出（推出（x A A）。）。 概括規(guī)則說明概括規(guī)則說明 x x是自由出現(xiàn)是自由出現(xiàn)x不是常元不是常元x不是選擇變元不是選擇變元計(jì)算機(jī)學(xué)院51計(jì)算機(jī)學(xué)院51縮寫公式縮寫公式 AB=(AB) AB= (AB) AB=(AB) (BA) AB= (AB) xA(x)=xA(x)計(jì)算機(jī)學(xué)院52計(jì)算機(jī)學(xué)院52公

33、式復(fù)雜度公式復(fù)雜度 公式公式A的復(fù)雜度表示為的復(fù)雜度表示為FC(A) 命題變元復(fù)雜度為命題變元復(fù)雜度為0 0，如果，如果P P是謂詞變元，則是謂詞變元，則FC (P)=0FC (P)=0。 如果公式如果公式A=A= B B，則，則FC (A)=FC(B)+1FC (A)=FC(B)+1。 如果公式如果公式A=B1A=B1B2B2，則，則FC (A)=maxFC(B1), FC(B2)+1FC (A)=maxFC(B1), FC(B2)+1。 如果公式如果公式A= A= x B B，則，則FC (A)= FC(B)+1FC (A)= FC(B)+1。計(jì)算機(jī)學(xué)院53計(jì)算機(jī)學(xué)院53演繹與證明演繹與證

34、明 定義定義3.2 3.2 設(shè)設(shè)是合式公式集是合式公式集, , Q Q是是合式公式，有推理步驟合式公式，有推理步驟A A1 1,A,A2 2, ,A An n，公式序列公式序列 1 1, , 2 2, , n n ，其中，其中A A1 1=1 1A A2 2=2 2. .A An n=n n ( ( n n =Q=Q) ) 每個(gè)每個(gè) k k滿足以下條件之一，滿足以下條件之一， (1) (1) 是公理；是公理； (2) (2) k k ； (3) (3) 有有i,jk i,jk k k= = i i j j由由 i i, , j j用用MPMP規(guī)則規(guī)則推出。推出。 (4) (4) 有有ijij使

35、使A Aj j= = x xA Ai i由用由用UGUG規(guī)則推出規(guī)則推出 則稱它為則稱它為Q Q的從的從的一個(gè)的一個(gè)推演推演( (演演繹繹) ), ,記為記為 Q Q。 稱為推演的稱為推演的前提集前提集，稱稱為為結(jié)論結(jié)論 序列序列A A1 1,A,A2 2, ,A An n，稱稱為從為從演繹出演繹出n n的的一個(gè)一個(gè)證明證明。 nn也稱由也稱由可可證明證明n n。 推理序列推理序列 如果推理步驟序列如果推理步驟序列是是A A1 1,A,A2 2, ,A An n，則推則推理序列長度理序列長度n n。 推論：推論： 如果如果Q Q是公理或是公理或 Q ，則則 Q計(jì)算機(jī)學(xué)院54計(jì)算機(jī)學(xué)院54 x(

36、P(x)P(x)A1 1= = P(x) P(x)A2 2= = P(x)P(x)A3 3= = x(P(x)P(x)計(jì)算機(jī)學(xué)院55計(jì)算機(jī)學(xué)院55 xP(x) xP(x)A1 1= xP(x) P(y)A2 2=(xP(x) P(y) (P(y) xP(x) )A3 3= P(y) xP(x)A4 4= P(y) P(y) A5 5= P(y) xP(x)A6 6= xP(x) P(y)A7 7= xP(x) xP(x)計(jì)算機(jī)學(xué)院56計(jì)算機(jī)學(xué)院56主要性質(zhì)主要性質(zhì) xR(x) y R(y) xR(x) y R(y) xR(x) xR(x) x(P(x) Q(x) (xP(x) x Q(x) x

37、(P(x) Q(x) (xP(x) x Q(x) x(P(x) Q(x) (xP(x) xQ(x) x(P(x) Q(x) (xP(x) xQ(x) x(P(x) Q(x) (xP(x) xQ(x) xP(x) xQ(x)x(P(x) Q(x) xy R(x,y) yxR(x,y) xy R(x,y) yxR(x,y) xyR(x,y) yx R(x,y) xyR(x,y) xR(x,x) xR(x,x) xyR(x,y) 計(jì)算機(jī)學(xué)院57計(jì)算機(jī)學(xué)院57 xQ(x) xQ(x) y Q(y) (yy Q(y) (y不在不在Q Q中出現(xiàn)中出現(xiàn)) ) A A1 1= = xQ(x) xQ(x) Q(

38、y)Q(y) A A2 2= = y y( ( xQ(x) xQ(x) Q(y)Q(y) A A3 3= = y y( ( xQ(x) xQ(x) Q(y)Q(y)( ( xQ(x) xQ(x) y Q(y)y Q(y) A A4 4= = xQ(x) xQ(x) y Q(y)y Q(y)計(jì)算機(jī)學(xué)院58計(jì)算機(jī)學(xué)院58 x x y R(x,y)y R(x,y)y y xR(x,y)xR(x,y) A A1 1= = x x y R(x,y) y R(x,y) y R(x,y)y R(x,y) A A2 2= = y R(x,y)y R(x,y)R(x,y)R(x,y) A A3 3= = x x

39、 y R(x,y) y R(x,y) R(x,y)R(x,y) A A4 4= = x x ( ( x x y R(x,y) y R(x,y) R(x,y)R(x,y) A A5 5= = x x ( ( x x y R(x,y) y R(x,y) R(x,y) R(x,y) ( ( x x y R(x,y) y R(x,y) xR(x,y)xR(x,y) ) A A6 6= =( ( x x y R(x,y) y R(x,y) xR(x,y)xR(x,y) ) A A7 7= = y y( ( x x y R(x,y) y R(x,y) xR(x,y)xR(x,y) ) A A8 8= =

40、y y( ( x x y R(x,y) y R(x,y) xR(x,y)xR(x,y) ) ( ( x x y R(x,y)y R(x,y)y y xR(x,y)xR(x,y) ) A A9 9= =( ( x x y R(x,y)y R(x,y)y y xR(x,y)xR(x,y) )計(jì)算機(jī)學(xué)院59計(jì)算機(jī)學(xué)院59 x x yR(x,y)yR(x,y)xR(x,x)xR(x,x) A A1 1= = x x yR(x,y)yR(x,y)yR(x,y)yR(x,y) A A2 2= = yR(x,y) yR(x,y) R(x,x)R(x,x) A A3 3= = x x yR(x,y)yR(x,

41、y) R(x,x)R(x,x) A A4 4= = x x ( ( x x yR(x,y)yR(x,y) R(x,x)R(x,x) A A5 5= = x x ( ( x x yR(x,y)yR(x,y) R(x,x) R(x,x) ( ( x x yR(x,y)yR(x,y)xR(x,x)xR(x,x) ) x x yR(x,y)yR(x,y)xR(x,x)xR(x,x)計(jì)算機(jī)學(xué)院60計(jì)算機(jī)學(xué)院60 Q(c) Q(c) xQ(x) xQ(x) A A1 1= = x x Q(x) Q(x) Q(c)Q(c) A A2 2=(=( x x Q(x) Q(x) Q(c) Q(c) ( (Q(c)

42、 Q(c) x x Q(x)Q(x) A A3 3= =Q(c) Q(c) x x Q(x)Q(x) A A4 4= = Q(c) Q(c) Q(c)Q(c) A A5 5= = Q(c) Q(c) x x Q(x)Q(x) A A6 6= = Q(c) Q(c) xQ(x)xQ(x)計(jì)算機(jī)學(xué)院61計(jì)算機(jī)學(xué)院61 Q(c) Q(c) xQ(x)xQ(x) A A1 1= = xQ(x) xQ(x) Q(c)Q(c) A A2 2=(=( xQ(x) xQ(x) Q(c) Q(c) ( ( Q(c)Q(c) xQ(x)xQ(x) A A3 3= = Q(c)Q(c) xQ(x) xQ(x) 計(jì)算

43、機(jī)學(xué)院62計(jì)算機(jī)學(xué)院62 xQ(x)xQ(x)xQ(x)xQ(x) A A1 1= = xQ(x)xQ(x) Q(c) Q(c) A A2 2= = Q(c) Q(c) xQ(x) xQ(x) A A3 3= = xQ(x)xQ(x) xQ(x) xQ(x) 計(jì)算機(jī)學(xué)院63計(jì)算機(jī)學(xué)院63 x(P(x)x(P(x)Q(x)Q(x) ( ( xP(x) xP(x) x x Q(x) Q(x) A A1 1= = ( ( x(P(x)x(P(x)Q(x)Q(x)(P(x)(P(x)Q(x)Q(x) A A2 2= =(P(x)(P(x)Q(x)Q(x)( ( xP(x)xP(x) P(x) P(x)

44、( ( xP(x) xP(x) Q(x)Q(x) A A3 3= (= ( x(P(x)x(P(x)Q(x)Q(x) ( ( xP(x)xP(x)P(x)P(x)( ( xP(x) xP(x) Q(x)Q(x) A A4 4= (= ( x(P(x)x(P(x)Q(x)Q(x) ( ( xP(x) xP(x) Q(x)Q(x) A A5 5= = x (x ( x(P(x)x(P(x)Q(x)Q(x) ( ( xP(x) xP(x) Q(x)Q(x) A A6 6= = x(P(x)x(P(x)Q(x)Q(x)x x ( ( xP(x) xP(x) Q(x)Q(x) A A7 7= = x x

45、 ( ( xP(x) xP(x) Q(x) Q(x) ( ( xP(x) xP(x) x x Q(x) Q(x) A A8 8= = x(P(x)x(P(x)Q(x)Q(x) ( ( xP(x) xP(x) x x Q(x) Q(x)計(jì)算機(jī)學(xué)院64計(jì)算機(jī)學(xué)院64 (xP(x) xQ(x) x(P(x) Q(x) A1 1= (xP(x) xQ(x) xP(x) A2 2= xP(x) P(x)A3 3= (xP(x) xQ(x) P(x)A4 4= (xP(x) xQ(x) xQ(x)A5 5= xQ(x) Q(x)A6 6= (xP(x) xQ(x) Q(x)A7 7= (xP(x) xQ(

46、x) P(x) Q(x)A8 8=x(xP(x) xQ(x) P(x) Q(x)A9 9= (xP(x) xQ(x) x(P(x) Q(x)計(jì)算機(jī)學(xué)院65計(jì)算機(jī)學(xué)院65演繹定理演繹定理 A A B B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A AB B 因?yàn)橐驗(yàn)锳 AxA不是有效公式，不是有效公式，A A 可證，可證， xA可證？ 變元變元 約束變元約束變元 自由變元自由變元 出現(xiàn)出現(xiàn) 約束出現(xiàn)約束出現(xiàn) 自由出現(xiàn)自由出現(xiàn)計(jì)算機(jī)學(xué)院66計(jì)算機(jī)學(xué)院66演繹定理演繹定理 A A B B，且且A A為閉公式為閉公式， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A AB B 歸納基礎(chǔ)：歸納基礎(chǔ)：用關(guān)于用關(guān)于 A A 到到B B的推演長度的推演長度

47、n n作歸納證明。作歸納證明。 當(dāng)當(dāng)n=1n=1時(shí)，時(shí)，B B或?yàn)楣?，或?qū)儆诨驗(yàn)楣?，或?qū)儆?，或，或B B是是A A。 若若B B是公理，則是公理，則A A1 1=B=BA A2 2= B= B(AB)A A3 3= = (AB)所以所以 AB，從而從而 A AB B 若若 B B ，則，則 若若B=AB=A，則，則 A A A AA A1 1=B =B 所以所以 A AA AA A2 2= B= B(AB)A A3 3= = (AB)有有 A AB B計(jì)算機(jī)學(xué)院67計(jì)算機(jī)學(xué)院67演繹定理演繹定理(2)(2) 歸納假設(shè)：歸納假設(shè)：假設(shè)假設(shè) A A 到到B B的推演長度小于的推演長度小于n

48、n定理成立。定理成立。 歸納證明：當(dāng)歸納證明：當(dāng) A A 到到B B的推演長度等于的推演長度等于n n時(shí)，并且時(shí)，并且B B由分離由分離規(guī)則推出有規(guī)則推出有 A A B B A A1 1=B=B1 1 A A2 2=B=B2 2 A An n=B=B A Ai i= = R R A Aj j= = R R B B 從從 的推演的推演 A A1 1=D=D1 1 A Am m= A= AR R A Ak k= A= A (R (RB B) ) A Ak+1k+1=(=(A A (R (R B B) ) (A A R R) ) (A (A B B) ) A Ak+2k+2= =(A A R R)

49、) (A (A B B) ) A Ak+3k+3=A =A B B 因?yàn)橐驗(yàn)閕,jn,i,jn,所以所以 A A R R A AR R A A R RB B A A (R (RB B) )計(jì)算機(jī)學(xué)院68計(jì)算機(jī)學(xué)院68演繹定理演繹定理(3)(3) 歸納證明：當(dāng)歸納證明：當(dāng) A A 到到B B的推演長度等于的推演長度等于n n時(shí)，并且時(shí)，并且B B由綜合規(guī)則推出，所以由綜合規(guī)則推出，所以 從從 的推演的推演A A1 1= =B B1 1. . A Am m= = A A R R A Am+1m+1= =x(A A R R )A Am+2m+2= = A A xR A A為閉公式為閉公式 A B A

50、1=B1 A2=B2 An-1= R An= xR An=B 因?yàn)橐驗(yàn)?A RA R推演推演長度等于長度等于n-1n-1，所以，所以 A AR R計(jì)算機(jī)學(xué)院69計(jì)算機(jī)學(xué)院69演繹定理演繹定理(4)(4) 到到A AB B 的推演的推演 由由 A AB B可知，有推理序列可知，有推理序列A A1 1, A, A2 2, A, Am m，使得，使得A Am m= = A AB B 。 證明有證明有 A A B B 。因?yàn)?。因?yàn)?有推理序列有推理序列A A1 1, A, A2 2, A, Am m，其中，其中 A Am m= = A AB B A Am+1m+1= = A A A Am+2m+2=

51、= B B計(jì)算機(jī)學(xué)院70計(jì)算機(jī)學(xué)院70 選擇規(guī)則：選擇規(guī)則： xP(x)P(c) 引入規(guī)則：引入規(guī)則： P(c) xP(x) 計(jì)算機(jī)學(xué)院71計(jì)算機(jī)學(xué)院71 x(P(x) Q(x) (xP(x) xQ(x) ) x(P(x) Q(x)，xP(x) xQ(x) A1 1= = x(P(x) Q(x) A2 2= = x(P(x) Q(x) (P(c) Q(c) A3 3= = P(c) Q(c) A4 4= = xP(x) A5 5= = xP(x) P(c) A6 6= = P(c) A7 7= = Q(c) A8 8= =Q(c) xQ(x) A9 9= = xQ(x)計(jì)算機(jī)學(xué)院72計(jì)算機(jī)學(xué)院

52、72 x(P(x) Q(x) (xP(x) xQ(x) x(P(x) Q(x) xP(x) xQ(x)A1 1= x(P(x) Q(x)A2 2= x(P(x) Q(x) P(x) Q(x)A3 3= P(x) Q(x)A4 4= P(x) Q(x) P(x) A5 5= P(x) A6 6= xP(x) A7 7= P(x) Q(x) Q(x) A8 8= Q(x) A9 9= xQ(x)A1010= xP(x) xQ(x)計(jì)算機(jī)學(xué)院73計(jì)算機(jī)學(xué)院73 x(P(x,y)Q(x,y)( xP(x,y) xQ(x,y) )？ x(P(x,b)Q(x,b)( xP(x, b) xQ(x, b) )

53、計(jì)算機(jī)學(xué)院74計(jì)算機(jī)學(xué)院74 定理定理3.11 3.11 設(shè)設(shè)c1, cm是在是在語句集中不出現(xiàn)的不同常元，語句集中不出現(xiàn)的不同常元， y1, , ym是在公式是在公式Q(c1, cm)中不出現(xiàn)的不同變元，用中不出現(xiàn)的不同變元，用y1, , ym分別同時(shí)代替分別同時(shí)代替Q(c1, cm)中的中的c1, , cm得到得到Q(y1, ym) 。若。若 Q(c1, cm)，則，則 Q(y1, ym) 。計(jì)算機(jī)學(xué)院75計(jì)算機(jī)學(xué)院75 證明步驟證明步驟A1 1 An n： (1)(1)使用公理模式對應(yīng)使用公理模式對應(yīng); ; (2)(2)使用使用Ak k對應(yīng)對應(yīng); ; (3)(3) 使用使用MPMP規(guī)則對

54、應(yīng)；規(guī)則對應(yīng)； (4)(4)使用使用UGUG規(guī)則對應(yīng)。規(guī)則對應(yīng)。 證明：證明： Q(c1, cm) A1 1=Q1 (c1, cm) An n=Qn (c1, cm) An n=Q (c1, cm) z1, , zn是在是在中不出現(xiàn)的不同變中不出現(xiàn)的不同變元，并且元，并且z1, zn y1, yn=。 A1 1=Q1 (z1, zm) An n=Qn (z1, zm) An n=Q (z1, zm) An+1= z1 znQ (z1, zm) An+2= z1 znQ (z1, zm) Q (y1, ym) An+3=Q (y1, ym)計(jì)算機(jī)學(xué)院76計(jì)算機(jī)學(xué)院76 x(P(x,y)Q(x,y

55、)(xP(x,y)xQ(x,y) ) x(P(x,c)Q(x,c)(xP(x,c)xQ(x,c) ) x(P(x,c)Q(x,c), xP(x,c) xQ(x,c) A1 1= = x(P(x,c)Q(x,c) A2 2= = P(x,c)Q(x,c) A3 3= = xP(x,c) A4 4= = P(x,c) A5 5= = Q(x,c) A6 6= = xQ(x,c)計(jì)算機(jī)學(xué)院77計(jì)算機(jī)學(xué)院77 若若 A(x)B(x)，則則 xA(x) x B(x) A1 1= =C1 Am m= = A(x)B(x) Am+1m+1= = x A(x)A(x) Am+2m+2= =xA(x)B(x)

56、Am+3m+3= =x( (xA(x)B(x) Am+4m+4= =x( (xA(x)B(x)(xA(x)xB(x) Am+5m+5= =xA(x)x B(x) 問題是什么問題是什么? ? X X是自由出現(xiàn)是自由出現(xiàn)計(jì)算機(jī)學(xué)院78計(jì)算機(jī)學(xué)院78主要內(nèi)容主要內(nèi)容 概述概述 命題邏輯公理系統(tǒng)命題邏輯公理系統(tǒng) 謂詞邏輯公理系統(tǒng)謂詞邏輯公理系統(tǒng) 公理系統(tǒng)性質(zhì)公理系統(tǒng)性質(zhì) 理論與模型理論與模型 判定問題判定問題 總結(jié)總結(jié)計(jì)算機(jī)學(xué)院79計(jì)算機(jī)學(xué)院79可靠性可靠性 可靠性定理：若可靠性定理：若 Q ，則，則 Q。 證明：設(shè)證明：設(shè)A A1 1,A,A2 2, ,A An n是是Q Q的從的從 的推演。歸納證

57、明：對于的推演。歸納證明：對于 Q i i ，有有 Q i i，i=1,2,i=1,2,n ,n n=1n=1時(shí)，若時(shí)，若Q i是公理，則是公理，則Q i是永真式。若是永真式。若Q i，則，則 Q i ， 有有 Q i i 公理模式公理模式A1v(Qv(Q (RQ) v(Q)(v(R)v(Q) 如果如果v(Q)=1，則v(Q)(v(R)v(Q)=1。 如果如果v(Q)=0，則v(Q)(v(R)v(Q)=1。 公理模式公理模式A2(P(P (QR) (PQ) (PR)同理同理v(Pv(P (QR) (PQ) (PR)=1)=1 公理模式公理模式A3( (Q R) (RQ)同理同理v(v(Q R)

58、 (RQ)=1)=1計(jì)算機(jī)學(xué)院80計(jì)算機(jī)學(xué)院80可靠性定理可靠性定理 若若Q i，則，則 Q i, , 對于對于v()=1， Ai有有v(Q i)=1，所以，所以 Q i 假設(shè)假設(shè)inin時(shí)定理成立時(shí)定理成立 證明證明i=ni=n時(shí)，時(shí)， 設(shè)設(shè)Q i由由Q j, , Q k用用MPMP規(guī)則推出，其中規(guī)則推出，其中j,kij,ki， Q k為為Q j Qi。 由歸納假設(shè)知，由歸納假設(shè)知， Qj且且 Qj Qi ， 所以所以 Qj， Qj Qi Qi 。 因此因此 Qn 即即 Q。計(jì)算機(jī)學(xué)院81計(jì)算機(jī)學(xué)院81協(xié)調(diào)協(xié)調(diào) 定義定義3.3 3.3 如果對于每個(gè)公式如果對于每個(gè)公式Q Q， Q Q，則，則

59、 稱不協(xié)調(diào)，稱不協(xié)調(diào)，否則稱否則稱 協(xié)調(diào)。協(xié)調(diào)。計(jì)算機(jī)學(xué)院82計(jì)算機(jī)學(xué)院82 定理定理3.3 3.3 若若 Q Q Q Q ，則，則 不協(xié)調(diào)。不協(xié)調(diào)。 證明：證明： Q Q Q Q即為公式即為公式 (Q QQ Q)A A1 1= = (Q QQ Q)A A2 2= = (Q QQ Q) (R (Q QQ Q) )A A3 3= =R (Q QQ Q) A A4 4= (= (R (Q QQ Q) (Q QQ Q) R )A A5 5= = (Q QQ Q) R A A6 6= = (Q QQ Q) A A7 7= = R R計(jì)算機(jī)學(xué)院83計(jì)算機(jī)學(xué)院83 定理定理3.4 3.4 若若 協(xié)調(diào)，則協(xié)

60、調(diào)，則 可滿足?？蓾M足。計(jì)算機(jī)學(xué)院84計(jì)算機(jī)學(xué)院84完備性定理完備性定理 完備性定理：若完備性定理：若 Q Q ，則，則 Q Q。 證明：證明： 若真值賦值若真值賦值v v滿足滿足 ，則它必滿足，則它必滿足Q ,Q ,即不可滿足即不可滿足 Q Q， 所以所以 Q Q 不可滿足。不可滿足。 因此，因此， Q Q 不協(xié)調(diào)。不協(xié)調(diào)。 所以有所以有 Q QQ Q。 有演繹定理有有演繹定理有 Q QQ Q。 由由( ( Q QQ)Q)Q Q，因此，因此，QQ計(jì)算機(jī)學(xué)院85計(jì)算機(jī)學(xué)院85可靠性定理可靠性定理(1 )(1 )公理公理1-31-3 可靠性定理：若可靠性定理：若 Q Q ，則，則 Q Q。 證明