離散數(shù)學(xué)第1章命題邏輯

1、1離散數(shù)學(xué)離散數(shù)學(xué)(Discrete (Discrete Mathematics)Mathematics)課程學(xué)時(shí)：共課程學(xué)時(shí)：共9696，本，本學(xué)期學(xué)期4848裴振奎裴振奎計(jì)算機(jī)與通信工程學(xué)計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)科學(xué)系院計(jì)算機(jī)科學(xué)系 Tel: Tel: 2課程性質(zhì) 離散數(shù)學(xué)（又稱計(jì)算機(jī)數(shù)學(xué)）是離散數(shù)學(xué)（又稱計(jì)算機(jī)數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計(jì)算機(jī)?，F(xiàn)代數(shù)學(xué)的重要分支，是計(jì)算機(jī)專業(yè)核心基礎(chǔ)課程之一。業(yè)核心基礎(chǔ)課程之一。3課程目標(biāo) 離散數(shù)學(xué)是以研究離散量的結(jié)離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般為：有限或可數(shù)個(gè)其研究對(duì)象一般為：

2、有限或可數(shù)個(gè)元素（例如：自然數(shù)、整數(shù)、真假元素（例如：自然數(shù)、整數(shù)、真假值、有限個(gè)結(jié)點(diǎn)等），而離散性也值、有限個(gè)結(jié)點(diǎn)等），而離散性也是計(jì)算機(jī)科學(xué)的顯著特點(diǎn)。是計(jì)算機(jī)科學(xué)的顯著特點(diǎn)。4與其他課程的關(guān)系 離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)的其他課程離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)的其他課程,如：數(shù)據(jù)如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)、容錯(cuò)技術(shù)、人工智能等有密設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)、容錯(cuò)技術(shù)、人工智能等有密切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。5n離散數(shù)學(xué)n上?？茖W(xué)技術(shù)文獻(xiàn)出版社n左孝凌等編著n離散數(shù)學(xué)n高等教育出版社n耿素

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

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

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

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

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

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

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

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

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

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

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

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

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

16、 之不一定?！啊笔菍?shí)質(zhì)條件命題。例：我買到了魚；:我吃魚。 ：如果我買到了魚，則我吃魚。但“如果我沒買到魚，則我吃魚”，在日常生活中不可能，但在單條件命題的定義中是允許的。 391.2 命題聯(lián)結(jié)詞可以證明： Q P 原命題 逆反命題 逆命題 反命題401.2 命題聯(lián)結(jié)詞列出真值表,由真值表得： 原命題逆反命題；逆命題反命題。 TTTTTTTTFFFTFFTTTFTTTTFFP QP PQQP41n5雙條件聯(lián)結(jié)詞（等價(jià)聯(lián)結(jié)詞）：雙條件聯(lián)結(jié)詞（等價(jià)聯(lián)結(jié)詞）：n（）符號(hào)（）符號(hào)“”，讀作：，讀作：“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”n 、為二個(gè)命題，（、為二個(gè)命題，（）為新）為新的命題，讀作：的命題，讀作：“當(dāng)且僅

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

18、2 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí)命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí) （）先括號(hào)內(nèi)，后括號(hào)外（）先括號(hào)內(nèi)，后括號(hào)外 （）運(yùn)算時(shí)聯(lián)結(jié)詞的優(yōu)先次序?yàn)椋海ǎ┻\(yùn)算時(shí)聯(lián)結(jié)詞的優(yōu)先次序?yàn)椋?（由高到低）（由高到低） （）聯(lián)結(jié)詞按從左到右的次序進(jìn)行運(yùn)算（）聯(lián)結(jié)詞按從左到右的次序進(jìn)行運(yùn)算 （）最外層的括號(hào)一律均可省去（）最外層的括號(hào)一律均可省去 （）可寫成）可寫成471.2 命題聯(lián)結(jié)詞例 （）可省去括號(hào) 因?yàn)椤啊边\(yùn)算是可結(jié)合的。而（）中的括號(hào)不能省去，因“”不滿足結(jié)合律。 481.2 命題聯(lián)結(jié)詞 命題聯(lián)結(jié)詞小結(jié)： （1）五個(gè)聯(lián)結(jié)詞的含義與日常生活中的聯(lián)結(jié)詞 的含義大致相同。 （2）“或”可分為可兼或（）和異或（

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

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

