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

1、2021-10-281第九章第九章命題邏輯命題邏輯 數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門(mén)學(xué)科。所謂數(shù)學(xué)數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門(mén)學(xué)科。所謂數(shù)學(xué)方法是指方法是指:用一套數(shù)學(xué)的符號(hào)系統(tǒng)來(lái)描述和處理思維的形式與規(guī)律。用一套數(shù)學(xué)的符號(hào)系統(tǒng)來(lái)描述和處理思維的形式與規(guī)律。因此因此,數(shù)理邏輯又稱為符號(hào)邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)數(shù)理邏輯又稱為符號(hào)邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系,并給出推理規(guī)則并給出推理規(guī)則

2、,進(jìn)行命題進(jìn)行命題演繹。演繹。主要內(nèi)容如下：主要內(nèi)容如下：9.1命題和命題聯(lián)結(jié)詞命題和命題聯(lián)結(jié)詞9.2命題公式命題公式9.3命題公式的等值關(guān)系和蘊(yùn)含關(guān)系命題公式的等值關(guān)系和蘊(yùn)含關(guān)系9.5命題演算的推理理論命題演算的推理理論2021-10-282 邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者古希臘學(xué)者亞里士多德亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問(wèn)題的學(xué)科就叫做數(shù)理邏輯，也叫做符號(hào)邏輯。、證明等問(wèn)題的學(xué)科就叫做數(shù)理邏輯，也叫做符號(hào)邏輯。 利用計(jì)算的方法來(lái)代替人們思維中的邏輯推理過(guò)程，這利用

3、計(jì)算的方法來(lái)代替人們思維中的邏輯推理過(guò)程，這種想法早在十七世紀(jì)就有人提出過(guò)。種想法早在十七世紀(jì)就有人提出過(guò)。萊布尼茨萊布尼茨就曾經(jīng)設(shè)想過(guò)就曾經(jīng)設(shè)想過(guò)能不能創(chuàng)造一種能不能創(chuàng)造一種“通用的科學(xué)語(yǔ)言通用的科學(xué)語(yǔ)言”，可以把推理過(guò)程象數(shù)，可以把推理過(guò)程象數(shù)學(xué)一樣利用公式來(lái)進(jìn)行計(jì)算，從而得出正確的結(jié)論。由于當(dāng)學(xué)一樣利用公式來(lái)進(jìn)行計(jì)算，從而得出正確的結(jié)論。由于當(dāng)時(shí)的社會(huì)條件，他的想法并沒(méi)有實(shí)現(xiàn)。但是它的思想?yún)s是現(xiàn)時(shí)的社會(huì)條件，他的想法并沒(méi)有實(shí)現(xiàn)。但是它的思想?yún)s是現(xiàn)代數(shù)理邏輯部分內(nèi)容的萌芽，從這個(gè)意義上講，萊布尼茨的代數(shù)理邏輯部分內(nèi)容的萌芽，從這個(gè)意義上講，萊布尼茨的思想可以說(shuō)是數(shù)理邏輯的先驅(qū)。思想可以說(shuō)是

4、數(shù)理邏輯的先驅(qū)。2021-10-2831847年，英國(guó)數(shù)學(xué)家年，英國(guó)數(shù)學(xué)家布爾布爾發(fā)表了發(fā)表了邏輯的數(shù)學(xué)分析邏輯的數(shù)學(xué)分析，建立了建立了“布爾代數(shù)布爾代數(shù)”，并創(chuàng)造一套符號(hào)系統(tǒng)，利用符號(hào)來(lái)表，并創(chuàng)造一套符號(hào)系統(tǒng)，利用符號(hào)來(lái)表示邏輯中的各種概念。布爾建立了一系列的運(yùn)算法則，利用示邏輯中的各種概念。布爾建立了一系列的運(yùn)算法則，利用代數(shù)的方法研究邏輯問(wèn)題，初步奠定了數(shù)理邏輯的基礎(chǔ)。代數(shù)的方法研究邏輯問(wèn)題，初步奠定了數(shù)理邏輯的基礎(chǔ)。十九世紀(jì)末二十世紀(jì)初，數(shù)理邏輯有了比較大的發(fā)展，十九世紀(jì)末二十世紀(jì)初，數(shù)理邏輯有了比較大的發(fā)展，1884年，德國(guó)數(shù)學(xué)家弗雷格出版了年，德國(guó)數(shù)學(xué)家弗雷格出版了數(shù)論的基礎(chǔ)數(shù)論的

5、基礎(chǔ)一書(shū)，在一書(shū)，在書(shū)中引入量詞的符號(hào)，使得數(shù)理邏輯的符號(hào)系統(tǒng)更加完備。書(shū)中引入量詞的符號(hào)，使得數(shù)理邏輯的符號(hào)系統(tǒng)更加完備。對(duì)建立這門(mén)學(xué)科做出貢獻(xiàn)的，還有美國(guó)人皮爾斯，他也在著對(duì)建立這門(mén)學(xué)科做出貢獻(xiàn)的，還有美國(guó)人皮爾斯，他也在著作中引入了邏輯符號(hào)。從而使現(xiàn)代數(shù)理邏輯最基本的理論基作中引入了邏輯符號(hào)。從而使現(xiàn)代數(shù)理邏輯最基本的理論基礎(chǔ)逐步形成，成為一門(mén)獨(dú)立的學(xué)科。礎(chǔ)逐步形成，成為一門(mén)獨(dú)立的學(xué)科。2021-10-284 非歐幾何的產(chǎn)生和集合論的悖論的發(fā)現(xiàn)非歐幾何的產(chǎn)生和集合論的悖論的發(fā)現(xiàn),說(shuō)明數(shù)學(xué)本身還存說(shuō)明數(shù)學(xué)本身還存在許多問(wèn)題，為了研究數(shù)學(xué)系統(tǒng)的無(wú)矛盾性問(wèn)題，需要以數(shù)學(xué)在許多問(wèn)題，為了研究數(shù)學(xué)

6、系統(tǒng)的無(wú)矛盾性問(wèn)題，需要以數(shù)學(xué)理論體系的概念、命題、證明等作為研究對(duì)象，研究數(shù)學(xué)系統(tǒng)理論體系的概念、命題、證明等作為研究對(duì)象，研究數(shù)學(xué)系統(tǒng)的邏輯結(jié)構(gòu)和證明的規(guī)律，這樣又產(chǎn)生了數(shù)理邏輯的另一個(gè)分的邏輯結(jié)構(gòu)和證明的規(guī)律，這樣又產(chǎn)生了數(shù)理邏輯的另一個(gè)分支支證明論。證明論。數(shù)理邏輯還發(fā)展了許多新的分支數(shù)理邏輯還發(fā)展了許多新的分支,如遞歸論、模型論等。遞歸如遞歸論、模型論等。遞歸論主要研究可計(jì)算性的理論，它和計(jì)算機(jī)的發(fā)展和應(yīng)用有密切論主要研究可計(jì)算性的理論，它和計(jì)算機(jī)的發(fā)展和應(yīng)用有密切的關(guān)系。模型論主要是研究形式系統(tǒng)和數(shù)學(xué)模型之間的關(guān)系。的關(guān)系。模型論主要是研究形式系統(tǒng)和數(shù)學(xué)模型之間的關(guān)系。數(shù)理邏輯近年

