1、1離散數學離散數學(Discrete (Discrete Mathematics)Mathematics)課程學時：共課程學時：共9696，本，本學期學期4848裴振奎裴振奎計算機與通信工程學計算機與通信工程學院計算機科學系院計算機科學系 Tel: Tel: 2課程性質 離散數學（又稱計算機數學）是離散數學（又稱計算機數學）是現代數學的重要分支，是計算機專現代數學的重要分支，是計算機專業核心基礎課程之一。業核心基礎課程之一。3課程目標 離散數學是以研究離散量的結離散數學是以研究離散量的結構和相互之間的關系為主要目標，構和相互之間的關系為主要目標，其研究對象一般為：有限或可數個其研究對象一般為：

2、有限或可數個元素（例如：自然數、整數、真假元素（例如：自然數、整數、真假值、有限個結點等），而離散性也值、有限個結點等），而離散性也是計算機科學的顯著特點。是計算機科學的顯著特點。4與其他課程的關系 離散數學與計算機科學的其他課程離散數學與計算機科學的其他課程,如：數據如：數據結構、操作系統、編譯原理、算法分析、邏輯結構、操作系統、編譯原理、算法分析、邏輯設計、系統結構、容錯技術、人工智能等有密設計、系統結構、容錯技術、人工智能等有密切的聯系。它是這些課程的先導和基礎課程。切的聯系。它是這些課程的先導和基礎課程。5n離散數學n上海科學技術文獻出版社n左孝凌等編著n離散數學n高等教育出版社n耿素

3、云、屈婉玲著n其它參考資料可以從下面的郵箱下載！，密碼 jsj2012教材與參考書6課程內容 本課程根據大綱的內容和相關獨立性， 可分為四大部分 第一部分 數理邏輯 包括命題邏輯;謂詞邏輯 第二部分 集合論 包括集合與關系;函數 7課程內容第三部分 代數系統 包括代數結構;格與布爾代數第四部分 圖論 8學習方法定義、定理多。 本課內容定義定理例題為了學好這門課，要求： （）弄懂定義、定理，弄懂例題，加深對定義、定理的理解； （）在復習基礎上，做好課外作業。同學之間可以討論，但要弄懂弄通。 （3）做好課堂筆記。9第一篇 數理邏輯 邏輯學邏輯學:研究思維形式及思維規律的科學。研究思維形式及思維規律

4、的科學。邏輯學分為二類：邏輯學分為二類：辯證邏輯辯證邏輯:是研究事物發展的客觀規律。是研究事物發展的客觀規律。形式邏輯形式邏輯:對思維的形式結構和規律進行研對思維的形式結構和規律進行研究。究。數理邏輯：是用數學的方法研究概念、數理邏輯：是用數學的方法研究概念、 判斷和推理的科學，屬于形式邏輯。判斷和推理的科學，屬于形式邏輯。10第一篇 數理邏輯 在數理邏輯中，用數學的方法是指引進一套符號體系的方法來研究概念、判斷和推理。即對符號進行判斷和推理。數理邏輯分為四大分支：證明論、模型論、遞歸論和公理集合論。我們這里介紹的是屬于四大分支的共同基礎古典數理邏輯(命題邏輯和謂詞邏輯)。使用計算機必須首先學

5、會編使用計算機必須首先學會編“程序程序”，那么什么，那么什么是程序？是程序？ 程序算法數據程序算法數據 算法邏輯控制算法邏輯控制 可見可見“邏輯邏輯”對于編程序是多么重要。要想學對于編程序是多么重要。要想學好、使用好計算機，必須學習邏輯，此外，通過好、使用好計算機，必須學習邏輯，此外，通過學習邏輯，掌握邏輯推理規律和證明方法學習邏輯，掌握邏輯推理規律和證明方法 ，會，會培培養學生的邏輯思維能力，提高證明問題的技巧。養學生的邏輯思維能力，提高證明問題的技巧。數理邏輯與計算機錢學森談“計算機與數理邏輯” 電子計算機與數理邏輯具有非常密切的關系。正是在數理邏輯中，把人類的推理過程分解成一些非常簡單原

6、始的、非常機械的動作，才使得用機器代替人類的推理的設想有了實現的可能。 有了電子計算機，使用它時，必須先進行程序設計，把整個推理、計算過程，絲毫不漏地考慮到，統統編入程序， 而機器則依次而運行；如稍有錯誤，將立即得到毫無意義的結果。可見必須有足夠的數理邏輯的訓練，熟悉推理過程的全部細節,才能從事程序設計。 此外，程序設計是一個很細致又很麻煩的工作，如何從事程序設計，如何防止在計算過程中出錯，如何很快地發現這種錯誤而及時加以改正，都是程序設計理論(軟件理)中非常根本又非常重要的內容，大家都認為，這些內容都與數理邏輯息息相關。 正如著名的計算機軟件大師戴克斯特拉 (E.W.Dijkstra)曾經說

7、過：我現在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現在覺悟了。我想，假如我早在數理邏輯上好好下點功夫的話，我就不會犯這么多錯誤。不少東西邏輯學家早就說過了，可是我不知道。要是我能年輕20歲的話，我就會回去學邏輯。15第一章 命題邏輯1.1 命題1.2 命題聯結詞1.3 命題公式1.4 真值表與等價公式1.5 蘊含式1.6 其他命題聯結詞1.7 范 式 1.8 推論理論16第一章 命題邏輯 教學目的及要求：教學目的及要求： 深刻理解和掌握命題邏輯中基本概念和基本方法。深刻理解和掌握命題邏輯中基本概念和基本方法。 教學內容：教學內容： 命題及表示、聯結詞、命題公式與翻譯、真值表命題及表示、聯