21、形。 該命題符號(hào)化為：P Q541.2 命題聯(lián)結(jié)詞（5）首先用字母表示簡(jiǎn)單命題。 P：老王去上海出差。 Q：小李去上海出差。 該命題符號(hào)化為：P Q 也可符號(hào)化為：（PQ）（PQ）或者 （P Q） （PQ）551.3 命題公式約定：約定： （）我們只注意命題的真假值，而不再去注（）我們只注意命題的真假值，而不再去注意命題的漢語意義。意命題的漢語意義。 （）對(duì)命題聯(lián)結(jié)詞，我們只注意真值表的定（）對(duì)命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生活中的含義。義，而不注意它日常生活中的含義。561.3 命題公式命題公式命題公式命題常元：表示確定的命題命題常元：表示確定的命題T，F(xiàn)。命題變?cè)阂哉?/p>

22、假為其變域之變?cè)?，或沒有指定命題變?cè)阂哉婕贋槠渥冇蛑冊(cè)驔]有指定真值的命題。常用大寫英文字母真值的命題。常用大寫英文字母表示。表示。命題公式：由命題變?cè)?、常元、?lián)結(jié)詞、括號(hào)，命題公式：由命題變?cè)?、常元、?lián)結(jié)詞、括號(hào)， 以規(guī)定的格式聯(lián)結(jié)起來的字符串。以規(guī)定的格式聯(lián)結(jié)起來的字符串。571.3 命題公式定義定義命題公式命題公式(wff)可按下述法則來生成：可按下述法則來生成： ）單個(gè)的命題變?cè)且粋€(gè)命題公式。）單個(gè)的命題變?cè)且粋€(gè)命題公式。 ）若是命題公式，）若是命題公式，也為命題公式。也為命題公式。 ）若、是命題公式，則（）若、是命題公式，則（）、）、 （）、（）、（）、（）、（）均）均為命

23、題公式。為命題公式。 ）當(dāng)且僅當(dāng)有限次使用（）（）（）當(dāng)且僅當(dāng)有限次使用（）（）（）所得到的包含有命題變?cè)兔}常元，聯(lián)結(jié)詞，所得到的包含有命題變?cè)兔}常元，聯(lián)結(jié)詞，括號(hào)的符號(hào)串才是命題公式。括號(hào)的符號(hào)串才是命題公式。 581.3 命題公式例如：(PQ)，(P(QR)，(PQ)R)，P都是命題公式。而(P)，(P)都不是命題公式591.4 真值表與等價(jià)公式命題公式的真值表 :命題變?cè)锰囟ǖ拿}來取代，這一過程稱為對(duì)該命題變?cè)M(jìn)行真值指派。命題公式可以看成是一個(gè)以真假值為定義域和真假值為值域的一個(gè)函數(shù)。寫成(x)601.4 真值表與等價(jià)公式 例如：公式 P (Q R) 定義三元函數(shù) Y(P，

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

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

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

27、有相同的真值，所以。 （）必要性：，即、有相同的真值表，所以 為永真式。例：證明； 711.4 真值表與等價(jià)公式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 真值表與等價(jià)公式下面列出15組等價(jià)公式 （1）雙重否定律 （2）同等律 ；（3）交換律 ； ；（4）結(jié)合律 （）（）； （）（）； （） （）731.4 真值表與等價(jià)公式（5）分配律 （）（）（）； （）（）（）（6）摩根律 （）； （） （7）吸收律 （） ； （） 741.4 真值表與等價(jià)公式（8）蘊(yùn)含律 （9）等

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

29、其中P1、 P2Pn 是是中的原子命題變?cè)械脑用}變?cè)?，若（若?）用某些命題公式代換中的一些原子命題變）用某些命題公式代換中的一些原子命題變?cè)狿i （2）用命題公式）用命題公式i代換代換Pi，則必須用，則必須用i代換中代換中的所有的所有Pi由此而得到的新的命題公式稱為命題公式的代換由此而得到的新的命題公式稱為命題公式的代換實(shí)例實(shí)例781.4 真值表與等價(jià)公式討論定義：討論定義：（）用命題公式只能代換原子命題變?cè)唬ǎ┯妹}公式只能代換原子命題變?cè)?，而?能去代換分子命題公式能去代換分子命題公式 。（）要用命題公式同時(shí)代換同一個(gè)原子命題變（）要用命題公式同時(shí)代換同一個(gè)原子命題變 元

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

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

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

