1、離散數(shù)學(xué)數(shù)理邏輯第1頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五1教材與參考資料教材： 離散數(shù)學(xué) （第2版），屈婉玲、耿素云、張立昂編，清華大學(xué)出版社參考資料：離散數(shù)學(xué)，劉玉珍、劉詠梅編，武漢大學(xué)出版社Discrete Mathematical Structures(Sixth Edition)， Bernard Kolman, Fobert C. Busby and Sharon Ross ，高等教育出版社有影印版、譯本Discrete Mathematics and Its Applications(Sixth Edition)，美Kenneth H. Rosen，機(jī)械工業(yè)出

2、版社影印版、譯本第2頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五2課程主要內(nèi)容數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)* 第3頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五3目的、意義和要求研究內(nèi)容：離散量的結(jié)構(gòu)及其相互間的關(guān)系。意義：計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。目的：打基礎(chǔ)必備的數(shù)學(xué)知識(shí)培養(yǎng)抽象思維能力、邏輯推理能力教學(xué)內(nèi)容：第1-7 章重點(diǎn)第9、14章備選第8、11章自學(xué)第10、12、13章不要求 第4頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五4學(xué)習(xí)要求1、課堂要求： 按時(shí)上課 認(rèn)真聽講2、課外要求： 復(fù)習(xí)(每次課后，安排半個(gè)小時(shí)) 認(rèn)真、按時(shí)完成作業(yè)(每次課后，安排

3、1個(gè)小時(shí))第5頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五5學(xué)習(xí)考查方法1、出勤率：10% 不定期檢查出勤情況2、作業(yè)完成情況：10% 對作業(yè)完成情況進(jìn)行登記3、課堂測驗(yàn) + 期中考試：20% 共 5 次4、期末考試（閉卷）：60%第6頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五6第一篇 數(shù)理邏輯第1章 導(dǎo) 論數(shù)理邏輯的概念數(shù)理邏輯的發(fā)展簡史數(shù)理邏輯的地位和作用第7頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五7（1）定義1.1 數(shù)理邏輯的概念 數(shù)理邏輯是采用數(shù)學(xué)方法研究抽象思維推理規(guī)律（形式推理）的一門科學(xué)。命題邏輯是數(shù)理邏輯的基本組成部分之一推理的基

4、本要素是命題把命題作為基本單位來分析符號(hào)化 研究公式間的關(guān)系 推導(dǎo)、演算 第8頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五8（2）方法 引入一套數(shù)學(xué)符號(hào)系統(tǒng)來進(jìn)行研究，強(qiáng)調(diào)推理過程中前提和結(jié)論之間的形式關(guān)系。例：A、B、C、D4人做百米競賽，觀眾甲、乙、丙預(yù)報(bào)比賽結(jié)果的名次為：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比賽結(jié)束后發(fā)現(xiàn)甲乙丙每人報(bào)告的情況都各對一半，試問實(shí)際名次如何？1.引入pi,qi,ri,si分別表示“A排名第i，B排名第i ，C排名第i ，D排名第i”2. 給出個(gè)命題之間的關(guān)系 （1）(r1 q2) (r1 q2) 1 （2）(r2 s3) (r2

5、 s3) 1 （3）(p2 s4) (p2 s4) 13.通過演算規(guī)則，得出結(jié)果第9頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五9（3）內(nèi)容謂詞邏輯命題邏輯第10頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五10（4）分支模型論證明論公理集合論遞歸論第11頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五111.2 數(shù)理邏輯的發(fā)展簡史創(chuàng)立階段起源階段完善階段 發(fā)展歷史第12頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五12起源階段 德國數(shù)學(xué)家、哲學(xué)家 G.Leibniz（16461716），提出建立一種普遍的符號(hào)語言，利用符號(hào)語言進(jìn)行思維演算的設(shè)想

