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

1、電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程1電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程離離 散散 數(shù)數(shù) 學(xué)學(xué)電子科技大學(xué)電子科技大學(xué)計算機科學(xué)與工程學(xué)院計算機科學(xué)與工程學(xué)院示示 范范 性性 軟軟 件件 學(xué)學(xué) 院院20222022年年3 3月月1818日星期五日星期五電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程22022-3-182022-3-18數(shù)理邏輯（數(shù)理邏輯（Mathematical LogicMathematical Logic） 是研究演繹推理的一門學(xué)科，用數(shù)學(xué)是研究演繹推理的一門學(xué)科

2、，用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。第二篇第二篇 數(shù)理邏輯數(shù)理邏輯電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程32022-3-182022-3-18主要研究內(nèi)容：推理主要研究內(nèi)容：推理 著重于推理過程是否正確著重于推理過程是否正確 著重于語句之間的關(guān)系著重于語句之間的關(guān)系 主要研究方法：數(shù)學(xué)的方法主要研究方法：數(shù)學(xué)的方法 就是引進一套符號體系的方法，所以就是引進一套符號體系的方法，所以數(shù)理邏輯又叫符號邏輯（數(shù)理邏輯又叫符號邏輯（Symbolic LogicSymbolic Logic）。）。 第二篇第二篇 數(shù)理邏輯

3、數(shù)理邏輯電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程42022-3-182022-3-18什么是數(shù)理邏輯什么是數(shù)理邏輯 ？用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。為什么要研究數(shù)理邏輯？為什么要研究數(shù)理邏輯？ 程序算法數(shù)據(jù)程序算法數(shù)據(jù) 算法邏輯控制算法邏輯控制總結(jié)總結(jié)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程52022-3-182022-3-18第二篇第二篇 數(shù)理邏輯數(shù)理邏輯命題邏輯命題邏輯 命題的基本命題的基本概念概念命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞命題公式命題公式命題的范式命題的范式 主要研

4、主要研 究內(nèi)容究內(nèi)容謂詞邏輯謂詞邏輯謂詞的基本謂詞的基本概念概念謂詞公式謂詞公式公式的標準公式的標準型型推理與證明技術(shù)推理與證明技術(shù)命題邏輯推理理命題邏輯推理理論論謂詞邏輯推理理謂詞邏輯推理理論論數(shù)學(xué)歸納法數(shù)學(xué)歸納法按定義證明法按定義證明法電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程62022-3-182022-3-18第三章第三章 命題邏輯命題邏輯 命題邏輯也稱命題演算，或語句邏輯。命題邏輯也稱命題演算，或語句邏輯。 研究內(nèi)容：研究內(nèi)容： （1 1）研究以命題為基本單位構(gòu)成的前提和結(jié)論）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系之間的可推導(dǎo)關(guān)系 （2

5、 2）研究什么是命題？）研究什么是命題？ （3 3）研究如何表示命題？）研究如何表示命題？ （4 4）研究如何由一組前提推導(dǎo)一些結(jié)論？）研究如何由一組前提推導(dǎo)一些結(jié)論？電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程72022-3-182022-3-18第三章第三章 命題邏輯命題邏輯 命題邏輯的特征：命題邏輯的特征： 在研究邏輯的形式時，我們把一個命在研究邏輯的形式時，我們把一個命題只分析到其中所含的命題成份為止，題只分析到其中所含的命題成份為止，不再分析下去。不把一個簡單命題再分不再分析下去。不把一個簡單命題再分析為非命題的集合，不把謂詞和量詞等析為非命題的集合，

6、不把謂詞和量詞等非命題成份分析出來。非命題成份分析出來。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程82022-3-182022-3-18第三章第三章 命題邏輯命題邏輯集合的表示方法集合的表示方法2命題公式命題公式3命題范式命題范式4命題基本概念命題基本概念1命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞2電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程92022-3-182022-3-183.1 3.1 本章學(xué)習(xí)要求本章學(xué)習(xí)要求重點掌握重點掌握一般掌握一般掌握了解了解11 1、五種基本、五種基本聯(lián)結(jié)詞聯(lián)結(jié)詞2 2、2424個基本個基本的等價公式的等價公式3

