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

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

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

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

4、二要素命題的二要素真值、陳述句真值、陳述句 例例2： (1) 11+101=1000。 命題命題 (2) 1+x =3。 命題函數(shù)命題函數(shù) Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 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 等價(jià)（雙蘊(yùn)涵等價(jià)（雙蘊(yùn)涵 biimplication, 或雙條件或雙條件bicondition） pq： p等價(jià)等價(jià)q Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 2021-7-1 6 非非 設(shè)設(shè)p是一個(gè)命題，則是一個(gè)命題，則p的的非非命題為命題為 p。 p的的真值真值與與p的真值相反。的真值相反。 例如例如: p： a是是b和和c的最大值。的最大值。 p: a不是不是b和和c的最大值。的最大值。 p與與p的的真值對(duì)應(yīng)關(guān)

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

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

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

9、學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 2021-7-1 11 條件條件 設(shè)設(shè)p和和q是命題，命題是命題，命題“如果如果p，則，則q”稱為蘊(yùn)涵或稱為蘊(yùn)涵或 條件命題，記作條件命題，記作pq。 當(dāng)當(dāng)p為真且為真且q為假為假時(shí)，時(shí)，pq為假為假，否則，否則pq為真。為真。 pq的真值表如下：的真值表如下： pqpq OO1 O11 1OO 111 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 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 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 2021-7-1 13 等價(jià)等價(jià) 設(shè)設(shè)p和和q是命題，命題是命題，命題“p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”稱為稱為p

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

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

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

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

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

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

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

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

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

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

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

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

23、T”(“1”)，就是具有值，就是具有值“F”(“0”)。 v而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè) 變量命題，常稱它為變量命題，常稱它為命題變量命題變量(或或命題變?cè)}變?cè)?，該命，該命 題變量無(wú)具體的真值，它的變域是集合題變量無(wú)具體的真值，它的變域是集合T，F(xiàn)(或或 0，1) v當(dāng)原子命題是命題變?cè)獣r(shí)，此復(fù)合命題也即為命題當(dāng)原子命題是命題變?cè)獣r(shí)，此復(fù)合命題也即為命題 變?cè)淖冊(cè)摹昂瘮?shù)函數(shù)”，且該，且該“函數(shù)函數(shù)”的值仍為的值仍為“真真”或或“假假”值，值， 這樣的函數(shù)可形象地稱為這樣的函數(shù)可形象地稱為“真值函數(shù)真值函數(shù)”,或稱為或稱為命題

24、命題 公式公式,此命題公式?jīng)]有確切真值。此命題公式?jīng)]有確切真值。 Discrete MathematicsHarbin Engineering University CST 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 2021-7-1 25 命題公式（命題公式（statement formula） 1.命題常項(xiàng)命題常項(xiàng)或或命題變?cè)}變?cè)且粋€(gè)公式；是一個(gè)公式； 2.如如A和和B是公式，則表達(dá)式是公式，則表達(dá)式(A)， (AB)，(AB)， (AB)和和 (AB)也是公式；也是公式； 3. 僅用僅用1和和2構(gòu)造的有限長(zhǎng)度的表達(dá)式是公式。構(gòu)造的有限長(zhǎng)度的表達(dá)式是公式。 在不

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

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

27、有命 題變?cè)}變?cè)?，指定指定p1、p2、pn一組真值，則這組真一組真值，則這組真 值稱為值稱為A的一個(gè)的一個(gè)解釋解釋,常記為常記為。 一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有2n個(gè)不同個(gè)不同 的解釋。的解釋。 如果公式如果公式A在解釋下是真的，則稱在解釋下是真的，則稱滿足滿足A；如；如 果果A在解釋下是假的，則稱在解釋下是假的，則稱弄假弄假A。 定義定義 將公式將公式A在其所有可能解釋下在其所有可能解釋下的的真值情況列成真值情況列成 的表，稱為的表，稱為A的的真值表真值表。 Discrete MathematicsHarbin Engineering Universit

28、y CST 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 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 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)校級(jí)精品課離散數(shù)學(xué)離散數(shù)學(xué) 2021-7-1

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

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

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

32、值演算命題邏輯等值演算 定義定義2.12.1 設(shè)設(shè)A A、B B是是公式，公式，如果在任意解釋下，如果在任意解釋下，A A 與與B B的的真值相同真值相同，則稱公式，則稱公式A A、B B是是等等值的值的，記作記作 A AB B。 例：由例：由 A Apqpq，B Bpqpq，A AB B是一個(gè)永真公是一個(gè)永真公 式，則式，則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 哈爾濱工程大學(xué)校級(jí)精品課哈爾濱工程大學(xué)

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

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