8、結詞、命題公式與翻譯、真值表與等價公式、重言式與蘊涵式、對偶與范式、推與等價公式、重言式與蘊涵式、對偶與范式、推理理論。理理論。 教學重點：教學重點： 命題邏輯中的基本概念和基本推理方法。命題邏輯中的基本概念和基本推理方法。 教學難點：推理理論。教學難點：推理理論。171.1 命題定義：定義： 具有確定真假值的陳述句叫命題。具有確定真假值的陳述句叫命題。 討論定義：討論定義： （1）命題可以是真的，或者是假的，但不能）命題可以是真的，或者是假的，但不能 同時為真又為假。同時為真又為假。 （2）命題分類：）命題分類： )原子命題（基本命題、本原命題）：原子命題（基本命題、本原命題）： 不能分解成

9、為更簡單的命題。不能分解成為更簡單的命題。 例：我是一位學生。例：我是一位學生。181.1 命題 )分子命題（復合命題）：若干個原子 命題使用適當的聯結詞所組成的新命題 例：張三是一位學生并且李四是一位工人（3）命題所用符號：常用大寫個英文字母 及加上下標 表示命題。 用、2、C7表示。（4）命題中所有的“真”用“”表示， 命題中所有的“假”用“”表示。191.1 命題例：判斷下列語句是否為命題。例：判斷下列語句是否為命題。 （1）十是整數。）十是整數。 （）（）（2）上海是一個村莊。（）上海是一個村莊。（）（3）今天下雨。）今天下雨。（4）加拿大是一個國家。（）加拿大是一個國家。（）（5）是

10、偶數而是奇數。（）是偶數而是奇數。（T）（6）雷鋒不是醫生。）雷鋒不是醫生。 （T）（7）在十進制中）在十進制中 （）（）（8）今天是星期天。）今天是星期天。 （）（）201.1 命題命令句，感嘆句，疑問句均不是命題。 （1）把門關上！ （2）你到哪里去？語句既為真，同時又包含假的不是命題，這樣的句子稱為“悖論”。 （3）他正在說謊。 （在命題邏輯中不討論這類問題）211.2 命題聯結詞在命題演算中也有類似的日常生活中的聯結詞稱做： “命題聯結詞”,下面先介紹五個常用的命題聯結詞。否定詞：（否定運算、非運算） （）符號 ,讀作“非”，“否定” 設命題為，則在的前面加否定詞 ，變成，讀做“的否定

11、”或“非”221.2 命題聯結詞（）定義 P的真值表：（）舉例： ：每一種生物均是動物。F ：有一些生物不是動物。T 這里不能講成“每一種生物都不是動物”。對量化命題的否定，除對動詞進行否定外，同時對量化詞也要加以否定。TFFT P PP231.2 命題聯結詞合取詞（合取詞（“合取合取”、“積積”、“與與”運算）運算） (1)符號符號“” 設，為兩個命題，則設，為兩個命題，則稱與的合稱與的合 取，讀作：取，讀作：“與與”、“與的合取與的合取”、“并并 且且”等。等。 (2)定義（由真值表給出）：定義（由真值表給出）：241.2 命題聯結詞TTTTFFFTFFTFFFFFQPP QQP的真值表

12、：251.2 命題聯結詞當且僅當和的真值均為“”，則（） 的真值為“”。否則，其真值為“”。注意：和是互為獨立的；地位是平等的，和的位置可以交換而不會影響的結果。261.2 命題聯結詞(3)舉例： (a) P：王華的成績很好 Q：王華的品德很好。 則：王華的成績很好并且品德很好。 (b)P：我們去種樹 Q：房間里有一臺電視機 則：我們去種樹與房間里有一臺電視機。271.2 命題聯結詞 (c) P：今天下大雨 Q：3+3=6 則：今天下大雨和3+3=6由例(b)(c)可見，在日常生活中，合取詞應用在二個有關系的命題之間。而在邏輯學中，合取詞可以用在二個毫不相干的命題之間。281.2 命題聯結詞

13、(d)P: 王大和王二是親兄弟。 Q: 他打開箱子然后拿出一件衣服來。 該語句不是合取聯結詞組成的命題。 291.2 命題聯結詞析取詞（或運算）析取詞（或運算） （）符號（）符號“” 設、為二個命題，則（設、為二個命題，則（）稱作）稱作與的與的“析取析取”，讀作：，讀作：“或或”。 （）定義（由真值表給出）：（）定義（由真值表給出）：301.2 命題聯結詞當且僅當、均為“”時，（）為“”。否則，其真值為“”TTTTFTTTFFFFP QQP的真值表：311.2 命題聯結詞區分“可兼或”與“不可兼或（異或，排斥或）” “可兼或”即P或Q為“T”時（PQ）為“T”，是析取。 例如： 燈泡有故障或開

14、關有故障。 今晚寫字或看書。 今天下雨或打雷。 以上例句均為“可兼或”。321.2 命題聯結詞“不可兼或”即P和Q的真值不同時，PQ為T。 （異或用“”表示）不是析取。FTTTFTTTFFFFPQQPPQ的真值表：331.2 命題聯結詞例： 他通過電視看雜技或到劇場看雜技。 他乘火車去北京或乘飛機去北京。以上兩句均為“不可兼或”。341.2 命題聯結詞單條件聯結詞：單條件聯結詞： （）符號（）符號“”，讀作：，讀作：“如果如果則則” 、為二個命題，（、為二個命題，（）為新的命題，）為新的命題，讀作：讀作：“如果則如果則” 。 （）定義（）定義 （由真值表給出）（由真值表給出）351.2 命題聯

