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

1、廣東工業(yè)大學(xué)計算機(jī)學(xué)院廣東工業(yè)大學(xué)計算機(jī)學(xué)院離散數(shù)學(xué)離散數(shù)學(xué)離離 散散 數(shù)數(shù) 學(xué)學(xué)離離 散散 數(shù)數(shù) 學(xué)學(xué)蔡瑞初蔡瑞初2第二篇第二篇 數(shù)理邏輯數(shù)理邏輯先看著名物理學(xué)家愛因斯坦出過的一道題：先看著名物理學(xué)家愛因斯坦出過的一道題：一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應(yīng)聘，這個商人為了試試哪個更聰明些，就把兩個人帶進(jìn)一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出自己頭上戴的帽子是什么顏色的?！闭f完后，商人將電燈關(guān)掉，然后三人都摸了一頂

2、帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應(yīng)試者看到商人頭上戴的是一頂紅帽子，其中一個人便喊道：“我戴的是黑帽子?！闭垎栠@個人說得對嗎？他是怎么推導(dǎo)出來的呢？3第二篇第二篇 數(shù)理邏輯數(shù)理邏輯要回答這樣的問題，實際上就是看由一些諸如要回答這樣的問題，實際上就是看由一些諸如“商商人戴的是紅帽子人戴的是紅帽子”這樣的前提能否推出這樣的前提能否推出“猜出答案猜出答案的應(yīng)試者戴的是黑帽子的應(yīng)試者戴的是黑帽子”這樣的結(jié)論來。這又需要這樣的結(jié)論來。這又需要經(jīng)歷如下過程：經(jīng)歷如下過程：(1) (1) 什么是前提？有哪些前提？什么是前提？有哪些前提？(2) (2) 結(jié)論是什么？結(jié)

3、論是什么？(3) (3) 根據(jù)什么進(jìn)行推理？根據(jù)什么進(jìn)行推理？(4) (4) 怎么進(jìn)行推理？怎么進(jìn)行推理？42022-3-112022-3-11數(shù)理邏輯（數(shù)理邏輯（Mathematical LogicMathematical Logic） 是研究演繹推理的一門學(xué)科，用是研究演繹推理的一門學(xué)科，用數(shù)學(xué)的數(shù)學(xué)的方法方法來研究來研究推理的規(guī)律推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。統(tǒng)稱為數(shù)理邏輯。第二篇第二篇 數(shù)理邏輯數(shù)理邏輯52022-3-112022-3-11主要研究內(nèi)容：主要研究內(nèi)容：推理推理 著重于著重于推理過程是否正確推理過程是否正確 著重于著重于語句之間的關(guān)系語句之間的關(guān)系主要研究方法：主要研究方法：

4、數(shù)學(xué)的方法數(shù)學(xué)的方法 就是引進(jìn)一套符號體系的方法，所以數(shù)就是引進(jìn)一套符號體系的方法，所以數(shù)理邏輯又叫符號邏輯（理邏輯又叫符號邏輯（Symbolic LogicSymbolic Logic）。）。 第二篇第二篇 數(shù)理邏輯數(shù)理邏輯62022-3-112022-3-11什么是數(shù)理邏輯什么是數(shù)理邏輯 ？用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。為什么要研究數(shù)理邏輯？為什么要研究數(shù)理邏輯？程序算法數(shù)據(jù)程序算法數(shù)據(jù)算法邏輯控制算法邏輯控制總結(jié)總結(jié)72022-3-112022-3-11第二篇第二篇 數(shù)理邏輯數(shù)理邏輯命題邏輯命題邏輯 命題的基本概念命題的基本概念命

5、題聯(lián)結(jié)詞命題聯(lián)結(jié)詞命題公式命題公式命題的范式命題的范式 主要研主要研 究內(nèi)容究內(nèi)容謂詞邏輯謂詞邏輯謂詞的基本概念謂詞的基本概念謂詞公式謂詞公式公式的標(biāo)準(zhǔn)型公式的標(biāo)準(zhǔn)型推理與證明技術(shù)推理與證明技術(shù)命題邏輯推理理論命題邏輯推理理論謂詞邏輯推理理論謂詞邏輯推理理論數(shù)學(xué)歸納法數(shù)學(xué)歸納法按定義證明法按定義證明法82022-3-112022-3-11第三章第三章 命題邏輯命題邏輯 命題邏輯也稱命題演算，或語句邏輯。命題邏輯也稱命題演算，或語句邏輯。 研究內(nèi)容：研究內(nèi)容： （1 1）研究以）研究以命題為基本單位命題為基本單位構(gòu)成的構(gòu)成的前提和結(jié)論前提和結(jié)論之間的可推導(dǎo)關(guān)系之間的可推導(dǎo)關(guān)系 （2 2）研究）研

6、究什么是命題什么是命題？ （3 3）研究）研究如何表示命題如何表示命題？ （4 4）研究）研究如何由一組前提推導(dǎo)一些結(jié)論如何由一組前提推導(dǎo)一些結(jié)論？92022-3-112022-3-11第三章第三章 命題邏輯命題邏輯 命題邏輯的命題邏輯的特征：特征： 在研究邏輯的形式時，我們在研究邏輯的形式時，我們把一個命題只把一個命題只分析到其中所含的命題成份為止，不再分析下分析到其中所含的命題成份為止，不再分析下去去。不把一個簡單命題再分析為非命題的集合，。不把一個簡單命題再分析為非命題的集合，不把不把謂詞謂詞和和量詞量詞等非命題成份分析出來。等非命題成份分析出來。 102022-3-112022-3-1

