數(shù)理邏輯-命題演算

數(shù)理邏輯

MathematicalLogic緒論

“邏輯”一詞來源于希臘字

oyez(羅各斯，英語logic)音譯。原意指思維。邏輯是以思維作為研究對象的，是研究人類思維及其規(guī)律的一門科學(xué)。邏輯的發(fā)源地、代表人物、代表作古希臘亞里士多德（邏輯之父）其代表著作《工具論》(十篇)中提出了(形式)邏輯的雛形,形成了邏輯這門古老的科學(xué)。古代中國墨子《墨經(jīng)》古印度“因明學(xué)”《正理經(jīng)》注.

亞里士多德(Aristoteles，公元前384-322年):古希臘哲學(xué)家.西方三圣之一.另兩位是蘇格拉底(Socrates，公元前469-399年)和柏拉圖(Platon，公元前427-347年).

墨子(公元前468-376年,一說公元前476-390年,又一說公元前480-400年;魯國人，有的說是宋國人

)

:春秋末戰(zhàn)國初時期的思想家、學(xué)者，墨家學(xué)派的創(chuàng)始人.2邏輯：形式邏輯：(formallogic)形式邏輯也稱為初等邏輯。它研究思維的(邏輯)形式結(jié)構(gòu)和(邏輯)規(guī)律，而不管思維的的具體內(nèi)容。形式邏輯只管形式，從錯誤的前提推出錯誤的結(jié)論，在形式上也可以是正確的。

——毛澤東在延安文藝座談會上的講話緒論3緒論

形式邏輯：

演繹邏輯：(deductivelogic)演繹邏輯的任務(wù)在于研究如何檢驗(yàn)演繹的正確性(即決定一個推理是否是正確地演繹出一個已知規(guī)則)以及如何構(gòu)造出正確的未知(演繹推理)規(guī)則。

歸納邏輯：(inductivelogic)歸納邏輯的任務(wù)在于研究如何測定不充分置信的推理的歸納概率的大小，從而決定該不充分置信推理的歸納強(qiáng)度規(guī)則，并且研究如何構(gòu)造出歸納強(qiáng)度高的推理規(guī)則。4緒論辯證邏輯：(dialecticallogic)

也稱為高等邏輯。它是研究人類的辯證思維及其規(guī)律的科學(xué)。辯證邏輯結(jié)合思維的具體內(nèi)容來研究思維形式的辯證規(guī)律。

形式邏輯和辯證邏輯都是從定性的角度來研究思維規(guī)律的。

西方哲學(xué)指導(dǎo)思想：西方哲學(xué)指導(dǎo)思想＝形式邏輯＋一切通過實(shí)驗(yàn)找因果關(guān)系愛因斯坦在1935給加里福尼亞的朋友舒衛(wèi)特的信中說：歐洲現(xiàn)代科學(xué)技術(shù)是偉大的，它之所以偉大，是因?yàn)楫?dāng)時它們是在一種指導(dǎo)思想下產(chǎn)生的。這個指導(dǎo)思想是什么呢？是古希臘的哲學(xué)，即形式邏輯體系和文藝復(fù)興時代的一切通過實(shí)驗(yàn)找它的因果關(guān)系的思想。因?yàn)橛羞@樣的哲學(xué)指導(dǎo)思想，所以才產(chǎn)生了近代的科學(xué)體系。

5緒論數(shù)學(xué)方法：引進(jìn)一套符號體系，用以建立一類數(shù)學(xué)符號語言(形式語言)，以其作為思維的載體，進(jìn)而建立起邏輯的各種形式系統(tǒng)，從而來研究思維及其規(guī)律的方法。數(shù)理邏輯是從定量的角度來研究思維規(guī)律的。西方公認(rèn)的數(shù)理邏輯創(chuàng)始人是十七世紀(jì)德國的萊布尼茨(Leibniz，公元1646-1716年)，他力圖建立一種精確的普遍語言，并尋求一種推理演算，以便用來解決論辯的爭論問題。數(shù)理邏輯在十九世紀(jì)興起，二十世紀(jì)得到飛躍式的發(fā)展。

數(shù)理邏輯：(mathematicallogic)數(shù)理邏輯也稱為符號邏輯。它是用數(shù)學(xué)的方法來研究形式邏輯(主要是演繹邏輯)，即研究演繹推理的規(guī)律的科學(xué)。數(shù)理邏輯是現(xiàn)代的形式邏輯。6緒論數(shù)理邏輯：經(jīng)典邏輯：現(xiàn)代邏輯：7第一章命題演算

§1.命題聯(lián)結(jié)詞命題函數(shù)§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)§3.初始符號形成規(guī)則合式公式賦值真值表§4.可滿足性有效性邏輯推論邏輯等價(jià)替換定理代入定理對偶定理§5.聯(lián)結(jié)詞歸約范式(NF)

§6.命題演算的形式推理8§1.命題聯(lián)結(jié)詞命題函數(shù)每給出一個命題,就要求作出一次判斷。在形式邏輯中,命題有時也稱為判斷。命題的真假取決于它是否如實(shí)地反映事物的真實(shí)情況,是否與事物的真實(shí)情況相符。如實(shí)反映事物的真實(shí)情況,與事物的真實(shí)情況相符,就是真命題;否則,就是假命題。真命題用t(true)來表示;假命題用f(false)來表示;t和f共稱為命題的真值(truth)。命題是命題邏輯推理的基本要素！1.命題(proposition)：命題是可辨真假的陳述語句。92.簡單命題(simpleproposition)：不包含其它命題作為組成部分的命題。

§1.命題聯(lián)結(jié)詞命題函數(shù)