15、結詞的真值表： TTTFFTTTFTFFPQQP361.2 命題聯結詞 當為“”，為“”時，則（）為“”， 否則（）均為“”。 ：稱為前件、條件、前提、假設 ：稱為后件、結論。（）舉例： P：我拿起一本書 Q：我一口氣讀完了這本書 371.2 命題聯結詞 PQ：如果我拿起一本書，則我一口氣讀完 了這本書。(b) P：月亮出來了 Q：33=9 PQ：如果月亮出來了，則33=9。通常稱： (a)為形式條件命題前提和結果有某種形式 和內容上的聯系。381.2 命題聯結詞 (b)為實質條件命題前提和結果可以有聯 系，也可以沒有聯系，只要滿足單條件命 題的定義。所以,是形式條件命題一定是實質條件命題,反

16、 之不一定。“”是實質條件命題。例：我買到了魚；:我吃魚。 ：如果我買到了魚，則我吃魚。但“如果我沒買到魚，則我吃魚”，在日常生活中不可能，但在單條件命題的定義中是允許的。 391.2 命題聯結詞可以證明： Q P 原命題 逆反命題 逆命題 反命題401.2 命題聯結詞列出真值表,由真值表得： 原命題逆反命題；逆命題反命題。 TTTTTTTTFFFTFFTTTFTTTTFFP QP PQQP41n5雙條件聯結詞（等價聯結詞）：雙條件聯結詞（等價聯結詞）：n（）符號（）符號“”，讀作：，讀作：“當且僅當當且僅當”n 、為二個命題，（、為二個命題，（）為新）為新的命題，讀作：的命題，讀作：“當且僅

17、當當且僅當” 。n （）定義（）定義 （由真值表給出）（由真值表給出）421.2 命題聯結詞P Q的真值表:每當和的真值相同時，則（）的真值為“”，否則（ ）的真值為“”。 TTTFFTFTFTFFP QQP431.2 命題聯結詞（）舉例： （a）設 ：ABC是等腰三角形 ：ABC有兩只角相等 ：ABC是等腰三角形當且僅當 有兩只角相等。441.2 命題聯結詞（b）下面均為等價聯結詞： 春天來了當且僅當燕子飛回來了。 平面上二直線平行，當且僅當二直線不相交。 當且僅當雪是白色的。451.2 命題聯結詞（）,中，、的地位是平等的，、 交換位置不會改變真值表中的值。（）當且僅當 僅當 當且461.

18、2 命題聯結詞命題聯結詞在使用中的優先級命題聯結詞在使用中的優先級 （）先括號內，后括號外（）先括號內，后括號外 （）運算時聯結詞的優先次序為：（）運算時聯結詞的優先次序為： （由高到低）（由高到低） （）聯結詞按從左到右的次序進行運算（）聯結詞按從左到右的次序進行運算 （）最外層的括號一律均可省去（）最外層的括號一律均可省去 （）可寫成）可寫成471.2 命題聯結詞例 （）可省去括號 因為“”運算是可結合的。而（）中的括號不能省去，因“”不滿足結合律。 481.2 命題聯結詞 命題聯結詞小結： （1）五個聯結詞的含義與日常生活中的聯結詞 的含義大致相同。 （2）“或”可分為可兼或（）和異或（

19、 ） （不可兼或） （3） “”為一元運算，其余四個均為二元運算。491.2 命題聯結詞(4) “”分為形式條件和實質條件命題，當前件為“”時，不論后件怎樣，則單條件命題的真值均為“”。(5)命題聯結詞是命題或命題之間的聯結詞，而不是名詞之間、數字之間和動詞之間的聯結詞。501.2 命題聯結詞以上介紹了五種常用的聯結詞及其相應的復合命題形式。數理邏輯的特點是把邏輯推理變成類似數學演算的完全形式化了的邏輯演算，為此，首先要把推理所涉及到的各命題符號化。步驟如下： 找出各簡單命題，分別符號化。 找出各聯結詞，把簡單命題逐個聯結起來。511.2 命題聯結詞例. 將下列命題符號化：（1）李明是計算機系

20、的學生，他住在312室或313室。（2）張三和李四是朋友。（3）雖然交通堵塞，但是老王還是準時到達了車站。（4）只有一個角是直角的三角形才是直角三角形。（5）老王或小李中有一個去上海出差。521.2 命題聯結詞解：（1）首先用字母表示簡單命題。 P：李明是計算機系的學生。 Q：李明住在312室。 R：李明住在313室。 該命題符號化為：P（QR）（2）張三和李四是朋友。是一個簡單句 該命題符號化為：P531.2 命題聯結詞（3）首先用字母表示簡單命題。 P：交通堵塞。 Q：老王準時到達了車站。 該命題符號化為：PQ（4）首先用字母表示簡單命題。 P：三角形的一個角是直角。 Q：三角形是直角三角

21、形。 該命題符號化為：P Q541.2 命題聯結詞（5）首先用字母表示簡單命題。 P：老王去上海出差。 Q：小李去上海出差。 該命題符號化為：P Q 也可符號化為：（PQ）（PQ）或者 （P Q） （PQ）551.3 命題公式約定：約定： （）我們只注意命題的真假值，而不再去注（）我們只注意命題的真假值，而不再去注意命題的漢語意義。意命題的漢語意義。 （）對命題聯結詞，我們只注意真值表的定（）對命題聯結詞，我們只注意真值表的定義，而不注意它日常生活中的含義。義，而不注意它日常生活中的含義。561.3 命題公式命題公式命題公式命題常元：表示確定的命題命題常元：表示確定的命題T，F。命題變元：以真

