大一各科課件-離散數(shù)理邏輯slide5-axiomsystem

數(shù)理邏輯-(3)邏輯公理系馬帥 3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) 歐幾里德（325BC-265BC），古希臘數(shù)學(xué)家《幾何原本》是把點(diǎn)、線、面、角等分為原始定義概念（23）和可義概念命題分為公理（5）、公設(shè)由公理公設(shè)出發(fā)加以證明的定理從簡(jiǎn)單到復(fù)雜，證明相當(dāng)嚴(yán)格。從而建立了歐幾得幾何學(xué)的第一公1．等于同量的2．等最3，等量減等量，其差仍相等4．彼此能重合的物體是全等的5．整體大于部

公1.由任意一點(diǎn)到另外任意2.一條有限3.以任意點(diǎn)為心及任意的4.凡直角都彼計(jì)算機(jī)學(xué) x(N(x)0≤x)x(N(x)y(N(y)x≤y))xy(N(x)N(y)x+yy+x)xy(N(x)N(y)x+y≤y)對(duì)象運(yùn)算關(guān)系計(jì)算機(jī)學(xué) 基本概念數(shù)數(shù)n的后繼n'1．0

3．沒有自然數(shù)n，使得n'等于04．對(duì)任意的自然數(shù)m和n，如果m’=n’，那么m=n，那么N包含每個(gè)自然計(jì)算機(jī)學(xué) 自然數(shù)公xy自然數(shù)公理是實(shí)質(zhì)公具體概念：后繼s()，0，+，自然數(shù)公理是所有的自然數(shù)命題真值的依從自然數(shù)公理能計(jì)算機(jī)學(xué) x(N(x)0≤x)x(N(x)y(N(y)x≤y))xy(N(x)N(y)x+y=y+x)是真xy(N(x)N(y)x+y≤y)x(I(x)0≤x)xy(I(x)y(I(y)x≤y)xy(y(I(x)I(yx+y=y+x)xy(I(x)I(y)x+y≤y))計(jì)算機(jī)學(xué) x(Q(x)R(c,x))x(Q(x)y(Q(y)R(x,y))xy(Q(x)Q(y)抽象：不同論 計(jì)算機(jī)學(xué) (1)各種初始符號(hào)。初始符號(hào)是一個(gè)形式系統(tǒng)的“字母”，經(jīng)解釋其中一部分是初始概念(2)形成規(guī)則。規(guī)定初始符號(hào)組成各種合適符號(hào)序列的規(guī)則。經(jīng)解釋(3)公理。把某些所要肯定的公式選出，作為推導(dǎo)其它所要肯定的公(4)變形規(guī)則應(yīng)用變形規(guī)則進(jìn)行推導(dǎo)可以得到一系列公式，這些公式經(jīng)過解釋是統(tǒng)的定理計(jì)算機(jī)學(xué) 公理從一些公理出發(fā)，根據(jù)演繹法，推導(dǎo)出一系列定理系叫作公理系統(tǒng)符號(hào)公式–公式是用于表達(dá)命題的符號(hào)串公理–公理是用于表達(dá)推理由之出發(fā)的初始肯定推理規(guī)則–推理規(guī)則是由公理及已證定理得出新定理定理–表達(dá)了肯定的所有命題計(jì)算機(jī)學(xué) 3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) 定義：命題邏輯的公理系統(tǒng)定義(1)1)命題變?cè)猀,Q2…,2)聯(lián)結(jié)詞3)括號(hào)：(2)形成規(guī)則(公式定義1若Q是命題變?cè)瑒tQ2)若Q是公式，則(Q)3)若Q,R是公式，則(QR)計(jì)算機(jī)學(xué) 命題邏輯公理系(3)公理：公理模式中P,Q,R為任意公1公理模式：R2公理模式A：(P(QR((PQ3公理模式：(QR(4)變形規(guī)則：推理規(guī)則(分離規(guī)則MP規(guī)則若Q和QR成立，則R成立。其中，Q和QR，R稱為結(jié)論計(jì)算機(jī)學(xué) 結(jié)詞符號(hào),,,可以認(rèn)為是縮寫公式，用≡表示縮(1)QR≡(2)QR≡(3)QR≡(QR)(4)QR≡計(jì)算機(jī)學(xué) (P(QR))((PQ)(P(QR))(QR)(P(QR))((PQ)(QR)(R