3.復(fù)合命題(compoundproposition)：包含其它命題作為組成部分，由其它命題組成的命題。4.支命題(branchproposition)：支命題是組成復(fù)合命題的各個命題。支命題可以是簡單命題，也可以是復(fù)合命題。簡單命題是命題邏輯推理的最小單位！10例1.(1)中國人民是偉大的。(2)雪是藍(lán)的。(3)1+101=110。(4)全體立正!(5)明天是否開大會?(6)天氣多好啊!

(7)我正在說謊。

(8)北京是中華人民共和國的首都。(9)3是素?cái)?shù)。

(10)大于3?！?.命題聯(lián)結(jié)詞命題函數(shù)例2.(1)別的星球上有類人的高級生命。

(2)在的小數(shù)展式中，數(shù)串‘12345’將出現(xiàn)偶數(shù)次。115.聯(lián)結(jié)詞(connective)：將支命題聯(lián)結(jié)起來構(gòu)成復(fù)合命題的詞項(xiàng)稱為聯(lián)結(jié)詞。一個復(fù)合命題由支命題、以及聯(lián)結(jié)它們的聯(lián)結(jié)詞構(gòu)成。復(fù)合命題的真假依賴于構(gòu)成它的各支命題的真假、以及所用的聯(lián)結(jié)詞的種類。

§1.命題聯(lián)結(jié)詞命題函數(shù)例3.(1)并非所有的人都是好人。(2)2是偶數(shù)并且是最小的素?cái)?shù)。

(3)未來戰(zhàn)爭是常規(guī)戰(zhàn)爭，或者是核戰(zhàn)爭。(4)如果a2能被2整除，則a能被2整除。(5)a是完全平方數(shù)當(dāng)且僅當(dāng)它的素?cái)?shù)分解式中各指數(shù)均是偶數(shù)。(6)我學(xué)英語,或者我學(xué)日語。(7)如果天氣好,那么我去散步。12例5.(1)a能被2整除。(2)a2能被2整除。

(3)a是完全平方數(shù)。

(4)a的素?cái)?shù)分解式中各指數(shù)均是偶數(shù)。

(5)x大于3?！?.命題聯(lián)結(jié)詞命題函數(shù)6.命題函數(shù)(propositionalfunction)：含有未知因素的具有命題形式的陳述語句。

命題函數(shù)不是命題，不能確定真假。137.命題函數(shù)轉(zhuǎn)化為命題的方法：§1.命題聯(lián)結(jié)詞命題函數(shù)例6.(1)大于3。(2)如果a2能被2整除，則a能被2整除。(3)a是完全平方數(shù)當(dāng)且僅當(dāng)它的素?cái)?shù)分解式中各指數(shù)均是偶數(shù)。(4)對于所有實(shí)數(shù)x，x大于3。(5)存在著實(shí)數(shù)x，x大于3。14§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)1.真值聯(lián)結(jié)詞(truthconnective)：在命題邏輯中所使用的、意義比較嚴(yán)格的聯(lián)結(jié)詞稱為真值聯(lián)結(jié)詞或命題聯(lián)結(jié)詞。

2.命題的形式化

：使用數(shù)學(xué)符號來表示一個命題中的簡單命題和真值聯(lián)結(jié)詞，從而將命題表示成一個公式(符號串)的過程，稱作命題的形式化(或命題的符號化)。一般的，用小寫的英文字母p,q,r,

等表示簡單命題。15

(1)“否定(negation)”(負(fù)判斷)

表示“否定”的符號是:(讀作:非、并非,not)(或~,–,N)。

符號稱為否定聯(lián)結(jié)詞,簡稱否定詞。對于一個命題p,p的否定命題“非p”表示為:p。

p稱為p的否定式。

p為真(當(dāng)且僅當(dāng))p為假。

“否定”的真值表見表1:常見的否定詞還有:不;不是;沒;沒有;

?！?.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)p

ptfft表1例1.并非所有的人都是好人。解.令:p—所有的人都是好人形式化:

p。16§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)

(2)“合取(conjunct)”(聯(lián)言判斷)表示“合取”的符號是:(讀作:且、并且,and)(或&,?,,C)

符號稱為合取聯(lián)結(jié)詞,簡稱合取詞。對于兩個命題p和q,p和q的合取命題“p且q”表示為:p

q。

p

q稱為p和q的合取式。p、q稱為該合取式的合取項(xiàng)。

p

q為真

p、q同時為真。

“合取”的真值表見表2:常見的合取詞還有:

a.并列：同時;也；既，又;一方面，另一方面；

。

b.遞進(jìn)：不僅，而且;不僅，還;

。

c.轉(zhuǎn)折：雖然，但是；盡管，可是;盡管，仍然;然而;而;卻；

。pqp

qttttffftffff表217(3)“析取(disjunct)”(選言判斷)表示“析取”的符號是:(讀作:或、或者,or)(或+,,D)

符號稱為析取聯(lián)結(jié)詞,簡稱析取詞。對于兩個命題p和q,p和q的析取命題“p或q”表示為:p

q。

p

q稱為p和q的析取式。p、q稱為該析取式的析取項(xiàng)。

p

q為真

p、q至少之一為真。“析取”的真值表見表3:常見的析取詞還有:是,還是;也許,也許;可能,可能;

?！?.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)pqp

qttttftfttfff表318例2.2是偶數(shù)并且是最小的素?cái)?shù)。解.令:p—2是偶數(shù)

q—2是最小的素?cái)?shù)形式化:p

q。

例3.未來戰(zhàn)爭是常規(guī)戰(zhàn)爭，或者是核戰(zhàn)爭。解.令:p—未來戰(zhàn)爭是常規(guī)戰(zhàn)爭q—未來戰(zhàn)爭是核戰(zhàn)爭形式化:p