6、。第13頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五13創(chuàng)立階段 英國數(shù)學(xué)家 G.Bool于1847年發(fā)表邏輯的數(shù)學(xué)分析，創(chuàng)建一套表示邏輯推理的基本符號(hào)以及符號(hào)的運(yùn)算規(guī)律，建立了布爾代數(shù)。 德國數(shù)學(xué)家 G.Frege于1879年在概念的演算一書中引進(jìn)謂詞符號(hào)和量詞符號(hào)，創(chuàng)建第一個(gè)比較嚴(yán)格的邏輯演算系統(tǒng)。第14頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五14完善階段 英國邏輯學(xué)家 和B.Russel于1910將當(dāng)時(shí)的數(shù)理邏輯寫入了數(shù)學(xué)原理中，使數(shù)理邏輯成為了一門專門的學(xué)科。 20 世紀(jì) 30 年代，由于眾多科學(xué)家的努力，衍生出許多新的分支，如：直覺主義邏輯、多值邏輯、

7、組合邏輯等。第15頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五151.3 數(shù)理邏輯的地位和作用1、計(jì)算機(jī)科學(xué)的重要的理論基礎(chǔ)之一；2、對數(shù)學(xué)、計(jì)算機(jī)科學(xué)、人工智能、語言學(xué)、控制論等諸多學(xué)科產(chǎn)生深遠(yuǎn)的影響。3、在計(jì)算機(jī)科學(xué)中的應(yīng)用：軟件、硬件設(shè)計(jì)第16頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五16第2章 命題邏輯2.1 命題邏輯基本概念 2.2 命題邏輯等值演算 2.3 范式2.4 命題邏輯推理理論 第17頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五172.1 命題邏輯基本概念 2.1.1 命題與聯(lián)結(jié)詞命題與真值(簡單命題, 復(fù)合命題)聯(lián)結(jié)詞(, ,

8、, , ) 命題公式及其分類命題公式及其賦值真值表命題公式的分類 第18頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五182.1.1 命題與聯(lián)結(jié)詞1、命題及相關(guān)概念（1）命題的定義兩者必居其一且只居其一二值邏輯 命題定義的理解：從兩個(gè)方面把握這個(gè)概念（1）陳述句；（2）真值唯一性（注意：真值可能目前還不知道答案）。命題：一個(gè)具有真假意義的陳述句。 什么是真值：只包含真/假兩個(gè)值的量。 T/1真 F/0假第19頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五19 注意：（1） 感嘆句、祈使句、疑問句都不是命題 （2）陳述句中的悖論以及判斷結(jié)果不唯一確定的也不是命題第20頁，

9、共86頁，2022年，5月20日，11點(diǎn)11分，星期五20中國的首都在北京。1+1=10請開門！x+y=1明年10月1日是晴天。本命題是假的。李紅既學(xué)英語又學(xué)日語。例1 判斷下列個(gè)自然語言是否是命題第21頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五21（2）幾個(gè)基本概念 真命題與假命題 命題變元與命題常元 真命題: 真值為真的命題 假命題: 真值為假的命題 若p即可以表示真命題，又可以表示假命題，則稱p為命題變元。 T永遠(yuǎn)表示真命題，F(xiàn)表示假命題，稱T和F為命題常元。第22頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五22例2真命題假命題真值不確定疑問句感嘆句祈使句悖

10、論(1),(2),(5)是命題, (3),(4),(6)(8)都不是命題真值確定, 但未知 下列句子中哪些是命題？并指出命題的真值。 (1) 北京是中華人民共和國的首都.(2) 2 + 5 8.(3) x + 5 3.(4) 你會(huì)開車嗎？(5) 2050年元旦北京是晴天.(6) 這只兔子跑得真快呀！(7) 請關(guān)上門！(8) 我正在說謊話.第23頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五23（1）簡單命題與復(fù)合命題（2）聯(lián)結(jié)詞的定義（3）聯(lián)結(jié)詞的優(yōu)先級(jí)2.聯(lián)接詞第24頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五24（1）簡單命題與復(fù)合命題簡單命題(原子命題):簡單陳