7、 3 掌握求命題掌握求命題范式的方法范式的方法3聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集的理解和學(xué)習(xí)的理解和學(xué)習(xí)2公式的代入規(guī)公式的代入規(guī)則和替換規(guī)則則和替換規(guī)則電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程102022-3-182022-3-183.2.1 3.2.1 命題命題定義定義3.2.13.2.1具有確切真值的陳述句稱為命題具有確切真值的陳述句稱為命題, , 該命題可以取一個該命題可以取一個“值值”，稱為真值。，稱為真值。真值只有真值只有“真真”和和“假假”兩種，兩種，分別用分別用“”(”(或或“”)”)和和“”(”(或或“”)”)表示。表示。3.2 3.2 命題與命題

8、聯(lián)結(jié)詞命題與命題聯(lián)結(jié)詞電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程112022-3-182022-3-18（1 1）太陽是圓的；）太陽是圓的； （2 2）成都是一個旅游城市；）成都是一個旅游城市；（3 3）北京是中國的首都；）北京是中國的首都；（4 4）這個語句是假的；）這個語句是假的；（5 5）1 11 11010；（6 6）+y+y；（7 7）我喜歡踢足球；）我喜歡踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中國是世界上人口最多的國家；）中國是世界上人口最多的國家；（1111）今天是晴

9、天；）今天是晴天；例例3.2.13.2.1TTT/F非命題非命題T/FFT/FTTT非命題非命題電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程122022-3-182022-3-18例例3.2.13.2.1（續(xù)）（續(xù)）（1212）把門關(guān)上；）把門關(guān)上；（1313）滾出去?。L出去?。?414）你要出去嗎？）你要出去嗎？（1515）今天天氣真好?。。┙裉焯鞖庹婧冒?！非命題非命題非命題非命題非命題非命題非命題非命題注意：注意：一切沒有判斷內(nèi)容的句子都不能作為命題，如命令一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。句、感嘆句

10、、疑問句、祈使句、二義性的陳述句等。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程132022-3-182022-3-18n命題一定是陳述句，但并非一切陳述句都是命題。命題一定是陳述句，但并非一切陳述句都是命題。n命題的真值有時可明確給出，有時還需要依靠環(huán)境、命題的真值有時可明確給出，有時還需要依靠環(huán)境、條件、實際情況時間才能確定其真值。條件、實際情況時間才能確定其真值。結(jié)論：結(jié)論：在數(shù)理邏輯中像字母在數(shù)理邏輯中像字母“x”“x”、“y”“y”、“z”“z”等字等字母總是表示變量。母總是表示變量。約定：約定：電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國

11、家精品課程國家精品課程142022-3-182022-3-18下列語句是否是命題？并判斷其真值結(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當且僅當雪是白的。當且僅當雪是白的。例例3.2.23.2.2電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程152022-3-182022-3-18一般來說

12、，命題可分兩種類型：一般來說，命題可分兩種類型：原子命題原子命題( (簡單命題簡單命題) )：不能再分解為更為簡單命題：不能再分解為更為簡單命題的命題。的命題。復(fù)合命題：可以分解為更為簡單命題的命題。而且復(fù)合命題：可以分解為更為簡單命題的命題。而且這些簡單命題之間是通過如這些簡單命題之間是通過如“或者或者”、“并并且且”、“不不”、“如果如果.則則.”.”、“當且僅當且僅當當”等這樣的關(guān)聯(lián)詞和標點符號復(fù)合而構(gòu)成一等這樣的關(guān)聯(lián)詞和標點符號復(fù)合而構(gòu)成一個復(fù)合命題。個復(fù)合命題。命題的分類命題的分類電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程162022-3-18202

13、2-3-181)1) 今天天氣很冷。今天天氣很冷。2)2) 今天天氣很冷并且刮風(fēng)。今天天氣很冷并且刮風(fēng)。3)3) 今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。例例3.2.33.2.3 通常用大寫的帶或不帶下標的英文字母、通常用大寫的帶或不帶下標的英文字母、.P.P、Q Q、R R、. Ai. Ai、Bi Bi 、CiCi、.Pi.Pi、QiQi、RiRi、.等表示命題等表示命題電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程172022-3-182022-3-183.2.2 3.2.2 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞設(shè)命題設(shè)命題P,QP,Q表示任意兩個