7、1第三章第三章 命題邏輯命題邏輯集合的表示方法集合的表示方法2命題公式命題公式3命題范式命題范式4命題基本概念命題基本概念1命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞2112022-3-112022-3-113.1 3.1 本章學(xué)習(xí)要求本章學(xué)習(xí)要求重點掌握重點掌握一般掌握一般掌握了解了解11 1、五種基本、五種基本聯(lián)結(jié)詞聯(lián)結(jié)詞2 2、2424個個基本基本的等價公式的等價公式3 3 掌握求命題掌握求命題范式的方法范式的方法3聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集的理解和學(xué)習(xí)的理解和學(xué)習(xí)2公式的代入規(guī)公式的代入規(guī)則和替換規(guī)則則和替換規(guī)則122022-3-112022-3-113.2.1 3.2.1 命題命題定義定義3.2.13.2.

8、1具有具有確切真值確切真值的陳述句稱為的陳述句稱為命題命題, , 該命題可以取一個該命題可以取一個“值值”，稱為，稱為真值真值。真值只有真值只有“真真”和和“假假”兩種，兩種，分別用分別用“”( (或或“”) )和和“”( (或或“”) )表示。表示。3.2 3.2 命題與命題聯(lián)結(jié)詞命題與命題聯(lián)結(jié)詞132022-3-112022-3-11（1 1）太陽是圓的；）太陽是圓的； （2 2）成都是一個旅游城市；）成都是一個旅游城市；（3 3）北京是中國的首都；）北京是中國的首都；（4 4）這個語句是假的；）這個語句是假的；（5 5）1 11 11010；（6 6）+y+y；（7 7）我喜歡踢足球；）

9、我喜歡踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中國是世界上人口最多的國家；）中國是世界上人口最多的國家；（1111）今天是晴天；）今天是晴天；例例3.2.13.2.1TTT/F非命題非命題T/FFT/FTTT非命題非命題142022-3-112022-3-11例例3.2.13.2.1（續(xù)）（續(xù)）（1212）把門關(guān)上；）把門關(guān)上；（1313）滾出去?。L出去?。?414）你要出去嗎？）你要出去嗎？（1515）今天天氣真好?。。┙裉焯鞖庹婧冒?！非命題非命題非命題非命題非命題非命題非命題非命題注意：注意：一切沒有判斷內(nèi)容的

10、句子都不能作為命題一切沒有判斷內(nèi)容的句子都不能作為命題，如命令，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。句、感嘆句、疑問句、祈使句、二義性的陳述句等。 152022-3-112022-3-11命題一定是陳述句，但并非一切陳述句都是命題。命題一定是陳述句，但并非一切陳述句都是命題。命題的真值有時可明確給出，有時還需要依靠命題的真值有時可明確給出，有時還需要依靠環(huán)境、環(huán)境、條件、實際情況時間條件、實際情況時間才能確定其真值。才能確定其真值。結(jié)論：結(jié)論：在數(shù)理邏輯中像在數(shù)理邏輯中像字母字母“x x”、“y y”、“z z”等字母總等字母總是表示是表示變量。變量。約定：約定：162022-

11、3-112022-3-11下列語句是否是命題？下列語句是否是命題？并判斷其真值結(jié)果？并判斷其真值結(jié)果？（1 1）四川）四川不不是一個國家；是一個國家；（2 2）3 3既既是素數(shù)是素數(shù)又又是奇數(shù)；是奇數(shù)；（3 3）張謙是大學(xué)生）張謙是大學(xué)生或是或是運動員；運動員；（4 4）如果如果周末天氣晴朗，周末天氣晴朗，則則我們將到郊外旅游；我們將到郊外旅游；（5 5）2+2=42+2=4當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)雪是白的。雪是白的。例例3.2.23.2.2172022-3-112022-3-11一般來說，命題可分兩種類型：一般來說，命題可分兩種類型：原子命題原子命題( (簡單命題簡單命題) )：不能再：不能再分解分

12、解為更為簡單命題為更為簡單命題的命題。的命題。復(fù)合命題復(fù)合命題：可以：可以分解分解為更為簡單命題的命題。而且為更為簡單命題的命題。而且這些簡單命題之間是通過如這些簡單命題之間是通過如“或者或者”、“并并且且”、“不不”、“如果如果.則則.”、“當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點符號復(fù)合而構(gòu)成一等這樣的關(guān)聯(lián)詞和標(biāo)點符號復(fù)合而構(gòu)成一個復(fù)合命題。個復(fù)合命題。命題的分類命題的分類182022-3-112022-3-11今天天氣很冷。今天天氣很冷。今天天氣很冷并且刮風(fēng)。今天天氣很冷并且刮風(fēng)。今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。例例3.2.33.2.3 通常用通常用大寫

13、的帶或不帶下標(biāo)的英文字母大寫的帶或不帶下標(biāo)的英文字母、.P.P、Q Q、R R、. . A Ai i、B Bi i 、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命題等表示命題192022-3-112022-3-113.2.2 3.2.2 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞設(shè)命題設(shè)命題P,QP,Q表示任意兩個命題表示任意兩個命題, ,則則最常見的命題聯(lián)結(jié)詞有：最常見的命題聯(lián)結(jié)詞有：聯(lián)接詞聯(lián)接詞記號記號 復(fù)合命題復(fù)合命題讀法讀法 記法記法真值結(jié)果真值結(jié)果 3.3.析取析取 P P或者或者Q QP P與與Q Q的析取的析取P P Q QP PQ=1Q=1P=1P=1或或Q=1Q=12.2.

14、合取合取 P P并且并且Q QP P與與Q Q的合取的合取PQPQPQPQ=1=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定P PP=1P=1 P=0P=04.4.蘊涵蘊涵若若P,P,則則Q QP P蘊涵蘊涵Q QP PQQP PQ=0Q=0 P=1,Q=0P=1,Q=05.5.等價等價 P P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q QP P等價于等價于Q QP PQ QP PQ=1Q=1P P=1=1, ,Q=1Q=1或或P P=0=0, ,Q=0Q=0例如：命題例如：命題P P：2 2是素數(shù)；是素數(shù)；Q Q：北京是中國的首都：北京是中國的首都202022-3-112022-3-