11、述句構(gòu)成的命題。簡單命題的符號(hào)化:用p, q, r, ,pi,qi,ri (i1)表示 用“1”表示真，用“0”表示假復(fù)合命題:由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。 例如 如果明天天氣好, 我們就出去郊游 設(shè)p:明天天氣好, q:我們出去郊游, 如果p, 則q 又如 張三一面喝茶一面看報(bào) 設(shè)p:張三喝茶, q:張三看報(bào), p并且q第25頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五25（2）聯(lián)結(jié)詞的定義否定詞（）定義2.1 設(shè)p為命題，復(fù)合命題 “非p”(或 “p的否定”)稱為p的否定式，記作p，符號(hào)稱作否定聯(lián)結(jié)詞, 并規(guī)定p為真當(dāng)且僅當(dāng) p為假。例如 p:2是合數(shù), p: 2不

12、是合數(shù)。p為假, p為真。第26頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五26合取詞（ ）定義2.2 設(shè)p,q為二命題, 復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式, 記作pq, 稱作合取聯(lián)結(jié)詞, 并規(guī)定 pq為真當(dāng)且僅當(dāng) p與q同時(shí)為真.例如 p:2是偶數(shù), q: 2是素?cái)?shù), pq: 表示的含義是2是偶素?cái)?shù)。 因?yàn)閜為真, q也為真，所以 pq為真。第27頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五27例3 將下列命題符號(hào)化. 解：記 p:王曉用功, q:王曉聰明(1) pq (2) pq(3) qp(4) 記 r: 張輝是三好生, s: 王麗是三好

13、生, rs(5) 簡單命題, 記 t: 張輝與王麗是同學(xué)(1) 王曉既用功又聰明.(2) 王曉不僅聰明，而且用功.(3) 王曉雖然聰明，但不用功.(4) 張輝與王麗都是三好生.(5) 張輝與王麗是同學(xué).第28頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五28析取詞（）定義2.3 設(shè) p、q為命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq, 稱作析取聯(lián)結(jié)詞, 并規(guī)定pq為假當(dāng)且僅當(dāng)p與q同時(shí)為假。例如 張三和李四至少有一人會(huì)英語設(shè) p:張三會(huì)英語, q:李四會(huì)英語, 符號(hào)化為pq。第29頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五29相容或與排斥或 析取詞表示的是

14、相容或，即 p 和 q 均為真時(shí) (p q)亦為真，而與之對應(yīng)的還有一個(gè)是排斥或，它表示的含義是p 和 q 不能同時(shí)為真。例如 這件事由張三和李四中的一人去做 設(shè) p:張三做這件事, q:李四做這件事 應(yīng)符號(hào)化為 (p q) (p q)第30頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五30例4 將下列命題符號(hào)化，并指出其真值解：記 p:2是素?cái)?shù), q:3是素?cái)?shù), r:4是素?cái)?shù), s:6是素?cái)?shù)(1) pr, (2) pq, (3) rs,(4) 記t:元元拿一個(gè)蘋果,u:元元拿一個(gè)梨真值:1真值: 1真值: 0(tu)(tu)(5) 記v:王曉紅生于1975年,w:王曉紅生于197

15、6年(vw)(vw)又可形式化為 vw(1) 2或4是素?cái)?shù).(2) 2或3是素?cái)?shù).(3) 4或6是素?cái)?shù).(4) 元元只能拿一個(gè)蘋果或一個(gè)梨.(5) 王曉紅生于1975年或1976年.第31頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五31蘊(yùn)涵詞（ ）定義2.4 設(shè) p,q為二命題, 復(fù)合命題 “如果p,則q” 稱作p與q的蘊(yùn)涵式, 記作pq, 并稱p是蘊(yùn)涵式的前件, q為蘊(yùn)涵式的后件. 稱作蘊(yùn)涵聯(lián)結(jié)詞, 并規(guī)定, pq為假當(dāng)且僅當(dāng) p為真且q為假.例如 如果明天天氣好, 我們就出去郊游 設(shè)p:明天天氣好, q:我們出去郊游, 形式化為 pq第32頁，共86頁，2022年，5月20日