22、假為其變域之變元，或沒有指定命題變元：以真假為其變域之變元，或沒有指定真值的命題。常用大寫英文字母真值的命題。常用大寫英文字母表示。表示。命題公式：由命題變元、常元、聯結詞、括號，命題公式：由命題變元、常元、聯結詞、括號， 以規定的格式聯結起來的字符串。以規定的格式聯結起來的字符串。571.3 命題公式定義定義命題公式命題公式(wff)可按下述法則來生成：可按下述法則來生成： ）單個的命題變元是一個命題公式。）單個的命題變元是一個命題公式。 ）若是命題公式，）若是命題公式，也為命題公式。也為命題公式。 ）若、是命題公式，則（）若、是命題公式，則（）、）、 （）、（）、（）、（）、（）均）均為命

23、題公式。為命題公式。 ）當且僅當有限次使用（）（）（）當且僅當有限次使用（）（）（）所得到的包含有命題變元和命題常元，聯結詞，所得到的包含有命題變元和命題常元，聯結詞，括號的符號串才是命題公式。括號的符號串才是命題公式。 581.3 命題公式例如：(PQ)，(P(QR)，(PQ)R)，P都是命題公式。而(P)，(P)都不是命題公式591.4 真值表與等價公式命題公式的真值表 :命題變元用特定的命題來取代，這一過程稱為對該命題變元進行真值指派。命題公式可以看成是一個以真假值為定義域和真假值為值域的一個函數。寫成(x)601.4 真值表與等價公式 例如：公式 P (Q R) 定義三元函數 Y(P，

24、Q，R) P (Q R) 定義命題公式A在其所有可能的賦值下取得的值列成的表稱為A的真值表。611.4 真值表與等價公式構造真值表的步驟如下： 1)找出給定命題公式中所有的命題變元，列 出所有可能的賦值。 2)按照從低到高順序寫出命題公式的各層次。 3)對應每個賦值，計算命題公式各層次的值，直到最后計算出整個命題公式的值。621.4 真值表與等價公式FTTTTFTTFTTFTTFTFFFF（）（）P QQP例構造命題公式（）的真值表：631.4 真值表與等價公式 例寫出命題公式（）的真值表 T TTT T FTT T TFT T FFT T TTF F FTF F TFF F FFF（)RQP

25、641.4 真值表與等價公式由上二例可見，個命題變元有組真值指派；個命題變元有23 組真值指派，個則有個2n個真值指派。651.4 真值表與等價公式等價式等價式定義定義如果對兩個公式，不論作何種指派，如果對兩個公式，不論作何種指派，它們真值均相同，則稱，是邏輯等價的，它們真值均相同，則稱，是邏輯等價的，亦說（）等價于（）亦說（）等價于（）,并記作：并記作：661.4 真值表與等價公式例：TTT TTTT FTTF TTTF F Q QPPP Q 671.4 真值表與等價公式例：判斷公式A：(PQ)(PQ)與 B：(PR)(PR)是否等價。解：列該公式的真值表：681.4 真值表與等價公式FFF

26、TTFTTFFFFFTFFFTTTFFFFFTTTFFFTFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP691.4 真值表與等價公式定理定理 命題公式命題公式的充要條件是的充要條件是為永真式。為永真式。說明：說明： “”為等價關系符，為等價關系符，表示和有等價表示和有等價關系。關系。 不為命題公式不為命題公式 “”為等價聯結詞（運算符），、為命題為等價聯結詞（運算符），、為命題公式，則（公式，則（ ）也為一命題公式。）也為一命題公式。 701.4 真值表與等價公式證明： （）充分性： 為永真式，即、

27、有相同的真值，所以。 （）必要性：，即、有相同的真值表，所以 為永真式。例：證明； 711.4 真值表與等價公式T T TT T T TTF T F T T T FTT T TF T F TFT T TF T FFFPQ PQP PQP由定理可知： 若，則 若，C，則721.4 真值表與等價公式下面列出15組等價公式 （1）雙重否定律 （2）同等律 ；（3）交換律 ； ；（4）結合律 （）（）； （）（）； （） （）731.4 真值表與等價公式（5）分配律 （）（）（）； （）（）（）（6）摩根律 （）； （） （7）吸收律 （） ； （） 741.4 真值表與等價公式（8）蘊含律 （9）等

28、價律 （）（）（10）零律；（11）同一律； （12）互補律；（13）輸出律 （）751.4 真值表與等價公式（14）歸繆律 （）（）（15）逆反律 說明：（）證明上述組等價公式的方法可用真值表法，把改為所得的命題公式為永真式，則成立。761.4 真值表與等價公式（2） 、 均滿足結合律， 則在單一用、 聯結詞組成的命題公式中，括號可以省去。（3）每個等價模式實際給出了無窮多個同類型的具體的命題公式。例如：(PQ) (P Q)， (PQ) (RS) (P Q) (R S)， (PQ) R) (P Q) R)771.4 真值表與等價公式置換規則置換規則定義定義給定一命題公式，其中給定一命題公式，

29、其中P1、 P2Pn 是是中的原子命題變元，中的原子命題變元，若（若（1）用某些命題公式代換中的一些原子命題變）用某些命題公式代換中的一些原子命題變元元Pi （2）用命題公式）用命題公式i代換代換Pi，則必須用，則必須用i代換中代換中的所有的所有Pi由此而得到的新的命題公式稱為命題公式的代換由此而得到的新的命題公式稱為命題公式的代換實例實例781.4 真值表與等價公式討論定義：討論定義：（）用命題公式只能代換原子命題變元，而不（）用命題公式只能代換原子命題變元，而不 能去代換分子命題公式能去代換分子命題公式 。（）要用命題公式同時代換同一個原子命題變（）要用命題公式同時代換同一個原子命題變 元