15、11總結(jié)總結(jié)P QP QP PPQPQPQPQPQPQP PQ Q0 00 01 10 00 01 11 10 10 11 10 01 11 10 01 01 00 00 01 10 00 01 11 10 01 11 11 11 1212022-3-112022-3-11說明說明1 1、聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結(jié)；名詞、形容詞、數(shù)詞等地聯(lián)結(jié)；2 2、聯(lián)結(jié)詞是兩個句子真值之間的聯(lián)結(jié)，而非句子聯(lián)結(jié)詞是兩個句子真值之間的聯(lián)結(jié)，而非句子的具體含義的聯(lián)結(jié)，兩個句子之間可以無任何的具體含義的聯(lián)結(jié)，兩個句子之間可以無任何地內(nèi)在

16、聯(lián)系；地內(nèi)在聯(lián)系；222022-3-112022-3-11說明說明3 3、聯(lián)結(jié)詞與自然語言之間的對應(yīng)聯(lián)結(jié)詞與自然語言之間的對應(yīng)并非一一對應(yīng)并非一一對應(yīng)；聯(lián)結(jié)詞聯(lián)結(jié)詞自然語言自然語言既既又又、不僅、不僅而且而且、雖然、雖然但但是是、并且、和、與，等等；、并且、和、與，等等；如如P P則則Q Q、只要、只要P P就就Q Q、P P僅當(dāng)僅當(dāng)Q Q、只有、只有Q Q才才P P、除非除非Q Q否則否則 P P，等等，等等等價、當(dāng)且僅當(dāng)、充分必要、等等；等價、當(dāng)且僅當(dāng)、充分必要、等等； 相容（可兼）的或相容（可兼）的或232022-3-112022-3-11符號化下列命題符號化下列命題（1 1）四川）四川

17、不不是人口最多的省份；是人口最多的省份；（2 2）王超是一個）王超是一個德智體德智體全面發(fā)展的好學(xué)生；全面發(fā)展的好學(xué)生；（3 3）教室的燈不亮可能是燈管壞了）教室的燈不亮可能是燈管壞了或者或者是停電了；是停電了；（4 4）如果如果周末天氣晴朗，周末天氣晴朗，那么那么學(xué)院將組織我們到學(xué)院將組織我們到石像湖春游；石像湖春游；（5 5）兩個三角形全等）兩個三角形全等當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)三角形的三條邊全三角形的三條邊全部相等。部相等。例例3.23.2. .4 4242022-3-112022-3-11例例3.23.2. .4 4 解解（1 1）設(shè)：四川是人口最多的省份。）設(shè)：四川是人口最多的省份。 則命題

18、（則命題（1 1）可表示為）可表示為。（2 2）設(shè)：王超是一個思想品德好的學(xué)生；）設(shè)：王超是一個思想品德好的學(xué)生； ：王超是一個學(xué)習(xí)成績好的學(xué)生；：王超是一個學(xué)習(xí)成績好的學(xué)生； R R：王超是一個體育成績好的學(xué)生。：王超是一個體育成績好的學(xué)生。 則命題（則命題（2 2）可表示為）可表示為R R。（3 3）設(shè)：教室的燈不亮可能是燈管壞了）設(shè)：教室的燈不亮可能是燈管壞了 ：教室的燈不亮可能是停電了：教室的燈不亮可能是停電了 則命題（則命題（3 3）可表示為）可表示為。252022-3-112022-3-11（4 4）設(shè)：周末天氣晴朗；）設(shè)：周末天氣晴朗； ：學(xué)院將組織我們到石像湖春游。：學(xué)院將組織

19、我們到石像湖春游。 則命題（則命題（4 4）可表示為）可表示為。（5 5）設(shè)：兩個三角形全等；）設(shè)：兩個三角形全等； ：三角形的三條邊全部相等。：三角形的三條邊全部相等。 則命題（則命題（5 5）可表示為）可表示為。例例3.23.2. .4 4 解解( (續(xù)續(xù)) )262022-3-112022-3-11 為了不使句子產(chǎn)生混淆，作如下約定為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)命題聯(lián)結(jié)詞之優(yōu)先級詞之優(yōu)先級如下：如下：1.1. 否定否定合取合取析取析取蘊涵蘊涵等價等價2.2. 同級的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序同級的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序( (從左從左到右到右) )3.3. 若運算要求與優(yōu)先

20、次序不一致時，可使用若運算要求與優(yōu)先次序不一致時，可使用括號括號；同級符號相鄰時，也可使用括號。；同級符號相鄰時，也可使用括號。括號中的運算為最優(yōu)先級括號中的運算為最優(yōu)先級。約約 定定272022-3-112022-3-11設(shè)命題設(shè)命題P P：明天上午七點下雨；：明天上午七點下雨； Q Q：明天上午七點下雪；：明天上午七點下雪； R R：我將去學(xué)校。：我將去學(xué)校。符號化下述語句：符號化下述語句：如果如果明天上午七點明天上午七點不不是雨是雨夾夾雪，雪，則則我將去學(xué)校我將去學(xué)校如果如果明天上午七點明天上午七點不不下雨下雨并且并且不不下雪，下雪，則則我將去學(xué)我將去學(xué)校校如果如果明天上午七點下雨明天上

