03-第三次課(范式與推理)課件

03第三次課(范式與推理)聰明出于勤奮，天才在于積累03第三次課(范式與推理)03第三次課(范式與推理)聰明出于勤奮，天才在于積累3/23/20211:02PMHongzhiQiao,XidianUniv.2作業(yè)問題：真值表順序000001010011100101110111

步驟過于省略。公式復(fù)雜時(shí)不細(xì)心。第一章---數(shù)理邏輯3/23/20211:02PMHongzhiQiao,XidianUniv.3n個(gè)命題變項(xiàng)所能組成的具有不同真值的命題公式僅有2個(gè),然而與任何一個(gè)命題公式等值而形式不同的命題公式可以有無窮多個(gè)。這樣，首先就要問凡與命題公式A等值的公式能否都可以化為某一個(gè)統(tǒng)一的標(biāo)準(zhǔn)形式希望這種標(biāo)準(zhǔn)形能為我們的討論帶來些方便，如借助于標(biāo)準(zhǔn)形對(duì)任意兩個(gè)形式上不同的公式，可判斷它們的是否等值。借助于標(biāo)準(zhǔn)形容易判斷任一公式是否為重言式或矛盾式。

第一章---數(shù)理邏輯n范式存在定理

任一命題公式都存在有與之等值的合取范式和析取范式。

第一章---數(shù)理邏輯7/24/20236HongzhiQiao,XidianUniv.求范式的步驟

對(duì)一個(gè)已給的公式,可按下述步驟求得該公式的合取范式和析取范式。

(1)消去已給公式中的聯(lián)結(jié)詞→和。

(2)重復(fù)使用摩根律和雙重否定律,把否定詞內(nèi)移到直接作用于命題變項(xiàng)上。

(3)重復(fù)使用分配律。

第一章---數(shù)理邏輯7/24/20237HongzhiQiao,XidianUniv.求(P∨Q)(P∧Q)的析取范式。

解：(P∨Q)(P∧Q)

=((P∨Q)∧(P∧Q))∨((P∨Q)∧(P∧Q))

=(P∧Q∧P∧Q)∨((P∨Q)∧(P∨Q))(摩根律、雙重否定)

=(P∧Q∧P∧Q)∨(P∧P)∨(P∧Q)∨(Q∧P)∨(Q∧Q)(分配律)

這已是析取范式了。又因P∧P,Q∧Q,P∧Q∧P∧Q都是矛盾式,從而利用2.2.1的同一律P∨F=P,還可簡(jiǎn)化為

(P∧Q)∨(P∧Q)

可見一公式的范式不是唯一的。

第一章---數(shù)理邏輯7/24/20238HongzhiQiao,XidianUniv.求(P∨Q)(P∧Q)的合取范式

解:(P∨Q)(P∧Q)

=((P∨Q)∨(P∧Q))∧((P∨Q)∨(P∧Q))

=((P∨Q)∨(P∧Q))∧((P∧Q)∨(P∨Q))(摩根律、雙重否定)

=(P∨Q)∧(P∨Q)(吸收律)第一章---數(shù)理邏輯7/24/20239HongzhiQiao,XidianUniv.對(duì)n個(gè)命題變項(xiàng)P1,…,Pn來說,所組成的公式(基本積)

Q1∧Q2∧…∧Qn

其中Qi=Pi

或Pi(i=1,…,n),則稱Q1∧…∧Qn為極小項(xiàng),并以mi表示。

極小項(xiàng)必須含有Q1,…,Qn全部n個(gè)文字。第一章---數(shù)理邏輯7/24/202310HongzhiQiao,XidianUniv.由兩個(gè)命題變項(xiàng)P1,P2可構(gòu)成四個(gè)極小項(xiàng)：P1∧P2,P1∧P2,P1∧P2和P1∧P2。若將Pi與1對(duì)應(yīng),而Pi與0對(duì)應(yīng),進(jìn)而將極小項(xiàng)

P1∧P2與00對(duì)應(yīng),簡(jiǎn)記為m0。

P1∧P2與01對(duì)應(yīng)，簡(jiǎn)記為m1。

P1∧P1與10對(duì)應(yīng),簡(jiǎn)記為m2。

P1∧P2與11對(duì)應(yīng),簡(jiǎn)記為m3。

n個(gè)命題變項(xiàng)P1,…,Pn可組成個(gè)極小項(xiàng)。每個(gè)極小項(xiàng)也可以mi表示。每個(gè)極小項(xiàng)中Q1,…,Qm全部出現(xiàn)。

第一章---數(shù)理邏輯7/24/202311HongzhiQiao,XidianUniv.定義：僅由極小項(xiàng)構(gòu)成的析取式為主析取范式。

