1、1,第一篇數(shù)理邏輯,第一章命題演算 第二章 謂詞演算,2,第一章命題演算,1.1 命題及聯(lián)結(jié)詞 1.2 命題變元與命題公式 1.3 命題演算的公式 1.4 其他聯(lián)結(jié)詞 1.5 范式 1.6 命題演算的推理,3,1.1 命題的概念,在數(shù)理邏輯中，能判斷真假但不能既真又假的陳述 句稱為命題。 對命題的判斷結(jié)果稱為命題的真值。 真值只能取兩個值：真(或1)或假(或)。 真值為真的命題稱為真命題，真值為假的命題稱為假命題。,4,例:判斷下列語句是否是命題,（1）中國是一個國家。 （2）所有素數(shù)都是奇數(shù)。 （3）3是奇數(shù)。 （4）雪是黑色的。 （5）地球外的星球上也有生物。 （）a是大于1的數(shù)。 （）你

2、去哪里？ （）全體立正！ （）請進來！ （10）x+y10,5,命題的類型,原子命題：也稱為原始命題或簡單命題，也就是自然語言中的簡單句。 復(fù)合命題：由幾個簡單命題通過聯(lián)結(jié)詞構(gòu)成的復(fù)雜命題。 例:(1)你看書，我也看書。 (2)燈泡有故障或開關(guān)有故障。 (3) 如果你不去，那么我也不去了。,6,命題的表示,習(xí)慣上，用英文大寫字母A,B,P,Q,或者用帶下標(biāo)的大寫字母來表示命題，這些符號稱為命題標(biāo)識符。 例如： A:中國的首都是北京。 B:9為素數(shù)。 C：若數(shù)a是4的倍數(shù)，則它一定是2的倍數(shù)。,7,命題變元,命題變元：一個任意的沒有賦予具體內(nèi)容的命題。 例如，用P表示任意的命題，則P是命題變元，

3、當(dāng)P用具體命題如“所有素數(shù)都是奇數(shù)”代入后，P就表示命題“所有素數(shù)都是奇數(shù)”。 命題變元沒有確定真值，只有當(dāng)命題變元用一個具體的命題“代入”時，它才有確定的真值。 指派：用一個具體的命題“代入”命題變元，也稱為對命題變元進行指派。,8,聯(lián)結(jié)詞,要求掌握各聯(lián)結(jié)詞所表示的含義、符號、真值表。 1.否定 2.合取：相當(dāng)于 (2)如果P是公式,則( P)是公式; (3)如果P,Q是公式,則(P Q),(PQ),(PQ), ( )是公式; (4)公式由且僅由有限次使用(1),(2),(3)而得.,命題公式是一個合理運用命題變元、命題聯(lián)結(jié)詞及括號所得到的符號串。,22,命題公式,如果P，Q和R是原子命題，

4、則 , (P QR) ，(P QR) ，(P Q ) (PQ) ， (P R) Q) 公式最外層括號可省略。,都是命題公式。,等都不是命題公式。,23,指派,定義 命題變元的一組確定的值(它由若干個T及F組成)叫做公式的一個指派。每個指派對應(yīng)公式的一個確定的值。,在含有2個命題變元的命題公式中，2個命題變元共有4組不同的指派。在含有3個命題變元的命題公式中，3個命題變元共有8組不同的指派。 一般地講: 在含有n個命題變元的命題公式中，n個命題變元共有 組不同的指派。,24,練習(xí):命題公式（P Q） R）P的真值表？,25,永真公式與永假公式,定義 如果對命題公式中命題變元進行任意一組不同指派，

5、其真值總是T，則稱這樣的命題公式為永真公式或重言式，記作T 。 定義 如果對命題公式中命題變元進行任意一組不同指派，其真值總是F，則稱這樣的命題公式為永假公式或矛盾式，并記作F 。 定義 如果命題公式至少存在一個指派使其真值為T，則稱這樣的命題公式為可滿足公式。,26,例1:命題公式P Q的真值表如下所示。,由上表可知P Q是可滿足公式。,27,例2:命題公式（P Q） P，其真值表如下所示。,P Q P Q （P Q） P F F F T F T F T T F F T T T T T 由表可知，（P Q） P是重言式。,28,例3:命題公式 （P （P Q），其真值表如下所示。,P Q P

6、 （ P Q ） （P （ P Q） F F T F F T T F T F T F T T T F 由表可知，（P （P Q）是矛盾式。,29, 1-3 命題演算的關(guān)系,1.命題間的等價關(guān)系 定義：設(shè)公式P、Q，在對于兩個公式中所有命題變元的任意一組指派，兩個公式P和Q都具有相同的真值，則稱P,Q是等價的命題，或P和Q邏輯等價，記為 。,注：有些書又將公式的等價關(guān)系稱為公式相等,30,例：命題公式P Q和 P Q，它們的真值表如下,由表可知，,T,T,T,T,F,F,T,T,31,注意事項:,與 是不同的， 表示的是公式間的關(guān)系，它不是聯(lián)結(jié)詞， 是聯(lián)結(jié)詞。 等價關(guān)系的特性： 1.自反性： 2