30、元 。（）永真式的代換實例仍為永真式；反之代換實（）永真式的代換實例仍為永真式；反之代換實 例為永真式時，則不能斷定原公式也一定是例為永真式時，則不能斷定原公式也一定是 永真式。永真式。791.4 真值表與等價公式例：為一永真式，若用任何命題公式代換，則仍為永真式為一個可滿足的命題公式，若用代換，則得（）為永真式，但（）并不是永真式。（）一個命題公式的代換實例有許多個，但不一定都等價于原來的命題公式 801.4 真值表與等價公式例設：（Q）若用（）代換中的，得：（）（Q（）是的代換實例，而：（）（Q）不是B的代換實例。例的代換實例有：（），（），（）等所以，一個命題公式的代換實例有無限個。81

31、1.4 真值表與等價公式下面討論取代過程（置換規則）：定義給定一命題公式，是的任何部分，若也是一命題公式，則稱是的子命題公式。例：（）（） 的子命題公式有：、（）、 （）、（）、 （）（）等。821.4 真值表與等價公式定理給定一命題公式，是的子公式。設B是一命題公式，若 B，并用B取代中的，從而生成一新的命題公式B，則B。從定理可見：一個命題公式A，經多次取代，所得到的新公式與原公式等價。例：證明：（）（） （） （）831.4 真值表與等價公式例：證明： （）（）（）（）為一永真式841.4 真值表與等價公式證明：原式： （）（）（）（） （）（）（）（） （）（）（）（）（） （）（）（