定理：任一含有n個(gè)命題變項(xiàng)的公式，都有唯一的一個(gè)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主析取范式。

第一章---數(shù)理邏輯7/24/202312HongzhiQiao,XidianUniv.用真值表法將PQ化成主析取范式。

由P,Q到PQ的真值表(從T即選取使該式真值為T的真值指派項(xiàng)的析取)列寫PQ,便得

PQ=(P∧Q)∨(P∧Q)=m0∨m3

并簡(jiǎn)記為∨0,3。這便是PQ的主析取范式。

又因?yàn)榈戎倒蕉加邢嗤恼嬷当?從而可知所有等值公式(變項(xiàng)均為n)的主析取范式是相同的，或說一個(gè)公式的主析取范式是唯一的。

第一章---數(shù)理邏輯7/24/202313HongzhiQiao,XidianUniv.用填滿命題變項(xiàng)法,將P→Q的析取范式化成主析取范式。

P→Q=P∨Q

已是P→Q的析取范式?，F(xiàn)將這范式中的合取式P添加變項(xiàng)Q,合取式Q添加P,即填滿變項(xiàng)P、Q,以構(gòu)成極小項(xiàng)。

P=P∧(Q∨Q)

=(P∧Q)∨(P∧Q)

Q=Q∧(P∨P)

=(Q∧P)∨(Q∧P)

第一章---數(shù)理邏輯7/24/202314HongzhiQiao,XidianUniv.從而

P→Q=P∨Q

=(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)

=(P∧Q)∨(P∧Q)∨(P∧Q)

=m0∨m1∨m3

=∨0,1,3

這便是P→Q的主析取范式。當(dāng)然也可以用真值表法來得到此主析取范式.第一章---數(shù)理邏輯7/24/202315HongzhiQiao,XidianUniv.某班級(jí)要從3名學(xué)生A，B，C中挑選1～2名搬花。由于工作需要，選派時(shí)要滿足以下條件：

（1）若A去，則C同去；

（2）若B去，則C不能去；

（3）若C不去，則A或B可以去。

問班里應(yīng)如何選派他們？

第一章---數(shù)理邏輯7/24/202316HongzhiQiao,XidianUniv.解：設(shè)P：派A去Q：派B去R：派C去

由已知條件可得公式

(P→R)∧(Q→R)∧(R→(P∨Q))

經(jīng)過演算可得

(P→R)∧(Q→R)∧(R→(P∨Q))

=m1∨m2∨m5第一章---數(shù)理邏輯7/24/202317HongzhiQiao,XidianUniv.由于

m1=P∧Q∧R,m2=P∧Q∧R,m5=P∧Q∧R

可知，選派方案有三種：

（a）C去，而A，B都不去；

（b）B去，而A，C都不去；

（c）A，C同去，而B不去。第一章---數(shù)理邏輯7/24/202318HongzhiQiao,XidianUniv.極小項(xiàng)的性質(zhì)

(1)對(duì)一個(gè)含有n個(gè)變項(xiàng)的公式來說,所有可能的極小項(xiàng)個(gè)數(shù)和該公式的解釋個(gè)數(shù)一樣多,都是i。

(2)每個(gè)極小項(xiàng)只在一個(gè)解釋下為真。

(3)極小項(xiàng)兩兩不等值,而且mi∧mj=F(i≠j)。第一章---數(shù)理邏輯7/24/202319HongzhiQiao,XidianUniv.由n個(gè)命題變項(xiàng)P1,…,Pn所組成的公式(基本和)

Q1∨Q2∨…∨Qn

其中Qi=Pi或Pi(i=1,…,n),則稱Qi∨…∨Qn

為極大項(xiàng),以Mi表示。

極大項(xiàng)必須含有Q1,…,Qn全部n個(gè)文字。

由兩個(gè)命題變項(xiàng)P1,P2可構(gòu)成四個(gè)極大項(xiàng)：P1∨P2,P1∨P2,P1∨P2和P1∨P2,并分別以M3,M2,M1和M0表示。

n個(gè)命題變項(xiàng)P1,…,Pn可組成個(gè)極大項(xiàng)。每個(gè)極大項(xiàng)也可以Mi來表示。每個(gè)極大項(xiàng)中Q1,…,Qn全部出現(xiàn)。

第一章---數(shù)理邏輯7/24/202320HongzhiQiao,XidianUniv.

定義：僅由極大項(xiàng)構(gòu)成的合取式為主合取范式。

定理：任一含有n個(gè)命題變項(xiàng)的公式，都有唯一的一個(gè)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主合取范式。