33、個(gè)完全指派，其中的一個(gè)完全指派，其中ui或?yàn)?，或?yàn)椤Ｈ绻麑?duì)于中部分變?cè)x以確定值，其或?yàn)?，或?yàn)椤Ｈ绻麑?duì)于中部分變?cè)x以確定值，其余變?cè)獩]有賦以確定的值，則這樣的一組值稱為公式的余變?cè)獩]有賦以確定的值，則這樣的一組值稱為公式的關(guān)于該變?cè)M的部分指派。關(guān)于該變?cè)M的部分指派。 定義定義使公式取真的指派稱為成真指派。使公式取真的指派稱為成真指派。881.5 重言式與 蘊(yùn)含式定義如果一個(gè)命題公式的所有完全指派均為成真指派，則該公式稱為重言式(永真式)。如果一個(gè)命題公式的所有完全指派均為成假指派，則該公式稱為矛盾式(永假式)。既不是永真式，又不是永假式，則稱此命題公式是可滿足式。討論： （）永真式的否定

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

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

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

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

38、定一個(gè)命題公式、，若,，則，則（） 證明：證明：， （）（）為永真式，）為永真式， 由條件，若一定為由條件，若一定為“”，則、均為，則、均為“”， （）也為）也為“”，結(jié)論：，結(jié)論：（）為為“”。1001.5 重言式與 蘊(yùn)含式上述也可用等價(jià)公式證明它：（）（）（）（ ） （）（）也為永真式（）成立定義設(shè)H1,H2.Hm,均為命題公式，若（H1H2 Hm ） ，則稱 H1,H2.Hm,共同蘊(yùn)含，并記作： H1,H2.Hm 。 1011.5 重言式與 蘊(yùn)含式 定理若 （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 其他聯(lián)結(jié)詞其他命題聯(lián)結(jié)詞：其他命題聯(lián)結(jié)詞： (1)不可兼或（異或，異）不可兼或（異或，異）(a)符號(hào)符號(hào):( ),讀作讀作“異或異或” (b)定義定義:（由真值表）（由真值表）(c)異或的性質(zhì)：異或的性質(zhì)：（）（ ） （）（ ） （） ()() FTTTFTTTFFFFP QQP1031.6 其他聯(lián)結(jié)詞（）（） （）（對(duì) 可分配的） 若 ，則有： ， 1041.6 其他聯(lián)結(jié)詞()“與非”聯(lián)結(jié)詞：(a)符號(hào),讀作“與的否定”或“與非”(b)定

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

41、“” cFFFFTFTFTFTTP QQPcc1091.6 其他聯(lián)結(jié)詞()不同真值表的命題公式：按命題公式的生成規(guī)則，用聯(lián)結(jié)詞可組成無限個(gè)命題公式。下面討論這些命題公式有多少種不同的真值表：(a)若命題變?cè)挥幸粋€(gè)，則用聯(lián)結(jié)詞組成的命題公式由四種不同的真值表，即為：TFTFTTTFFF3210P1101.6 其他聯(lián)結(jié)詞所有依賴于的命題公式均等價(jià)于這四個(gè)中的一個(gè) (b)若有二個(gè)命題變?cè)?，則命題公式的不同真值表有：222=24=16種。推廣到一般：若有個(gè)變?cè)拿}公式，則可構(gòu)成不同的真值表為22n（個(gè)）。 1111.6 其他聯(lián)結(jié)詞 （）二元運(yùn)算中的全部聯(lián)結(jié)詞總結(jié)：（）二元運(yùn)算中的全部聯(lián)結(jié)詞總結(jié)：

42、 、 是五個(gè)基本聯(lián)結(jié)詞。是五個(gè)基本聯(lián)結(jié)詞。到此為止，一個(gè)符號(hào)系統(tǒng)已定義完畢，它們是：到此為止，一個(gè)符號(hào)系統(tǒng)已定義完畢，它們是： 命題變?cè)}變?cè)?:、值值 :、 運(yùn)算符運(yùn)算符 :、 、括號(hào)括號(hào) :（）（）關(guān)系符關(guān)系符 : 、。C1121.6 其他聯(lián)結(jié)詞全功能聯(lián)結(jié)詞集合：全功能聯(lián)結(jié)詞集合： 定義定義一個(gè)聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子一個(gè)聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)的表達(dá)出來，則稱此聯(lián)足以把一切命題公式等價(jià)的表達(dá)出來，則稱此聯(lián)結(jié)詞集合為全功能聯(lián)結(jié)詞集合（完備聯(lián)接詞組）。結(jié)詞集合為全功能聯(lián)結(jié)詞集合（完備聯(lián)接詞組）。定義定義設(shè)有一聯(lián)結(jié)詞集合，若設(shè)有一聯(lián)結(jié)詞集合，若 （）

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

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

