湖南大學(xué)離散數(shù)學(xué)教案--命題邏輯.ppt

1、第一章 命題邏輯,楊圣洪引言 邏輯學(xué)是推理的基礎(chǔ)，在社會(huì)學(xué)、自然科學(xué)尤其計(jì)算機(jī)學(xué)科中得到普遍應(yīng)用。 數(shù)理邏輯是邏輯學(xué)的一個(gè)分支，也是數(shù)學(xué)的分支，它用數(shù)學(xué)方法研究推理規(guī)律，它采用符號(hào)的方法來(lái)描述和處理思維形式、思維過(guò)程和思維規(guī)律，它在程序設(shè)計(jì)、數(shù)字電路設(shè)計(jì)、計(jì)算機(jī)原理、人工智能等計(jì)算機(jī)課程得到了廣泛應(yīng)用。 命題邏輯是數(shù)理邏輯的基礎(chǔ)部分， 但究竟什么是命題？ 如何表示命題？ 如何構(gòu)造出復(fù)雜的命題？ 在本章將討論這些問(wèn)題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (1)湖南大學(xué)是一本學(xué)校。 (2)命題邏輯是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程。 (3)命題及聯(lián)結(jié)詞是命題邏輯

2、的最基礎(chǔ)的內(nèi)容。 (4)4是素?cái)?shù)。 (5)湖南大學(xué)坐落于湘江以東。 (6)2011年湖南長(zhǎng)沙輕軌通車(chē)。 其中(1)、(2)、(3) 與事實(shí)相符，是對(duì)的、正確的，稱(chēng)為真命題，或者稱(chēng)命題的值為“真”，簡(jiǎn)記為T(mén)或數(shù)字1。 而(4)、(5)明顯與事實(shí)不相符，是錯(cuò)的、不正確，稱(chēng)為假命題，或稱(chēng)命題的值為“假”，簡(jiǎn)記為F或數(shù)字0。 陳述句(6)的正確性，到2011年12月時(shí)能確定的，若屆時(shí)開(kāi)通了則它是對(duì)的、為真命題，否為假命題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (7) x與y之和為100，其中x為整數(shù)，y為整數(shù) (8)1加1等于10 (7)的對(duì)錯(cuò)不確定的。當(dāng)x為50、y為50時(shí)是對(duì)的

3、，當(dāng)x為51、y為52時(shí)是錯(cuò)的。 (8)的對(duì)錯(cuò)是不確定的，為二進(jìn)制時(shí)正確，當(dāng)為八進(jìn)制、十進(jìn)制時(shí)是錯(cuò)的，因此這兩個(gè)陳述句不是命題。 (9)岳麓山的紅葉真美呀！ (10)動(dòng)作快點(diǎn)！ (11)你是離散數(shù)學(xué)老師嗎？ 這三個(gè)語(yǔ)句不是陳述語(yǔ)句，因此不是命題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (12)我在說(shuō)假話。 (13)我只給自己不能理發(fā)的人理發(fā)。 (14)派出所說(shuō):必須先房子再能上戶(hù)口 單位后勤說(shuō):必須先有戶(hù)口才能分房 你能上到戶(hù)口與要到房子嗎? 這是一個(gè)悖論，其真值不能確定，故不是命題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (13)我既要學(xué)程序設(shè)計(jì)，又要學(xué)離

4、散數(shù)學(xué)。 (14)我們?cè)绮驮诠⑹程没蛲饷嬖琰c(diǎn)攤上吃。 (15)我不是數(shù)學(xué)院的學(xué)生 這三個(gè)陳述句都與事實(shí)相符，是對(duì)的，是真命題，其值為真(T/1)。 其中(13)與(14)可分解為另外二句話的組合， 而(15)是對(duì)“我是數(shù)學(xué)院學(xué)生”的否定，這些語(yǔ)句稱(chēng)為“復(fù)合命題”，不能再分解的語(yǔ)句稱(chēng)為“簡(jiǎn)單命題”或“原子命題”，為了便于推理與書(shū)寫(xiě)，常用小寫(xiě)字母表示簡(jiǎn)單命題或原子命題。,1.1 命題及聯(lián)結(jié)詞 簡(jiǎn)單命題組合成復(fù)雜命題時(shí)所使用的輔助詞稱(chēng)為“聯(lián)結(jié)詞”。 命題邏輯中的聯(lián)結(jié)詞歸納為以下5種。 合?。篊語(yǔ)言中 期末考試后我為年級(jí)第8名，所以老爸應(yīng)該給我買(mǎi)iphone4。這是假言推理。 A(AB)B 從形式上