q。§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)19(4)“蘊(yùn)涵((material)implication)”(假言判斷)（又稱為“蘊(yùn)含”）

表示“蘊(yùn)涵”的符號是:(讀作:如果,則,if-then)(或,I)

符號稱為蘊(yùn)涵聯(lián)結(jié)詞,簡稱蘊(yùn)涵詞。對于兩個命題p和q,p和q的蘊(yùn)涵命題“如果p,則q”表示為:p

q。p

q稱為p和q的蘊(yùn)涵式。p稱為該蘊(yùn)涵式的前件(antecedent);q稱為該蘊(yùn)涵式的后件(consequent)

。

p

q為真

q真或p假。

“蘊(yùn)涵”的真值表見表4:常見的蘊(yùn)涵詞還有:

a.充分條件:如果,那么(那末);若,則;倘若,則;假使,就;只要,就;當(dāng),便;

。

b.必要條件:只有,才;必須,不;必須,才;沒有,就沒有;不,就不;除非,不;除非,才;才;

?！?.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)pqp

qttttfffttfft表420§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)例4.如果a2能被2整除，則a能被2整除。解.令:p—a2能被2整除q—a能被2整除形式化:p

q。注.

“只有,才”。

例如.人民,只有人民,才是創(chuàng)造世界歷史的動力。

日常語言與數(shù)理邏輯在蘊(yùn)涵詞上的區(qū)別之一:日常語言只注重條件(蘊(yùn)涵前件)成立(為真)時,蘊(yùn)涵命題的真假;而不關(guān)心條件不成立(為假)時,蘊(yùn)涵命題的真假。

例如：如果我去圖書館,我就幫你還了這本書。例5.只有充分發(fā)揚(yáng)民主，才能充分調(diào)動人民群眾的積極性。解.令:p—我們充分發(fā)揚(yáng)民主q—我們充分調(diào)動人民群眾的積極性形式化:q

p。21§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)例如.對稱性:xRy

yRx;

反對稱性:xRy

yRx

x=y;

傳遞性:xRy

yRz

xRz

日常語言與數(shù)理邏輯在蘊(yùn)涵詞上的區(qū)別之二:日常語言只關(guān)心條件(蘊(yùn)涵前件)與結(jié)論(蘊(yùn)涵后件)間有某種內(nèi)在聯(lián)系(遺傳性(entailment

或genetic))的蘊(yùn)涵命題的真假;而不討論條件與結(jié)論間沒有任何內(nèi)在聯(lián)系(無遺傳性)的蘊(yùn)涵命題的真假。

例如：如果雪是黑的,則牛有三條腿。

如果1+1=3,則太陽從西邊升起。

如果細(xì)胞能進(jìn)行分裂,則飛機(jī)能飛。

這正是將此種真值聯(lián)結(jié)詞稱為“形式蘊(yùn)涵”或“實(shí)質(zhì)蘊(yùn)涵”的原因。即只與形式有關(guān),而與內(nèi)容無關(guān)。

西方人認(rèn)為內(nèi)容是表象,形式(結(jié)構(gòu))是本質(zhì)(實(shí)質(zhì))。

蘊(yùn)涵怪論22§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)

(5)“等價(jià)((material)equivalence)”(充要條件假言判斷)（又稱為“等值”。）表示“等價(jià)”的符號是:(讀作:當(dāng)且僅當(dāng),iff—ifandonlyif)(或,E)

符號稱為等價(jià)聯(lián)結(jié)詞,簡稱等價(jià)詞。對于兩個命題p和q,p和q的等價(jià)命題“p當(dāng)且僅當(dāng)q”表示為:p

q。

p

q稱為p和q的等價(jià)式。p稱為該等價(jià)式的左端;q稱為該等價(jià)式的右端。

p

q為真

p與q真值相同。

“等價(jià)”的真值表見表5:常見的等價(jià)詞還有:充分必要;除非不,否則;

。pqp

qttttffftffft表523§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)例6.a是完全平方數(shù)當(dāng)且僅當(dāng)它的素?cái)?shù)分解式中各指數(shù)均是偶數(shù)。解.令:p—a是完全平方數(shù)q—a的素?cái)?shù)分解式中各指數(shù)均是偶數(shù)形式化:p

q。注.

日常語言與數(shù)理邏輯在等價(jià)詞上的區(qū)別之一:日常語言只注重條件和結(jié)論(左右端)至少有一方成立(為真)時的等價(jià)命題;而不關(guān)心條件和結(jié)論都不成立(為假)時的等價(jià)命題的真假。

例如：地球人能到河外星系當(dāng)且僅當(dāng)宇宙飛船能突破光束。

日常語言與數(shù)理邏輯在等價(jià)詞上的區(qū)別之二:日常語言只關(guān)心條件與結(jié)論(左右端)間有某種內(nèi)在聯(lián)系(遺傳性)的等價(jià)命題的真假;而不討論條件與結(jié)論間沒有任何內(nèi)在聯(lián)系(無遺傳性)的等價(jià)命題的真假。

例如.：牛有三條腿當(dāng)且僅當(dāng)雪是黑的。

太陽從西邊升起當(dāng)且僅當(dāng)1+1=3。

飛機(jī)能飛當(dāng)且僅當(dāng)細(xì)胞能進(jìn)行分裂。

這正是將此種真值聯(lián)結(jié)詞稱為“形式等價(jià)”或“實(shí)質(zhì)等價(jià)”的原因。即只與形式有關(guān),而與內(nèi)容無關(guān)。等價(jià)怪論24§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)3.形式化舉例

：例7.(1)如果小張做完了作業(yè)并且沒有其他事情,他就去踢球或去看電視。

(2)小王總是在辦公室忙碌，除非他病了或辦公室停電。