14、命題表示任意兩個命題, ,則最常見的命題聯(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 QPQ=1PQ=1P=1P=1或或Q=1Q=12.2.合取合取 P P并且并且Q QP P與與Q Q的合取的合取PQPQPQ=1PQ=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定PPP=1P=1 P=0 P=04.4.蘊涵蘊涵若若P,P,則則Q QP P蘊涵蘊涵Q QPQPQPQ=0 PQ=0 P=1,Q=0 P=1,Q=05.5.等價等

15、價 P P當且僅當當且僅當Q QP P等價于等價于Q QP PQ QP PQ=1Q=1P=1,Q=1P=1,Q=1或或P=0,Q=0P=0,Q=0例如：命題例如：命題P P：2 2是素數(shù)；是素數(shù)；Q Q：北京是中國的首都：北京是中國的首都電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程182022-3-182022-3-18總結(jié)總結(jié)P QP QPPPQPQPQPQPQPQP 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 1電子科技大學(xué)離散數(shù)

16、學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程192022-3-182022-3-18說明說明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)在聯(lián)系；間可以無任何地內(nèi)在聯(lián)系；電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程202022-3-182022-3-18說明說明3 3、聯(lián)結(jié)詞與自然語言之間的

17、對應(yīng)并非一一對應(yīng)；、聯(lián)結(jié)詞與自然語言之間的對應(yīng)并非一一對應(yīng)；聯(lián)結(jié)詞聯(lián)結(jié)詞自然語言自然語言既既又又、不僅、不僅而且而且、雖然、雖然但但是是、并且、和、與，等等；、并且、和、與，等等；如如P P則則Q Q、只要、只要P P就就Q Q、P P僅當僅當Q Q、只有、只有Q Q才才P P、除非除非Q Q否則否則P P，等等，等等等價、當且僅當、充分必要、等等；等價、當且僅當、充分必要、等等； 相容（可兼）的或相容（可兼）的或電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程212022-3-182022-3-18符號化下列命題符號化下列命題（1 1）四川不是人口最多的省份；）四

18、川不是人口最多的省份；（2 2）王超是一個德智體全面發(fā)展的好學(xué)生；）王超是一個德智體全面發(fā)展的好學(xué)生；（3 3）教室的燈不亮可能是燈管壞了或者是停電了；）教室的燈不亮可能是燈管壞了或者是停電了；（4 4）如果周末天氣晴朗，那么學(xué)院將組織我們到）如果周末天氣晴朗，那么學(xué)院將組織我們到石像湖春游；石像湖春游；（5 5）兩個三角形全等當且僅當三角形的三條邊全）兩個三角形全等當且僅當三角形的三條邊全部相等。部相等。例例3.2.43.2.4電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程222022-3-182022-3-18例例3.2.4 3.2.4 解解（1 1）設(shè)：四川

19、是人口最多的省份。）設(shè)：四川是人口最多的省份。 則命題（則命題（1 1）可表示為）可表示為。（2 2）設(shè)：王超是一個思想品德好的學(xué)生；）設(shè)：王超是一個思想品德好的學(xué)生； ：王超是一個學(xué)習(xí)成績好的學(xué)生；：王超是一個學(xué)習(xí)成績好的學(xué)生； R R：王超是一個體育成績好的學(xué)生。：王超是一個體育成績好的學(xué)生。 則命題（則命題（2 2）可表示為）可表示為RR。（3 3）設(shè)：教室的燈不亮可能是燈管壞了）設(shè)：教室的燈不亮可能是燈管壞了 ：教室的燈不亮可能是停電了：教室的燈不亮可能是停電了 則命題（則命題（3 3）可表示為）可表示為。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程23

20、2022-3-182022-3-18（4 4）設(shè)：周末天氣晴朗；）設(shè)：周末天氣晴朗； ：學(xué)院將組織我們到石像湖春游。：學(xué)院將組織我們到石像湖春游。 則命題（則命題（4 4）可表示為）可表示為。（5 5）設(shè)：兩個三角形全等；）設(shè)：兩個三角形全等； ：三角形的三條邊全部相等。：三角形的三條邊全部相等。 則命題（則命題（5 5）可表示為）可表示為。例例3.2.4 3.2.4 解解( (續(xù)續(xù)) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程242022-3-182022-3-18 為了不使句子產(chǎn)生混淆，作如下約定，命為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)詞之優(yōu)先級如

21、下：題聯(lián)結(jié)詞之優(yōu)先級如下：1.1. 否定否定合取合取析取析取蘊涵蘊涵等價等價2.2. 同級的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序同級的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序( (從左從左到右到右) )3.3. 若運算要求與優(yōu)先次序不一致時，可使用若運算要求與優(yōu)先次序不一致時，可使用括號；同級符號相鄰時，也可使用括號。括號；同級符號相鄰時，也可使用括號。括號中的運算為最優(yōu)先級。括號中的運算為最優(yōu)先級。約約 定定電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程252022-3-182022-3-18設(shè)命題設(shè)命題P P：明天上午七點下雨；：明天上午七點下雨；Q Q：明天上午七點下雪；：明天上午