5、看，結(jié)論B是AB的后件，推導(dǎo)的結(jié)果是將后件分離出來(lái)，故也稱(chēng)為分離原則。 利用假言推理規(guī)則或分離規(guī)則，結(jié)合析取、合取、否定的定義，只要不歉麻煩，幾乎可推出所有的結(jié)論。 為了提高推理效率，還需要學(xué)習(xí)、掌握某些推理規(guī)則。,例題 求證 AAB 采用定義1來(lái)證明，即證明AAB為永真式。 AAB A(AB) (的等值式) (AA)B (結(jié)合律) 1B (析取的性質(zhì)) 1 (析取的性質(zhì)) 所以AAB,例題 求證 ABA ABA (AB)A (的等值式) (AB)A (德摩律) ABA (結(jié)合律) 1B (析取的性質(zhì)) 1 (析取的性質(zhì)) 類(lèi)似 ABB 根據(jù)的定義可知AB為真時(shí)，A與B均為真，因此由推理定義2

6、可知 ABA， AB B 。 同樣由的定義可知A為真時(shí) AB為真，故由推理定義2可知AAB。 然這3個(gè)推理式不必記憶！推理定義2效率較高,例題 求證 (AB)(BC)(AC) 根據(jù)定義1，要證明下式為永真式。 (AB)(BC) (AC) (AB)(BC) (AC) (的等值式) (AB)( BC) (AC) (的等值式) (AB) (BC) (AC) (德摩律) (A B)(A C )(B B) (BC) (AC) (分配律) (A B)(A C )1(BC) (AC) (析取的性質(zhì)) (A B)(A C )(BC) (AC) (析取的性質(zhì)) (A BAC)(A CAC )(BCAC) (分配

7、律) (1 BC)(1 CC )(BA1) (析取的性質(zhì)) 111 (析取的性質(zhì)) 1 (析取的性質(zhì)) 判斷公式的類(lèi)型，除等值演算外，還有真值表與范式等方法。,例題 求證 (AB)(BC)(AC),由上表可知， (AB)(BC) (AC) 為重言式， 由定義1可知(AB)(BC) (AC)。 這是有名的傳遞律，要記住呀！,例題 求證 (AB)(CD)(AC)BD 利用定義1證明了假言推理規(guī)則(AB)AB,傳遞規(guī)則(AB)(BC)(AC)。 有了這2條規(guī)則后,可用定義2來(lái)證明推理式了。 由于這2條規(guī)則的結(jié)論中沒(méi)有析取式，只有條件式，因此將題中結(jié)論轉(zhuǎn)換為 BD,題設(shè)中轉(zhuǎn)換為 (1)(AB)(CD)

8、(AC)為真前提條件(定義2的套路) (2) (AB)為真(1)及合取的性質(zhì) (3) (CD)為真(1)及合取的性質(zhì) (4) (AC)為真(1)及合取的性質(zhì) (5)(BA)為真(2)及(AB) (BA) (6) (AC)為真(4)及(AC) (AC) (7) (BC)為真(5)、(6)及推理傳遞律 (8) (BD)為真(7)、(3)及推理傳遞律 (9) BD為真(8)及(BD) BD,例題 求證 (AB)(CD)(BD)AC 可用傳遞律來(lái)證明，還有更高效的方法 由定義1只要證(AB)(CD)(BD)(AC)為重言式，而 (AB)(CD)(BD)(AC) (AB)(CD)(BD) (AC) (

9、(AB)(CD)(BD)A)C) (AB)(CD)(BD)A)C) (AB)(CD)(BD)A)C 故只需證 (AB)(CD)(BD)A)C為重言式 即只需證明(AB)(CD)(BD)AC A從結(jié)論中挪到前提中，這種技巧稱(chēng)為附加條件(CP)法，適合于結(jié)論為條件式的情形。,例題 求證 (AB)(CD)(BD)AC (1)(AB)(CD)(BD)A為真 CP規(guī)則及前提 (2)AB為真(1)及合取的性質(zhì) (3)A為真(1)及合取的性質(zhì) (4)B為真(2)(3)及假言推理式(AB)AB (5)BD為真(1)及合取的性質(zhì) (6)BD為真(5)及BDBD (7)D為真(4)(6)及假言推理式(BD)BD

10、(8)CD為真(1)及合取的性質(zhì) (9)DC為真(8)及原命題逆否命題 (10)C為真(7)(9)假言推理式(DC)DC 提示：熟練后可不寫(xiě)(1)式，直接引用(2)(3)(5)(8)！,例題 求證 (AB)(CD)(BD)AC (1)AB為真前提條件 (2)A為真附加前提 (3)B為真(1)(2)及假言推理式(AB)AB (4)BD為真前提條件 (5)BD為真(4)及BDBD (6)D為真(3)(5)及假言推理式(BD)BD (7)CD為真前提條件 (8)DC為真(7)及原命題逆否命題 (9)C為真 (6)(8)假言推理式(DC)DC,求證 (WR)V, V(CS),SU,C,UW 提示：此處