(3)小李沒在圖書館看書,他要么找老師答疑去了,要么因身體不舒服先回宿舍去了。解.(1)令:p—小張做完了作業(yè)q—小張有其他事情

r—小張?zhí)咔?/p>

s—小張看電視形式化:(p

q)(r∨

s)。

25§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)(2)令:p—小王病了q—辦公室停電

r—小王在辦公室忙碌形式化:((p

q))

r。

(3)令:p—小李在圖書館看書q—小李找老師答疑

r—小李身體舒服s—小李回宿舍形式化:

p

(q

((

r)

s))。26§2.命題的形式化真值聯(lián)結(jié)詞真值函項(xiàng)例8.(1)拿破侖(Napoleon)相信“巴拓(Brutus)殺了凱撒(Caesar)”。

(2)第一個命題是邏輯上根據(jù)第二個命題得出的。

4.真值函項(xiàng)(truth-function)：一個聯(lián)結(jié)詞,只要給出自變項(xiàng)們的真值,就能夠推斷出由此聯(lián)結(jié)詞構(gòu)成的整個復(fù)合命題的真值,具有這種特性的聯(lián)結(jié)詞稱為真值函項(xiàng)算子(truth-functionaloperator)

。由真值函項(xiàng)算子構(gòu)成的復(fù)合命題稱為真值函項(xiàng)。

五大真值聯(lián)結(jié)詞:,,,,均是真值函項(xiàng)算子;由它們構(gòu)成的復(fù)合命題都是真值函項(xiàng)。27§3.初始符號形成規(guī)則合式公式賦值真值表1.初始符號(initialsymbol)：

命題變項(xiàng)(propositionalvariables)：p,q,r,(不夠加下標(biāo));真值聯(lián)結(jié)詞(truth-connectives)：，，，，

(not,and,or,if-then,iff);2.形成規(guī)則(formationrules)：

FR1.單獨(dú)一個命題變項(xiàng)是公式(原子);

FR2.如果

是公式，則

也是公式;FR3.如果,

都是公式，則(

)也是公式;

注：這里:=,,,;原子—原子公式。3.合式公式(Wff-wellformedformula)：

有限次應(yīng)用上述FR1

FR3規(guī)則所構(gòu)成的有限符號串稱為合式公式(簡稱公式)。28§3.初始符號形成規(guī)則合式公式賦值真值表注：

由于有限符號串稱為字(word),故合式公式就是合法的(legal)字;

形成規(guī)則的三種表示法:

a.歸納定義(見2的定義)；

b.巴科斯范式(BNF---backusnormalform)

:

Wff::=propositionalvariables|

Wff|(Wff

Wff)

這里:=,,,；

c.

條件-結(jié)論式(condition-conclusion):p，，

這里:=,,,；

課本引入命題常項(xiàng)(propositionalconstants)：T,F(兩個特殊的命題)

我們的演算系統(tǒng)不引入；

空箱理論:形式邏輯

數(shù)理邏輯(符號化,形式化,結(jié)構(gòu)化,抽象)命題

公式(符號化,形式化,結(jié)構(gòu)化,抽象)。29§3.初始符號形成規(guī)則合式公式賦值真值表4.括號省略的原則：

(1)最外層括號省略；(2)使用優(yōu)先級：

(高);

，(中);

，(低)。5.賦值(value-assignment)：

給公式所涉及到的所有命題變項(xiàng)(原子公式)的每一個指派一個真值的過程稱為一個賦值。例1.公式(((p

q)(r))(p

r))

。30§3.初始符號形成規(guī)則合式公式賦值真值表設(shè)公式

所含的全部命題變項(xiàng)為:p1,p2,

,pn,則公式

稱為一個n元命題公式,并記

為

(p1,p2,

,pn)。由于公式是真值函項(xiàng),故只要命題變項(xiàng)p1,p2,

,pn的真值確定,則公式的相應(yīng)真值也就確定了。給公式的命題變項(xiàng)p1,p2,

,pn一組確定的真值p1

,p2

,

,pn

后所得到的序列

v=(p1

,p2

,

,pn

)稱為公式關(guān)于命題變項(xiàng)組(p1,p2,

,pn)的一個賦值。公式在該賦值v下的真值記為(v)或

v或更明確的

(p1

,p2

,

,pn

)。31證實(shí)賦值(verifyingvalue-assignment):使(v)=t的賦值v稱為公式的一個證實(shí)賦值。

弄假賦值(falsifyingvalue-assignment):使(v)=f的賦值v稱為公式的一個弄假賦值。一個公式

=

(p1,p2,

,pn)的賦值有2n個。§3.初始符號形成規(guī)則合式公式賦值真值表6.真值表(truth-table)：

將一公式在所有賦值下形成真值的過程排列起來形成一張表,這張表就稱為真值表。例2.3元命題公式=(p

q

r)

q

的真值表。32

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

1.可滿足性(satisfiability)：

公式

是可滿足的至少存在著的一個證實(shí)賦值v。

可滿足的公式記為Sat

。

例1.公式=(p

q

r)

q是可滿足的。

2.不可滿足性(unsatisfiability)：

公式

是不可滿足的的每一個賦值v都是它的弄假賦值。

不可滿足的公式記為Unsat或Insat

。例2.公式=p

p是不可滿足的。注.

不可滿足的公式又稱為邏輯謬誤(logicalmistake)、矛盾式(contradiction)。33§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理3.有效性(validity)：

公式

是有效的的每一個賦值v都是它的證實(shí)賦值。

有效的公式記為?

。例3.公式=p

p是有效的。注.

有效的公式又稱為邏輯真理(logicaltruth)、重言式(tauology)。

有效性的證明方法：

真值表法:看

之列是否全為t，若是則