7、來(lái)發(fā)展特別迅速，主要原因是這門(mén)學(xué)科對(duì)于數(shù)數(shù)理邏輯近年來(lái)發(fā)展特別迅速，主要原因是這門(mén)學(xué)科對(duì)于數(shù)學(xué)其它分支如集合論、數(shù)論、代數(shù)、拓?fù)鋵W(xué)等的發(fā)展有重大的學(xué)其它分支如集合論、數(shù)論、代數(shù)、拓?fù)鋵W(xué)等的發(fā)展有重大的影響，特別是對(duì)計(jì)算機(jī)科學(xué)的發(fā)展起了推動(dòng)作用。反過(guò)來(lái)，其影響，特別是對(duì)計(jì)算機(jī)科學(xué)的發(fā)展起了推動(dòng)作用。反過(guò)來(lái)，其他學(xué)科的發(fā)展也推動(dòng)了數(shù)理邏輯的發(fā)展。他學(xué)科的發(fā)展也推動(dòng)了數(shù)理邏輯的發(fā)展。2021-10-285問(wèn)題o 1.如何用符號(hào)有效地表示實(shí)際應(yīng)用中的邏輯問(wèn)題?o 2.如何用符號(hào)進(jìn)行邏輯演算、推理和論證？o 3.如何將邏輯問(wèn)題計(jì)算機(jī)化、自動(dòng)化？2021-10-2869.1命題和命題聯(lián)結(jié)詞命題和命題聯(lián)結(jié)詞

8、9.1.1命題的概念命題的概念命題命題：是能分辨真假的陳述句。：是能分辨真假的陳述句。例例1判斷下列語(yǔ)句是否是命題。判斷下列語(yǔ)句是否是命題。（1）空氣是人生存所必需的）空氣是人生存所必需的（2）請(qǐng)把門(mén)關(guān)上。）請(qǐng)把門(mén)關(guān)上。（3）南京是中國(guó)的首都。）南京是中國(guó)的首都。（4）你吃飯了嗎？）你吃飯了嗎？（5）x=3。（6）明年春節(jié)是個(gè)大晴天。）明年春節(jié)是個(gè)大晴天。（7）我正在說(shuō)謊。）我正在說(shuō)謊。解解 語(yǔ)句（語(yǔ)句（1）,（3）,（5），），(6)是陳述句是陳述句（1），（），（3），），(6)是命題是命題.（7）是悖論）是悖論2021-10-287 用真值來(lái)描述命題是用真值來(lái)描述命題是“真真”還是還是“

9、假假”。分別用。分別用“1”和和“0”表示表示命題用大寫(xiě)的拉丁字母命題用大寫(xiě)的拉丁字母A、B、C、P、Q、或者帶下標(biāo)的大寫(xiě)的字母來(lái)表示?；蛘邘聵?biāo)的大寫(xiě)的字母來(lái)表示。例例2 判斷下列陳述句是否是命題。判斷下列陳述句是否是命題。P：地球外的星球上也有人；：地球外的星球上也有人；Q：小王是我的好朋友；：小王是我的好朋友；解解P、Q是命題是命題2021-10-2889.1.2命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞 原子命題原子命題：由簡(jiǎn)單句形成的命題。：由簡(jiǎn)單句形成的命題。 復(fù)合命題復(fù)合命題：由一個(gè)或幾個(gè)原子命題通過(guò)聯(lián)結(jié)詞的聯(lián)接：由一個(gè)或幾個(gè)原子命題通過(guò)聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。而構(gòu)成的命題。例例3A：李明既是三好學(xué)

10、生又是足球隊(duì)員。：李明既是三好學(xué)生又是足球隊(duì)員。B：張平或者正在釣魚(yú)或者正在睡覺(jué)。：張平或者正在釣魚(yú)或者正在睡覺(jué)。C：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會(huì)。：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會(huì)。2021-10-289定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。1.否定否定“”定義定義9-1設(shè)設(shè)P是一個(gè)命題，利用是一個(gè)命題，利用“”和和P組成的復(fù)合命題稱組成的復(fù)合命題稱為為P的的否命題否命題，記作，記作“P”(讀作讀作“非非P”)。命題命題P取值為真時(shí)，命題取值為真時(shí)，命題P取值為假；命題取值為假；命題P取值為假時(shí)，命題取值為假時(shí)，命題P取值為真。取值為真。例例

11、4設(shè)設(shè)P：上海是一個(gè)城市；：上海是一個(gè)城市；Q：每個(gè)自然數(shù)都是偶數(shù)。：每個(gè)自然數(shù)都是偶數(shù)。 P P 1001則有則有P：上海不是一個(gè)城市：上海不是一個(gè)城市;Q：并非每個(gè)自然數(shù)都是偶數(shù)。：并非每個(gè)自然數(shù)都是偶數(shù)。2021-10-28102合取合取“”定義定義9-2設(shè)設(shè)P和和Q是兩個(gè)命題，由是兩個(gè)命題，由P、Q利用利用“”組成的復(fù)合命題，稱為組成的復(fù)合命題，稱為合取式復(fù)合命題合取式復(fù)合命題，記作，記作“PQ”（讀作（讀作“P且且Q”）。）。當(dāng)且僅當(dāng)命題當(dāng)且僅當(dāng)命題P和和Q均取值為真時(shí)，均取值為真時(shí)，PQ才取值為真。才取值為真。 例例5設(shè)設(shè)P：我們?nèi)タ措娪?。：我們?nèi)タ措娪?。Q：房間里有十張桌子。則：

12、房間里有十張桌子。則PQ表示表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。我們?nèi)タ措娪安⑶曳块g里有十張桌子。”P(pán)QPQ0000101001112021-10-28113.析取析取“”定義定義9-3由命題由命題P和和Q利用利用“”組成的復(fù)合命題，稱為組成的復(fù)合命題，稱為析析取式復(fù)合命題取式復(fù)合命題，記作，記作“PQ”（讀作（讀作“P或或Q”）。）。當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P和和Q至少有一個(gè)取值至少有一個(gè)取值為真時(shí)，為真時(shí)，PQ取值為真。取值為真。 PQPQ000011101111例例6將命題將命題“他可能是他可能是100米或米或400米賽跑的冠軍。米賽跑的冠軍?！狈?hào)化。符號(hào)化。解令解令P：他可能是：他可能是