21、午七點下雨或或下雪，下雪，則則我將我將不不去學(xué)校去學(xué)校明天上午我將明天上午我將雨雪無阻雨雪無阻一定去學(xué)校一定去學(xué)?？煞柣癁椋嚎煞柣癁椋?PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。 或或 (PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)R(PQ)R。例例3.23.2. .5 5可符號化為：可符號化為：(PQ)R(PQ)R。可符號化為可符號化為:(:(PQ)RPQ)R?？煞柣癁榭煞柣癁?(PQ)R:(PQ)R。282022-3-112022-3-11例例3.23.2. .6 6設(shè)命題設(shè)命題P P：你陪伴我；：你陪伴我； Q Q：你代我叫車子；

22、：你代我叫車子； R R：我將出去。：我將出去。 符號化下述語句：符號化下述語句： 除非除非你陪伴我或代我叫車子，你陪伴我或代我叫車子，否則否則我將我將不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫輛車子，代我叫輛車子，則則我將出去我將出去 如果如果你你不不陪伴我陪伴我或或不不代我叫輛車子，我將代我叫輛車子，我將不不出去出去R(PQ) R(PQ) 或或 (PQ)RPQ)R( (PQ)RPQ)R(PQ)RPQ)R292022-3-112022-3-11例例設(shè)設(shè)P:P:雪是白色的雪是白色的;Q:2+2=4;Q:2+2=4。將下列命題符號化：。將下列命題符號化：（1 1）因為雪是白色的，所以）

23、因為雪是白色的，所以2+2=42+2=4； PQ PQ （2 2）如果）如果2+2=42+2=4，則雪是白色的；，則雪是白色的； QPQP（3 3）只有雪是白色的，才有）只有雪是白色的，才有2+2=42+2=4； QPQP（4 4）只有）只有2+2=42+2=4，雪才是白色的；，雪才是白色的； PQPQ（5 5）只要雪不是白色的，就有）只要雪不是白色的，就有2+2=42+2=4； PQPQ（6 6）除非雪是白色的，否則）除非雪是白色的，否則2+242+24； PP Q Q或或QPQP（7 7）雪是白色的當(dāng)且僅當(dāng)）雪是白色的當(dāng)且僅當(dāng)2+2=42+2=4； P P Q Q302022-3-1120

24、22-3-11用復(fù)合命題表示如下圖所示的邏輯電路用復(fù)合命題表示如下圖所示的邏輯電路：例例 3.2.8 3.2.8圖圖3.2.43.2.4 圖圖3.2.53.2.5 圖圖3.2.63.2.6QPP P Q QQPP PQ QPP P解解: :設(shè)設(shè)P P：輸入端為高電位：輸入端為高電位,Q,Q：輸入端為高電位：輸入端為高電位, ,則則 “與門與門”對應(yīng)于對應(yīng)于PQPQ； “或門或門”對應(yīng)于對應(yīng)于PQPQ； “非門非門”對應(yīng)于對應(yīng)于P P。312022-3-112022-3-113.3 3.3 命題公式、解釋與真值表命題公式、解釋與真值表定義定義3.3.13.3.1 一個特定的命題是一個一個特定的命

25、題是一個常值命題常值命題，它不是它不是具有值具有值“T T”( (“1 1”) )，就是具有值，就是具有值“F F”( (“0 0”) )。而一個任意的沒有賦予具體內(nèi)容的原子命題是一個變而一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題，常稱它為量命題，常稱它為命題變量命題變量( (或或命題變元命題變元) )，該命題變該命題變量無具體的真值，它的變域是集合量無具體的真值，它的變域是集合 T T，F(xiàn) F ( (或或00，11) )注意注意(1)(1)復(fù)合命題為命題變元的復(fù)合命題為命題變元的“函數(shù)函數(shù)”, ,其其函數(shù)值仍為函數(shù)值仍為 真真 或或“假假”值值。(2)(2)真值函數(shù)或命題公式真值函數(shù)

26、或命題公式，沒有確沒有確切切真值真值。真值函數(shù)真值函數(shù)322022-3-112022-3-113.3.13.3.1命題公式命題公式定義定義3.3.2 (3.3.2 (命題公式命題公式) )命題變元本身是一個公式；命題變元本身是一個公式；如如G G是公式，則是公式，則(G)(G)也是公式；也是公式；如如G G，H H是公式，則是公式，則(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH H) )也是公式；也是公式；僅由有限步使用規(guī)則僅由有限步使用規(guī)則1-31-3后產(chǎn)生的結(jié)果。該公式常后產(chǎn)生的結(jié)果。該公式常用符號用符號G G、H H、等表示。等表示。332022-3-112022-3