有效；否則

不有效。

反證法:假設(shè)

有一弄假賦值v,

則得到矛盾。34§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例4.判斷并證明公式=((pq)(p

r))(q

r)

r是有效的。解.真值表法:=((pq)(p

r))(q

r)

r之列全是t,故

有效,即

?((pq)(p

r))(q

r)

r。

反證法:假設(shè)有一賦值v=(p

,q

,r

),是公式

=((pq)(p

r))(q

r)

r

的弄假賦值,

則(v)=f。

……注.

不可滿足性的證明方法：

真值表法:看

之列是否全為f，全為f,

不可滿足;否則,

可滿足。

反證法:假設(shè)

有一證實(shí)賦值v,

則得到矛盾。

可能性偶然性(contingency)：

公式

是可能的(或偶然的)既不是重言的又不是矛盾的。35§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

二個簡單的結(jié)論:(1)公式

是有效的

公式

是不可滿足的;(2)公式

是可能的(偶然的)

公式

和都是可滿足的。注.

有效性(重言式)、偶然性、不可滿足性(矛盾式)

三概念將全部命題公式的集合劃分為三部分；可滿足性=偶然性+有效性(重言式)；

根椐上述簡單結(jié)論(1)可知，重言式與矛盾式一一對應(yīng)；也即邏輯真理與邏輯謬誤是結(jié)伴而生的；有一個邏輯真理，就有一個邏輯謬誤；反之亦然。重言式矛盾式偶然的全部命題公式的集合36§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理4.邏輯蘊(yùn)涵關(guān)系(logicalimplicationrelation)：

稱公式與公式

1,2,,n有邏輯蘊(yùn)涵關(guān)系（公式

1,2,,n邏輯蘊(yùn)涵公式），記為

1,2,,n?

對于公式

1,2,,n和公式的合成變項(xiàng)組的任一賦值v,均有：如果v同時是公式

1,2,,n的證實(shí)賦值，則v也是公式的證實(shí)賦值。即

1(v)=t,2(v)=t,,n(v)=t

(v)=t

。

其中：公式

1,2,,n稱為前提(premise)，公式稱為結(jié)論(conclusion)。注.

邏輯蘊(yùn)涵關(guān)系又稱為邏輯推論關(guān)系,簡稱邏輯推論(logicalinference)，也稱為邏輯推理關(guān)系,簡稱邏輯推理(logicalreasoning)。

邏輯蘊(yùn)涵關(guān)系1,2,,n?按關(guān)系的記法應(yīng)是(1,2,,n,)?；這說明邏輯蘊(yùn)涵關(guān)系?是一n+1元關(guān)系。

37§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

特殊情況，前提公式只有一個(n=1),即?對于公式

和公式的合成變項(xiàng)組的任一賦值v，均有：如果v是公式

的證實(shí)賦值，則v也是公式的證實(shí)賦值。即(v)=t

(v)=t

。

邏輯蘊(yùn)涵

?

可看作是有條件(即(v)=t)的有效性。

符號

和

用來分別表示自然語言中的詞匯“當(dāng)且僅當(dāng)”，“如果，則”。

連接的左右兩邊都是語句(命題)，而

?連接的左右兩邊都是公式。

符號?表示邏輯蘊(yùn)涵關(guān)系，符號表示邏輯等價(jià)關(guān)系。使(v)=t的賦值的集合全部賦值的集合在此集合上公式

有效定理1.以下三條等價(jià)(1)?(

邏輯蘊(yùn)涵)(2)?(

是有效的)(3)Insat(

)(

是不可滿足的)38§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理證.(1)

(2):對(,的合成變項(xiàng)組的)任一賦值v,

若(v)=t,則根據(jù)

?,由邏輯蘊(yùn)涵的定義,有(v)=t，從而按的真值表，可知(

)(v)=t。

若(v)=f,則無論(v)=t還是f，按的真值表，均有(

)(v)=t。

綜合

,

這兩種情況，總有(

)(v)=t，按有效性的定義，有?

。

(2)

(3):對任一賦值v,

若(v)=t,則根據(jù)?,由有效性的定義,有(

)(v)=t，從而按的真值表，可知(v)=t,于是按的真值表，可知()(v)=f,

最后按的真值表，可知()(v)=f

。

若(v)=f,則無論()(v)=t還是f，按的真值表，均有()(v)=f

。

綜合

,

這兩種情況，總有()(v)=f

，按不可滿足性的定義，有Insat(

)。39§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理注.

定理1中(1)

(2)表明了有效性與邏輯蘊(yùn)涵間的轉(zhuǎn)換關(guān)系。也表明了邏輯蘊(yùn)涵與形式蘊(yùn)涵間的轉(zhuǎn)換關(guān)系,即,邏輯蘊(yùn)涵是有效的形式蘊(yùn)涵。

定理1中(1)

(3)表明了邏輯蘊(yùn)涵的結(jié)論的反面與其前提是不可能相容的。而這點(diǎn)正是《人工智能》中證明邏輯蘊(yùn)涵的理論根據(jù)。其思想是:為了證明邏輯蘊(yùn)涵

?,轉(zhuǎn)而去證

是不可滿足的。而證

的不可滿足性,《人工智能》有強(qiáng)有力的工具—魯濱遜(Robbins)1965年提出的消解原理(也稱歸結(jié)法)。

(3)

(1):對任一賦值v,

若(v)=t,則根據(jù)Insat(

),由不可滿足性的定義,有(

)(v)=f，從而按的真值表，可知必有()(v)=f,于是按的真值表，可知(v)=t,

所以按邏輯蘊(yùn)涵的定義，有?。40§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理邏輯蘊(yùn)涵的證明方法：

真值表法:看

之列是否