13、100米賽跑冠軍；米賽跑冠軍；Q：他可能是：他可能是400米賽跑冠軍。米賽跑冠軍。則命題可表示為則命題可表示為PQ。2021-10-2812設(shè)設(shè)P、Q是兩個(gè)命題，是兩個(gè)命題，P異或異或Q是是一個(gè)復(fù)合命題，記作一個(gè)復(fù)合命題，記作PQ。 PQPQ000011101110例例7今天晚上我在家看電視或去劇場(chǎng)看戲。今天晚上我在家看電視或去劇場(chǎng)看戲。令令P：今天晚上我在家看電視。：今天晚上我在家看電視。Q：今天晚上我去劇場(chǎng)看戲：今天晚上我去劇場(chǎng)看戲例例7中的命題可表示為中的命題可表示為PQ，或者表示為，或者表示為（PQ)(PQ)。由于由于“”可用可用“”，“”和和“”表示，故我表示，故我們不把它當(dāng)作們不把

14、它當(dāng)作基本基本聯(lián)結(jié)詞。聯(lián)結(jié)詞。2021-10-28134.蘊(yùn)含蘊(yùn)含“”定義定義9-4由命題由命題P和和Q利用利用“”組成的復(fù)合命題，稱為組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題蘊(yùn)含式復(fù)合命題，記作，記作“PQ”（讀作（讀作“如果如果P，則，則Q”）。）。當(dāng)當(dāng)P為真，為真，Q為假時(shí)，為假時(shí)，PQ為為假，否則假，否則PQ為真。為真。PQPQ001011100111例例8將命題將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它。如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)符號(hào)化?；?。解解令令P：我得到這本小說(shuō)；：我得到這本小說(shuō)；Q：我今夜就讀完它。：我今夜就讀完它。于是上述命題可表示為于是上述命題可表示為P

15、Q。例例9若若P：雪是黑色的；：雪是黑色的；Q：太陽(yáng)從西邊升起；：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。則：太陽(yáng)從東邊升起。則PQ和和PR所表示的命題都是真的所表示的命題都是真的.2021-10-28145等值等值“”定義定義9-5由命題由命題P和和Q，利用，利用“”組成的復(fù)合命題組成的復(fù)合命題,稱為稱為等值式復(fù)合命題等值式復(fù)合命題，記作，記作“PQ”（讀作（讀作“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”）。）。當(dāng)當(dāng)P和和Q的真值相同時(shí)的真值相同時(shí),PQ取真取真,否則取假。否則取假。 PQPQ001010100111例例10非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。解解令令P：某人是倉(cāng)庫(kù)工作

16、人員；：某人是倉(cāng)庫(kù)工作人員；Q：某人可以進(jìn)入倉(cāng)庫(kù)。：某人可以進(jìn)入倉(cāng)庫(kù)。則上述命題可表示為則上述命題可表示為PQ。2021-10-2815 例例11黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù)是素?cái)?shù)令令P：黃山比喜馬拉雅山高；：黃山比喜馬拉雅山高；Q：3是素?cái)?shù)是素?cái)?shù)本例可符號(hào)化為本例可符號(hào)化為PQ 從漢語(yǔ)的語(yǔ)義看，從漢語(yǔ)的語(yǔ)義看，P與與Q之間并無(wú)聯(lián)系，但就聯(lián)結(jié)之間并無(wú)聯(lián)系，但就聯(lián)結(jié)詞詞的定義來(lái)看，因?yàn)榈亩x來(lái)看，因?yàn)镻的真值為假，的真值為假，Q的真值為真，的真值為真，所以所以PQ的真值為假。的真值為假。 對(duì)于上述五種聯(lián)結(jié)詞，應(yīng)注意到：對(duì)于上述五種聯(lián)結(jié)詞，應(yīng)注意到：復(fù)合命題的真

17、值只取決于構(gòu)成它的各原子命題的真復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無(wú)關(guān)。值，而與這些原子命題的內(nèi)容含義無(wú)關(guān)。2021-10-28169.1.3命題符號(hào)化命題符號(hào)化利用聯(lián)結(jié)詞可以把許多日常語(yǔ)句符號(hào)化?；静襟E如下：利用聯(lián)結(jié)詞可以把許多日常語(yǔ)句符號(hào)化?；静襟E如下：（1）從語(yǔ)句中分析出各原子命題，將它們符號(hào)化；）從語(yǔ)句中分析出各原子命題，將它們符號(hào)化；（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來(lái)，）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來(lái)，組成復(fù)合命題的符號(hào)化表示。組成復(fù)合命題的符號(hào)化表示。2021-10-2817例例12用符號(hào)形式表示下列命題。用