16、，11點(diǎn)11分，星期五32蘊(yùn)涵詞的其它表述方式pq 的邏輯關(guān)系: q為p的必要條件, p為q的充分條件?！叭绻鹥,則q” 的多種表述方式： 若p,就q 只要p,就q p僅當(dāng)q 只有q 才p 除非q, 才p 除非q, 否則非p當(dāng)p為假時(shí)，pq為真(不管q為真, 還是為假)第33頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五33例5 設(shè)p:天冷, q:小王穿羽絨服，將下列命題符號(hào)化 注意： pq 與 qp 等值（真值相同） pqpqqp 或 pqpqqp qppq 或 qpqp(1) 只要天冷，小王就穿羽絨服.(2) 因?yàn)樘炖?，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷.(4

17、) 只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候.第34頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五34等價(jià)詞（ ）定義2.5 設(shè)p, q為命題, 復(fù)合命題 “p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式, 記作pq, 稱作等價(jià)聯(lián)結(jié)詞. 并規(guī)定pq為真當(dāng)且僅當(dāng) p與q同時(shí)為真或同時(shí)為假。 pq 的邏輯關(guān)系: p與q互為充分必要條件例如 這件事張三能做好, 且只有張三能做好 設(shè)p:張三做這件事, q:這件事做好了 形式化為: pq第35頁，共86頁，2022年，5月20

18、日，11點(diǎn)11分，星期五35例6 求下列復(fù)合命題的真值：1011(1) 2+24 當(dāng)且僅當(dāng) 3+36.(2) 2+24 當(dāng)且僅當(dāng) 3是偶數(shù).(3) 2+24 當(dāng)且僅當(dāng) 太陽從東方升起.(4) 2+25 當(dāng)且僅當(dāng) 美國位于非洲.第36頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五36分析找出簡單命題用字母表示簡單命題用聯(lián)接詞聯(lián)接命題符號(hào)命題符號(hào)化的一般規(guī)則第37頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五37分析找出簡單命題用字母表示簡單命題用聯(lián)接詞聯(lián)接命題符號(hào)解 令 p: 我上街 q: 我累 r: 我去書店看看 則可符號(hào)化為：（pq)r例7 將下列命題符號(hào)化：如果我上

19、街并且我不累，我就去書店看看。簡單命題：我上街。我累。我去書店看看。第38頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五38例8 試將下列命題符號(hào)化：如果你不看電影，那么我也不看電影小王一邊吃飯，一邊看書解:（1）設(shè)p：你看電影， q：我看電影，則： p q （2）設(shè)p：小王吃飯，q：小王看書，則： pq第39頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五39（3）聯(lián)結(jié)詞的優(yōu)先級(jí)聯(lián)結(jié)詞優(yōu)先級(jí):( ), , , , 同級(jí)按從左到右的順序進(jìn)行第40頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五401、分析下列各命題的真值 （1） 2+2=4當(dāng)且僅當(dāng)3是奇數(shù) （2

20、） 2+2=4當(dāng)且僅當(dāng)3不是奇數(shù) （3） 2+24當(dāng)且僅當(dāng)3是奇數(shù) （4） 2+24當(dāng)且僅當(dāng)3不是奇數(shù)2、將下列命題符號(hào)化 （1）小王是游泳冠軍或者百米賽跑冠軍 （2）小王現(xiàn)在在宿舍或者在圖書館 （3）選小王或者小李中的一人當(dāng)班長 （4）如果我上街，我就去書店看看，除非我很累課堂練習(xí)（1）第41頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五41課堂練習(xí)（2）3、將下列命題符號(hào)化 （1）李平既聰明又用功 （2）李平雖然聰明，但不用功 （3）李平不但聰明，而且用功 （4）李平不是不聰明，而是不用功4、將下列命題符號(hào)化 （1）只要不下雨，我就騎自行車上班 （2）只有不下雨，我才騎自行車上

21、班 （3）若2+2=4，則太陽從東方升起 （4）若2+24,則太陽從東方升起第42頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五422.1.2 合式公式及其分類1.命題語言的字母表 ：2.合式公式的基本概念3.真值表4.合式公式的分類第43頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五431.命題語言的字母表命題語言的字母表 ：命題常元：T, F (或 1，0)命題變元：p1, p2, , pn聯(lián)接詞：，輔助符號(hào)：（ ）第44頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五44（1）合式公式(命題公式, 公式)的定義定義2.6 合式公式遞歸定義如下：(1) 單