之列?

若

,邏輯蘊(yùn)涵;否則,

不邏輯蘊(yùn)涵。(列是對應(yīng)元素的;并且f

f,f

t,t

t。)

分析賦值法:

(a)構(gòu)造法:對任一賦值v,證明((v)=t)((v)=t);(b)逆否證法:對任一賦值v,證明((v)=f)((v)=f);(c)無義證法:對任一賦值v,證明(v)=f;(d)平凡證法:對任一賦值v,證明(v)=t。41§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例5.判斷并證明邏輯蘊(yùn)涵(p

q)(q

r)?p

r。解.令=(p

q)(q

r)，=p

r。

邏輯蘊(yùn)涵

?的真值表如下表2所示:pqrp

qq

r(p

q)(q

r)p

rtttttttttftffftftftfttffftfffttttttftftfftfftttttffftttt表2觀察可知之列

之列，故邏輯蘊(yùn)涵，即

(p

q)(q

r)?p

r。42例6.證明邏輯蘊(yùn)涵

q(p

q)

?p。證.(a)

令=

q(p

q)

，=

p。對任一賦值v=(p

,q

)，若(v)=t，則

q

(p

q

)=t。于是按

的真值表，必有

q

=t，且p

q

=t，又按

的真值表，可得q=f，從而按

的真值表，必有p

=f，再按

的真值表，可得

p

=t，即(v)=t

。

故根椐構(gòu)造法，可知邏輯蘊(yùn)涵，即

q(p

q)

?p。

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理43(b)

令=

q(p

q)

，=

p。對任一賦值v=(p

，q

)，若(v)=f，則

p

=f

，按

的真值表，可得p

=t。于是(1)若q

=t，則按

的真值表，有

q

=f

，無論p

q

=t還是f,按

的真值表,都有

q

(p

q

)=f

；

(2)若q

=f，則由已證得的p

=t，按

的真值表，可得p

q

=f，

無論

q

=t還是f，按

的真值表,都有

q

(p

q

)=f。

綜合(1)，(2)，總有

q

(p

q

)=f，即(v)=

f

。故根椐逆否證法，可知邏輯蘊(yùn)涵，即

q(p

q)?p?！?.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理44§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例7.證明邏輯蘊(yùn)涵p

p

?q。證.采用無義證法:令=p

p

，=q。

顯然，是不可滿足的。故按不可滿足性的定義，對任一賦值v，總有(v)=f;根椐無義證法，可知邏輯蘊(yùn)涵，即

p

p

?q。例8.證明邏輯蘊(yùn)涵p?(q

q)

q。證.采用平凡證法:令=p

，=(q

q)

q。

易證

是有效的。故按有效性的定義，對任一賦值v，總有(v)=t;根椐無義證法，可知邏輯蘊(yùn)涵，即

p?(q

q)

q。45§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理定理2.以下五條等價(jià)(1)

1,2,,n-1,n?;

(2)?

1(

2(

n-1(

n

)));

(3)?

1

2

n-1

n

;(4)

1

2

n-1

n

?

;(5)Insat(

1

2

n-1

n

)。證.(3)

(4)

(5):令:

=

1

2

n-1

n，則根據(jù)定理1,可知(3)

(4)

(5)。

(1)

(2):對任一賦值v,

若

1(v)=t,

2(v)=t,,

n-1(v)=t,

n(v)=t,則根據(jù)

1,2,,n-1,n?,由邏輯蘊(yùn)涵的定義,有(v)=t,于是由n(v)=t,按的真值表,可知(

n

)(v)=t,再n-1(v)=t,按的真值表,可知(

n-1(

n

))(v)=t,

,再2(v)=t,按的真值表，可知(

2(

n-1(

n

)))(v)=t,

最后再1(v)=t,按的真值表，可知(

1(

2(

n-1(

n

))))(v)=t。46§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

否則,必存在著k(1kn)使1(v)=t,

2(v)=t,,

k-1(v)=t,

k(v)=f,則無論(

k+1(

n-1(

n

)))(v)=t還是f,由k(v)=f,按的真值表，都有

(

k

(

k+1(

n-1(

n

))))(v)=t,

從而再由k-1(v)=t,按的真值表，可知(

k-1

(

k

(

k+1(

n-1(

n

)))))(v)=t,

,

,再由2(v)=t,按的真值表，可知

(

2(

n-1(

n

)))(v)=t,

最后再由1(v)=t,按的真值表，可知

(

1(

2(

n-1(

n

))))(v)=t。綜合

,

這兩種情況，總有(

1(

2(

n-1(

n

))))(v)=t

，47§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

所以按有效性的定義，有?

1(

2(

n-1(

n

)))

。

(2)

(3):對任一賦值v,

若(

1

2

n-1

n)(v)=t,則按

的真值表,可知1(v)=t,

2(v)=t,,

n-1(v)=t,

n(v)=t,則根據(jù)

?

1(

2(

n-1(

n

))),由有效性的定義,可知(1(

2(

n-1(

n

))))(v)=t,于是由1(v)=t,按的真值表,可知

(

2(

n-1(

n

)))(v)=t,再由2(v)=t,按的真值表,可知(

3(

n-1(

n

)))(v)=t,48§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

,再由n-2(v)=t,按的真值表，可知(

n-1(

n

))(v)=t,

再由n-1(v)=t,按的真值表，可知(

n

)(v)=t,

最后再由n(v)=t,按的真值表，可知

(v)=t。于是由

的真值表,可知(

1

2

n-1

n

)(v)=t。

否則,(

1

2

n-1

n)(v)=f,則無論(v)=t還是f,按的真值表，都有

(

1

2

n-1

n

)(v)=t。

綜合

,

這兩種情況，總有