18、符號(hào)形式表示下列命題。（1）如果明天早上下雨或下雪，那么我不去學(xué)校）如果明天早上下雨或下雪，那么我不去學(xué)校（2）如果明天早上不下雨且不下雪，那么我去學(xué)校。）如果明天早上不下雨且不下雪，那么我去學(xué)校。（3）如果明天早上不是雨夾雪，那么我去學(xué)校。）如果明天早上不是雨夾雪，那么我去學(xué)校。（4）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。解解令令P：明天早上下雨；：明天早上下雨；Q：明天早上下雪；：明天早上下雪；R：我去學(xué)校。：我去學(xué)校。（2）（）（PQ）R； （1）（）（PQ）R；（4）R（PQ） （3）(PQ）R；2021-10-2818例例13將下列

19、命題符號(hào)化將下列命題符號(hào)化（1）派小王或小李出差；派小王或小李出差；（2）我們不能既劃船又跑步；我們不能既劃船又跑步；（3）如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定；如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定；解解（1）令令P：派小王出差；：派小王出差；Q：派小李出差。：派小李出差。命題符號(hào)化為命題符號(hào)化為PQ。 （2）令令P：我們劃船；：我們劃船；Q：我們跑步。則命題可：我們跑步。則命題可表示為表示為(PQ）。）。 （3）令）令P：你來(lái)了；：你來(lái)了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。則命題可表示為則命題可表示為P（QR）2021-10-2819（4）如果李明是體育愛(ài)好者，但不

20、是文藝愛(ài)好者，那么如果李明是體育愛(ài)好者，但不是文藝愛(ài)好者，那么李明不是文體愛(ài)好者李明不是文體愛(ài)好者（5）假如上午不下雨，我去看電影，否則就在家里看書(shū)。假如上午不下雨，我去看電影，否則就在家里看書(shū)。（4）令）令P：李明是體育愛(ài)好者；：李明是體育愛(ài)好者；Q：李明是文藝愛(ài)好者。：李明是文藝愛(ài)好者。則命題可表示為（則命題可表示為（PQ）（PQ）（5）令）令P：上午下雨；：上午下雨；Q：我去看電影；：我去看電影；R：我在家讀書(shū)。：我在家讀書(shū)。則命題可表示為（則命題可表示為（PQ）（PR）。）。解：解：2021-10-28201.判斷下列語(yǔ)句哪些是命題，若是命題，則指出其真值。判斷下列語(yǔ)句哪些是命題，若是

21、命題，則指出其真值。（1）只有小孩才愛(ài)哭。只有小孩才愛(ài)哭。（2）X+6=Y（3）銀是白的。銀是白的。（4）起來(lái)吧，我的朋友。起來(lái)吧，我的朋友。(是是假假) (不是不是)(是是真真) (不是不是)練練 習(xí)習(xí)2021-10-2821 2將下列命題符號(hào)化將下列命題符號(hào)化（1）我看見(jiàn)的既不是小張也不是老李。）我看見(jiàn)的既不是小張也不是老李。 解解令令P：我看見(jiàn)的是小張；：我看見(jiàn)的是小張；Q：我看見(jiàn)的是老李。：我看見(jiàn)的是老李。則該命題可表示為則該命題可表示為PQ （2）如果晚上做完了作業(yè)并且沒(méi)有其它的事，如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)看電視或聽(tīng)音樂(lè)。他就會(huì)看電視或聽(tīng)音樂(lè)。解解令令P：他晚上做完

22、了作業(yè)；：他晚上做完了作業(yè)；Q：他晚上有其它的事；：他晚上有其它的事；R：他看電視；：他看電視；S：他聽(tīng)音樂(lè)。：他聽(tīng)音樂(lè)。則該命題可表示為則該命題可表示為（PQ）（RS）2021-10-28229.2命題公式命題公式9.2.1命題公式的概念命題公式的概念1.命題常元命題常元:一個(gè)表示確定命題的大寫(xiě)字母。一個(gè)表示確定命題的大寫(xiě)字母。2命題變?cè)}變?cè)?一個(gè)沒(méi)有指定具體內(nèi)容的命題符號(hào)。一個(gè)沒(méi)有指定具體內(nèi)容的命題符號(hào)。 一個(gè)命題變?cè)?dāng)沒(méi)有對(duì)其賦予內(nèi)容時(shí)，它的真值一個(gè)命題變?cè)?dāng)沒(méi)有對(duì)其賦予內(nèi)容時(shí)，它的真值不能確定，一旦用一個(gè)具體的命題代入，它的真值就確不能確定，一旦用一個(gè)具體的命題代入，它的真值就確定

23、了。定了。3.命題公式命題公式 命題公式（或簡(jiǎn)稱公式）是由命題公式（或簡(jiǎn)稱公式）是由0、1和命題變?cè)院兔}變?cè)约懊}聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號(hào)串（或者說(shuō)一及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號(hào)串（或者說(shuō)一個(gè)表達(dá)式）。個(gè)表達(dá)式）。2021-10-2823定義定義9-6（命題公式的遞歸定義）（命題公式的遞歸定義）(1)0，1是命題公式；是命題公式；(2)命題變?cè)敲}公式；命題變?cè)敲}公式；(3)如果如果A是命題公式，則是命題公式，則A是命題公式；是命題公式；(4)如果如果A和和B是命題公式，則（是命題公式，則（AB），），(AB),(AB),(AB)也是命題公式；也是命題公式；有限次地利用上

24、述有限次地利用上述(1)-(4)而產(chǎn)生的符號(hào)串是命題公式。而產(chǎn)生的符號(hào)串是命題公式。例例1下列符號(hào)串是否為命題公式。下列符號(hào)串是否為命題公式。(1)P(QPR)；(2)(PQ)(QR)解解(1)不是命題公式。不是命題公式。(2)是命題公式。是命題公式。2021-10-2824注：從圖論的觀點(diǎn)看，每一命題公式都注：從圖論的觀點(diǎn)看，每一命題公式都可以用一棵二元樹(shù)來(lái)表示，其中樹(shù)的結(jié)可以用一棵二元樹(shù)來(lái)表示，其中樹(shù)的結(jié)點(diǎn)與聯(lián)結(jié)詞對(duì)應(yīng)，而樹(shù)葉則對(duì)應(yīng)于命題點(diǎn)與聯(lián)結(jié)詞對(duì)應(yīng)，而樹(shù)葉則對(duì)應(yīng)于命題變?cè)?。變?cè)?021-10-28259.2.2真值指派真值指派 命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一命題公式代表一

25、個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才成為命題，有確定的真值。成為命題，有確定的真值。如果張老師來(lái)了，那么這個(gè)問(wèn)題可以得到解決。如果張老師來(lái)了，那么這個(gè)問(wèn)題可以得到解決。如果學(xué)校放假，那么我就不去學(xué)校。如果學(xué)校放假，那么我就不去學(xué)校。例如：例如：PR2021-10-2826 公式與其命題變?cè)g的真值關(guān)系，可以用真值公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來(lái)。表的方法表示出來(lái)。如果我們不關(guān)心命題變?cè)兔}公式代表什么命題，如果我們不關(guān)心命題變?cè)兔}公式代表什么命題，只關(guān)心命題變?cè)恼嬷祵?duì)命題公式

26、的真值的影響，那么只關(guān)心命題變?cè)恼嬷祵?duì)命題公式的真值的影響，那么我們就可以對(duì)命題變?cè)谜嬷等ゴ?。我們就可以?duì)命題變?cè)谜嬷等ゴ搿６x定義9-7設(shè)設(shè)F為含有命題變?cè)獮楹忻}變?cè)狿1，P2，,Pn的命題公的命題公式，對(duì)式，對(duì)P1，P2，,Pn分別指定一個(gè)真值分別指定一個(gè)真值,稱為對(duì)公式稱為對(duì)公式F的的一組一組真值指派真值指派。F(P1,P2,P3)=(P1P2)P32021-10-2827例例2給出公式給出公式F=(PQ)(QR)(PR）的真值表）的真值表。 解解公式公式F的真值表如下：的真值表如下：PQRPQQR(PQ)(QR)PRF0 0 00 0 00 0 10 0 10 1 00

27、1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 10 00 01 11 11 11 11 11 10 00 00 01 10 00 00 01 11 11 10 01 10 00 00 01 10 00 00 00 01 10 01 10 00 00 01 10 01 11 11 10 02021-10-28289.2.3公式類(lèi)型公式類(lèi)型定義定義9-8如果對(duì)于命題公式如果對(duì)于命題公式F所包含的命題變?cè)娜魏我凰拿}變?cè)娜魏我唤M真值指派，組真值指派，F(xiàn)的真值恒為真，則稱公式的真值恒為真，則稱公式F為為重言式重言式（或（或永真公永真公

