第1章 命題邏輯(class-1)

1、Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 1 2021-7-11-20 離離 散散 數(shù)數(shù) 學學 王燕王燕 計算機軟件與理論研究所計算機軟件與理論研究所 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 2 命題（命題（Proposition） 具有具有確切真值確切真值的陳述句稱為的陳述句稱為命題命題,該命題

2、可以該命題可以 取一個取一個“值值”，稱為，稱為真值真值。 真值只有真值只有“真真”和和“假假”兩種，分別用兩種，分別用“”(或或 “”)和和“”(或或“”)表示。表示。 1.1 命題與命題聯(lián)結詞命題與命題聯(lián)結詞 用用英文字母英文字母表示命題，如：表示命題，如：p p、q q、rr 或或 P P、Q Q、RR Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 3 例例1.1命題表示命題表示 p: p: 離散數(shù)學是計算機系學生的必修課離散數(shù)學是計算機系學生

3、的必修課 q: q: 李某是計算機系的學生李某是計算機系的學生 r: r: 李某（選）修（了）離散數(shù)學課程李某（選）修（了）離散數(shù)學課程 s: s: 離散數(shù)學不是計算機系學生的必修課離散數(shù)學不是計算機系學生的必修課 注意：p與s的真值關系：互相否定 真值情況真值情況: : p p的真值取的真值取 1 1 q q、r r的真值的真值由李某由李某的情況的情況確定確定 s s的真值取的真值取 0 0 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 4 命題的

4、二要素命題的二要素真值、陳述句真值、陳述句 例例2： (1) 11+101=1000。 命題命題 (2) 1+x =3。 命題函數(shù)命題函數(shù) Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 5 命題聯(lián)接詞（命題聯(lián)接詞（logical connectives） 非（非（negation） p：非非p 合?。ê先。╟onjunction） pq： p并且并且q 析?。ㄎ鋈。╠isjunction） pq： p或者或者q 條件（條件（implication,或

5、或condition） pq： 若若p則則q 等價（雙蘊涵等價（雙蘊涵 biimplication, 或雙條件或雙條件bicondition） pq： p等價等價q Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 6 非非 設設p是一個命題，則是一個命題，則p的的非非命題為命題為 p。 p的的真值真值與與p的真值相反。的真值相反。 例如例如: p： a是是b和和c的最大值。的最大值。 p: a不是不是b和和c的最大值。的最大值。 p與與p的的真值對應關

6、系真值對應關系如下表（真值表）：如下表（真值表）： p p O1 1O Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 7 合取合取 設設p和和q是命題，則是命題，則p和和q的合取記作的合取記作pq，稱為，稱為 “p并且并且q”。 命題命題pq為真為真的條件是的條件是p和和q同為真同為真，否則，否則pq 為假。為假。 pq的真值表如下：的真值表如下： pqpq OOO O1O 1OO 111 Discrete MathematicsHarbin Eng

7、ineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 8 合取命題示例合取命題示例 若若 令令 p： a b 。 q： a c 。 則則 pq表示命題：表示命題： a b 且且 a c 。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 9 析取析取 設設p、q是命題，其析取記作是命題，其析取記作pq，稱為，稱為 “p或者或者 q”。 命題命題pq為真為真當且僅當當且僅當p，

8、q中至少一個為真。中至少一個為真。 pq的真值表如下：的真值表如下： pqpq OOO O11 1O1 111 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 10 析取命題示例析取命題示例 若令：若令： p： a = b ； q： a = c。 則則 pq表示命題：表示命題： a = b 或或 a = c。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大

9、學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 11 條件條件 設設p和和q是命題，命題是命題，命題“如果如果p，則，則q”稱為蘊涵或稱為蘊涵或 條件命題，記作條件命題，記作pq。 當當p為真且為真且q為假為假時，時，pq為假為假，否則，否則pq為真。為真。 pq的真值表如下：的真值表如下： pqpq OO1 O11 1OO 111 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 12 條件命題示例條件命題示例 令：令：p： a是是b和和c的最大值。的

10、最大值。 q： a b 。 r： a c 。 s： a = b。 u： a = c。 （1）p（ q r）表示命題：）表示命題： 如果如果a是是b和和c的最大值，則的最大值，則a b 且且 a c 。 （2）p（ su）表示命題：）表示命題： 如果如果a是是b和和c的最大值，則的最大值，則a = b 或或 a = c。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 13 等價等價 設設p和和q是命題，命題是命題，命題“p當且僅當當且僅當q”稱為稱為p

11、與與q的的 等價（雙條件等價（雙條件/雙蘊涵），記作雙蘊涵），記作pq。 pq在在p和和q具有具有相同真值相同真值時時為真為真，否則為假。，否則為假。 p q的真值表如下：的真值表如下： PQP Q OO1 O1O 1OO 111 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 14 等價命題示例等價命題示例 若令：若令： p：8是偶數(shù)。是偶數(shù)。 q：8能被能被2整除。整除。 則則 pq表示命題：表示命題： 8是偶數(shù)當且僅當是偶數(shù)當且僅當8能被能被2整

