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

1、1離散數(shù)學(xué)離散數(shù)學(xué)(Discrete (Discrete Mathematics)Mathematics)課程學(xué)時：共課程學(xué)時：共9696，本，本學(xué)期學(xué)期4848裴振奎裴振奎計算機與通信工程學(xué)計算機與通信工程學(xué)院計算機科學(xué)系院計算機科學(xué)系 Tel: Tel: 2課程性質(zhì) 離散數(shù)學(xué)（又稱計算機數(shù)學(xué)）是離散數(shù)學(xué)（又稱計算機數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計算機?，F(xiàn)代數(shù)學(xué)的重要分支，是計算機專業(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)，其研究對象一般為：有限或可數(shù)個其研究對象一般為：

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

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

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

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

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

7、過：我現(xiàn)在年紀(jì)大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多錯誤。不少東西邏輯學(xué)家早就說過了，可是我不知道。要是我能年輕20歲的話，我就會回去學(xué)邏輯。15第一章 命題邏輯1.1 命題1.2 命題聯(lián)結(jié)詞1.3 命題公式1.4 真值表與等價公式1.5 蘊含式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é)詞、命題公式與翻譯、真值表與等價公式、重言式與蘊涵式、對偶與范式、推與等價公式、重言式與蘊涵式、對偶與范式、推理理論。理理論。 教學(xué)重點：教學(xué)重點： 命題邏輯中的基本概念和基本推理方法。命題邏輯中的基本概念和基本推理方法。 教學(xué)難點：推理理論。教學(xué)難點：推理理論。171.1 命題定義：定義： 具有確定真假值的陳述句叫命題。具有確定真假值的陳述句叫命題。 討論定義：討論定義： （1）命題可以是真的，或者是假的，但不能）命題可以是真的，或者是假的，但不能 同時為真又為假。同時為真又為假。 （2）命題分類：）命題分類： )原子命題（基本命題、本原命題）：原子命題（基本命題、本原命題）： 不能分解成

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

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

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

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

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

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

15、結(jié)詞的真值表： TTTFFTTTFTFFPQQP361.2 命題聯(lián)結(jié)詞 當(dāng)為“”，為“”時，則（）為“”， 否則（）均為“”。 ：稱為前件、條件、前提、假設(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)為實質(zhì)條件命題前提和結(jié)果可以有聯(lián) 系，也可以沒有聯(lián)系，只要滿足單條件命 題的定義。所以,是形式條件命題一定是實質(zhì)條件命題,反

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、 、 是五個基本聯(lián)結(jié)詞。是五個基本聯(lián)結(jié)詞。到此為止，一個符號系統(tǒng)已定義完畢，它們是：到此為止，一個符號系統(tǒng)已定義完畢，它們是： 命題變元命題變元 :、值值 :、 運算符運算符 :、 、括號括號 :（）（）關(guān)系符關(guān)系符 : 、。C1121.6 其他聯(lián)結(jié)詞全功能聯(lián)結(jié)詞集合：全功能聯(lián)結(jié)詞集合： 定義定義一個聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子一個聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價的表達出來，則稱此聯(lián)足以把一切命題公式等價的表達出來，則稱此聯(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é)詞的等價式能表達任何的一（）用中的聯(lián)結(jié)詞的等價式能表達任何的一個命題公式；個命題公式； （）刪除中的任一聯(lián)結(jié)詞，從而形成一個新（）刪除中的任一聯(lián)結(jié)詞，從而形成一個新的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞集合，至少有一個命題公式不能，至少有一個命題公式不能用用中的聯(lián)結(jié)詞的等價式來表示，則稱中的聯(lián)結(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é)詞單一表達下述命題公式：1141.6 其他聯(lián)結(jié)詞（） ，

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

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

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

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

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

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

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

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

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

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

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

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

56、n(確保該大項為F)。n 用“”聯(lián)結(jié)上述大項，即可。例如求 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)的主析取范式中含有下面小項的主析取

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

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

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