22、七點下雪；R R：我將去學(xué)校。：我將去學(xué)校。符號化下述語句：符號化下述語句：如果明天上午七點不是雨夾雪，則我將去學(xué)校如果明天上午七點不是雨夾雪，則我將去學(xué)校如果明天上午七點不下雨并且不下雪，則我將去學(xué)如果明天上午七點不下雨并且不下雪，則我將去學(xué)校校如果明天上午七點下雨或下雪，則我將不去學(xué)校如果明天上午七點下雨或下雪，則我將不去學(xué)校明天上午我將雨雪無阻一定去學(xué)校明天上午我將雨雪無阻一定去學(xué)?？煞柣癁椋嚎煞柣癁椋?PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。 或或 (PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)R(PQ)R。例例3.2.53.2.

23、5可符號化為：可符號化為：(PQ)R(PQ)R。可符號化為可符號化為:(PQ)R:(PQ)R?？煞柣癁榭煞柣癁?(PQ)R:(PQ)R。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程262022-3-182022-3-18例例3.2.63.2.6設(shè)命題設(shè)命題P P：你陪伴我；：你陪伴我； Q Q：你代我叫車子；：你代我叫車子； R R：我將出去。：我將出去。 符號化下述語句：符號化下述語句： 除非你陪伴我或代我叫車子，否則我將不出去除非你陪伴我或代我叫車子，否則我將不出去 如果你陪伴我并且代我叫輛車子，則我將出去如果你陪伴我并且代我叫輛車子，則我將出去 如果你

24、不陪伴我或不代我叫輛車子，我將不出去如果你不陪伴我或不代我叫輛車子，我將不出去R(PQ) R(PQ) 或或 (PQ)R(PQ)R(PQ)R(PQ)R(PQ)R(PQ)R電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程272022-3-182022-3-18例例設(shè)設(shè)P:P:雪是白色的雪是白色的;Q:2+2=4;Q:2+2=4。將下列命題符號化：。將下列命題符號化：（1 1）因為雪是白色的，所以）因為雪是白色的，所以2+2=42+2=4； PQ PQ （2 2）如果）如果2+2=42+2=4，則雪是白色的；，則雪是白色的； QP QP（3 3）只有雪是白色的，才有）只有

25、雪是白色的，才有2+2=42+2=4； QP QP（4 4）只有）只有2+2=42+2=4，雪才是白色的；，雪才是白色的； PQ PQ（5 5）只要雪不是白色的，就有）只要雪不是白色的，就有2+2=42+2=4； PQ PQ（6 6）除非雪是白色的，否則）除非雪是白色的，否則2+242+24； P P Q Q或或QPQP（7 7）雪是白色的當且僅當）雪是白色的當且僅當2+2=42+2=4； P P Q Q電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程282022-3-182022-3-183.2.4 3.2.4 命題聯(lián)結(jié)詞的應(yīng)用命題聯(lián)結(jié)詞的應(yīng)用例例 3.2.7 3

26、.2.7 用復(fù)合命題表示如下圖所示的開關(guān)用復(fù)合命題表示如下圖所示的開關(guān)電路：電路： 圖圖3.2.1 3.2.1 圖圖3.2.2 3.2.2 圖圖3.2.33.2.3PQPPQABABABABA A設(shè)：設(shè)：開關(guān)閉合；：開關(guān)閉合。：開關(guān)閉合；：開關(guān)閉合。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程292022-3-182022-3-18用復(fù)合命題表示如下圖所示的邏輯電路：用復(fù)合命題表示如下圖所示的邏輯電路：例例 3.2.8 3.2.8圖圖3.2.4 3.2.4 圖圖3.2.5 3.2.5 圖圖3.2.63.2.6QPP P Q QQPP PQ QPP P解解: :

27、設(shè)設(shè)P P：輸入端為高電位：輸入端為高電位,Q,Q：輸入端為高電位：輸入端為高電位, ,則則 “ “與門與門”對應(yīng)于對應(yīng)于PQPQ； “ “或門或門”對應(yīng)于對應(yīng)于PQPQ； “ “非門非門”對應(yīng)于對應(yīng)于P P。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程302022-3-182022-3-183.3 3.3 命題公式、解釋與真值表命題公式、解釋與真值表定義定義3.3.1 3.3.1 一個特定的命題是一個常值命題，它不是一個特定的命題是一個常值命題，它不是具有值具有值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。而一個任