(

1

2

n-1

n

)(v)=t，49§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

所以按有效性的定義，有

?

1

2

n-1

n

。

(3)

(1):對任一賦值v,若

1(v)=t,

2(v)=t,,

n-1(v)=t,

n(v)=t,則按的真值表,可知(

1

2

n-1

n)(v)=t,于是根據(jù)?

1

2

n-1

n

,由有效性的定義,可知(

1

2

n-1

n

)(v)=t,從而按的真值表,可知(v)=t。所以,由邏輯蘊(yùn)涵的定義,可得

1,2,,n-1,n?。50§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理定理3.(基本邏輯蘊(yùn)涵式)

(1)p

q?

p,p

q?q(合取分析式)(2)p?

p

q,q?

p

q(析取構(gòu)成式)(3)p,p

q?q(充足理由律，假言推理、肯定(分離)前件式)(4)

q,p

q?

p(假言推理、否定(拒絕)后件式)(5)

q,

p

q?p(換質(zhì)位律、否定(拒絕)后件式)(6)

p,p

q?q(相容選言推理、否定肯定式)(7)p

q,q

r?p

r((假言)三段論原則)(8)p

q,p

r,q

r?r(二難推理、簡單構(gòu)成式)(9)?p

p(排中律)(10)?

(p

p)(無矛盾律)(11)p

?p(或?p

p)(同一律)51§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理注.

定理3的(11)(10)(9)(3)反映的是《形式邏輯》的命題邏輯中著名的四大推理規(guī)律:同一律,無矛盾律,排中律,充足理由律。

同一律:在同一思維的過程中,每一思想的自身都具有同一性。

其形式表示為:?p

p。

無矛盾律:在同一思維的過程中,反映對象的同一方面的兩個互相矛盾、互相反對的思想不能都是真的，必有一個是假的。

其形式表示為:?

(p

p)。

排中律:在同一思維的過程中,兩個互相矛盾的思想不能都是假的，必有一個是真的。

其形式表示為:?p

p。

充足理由律:在思維過程中,任何一個正確的真實(shí)的思想總有它的充足理由。

其形式表示為:?p(pq)q。52注.

邏輯等價(jià)關(guān)系

按關(guān)系的記法應(yīng)是(,)；這說明邏輯等價(jià)關(guān)系是一二元關(guān)系。

?且?

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理5.邏輯等價(jià)關(guān)系(logicalequivalencerelation)：

稱公式

與公式

有邏輯等價(jià)關(guān)系(公式

邏輯等價(jià)公式

)，記為

對于公式

和公式的合成變項(xiàng)組的任一賦值v，均有：(v)=

(v)。其中：公式

稱為左邊，公式稱為右邊。邏輯等價(jià)的證明方法：

真值表法:看

之列是否=之列?

若=,邏輯等價(jià);否則,

不邏輯等價(jià)。53§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例9.判斷并證明邏輯等價(jià)(p

q)

r

p(q

r)

。解.采用真值表法。令=(p

q)

r，=p(q

r)

。

邏輯等價(jià)

的真值表如下表3所示:觀察可知之列=

之列，故邏輯等價(jià)，即

(p

q)

r

p(q

r)。pqrp

q(p

q)

rq

rp(q

r)tttttttttftttttfttttttffttftfttttttftfttttfftftttfffffff表354§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例10.判斷并證明邏輯等價(jià)p(q

r)(p

q)(p

r)。解.采用真值表法。令=p(q

r)，=(p

q)(p

r)

。

邏輯等價(jià)

的真值表如下表4所示:觀察可知之列=

之列，故邏輯等價(jià)，即(p

q)

r

(p

q)(p

r)。pqrq

rp(q

r)p

qp

r(p

q)(p

r)ttttttttttftttfttftttftttfffffffftttffffftftffffffttffffffffffff表455§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理例11.判斷并證明邏輯等價(jià)p

q

q

p。解.采用真值表法。令=p

q，

=

q

p

。

邏輯等價(jià)

的真值表如下表5所示:觀察可知之列=之列，故

邏輯等價(jià)，即

p

q

q

p。pqp

q

q

p

q

ptttffttfftfffttfttfftttt表556定理4.

?

(邏輯等價(jià)與形式等價(jià)間的轉(zhuǎn)換關(guān)系)。證.先證

:對公式

、的合成變項(xiàng)組的任一賦值v,

若(v)=t,則根據(jù)

,由邏輯等價(jià)的定義,有(v)=(v),于是(v)=t,從而按的真值表,可知(

)(v)=t。

若(v)=f,則根據(jù)

,由邏輯等價(jià)的定義,有(v)=(v),于是(v)=f,從而按的真值表,可知(

)(v)=t。

綜合

,

這兩種情況，總有(

)(v)=t，按有效性的定義，有?

。

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理57次證

:對任一賦值v,

若(v)=t,則根據(jù)?

,由有效性的定義,有(

)(v)=t,從而按的真值表,可知(v)=t,于是(v)=(v)=t。

若(v)=f,則根據(jù)?

,由有效性的定義,有(

)(v)=t,從而按的真值表,可知(v)=f,于是(v)=(v)=f。

綜合

,

這兩種情況，總有(v)=(v)，按邏輯等價(jià)的定義，有

。§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理58定理5.邏輯等價(jià)關(guān)系是(全體命題公式集上的)一種等價(jià)關(guān)系。

(1)自反性:;

(2)對稱性:

;

(3)傳遞性:

且

證.(1)自反性:對任一命題公式

，

對任一賦值v,(v)=(v)(相等=的自反性)

(邏輯等價(jià)的定義)(2)對稱性:

對于公式

、的合成變項(xiàng)組的任一賦值v,

(v)=(v)(邏輯等價(jià)的定義)