45、由聯(lián)結(jié)詞， ，組成的等價(jià)的命題公式，然后求它的對(duì)偶式；例：求(PQ)(PR)的對(duì)偶式1171.7 對(duì)偶與范式（）在寫對(duì)偶式時(shí)，原命題公式中括號(hào)不能省去，必須按優(yōu)先級(jí)的次序畫上括號(hào)，并在求其對(duì)偶式時(shí)仍將保留括號(hào)。例：（）對(duì)偶式寫成 （），而不能寫成1181.7 對(duì)偶與范式定理（摩根推廣定理）設(shè)和A*為對(duì)偶式P1,P2Pn 是出現(xiàn)在和A*中的所有原子命題變?cè)?，于是有：（P1，P2Pn） A* （P1，P2Pn）（1）（P1，P2Pn） A*（P1，P2Pn）（）1191.7 對(duì)偶與范式證明：由摩根定理（）（） （）（） 不難看出：一個(gè)命題公式的否定等價(jià)于它的對(duì)偶式，且把變?cè)姆穸ù婷恳粋€(gè)變?cè)＠?/p>

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

47、式前面講過永真式的代換實(shí)例仍為永真式，所以用 Pi代換A*和B*中的Pi （1in)則得： *（ P1， P2 Pn） *（ P1， P2 Pn）即為：*（P1，P2Pn） *（P1，P2Pn）1241.7 對(duì)偶與范式如何判定命題公式為永真式、永假式和可滿足式或二個(gè)命題公式等價(jià)，歸納有三種方法：（1）真值表法：對(duì)于變?cè)乃姓嬷抵?派，看對(duì)應(yīng)命題公式的真值。 （2）命題演算方法：化簡(jiǎn)命題公式至最簡(jiǎn)式，看是否存在和 （）、（）等價(jià)，若不則為可滿足的。（3）范式方法：本節(jié)就介紹此法。1251.7 對(duì)偶與范式什么叫范式 把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。什么叫判定 以有限次步驟來決

48、定命題公式是否為永真式、永假式，還是可滿足的，或者判定二個(gè)命題公式是否等價(jià)等這一類的問題，統(tǒng)稱為判定問題。討論范式和主范式的目的就是為了進(jìn)行判定。1.7 對(duì)偶與范式 范式就是命題公式形式的規(guī)范形式。這里約定在范式中 只含有聯(lián)結(jié)詞、和。一.析取范式與合取范式1.合取式與析取式 合取式：是用“”聯(lián)結(jié)命題變?cè)蜃冊(cè)姆穸?gòu)成的式子。 如 P 、P 、PQ、PQR 析取式：是用“” 聯(lián)結(jié)命題變?cè)蜃冊(cè)姆穸?gòu)成的式子。 如 P 、P 、PQ、PQR注: PPP PPP P是合(析)取式.n2.析取范式n 公式A如果寫成如下形式：n A1A2.An (n1) 其中每個(gè)Ai (i=1,2.n)是合取式，稱

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

50、前。 A(P1,P2,Pn)A*(P1,P2,Pn) 底底-摩根定律摩根定律 (PQ)PQ (PQ)PQ 用分配律、用分配律、冪冪等律等公式等律等公式進(jìn)進(jìn)行整理，使之成行整理，使之成為為所所要求的形式。要求的形式。 1291.7 對(duì)偶與范式（）利用等價(jià)公式：化去“”、“”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用，表達(dá)的公式。 例: ， （）（） （）（） （）將“”深入到原子命題變?cè)埃⑹棺冊(cè)白疃嘀挥幸粋€(gè)“”詞。例：（） 1301.7 對(duì)偶與范式（）利用“”對(duì)“”的分配，將公式化為析取范式。（）除去永假項(xiàng)得最簡(jiǎn)析取范式。例：求（）（）的析取范式： 1311.7 對(duì)偶與范式解： （）（( （）

51、 （）) ( （） （）) -（1）化去詞（ ）（）（ ）-（2）將“”深入到變?cè)懊妫⒆疃啾Ａ粢粋€(gè)（ ）（ ）（ ）（ ）（ ）-（3）“”對(duì)或“”的分配，化成為析取范式（）（） -（4）最簡(jiǎn)析取范式1321.7 對(duì)偶與范式求一個(gè)命題公式的合取范式的方法和求析取范式的方法類同： 第（）、（）步相同； 第（）利用“”對(duì)“”的分配就行； 第（）去掉永真的析取項(xiàng)。例求(PQ)R的析取范式與合取范式 (PQ)R (PQ)(PQ)R (PQ)(PQ)R -析取范式 (PQ)R(PQ)(PQ)R (PQ)(PQ)R (PQR)(PQR) -合取范式二.主析取范式與主合取范式 一個(gè)公式的析取范式與合取范