12、除。整除。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 15 命題表示命題表示 區(qū)別： r r （pqpq）與（ r p)qr p)q 國家留學基金委選派碩士留學生的條件是：國家留學基金委選派碩士留學生的條件是： PETS5成績合格（總分成績合格（總分55分，其中聽力分，其中聽力18分，口語分，口語 3分），具有學士學位分），具有學士學位或或優(yōu)秀應屆本科畢業(yè)生。優(yōu)秀應屆本科畢業(yè)生。 p：小張具有學士學位；：小張具有學士學位； q：小張是優(yōu)秀應屆本科

13、畢：小張是優(yōu)秀應屆本科畢 業(yè)生；業(yè)生；r：小張：小張PETS5成績合格。成績合格。 命題表示為：命題表示為： r （pq） Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 16 一般來說，命題可分兩種類型：一般來說，命題可分兩種類型： 原子命題原子命題(簡單命題簡單命題)：不能再：不能再分解分解為更為簡單命題為更為簡單命題 的命題。的命題。 復合命題復合命題：可以：可以分解分解為更為簡單命題的命題。而且為更為簡單命題的命題。而且 這些簡單命題之間是通過

14、如這些簡單命題之間是通過如“或者或者”、“并并 且且”、“不不”、“如果如果.則則.”、“當且僅當當且僅當” 等這樣的關聯(lián)詞和標點符號復合而構成一個復等這樣的關聯(lián)詞和標點符號復合而構成一個復 合命題。合命題。 命題的分類命題的分類 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 17 命題聯(lián)結詞的應用命題聯(lián)結詞的應用 數(shù)字邏輯中與命題聯(lián)接詞對應的門電路：數(shù)字邏輯中與命題聯(lián)接詞對應的門電路： PQP P Q 設：設： ：開關閉合；：開關閉合。：開關閉合；

15、：開關閉合。 ABABABABA A Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 18 命題符號化命題符號化 n命題符號化過程命題符號化過程 分析并分析并確定原子命題確定原子命題，用大寫或小寫字母表，用大寫或小寫字母表 示；示； 對于復合命題中的連詞，對于復合命題中的連詞，確定確定具有相同邏輯具有相同邏輯 含義的命題含義的命題聯(lián)接詞；聯(lián)接詞； 按照語句的順序關系，將命題符號化表示；按照語句的順序關系，將命題符號化表示； 比較符號化后的命題與自然語言

16、命題的真值比較符號化后的命題與自然語言命題的真值 對應關系，檢查符號化命題的準確性。對應關系，檢查符號化命題的準確性。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 19 例例1.6 將下列命題符號化將下列命題符號化 1.小張既聰明又用功。小張既聰明又用功。 2.小張雖聰明但不用功。小張雖聰明但不用功。 3.除非你努力，否則你將失敗。除非你努力，否則你將失敗。 4.小張或小林都可以做這件事。小張或小林都可以做這件事。 5.我們不能既劃船又跑步。我們不

17、能既劃船又跑步。 6.僅當你走我將留下。僅當你走我將留下。 7.如果小張和小林都不做這些工作，我就做。如果小張和小林都不做這些工作，我就做。 8.假如上午不下雨，我去看電影，否則就在家里讀假如上午不下雨，我去看電影，否則就在家里讀 書或看報。書或看報。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 20 例例1.6 題解（題解（1） 1.小張既聰明又用功。小張既聰明又用功。 解：設解：設p：小張聰明。：小張聰明。 q：小張用功。：小張用功。 自然語言

18、中自然語言中“既既又又.”與與“且且”意義一樣，故命題意義一樣，故命題 可符號化為：可符號化為： pq 2.小張雖聰明但不用功。小張雖聰明但不用功。 解：這里解：這里“雖雖.但但”所表達的實際意義是：所表達的實際意義是： 小張聰明且不用功。故命題可符號化為：小張聰明且不用功。故命題可符號化為： p q Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 21 例例1.6 題解（題解（2） 3.除非你努力，否則你將失敗。除非你努力，否則你將失敗。 解：設解：

19、設p：你努力。：你努力。 q：你失敗。：你失敗。 這個命題可理解為：如果你不努力，則你將失敗。這個命題可理解為：如果你不努力，則你將失敗。 故命題可符號化為：故命題可符號化為： pq 4.小張或小林都可以做這件事。小張或小林都可以做這件事。 解：設解：設 p：小張可以做這件事。：小張可以做這件事。 q：小林可以做這件事：小林可以做這件事 這個命題可理解為：這個命題可理解為：小張可以做這件事，并且小林也可以小張可以做這件事，并且小林也可以 做這件事。做這件事。 故命題可符號化為：故命題可符號化為： pq Discrete MathematicsHarbin Engineering Univers