32、）（）它是（永真式）的代換實例，永真式的代換實例仍為永真式！851.4 真值表與等價公式例：證明： （）（）（ ） （）（）（） （） （） 證明：（）左邊(）（ ） （） （ ） （）（ ） （ ）861.4 真值表與等價公式（）左邊 （） （） （） （） （）871.5 重言式與 蘊含式 命題公式的重言式命題公式的重言式(永真式永真式)、矛盾式、矛盾式(永假式永假式)和可滿足式和可滿足式 定義定義設公式中有設公式中有n個不同的原子變元個不同的原子變元 p1,pn,(n為正整數為正整數)。該變元組的任意一組確定的值。該變元組的任意一組確定的值（ u1,un）稱為關于）稱為關于p1,pn的一

33、個完全指派，其中的一個完全指派，其中ui或為，或為。如果對于中部分變元賦以確定值，其或為，或為。如果對于中部分變元賦以確定值，其余變元沒有賦以確定的值，則這樣的一組值稱為公式的余變元沒有賦以確定的值，則這樣的一組值稱為公式的關于該變元組的部分指派。關于該變元組的部分指派。 定義定義使公式取真的指派稱為成真指派。使公式取真的指派稱為成真指派。881.5 重言式與 蘊含式定義如果一個命題公式的所有完全指派均為成真指派，則該公式稱為重言式(永真式)。如果一個命題公式的所有完全指派均為成假指派，則該公式稱為矛盾式(永假式)。既不是永真式，又不是永假式，則稱此命題公式是可滿足式。討論： （）永真式的否定

34、為永假式（）；永假式的否定為永真式（）。 （）二個永真式的析取、合取、蘊含、等價 均為永真式。891.5 重言式與 蘊含式定義命題公式稱為蘊含命題公式，當且僅當 是一個永真式，記作：說明：“ ”讀作“蘊含”，“蘊含”，“能推得” “ ”是關系符， 不為命題公式。例：證明： ； P （）列出真值表 證明：（）和（）為永真式901.5 重言式與 蘊含式（）可用等價公式證：（） （） T（） （） TT T TT T T T TF T TT T TF TF T FF T TTFF T FF T FFF（）（）QP911.5 重言式與 蘊含式定理定理設、是二個命題公式設、是二個命題公式的充分必要條件是

35、的充分必要條件是 且且 。證明：若證明：若，則，則為一永真式為一永真式由定律：（由定律：（）（）（） （）且（）且（）也為一永真式）也為一永真式 即：即： 且且成立成立反之反之 且且 則則也成立也成立此定理把此定理把“”和和“ ”之間建立了相應的關系。之間建立了相應的關系。921.5 重言式與 蘊含式下面給出常用的蘊含式 I1 （）I2 （ ）I3（） I4 （） I5 （） I6 （）（） （） I7 （）（） （）I8 （）（） （）I9 P 931.5 重言式與 蘊含式I10 I11 （） I12 （） I13 （）（）（） 證明上述蘊含式的方法有三種： （）把“ ”關系符改為“”聯結詞

36、，證明它為永真式。 (a)真值表法 (b)命題演算法941.5 重言式與 蘊含式（）找出使單條件命題前件為“”的所有真值指派，試看能否導致后件均為“”，若為“”，則蘊含關系成立。TTTFFTTTFTFFPQQP951.5 重言式與 蘊含式例：（） 前件為“”的所有指派為、（）均為“”， 為“”，為“”，也應為“”， （） 成立（）找出使單條件命題的后件均為“”的所有真值指派，試看前件的所有真值是否為“”，若是，則蘊含成立。961.5 重言式與 蘊含式例：（） 后件為“”的所有條件是：為“”， 代入前件得 （）若為，則（）為“”； （）若為，則（）為“”； （） 成立 若后件簡單則可選用(3)；

37、若前件簡單則可選用(2)。二種方法是互為獨立的，只需使用一種證明就行。971.5 重言式與 蘊含式討論一下永真式 可得出三個結論： （）若一個命題公式等價于一個永真式，則該公式一定為永真式。 （）若一個永真的命題公式蘊含一個命題公式，則此命題公式一定也為永真式。 （）若一個永假的命題公式蘊含一個命題公式，則該公式可能是永真式、永假式或可滿足的。 981.5 重言式與 蘊含式定理給定命題公式、， 若，且，則。 證明：，且， （）（）為永真式， 由I6：（）（） （）， （）也為永真式；即，成立991.5 重言式與 蘊含式推論推論若若B1、B1 B2Bm ，則，則。定理定理給定一個命題公式、，若給

38、定一個命題公式、，若,，則，則（） 證明：證明：， （）（）為永真式，）為永真式， 由條件，若一定為由條件，若一定為“”，則、均為，則、均為“”， （）也為）也為“”，結論：，結論：（）為為“”。1001.5 重言式與 蘊含式上述也可用等價公式證明它：（）（）（）（ ） （）（）也為永真式（）成立定義設H1,H2.Hm,均為命題公式，若（H1H2 Hm ） ，則稱 H1,H2.Hm,共同蘊含，并記作： H1,H2.Hm 。 1011.5 重言式與 蘊含式 定理若 （H1 H2Hm ）,P ， 則（H1 H2Hm ） （）。 證明：（H1 H2Hm P） （H1 H2Hm P）Q （ H1 H2

39、 Hm ） （ P Q ） （H1 H2Hm ） （ P Q ） H1 H2 . Hm（）也為永真式 （ H1 ,H2 . Hm ）（）成立 1021.6 其他聯結詞其他命題聯結詞：其他命題聯結詞： (1)不可兼或（異或，異）不可兼或（異或，異）(a)符號符號:( ),讀作讀作“異或異或” (b)定義定義:（由真值表）（由真值表）(c)異或的性質：異或的性質：（）（ ） （）（ ） （） ()() FTTTFTTTFFFFP QQP1031.6 其他聯結詞（）（） （）（對 可分配的） 若 ，則有： ， 1041.6 其他聯結詞()“與非”聯結詞：(a)符號,讀作“與的否定”或“與非”(b)定

40、義：（由真值表） （）（）FTTTFTTTFTFFP QQP1051.6 其他聯結詞(c)性質：（）（）（） （）（）（）（）（）（） （）（） 不可結合（）（） 不可結合 ，1061.6 其他聯結詞()“或非”聯結詞：(a)符號：“” （）讀作：“或的否定”或 “或非” (b)定義（由真值表給出）：（） （）FTTFFTFTFTFFQP1071.6 其他聯結詞(c)性質：（可交換的）（）（）（）（）（）（） 不可結合（）（） 不可結合；(d)由（）和（）中的性質可見，和是互為對偶的。 1081.6 其他聯結詞(4)“ 蘊含否定”聯結詞：(a)符號：(b)定義(由真值表給出）：P Q (PQ)

41、“” cFFFFTFTFTFTTP QQPcc1091.6 其他聯結詞()不同真值表的命題公式：按命題公式的生成規則，用聯結詞可組成無限個命題公式。下面討論這些命題公式有多少種不同的真值表：(a)若命題變元只有一個，則用聯結詞組成的命題公式由四種不同的真值表，即為：TFTFTTTFFF3210P1101.6 其他聯結詞所有依賴于的命題公式均等價于這四個中的一個 (b)若有二個命題變元、，則命題公式的不同真值表有：222=24=16種。推廣到一般：若有個變元的命題公式，則可構成不同的真值表為22n（個）。 1111.6 其他聯結詞 （）二元運算中的全部聯結詞總結：（）二元運算中的全部聯結詞總結：

42、 、 是五個基本聯結詞。是五個基本聯結詞。到此為止，一個符號系統已定義完畢，它們是：到此為止，一個符號系統已定義完畢，它們是： 命題變元命題變元 :、值值 :、 運算符運算符 :、 、括號括號 :（）（）關系符關系符 : 、。C1121.6 其他聯結詞全功能聯結詞集合：全功能聯結詞集合： 定義定義一個聯結詞集合，用其中聯結詞構成的式子一個聯結詞集合，用其中聯結詞構成的式子足以把一切命題公式等價的表達出來，則稱此聯足以把一切命題公式等價的表達出來，則稱此聯結詞集合為全功能聯結詞集合（完備聯接詞組）。結詞集合為全功能聯結詞集合（完備聯接詞組）。定義定義設有一聯結詞集合，若設有一聯結詞集合，若 （）

43、用中的聯結詞的等價式能表達任何的一（）用中的聯結詞的等價式能表達任何的一個命題公式；個命題公式； （）刪除中的任一聯結詞，從而形成一個新（）刪除中的任一聯結詞，從而形成一個新的聯結詞集合的聯結詞集合，至少有一個命題公式不能，至少有一個命題公式不能用用中的聯結詞的等價式來表示，則稱中的聯結詞的等價式來表示，則稱A為最為最小的全功能聯結詞集合小的全功能聯結詞集合(最小完備聯接詞組最小完備聯接詞組)。 1131.6 其他聯結詞我們可以證明：，；，；，；均為全功能聯結詞集合，且均是最小的全功能聯結詞集合。 例：用上述最小全功能聯結詞集合中的聯結詞單一表達下述命題公式：1141.6 其他聯結詞（） ，

44、（） （ ） ， （） ， () ， （ ） （）（） （ ） （ ） （） cc1151.7 對偶與范式對偶原理（對偶定律）對偶原理（對偶定律）定義定義給定二個命題公式和給定二個命題公式和A* ，若用，若用代換代換，用用代換代換，用代換，用代換，其中，用代換，用代換，其中一個命題公式由另一個命題公式得來，則稱一個命題公式由另一個命題公式得來，則稱和和A*是互為對偶的，而聯結詞是互為對偶的，而聯結詞和和也是互為也是互為對偶的對偶的例：寫出下列命題公式的對偶式：例：寫出下列命題公式的對偶式： （） （） 對偶式對偶式 A* 1161.7 對偶與范式討論定義：（）若命題公式中有聯結詞，則必須把化成

45、由聯結詞， ，組成的等價的命題公式，然后求它的對偶式；例：求(PQ)(PR)的對偶式1171.7 對偶與范式（）在寫對偶式時，原命題公式中括號不能省去，必須按優先級的次序畫上括號，并在求其對偶式時仍將保留括號。例：（）對偶式寫成 （），而不能寫成1181.7 對偶與范式定理（摩根推廣定理）設和A*為對偶式P1,P2Pn 是出現在和A*中的所有原子命題變元，于是有：（P1，P2Pn） A* （P1，P2Pn）（1）（P1，P2Pn） A*（P1，P2Pn）（）1191.7 對偶與范式證明：由摩根定理（）（） （）（） 不難看出：一個命題公式的否定等價于它的對偶式，且把變元的否定代替每一個變元。例

46、：設（，） （），驗證上述定理：1201.7 對偶與范式證明：()（，） （，） A*（，） A*（，）（）（ ，） A*（，）（ ） 有（ ， ， ） A*（，）1211.7 對偶與范式定理若二個命題公式互為等價，則它們的對偶式也互為等價，亦即若，則A*B*成立。證明：已知：、為任一命題公式，且，要證明A*B*設：P1、P2Pn 是出現在和中的原子命題變元， 1221.7 對偶與范式由，即（P1，P2Pn） （P1，P2Pn） （P1，P2Pn） （P1，P2Pn）由摩根推廣定理*（P1，P2Pn） *（P1，P2Pn）1231.7 對偶與范式*（P1，P2Pn） *（P1，P2Pn）為永真

47、式前面講過永真式的代換實例仍為永真式，所以用 Pi代換A*和B*中的Pi （1in)則得： *（ P1， P2 Pn） *（ P1， P2 Pn）即為：*（P1，P2Pn） *（P1，P2Pn）1241.7 對偶與范式如何判定命題公式為永真式、永假式和可滿足式或二個命題公式等價，歸納有三種方法：（1）真值表法：對于變元的所有真值指 派，看對應命題公式的真值。 （2）命題演算方法：化簡命題公式至最簡式，看是否存在和 （）、（）等價，若不則為可滿足的。（3）范式方法：本節就介紹此法。1251.7 對偶與范式什么叫范式 把命題公式化歸為一種標準的形式，稱此標準形式為范式。什么叫判定 以有限次步驟來決

48、定命題公式是否為永真式、永假式，還是可滿足的，或者判定二個命題公式是否等價等這一類的問題，統稱為判定問題。討論范式和主范式的目的就是為了進行判定。1.7 對偶與范式 范式就是命題公式形式的規范形式。這里約定在范式中 只含有聯結詞、和。一.析取范式與合取范式1.合取式與析取式 合取式：是用“”聯結命題變元或變元的否定構成的式子。 如 P 、P 、PQ、PQR 析取式：是用“” 聯結命題變元或變元的否定構成的式子。 如 P 、P 、PQ、PQR注: PPP PPP P是合(析)取式.n2.析取范式n 公式A如果寫成如下形式：n A1A2.An (n1) 其中每個Ai (i=1,2.n)是合取式，稱

49、之為A的析取范式。 n3.合取范式n 公式A如果寫成如下形式：n A1A2.An (n1) 其中每個Ai (i=1,2.n)是析取式，稱之為A的合取范式。n 例如，PQ 的析取范式與合取范式：n PQ (PQ)(PQ)-析取范式n PQ (PQ)(PQ)-合取范式4.析取范式與合取范式的寫法析取范式與合取范式的寫法 先用相先用相應應的公式去掉的公式去掉和和。 公式公式E16 PQPQ 公式公式E21 PQ (PQ)(PQ) 公式公式E20 PQ (PQ)(QP) 再用再用E16 PQ (PQ)(PQ) 用公式的否定公式或摩根定律將用公式的否定公式或摩根定律將后移到命后移到命題變題變元之前。元之

50、前。 A(P1,P2,Pn)A*(P1,P2,Pn) 底底-摩根定律摩根定律 (PQ)PQ (PQ)PQ 用分配律、用分配律、冪冪等律等公式等律等公式進進行整理，使之成行整理，使之成為為所所要求的形式。要求的形式。 1291.7 對偶與范式（）利用等價公式：化去“”、“”聯結詞，把命題公式變為與其等價的用，表達的公式。 例: ， （）（） （）（） （）將“”深入到原子命題變元之前，并使變元之前最多只有一個“”詞。例：（） 1301.7 對偶與范式（）利用“”對“”的分配，將公式化為析取范式。（）除去永假項得最簡析取范式。例：求（）（）的析取范式： 1311.7 對偶與范式解： （）（( （）

51、 （）) ( （） （）) -（1）化去詞（ ）（）（ ）-（2）將“”深入到變元前面，并最多保留一個（ ）（ ）（ ）（ ）（ ）-（3）“”對或“”的分配，化成為析取范式（）（） -（4）最簡析取范式1321.7 對偶與范式求一個命題公式的合取范式的方法和求析取范式的方法類同： 第（）、（）步相同； 第（）利用“”對“”的分配就行； 第（）去掉永真的析取項。例求(PQ)R的析取范式與合取范式 (PQ)R (PQ)(PQ)R (PQ)(PQ)R -析取范式 (PQ)R(PQ)(PQ)R (PQ)(PQ)R (PQR)(PQR) -合取范式二.主析取范式與主合取范式 一個公式的析取范式與合取范

52、式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。主析取范式 1.小項 定義：在一個有n個命題變元的合取式中，每個變元與它的否定必出現且僅出現一次，稱這個合取式是個小項。 例如，兩個變元的小項： PQ、PQ、 PQ、 PQ 小項的性質 m3 m2 m1 m0 P Q PQ PQ PQ PQ 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F a).有n個變元，則有2n個小項。 b).每一組指派有且只有一個小項為T。為了記憶方便，可將各組指派對應的為T的小項分別記作m0,m1,m2,m2n-1 上例中 m0PQ m1