28、式式），常用），常用“1”表示表示。相反地，若對(duì)于。相反地，若對(duì)于F所包含的命題變?cè)乃拿}變?cè)娜魏我唤M真值指派，任何一組真值指派，F(xiàn)的真值恒為假，則稱公式的真值恒為假，則稱公式F為為矛盾式矛盾式（或（或永假公式永假公式），常用），常用“0”表示表示。如果至少有一組真值指派使公式。如果至少有一組真值指派使公式F的真值為真，則稱的真值為真，則稱F為為可滿足公式可滿足公式。例例3構(gòu)造下列命題公式的真值表，并判斷它們是何種類(lèi)型的公式構(gòu)造下列命題公式的真值表，并判斷它們是何種類(lèi)型的公式（1）（）（PQ）（PQ）；）；（2）（）（QP）（PQ）；）；（3）（）（PQ）（QR）（PR）。）。202

29、1-10-2829 解解令令F1=(PQ)(PQ)，F(xiàn)2=(QP)(PQ)F1和和F2的真值表如下：的真值表如下：PQPPQPQ(PQ)F1QPPQF20010101100011101101010010111001100101100由上可知：由上可知：F1是重言式是重言式,F2是矛盾式是矛盾式。 (3)的真值表沒(méi)有畫(huà)出，它是可滿足公式。的真值表沒(méi)有畫(huà)出，它是可滿足公式。2021-10-28309.3命題公式的等值關(guān)系和蘊(yùn)含關(guān)系命題公式的等值關(guān)系和蘊(yùn)含關(guān)系9.3.1命題公式的等值關(guān)系命題公式的等值關(guān)系定義定義9-9設(shè)設(shè)A和和B是兩個(gè)命題公式是兩個(gè)命題公式,P1,P2,Pn是所有出現(xiàn)是所有出現(xiàn)于于

30、A和和B中的命題變?cè)械拿}變?cè)?如果對(duì)于如果對(duì)于P1,P2,Pn的任的任一組真值指派一組真值指派,A和和B的真值都相同的真值都相同,則稱公式則稱公式A和和B等值等值,記為記為AB,稱稱AB為等值式為等值式。例如例如代數(shù)中令代數(shù)中令F1(x,y)=(x+y)2,F2(x,y)=x2+2xy+y2則則(x+y)2=x2+2xy+y2即即F1(x,y)=F2(x,y)類(lèi)似地，在命題邏輯中類(lèi)似地，在命題邏輯中例如例如令令F1(P1,P2)=P1P2F2(P1,P2)=P2P1則則P1P2P2P1即即F1(P1,P2)F2(P1,P2)2021-10-2831注注 意意：（1）符號(hào)）符號(hào)“”與與“”的

31、區(qū)別與聯(lián)系。的區(qū)別與聯(lián)系。“”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，AB不表示一個(gè)公式，它表示不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。兩個(gè)公式間的一種關(guān)系，即等值關(guān)系?！啊笔锹?lián)結(jié)詞，是聯(lián)結(jié)詞，AB是一個(gè)公式。是一個(gè)公式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永真公式。是永真公式。例如例如(PQ)(PQ)(PQ)(PQ)2021-10-2832（2）可以驗(yàn)證，可以驗(yàn)證，等值關(guān)系是等價(jià)關(guān)系等值關(guān)系是等價(jià)關(guān)系。即即自反性自反性：對(duì)任意公式：對(duì)任意公式A，有，有AA。對(duì)稱性對(duì)稱性：對(duì)任意公式：對(duì)任意公式A，B，若，若AB，則，則BA?？蓚鬟f性可傳遞性：對(duì)任意公式：對(duì)任意公式A、B、C，若，若AB，BC，則，則

32、AC。（3）當(dāng)）當(dāng)A是重言式時(shí)，是重言式時(shí)，A1；當(dāng)；當(dāng)A是矛盾式時(shí)，是矛盾式時(shí)，則則A0。2021-10-28339.3.2基本的等值式基本的等值式設(shè)設(shè)P、Q、R是命題變?cè)?，下表中列出了是命題變?cè)?，下表中列出?4個(gè)最基本的等值式個(gè)最基本的等值式:編號(hào)編號(hào) 公公式式E1E1 E2E2 E3E3 E4E4 E5E5 E6E6 E7E7 PQQP交換律交換律PQQP交換律交換律(PQ)RP(QR)結(jié)合律結(jié)合律(PQ)RP(QR)結(jié)合律結(jié)合律P(QR)(PQ)(PR)分配律分配律P(QR)(PQ)(PR)分配律分配律P0P同一律同一律P1P同一律同一律P P1互否律互否律P P0互否律互否律 （

33、P）P雙重否定律雙重否定律PPP等冪律等冪律PPP等冪律等冪律2021-10-2834編編號(hào)號(hào) 公公式式E8E8 E9E9 E10E10 E11E12E13E14E15P11零一律零一律P00零一律零一律P（PQ）P吸收律吸收律P（PQ）P吸收律吸收律 （PQ） P Q德德.摩根定律摩根定律 （PQ） P Q德德.摩根定律摩根定律PQ PQPQ(PQ)( P Q)P(QR)(PQ)RPQ(PQ)(QP)PQ Q P2021-10-28359.3.3等值式的判別等值式的判別有兩種方法：真值表方法，命題演算方法有兩種方法：真值表方法，命題演算方法1、真值表方法、真值表方法例例1用真值表方法證明用真

34、值表方法證明E10： (P Q)PQ 解解令：令：A= (P Q)，B= PQ，構(gòu)造，構(gòu)造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB。 0PQP Q (P Q) P Q PQAB00111110110100111100101101000012021-10-2836例例2用真值表方法證明用真值表方法證明E11：PQP Q解解令令A(yù)=PQ，B= P Q構(gòu)造構(gòu)造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB.1PQ P P QPQAB0011110111111000

35、01101112021-10-2837例例3用真值表方法判斷用真值表方法判斷PQPQ是否成立是否成立. 解解令令A(yù)=PQ，B= PQ構(gòu)造構(gòu)造A，B以及以及AB的真值表的真值表 由于公式由于公式AB所標(biāo)記的列不全為所標(biāo)記的列不全為1，AB不是不是永真公式，因此永真公式，因此AB不成立。不成立。P P Q P QPQAB011111010010011001100111Q01012021-10-2838PQ P Q QPPQAB0011111011011101001101100111所以所以PQ QP例例4用真值表方法判斷用真值表方法判斷PQ QP是否成立是否成立. 解解令令A(yù)=PQ，B= Q P構(gòu)