20、ity CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 22 例例1.6 題解（題解（3） 5.我們不能既劃船又跑步。我們不能既劃船又跑步。 解：設解：設p：我們劃船。：我們劃船。q：我們跑步。：我們跑步。 故命題可符號化為：故命題可符號化為： (pq) 6.僅當你走我將留下。僅當你走我將留下。 解：設解：設p：你走。：你走。q：我留下。：我留下。 “僅當僅當”所表達的是必要條件。故命題可符號化為：所表達的是必要條件。故命題可符號化為： q p Discrete MathematicsHarbin Engineering University CST

21、 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 23 例例1.6 題解（題解（4） 7.如果小張和小林都不做這些工作，我就做。如果小張和小林都不做這些工作，我就做。 解：設解：設 P：小張做這些工作。小張做這些工作。Q：小林做這些工作。小林做這些工作。 R：我做這些工作。我做這些工作。 故命題可符號化為：故命題可符號化為： （ P Q）R 8.假如上午不下雨，我去看電影，否則就在家里讀書或看報。假如上午不下雨，我去看電影，否則就在家里讀書或看報。 解：設解：設 P：上午下雨。：上午下雨。 Q：我去看電影。：我去看電影。 R：我在家里讀書。：我在家里讀書。S

22、：我在家里看報。：我在家里看報。 這個命題可理解為：這個命題可理解為：如果上午不下雨，則我去看電影；如果如果上午不下雨，則我去看電影；如果 上午下雨，則我在家里讀書或看報。上午下雨，則我在家里讀書或看報。 故命題可符號化為：故命題可符號化為： （ PQ） （P (RS) Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 24 1.2 命題公式及其賦值命題公式及其賦值 v一個特定的命題是一個一個特定的命題是一個常值命題常值命題，它不是具有值它不是具有值 “

23、T”(“1”)，就是具有值，就是具有值“F”(“0”)。 v而一個任意的沒有賦予具體內容的原子命題是一個而一個任意的沒有賦予具體內容的原子命題是一個 變量命題，常稱它為變量命題，常稱它為命題變量命題變量(或或命題變元命題變元)，該命，該命 題變量無具體的真值，它的變域是集合題變量無具體的真值，它的變域是集合T，F(xiàn)(或或 0，1) v當原子命題是命題變元時，此復合命題也即為命題當原子命題是命題變元時，此復合命題也即為命題 變元的變元的“函數(shù)函數(shù)”，且該，且該“函數(shù)函數(shù)”的值仍為的值仍為“真真”或或“假假”值，值， 這樣的函數(shù)可形象地稱為這樣的函數(shù)可形象地稱為“真值函數(shù)真值函數(shù)”,或稱為或稱為命題

24、命題 公式公式,此命題公式沒有確切真值。此命題公式沒有確切真值。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 25 命題公式（命題公式（statement formula） 1.命題常項命題常項或或命題變元命題變元是一個公式；是一個公式； 2.如如A和和B是公式，則表達式是公式，則表達式(A)， (AB)，(AB)， (AB)和和 (AB)也是公式；也是公式； 3. 僅用僅用1和和2構造的有限長度的表達式是公式。構造的有限長度的表達式是公式。 在不

25、產生混淆的情況下，為了避免公式中使用太多的在不產生混淆的情況下，為了避免公式中使用太多的 括號，約定省略最外層括號。括號，約定省略最外層括號。 注：命題公式也稱為良態(tài)公式（注：命題公式也稱為良態(tài)公式（well-formed formula, wff） Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 26 命題公式的解釋和真值表命題公式的解釋和真值表 設設p1、p2、pn是出現(xiàn)在公式是出現(xiàn)在公式A中的所有命題變中的所有命題變 量量，指定指定p1、p2、p

26、n一組真值，則這組真一組真值，則這組真 值稱為值稱為A的一個的一個解釋解釋,常記為常記為。 若有個命題變元，則應有若有個命題變元，則應有2n個不同的解釋。個不同的解釋。 將公式將公式A在其所有可能解釋下在其所有可能解釋下的的真值情況列成真值情況列成的的 表，稱為表，稱為A的的真值表真值表。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 27 公式的解釋與真值表公式的解釋與真值表 定義定義 設設p1、p2、pn是出現(xiàn)在公式是出現(xiàn)在公式A中的所有命中的所