28、意的沒有賦予具體內(nèi)容的原子命題是一個變而一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題，常稱它為命題變量量命題，常稱它為命題變量( (或命題變元或命題變元) )，該命題變，該命題變量無具體的真值，它的變域是集合量無具體的真值，它的變域是集合TT，F(xiàn)(F(或或00，1)1)注意注意(1)(1)復(fù)合命題為命題變元的復(fù)合命題為命題變元的“函數(shù)函數(shù)”,”,其函數(shù)值仍為其函數(shù)值仍為 真真 或或“假假”值。值。(2)(2)真值函數(shù)或命題公式，沒有確切真值。真值函數(shù)或命題公式，沒有確切真值。真值函數(shù)真值函數(shù)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程312022-3-18

29、2022-3-183.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、等表示。等表示。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程322022-3-182022-3-1

30、8符號串：符號串：(P(QR)(Q(SR)(P(QR)(Q(SR)； (PQ) (PQ)； (P(PQ) (P(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命題公式。等都是命題公式。例例3.3.13.3.1例例3.3.23.3.2符號串：符號串：(PQ)Q)(PQ)Q)； (PQ(PQ；(PQ(R(PQ(R； PQ PQ。等都不是合法的命題公式。等都不是合法的命題公式。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程332022-3-182022-3-18例例3.3.33.3.3試用符號形式寫出下列命題：試用符號形式寫出下列命題：（1 1）

31、雖然今天天氣晴朗，老陳還是不來；）雖然今天天氣晴朗，老陳還是不來；（2 2）除非你陪伴我或代我叫車子，否則我將不出去；）除非你陪伴我或代我叫車子，否則我將不出去；（3 3）停機的原因在于語法錯誤或者程序錯誤；）停機的原因在于語法錯誤或者程序錯誤；（4 4）若）若a a和和b b是偶數(shù)，則是偶數(shù)，則a+ba+b是偶數(shù)；是偶數(shù)；（5 5）我們要做到身體好、學(xué)習(xí)好、工作好，為祖國四）我們要做到身體好、學(xué)習(xí)好、工作好，為祖國四化建設(shè)而奮斗?；ㄔO(shè)而奮斗。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程342022-3-182022-3-18例例3.3.3 3.3.3 解解

32、（1 1）P P：今天天氣晴朗：今天天氣晴朗,Q,Q：老陳要來：老陳要來, ,則有：則有：PQPQ；（2 2）P P：你陪伴我；：你陪伴我； Q Q：你代我叫車子；：你代我叫車子；R R：我出去。：我出去。則有：則有：RPQ RPQ 或或 P Q R P Q R；（3 3）P P：停機的原因在于語法錯誤，：停機的原因在于語法錯誤，Q Q：停機的原因在：停機的原因在于程序錯誤，則有：于程序錯誤，則有：PQPQ；（4 4）P P：a a是偶數(shù)；是偶數(shù)；Q Q：b b是偶數(shù)，是偶數(shù)，R R：a+ba+b是偶數(shù)，則有：是偶數(shù)，則有：PQRPQR；（5 5）P P：我們要做到身體好：我們要做到身體好,Q

33、,Q：我們要做到學(xué)習(xí)好：我們要做到學(xué)習(xí)好, R, R：我們要做到工作好，我們要做到工作好，S S：我們要為祖國四化建設(shè)而奮斗，：我們要為祖國四化建設(shè)而奮斗，則有：則有：PQRPQR S S。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程352022-3-182022-3-18公式公式(P(QR)(Q(SR)(P(QR)(Q(SR)可表示可表示如下：如下：(P(QR)(Q(SR)(P(QR)(Q(SR)P(QR)P(QR) Q(SR) Q(SR)P QR P QR Q Q SR SRQ R Q R S R S RS S例例3.3.43.3.4電子科技大學(xué)離散數(shù)學(xué)課

34、程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程362022-3-182022-3-183.3.2 3.3.2 公式的解釋與真值表公式的解釋與真值表定義定義3.3.3 3.3.3 設(shè)設(shè)P1P1、P2P2、PnPn是出現(xiàn)在公式是出現(xiàn)在公式G G中的所中的所有命題變元，指定有命題變元，指定P1P1、P2P2、PnPn一組真值，則這一組真值，則這組真值稱為組真值稱為G G的一個解釋的一個解釋, ,常記為。常記為。 一般來說，若有個命題變元，則應(yīng)有一般來說，若有個命題變元，則應(yīng)有2n2n個不個不同的解釋。同的解釋。 如果公式如果公式G G在解釋下是真的，則稱滿足在解釋下是真的，則稱滿足G G；如

35、；如果果G G在解釋下是假的，則稱弄假在解釋下是假的，則稱弄假G G。定義定義3.3.4 3.3.4 將公式將公式G G在其所有可能解釋下的真值情況在其所有可能解釋下的真值情況列成的表，稱為列成的表，稱為G G的真值表。的真值表。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程372022-3-182022-3-18例例3.3.53.3.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 11

36、0 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 01電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程382022-3-182022-3-18例例3.3.53.3.5（續(xù)）（續(xù)）P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1進一步化簡為：進一步化簡為：電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程392022-3-182022-3-18例例3.

37、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)。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程402022-3-182022-3-18從這三個真值表可以看到一個非常有趣的事實：從這三個真值表可以看到一個非常有趣的事實： 公式公式G1G1對所有可能的解釋具有對所有可能的解釋具有“真真”值值 公式公式G3G3對所有可能的解釋均具有對所有可能的解釋均具有“假假”值值 公式

38、公式G2G2則具有則具有“真真”和和“假假”值值結(jié)論結(jié)論電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程412022-3-182022-3-18定義定義3.3.53.3.51.1. 公式公式G G稱為永真公式稱為永真公式( (重言式重言式) )，如果在它的所有，如果在它的所有解釋之下都為解釋之下都為“真真”。2.2. 公式公式G G稱為永假公式稱為永假公式( (矛盾式矛盾式),),如果在它的所有如果在它的所有解釋之下都為解釋之下都為“假假”。3.3. 公式公式G G稱為可滿足的，如果它不是永假的。稱為可滿足的，如果它不是永假的。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)

39、離散數(shù)學(xué)課程組國家精品課程國家精品課程422022-3-182022-3-18從上述定義可知三種特殊公式之間的關(guān)系：從上述定義可知三種特殊公式之間的關(guān)系：1)1) 永真式永真式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。2)2) 永真式一定是可滿足式永真式一定是可滿足式, ,可滿足式不一定是永真式可滿足式不一定是永真式3)3) 可滿足式的否定不一定為不可滿足式可滿足式的否定不一定為不可滿足式( (即為矛盾式即為矛盾式) )結(jié)論結(jié)論電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程432022-3-182022-3

40、-18例例3.3.73.3.7寫出下列公式的真值表，并驗證其公式是重言式、寫出下列公式的真值表，并驗證其公式是重言式、矛盾式、可滿足公式。矛盾式、可滿足公式。（1 1）G1=(G1=() )( () )；（2 2）G2=(G2=(Q)Q)( ( (Q)Q)(Q(Q)；（3 3）G3=(PG3=(PQ)Q)Q Q。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程442022-3-182022-3-18例例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永真公式永真公式永假公

41、式永假公式可滿足公式可滿足公式三個公式的真值表如下：三個公式的真值表如下：電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程452022-3-182022-3-18若將其看成兩個公式，分別令：若將其看成兩個公式，分別令： ， 。則則是一個永真公式，即這兩個公式對任何是一個永真公式，即這兩個公式對任何解釋都必同為真假，此時，說和相等，記為解釋都必同為真假，此時，說和相等，記為。為此可定義：。為此可定義：分析公式（分析公式（1 1）定義定義3.3.6 3.3.6 設(shè)設(shè)G G、H H是公式，如果在任意解是公式，如果在任意解釋下，釋下，G G與與H H的真值相同，則稱公式的真

42、值相同，則稱公式G G、H H是等價的，記作是等價的，記作G GH H。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程462022-3-182022-3-18公式公式G G、H H等價的充分必要條件是公式等價的充分必要條件是公式G GH H是永真公式是永真公式證明證明:“:“”假定假定G G，H H等價，則等價，則G G，H H在其任意解釋在其任意解釋下或同為真或同為假，于是由下或同為真或同為假，于是由“”的意義知，的意義知，G GH H在其任何的解釋下，其真值為在其任何的解釋下，其真值為“真真”，即，即G GH H為永為永真公式。真公式。“”假定公式假定公式G

43、GH H是永真公式，是它的任意解釋，是永真公式，是它的任意解釋，在下，在下，G GH H為真，因此，為真，因此，G G、H H或同為真，或同為假，或同為真，或同為假，由于的任意性，故有由于的任意性，故有G GH H。定理定理3.3.13.3.1電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程472022-3-182022-3-18 首先，雙條件詞首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式是一種邏輯聯(lián)結(jié)詞，公式G GH H是命題公式，其中是命題公式，其中“”是一種邏輯運算，是一種邏輯運算，G GH H的結(jié)果仍是一個命題公式。而邏輯等價的結(jié)果仍是一個命題公式。而邏輯等價“

44、”則是描述了兩則是描述了兩個公式個公式G G與與H H之間的一種邏輯等價關(guān)系，之間的一種邏輯等價關(guān)系，G GH H表示表示“命題公式命題公式G G等價于命題公式等價于命題公式H”H”，G GH H 的結(jié)果不是命題公式。的結(jié)果不是命題公式。 其次，如果要求用計算機來判斷命題公式其次，如果要求用計算機來判斷命題公式G G、H H是否邏輯等價，即是否邏輯等價，即G GH H那是辦不那是辦不到的，然而計算機卻可到的，然而計算機卻可“計算計算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 與與“”的區(qū)別的區(qū)別電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程4

45、82022-3-182022-3-18“=”“=”的性質(zhì)的性質(zhì)由于由于“=”“=”不是一個聯(lián)結(jié)詞，而是一種關(guān)系，為此，不是一個聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個性質(zhì)：這種關(guān)系具有如下三個性質(zhì)：（1 1）自反性）自反性 G=G G=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ì)含義。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程492022-3-182022-3-183.3.4 3.3.4

46、命題公式的基本等價關(guān)系命題公式的基本等價關(guān)系例例3.3.8 3.3.8 證明公式證明公式G1G1( () )與公式與公式G2G2(PQ)(QP)(PQ)(QP)之間是邏輯等價的。之間是邏輯等價的。 解：根據(jù)定理解：根據(jù)定理3.3.13.3.1，只需判定公式，只需判定公式G3G3( () ) (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 1電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程502022-3-182022-3-18

47、設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：基本等價公式基本等價公式1) 1) 1 1：GGGGG 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: G(HS)6: G(HS)(GH)S(GH)S4) 4) 7 7：G(GH)G(GH) G ( G (吸收律吸收律) ) 8 8：G(GH)G(GH) G G電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程512022-3

48、-182022-3-185) 5) 9 9：G(HS)G(HS)(GH)(GS)(GH)(GS)( (分配律）分配律） 1010：G(HS)G(HS)(GH)(GS)(GH)(GS)6) 6) 1111：GGG G( (同一律同一律) ) 1212：GGG G 7) 7) 1313：GG( (零律）零律） 1414：GG8) 8) 1515：GGGG1 1( (排中律排中律) )9) 9) 1616：GGGG0 0( (矛盾律矛盾律) )基本等價公式（續(xù)）基本等價公式（續(xù)）電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程522022-3-182022-3-18基本等

49、價公式（續(xù)）基本等價公式（續(xù)）10) 10) 1717：(G)(G)G G ( (雙重否定律雙重否定律) )11) 11) 1818：(GH)(GH)GH (De MoRGanGH (De MoRGan定律定律) ) 1919：(GH)(GH)GHGH12) 12) 20: (G20: (GH)H)(GH)(HG)(GH)(HG)( (等價等價) )13) 13) 2121：(GH)(GH)(GH) (GH) ( (蘊涵蘊涵) )14) E2214) E22：G G G (G (假言易位假言易位) )15) E2315) E23：G G G G ( (等價否定等式等價否定等式) )16) E2