7、.對稱性：若 ，則 3.傳遞性：若 ， ，則,32,常用的邏輯等式,33,常用的邏輯等式,否定深入,34,常用的邏輯等價式,35,常用的邏輯等式,36,常用的邏輯等式,37,證明兩個命題公式等價的方法,要證明兩個命題公式是等價的，不僅可以用真值表法，也可以用基本等式，通過“演算”來證明兩個命題公式是相等的。 證明兩個命題公式相等的兩種方法 1.真值表法 2.等價演算,38,例1： 證明下列邏輯等式。等價演算,39,例：試證語句“不會休息的人也不會工作，沒有豐富知識的人也不會工作” ，與語句“工作得好的人一定會休息并且有豐富的知識”具有相同的邏輯含義。,解：設(shè)P：某人工作得好，Q：某人會休息，

8、R：某人有豐富知識，則第一個語句可符號化為,所以上述兩個語句含義相同,第二個語句可符號化為,40,蘊含關(guān)系(重言蘊含),定義：當(dāng)且僅當(dāng)命題AB是邏輯真時(即AB T)，稱“A蘊含B”，表示為： 蘊含關(guān)系的特征 1.自反性： 2.反對稱性：若 ， ，則 3.傳遞性：若 ， ，則,41,常用的蘊含重言式（理解）,重要的蘊涵關(guān)系公式參看書12 表1-3-2,42,基本聯(lián)結(jié)詞的對偶符號,對偶：是對聯(lián)結(jié)詞或公式的一種操作。符號為“*”； 其中：*=，*= ，*= ， T*=F， F*=T,基本聯(lián)結(jié)詞： ，。 聯(lián)結(jié)詞 和 可以利用公式化為基本聯(lián)結(jié)詞。,43,對偶公式,定義 設(shè)A是命題公式，且A中僅有聯(lián)結(jié)詞