36、造構(gòu)造A，B以及以及AB的真值表的真值表2021-10-2839代換實(shí)例o 定義: 設(shè)A是一個(gè)命題公式,P1,P2,Pn是其中出現(xiàn)的所有命題變?cè)?n(1)用某些公式代換A中的某些命題變?cè)猲(2)若用命題公式Qi代換Pi,則必須同時(shí)用Qi代替公式A中的所有Pi. 這樣代換后得到的新公式B稱為公式A的一個(gè)代換實(shí)例2021-10-28402等值演算方法等值演算方法(1)代入規(guī)則代入規(guī)則代入規(guī)則代入規(guī)則對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。處均用同一命題公式代入，得到的仍是重言式。例如例如F=（PQ）（ QP）是重言式，若是重

37、言式，若用公式用公式AB代換命題變?cè)鷵Q命題變?cè)狿得公式得公式F1=（AB）Q）（ Q（AB），），F(xiàn)1仍是重言式。仍是重言式。2021-10-2841注意：因?yàn)樽⒁猓阂驗(yàn)锳B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是重言式。是重言式。所以，若對(duì)所以，若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式公式代入，則得到的仍是等值式。例如例如 (PQ) P Q，即即 (PQ) P Q是永真公式是永真公式于是，用于是，用PS對(duì)對(duì)P進(jìn)行代入進(jìn)行代入得得 (PS)Q) (PS) Q結(jié)論：結(jié)論：基本等值式中基本等值式中P,Q,R可以是任意的命題公式

38、?？梢允侨我獾拿}公式。2021-10-2842(2)置換規(guī)則置換規(guī)則定義定義9-10設(shè)設(shè)C是命題公式是命題公式A的一部分（即的一部分（即C是公式是公式A中中連續(xù)的幾個(gè)符號(hào)），且連續(xù)的幾個(gè)符號(hào)），且C本身也是一個(gè)命題公式，則稱本身也是一個(gè)命題公式，則稱C為公式為公式A的的子公式子公式。 例如例如設(shè)公式設(shè)公式A=（ PQ）（PQ）（R S）。）。 則則 PQ，PQ，（，（PQ）（R S）等均是等均是A的子公式，的子公式，但但 P，P和和Q等均不是等均不是A的子公式。的子公式。2021-10-2843置換規(guī)則置換規(guī)則設(shè)設(shè)C是公式是公式A的子公式，的子公式，CD。如果將。如果將公式公式A中的子公式中

39、的子公式C置換成公式置換成公式D之后，之后，得到的公式是得到的公式是B，則，則AB。 若若A=( PQ)(PQ)(R S)B=( PQ)( PQ)(R S)則則AB 例如例如2021-10-2844(3)等值演算等值演算等值演算是指利用已知的一些等值式，根據(jù)置換等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過(guò)程。一些等值式的過(guò)程。 由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)}變?cè)狿，Q，R是成立的，而且當(dāng)是成立的，而且當(dāng)P，Q，R分別為命分別為