50、416) E24：(G (G ) (G) (G) )G (G (歸謬論歸謬論) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程532022-3-182022-3-18這種圖是將這種圖是將G G，H H理解為某總體論域上的子集合，而理解為某總體論域上的子集合，而規(guī)定規(guī)定GHGH為兩集合的公共部分（交集合），為兩集合的公共部分（交集合），GHGH為為兩集合的全部（并集合），兩集合的全部（并集合），GG為總體論域（如矩為總體論域（如矩形域）中形域）中G G的補集，將命題中的真值的補集，將命題中的真值“1”“1”理解為集理解為集合中的總體論域（全集），將命題中的真值合中

51、的總體論域（全集），將命題中的真值“0”“0”理解為集合中的空集，則有：理解為集合中的空集，則有： GH GH GUABUABUA命題與集合之間的關(guān)系命題與集合之間的關(guān)系電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程54 “” “” 對對“”“”與與“”“”對對“”“”的對比的對比等冪律等冪律; ; GG GGG GGG GGG G交換律交換律= = = GH GHHGHG GH GHHGHG結(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

52、)=(GH)S恒等律恒等律；GG GG零律零律；GG G G吸收律吸收律 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)=(GH)(GS)G(HS)=(GH)(GS)AA 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程552022-3-182022-3-18設(shè)設(shè)G(P1

53、,P2,Pn)G(P1,P2,Pn)是一個命題公式，其中：是一個命題公式，其中： P1P1、P2P2、PnPn是命題變元，是命題變元，G1(P1,P2,Pn)G1(P1,P2,Pn)、G2(P1,P2,Pn)G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)Gn(P1,P2,Pn)為任意為任意的命題公式，分別用的命題公式，分別用G1G1、G2G2、GnGn取代取代G G中的中的P1P1、P2P2、PnPn后得到新的命題公式：后得到新的命題公式： G(G1,G2,Gn) G(G1,G2,Gn)G(P1,P2,Pn)G(P1,P2,Pn)若若G G是永真公式（或永假公式），則是永真公式（或永假