27、-11符號串：符號串： (QR(QR) ), ,( (P(QRP(QR) SS, , ( (SRSR) ), , ( (QQ( (SRSR) (P(QRP(QR)( (QQ( (SRSR)；等都是命題公式。等都是命題公式。例例3 3. .3.13.1例例3.3.23.3.2符號串：符號串：( (PQPQ) )QQ) )； ( (PQPQ；( (PQPQ( (R R； PQPQ。等都不是合法的命題公式。等都不是合法的命題公式。342022-3-112022-3-113.3.2 3.3.2 公式的解釋與真值表公式的解釋與真值表定義定義3.3.3 3.3.3 設(shè)設(shè)P P1 1、P P2 2、P Pn

28、 n是出現(xiàn)在公式是出現(xiàn)在公式G G中的所中的所有命題變元有命題變元，指定指定P P1 1、P P2 2、P Pn n一組真值，則這組一組真值，則這組真值稱為真值稱為G G的一個的一個解釋解釋, ,常記為常記為。 一般來說，若有個命題變元，則應(yīng)有一般來說，若有個命題變元，則應(yīng)有2 2n n個不個不同的解釋。同的解釋。 如果公式如果公式G G在解釋下是真的，則稱在解釋下是真的，則稱滿足滿足G G；如；如果果G G在解釋下是假的，則稱在解釋下是假的，則稱弄假弄假G G。定義定義3.3.43.3.4 將將公式公式G G在其所有可能解釋下在其所有可能解釋下的的真值情況真值情況列成列成的表，稱為的表，稱為

29、G G的的真值表真值表。352022-3-112022-3-11例例3 3. .3.53.5求下面公式的真值表：求下面公式的真值表： (P(P( P PQ)R)QQ)R)Q 其中，、是的所有命題變元。其中，、是的所有命題變元。P Q R P PQ( PQ)RP( PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1 0 1 10 1 1 1 1 1 111 0 0 0 1 0 001 0 1 0 1 1 111 1 0 0 0 0 011 1 1 0 0 0 01362022-3-112022-3-11例例3 3. .3.53.5（續(xù)）（續(xù)）P Q R(P( PQ

30、)R)Q0 0 0 1 1 0 0 1 1 1 0 0 10 0 1 1 1 0 0 1 1 1 0 0 10 1 0 1 1 1 0 1 1 1 1 0 10 1 1 1 1 1 1 1 1 1 1 1 11 0 0 0 0 1 0 0 0 0 1 0 01 0 1 1 0 1 1 1 1 0 1 1 11 1 0 0 0 0 0 1 0 0 0 0 11 1 1 0 0 0 0 1 0 0 0 0 1化簡表示：化簡表示：372022-3-112022-3-11例例3 3. .3.53.5（續(xù)）（續(xù)）P Q R(P( PQ)R)Q0 0 010 0 110 1 010 1 111 0 001

31、 0 111 1 011 1 1 1進(jìn)一步化簡為：進(jìn)一步化簡為：382022-3-112022-3-11例例3.3.63.3.6 P Q () () ( ) (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面這組公式的真值表：求下面這組公式的真值表： 1 1 ( ()； 2 2( ()； 3 3 ( ( ) ) ( (Q)Q)。392022-3-112022-3-11從這三個真值表可以看到一個非常有趣的事實：從這三個真值表可以看到一個非常有趣的事實： 公式公式G G1 1對所有可能的解釋具有對所有可能的解釋具有“真真”值值 公式公式G G3 3對所有可能的解釋均具

32、有對所有可能的解釋均具有“假假”值值 公式公式G G2 2則具有則具有“真真”和和“假假”值值結(jié)論結(jié)論402022-3-112022-3-11定義定義3.3.53.3.5公式公式G G稱為稱為永真公式永真公式( (重言式重言式) )，如果在它的所有解，如果在它的所有解釋之下都為釋之下都為“真真”。公式公式G G稱為稱為永假公式永假公式( (矛盾式矛盾式),),如果在它的所有解釋如果在它的所有解釋之下都為之下都為“假假”。公式公式G G稱為稱為可滿足的可滿足的，如果它不是永假的。，如果它不是永假的。412022-3-112022-3-11從上述定義可知三種特殊公式之間的關(guān)系：從上述定義可知三種特

33、殊公式之間的關(guān)系：1)1) 永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2) 永真式一定是可滿足式永真式一定是可滿足式, ,可滿足式不一定是永真式可滿足式不一定是永真式3)3) 可滿足式的否定不一定為不可滿足式可滿足式的否定不一定為不可滿足式( (即為矛盾式即為矛盾式) )結(jié)論結(jié)論422022-3-112022-3-11例例3.3.73.3.7寫出下列公式的真值表，并驗證其公式是重言式、寫出下列公式的真值表，并驗證其公式是重言式、矛盾式、可滿足公式。矛盾式、可滿足公式。（1 1）G G1 1=(=() )( ( ) )

34、；（2 2）G G2 2=(=(Q)Q)( ( ( (Q)Q) (Q(Q)；（3 3）G G3 3=(P=(P Q)Q) Q Q。432022-3-112022-3-11例例3.3.7 3.3.7 解解P Q() ( )( Q) (Q) (Q) (PQ) Q0 01 0 10 11 0 11 0 1 0 11 11 0 0永真公式永真公式永假公式永假公式可滿足公式可滿足公式三個公式的真值表如下：三個公式的真值表如下：442022-3-112022-3-11若將其看成兩個公式，分別令：若將其看成兩個公式，分別令： ， 。則則是一個永真公式，即這兩個公式對任何是一個永真公式，即這兩個公式對任何解釋

35、都必同為真假，此時，說和相等，記為解釋都必同為真假，此時，說和相等，記為。為此可定義：。為此可定義：分析公式（分析公式（1 1）定義定義3 3. .3.63.6 設(shè)設(shè)G G、H H是是公式，公式，如果在任意解釋如果在任意解釋下，下，G G與與H H的的真值相同，則稱公式真值相同，則稱公式G G、H H是是等價的等價的，記作記作G GH H。452022-3-112022-3-11公式公式G G、H H等價等價的充分必要條件是公式的充分必要條件是公式G GH H是永真公式是永真公式證明證明: :“”假定假定G G，H H等價，則等價，則G G，H H在其任意解釋在其任意解釋下或同為真或同為假，于

36、是由下或同為真或同為假，于是由“”的意義知，的意義知，G GH H在其任何的解釋下，其真值為在其任何的解釋下，其真值為“真真”，即，即G GH H為永真公式。為永真公式。“”假定公式假定公式G GH H是永真公式，是它的任意解釋，是永真公式，是它的任意解釋，在下，在下，G GH H為真，因此，為真，因此，G G、H H或同為真，或同為假，或同為真，或同為假，由于的任意性，故有由于的任意性，故有G GH H。定理定理3 3. .3.13.1462022-3-112022-3-11 首先，雙條件詞首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式是一種邏輯聯(lián)結(jié)詞，公式G GH H是命題公式，其中是命題公式，

37、其中“”是一種邏輯運算，是一種邏輯運算，G GH H的結(jié)果仍是一個命題公式的結(jié)果仍是一個命題公式。而邏輯等價而邏輯等價“”則是描則是描述了兩個公式述了兩個公式G G與與H H之間的一種邏輯等價關(guān)系，之間的一種邏輯等價關(guān)系，G GH H表表示示“命題公式命題公式G G等等價價于命題公式于命題公式H H”，G GH H 的結(jié)果的結(jié)果不不是命題公式是命題公式。 其次，如果要求用計算機(jī)來判斷命題公式其次，如果要求用計算機(jī)來判斷命題公式G G、H H是是否邏輯等價，即否邏輯等價，即G GH H那是辦不到的那是辦不到的，然而計算機(jī)卻可然而計算機(jī)卻可“計算計算”公式公式G GH H是否是永真公式。是否是永真

38、公式。 “” 與與“”的區(qū)別的區(qū)別472022-3-112022-3-11“= =”的性質(zhì)的性質(zhì)由于由于“= =”不是一個聯(lián)結(jié)詞，而是一種關(guān)系，為此，不是一個聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個性質(zhì)：這種關(guān)系具有如下三個性質(zhì)：（1 1）自反性）自反性 G=GG=G；（2 2）對稱性）對稱性 若若G=HG=H，則，則H=GH=G；（3 3）傳遞性）傳遞性 若若G=HG=H，H=SH=S，則，則G=SG=S。這三條性質(zhì)體現(xiàn)了這三條性質(zhì)體現(xiàn)了“= =”的實質(zhì)含義。的實質(zhì)含義。 482022-3-112022-3-113.3.4 3.3.4 命題公式的基本等價關(guān)系命題公式的基本等價關(guān)系例例

39、3.3.83.3.8 證明公式證明公式G G1 1( () )與公式與公式G G2 2(PQ)(QP)(PQ)(QP)之間是邏輯等價的。之間是邏輯等價的。 解：解：根據(jù)定理根據(jù)定理3.3.13.3.1，只需判定公式，只需判定公式G G3 3( () ) (PQ)(QP)(PQ)(QP)為永真公式。為永真公式。P Q G3() (Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11 1 1 1 1 1 1492022-3-112022-3-11設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：基本等價公式基本等價公式1) 1) 1 1：GGGG

40、G G ( (冪等律冪等律) ) 2 2：GGGGG G2) 2) 3 3：GHGHHG HG ( (交換律交換律) ) 4 4：GHGHHGHG3) 3) 5 5：G(HS)G(HS)(GH)S(GH)S( (結(jié)合律結(jié)合律) ) 6 6: : G(HS) G(HS)(GH)S(GH)S4)4) 7 7：G(GH)G(GH) G G ( (吸收律吸收律) ) 8 8：G(GH)G(GH) G G502022-3-112022-3-115)5) 9 9：G(HS)G(HS)(GH)(GS)(GH)(GS)( (分配律）分配律） 1010：G(HS)G(HS)(GH)(GS)(GH)(GS)6)

41、6) 1111：GGG G( (同一律同一律) ) 1212：GGG G 7) 7) 1313：GG( (零律）零律） 1414：GG8) 8) 1515：GGGG1 1( (排中律排中律) )9) 9) 1616：GGGG0 0( (矛盾律矛盾律) )基本等價公式（續(xù)）基本等價公式（續(xù)）512022-3-112022-3-11基本等價公式（續(xù)）基本等價公式（續(xù)）10) 10) 1717：(G)(G)G G ( (雙重否定律雙重否定律) )11) 11) 1818：(GH)(GH)GH GH (De Morgan(De Morgan定律定律) ) 1919：(GH)(GH)GHGH。12) 1