53、PQ m2PQ m3PQ2.主析取范式定義 析取范式 A1A2.An, , 其中每個Ai (i=1,2.n)都是小項，稱之為主析取范式。3.主析取范式的寫法 方法：列真值表 列出給定公式的真值表。 找出真值表中每個“T”對應的小項。 (如何根據一組指派寫對應的為“T”的項：如果變元P被指派為T，P在小項中以P形式出現；如變元P被指派為F,P在小項中以P形式出現(因要保證該小項為T)。 用“”聯結上述小項，即可。例如求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m0m1m3 (PQ)(PQ)(PQ) PQm0m3 (PQ)(

54、PQ)思考題:永真式的主析取范式是什么樣 ？方法：用公式的等價變換先寫出給定公式的析取范式 A1A2.An 。為使每個Ai都變成小項，對缺少變元的Ai補全變元，比如缺變元R，就用聯結永真式(RR)形式補R。用分配律等公式加以整理。 PQPQ(P(QQ)(P P) Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)主合取范式1.大項定義:在有n個命題變元的析取式中，每個變元與它的否定必出現且僅出現一次,稱之為大項。 例如，有兩個變元的大項及其真值表： M0 M1 M2 M3 P Q PQ PQ PQ PQ F F F T T T F T T F T T T F T T F T T T

55、T T T F大項的性質 a).有n個變元，則有2n個大項。 b).每一組指派有且只有一個大項為F。 為了記憶方便，可將各組指派對應的為F的大項分別記作M0,M1,M2,M2n-1 。 上例中 M0 PQ M1 PQ M2 PQ M3 PQ n2.主合取范式定義n 合取范式 A1A2. An, , 其中每個Ai (i=1,2.n)都是大項，稱之為主合取范式。n3.主合取范式的寫法n 方法：列真值表n 列出給定公式的真值表。n 找出真值表中每個“F”對應的大項。n 如何根據一組指派寫對應的為“F”的大項：n如果變元P被指派為F，P在大項中以P形式出現；n如變元P被指派為T，P在大項中以P形式出現

