離散-3-1-命題邏輯.ppt

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

2、結(jié)論。 判斷有效結(jié)論的方法： 證明蘊涵關(guān)系 演繹法：構(gòu)造命題公式的一個有限序列：A1，A2，An 其中： A1是某個前提Hi；Ai(i2)或是某個前提Hi，或是某些Aj(ji)的有效結(jié)論, 并且An就是C，公式C稱為該演繹的有效結(jié)論，或稱從H1，Hn演繹出C。,. -吳揚揚制-,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ī)則): 在推導(dǎo)的任何步驟上所得到的結(jié)論都可在 其后

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

4、(2)(3)拒取式 P (1)(4)拒取式,. -吳揚揚制-,5,1.5 推理理論 3.附加前提法(CP規(guī)則),如果欲推出的結(jié)論為條件式RC時，只需將其前件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) R (3)(5)析取三段論 (7) SR 前提 (8) S (6)(7)拒取式 (9)

5、PS CP規(guī)則,. -吳揚揚制-,6,1.5 推理理論 4.反證法(歸謬法),把結(jié)論的否定作為附加前提，與給定前提一起推證，若能引出矛盾， 則說明結(jié)論是有效的。 要證 A1A2AnB,只需證A1A2AnB是永假式。,蘊涵式 恒等式,A1,A2,An,B不相容,例3：用反證法證明例1的(PQ)(QR)R P。 證明：（1） （P） 附加前提 （2） P (1)雙重否定律 （3） (PQ) 前提 （4） Q (2)(3)假言推論 （5） (QR) 前提 （6） R (4)(5)假言推論 (7) R 前提 (8) RR (6)(7),7,應(yīng)用: 邏輯電路設(shè)計(1),1938年C.Shannon的碩士

6、論文第一次把開關(guān)電路設(shè)計和二值邏輯聯(lián)系起來。 命題變元 - 二值器件，如開關(guān)，電燈，電子管、晶體管等 - 非門、反相器 - 與門,串聯(lián) - 或門,并聯(lián) 化簡電路 電路設(shè)計,非門：,與門：,或門：,描述設(shè)計要求,將設(shè)計要求表示成公式,將公式化簡,畫出邏輯電路圖,. -吳揚揚制-,8,應(yīng)用: 數(shù)字邏輯電路設(shè)計（2）,例：設(shè)計一個報警裝置，其要求是：如果總經(jīng)理室的人工控制開關(guān)合上， 那么，當(dāng)倉庫的門被撬，或當(dāng)工作人員尚未切斷監(jiān)視器電源，且 通向倉庫的通道有人時，就必須報警. P:人工控制開關(guān)合上; Q: 倉庫的門被撬; R:監(jiān)視器電源未切斷; S: 通向倉庫的通道有人; W:報警器響 輸入端: P,

7、Q,R,S; 輸出端:W,W P(Q(RS),P Q R S,W,方法2：,列出輸入/輸出表,構(gòu)造主范式,化簡公式,畫出電路圖,. -吳揚揚制-,9,作業(yè)：P31 1(1)， 2(1)， 3(1),. -吳揚揚制-,10,基本永真蘊涵式：,附加式： P PQ 化簡式： PQ P 假言推論： P(PQ) Q 假言三段論:(PQ)(QR) PR 析取三段論: P(PQ) Q 拒取式： Q(PQ) P,推理規(guī)則 直接證法 附加前提法 反證法,. -吳揚揚制-,11,基本邏輯恒等式（P9）,雙重否定律：P P 補余律：PP T PP F 等冪律：PP P PP P 交換律：PQ QP PQ QP 結(jié)合律:(PQ)R P(QR) (PQ)R P(QR) 分配律: P(QR)(PQ