42、2) 2020: : (G(GH)H)( (GH)(HGGH)(HG) ) ( (等價等價) )13) 13) 2121：(GH)(GH)(GH) (GH) ( (蘊涵蘊涵) )14) 14) E E2222：G G G G。 ( (假言易位假言易位) )15)15) E E2323：G G G G。 ( (等價否定等式等價否定等式) )16)16) E E2424：(G(G ) (G) (G ) ) G G ( (歸謬論歸謬論) )522022-3-112022-3-11這種圖是將這種圖是將G G，H H理解為某總體論域上的子集合，而理解為某總體論域上的子集合，而規(guī)定規(guī)定GHGH為兩集合的公

43、共部分為兩集合的公共部分（交集合），（交集合），GHGH為為兩集合的全部兩集合的全部（并集合），（并集合），G G為總體論域（如矩為總體論域（如矩形域）中形域）中G G的的補(bǔ)集，補(bǔ)集，將命題中的真值將命題中的真值“1 1”理解為集理解為集合中的總體論域（全集），將命題中的真值合中的總體論域（全集），將命題中的真值“0 0”理解為集合中的空集，則有：理解為集合中的空集，則有： GH GH GUABUABUA命題與集合之間的關(guān)系命題與集合之間的關(guān)系53 “” 對對“”與與“”對對“”的對比的對比等冪律等冪律; ; GGGGG GGG GGG G交換律交換律= = = GHGHHGHG GH GHH

44、GHG結(jié)合律結(jié)合律A(BC)=(AB)CA(BC)=(AB)CA(BC)=(AB)CA(BC)=(AB)CG(HS)=(GH)SG(HS)=(GH)SG(HS)=(GH)SG(HS)=(GH)S恒等律恒等律；GG GG零律零律；GG GG吸收律吸收律 A(AB)=A A(AB)=A A(AB)=A A(AB)=A G(GH)=G G(GH)=GG(GH)=G G(GH)=G否定律否定律 (G)(G)G G分配律分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)G(HS)=(GH)(GS)G(HS)=(GH)(GS)G(HS)=