56、n(確保該大項為F)。n 用“”聯結上述大項，即可。例如求 PQ和PQ的主合取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ M2 PQ PQ M1M2 (PQ )(PQ)例如，求(PQ)R的主合取范式(PQ)R (PQ)R(PQ)R(PR)(QR) (P(QQ)R)(PP)QR) (PQR) (PQR) (PQR)(PQR) (PQR) (PQR)(PQR)課堂練習：課堂練習：1.已知已知A(P,Q,R)的真值表如圖：的真值表如圖：求它的主析取和主合取范式。求它的主析取和主合取范式。2.已知已知A(P,Q,R)的主析取范式中含有下面小項的主析取

57、范式中含有下面小項m1, m3, m5, m7求它的和主合取范式求它的和主合取范式.P Q R A(P,Q,R)F F F TF F T FF T F FF T T TT F F TT F T FT T F TT T T T145討論（）與命題公式等價的主合范式中大項的個數等于其真值表中真值為“”的個數。由真值表找大項的方法為：將表中值為“”的對應真值指派中，把變元寫成否定，把變元的否定寫成變元。（）只要命題公式不是永真式，則一定可以寫出對應與其等價的唯一的主合取范式。146（）若命題公式為含有個變元的永假式，則主合取范式包含了2n個大項的合取式。（）可用主合取范式判定二個命題公式是否等價。（

58、）已知一個命題公式的主析取范式，則一定可以直接寫出與其等價的主合取范式來。反之也行。例： （ ）（）（） 主析取范式 （ ） 主合取范式147（）對應于有個變元的命題公式，則一定有： 主析范式小項數主合范式大項數2n1.8 推理理論 一公安民警審查一件盜竊案，根據下列事實:(1) 張平或王磊盜竊了機房的計算機一臺；(2) 若張平盜竊了計算機，則作案時間不可能發生在午夜之前；(3) 若王磊的證詞正確，則午夜時機房里的燈未滅；(4) 若王磊的證詞不正確，則作案時間發生在午夜之前；(5) 午夜時機房燈光滅了。斷定：盜竊計算機的是王磊。解：（1） 符號化設Z:張平盜竊了計算機；W:王磊盜竊了計算機；M

59、:午夜時燈光滅了；R:作案時間發生在午夜前；S:王磊的證詞正確。ZW Z RS MS RMW1491.8 推理理論 按公認的推論規則，從前提集合中推導出一個結論來，這樣的推導過程稱為演繹，或者叫形式證明。 在任何論證中，若認定前提是真的，且從前提集合推導出結論的論證是遵守了邏輯規則的，則我們稱此結論是合法的。根據邏輯規則推導出來的任何結論稱為有效結論。推論規則就是指確定論證的有效性的判據，常是用命題形式表示這些規則，而不涉及實際命題和它的真值。1501.8 推理理論定義給定二個命題公式和，當且僅當是一個永真式，才可以說是從推導出來的，或稱是前提的有效結論，也稱為由A 推出 B,記作：A B定義

60、設H1，H2,Hm,都是命題公式，當且僅當H1 H2 Hm ，才可以說是前提集合 H1，H2,Hm 的有效結論。記作： H1，H2,Hm 1511.8 推理理論本節介紹的證明方法，歸納分成三類：（一）真值表技術；（二）推論規則；（三）間接證明法。 真值表技術的主要依據是“”的真值表定義。若AB當且僅當（AB）為永真式。TTTFFTTTFTFFQP1521.8 推理理論從給定真值表常用的判斷方法有二種： （）檢查真值表中H1，H2,Hm全部為“”的所有行，看結論是否也均為“”，若均為“”，則結論有效。否則結論無效。（）看結論為“”的所有行，檢查每行前提H1，H2,Hm中是否至少有一個為，若有“”