QQ計(jì)算機(jī)學(xué) 已知Q成立，證明R→Q成A1=QA2=A3=

A1推理序33計(jì)算機(jī)學(xué) 定義3.2設(shè)Γ是公式集Q

Γ稱為推演的前提集α1α2,αn，其AA (α每個(gè)αk(1)α是公理(2)α(3有ijkαkαiα由αα用MP規(guī)則推則稱它為Q的從Γ的一個(gè)推演(演繹記為Γ├Q

稱ααn為結(jié)推理序1推論如果Q是公QΓ，則Γ├計(jì)算機(jī)學(xué) 證明與定 則A1,A2,AnQ稱為Γ├Q的一個(gè)證明。計(jì)算機(jī)學(xué) {P,A1=A2=PA4=A5=A6=A7=

A2=A1A4A2A5=A4A6A6=計(jì)算機(jī)學(xué) ├(QR)A1=Q A2=(Q(RQ))((QR)(QQ))A2A3=(QR) 計(jì)算機(jī)學(xué) Q(QR)(涵義A1=A2=(RQ)A3=((RQ)(Q→R))(Q((RQ)A4=Q((RQ)A5=(Q((RQ)(Q→R)))((Q(RQ))(QA6=(Q(RQ))(QA7=Q

A2A3├A2A4A5├1A6├計(jì)算機(jī)學(xué) Γ{Q}R當(dāng)且僅當(dāng)Γ1Γ{Q}R成立，證明Γ(1.1)歸納基礎(chǔ)：用關(guān)于Γ{Q}到R的推演長(zhǎng)度n當(dāng)n=1時(shí)，R或?yàn)楣?，或?qū)儆讦＃騌是QA2=A3=所以├QR，從而Γ├若R=Q，則Q所以Γ├

若RΓA2=A3=有Γ計(jì)算機(jī)學(xué) (1.2)歸納假設(shè)：假設(shè)Γ{Q}到R的推演長(zhǎng)度小于n(1.3)歸納證明：當(dāng)Γ{Q}到R的推演長(zhǎng)度等于nΓ{Q}Ai=

因?yàn)閕,j<n,有所Γ{Q}├Γ├Γ{Q}├Γ├Q

Am=Ak=QAk+1=Q((QP)(Q

=(QP)(QAk+3=(Q計(jì)算機(jī)學(xué) 由ΓQR可知，有推理序列A1A2,……Am，使得Am=QR。證明有Γ{Q}R。因有推理序列A1A2,……Am，其Am=Am+1=Am+2=計(jì)算機(jī)學(xué) 證明PQ├P{P,Q,(PQ)}├Q，{P,Q,(PQ)}├123(P4(PQ)(P5P6所以有P,Q├(PQ)，即P,QP

AA2A3├QA4=A3A5=A1計(jì)算機(jī)學(xué) 證明PQ(PR(PQ演繹定理：(PQ)(PR，PQ1(PQ)23=(PQ)(PR)(456(PQ)(PR)(7=910Q

AA├QRA3=A1AA4=A2├QRA6=A1AA7=A2A計(jì)算機(jī)學(xué) 如果{ΓQ}├RΓQ}├R,則Γ├1Q2Q3(QR)(RQ456(Q7

Γ{Q}├RΓ├Γ{Q}├RΓ├A3A3=A2AA,A4├(QA6=A5計(jì)算機(jī)學(xué) 如果{ΓQ}├RΓQ}├R，則Γ1Q2Q3(QR)(45Q67Q8(9

Γ{Q}├RΓ├Γ{Q}├RΓ├├(QR)(A3=A1AA,A├A,A├(QA8=A7計(jì)算機(jī)學(xué) 定理：若Γ├R，則Γ├QRAk-1=Ck-Ak+1=RAk+2=

Ak+1=Ak定理：若ΓPQΓP(QR，則Γ├PRAm-1=Dm-Am=Am+n-1=Dm+n-Am+n=PAm+n+1=(P→(Q→R))→((P→Q)Am+n+2=(P→Q)

Γ├Γ├P3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) (1) 變?cè)簒,x 常元：,c3)函詞符號(hào)：f1,f1,......；f2,f 4)謂詞符號(hào)1,Q1,......；Q2,Q 5)運(yùn)算符號(hào)：,67

號(hào)：號(hào)：計(jì)算機(jī)學(xué) (2) k3若是t…t項(xiàng)，則是fn(t,…t)k(3)1)若是t,,n項(xiàng)，則Qkn(t,…t)2)若Q是公式，則(Q)是公3)若Q和R是公式，則(QR)4)若Q是公式，則(xQ)計(jì)算機(jī)學(xué) (4)公理集合1理模式A1：Q2理模式A2：(P(QR((PQ3A3：(QR5).公理模式A5：x(QR(x(QxR(x))，其中x不(5)推理規(guī)1)分離規(guī)則（簡(jiǎn)稱MP規(guī)則）：從Q和QR推出R2)概括規(guī)則（簡(jiǎn)稱UG規(guī)則）：從Q(x)推出(xQ計(jì)算機(jī)學(xué) ,,,(2).QR≡(3).QR≡(QR)(4).QR≡xQ(x)計(jì)算機(jī)學(xué) 定義設(shè)Γ是合式公式集Q是合式式序列α1α2,αn，其中A1AA (α每個(gè)αk(1)α是公(2)α(3有i,j<kαkαiα由αiα用MP規(guī)推出(4)有i<j使Aj=xAi由用UG規(guī)則推則稱它為Q的從Γ的一個(gè)推演(繹),記為Γ├Q

序列從演繹出證明?？勺C明α。推理序1如果Q是公理或Γ，則Γ├計(jì)算機(jī)學(xué) 定義：如果├Q，則Q計(jì)算機(jī)學(xué) ={證明1P(x)23

Q計(jì)算機(jī)學(xué) xQ(xyQ(y)(y不在Q證明A1=xQ(x) AA2=y(xQ(x) A3=y(xQ(x)Q(y))(xQ(x)y AA4=xQ(x)y A3=A2計(jì)算機(jī)學(xué) Γ{A}├B當(dāng)且僅當(dāng)Γ├式，A可證，xA可證？？

約束變自由約束出自由出計(jì)算機(jī)學(xué) Γ{A}├B，且A為閉公式(語(yǔ)句)，當(dāng)且僅當(dāng)Γ├歸納基礎(chǔ)：用關(guān)于Γ{A}到B的推演長(zhǎng)度n當(dāng)n=1時(shí)，B或?yàn)楣?，或?qū)儆讦?，或B是AA2A3–所以├AB，從而Γ├若BΓA2A3–有Γ├

若B=AA所以Γ├計(jì)算機(jī)學(xué) 歸納假設(shè)：假設(shè)Γ{A}到B的推演長(zhǎng)度小于n定理成 Γ{A} A ? ?

因?yàn)閕,j<nΓ{A}├Γ├

從ΓAAmAAAnAi=AjR

Γ{A}├Γ├A

1=((RB))R)(AAk+=AR)(AA+計(jì)算機(jī)學(xué) Γ{A}

因?yàn)棣A}├R推演 從Γ的推An-2=

長(zhǎng)度等于n-1Γ├

AAmA–Am+1=x(ARAn-1=xR=

AmAA為閉計(jì)算機(jī)學(xué) Γ到AB的推由Γ├AB可知，有推理序列A,A2m使得AB證明有Γ{A}├B。因AAAmAmAm計(jì)算機(jī)學(xué) 定理：├x(Q(x)R(x))(xQ(x)僅需證x(Q(x)R(x))├xQ(x)xR(x)。設(shè)Γ={x(Q(x)R(x))A1A2x(Q(x)R(x))A3A4Q(x)R(x)A5A6A7Q(x)R(x)A8A9A10

AA2=A1A4=A3AA7=A3A├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)計(jì)算機(jī)學(xué) 定理設(shè)c1,…cm是在Γ語(yǔ)句集中不出現(xiàn)的不同?！?ym是在公式Q(c1,…,cm)中不出現(xiàn)的不同變?cè)?，用…ym分別同時(shí)代替Q(c1,…cm)中的c1…cm得Q(y1,…ym。若ΓQ(c1,…cm)，則ΓQ(y1,…ym)Γ├Q(c1,…,A1Q(c1,…,…AnQ(c1,…,Q 驟~：(2)使用AkΓ對(duì)應(yīng)(3)使用MP(4)使用UG

z1,…,zn是在Γ元，并且{z1,…,zn}{y1,…,yn}=A1Q(z1,…,…An(z1,…,An(z1,…,An+1=z1…znQ(z1,…,An+2=z1…znQ(z1,…,Q(y1,…,An+3=Q(y1,…,x(P(x,c)→Q(x,c)),xP(x,c)├12=3456若ΓA(x)B(x)，則ΓxA(xxmm+x

問題是什么X是自由Am+5=xA(x)x3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) ：Q,QR反證律：如果ΓQRΓQ├R,則Γ歸謬律：如果ΓQRΓQ├R，則Γ計(jì)算機(jī)學(xué) ├(P(QR))├├QQ

├├├(QR├Q(Q├(QR)├(QR)(Q計(jì)算機(jī)學(xué) ├Q((QR)├├(PQ)((QR)(P├(QR)((QR)├(QR)((QR)├(QRR)├(PQR)(P(Q├├(PQ)(PR)(PQ├(PR)((QR)((PQ)計(jì)算機(jī)學(xué) Q,QRA1=A2=A3=

A1ΓA2ΓA1,A2計(jì)算機(jī)學(xué) PQ,A1=(QR)(PA3=PA4=(P(QR))((PQ)A5=(PQ)

A2ΓA1=A2A3A2A4,A3A5A6ΓA5,計(jì)算機(jī)學(xué) 例 證明A1=((QR))((PQ)(P AA2((PQ)(PR))(Q((PQ)(P AA3=(Q((PQ)(PR)))((Q(PQ))(Q(P AA4(P(QR))((Q(PQ))(Q(PA5=((((QR))((Q(PQ))(Q(P

A1A2A3(((P(QR))(Q(PQ)))(((P(QR))(Q(P AA6=((((QR))(Q(PQ)))((P(QR))(Q(PR)))A5=A4A7A8(Q(PQ))((P(QR))(Q(PA9(P(QR))(Q(PA10((QR))(Q(P

AAA8A├A6A├計(jì)算機(jī)學(xué) 例 證明├(QR)((PQA1=(QR)(P(QA2=(P(QR))((PQ)(PA3=(QR)((PQ)(P

A2A1,A2├計(jì)算機(jī)學(xué) 例 證明A1=(QR)((PQ)├(QR)((PQ(PR(例A2=((QR)((PQ)P(QR (例A3=((P A2,A1├計(jì)算機(jī)學(xué) 證明P(QR),A1=A2=(P(QR))((PQ)A3=(PQ)(PRA4=Q(PA6=A7=P

A1A2A2A├A5A4A├6A3A├計(jì)算機(jī)學(xué) A1=((PQ)(PR))(Q((P A2= A2A3=Q(P A4=(Q((PP(QR),Q├PR(例A5=((PQ)(PR))A6=(Q(PR))

A1,A4├(P(QR))├(Q(PR))(例A7=((PQ)(PR))(P A5,A6├計(jì)算機(jī)學(xué) 證明A1=(Q A2A2=Q((QQ) A3=(Q(QQ))A4=Q

1A2├3，├計(jì)算機(jī)學(xué) 證明A1=QA2=(QQ)A3=(QQ)A4=QA5=(Q((QQ)(QA6=(QQ)(QA7=(QA8=Q

A1,A2,A3├A2A5A4├├QQ(例A6A7├計(jì)算機(jī)學(xué) 證明QA1=A2=A3=

├QQ(例A1A1├計(jì)算機(jī)學(xué) A1=(QR) A2=(RQ) 計(jì)算機(jī)學(xué) A

QQ(例AAA├ AAAQA7=(QQ)((QR)(Q

AA├├QQ(例A8=(QR)(Q

├(PQ)((QR)(PR))(例AA6AA計(jì)算機(jī)學(xué) 證明├(QR(RA1A2(QR)(RA3(QR)(R

├(QR)(QR)(例A2A├計(jì)算機(jī)學(xué) 證明├(QR12

├(QR(RQ)(例QQ(例3(Q├(QR)((PQ)(PR))(例45(QR)

A3A├A1,A4├計(jì)算機(jī)學(xué) 證明├(QRA1(QR A2(QQ)((QR)(QR├(PQ)((QR)(PR))(例A3(QA4(QR)(QRA5(QR)

QQR(例A2AA4,A1├計(jì)算機(jī)學(xué) 證明A1A3=QA5=QQ)(QA6(QR)

A1├A2A4A3AA5├計(jì)算機(jī)學(xué) ├(QQ)(RQ)(例(((QQ)(QQ)) A(QQ)(QQ)

AAAAA計(jì)算機(jī)學(xué) 證明QQA1=QQA2=(QQ)A3=QQ

QR├(QQ)Q(例AA計(jì)算機(jī)學(xué) 證明A2=(QQ)(QA3=(QA4=

QQ(例├QQ(例A2A1QR≡(Q計(jì)算機(jī)學(xué) 證明A1=QA2=

QQ(例QR≡Q計(jì)算機(jī)學(xué) Q(QA1Q(RA2(RQ)(QA3Q(Q

A1,A2├計(jì)算機(jī)學(xué) A1A2(RQ)A3QA4A5A6(Q(QR))((QR)A7

├Q(QR)(例A4,A3├├(QR)A5,A6├A8(QR)(RA9

├(P(QR(Q(PR(例QR≡Q計(jì)算機(jī)學(xué) 證明├(QR)(QA1R(QA3Q(R(QA4(R(QR))((QA5Q((QR)

A2,A1├├(QR)(RA3,A4├A6(Q((QR)R((QR)(Q (例A7(QR)(QA8(QR)(Q

A6,A5├QR≡Q計(jì)算機(jī)學(xué) 證明├Q((QR) ├QQ(例├(P(QR))(Q(PR))(例A3 A2A├計(jì)算機(jī)學(xué) 證明A1A2

QQ(例├(P(QR))(Q(PR))(例A3((QR)R)(RA4

├(QR)AAA5A6(Q(QR))

A4;├(P(QR))(QA5;├(QR)QR≡(Q計(jì)算機(jī)學(xué) 證明├(QR)((QR)1(QQ QQQ)(例A2=((RQ)(QQ))((RQ)1├(QR((PQ(PR))(例A3=((QR)((RQ)(QQ)))((QR)((RQ)2├(QR)((PQ)(P4=(QR)((RQ)A5=(QR)((RQ)

├(PQ)((QR)(PA3A├6=(RQ)((QR)7=(QR)8=(QR)((QR)9(QR)((QR)

5├(P(QR))(Q(PR)(例AA7├8├(P(QR))計(jì)算機(jī)學(xué) 證明├(QR)((QR)1(QQ)A2=(QQ)

QQQ(例├(QR)3

AA4((RQ)(QQ))((RQ)3├(QR((PQ(PR(例5((QR)((RQ)(QQ)((QR)((RQ) 4├(QR)((PQ)(P6(QR)((RQ)(QQ)7(QR)((RQ)8(RQ)9(QR)10(QR)11(QR)

├(PQ((QR(PR(例A5=A65├(P(QR(Q(PR(例├(QR)AA810├(P(QR))(Q計(jì)算機(jī)學(xué) 證明├(QRR1(Q(RR))((R2=A3=(Q(RR))4(QRR)

├(QR)├QQ(例P(QR),QPR(例QR≡(Q計(jì)算機(jī)學(xué) 證明A1=A2=

計(jì)算機(jī)學(xué) 證明QRA1=(RQ)(QA2=((RQ)(Q3

├(RQ)(Q├(RQ)(QR)QR=(QR)4QR計(jì)算機(jī)學(xué) 證明123A4=(Q(QR))((Q5(Q6QR

A1├AAQR計(jì)算機(jī)學(xué) 證明├(QA1=(QA2=(QQ)(QA3=(QA4=(Q

QQ(例QQ(例AAQR≡計(jì)算機(jī)學(xué) 證明├(PQR(P(QA1=(PQR)(R(PQA2=(R(PQ))(R(PA3=(PQ)(PA4=(R(PQ))(R(P

├(QR)(RQR≡QQ(例A3;├(QR)((PQ)(PR))(例A5=(R(PQ))(P(R(P(QR))(Q(PR))(例A6=(RQ) A7=((RQ)(QR))((P(R(QR)((PQ)(PR))(例A8=(P(RA9=(PQR)

A6├A1A,A,A,A計(jì)算機(jī)學(xué) A1(QR(Q ├QQ(例A2=((QR)(QR))(Q((QR)A3=Q((QR)

├(P(QR))(Q(PR))(例A,AA4=((QR)A5=Q(R(QA6=

├(QR)(RA,AQR≡計(jì)算機(jī)學(xué) 證明A1=(RQ)(Q

├(RQ)(QA2=((RQ)(QR))((QR)├(QR)A3=(QR)A4=

A,AQR≡計(jì)算機(jī)學(xué) 證明A1=A2=A3=A4=(Q(QR))A5=A6=

├A,A├A,AQR≡計(jì)算機(jī)學(xué) 證明PQ(PR(PQA1=(P(QR))((Q A2=((PQ)(PR))(P(QQR≡計(jì)算機(jī)學(xué) ├xR(x)├xR(x)├Q(c)├Q(c)├xR(x)

├xyR(x,y)├xyR(x,y)├xyR(x,y)├xyR(x,y)├xR(x,x)├x(P(x)Q(x))(xP(x)├x(P(x)Q(x))(xP(x)├x(P(x)Q(x))(xP(x)├xP(x)xQ(x))x(P(x)├x(P(x)Q(x))(xP(x)├x(P(x)Q(x))(xP(x)計(jì)算機(jī)學(xué) ├xP(x)├xP(x)├xP(x)├xP(x)計(jì)算機(jī)學(xué) 選擇規(guī)引入規(guī)P(c)計(jì)算機(jī)學(xué) 證明xQ(xyQ(y)(y不在QA1=xQ(x)A2=y(xQ(x)A3=y(xQ(x)Q(y))(xQ(x)yA4=xQ(x)y

A4A5A,A計(jì)算機(jī)學(xué) xR(xyR(y(y不在QA ├xQ(x)yQ(y)（例A2=(yQ(y)xQ(x))(xQ(x)├(QR)(RA(xQ(x)AxR(x)

AAxQ(x)計(jì)算機(jī)學(xué) 證明├Q(cA1=xQ(x) AA2=(xQ(x)Q(c))(Q(c)├(QR)A3=Q(c)A4Q(c)A5Q(c)A

A,A2QQ(例A,AxQ(x)計(jì)算機(jī)學(xué) AA2=(xQ(x)Q(c))(Q(c)├(QR)(RA3=Q(c)

A,A計(jì)算機(jī)學(xué) A1xQ(x)A2Q(c)A3xQ(x)

AQ(cxQ(x)(例A,A計(jì)算機(jī)學(xué) 證明├xyA1=xyR(x,y)yA2=yA3=xyR(x,y)A4=x(xyR(x,y)

AAA,AA5=x(xyR(x,y)R(x,y))(xyR(x,y) AA6=xyR(x,y)A7=y(xyR(x,y)

AAA8=y(xyR(x,y)xR(x,y))(xyR(x,y)yxR(x,y))AA9=(xy AA計(jì)算機(jī)學(xué) xyR(x,yAyx├xyR(x,y)yxR(x,y)(例AxyR(x,y)A;├(QR)(RAxyR(x,y)xQ(x)AxyR(x,y)xQ(x)計(jì)算機(jī)學(xué) xyR(x,yyxAxyR(x,y)AyR(c,y)AR(c,y)AxyR(x,y)xA

AAQ(c)xQ(x)(例38)A1AA3A6=y())A5A7=xyR(x,y) A計(jì)算機(jī)學(xué) 證明A2=yR(x,y)A3=xyR(x,y)

AAA,AA6 A,A5計(jì)算機(jī)學(xué) xR(x,xA1A2xR(x,x)A3xR(x,x)A4xyR(x,y)A5xyR(x,y)xA6xR(x,x)x

A├(QR)(RA3A4計(jì)算機(jī)學(xué) 證明├x(P(x)Q(x))(xP(x)xA1 AA2=(P(x)Q(x))((xP(x)P(x))(xP(x)├(QR)((PQ)(PR))(例A3(x(P(x)Q(x))((xP(x)P(x))(xP(x)A,A4A5(x(P(x)Q(x))(xP(x)A6=x((x(P(x)Q(x))(xP(x)A7x(P(x)Q(x))x(xP(x)

A(P(QRQPR(例AA8=x(xP(x)Q(x))(xP(x)xA9=x(P(x)Q(x))(xP(x)x

AA,計(jì)算機(jī)學(xué) x(P(xQ(x(xP(xAx(P(x)Q(x))(P(x)A2=

A├Q(c)xQ(x)(例A3=(Q(x)xQ(x))((P(x)Q(x))(P(x)

))A(P(x)Q(x))(P(x)A(P(x)xQ(x))(xAx(P(x)Q(x))A7=x(x(P(x)Q(x))(x

A,AA,A8=x(x(P(x)Q(x))(xQ(x)P(x)))((x(P(x)Q(x))x(xA(x(P(x)Q(x))x(x AAx(xQ(x)P(x))(xQ(x)xA(xQ(x)xP(x))(xP(x)xA12=(xP(x)xQ(x))(xP(x)xA13(x(P(x)Q(x))(xP(x)x A9,A10A11,計(jì)算機(jī)學(xué) 證明xP(x)xQ(xx(P(x)1(xP(x)xQ(x))23=(xP(x)xQ(x))4(xP(x)xQ(x))5=xQ(x)6(xP(x)xQ(x))7(xP(x)xQ(x))P(x)A8=x((xP(x)xQ(x))P(x)9x((xP(x)xQ(x))P(x)

├QRQ(例AA,├QRAA,├((PQ)(PR))(PQR)(例(xP(x)xQ(x))x(P(x) A10(xP(x)xQ(x))x(P(x)

A,A9├計(jì)算機(jī)學(xué) 證明A1xP(x) AA2xQ(x) AA3=(xP(x)xQ(x))(P(x)

PQ,RT├PRA4=x((xP(x)xQ(x))(P(x) A5=x((xP(x)xQ(x))(P(x)Q(x)))xQ(x))x(P(x)A6(xP(x)xQ(x))x(P(x) A,A計(jì)算機(jī)學(xué) 證明x(P(xQ(x(xP(xA1(xP(x)xQ(x))xP(x (例A2x(P(x)Q(x))(xP(x) A3x(P(x)Q(x))(xP(x)xQ(x))A4x(P(x)Q(x))(xP(x)A5(xP(x)xQ(x))(xP(x)A6x(P(x)Q(x))(xP(x)

(例A,A計(jì)算機(jī)學(xué) 證明├x(P(x)Q(x))(xP(x)1=xP(x) A2xQ(x) A3=xP(x)xQ(x)P(x)4P(x)Q(x)(P(x)5xP(x)xQ(x)(P(x)

PQ,RT├PRA3├6=(xP(x)xQ(x))xP(x)7(xP(x)xQ(x))(P(x)8(xP(x)xQ(x))(P(x)9=x((xP(x)xQ(x))(P(x)10(xP(x)xQ(x))x(P(x)

A6├A4A11=x(P(x)Q(x))(xP(x)1=x(P(x)Q(x))(xP(x)

├(QR)(R計(jì)算機(jī)學(xué) 3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) 可靠性定理：若ΓQ，則ΓQ證明：設(shè)QΓ├Qi，有Γ╞Q，1.n=1時(shí)，若Q是公理，則Q是永真式。若Q，則├Qi，有Γ╞Qi公理模式–v(Q–––公理模式–(P(QR))((PQ)–同理v((P(QR))((PQ)公理模式–(QR)–同理v((QR)計(jì)算機(jī)學(xué) 若QiΓ，則ΓQ對(duì)于v(Γ)=1，AiΓ有v(Qi)=1，所Γ╞Q2.假設(shè)i<n3.證明i=n設(shè)Qi由QjQk用MP規(guī)則推出，其中j,k<iQk為Qj→Qi由歸納假設(shè)知ΓQjΓQjQi,所以ΓQjΓQjQi由ΓQj,ΓQjQi,所以Γ╞Qi因此當(dāng)i=n時(shí)成即ΓQ計(jì)算機(jī)學(xué) 定義3.3如果對(duì)于每個(gè)公式Q，ΓQ，則Γ稱不協(xié)調(diào)，否計(jì)算機(jī)學(xué) 定理3.3若ΓQQ，則Γ證明：Q∧Q等價(jià)于A1=A2=(QQ)(R(QQ)A3=RA4(R(QQ))((QQ)RA5(QQ)A6A7Γ├R（R為任意公式定理3.4若Γ協(xié)調(diào)，則?？蓾M足完備性定理：若ΓQΓQ證明若真值賦值v滿足Γ，則它必滿足Q,即不可滿足所以Γ{Q}不可滿因此，Γ{Q}不協(xié)調(diào)所以有Γ{Q}├Q有演繹定理有Γ├QQ由├(QQ)Q計(jì)算機(jī)學(xué) 可靠性定理：若Γ├Q，則Γ╞Q歸納證明：對(duì)于Γ├Qi，有Γ╞Qi，1n=1時(shí)，即Qi是公理，則Qi(1)公理模式–v(Q–如果v(Q)=1，則v(Q)(v(R)v(Q))=1–如果v(Q)=0，則v(A)(v(R)v(Q))=1(2)公理模式–(P(QR))((PQ)–同理v((P(QR((PQ(3)公理模式–(QR)–同理v((QR)計(jì)算機(jī)學(xué) (4Qi4xQQtx。–任取解釋I和賦值t–若I(xQ)(v)=1，則對(duì)于每個(gè)–所以I(Qtx–這表明Qi是永真式，即Γ╞Qi計(jì)算機(jī)學(xué) 可靠性定理(3)—公理(5)設(shè)A是公理5x(QR)(QxR)。其中x是公式Q的自由–若I(xQR)則I(xQR)(Q–若(xQR))(v)=1，且I(Q)(v)=0，所以I(xQR)(Q–若(x(QR))(v)=1，且則對(duì)于任意dD，I(x(QR))(v[x/d])=1因?yàn)镮(Q)(v)=1，所以I(R)(v[x/d])=1。從而I(xR)(v)=1，因此有I(x(QR)計(jì)算機(jī)學(xué) 可靠性定理(4)—MP規(guī) –Γ╞假設(shè)i<n證明i=n,其中j,<k為→–由歸納假設(shè)知，ΓQ且Γ├Qj所以ΓQjΓQj→ΓQ–因此Γ╞即Γ計(jì)算機(jī)學(xué) (7)證明i=n–設(shè)Q由k用UG規(guī)則推出，其中k<i，–由歸納假設(shè)知，ΓQk所以ΓQ–因?yàn)镼i=xQk，對(duì)于任意所以，I(xQk–因此Γ╞即Γ╞QUG規(guī)則：If├P(x),then計(jì)算機(jī)學(xué) 如定理3.12若Γ├P(x)∧P(x)，則Γ不協(xié)若計(jì)算機(jī)學(xué) 若Γ╞Q，則Γ├證明所以Γ{Q}不協(xié)調(diào)，即Γ├Q又因?yàn)椹?QQ)所以Γ├

推論若╞Q計(jì)算機(jī)學(xué) 若Γ╞Q，則Γ├證設(shè)R是QΓ{R}├R。由演繹定理知，ΓRR，因?yàn)椹?RR)R，故Γ├R，因此，Γ├Q。計(jì)算機(jī)學(xué) (t12)…t11=t21…可靠性定若ΓQΓ完備性定若Γ╞Q，則Γ├計(jì)算機(jī)學(xué) 3.1邏輯公理系3.2命題邏輯公理系3.3謂詞邏輯公理系3.4定理證3.5公理系統(tǒng)性3.6理論與模3.7判定問計(jì)算機(jī)學(xué) (1).x(Q(x)(2).x(Q(x)y(Q(y)(3).xy(Q(x)Q(y)(4).xy(Q(x)Q(y)計(jì)算機(jī)學(xué) 定義：對(duì)于任意ε>0，存在N>0，對(duì)于任何n，當(dāng)n>N，都有|nb|<ε，則稱序列xn的極限是b，記limxn序列極限的形式表ε(ε>0N(N>0n(n>N|xn-|<limf(x)ε(ε>0δ(δ>0x(|x-x0|<δ|f(x)-計(jì)算機(jī)學(xué) 定理1若序列的極限存在，則極限值唯ε(ε>0N1(N1>0n(n>N1|xn-計(jì)算機(jī)學(xué) 證明S1=ε(ε>0N1(N1>0n(n>N1|xn-S2=a)/2S3=(ε0>0N1(N1>0n(n>N1|xn-S4=N1(N1>0n(n>N1|xn-))S5=N'1>0n(n>N'1|xn-S6n(n>N'1|xn-S7n>N'1|xn-S8=ε(ε>0N2(N2>0n(n>N2|xn-S9n>N'2|xn-S10=NmaN''S11n>Nn>S12n>Nn>S13n>N|xn-S14n>N|xn-εS15n>S16|nS17|nS18n<a+ε(取xb>S19xnS20S21=+)<S22(xnb2若序列{}有極限，則{nε(ε>0N(N>0n(n>N|xn-S1=ε(ε>0