《離散-3-1-命題邏輯.ppt》由會員分享,可在線閱讀,更多相關(guān)《離散-3-1-命題邏輯.ppt(11頁珍藏版)》請在裝配圖網(wǎng)上搜索。
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,H
2、2,,Hn邏輯推出的結(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ī)則): 在推
3、導(dǎo)的任何步驟上所得到的結(jié)論都可在 其后的任何步驟中引入使用。 由基本蘊涵式/基本恒等式得出推理規(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)拒取式,
4、,,證法2: PQ 前提 QR 前提 R 前提 Q (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)
5、 R (3)(5)析取三段論 (7) SR 前提 (8) S (6)(7)拒取式 (9) 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、 前提 (6) R (4)(5)假言推論 (7) R 前提 (8) RR (6)(7),7,應(yīng)用: 邏輯電路設(shè)計(1),1938年C.Shannon的碩士論文第一次把開關(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)
7、合上, 那么,當(dāng)倉庫的門被撬,或當(dāng)工作人員尚未切斷監(jiān)視器電源,且 通向倉庫的通道有人時,就必須報警. P:人工控制開關(guān)合上; Q: 倉庫的門被撬; R:監(jiān)視器電源未切斷; S: 通向倉庫的通道有人; W:報警器響 輸入端: P,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 假言三
8、段論:(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)(PR) P(QR)(PQ)(PR) 德摩根律: (PQ) PQ (PQ) PQ 蘊涵等值式: PQ PQ 等價等值式: PQ (PQ)(QP) 零律: PT T PF F 同一律: PF P PT P,推理理論 反證法,