對任一賦值v,

(v)=(v)(相等=的對稱性)(邏輯等價(jià)的定義)

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理59(3)傳遞性:

且對于公式

、、的合成變項(xiàng)組的任一賦值v,

(v)=(v)且(v)=(v)(邏輯等價(jià)的定義)

對任一賦值v,

(v)=(v)(相等=的傳遞性)

(邏輯等價(jià)的定義)§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理定理6.(基本邏輯等價(jià)式)

(1)雙重否定律：

pp;(2)冪等律：p

pp,p

pp;(3)結(jié)合律：(p

q)

rp

(q

r),(p

q)

rp

(q

r);60§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理定理6.(基本邏輯等價(jià)式)(4)吸收律：p

(p

q)p,p

(p

q)p;

(5)交換律：p

q

q

p,p

q

q

p;(6)分配律：p

(q

r)(p

q)

(p

r),p

(q

r)(p

q)

(p

r);(7)逆否律：p

q

q

p;(換質(zhì)位律)(8)deMorgan律：

(p

q)

p

q,

(p

q)

p

q;(9)歸約律：p

q

p

q,p

q

(p

q)

(q

p);(10)化簡律：p

(q

q

r)p,p

(q

q

r)p。(真值聯(lián)結(jié)詞)61注.

定理6中(3)結(jié)合律，(5)交換律，(2)冪等律，(4)吸收律說明命題邏輯(?,

,

)構(gòu)成(代數(shù))格。

定理6中(3)結(jié)合律，(5)交換律，(2)冪等律，(4)吸收律，(6)分配律說明命題邏輯(?,

,

)構(gòu)成分配格。

如果引入兩個命題常項(xiàng)(propositionalconstant)T(真值恒為t)和F(真值恒為f),以及序?(

?

?

)

,則有F?p?T及p

pT,p

pF。于是命題邏輯(?,

?,

,

,,F,T)是有界格，進(jìn)而有補(bǔ)的分配格,即，布爾代數(shù)。

定理6中(1)雙重否定律是《形式邏輯》與《辯證邏輯》的主要區(qū)別之一：《辯證邏輯》三大規(guī)律之一否定之否定規(guī)律說：事物否定之否定的發(fā)展過程，不是(象命題邏輯那樣)

簡單的回到原位，而是呈現(xiàn)螺旋式(似有周期性)上升和波浪式前進(jìn)運(yùn)動的特點(diǎn)?！?.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理62§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理

定理6中(1)雙重否定律以及定理3中(9)排中律也是經(jīng)典邏輯與現(xiàn)代直覺主義邏輯的主要區(qū)別之一：現(xiàn)代直覺主義邏輯不僅不承認(rèn)排中律，而且也不承認(rèn)雙重否定律的一半：

p?p，只承認(rèn)另一半：p

?

p。

利用雙重否定律可檢查一些命題(判斷)語句的失誤。例如：

科學(xué)發(fā)展到今天，誰也不會否認(rèn)地球不是圍繞著太陽運(yùn)行的。

任何人在工作中難免不犯錯誤。

我并非反對在寫戰(zhàn)爭的影片里不該有某些愛情描寫。

難道能夠否認(rèn)這部小說沒有不足之處嗎？

能否堅(jiān)持實(shí)踐第一的觀點(diǎn)是貫徹實(shí)事求是路線的思想前提。

63§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理定理7.邏輯蘊(yùn)涵關(guān)系是(全體命題公式集上的)一種“半序關(guān)系”。

(1)自反性:

?;

(2)反對稱性:

?

且?

;

(3)傳遞性:

?

且?

?

。證.(1)自反性:對任一命題公式

，

對任一賦值v,若(v)=t,則(v)=t(同一性)

?

(邏輯蘊(yùn)涵的定義)(2)反對稱性:?且?

對公式

、的合成變項(xiàng)組的任一賦值v,((v)=t

(v)=t)

且((v)=t

(v)=t)(邏輯蘊(yùn)涵)

對任一賦值v,

(v)=t

(v)=t

對任一賦值v,

(v)=(v)(邏輯等價(jià)的定義)64注.

邏輯蘊(yùn)涵關(guān)系不是(全體命題公式集上的)一種真正的半序關(guān)系，而是(全體命題公式集上的)一種(類似的)“半序關(guān)系”。因?yàn)樵诜磳ΨQ性里，用邏輯等價(jià)代替了相等。

結(jié)合邏輯等價(jià)定義的注二及定理7的(2)反對稱性，得到下面的結(jié)論：

?且?

§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理(3)傳遞性:

?

且?

對公式

、、的合成變項(xiàng)組的任一賦值v,

((v)=t)

((v)=t)

且((v)=t)

((v)=t)

(邏輯蘊(yùn)涵)

對任一賦值v,

((v)=t)

((v)=t)

(的傳遞性)

?

(邏輯蘊(yùn)涵的定義)65§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理引理1.邏輯運(yùn)算是保持邏輯等價(jià)的。

即如果

1

1且2

2

,則(1)

1

1;

(2)

1

2

1

2

;

(3)

1

2

1

2

;

(4)

1

2

1

2

;

(5)

1

2

1

2

。證.(2)對任一賦值v,

根據(jù)條件

1

1且2

2

,

由邏輯等價(jià)的定義可知,

1(v)=

1(v)且2(v)=2(v),從而按

的真值表:

若

1(v)=

1(v)=t且2(v)=2(v)=t

,則(

1

2)(v)=t=(1

2)(v);

66§4.可滿足性有效性邏輯推論邏輯等價(jià)

替換定理代入定理對偶定理若

1(v)=

1(v)=t且2(v)=2(v)=f

,則(

1

2)(v)=t=(1

2)(v)