同樣使用真值表列寫公式的方法，以及將合取范式中的析取式填滿命題變項(xiàng)的方法都可得到一個(gè)公式的唯一的主合取范式。第一章---數(shù)理邏輯7/24/202321HongzhiQiao,XidianUniv.用真值表法將PQ化成主合取范式。

依由P、Q到PQ的真值表,從F(即選取使該式真值為F的反真值指派項(xiàng)的合取)列寫PQ,便得

PQ=(P∨Q)∧(P∨Q)

=M1∧M2

并簡(jiǎn)記為∧1,2。這便是PQ的主合取范式。

第一章---數(shù)理邏輯7/24/202322HongzhiQiao,XidianUniv.用填滿命題變項(xiàng)法,將已為合取范式的P∧Q化為主合取范式。

P∧Q=(P∨(Q∧Q))∧(Q∨(P∧P))

=(P∨Q)∧(P∨Q)∧(Q∨P)∧(Q∨P)

=(P∨Q)∧(P∨Q)∧(P∨Q)

=M2∧M1∧M0

=∧0,1,2第一章---數(shù)理邏輯7/24/202323HongzhiQiao,XidianUniv.極大項(xiàng)的性質(zhì)

(1)對(duì)一個(gè)含有n個(gè)變項(xiàng)的公式來說,所有可能的極大項(xiàng)個(gè)數(shù)和該公式的解釋個(gè)數(shù)一樣多,都是i。

(2)每個(gè)極大項(xiàng)只在一個(gè)解釋下為假。

(3)極大項(xiàng)兩兩不等值,而且Mi∨Mj=T(i≠j)。第一章---數(shù)理邏輯7/24/202324HongzhiQiao,XidianUniv.

推理第一章---數(shù)理邏輯7/24/202325HongzhiQiao,XidianUniv.如果今天我病了,那么我沒來上課。

今天我病了。

所以今天我沒來上課。

這是自然語句給出的三個(gè)命題，有前提有結(jié)論，表示了一種推理關(guān)系。

引入符號(hào)，以P表示"今天我病了",Q表示"我沒來上課"(則第一個(gè)自然語句表示為P→Q)。便可將這推理關(guān)系以條件式

((P→Q)∧P)→Q來表示。第一章---數(shù)理邏輯7/24/202326HongzhiQiao,XidianUniv.也可以用圖式表示:

圖示

這個(gè)條件式或圖式就是一推理形式。說明如果P真,P→Q真,就可推得Q真,這里的P、Q可表任意命題,從而推理形式

((P→Q)∧P)→Q

反映了一類推理關(guān)系。

第一章---數(shù)理邏輯7/24/202327HongzhiQiao,XidianUniv.推理一般分為兩類：演繹推理和歸納推理。凡前提和結(jié)論存在必然聯(lián)系的推理屬于演繹推理，否則屬于歸納推理。古典的數(shù)理邏輯主要研究演繹推理.第一章---數(shù)理邏輯7/24/202328HongzhiQiao,XidianUniv.我們可以給出關(guān)于推理的如下定義：

設(shè)α1，α2，…，αn，β都是命題形式，稱推理"α1，α2，…，αn"推出β是有效的，如果對(duì)α1，α2，…，αn，β中出現(xiàn)的命題變項(xiàng)的任一指派，若α1，α2，…，αn都真，則β亦真，否則，稱"由α1，α2，…，αn推出β"是無效的或不合理的。

另外，在推理形式中，推理形式的有效與否與前提中命題形式的排列次序無關(guān)。第一章---數(shù)理邏輯7/24/202329HongzhiQiao,XidianUniv.命題公式A1，A2，…，An推B的推理正確當(dāng)且僅當(dāng)

(A1∧A2∧…∧An)→B為重言式。

課本P24定義1.4-1常用的推理規(guī)則：（課本上P25）第一章---數(shù)理邏輯7/24/202330HongzhiQiao,XidianUniv.證明方法：1.無義證明法。P假，P→Q為真。2.平凡證明法。Q真，P→Q為真。3.直接證明法。假設(shè)P真→Q真，P→Q為真。4.間接證明法。反證法。第一章---數(shù)理邏輯7/24/202331HongzhiQiao,XidianUniv.構(gòu)造下面推理的證明：如果小張追小李并且小李對(duì)小張有意思，則他們能成為朋友?；蛘咚麄儾怀蔀榕笥?，或者他們成為一對(duì)戀人。他們沒有成為一對(duì)戀人。小張追小李。因此，小李對(duì)小張沒有意思。

解：先將簡(jiǎn)單命題符號(hào)化。

P：小張追小李；Q：小李對(duì)小張有意思；R：他們成為朋友；

S：他們成為一對(duì)戀人。

前提：(P∧Q)→R，