9、 ， 。在A中把，F(xiàn)，T分別換成， T，F(xiàn)后所得的命題公式 稱為A的對偶公式。 問：（A*）*=,A,44,練習(xí),例如，命題公式P（ QR）的對偶公式為 P（ QR） 。,命題公式（ PT）Q的對偶公式為,（ PF）Q。,45,練習(xí)：,寫出下列式子的對偶公式并化簡 1. 2. 3.,46,1-5 范式,1 析取范式 定義 如果一個命題公式可等價地表示為 其中 都是命題變元或其否定的所組成的合取式，則稱這種表示形式為析取范式。 例如， 是析取范式。 但是， 不是析取范式， 因為（P Q）和（ ）都不是合取式。,47,求命題公式的析取范式的步驟：,(1）首先把命題公式中的各類聯(lián)結(jié)詞轉(zhuǎn)化為， 。 （

10、2）利用德摩根律，把聯(lián)結(jié)詞否定“ ”置于各個命題變元的前面,并利用雙重否定律減少否定符號。 （3）利用分配律和結(jié)合律把命題公式轉(zhuǎn)化為析取范 式。注意：求析取范式利用對 的分配律;,48,例1 求命題公式,的析取范式,解:,由此得到,的析取范式為,49,析取范式的特性,一公式為矛盾式的充分必要條件是其析取范式的每一析取項中均必同時包括一命題變元及其否定。,50,練習(xí),課后題1.19 （5）,51,主析取范式,定義在含有n個變元的合取式中，每個命題變元和其否定不同時存在，而兩者之一必出現(xiàn)且僅出現(xiàn)一次，則稱此合取式為小項 例如：對而言， PQ，PQ， P Q PP 對而言， P Q， PQR， PQ

11、,即：每個命題變元必須出現(xiàn)一次，但是要么只能以肯定形式出現(xiàn)，要么只能以否定形式出現(xiàn)。,不是小項,都是小項,不是小項,都是小項；,52,小項,由于每個命題變元或以原形或以否定形式出現(xiàn)且僅出現(xiàn)一次，因而n個命題變元共可產(chǎn)生 個不同的小項.,若在最小項中，將命題變元的原形對應(yīng)T，否定形對應(yīng)F，則每個最小項對應(yīng)一個指派，該指派正是使對應(yīng)的最小項取真值T的唯一的指派，而除此之外的所有指派必使對應(yīng)的最小項為F.,例如:3個變元P，Q，R的小項有8個，使每個小項的真值為T的指派分別如下:,53,(F，F(xiàn)，F(xiàn)),(F，F(xiàn)，T),(F，T，F(xiàn)),(F，T，T),(T，F(xiàn)，F(xiàn)),(T，F(xiàn)，T),(T，T，F(xiàn)),(

12、T，T，T),54,主析取范式,定義 對于一個含有n個變元的命題公式，如果已表示成析取范式，且該析取范式中的每一個合取項都是小項，則稱此析取范式為主析取范式。 求命題公式的主析取范式的方法： （1）求出命題公式的析取范式； （2）利用等價式 對缺少某些命題變元如P，Q等的合取項，用P P，Q Q等補上； （3）再用分配和結(jié)合律展開，并合并相同的合取項后，就得到主析取范式。,55,例3：求P（Q P）的主析取范式。,解：先把命題公式P （Q P）轉(zhuǎn)化為析取范式。,56,例4：求（P Q） R的主析取范式。,57,練習(xí),課后題1.20 （2）,58,用真值表求主析取范式,定理:一公式的真值表中，使

13、其真值為T的指派所對應(yīng)的小項而形成的析取式即為此公式的主析取范式。,求主析取范式的兩種方法: 1.利用基本等式推出 2.利用真值表,59,用真值表求主析取范式,表 P Q R （P Q） R F F F F F F T T F T F F F T T T T F F F T F T F T T F F T T T T 上表是前面例4的（P Q） R的真值表 。由表可知，,60,例5：求 的主析取范式。解 先列出公式的真值表如下:,P Q R （P Q） R F F F T F F T F F T F T F T T F T F F T T F T F T T F F T T T T 由表可知，

14、因此所求的主析取范式為 （ P Q R）（ P Q R） （P Q R）（P Q R）。,61,1-5 范式,2合取范式 定義 如果一個命題公式可等價地表示為 其中 都是由命題變元或其否定所組成的析取式，則稱這種表示形式為合取范式。 例如，（P Q）（ P R）（Q R）是合取范式。 （P Q）（P Q）（R Q） P Q，P Q，R Q都不是析取式。,不是合取范式，,62,求命題公式的合取范式的方法,（1）首先把命題公式中各類聯(lián)結(jié)詞轉(zhuǎn)化為，； （2）利用摩根律把否定詞 置于各個命題變元的前面； （3）利用結(jié)合律和分配律（對的分配），把命題公式轉(zhuǎn)化為合取范式。,63,例6：求命題公式（P Q）

15、（R S）的合取范式。,解 首先把命題公式中的聯(lián)結(jié)詞轉(zhuǎn)化為，有,64,例7：求 合取范式。,解 因為 ，所以,65,練習(xí),1.18 （5）,66,主合取范式,定義如果有個析取式含有n個變元，其中每個命題變元和其否定不同時存在，而兩者之一必出現(xiàn)且僅出現(xiàn)一次，則稱此析取式為大項 例如：對，而言， P Q，P Q， P Q都是大項； 對，而言， P Q ， P Q 都是大項，但P Q不是大項,67,主合取范式,定義 如果在一個含有n個變元的命題公式的合取范式中，每一項都是大項，則稱這個合取范式為主合取范式。 求命題公式的主合取范式的方法： （1）求出命題公式的合取范式； （2）利用等價式 把合取范式

16、的析取項中缺少的某些變元如P，Q等，用P P和Q Q等補上； （3）利用分配律（對的分配）展開，合并相同的析取項后即得主合取范式。,68,例8：求 的主合取范式。,69,練習(xí),課后題1.21（2）,70,用真值表求主析取范式,定理1.5.2:一公式的真值表中，使其真值為F的指派所對應(yīng)的大項而形成的析取式即為此公式的主合取范式。,求主合取范式的兩種方法: 1.利用基本等式推出 2.利用真值表,71,3用真值表求 主合取范式,72,1-6 命題演算的推理,推理是從前提得到結(jié)論的過程。 前提是指已知的命題公式。 結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。,73,邏輯結(jié)論,若(A1A2 Ak)B為重

17、言式,即： (A1A2 Ak)=B,則稱A1,A2,Ak推結(jié)論B的推理正確,B是A1,A2,Ak的邏輯結(jié)論或有效結(jié)論. 所以判斷推理(A1A2 Ak)=B是否正確的方法就是判斷(A1A2 Ak)B是否為重言式.可以使用：真值表法,等值演算法等.,74,例：如果天氣涼快,小王就不去游泳.天氣涼快,所以小王沒去游泳.,解上述類型的推理問題,應(yīng)先將命題符號化,然后寫出前提、結(jié)論和推理的形式結(jié)構(gòu),最后進行判斷. (1)P：天氣涼快; Q：小王去游泳. 前提：PQ, P. 結(jié)論： Q. 推理的形式結(jié)構(gòu)為 (PQ)P) Q. (*) 判斷(*)是否為重言式.,75,真值表法,真值表的最后一列全為T,因而(*)是重言式.所以推理正確.,76,等值演算法,(PQ)P) Q (PQ) P) Q (P Q) P) Q (P P ) ( Q P) Q (Q P) Q ( QQ ) P T,77,思考題：,用等價演算法判斷如下推理正確與否？ 若今天不是