54、公式），則GG也是一個也是一個永真公式（或永假公式）。永真公式（或永假公式）。定理定理3.3.2(3.3.2(代入定理代入定理) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程562022-3-182022-3-18例例3.3.93.3.9設(shè)設(shè)( (, , ) )( ()，證明公，證明公式式G G是一個永真公式。另有兩個任意公式：是一個永真公式。另有兩個任意公式： ( (, , ) )( () )； ( (, , ) )( () )。 進一步驗證代入定理的正確性。進一步驗證代入定理的正確性。 解解 建立公式建立公式G G的真值表如的真值表如右所示。可見右所示。可

55、見為永真公式。為永真公式。P Q()0 010 111 011 11電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程572022-3-182022-3-18例例3.3.93.3.9（續(xù)）（續(xù)） 將，代入到中分別取代將，代入到中分別取代G G中的命題變元中的命題變元P P、Q Q，所得到的公式為：所得到的公式為： (P, Q) = G(H, S) = (H(HS)S (P, Q) = G(H, S) = (H(HS)S = ( = ()()()()()()() ) 建立新公式建立新公式(P, Q)(P, Q)的真值表。的真值表。P Q()()()()0 0 1 1 1

56、 1 1 1 1 1 00 1 0 0 0 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 1電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程582022-3-182022-3-18定理定理3.3.3(3.3.3(替換定理替換定理) )設(shè)設(shè)G1G1是是G G的子公式的子公式( (即即 G1 G1是公式是公式G G的一部分的一部分) )，H1H1是是任意的命題公式，在任意的命題公式，在G G中凡出現(xiàn)中凡出現(xiàn)G1G1處都以處都以H1H1替換后替換后得到新的命題公式得到新的命題公式H H，若，若G1G1H1H1，則，

57、則G GH H。利用24個基本等價公式及代入定理和替換定理，可完成公式的轉(zhuǎn)化和等價判定。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程592022-3-182022-3-18例例3.3.103.3.10利用基本的等價關(guān)系，完成如下工作：利用基本的等價關(guān)系，完成如下工作：（1 1）判斷公式的類型：）判斷公式的類型： 證明證明 ( () ( ()()()()() )是一個永真公是一個永真公式。式。（2 2）證明公式之間的等價關(guān)系：）證明公式之間的等價關(guān)系：證明證明() = () = ()（3 3）化簡公式：）化簡公式：證明證明( (P(P(R)(R)(R)(PR) =

58、 R R)(PR) = R 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程602022-3-182022-3-18例例3.3.10 3.3.10 證明證明（1 1）() ( ()()()()() ) = ( = ()()()()()() = ( = ()()()()() ( ()()() = ( = ()()()()() ) ( ( ()()() = ( = ()()()()()() = T) = T 即即:(:() ( ()()()()() )為永真公式；為永真公式； 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程612022-3-

59、182022-3-18例例3.3.10 3.3.10 證明（續(xù)）證明（續(xù)）（2 2） P(QR)= P(QR)=P(QR)=P(QR)=P(P(QR)QR) =( =(PPQ)R=Q)R=(PQ)R=(PQ)R(PQ)R=(PQ)R 即有即有: P(QR)=(PQ)R: P(QR)=(PQ)R； （3 3） ( (P(P(QR)(QR)(PR) QR)(QR)(PR) = ( = (PPQ)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 即有即有: (: (

60、P(P(QR)(QR)(PR) = RQR)(QR)(PR) = R。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家精品課程國家精品課程622022-3-182022-3-183.3.6 3.3.6 命題公式的應(yīng)用命題公式的應(yīng)用例例3.3.11 3.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)電子科技大學(xué)離散數(shù)學(xué)