11、用逗號(hào)簡(jiǎn)寫(xiě)前述各例中的合取式，從而鼓勵(lì)大家直接引用前提。 利用假言推理、傳遞律及前面所學(xué)的等值式，可以推出結(jié)論。在黑板上演示一番 考慮到本題的結(jié)論是W，可采用反證法。 根據(jù)定義2可知“當(dāng)前提為真時(shí)結(jié)論也為真”， 反證法是“前提為真時(shí)，假設(shè)結(jié)論不為真即結(jié)論的否定為真”。 即基于前提、結(jié)論否定進(jìn)行推理。 如果推出了一個(gè)矛盾的結(jié)論出來(lái)，則說(shuō)明“假設(shè)結(jié)論不為真”是錯(cuò)誤的，即表示結(jié)論只能為真了,求證 (WR)V, V(CS),SU,C,UW (1)W為真假設(shè)結(jié)論W為0即 W為1(真) (2)W為真 (1)與否定的性質(zhì) (3)(WR)為真 (2)與析取的性質(zhì) (4)(WR)V為真前提條件 (5)V為真(4

12、)(3)假言推理(WR)V)(WR) V (6)V(CS)為真前提條件 (7) (CS)為真(5)(6)假言推理(V(CS)V(CS) (8) CS為真 (7)與條件式的等值式CSCS (9)C為真前提條件 (10)S為真(8)(9)與假言推理(CS)( C)S (11) SU為真前提條件 (12)U為真(10)(11)假言推理(SU)SU (13) U為真前提條件 顯然(12)與(13)矛盾，故假設(shè)有誤！,應(yīng)用題 天氣情況要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回來(lái)后不做飯， 結(jié)論是：如果我已做飯那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做

13、飯，則問(wèn)題可表示為 MR，MC，CFFR (MR)(MR) ，MC，CFFR,應(yīng)用題MR，MC，CFFR (1)F為真附件前提 (2)CF為真前提條件 (3)FC為真(2)的等值式 (4) FC為真(3)的等值式 (5) C為真(1)(4)的假言推理 (6) MC為真前提條件 (7)CM為真(6)的等值式 (8) M為真(5)(7)的假言推理 (9) MR為真前提條件 (10) MR為真(9)的等值式 (11) R為真(8)(10)的假言推理,應(yīng)用題MR，MC，CFFR (1)F為真附件前提 (2)CF為真前提條件 (3)FC為真(2)的等值式 (4) FC為真(3)的等值式 (5) C為真(

14、1)(4)的假言推理 (6) MC為真前提條件 (7)CM為真(6)的等值式 (8) M為真(5)(7)的假言推理 (9) (MR)(MR)為真前提條件 (10) (MR) (MR)為真(9)的等值式 (11) MR (MR)為真(10)的等值式 (12) MR為真(8)與析取的定義 (13) (MR)為真(11)(12)的假言推理 (14) R為真(13)與合取的定義,定義2證明推理式的規(guī)律 (1)利用“條件等值式”，盡可能將前提、中間結(jié)論及最終結(jié)論中的“析取式”轉(zhuǎn)換為“條件式”，以便可引用假言推理、傳遞律。 (2)如果結(jié)論為條件式，則將條件式的前件做為附加前提。CP原則 (3)如果結(jié)論的否

15、定在前提中多次出現(xiàn)，可采 用反證法。 (4)每一步的推理理由可簡(jiǎn)化，如“前提條件”簡(jiǎn)寫(xiě)為“P”，“假言推理”可簡(jiǎn)寫(xiě)“M”，等值式只寫(xiě)“等值”或簡(jiǎn)寫(xiě)“E”。 (5)這種從前提出發(fā)，應(yīng)用已證明的推理式，不斷推出中間結(jié)論，最后推出結(jié)論的方式，稱(chēng)為自然推理，這是最常見(jiàn)的方式。,1.7消解規(guī)則 證明(AC)(BC)AB (1) (AC)為真前提條件 (2) A C為真與(1)等值 (3) BC為真前提條件 (4) C B為真與(3)等值 (5)CB為真與(4)等值 (6) AB為真(2)(5)傳遞律 (7) AB為真與(6)等值 因此當(dāng)(AC)(BC)為真時(shí)，AB為真。 由于(AC(BC)中互補(bǔ)的公式C

16、、C同時(shí)消失了，稱(chēng)“AB”為 “(AC)，(BC)”的消解式。 因此在采用定義2進(jìn)行推理時(shí)，只要(AC)、(BC)同時(shí)為真，則可直接寫(xiě)出AB為真，從而節(jié)省大量的中間環(huán)節(jié)，提高了證明效率。,1.7消解規(guī)則 例題 (AB)(CD)(BD)AC 利用條件式的等值式，則此題等價(jià)于證明 (AB)(CD)(BD)AC (1) (AB)為真前提條件 (2) (BD)為真前提條件 (3) AD為真 當(dāng)(1)(2)為真消解式AD為真 (4) CD為真前提條件 (5) AC為真當(dāng)(3)(4)為真消解式AC為真 采用假言推理原則時(shí)，盡可能將析取轉(zhuǎn)換為條件式。 采用消解法時(shí)，盡可能將條件式轉(zhuǎn)換為析取。 消解法是一種高效的方法。 消解法可完成1.6節(jié)中所有推理式,1.7消解規(guī)則 采用定傳遞律證明了(AC)(BC)AB 因AB AB,故可用假言推理及CP原則證明 (1) A為真附加前提 (2) (AC)為真前提條件 (3) A C為真與