22、個(gè)命題常項(xiàng)或變項(xiàng)是合式公式，并稱作原子合式公式；(2) 若A是合式公式, 則 (A)也是合式公式；(3) 若A, B是合式公式, 則(AB), (AB), (AB), (AB)也是合式公式；(4) 只有有限次地應(yīng)用(1)(3)形成的符號(hào)串才是合式公式。2、合式公式的基本概念說明:(1) 元語言符號(hào)與對象語言符號(hào) (2) 在不影響運(yùn)算順序時(shí), 括號(hào)可以省去 例如 0, p, pq, (pq)(pr), pq r, (pq)r第45頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五45（2）合式公式的層次定義2.7 (1) 單個(gè)命題變項(xiàng)或命題常項(xiàng)是0層公式(2) 稱A是n+1(n0)層公式

23、是指下面情況之一：(a) A=B, B是n層公式(b) A=BC, 其中B,C分別為i層和j層公式, 且 n=max(i, j)(c) A=BC, 其中B,C的層次及n同(b)(d) A=BC, 其中B,C的層次及n同(b)(e) A=BC, 其中B,C的層次及n同(b)例如 p 0層 p 1層 pq 2層 (pq)r 3層 (pq) r)(rs) 4層第46頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五46（3）公式的賦值定義2.8 設(shè) p1, p2, , pn是出現(xiàn)在公式A中全部的命題變項(xiàng)，給 p1, p2, , pn指定一組真值，稱為對A的一個(gè)賦值或解釋。使公式為真的賦值稱作

24、成真賦值, 使公式為假的賦值稱作成假賦值。說明: (1) 賦值記作=12n，其中i=0或1，諸i之間不加標(biāo)點(diǎn)符號(hào)；(2) 通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng), 即：當(dāng)A的全部命題變項(xiàng)為p1, p2, , pn時(shí), 給A賦值12n是指 p1=1,p2=2,pn=n; 當(dāng)A的全部命題變項(xiàng)為p,q,r,時(shí), 給A賦值123是指p=1, q=2, r=3, 第47頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五47實(shí)例例8 公式A=( p1 p2 p3 )(p1 p2) 000是成真賦值, 001是成假賦值 公式B= (pq)r 000是成假賦值, 001是成真賦值第48頁，共86頁

25、，2022年，5月20日，11點(diǎn)11分，星期五483、真值表真值表: 命題公式在所有可能的賦值下的取值的列表。含n個(gè)變項(xiàng)的公式有2n個(gè)賦值 用0或1表示公式中命題變元的取值，并依據(jù)聯(lián)結(jié)詞的邏輯規(guī)則計(jì)算出復(fù)合命題（公式）的真值，用一個(gè)對應(yīng)表表示的一種方法。第49頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五49基本復(fù)合命題真值表匯總 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1第50頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五50 p q qp (qp) q (qp)

26、qp 0 00 11 01 1 1011 0001 1111例9 給出公式的真值表(1) (qp) qp；(2) (pq) q； (3) (pq) r.例9第51頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五51 p q ppq (pq) (pq) q0 00 11 01 1 1100110100100000(2) (pq) q第52頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五52 p q r pq r (pq)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010(3) (pq

27、) r第53頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五534、命題公式的分類重言式(永真式): 無成假賦值的命題公式矛盾式(永假式): 無成真賦值的命題公式可滿足式: 非矛盾式的命題公式注意: 重言式是可滿足式，但反之不真.例如 上例中(1) (qp)qp為重言式(2) (pq)q為矛盾式(3) (pq)r為非重言式的可滿足式第54頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五542、判斷下列命題公式的類型（1）（2）課堂練習(xí)1、構(gòu)造下列命題公式的真值表（1）（2）第55頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五552.2 命題邏輯等值演算2.2.1

28、 等值式與等值演算等值式基本等值式等值演算2.2.2 聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞第56頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五56 2.2.1 等值式與等值演算1、等值式的定義定義2.11 若等價(jià)式AB是永真式, 則稱A與B等值, 記作AB, 并稱AB是等值式。第57頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五57(1) 是元語言符號(hào), 不要混同于和=。(2) A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同, 即A與B有相同的真值表。(3) 可能有啞元出現(xiàn). 在B中出現(xiàn), 但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元. 同樣,在A中出現(xiàn)