45、(GH)(GS)G(HS)=(GH)(GS)AA 542022-3-112022-3-11設(shè)設(shè)G G( (P P1 1, ,P P2 2, , ,P Pn n) )是一個命題公式是一個命題公式，其中其中： P P1 1、P P2 2、P Pn n是命題變元是命題變元，G G1 1(P(P1 1, ,P P2 2, , ,P Pn n) )、G G2 2(P(P1 1, ,P P2 2, , ,P Pn n) )、.、G Gn n(P(P1 1, ,P P2 2, , ,P Pn n) )為任意的為任意的命題公式，命題公式，分別分別用用G G1 1、G G2 2、G Gn n取代取代G G中的中

46、的P P1 1、P P2 2、P Pn n后得到新的命后得到新的命題題公式公式： G(G(G G1 1, ,G G2 2, , ,G Gn n) )G G( (P P1 1, ,P P2 2, , ,P Pn n) )若若G G是永真公式是永真公式（或永假公式或永假公式），），則則G G也是一個也是一個永真公式永真公式（或永假公式或永假公式）。定理定理3.3.2(3.3.2(代入定理代入定理) )552022-3-112022-3-11例例3.3.93.3.9設(shè)設(shè)( (, , ) )( ( ()，證明公，證明公式式G G是一個永真公式。另有兩個任意公式：是一個永真公式。另有兩個任意公式： (

47、(, , ) )( ( ) )； ( (, , ) )( () )。 進(jìn)一步驗證代入定理的正確性。進(jìn)一步驗證代入定理的正確性。 解解 建立公式建立公式G G的真值表如的真值表如右所示。可見右所示?？梢姙橛勒婀?。為永真公式。P Q()0 010 111 011 11562022-3-112022-3-11例例3.3.93.3.9（續(xù)）（續(xù)） 將，代入到中分別取代G中的命題變元P、Q，所得到的公式為： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。P Q( )( )()()0 0 1 1 1 1 1 1 1 1 00 1 0 0 0

48、0 0 1 0 1 01 0 1 1 0 1 1 0 0 1 01 1 1 0 1 1 0 1 1 1 1572022-3-112022-3-11定理定理3.33.3.3.3( (替換定理替換定理) )設(shè)設(shè)G G1 1是是G G的子公式的子公式( (即即 G G1 1是公式是公式G G的一部分的一部分) )，H H1 1是任是任意的命題公式，在意的命題公式，在G G中凡出現(xiàn)中凡出現(xiàn)G G1 1處都以處都以H H1 1替換后得替換后得到新的命題公式到新的命題公式H H，若，若G G1 1H H1 1，則則G GH H。利用利用2424個基本等價公式及代入定理和替換定個基本等價公式及代入定理和替換

49、定理，可完成公式的轉(zhuǎn)化和等價判定。理，可完成公式的轉(zhuǎn)化和等價判定。582022-3-112022-3-11例例3.3.103.3.10利用基本的等價關(guān)系，完成如下工作：利用基本的等價關(guān)系，完成如下工作：（1 1）證明公式之間的等價關(guān)系：）證明公式之間的等價關(guān)系：證明證明( () = () = ()（2 2）化簡公式：）化簡公式：證明證明( ( P(P( R)(R)(R)(PR) = R R)(PR) = R 592022-3-112022-3-11例例3.3.10 3.3.10 解答解答（1 1） P P(Q(QR)=R)= P P(Q(QR)=R)= P P( ( Q QR)R) =( =(

50、 P P Q)R=Q)R= (P(PQ)R=(PQ)R=(PQ)RQ)R 即有即有: : P P(Q(QR)=(PR)=(PQ)RQ)R； （2 2） ( ( P(P( QR)(QR)(PR) QR)(QR)(PR) = ( = ( PP Q)R)(QP)R)Q)R)(QP)R) = ( = ( (PQ)R)(QP)R)(PQ)R)(QP)R) = ( = ( (PQ)(QP)R(PQ)(QP)R = TR = R = TR = R 即有即有: : ( ( P(P( QR)(QR)(PR) = RQR)(QR)(PR) = R。 602022-3-112022-3-113.3.6 3.3.6

51、命題公式的應(yīng)用命題公式的應(yīng)用例例3.3.113.3.11 利用基本的等價關(guān)系，化簡下列電路圖利用基本的等價關(guān)系，化簡下列電路圖 &11&TSRQPRPSQPSPQRP解：解：上述電路圖可描述為：上述電路圖可描述為：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)（2 2）(PQR)(PQS)(PST)(PQR)(PQS)(PST)612022-3-112022-3-113.3.6 3.3.6 命題公式的應(yīng)用命題公式的應(yīng)用將下面程序語言進(jìn)行化簡。將下面程序語言進(jìn)行化簡。If A then if B then X else Y else if B

52、then X else YIf A then if B then X else Y else if B then X else Y TFFTFTStartStartAXYEndBB 解：解：執(zhí)行執(zhí)行X X的條件為：的條件為： ( ()()( ) ) 執(zhí)行執(zhí)行Y Y的條件為：的條件為： ( ( )()( ) )622022-3-112022-3-11例例3.3.12(3.3.12(續(xù)）續(xù)） 執(zhí)行執(zhí)行X X的條件可化簡為：的條件可化簡為：( ()()( ) )( ( ) )執(zhí)行執(zhí)行Y Y的條件可化簡為：的條件可化簡為：( ( )()( ) ) ( ( ) ) TXYEndStartStartAF程

53、序可簡化為：程序可簡化為：If B then X else YIf B then X else Y 632022-3-112022-3-113.5 3.5 公式的標(biāo)準(zhǔn)型公式的標(biāo)準(zhǔn)型范式范式3.5.1 3.5.1 析取范式和合取范式析取范式和合取范式定義定義3.5.13.5.1 （1 1）命題變元或命題變元的否定稱為）命題變元或命題變元的否定稱為文字文字（2 2）有限個文字的析取稱為）有限個文字的析取稱為析取式析取式( (也稱為也稱為子句）子句）（3 3）有限個文字的合取稱為）有限個文字的合取稱為合取式合取式( (也稱為也稱為短語）短語）（4 4）P P與與 P P稱為稱為互補(bǔ)對互補(bǔ)對。6420

54、22-3-112022-3-11例子例子（1 1）、）、 是文字；是文字；（2 2）是子句；是子句； （3 3）是短語。是短語。 P P是一個子句，這種說法正確么？是一個子句，這種說法正確么？一個命題變元或者其否定既可以是簡單一個命題變元或者其否定既可以是簡單的子句，也可以是簡單的短語。的子句，也可以是簡單的短語。因此，因此， 不但是文字，也是子句、短語不但是文字，也是子句、短語 652022-3-112022-3-11定義定義3.5.23.5.2（1 1）有限個短語的析取式稱為）有限個短語的析取式稱為析取范式析取范式（2 2）有限個子句的合取式稱為）有限個子句的合取式稱為合取范式合取范式一個

55、不含最外層括號的短語（子句）也一個不含最外層括號的短語（子句）也可以是析取范式（合取范式）。可以是析取范式（合取范式）。662022-3-112022-3-11例子例子（1 1）、）、 是析取范式、合取范式；是析取范式、合取范式；（2 2） 是子句、析取范式、合取范式，是子句、析取范式、合取范式， ( ( ) )僅是子句、合取范式；僅是子句、合取范式；（3 3） 是短語、析取范式、合取范式，是短語、析取范式、合取范式， ( () )僅是短語、析取范式；僅是短語、析取范式；（4 4）( ()()( ) )是析取范式；是析取范式；（5 5）( ()()( ) )是合取范式；是合取范式；（6 6）句

56、子）句子( ( ) )、 ( () )既不是析取范既不是析取范式也不是合取范式式也不是合取范式672022-3-112022-3-11總結(jié)總結(jié)（1 1）單個單個的的文字文字是是子句、短語、析取范式，合取范式子句、短語、析取范式，合取范式（2 2）單個單個的的子句子句是是析取范式析取范式；（3 3）單個單個的的短語短語是是合取范式合取范式；（4 4）若）若單個單個的的子句（短語）子句（短語）無最外層括號，則是無最外層括號，則是合取合取范式（析取范式）；范式（析取范式）；（5 5）析取范式、合取范式析取范式、合取范式僅含聯(lián)結(jié)詞集僅含聯(lián)結(jié)詞集 ， （6 6） “ ”聯(lián)結(jié)詞僅出現(xiàn)在聯(lián)結(jié)詞僅出現(xiàn)在命題變

57、元前命題變元前。682022-3-112022-3-11范式的求解方法范式的求解方法定理定理3.5.13.5.1 對于任意命題公式，都存在與其等價對于任意命題公式，都存在與其等價的析取范式和合取范式。的析取范式和合取范式。轉(zhuǎn)換方法：轉(zhuǎn)換方法：（1 1）利用等價公式中的等價式和蘊涵式將公式中）利用等價公式中的等價式和蘊涵式將公式中的的、用聯(lián)結(jié)詞用聯(lián)結(jié)詞 、來取代，這可利用來取代，這可利用如下等價關(guān)系：如下等價關(guān)系：( () = () = ( ) )；( () = () = ()()() ) = ( = ( )()( ) )。692022-3-112022-3-11范式的求解方法范式的求解方法(

58、(續(xù)續(xù)) )（2 2）重復(fù)使用德）重復(fù)使用德 摩根定律將否定號移到各個命題摩根定律將否定號移到各個命題變元的前端，并消去多余的否定號，這可利用如下變元的前端，并消去多余的否定號，這可利用如下等價關(guān)系：等價關(guān)系： ( ( ) =) =； ( () = ) = ； ( () = ) = 。（3 3）重復(fù)利用分配律，可將公式化成一些合取式的）重復(fù)利用分配律，可將公式化成一些合取式的析取，或化成一些析取式的合取，這可利用如下等析取，或化成一些析取式的合取，這可利用如下等價關(guān)系：價關(guān)系：( () = () = ()()() )； ( () = () = ()()() )。702022-3-112022-

59、3-11例例3.5.13.5.1求公式：求公式：( ( )()(R)R)的析取范式和合取范式的析取范式和合取范式解解 ( ( )()(R) R) = (= ( )()( R)(R)( RP)RP)= (= ( R)(R)( RPRP）= (= ( )()( R)R)( )()( RP) RP) = (= ( R)R)合取范式合取范式= = R R析取范式析取范式 712022-3-112022-3-11范式的不惟一性范式的不惟一性 考慮公式：考慮公式： ( ()()() )， 其與之等價的析取范式：其與之等價的析取范式： ( () )； ( ()()() )； ( ( )()() )； ( (

60、)()() )。這種不惟一的表達(dá)形式給研究問題帶來了不便。這種不惟一的表達(dá)形式給研究問題帶來了不便。722022-3-112022-3-113.5.2 3.5.2 主析取范式和主合取范式主析取范式和主合取范式1 1 極小項和極大項極小項和極大項定義定義 3.5.33.5.3 在含有在含有n n個個命題變元命題變元P P1 1、P P2 2、P P3 3、P Pn n的短語或子句中，若每個命題變元與其否定不同的短語或子句中，若每個命題變元與其否定不同時存在，但二者之一恰好出現(xiàn)時存在，但二者之一恰好出現(xiàn)一次且僅一次，一次且僅一次，則稱則稱此短語或子句為此短語或子句為關(guān)于關(guān)于P P1 1、P P2 2、P P3 3