《《講命題邏輯》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《講命題邏輯》PPT課件.ppt（26頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1.5演繹與推理,命題演算的一個(gè)主要任務(wù)在于提供一種正確的思維規(guī)律，即推理規(guī)則，應(yīng)用此規(guī)則從一些前提中推導(dǎo)出一個(gè)結(jié)論來(lái)，這種推導(dǎo)過(guò)程稱為演繹或形式證明。,,先看如下實(shí)例：,x2是偶數(shù)。,結(jié)論 Q, P,設(shè)x屬于實(shí)數(shù), P: x是偶數(shù), Q: x2是偶數(shù)。,x是偶數(shù)。,例1和例4正確,即：證據(jù)1+證據(jù)2結(jié)論,如果AB是一永真式, 那么稱為永真蘊(yùn)含式, 記為AB, 讀做“A永真蘊(yùn)含B”。,1.2.3 永真蘊(yùn)含式,根據(jù)定義，可以用真值表進(jìn)行證明，如：,所以：P(PQ),永真蘊(yùn)含式除了可以用真值表證明，但也可用以下任一辦法證明: (1) 假定前件是真, 若能推出后件是真, 則此蘊(yùn)含式是真。 (2)
2、假定后件是假, 若能推出前件是假, 則此蘊(yùn)含式是真。,(ii) 若Q是假, 則PQ是假, 所以Q(PQ)是假。故 Q(PQ) P。,例 證明Q(PQ) P,方法1: 設(shè)Q(PQ )是真,,則Q , PQ是真。,所以, Q是假, P是假。,因而P是真。,故Q(PQ ) P,方法2: 設(shè)P是假, 則P是真。以下分情況討論：,(i) 若Q為真, 則Q是假, 所以Q(PQ)是假。,“”與“”的區(qū)別,“”僅是一般的蘊(yùn)涵聯(lián)結(jié)詞，GH的結(jié)果仍是一個(gè)公式，而“”卻描述了兩個(gè)公式G，H之間的一種邏輯蘊(yùn)涵關(guān)系，GH的“結(jié)果”，是非命題公式； 用計(jì)算機(jī)來(lái)判斷GH是辦不到的，然而計(jì)算機(jī)卻可“計(jì)算”公式GH是否為永真公
3、式。,表 1.2 2 永真蘊(yùn)含式,證 A是真時(shí), B和C都真, 所以BC也真。因此ABC永真, 則A BC。,永真蘊(yùn)含式的兩個(gè)性質(zhì),1. 若AB , BC 則AC,這一性質(zhì)也可敘述為: 永真蘊(yùn)含都是傳遞的。,證 AB永真; BC永真, 所以 (AB)(BC)永真。 由公式I6得AC永真, 既A C。,2. 若AB , AC, 則ABC。,證明： A B意味著 A(P1, P2 , ,Pn)B(P1, P2, . , Pn)永真。 則，B(P1,P2,,Pn) A (P1,P2,,Pn)永真。 由定理 1 得 B*(P1,P2,,Pn)A*(P1,P2,,Pn )永真 因?yàn)樯鲜绞怯勒媸? 可以使
4、用代入規(guī)則, Pi代Pi, 1in, 得B* A*。,定理3 如果AB，且A、B為命題變?cè)狿1, P2, , Pn及聯(lián)結(jié)詞、、構(gòu)成的公式, 則B*A*。,推理的邏輯表示,定義:若H1 H2H3HnC,則稱C是H1 ,H2 , H3 , , Hn的有效結(jié)論. 也就是說(shuō),推理的正確在邏輯中就在于結(jié)論與條件之間是永真蘊(yùn)涵關(guān)系.,判斷有效結(jié)論的常用方法,主要的方法有： 1.真值表技術(shù) 2.構(gòu)造證明法 3.間接證明方法,1、真值表技術(shù),前提G1,G2,,Gn和結(jié)論H 如果將P1,P2,,Pn中所有可能的解釋及G1,G2,,Gn，H的對(duì)應(yīng)真值結(jié)果都列在一個(gè)表中，根據(jù)“”的定義，則有判斷方法如下：,對(duì)所有G
5、1,G2,,Gn都具有真值T的行(表示前提為真的行)，如果在每一個(gè)這樣的行中，H也具有真值T，則H是G1,G2,,Gn的邏輯結(jié)果。 對(duì)所有H具有真值為F的行(表示結(jié)論為假的行),如果在每一個(gè)這樣的行中，G1,G2,,Gn中至少有一個(gè)公式的真值為F(前提也為假)，則H是G1,G2,,Gn的邏輯結(jié)果.,,例,判斷下列H是否是前提G1,G2的邏輯結(jié)果 (1)H：Q；G1：P；G2：PQ；,解：建立真值表如下：,根據(jù)上述真值表技術(shù)，有： P (PQ) Q ；,2、構(gòu)造證明法,演繹法是從前提（假設(shè)）出發(fā)，依據(jù)公認(rèn)的推理規(guī)則，推導(dǎo)出一個(gè)結(jié)論來(lái)。 （1）推理規(guī)則 P規(guī)則（稱為前提引用規(guī)則）：在推導(dǎo)的過(guò)程中，
6、可隨時(shí)引入前提集合中的任意一個(gè)前提； 規(guī)則（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)的過(guò)程中，可以隨時(shí)引入公式S，該公式S是由其前的一個(gè)或多個(gè)公式推導(dǎo)出來(lái)的邏輯結(jié)果。 規(guī)則（附加前提規(guī)則）：如果能從給定的前提集合與公式P推導(dǎo)出S，則能從此前提集合推導(dǎo)出PS。,表 1.5 -1 最常用的推理規(guī)則,,,例,某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒(méi)有外出，根據(jù)上述案情可得前提如下： 前提：1.兇手為王某或陳某。PQ 2.如果王某是兇手，則他在作案當(dāng)晚必外出。PR 3.王某案發(fā)之晚并未外出。R 結(jié)論：陳某是兇手。Q 則上述例子可描述為： PR,RP(
7、拒取式) PQ，PQ(析取三段論),證明：令P：馬會(huì)飛；Q：羊吃草； R：母雞是飛鳥；S：那么烤熟的鴨子還會(huì)跑。,如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。所以羊不吃草。,例,證明： SP RSP R拒取式,PQRP (PQ)拒取式 PQ Q簡(jiǎn)化式,,符號(hào)化上述語(yǔ)句為：=PQR,RS,S,G=Q。證明G。,說(shuō)明,這里需要特別注意的是：推理的有效性和結(jié)論的真實(shí)性是不同的，有效的推理不一定產(chǎn)生真實(shí)的結(jié)論；而產(chǎn)生真實(shí)結(jié)論的推理過(guò)程未必是有效的，因?yàn)橛行У耐评碇锌赡馨瑸椤凹佟钡那疤幔鵁o(wú)效的推理卻可能包含為“真”的前提。 由此可見(jiàn)，推理有效性是一回
8、事，前提與結(jié)論的真實(shí)與否是另一回事。所謂推理有效，指的是它的結(jié)論是它的前提的合乎邏輯的結(jié)果。也即，如果它的前提都為真，那么所得的結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧?，如果推理是有效的話，那么不可能它的前提都為真時(shí)，而它的結(jié)論為假。,證明： P（前提引入） P（前提引入） P（前提引入） T，構(gòu)造性二難,構(gòu)造下列推理的證明： 前提： ， ， 結(jié)論：,證明： st P(前提引入) t P(前提引入) s T,拒取式 s r P(前提引入) r T,假言推理 p r P(前提引入) p T,拒取式 pq P
9、(前提引入) q T,析取三段論,用附加前提(CP規(guī)則)證明法證明下面推理。,證明 : P s P（附加前提引入） T，析取三段論 P T，假言推理 P r T，假言推理 CP規(guī)則,3。間接證明（反證法）方法就是：,將結(jié)論的否定加入到前提集合中構(gòu)成一組新的前提，然后證明這組新的前提集合是不相容的，即蘊(yùn)涵一個(gè)矛盾式。,可等價(jià)證明： G1,G2,,Gn,H RR,例,證：(P)P(否定結(jié)論) P PQP Q假言推理 (QR)P QR Q簡(jiǎn)化式 QQ合取式,設(shè)=PQ,(QR),G=P。證明：G。,25,用反證法證明：,證明： P P T，假言推理 P（否定結(jié)論引入） T，替換 T，拒取式 s T，化簡(jiǎn) P T，合取。 由得出了矛盾，根據(jù)反證法說(shuō)明原推理正確。,直接證明法、反證法、帶CP的證明方法之間的關(guān)系：,G1,G2,,Gn G1,G2,,Gn, G1,G2,,Gn () G1,G2,,Gn() G1,G2,,Gn,
《講命題邏輯》PPT課件.ppt