27、有命 題變元題變元，指定指定p1、p2、pn一組真值，則這組真一組真值，則這組真 值稱為值稱為A的一個的一個解釋解釋,常記為常記為。 一般來說，若有個命題變元，則應有一般來說，若有個命題變元，則應有2n個不同個不同 的解釋。的解釋。 如果公式如果公式A在解釋下是真的，則稱在解釋下是真的，則稱滿足滿足A；如；如 果果A在解釋下是假的，則稱在解釋下是假的，則稱弄假弄假A。 定義定義 將公式將公式A在其所有可能解釋下在其所有可能解釋下的的真值情況列成真值情況列成 的表，稱為的表，稱為A的的真值表真值表。 Discrete MathematicsHarbin Engineering Universit

28、y CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 28 例例 p q (pq)p (pq)p (p q) (pq) 0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面這組公式的真值表：求下面這組公式的真值表： A A1 1 (pq)p(pq)p； A A2 2(pq)p(pq)p； A A3 3 (p (p q)q) (pq)(pq)。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1

29、 29 從這三個真值表可以看到一個非常有趣的事實：從這三個真值表可以看到一個非常有趣的事實： 公式公式G G1 1對所有可能的解釋具有對所有可能的解釋具有“真真”值值 公式公式G G3 3對所有可能的解釋均具有對所有可能的解釋均具有“假假”值值 公式公式G G2 2則具有則具有“真真”和和“假假”值值 結論結論 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 30 定義定義 公式公式A稱為稱為永真公式永真公式(重言式重言式)，如果在它的，如果在它的所有

30、所有 解釋解釋之下都為之下都為“真真”。 公式公式A稱為稱為永假公式永假公式(矛盾式矛盾式),如果在它的如果在它的所有解所有解 釋釋之下都為之下都為“假假”。 公式公式A稱為稱為可滿足的可滿足的，如果它，如果它不是永假不是永假的。的。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 31 從上述定義可知三種特殊公式之間的關系：從上述定義可知三種特殊公式之間的關系： 永真式永真式A A的否定的否定 A A是矛盾式；矛盾式是矛盾式；矛盾式A A的否定的否定

31、 A A 是永真式。是永真式。 永真式一定是可滿足式永真式一定是可滿足式, ,可滿足式不一定是永真可滿足式不一定是永真 式式 可滿足式的否定不一定為不可滿足式可滿足式的否定不一定為不可滿足式( (即為矛盾即為矛盾 式式) ) 如果公式如果公式A A在解釋下是真的，則稱滿足在解釋下是真的，則稱滿足A A； 如果如果A A在解釋下是假的，則稱弄假于在解釋下是假的，則稱弄假于A A。 結論結論 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 32 命題邏輯等

32、值演算命題邏輯等值演算 定義定義2.12.1 設設A A、B B是是公式，公式，如果在任意解釋下，如果在任意解釋下，A A 與與B B的的真值相同真值相同，則稱公式，則稱公式A A、B B是是等等值的值的，記作記作 A AB B。 例：由例：由 A Apqpq，B Bpqpq，A AB B是一個永真公是一個永真公 式，則式，則A AB B p q p q pq (p q) (pq) 0 0 1 11 0 1 1 11 1 00 01 1 11 11 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學

33、校級精品課離散數(shù)學離散數(shù)學 2021-7-1 33 “” 與與“”的區(qū)別的區(qū)別 首先首先，等價的等價的“”是一種邏輯聯(lián)結詞，公式是一種邏輯聯(lián)結詞，公式 A AB B是命題公式，其中是命題公式，其中“”是一種邏輯運算，是一種邏輯運算， A AB B的結果仍是一個命題公式的結果仍是一個命題公式。而邏輯等價而邏輯等價“” 則是描述了兩個公式則是描述了兩個公式A A與與B B之間的一種邏輯等之間的一種邏輯等值值-關關 系的描述系的描述，A AB B表示表示“命題公式命題公式A A與命題公式與命題公式B B是是等等 值的值的”，A AB B 的結果不是命題公式的結果不是命題公式。 其次，如果要求用計算機

34、來判斷命題公式其次，如果要求用計算機來判斷命題公式A A、B B 是否邏輯等值，即是否邏輯等值，即A AB B那是辦不到的那是辦不到的，然而計算機然而計算機 卻可卻可“計算計算”公式公式A AB B是否是永真公式。是否是永真公式。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 34 “”的性質的性質 由于由于“”不是一個聯(lián)結詞，而是一種關不是一個聯(lián)結詞，而是一種關 系，為此，這種關系具有如下三個性質：系，為此，這種關系具有如下三個性質： （1）自反性）自反性 AA； （2）對稱性）對稱性 若若AB，則，則BA； （3）傳遞性）傳遞性 若若AB，BC，則，則AC。 這三條性質體現(xiàn)了這三條性質體現(xiàn)了“”的實質含義。的實質含義。 作業(yè)作業(yè) Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學校級精品課哈爾濱工程大學校級精品課離散數(shù)學離散數(shù)學 2021-7-1 35 設設A，B，S