29、, 但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元. 啞元的值不影響命題公式的真值。說明第58頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五582、性質(zhì)(1) A A(2) 若A B，則 B A(3) 若A B且B C，則 A C第59頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五593、真值表法判斷公式是否等值結(jié)論: (pq) (pq) p q p q pq (pq) pq (pq)(pq) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1例1 判斷 (pq) 與 pq 是否等值解第60頁，共86頁，

30、2022年，5月20日，11點(diǎn)11分，星期五60 p q r p(qr) (pq)r (pq)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)與(pq)r等值, 但與(pq)r不等值 例2 判斷下述3個(gè)公式之間的等值關(guān)系: p(qr), (pq)r, (pq)r解第61頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五614、基本等值式（1）雙重否定律：（2）等冪律：第62頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五

31、62（3）交換律：（4）結(jié)合律：（5）分配律：（6）德 摩根定律：第63頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五63（7）吸收律：（8）蘊(yùn)含等值式：（9）等價(jià)等值式：第64頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五64（10）零律：（11）同一律：（12）排中律：第65頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五65（13）矛盾律：（14）等價(jià)否定等值式：（15）歸謬律：（16）假言易位：第66頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五66 (1) 代入規(guī)則 代入規(guī)則：對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得

32、到的仍是重言式。 例如 F=（pq）（qp）是重言式，若用公式rs代換命題變元p得公式 F1=（rs）q）（q（rs）， F1仍是重言式。注意：因?yàn)锳 B當(dāng)且僅當(dāng)A B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。5、等值演算第67頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五67(2) 置換規(guī)則 例如 設(shè)公式A=（PQ）（PQ）（RS）。 則PQ，PQ，（PQ）（RS）等均是A的子公式， 置換規(guī)則：設(shè)C是公式A的子公式，CD。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則AB。 子公式： 設(shè)C是命題公式A的一部分（

33、即C是公式A中連續(xù)的幾個(gè)符號(hào)），且C本身也是一個(gè)命題公式，則稱C為公式A的子公式。 第68頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五68(3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。 例3 證明 p(qr) (pq)r證 p(qr) p(qr) （蘊(yùn)涵等值式） (pq)r （結(jié)合律） (pq)r （德摩根律） (pq) r （蘊(yùn)涵等值式）第69頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五69 例4：證明（AB)(BA)是永真式。證明: (A B)(B A) 蘊(yùn)涵等值式 (AB)(BA)

34、德摩根律、雙重否定律 (AB)(BA) 分配律 (ABA)(BBA)交換律、結(jié)合律、補(bǔ)余律 T （AB)(BA)是永真式第70頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五70（同一律）（排中律）（分配律）證明 例5證：第71頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五71例6 用等值演算法判斷下列公式的類型(1) q(pq) 解 q(pq) q(pq) （蘊(yùn)涵等值式） q(pq) （德摩根律） p(qq) （交換律，結(jié)合律） p0 （矛盾律） 0 （零律）該式為矛盾式.第72頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五72例6(續(xù))(2) (pq)(q

35、p) 解 (pq)(qp) (pq)(qp) （蘊(yùn)涵等值式） (pq)(pq) （交換律） 1該式為重言式.第73頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五73例6(續(xù))(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié):A為矛盾式當(dāng)且僅當(dāng)A0; A為重言式當(dāng)且僅當(dāng)A1說明:演算步驟不惟一,應(yīng)盡量使演算短些第74頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五74例7：應(yīng)用題 某勘探隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，3人的判斷如下： 甲說：這不是鐵，也不是銅 乙說：這不是鐵，是錫 丙說：這不是錫，是鐵 經(jīng)過實(shí)驗(yàn)鑒定后發(fā)現(xiàn)，其中一人2個(gè)判斷都是正確的，一人判斷對了一半，另外一個(gè)人全錯(cuò)了。根據(jù)以上情況判斷礦樣的種類。第75頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五75解：設(shè) p：礦樣為鐵，q：礦樣為銅，r：礦樣為錫，則可得：第76頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五76第77頁，共86頁，2022年，5月20日，11點(diǎn)11分，星期五7