40、命題公式時(shí)，這些等值式也成立題公式時(shí)，這些等值式也成立2021-10-2845例例2證明命題公式的等值關(guān)系：證明命題公式的等值關(guān)系：（PQ）（RQ）（PR）Q；證明證明（PQ）（RQ）（ PQ）( RQ)E11（ P R）QE3 (分配律分配律) (PR)QE10(德德.摩根定律摩根定律)(PR)QE11所以（所以（PQ）（RQ）（PR）Q2021-10-2846例例3證明下列命題公式的等值關(guān)系證明下列命題公式的等值關(guān)系(P Q) ( P ( P Q) P Q證明證明(P Q) ( P ( P Q)(P Q) ( P P) Q)E2(結(jié)合律結(jié)合律)(P Q) ( P Q)E7(等冪律等冪律)(

41、 P Q) (P Q)E1(交換律交換律) P (Q (P Q)E2(結(jié)合律結(jié)合律) P QE 1，E9(交換律，吸收律交換律，吸收律)2021-10-2847例例4判別下列公式的類(lèi)型。判別下列公式的類(lèi)型。（1）Q ( P( PQ)（2）(PQ) P解解(1)Q ( P( PQ)Q (P( PQ)E11,E6Q (P P)(PQ)E3 Q (1(PQ)E5Q (PQ)E4 Q P QE10(Q Q) PE1 ,E20E5 ,E8 所以所以Q ( P( PQ)是矛盾式。是矛盾式。2021-10-2848（2）(PQ) P( PQ) PE11 PE9 于是該公式是可滿足式。于是該公式是可滿足式。2

42、021-10-2849例例3證明下列命題公式的等值關(guān)系證明下列命題公式的等值關(guān)系PQ(PQ)(QP)E14PQPQQPPQ001111011000010010111111(PQ)(QP)根據(jù)代入規(guī)則，對(duì)任意命題公式根據(jù)代入規(guī)則，對(duì)任意命題公式A,BAB(AB)(BA)2021-10-2850 有了等值式，再由代入和替換定律可以得到許許多多的等值式。這些等值式還表明，同一個(gè)公式G可以有各種各樣的表達(dá)方式。 經(jīng)驗(yàn)表明，自覺(jué)地使用邏輯規(guī)律與不自覺(jué)地使用邏輯規(guī)律是完全不一樣的。2021-10-2851例例試用較少的開(kāi)關(guān)設(shè)計(jì)一個(gè)與如圖有相同功能的電路。試用較少的開(kāi)關(guān)設(shè)計(jì)一個(gè)與如圖有相同功能的電路。 PQ

43、RSPS 解：將所示之開(kāi)關(guān)電路用下述命令表示：解：將所示之開(kāi)關(guān)電路用下述命令表示：（P Q S） （P S R）=（P S） （Q R） QRPS2021-10-2852例例將下面一段程序語(yǔ)言進(jìn)行化簡(jiǎn)將下面一段程序語(yǔ)言進(jìn)行化簡(jiǎn):IfAthenifBthenXelseYelseifBthenXelseY解解將程序用流程圖表示：將程序用流程圖表示：TSTARTABBTFXYTFF從框圖可知：執(zhí)行從框圖可知：執(zhí)行X的條件為：的條件為：(AB) ( A B)=B (AA)=B執(zhí)行執(zhí)行Y的條件為：的條件為：( A B) (AB)= B因此這段程序可以簡(jiǎn)化為：因此這段程序可以簡(jiǎn)化為：IfBthenXels

44、eY2021-10-28539.3.4命題公式的蘊(yùn)含關(guān)系命題公式的蘊(yùn)含關(guān)系定義定義9-11設(shè)設(shè)A，B是兩個(gè)公式，若公式是兩個(gè)公式，若公式AB是重言式，即是重言式，即AB1，則稱，則稱公式公式A蘊(yùn)含公式蘊(yùn)含公式B，記作，記作AB。稱稱“AB”為為蘊(yùn)含式蘊(yùn)含式。注意：符號(hào)注意：符號(hào)“”和和“”的區(qū)別和聯(lián)系與符號(hào)的區(qū)別和聯(lián)系與符號(hào)“”與與“”的區(qū)別和聯(lián)系類(lèi)似。的區(qū)別和聯(lián)系類(lèi)似。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，“AB”不是公式，它表示公式不是公式，它表示公式A與與B之間存在蘊(yùn)含關(guān)系。之間存在蘊(yùn)含關(guān)系。 “”是聯(lián)系詞，是聯(lián)系詞，AB是一個(gè)公式。是一個(gè)公式。AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永真公式是永真公式。20

45、21-10-2854ABAB001011100111AB意味著意味著AB是永真公式，是永真公式，意味著對(duì)于命題變?cè)馕吨鴮?duì)于命題變?cè)狿1,P1,Pn的任意一組真值指派，的任意一組真值指派，A為真而為真而B(niǎo)為假的情形不可能發(fā)生，為假的情形不可能發(fā)生，即意味著當(dāng)即意味著當(dāng)A為真時(shí)，為真時(shí)，B也一定為真。也一定為真。2021-10-2855AB是偏序關(guān)系是偏序關(guān)系即即自反性自反性：AA。反對(duì)稱反對(duì)稱：若：若AB，BA，則，則AB。傳遞性傳遞性：若：若AB，BC，則，則AC。 反對(duì)稱性的證明：反對(duì)稱性的證明：設(shè)設(shè)AB且且BA，由定義由定義9-11AB1且且BA1于是于是AB(AB) (BA)E141

46、11因此因此AB2021-10-2856傳遞性的證明：傳遞性的證明：設(shè)設(shè)AB，BC，則則AB1，BC1( A B C) ( AB C)(AB) C) ( A (BC)(1 C) ( A 1)1 11 因此因此AC.于是于是ACA C ( A C) (BB)2021-10-28579.3.5基本的蘊(yùn)含式基本的蘊(yùn)含式編號(hào)編號(hào)蘊(yùn)蘊(yùn)含含式式I1P QPI2P QQI3PP QI4QP QI5 PPQI6QPQI7 (PQ)PI8 (PQ) Q設(shè)設(shè)P、Q、R是命題變?cè)?，下表中列出了是命題變?cè)?，下表中列出?6個(gè)最基本的蘊(yùn)含式。個(gè)最基本的蘊(yùn)含式。2021-10-2858編號(hào)編號(hào)蘊(yùn)蘊(yùn)含含式式I9P QP Q

47、或表示為：或表示為：P、QP QI10 P (P Q)Q P、(P Q)QI11P (PQ)QP、PQQI12 Q (PQ)P Q、PQPI13(PQ) (QR)PRPQ、QRPRI14(P Q) (PR) (QR)RP Q、PR、QRRI15PQ(P R)(Q R)I16PQ(P R)(Q R)2021-10-28599.3.6蘊(yùn)含式的判別蘊(yùn)含式的判別判定判定“AB”是否成立的問(wèn)題可轉(zhuǎn)化為判定是否成立的問(wèn)題可轉(zhuǎn)化為判定AB是否為重言式是否為重言式，有下述判定方法：，有下述判定方法：（1）真值表；）真值表；（2）等值演算；）等值演算；（3）假定前件）假定前件A為真，判斷后件為真，判斷后件B是否

48、為真；是否為真；（4）假定后件）假定后件B為假，判斷前件為假，判斷前件A是否為假。是否為假。2021-10-28601.真值表方法真值表方法例例4證明證明I14：(PQ)(PR)(QR) R證明證明令公式令公式F=(PQ)(PR)(QR)R，其真值表如下：其真值表如下：2021-10-2861PQRPQPRQR(PQ)(PR)(QR)F0000010100111001011101110011111111110101110111010001010111111111 公式公式F對(duì)任意的一組真值指派取值均為對(duì)任意的一組真值指派取值均為1，故，故F是重言式。是重言式。(PQ)(PR）（QR）R2021

49、-10-28622.等值演算方法等值演算方法例例5證明證明I11：P（PQ） Q證明證明（P（PQ）Q(變成證明它為永真變成證明它為永真) （P（ PQ）QE11 （ P （ PQ）QE10 （ PQ） （ PQ）E2 1代入規(guī)則代入規(guī)則,E5因此因此P（PQ） Q2021-10-28633.假定前件假定前件A真真假定前件假定前件A為真，檢查在此情況下，其后件為真，檢查在此情況下，其后件B是否也為真。是否也為真。ABAB001011100111證明令前件證明令前件 Q（PQ）為真，）為真，則則 Q為真為真,且且PQ為真。為真。于是于是Q為假，因而為假，因而P也為假。由此也為假。由此 P為真。為

50、真。故蘊(yùn)含式故蘊(yùn)含式I12成立。成立。例例6證明證明I12: Q（PQ） P即要證明即要證明 Q（PQ） P為永真為永真2021-10-28644、假定后件假定后件B假假假定后件假定后件B為假，檢查在此情況下，其前件為假，檢查在此情況下，其前件A是否也為假。是否也為假。例例7證明蘊(yùn)含式證明蘊(yùn)含式(PQ) (RS)(P R)(Q S)證明證明令后件令后件(P R)(Q S)為假，則為假，則P R為真，為真，Q S為假為假,于是于是P、R均為真，而均為真，而Q和和S至少一個(gè)為假。至少一個(gè)為假。由此可知由此可知PQ與與RS中至少一個(gè)為假中至少一個(gè)為假,因此因此(PQ) (RS)為假為假.故上述蘊(yùn)含式

51、成立。故上述蘊(yùn)含式成立。2021-10-28651判斷下列等值式是否成立判斷下列等值式是否成立（1）（）（PQ）（RQ）（PR）Q解（解（1）（）（PQ）（RQ）（ PQ）（ RQ）E11（ P R）QE3 （PR）QE10（PR）QE11練練 習(xí)習(xí)2021-10-2866（2）（）（P Q）（ PQ） （ PQ）（ QP）E6，E10 （PQ）（QP）E11 （PQ）E14 （ （P Q） （ PQ）（2） （PQ）（P Q）（ PQ）2021-10-28672判定蘊(yùn)含式判定蘊(yùn)含式是否成立是否成立解假定后件（解假定后件（PQ）（PR）為假，）為假，則則PQ為真，為真，PR為假。為假。由由PR

52、為假為假,得得P為真，為真，R為假。為假。又又PQ為真，故得為真，故得Q為真。為真。于是于是P為真，為真，QR為假。為假。從而從而P（QR）為假。）為假。因此蘊(yùn)含式成立。因此蘊(yùn)含式成立。)()()(RPQPRQP2021-10-28682判定判定是否成立是否成立)()()(RPQPRQP解法二解法二右式右式（ PQ）（ PR） （ PQ）（ PR）（P Q）（ PR）（P PR）（ Q PR）1（ P QR） P（ QR） P（QR）P（QR）所以所以成立成立)()()(RPQPRQP2021-10-28699.5命題演算的推理理論命題演算的推理理論9.5.1推理推理推理是由已知的命題得到新命

53、題的思維過(guò)程。推理是由已知的命題得到新命題的思維過(guò)程。 定義定義9-19設(shè)設(shè)A和和B是兩個(gè)命題公式，如果是兩個(gè)命題公式，如果AB，即如，即如果命題公式果命題公式AB為重言式，則稱為重言式，則稱B是前提是前提A的結(jié)論的結(jié)論或或從從A推出推出結(jié)論結(jié)論B。 一般地設(shè)一般地設(shè)H1，H2，,Hn和和C是一些命題公式是一些命題公式,若蘊(yùn)含若蘊(yùn)含式式H1H2HnC (*)成立，則稱成立，則稱C是前提集合是前提集合H1，H2，,Hn的結(jié)論的結(jié)論，或稱從前提，或稱從前提H1，H2，,Hn能推出結(jié)能推出結(jié)論論C。有時(shí)也記作。有時(shí)也記作H1，H2，,HnC2021-10-28709.5.2如何判斷由一個(gè)前提集合能否

54、推出如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論某個(gè)結(jié)論 1、真值表法、真值表法對(duì)于命題公式對(duì)于命題公式中所有命題中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為永真永真。CHHHn)(212021-10-2871例例1考察結(jié)論考察結(jié)論C是否是下列前提是否是下列前提H1，H2的結(jié)論。的結(jié)論。（1）H1：PQ，H2：P，C：QPQ00011011解解 構(gòu)造其真值表如下：構(gòu)造其真值表如下：PQPQ（PQ）P(PQ)P)Q111011010101001001112021-10-2872（2）H1：PQ，H2：P，C：Q解解 構(gòu)造其真值表如下：構(gòu)造其

55、真值表如下：PQPQ(PQ)P1111101101000010(PQ)P)Q1011PQ00011011 在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定的前提是否能推出這個(gè)結(jié)論來(lái)。的前提是否能推出這個(gè)結(jié)論來(lái)。2021-10-28732、等值演算方法、等值演算方法例例證明證明PRRQQP、分析：根據(jù)題意，需證明分析：根據(jù)題意，需證明PRRQQP)()(.)()(是永真公式是永真公式即需證明即需證明PRRQQPPRRRQQP)()( ()( ( PRQQP) )()( ( PRQQRQP) )()( ( PRQP)( PRQP)(1PRQP)(

56、)(PRRQQP證明證明PRRQQP) )( ()( (2021-10-28743、“形式證明形式證明”方法方法（1）基本述語(yǔ)）基本述語(yǔ)形式證明形式證明：一個(gè)描述推理過(guò)程的命題序列，其中每個(gè)：一個(gè)描述推理過(guò)程的命題序列，其中每個(gè)命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，序列中最后一個(gè)命題就是所要求的結(jié)論，這樣的命題序列稱序列中最后一個(gè)命題就是所要求的結(jié)論，這樣的命題序列稱為形式證明。為形式證明。有效的證明有效的證明：如果證明過(guò)程中的每一步所得到的結(jié)論：如果證明過(guò)程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的

57、。都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。有效的結(jié)論有效的結(jié)論：通過(guò)有效的證明而得到結(jié)論，稱作是有：通過(guò)有效的證明而得到結(jié)論，稱作是有效的結(jié)論。效的結(jié)論。2021-10-2875為了證明為了證明C是前提是前提H1，H2，,Hn的結(jié)論的結(jié)論,即需證明即需證明:當(dāng)前提當(dāng)前提H1，H2，,Hn均為真時(shí)，均為真時(shí)，C必為真。必為真。H1，Q1，H2，Q2，Hi，Q3，C例如例如通過(guò)構(gòu)造一個(gè)命題序列，來(lái)描述這一推理過(guò)程。通過(guò)構(gòu)造一個(gè)命題序列，來(lái)描述這一推理過(guò)程。2021-10-2876(2)推理規(guī)則推理規(guī)則前提引用規(guī)則前提引用規(guī)則：在證明的任何步驟上都可以引用前提。在證明的任何步驟上都可以引用

58、前提。結(jié)論引用規(guī)則結(jié)論引用規(guī)則：在證明的任何步驟上所得到的結(jié)論都可在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。以在其后的證明中引用。置換規(guī)則置換規(guī)則：在證明的任何步驟上，命題公式的子公式都在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換?？梢杂门c它等值的其它命題公式置換。代入規(guī)則代入規(guī)則：在證明的任何步驟上，重言式中的任一命題在證明的任何步驟上，重言式中的任一命題變?cè)伎梢杂靡幻}公式代入，得到的仍是重言式。變?cè)伎梢杂靡幻}公式代入，得到的仍是重言式。2021-10-2877常用的一些蘊(yùn)涵關(guān)系常用的一些蘊(yùn)涵關(guān)系I9P、QP QI10 P、P QQI11P、P

