《離散-3-1-命題邏輯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散-3-1-命題邏輯.ppt（11頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、. -吳揚(yáng)揚(yáng)制-,1,主要內(nèi)容：,1.5.1 推理理論 推理規(guī)則 常用推理方法 直接證法 附加前提證法 反證法 應(yīng)用：邏輯電路設(shè)計(jì),1.5 推理理論,推理(也稱論證)：由已知命題得到新的命題的思維過程. 邏輯學(xué)中,把從前題(公理或假設(shè))出發(fā),依據(jù)公認(rèn)的推理規(guī)則,推導(dǎo)出結(jié)論, 這一過程稱為有效推理或形式證明, 所得結(jié)論叫做有效結(jié)論.,關(guān)心的不是結(jié)論的真實(shí)性, 而是推理的有效性。,數(shù)理邏輯中，注重的是研究用來從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理， 與這些規(guī)則和原理有關(guān)的理論稱為推理理論。 如果 H1H2 HnC, 則稱C是一組前提H1，H2，，Hn的有效結(jié)論， 或稱C是從前提H1，H

2、2，，Hn邏輯推出的結(jié)論。 判斷有效結(jié)論的方法： 證明蘊(yùn)涵關(guān)系 演繹法：構(gòu)造命題公式的一個(gè)有限序列：A1，A2，，An 其中： A1是某個(gè)前提Hi；Ai(i2)或是某個(gè)前提Hi，或是某些Aj(ji)的有效結(jié)論, 并且An就是C，公式C稱為該演繹的有效結(jié)論，或稱從H1，，Hn演繹出C。,. -吳揚(yáng)揚(yáng)制-,3,1.5 推理理論 1.推理規(guī)則,B稱為推理規(guī)則的結(jié)論。 常用演繹證明方法: 直接證法、附加前提法和間接證法。,在數(shù)理邏輯中，從前提推導(dǎo)出結(jié)論，要依據(jù)事先提供的公認(rèn)的推理規(guī)則。 推理規(guī)則： 規(guī)則P(前提引入規(guī)則): 在推導(dǎo)的任何步驟上都可引入前提。 規(guī)則T(結(jié)論引入規(guī)則): 在推

3、導(dǎo)的任何步驟上所得到的結(jié)論都可在 其后的任何步驟中引入使用。 由基本蘊(yùn)涵式/基本恒等式得出推理規(guī)則 當(dāng)且僅當(dāng) A1A2An B 時(shí)，稱,4,1.5 推理理論 2.直接證法,直接證法: 從前提(一組命題公式)出發(fā)，應(yīng)用推理規(guī)則(蘊(yùn)涵式恒等式)， 推導(dǎo)出結(jié)論（一個(gè)公式）. 例1 證明下列推理有效:如果今天下大雨，則這里難通行；如果這里難通行， 則他們不能準(zhǔn)時(shí)達(dá)到。他們準(zhǔn)時(shí)達(dá)到，所以今天沒下大雨。 證明：設(shè) P: 今天下大雨. Q: 這里難通行. R: 他們準(zhǔn)時(shí)達(dá)到. (PQ)(QR)R P,證法1： PQ 前提 QR 前提 PR (1)(2)假言三段論 R 前提 P (3)(4)拒取式,

4、,,證法2： PQ 前提 QR 前提 R 前提 Q (2)(3)拒取式 P (1)(4)拒取式,. -吳揚(yáng)揚(yáng)制-,5,1.5 推理理論 3.附加前提法(CP規(guī)則),如果欲推出的結(jié)論為條件式RC時(shí)，只需將其前件R加入到前提中, 作為附加前提，再去推出后件C即可。 要證 A1A2An AB, 只需證 A1A2AnA B (A1A2An)(AB) (A1A2An)(AB) (A1A2AnA)B (A1A2AnA)B 例2：證明：P(QR), QP, SR PS,P 附加前提 P(QR) 前提 QR (1)(2)假言推論 QP 前提 Q (1)(4)拒取式,,(6)

5、 R (3)(5)析取三段論 (7) SR 前提 (8) S (6)(7)拒取式 (9) PS CP規(guī)則,,. -吳揚(yáng)揚(yáng)制-,6,1.5 推理理論 4.反證法(歸謬法),把結(jié)論的否定作為附加前提，與給定前提一起推證，若能引出矛盾， 則說明結(jié)論是有效的。 要證 A1A2AnB,只需證A1A2AnB是永假式。,蘊(yùn)涵式 恒等式,A1,A2,,An,B不相容,例3：用反證法證明例1的(PQ)(QR)R P。 證明：（1） （P） 附加前提 （2） P (1)雙重否定律 （3） (PQ) 前提 （4） Q (2)(3)假言推論 （5） (QR)

6、 前提 （6） R (4)(5)假言推論 (7) R 前提 (8) RR (6)(7),7,應(yīng)用: 邏輯電路設(shè)計(jì)(1),1938年C.Shannon的碩士論文第一次把開關(guān)電路設(shè)計(jì)和二值邏輯聯(lián)系起來。 命題變?cè)?--- 二值器件，如開關(guān)，電燈，電子管、晶體管等 --- 非門、反相器 --- 與門,串聯(lián) --- 或門,并聯(lián) 化簡電路 電路設(shè)計(jì),非門：,與門：,或門：,描述設(shè)計(jì)要求,,將設(shè)計(jì)要求表示成公式,,將公式化簡,,畫出邏輯電路圖,. -吳揚(yáng)揚(yáng)制-,8,應(yīng)用: 數(shù)字邏輯電路設(shè)計(jì)（2）,例：設(shè)計(jì)一個(gè)報(bào)警裝置，其要求是：如果總經(jīng)理室的人工控制開關(guān)

7、合上， 那么，當(dāng)倉庫的門被撬，或當(dāng)工作人員尚未切斷監(jiān)視器電源，且 通向倉庫的通道有人時(shí)，就必須報(bào)警. P:人工控制開關(guān)合上; Q: 倉庫的門被撬; R:監(jiān)視器電源未切斷; S: 通向倉庫的通道有人; W:報(bào)警器響 輸入端: P,Q,R,S; 輸出端:W,W P(Q(RS)),P Q R S,,,,,,,,,W,,方法2：,列出輸入/輸出表,,構(gòu)造主范式,,化簡公式,,畫出電路圖,. -吳揚(yáng)揚(yáng)制-,9,作業(yè)：P31 1(1)， 2(1)， 3(1),. -吳揚(yáng)揚(yáng)制-,10,基本永真蘊(yùn)涵式：,附加式： P PQ 化簡式： PQ P 假言推論： P(PQ) Q 假言三

8、段論:(PQ)(QR) PR 析取三段論: P(PQ) Q 拒取式： Q(PQ) P,推理規(guī)則 直接證法 附加前提法 反證法,. -吳揚(yáng)揚(yáng)制-,11,基本邏輯恒等式（P9）,雙重否定律：P P 補(bǔ)余律：PP T PP F 等冪律：PP P PP P 交換律：PQ QP PQ QP 結(jié)合律:(PQ)R P(QR) (PQ)R P(QR) 分配律: P(QR)(PQ)(PR) P(QR)(PQ)(PR) 德摩根律: (PQ) PQ (PQ) PQ 蘊(yùn)涵等值式: PQ PQ 等價(jià)等值式: PQ (PQ)(QP) 零律： PT T PF F 同一律： PF P PT P,推理理論 反證法,