52、式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。主析取范式 1.小項(xiàng) 定義：在一個(gè)有n個(gè)命題變?cè)暮先∈街校總€(gè)變?cè)c它的否定必出現(xiàn)且僅出現(xiàn)一次，稱這個(gè)合取式是個(gè)小項(xiàng)。 例如，兩個(gè)變?cè)男№?xiàng)： PQ、PQ、 PQ、 PQ 小項(xiàng)的性質(zhì) 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個(gè)變?cè)?，則有2n個(gè)小項(xiàng)。 b).每一組指派有且只有一個(gè)小項(xiàng)為T。為了記憶方便，可將各組指派對(duì)應(yīng)的為T的小項(xiàng)分別記作m0,m1,m2,m2n-1 上例中 m0PQ m1

53、PQ m2PQ m3PQ2.主析取范式定義 析取范式 A1A2.An, , 其中每個(gè)Ai (i=1,2.n)都是小項(xiàng)，稱之為主析取范式。3.主析取范式的寫法 方法：列真值表 列出給定公式的真值表。 找出真值表中每個(gè)“T”對(duì)應(yīng)的小項(xiàng)。 (如何根據(jù)一組指派寫對(duì)應(yīng)的為“T”的項(xiàng)：如果變?cè)狿被指派為T，P在小項(xiàng)中以P形式出現(xiàn)；如變?cè)狿被指派為F,P在小項(xiàng)中以P形式出現(xiàn)(因要保證該小項(xiàng)為T)。 用“”聯(lián)結(jié)上述小項(xiàng)，即可。例如求 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)思考題:永真式的主析取范式是什么樣 ？方法：用公式的等價(jià)變換先寫出給定公式的析取范式 A1A2.An 。為使每個(gè)Ai都變成小項(xiàng)，對(duì)缺少變?cè)腁i補(bǔ)全變?cè)?，比如缺變?cè)猂，就用聯(lián)結(jié)永真式(RR)形式補(bǔ)R。用分配律等公式加以整理。 PQPQ(P(QQ)(P P) Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)主合取范式1.大項(xiàng)定義:在有n個(gè)命題變?cè)奈鋈∈街?，每個(gè)變?cè)c它的否定必出現(xiàn)且僅出現(xiàn)一次,稱之為大項(xiàng)。 例如，有兩個(gè)變?cè)拇箜?xiàng)及其真值表： 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大項(xiàng)的性質(zhì) a).有n個(gè)變?cè)?，則有2n個(gè)大項(xiàng)。 b).每一組指派有且只有一個(gè)大項(xiàng)為F。 為了記憶方便，可將各組指派對(duì)應(yīng)的為F的大項(xiàng)分別記作M0,M1,M2,M2n-1 。 上例中 M0 PQ M1 PQ M2 PQ M3 PQ n2.主合取范式定義n 合取范式 A1A2. An, , 其中每個(gè)Ai (i=1,2.n)都是大項(xiàng)，稱之為主合取范式。n3.主合取范式的寫法n 方法：列真值表n 列出給定公式的真值表。n 找出真值表中每個(gè)“F”對(duì)應(yīng)的大項(xiàng)。n 如何根據(jù)一組指派寫對(duì)應(yīng)的為“F”的大項(xiàng)：n如果變?cè)狿被指派為F，P在大項(xiàng)中以P形式出現(xiàn)；n如變?cè)狿被指派為T，P在大項(xiàng)中以P形式出現(xiàn)

56、n(確保該大項(xiàng)為F)。n 用“”聯(lián)結(jié)上述大項(xiàng)，即可。例如求 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)課堂練習(xí)：課堂練習(xí)：1.已知已知A(P,Q,R)的真值表如圖：的真值表如圖：求它的主析取和主合取范式。求它的主析取和主合取范式。2.已知已知A(P,Q,R)的主析取范式中含有下面小項(xiàng)的主析取

57、范式中含有下面小項(xiàng)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討論（）與命題公式等價(jià)的主合范式中大項(xiàng)的個(gè)數(shù)等于其真值表中真值為“”的個(gè)數(shù)。由真值表找大項(xiàng)的方法為：將表中值為“”的對(duì)應(yīng)真值指派中，把變?cè)獙懗煞穸?，把變?cè)姆穸▽懗勺冊(cè)＃ǎ┲灰}公式不是永真式，則一定可以寫出對(duì)應(yīng)與其等價(jià)的唯一的主合取范式。146（）若命題公式為含有個(gè)變?cè)挠兰偈?，則主合取范式包含了2n個(gè)大項(xiàng)的合取式。（）可用主合取范式判定二個(gè)命題公式是否等價(jià)。（

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

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

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