59、QQI12 Q、PQ PE2E2 (PQ)RP(QR),(PQ)RP(QR)I13PQ、QRPRE1E1 PQQP,PQQPE6E6 （ P）PPQ Q PE152021-10-2878例例2證明證明R(PQ)是前提是前提PQ,QR,PS,S的結(jié)論。的結(jié)論。 所以所以PQ，QR，PS，SR（PQ)編號(hào)編號(hào)公公式式依依據(jù)據(jù)（1）（2）（3）（4）（5）（6）（7）（8）PSSPPQQQRRR（PQ）前提（前提引入規(guī)則）前提（前提引入規(guī)則）前提（前提引入規(guī)則）前提（前提引入規(guī)則）（1），（），（2）；）；I12前提前提（3），（），（4）；）；I10前提前提（5），（），（6）；）；I11（4），

60、（），（7）；）；I92021-10-2879例例3證明證明RS是前提是前提P（QS），），RP和和Q的有效結(jié)論。的有效結(jié)論。證明證明 編號(hào)編號(hào)公公式式依依據(jù)據(jù)(1)(2)(3)(4)(5)(6)(7)(8)(9)RPRPP（QS）R（QS）R（QS）Q（RS）QRSRS前提前提（1）；）；E11前提前提（2），（），（3）；）；I13（4）；）；E11（5）；）；E1，E2前提前提（6），（），（7）；）；I10（8）；）；E112021-10-2880蘊(yùn)含證明規(guī)則：蘊(yùn)含證明規(guī)則：證明證明P（QR） P（ QR） （PQ）R（PQ）R（ P Q）R,)()(RQPRQPE132021-10-