離散數(shù)學(xué)自考第一章(課后習(xí)題和答案)

1、離散數(shù)學(xué)楊老師離散數(shù)學(xué)離散數(shù)學(xué)（又稱計(jì)算機(jī)數(shù)學(xué)計(jì)算機(jī)數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計(jì)算機(jī)專業(yè)課程中的核心基礎(chǔ)課程之一。離散數(shù)學(xué)離散數(shù)學(xué)以是研究：離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般為：有限或可數(shù)個(gè)元素（例如：自然數(shù)、整數(shù)、真假值、有限個(gè)結(jié)點(diǎn)等），而離散性也是計(jì)算機(jī)科學(xué)的顯著特點(diǎn)。 離散數(shù)學(xué)離散數(shù)學(xué)離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)的其他課程如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)、容錯(cuò)技術(shù)、人工智能等有密切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。第一部分：數(shù)理邏輯 第二部分：集合論第三部分：代數(shù)系統(tǒng) 第四部分：圖論第一章 命題演算n命題概念n基本連接詞與復(fù)合命題n合式公

2、式與聯(lián)結(jié)詞優(yōu)先順序n命題公式的等價(jià)變化、命題符號(hào)化n構(gòu)造真值表證明等價(jià)式n不構(gòu)造真值表證明蘊(yùn)含式n范式與主范式，互化n應(yīng)用P、T規(guī)則的推理證明nCP規(guī)則與間接推理證明1.1 命題概念n命題：具有唯一真值的陳述句叫命題，亦可簡稱為語句。(1)命題可以是真的，或者是假的，但不能同時(shí)為真又為假(2)命題所用符號(hào)：常用大寫個(gè)英文字母表示命題。用、表示。(3)命題中所有的“真”用“”表示， 命題中所有的“假”用“”表示。(4)命令句，感嘆句，疑問句均不是命題。判斷下列句子中哪些構(gòu)成命題1.8是偶數(shù)；2.雪是黑的；3.明年國慶節(jié)是個(gè)春天；4.3+895.我是大學(xué)生；6.火星上有生物；7.星期五下午開會(huì)嗎？

3、8.請(qǐng)勿吸煙；9.這束花多么的好看啊！10.x+y 5.命題命題命題命題命題命題疑問句 不是命題祈使句 不是命題感嘆句 不是命題無法確定真值 不是命題n表示命題的符號(hào)稱為命題標(biāo)示符，例：P：今天中午十點(diǎn)下雨； 24：今天上午十點(diǎn)下雨；此處的P，24就是標(biāo)示符。n一個(gè)命題標(biāo)示符如表示確定命題，就稱為命題常量，如果命題標(biāo)示符只標(biāo)志命題的位置，就稱為命題變?cè)?，因?yàn)槊}變?cè)梢员硎救我饷}，他不能確定真值因此不是命題1.2 復(fù)合命題與聯(lián)結(jié)詞n原子命題：不能再分解的命題，不包含任何聯(lián)結(jié)詞的命題。n復(fù)合命題：經(jīng)過一些聯(lián)結(jié)詞復(fù)合而成的命題。在命題演算中也有類似的日常生活中的聯(lián)結(jié)詞稱做：“命題聯(lián)結(jié)詞”下面先介

4、紹五個(gè)常用的命題聯(lián)結(jié)詞。否定詞否定詞：（否定運(yùn)算、非運(yùn)算）（）符號(hào) , ,讀作“非”，“否定”，設(shè)命題為，則在的前面加否定詞 ，變成 ， 讀做“的否定”或“非”例：北京是一座城市。 ：北京不是一座城市。：每一種生物均是動(dòng)物。F：有一些生物不是動(dòng)物。T這里不能講成“每一種生物都不是動(dòng)物”為假命題了。對(duì)量化命題的否定，除對(duì)動(dòng)詞進(jìn)行否定外，同時(shí)對(duì)量化詞也要加以否定。（2） 的真值由P的真值來確定P PTFFT合取詞合取詞（“合取”、“積”、“與”運(yùn)算）符號(hào)“” 設(shè)，為兩個(gè)命題，則稱與的合取，讀作：“與”、“與的合取”、“并且”等。定義（由真值表給出）：PQP QQPFFFFFTFFTFFFTTTT當(dāng)

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

6、FFFFTTTFTTTT當(dāng)且僅當(dāng)、均為“”時(shí)，（）為“”。否則，其真值為“”區(qū)分“可兼或”與“不可兼或（異或，排斥或）” 析取詞為可兼或即:P和Q均為“T”時(shí)（PQ）為“T”， “不可兼或”中當(dāng)P和Q均為“T”時(shí)，則P異或Q為“F”可兼可兼“或或”：燈泡有故障或開關(guān)有故障。今晚寫字或看書。今天下雨或打雷。不可兼不可兼“或或”：他通過電視看雜技或或到劇場看雜技。 他乘火車去北京或或乘飛機(jī)去北京。單條件聯(lián)結(jié)詞：單條件聯(lián)結(jié)詞：（）符號(hào)“”，讀作：“如果則”、“如果那么”、為二個(gè)命題，（）為新的命題，讀作：“如果則”，“僅當(dāng)”，“當(dāng)且”，“是的充分條件”。（）定義（由真值表定義）： PQPQFFTFT

7、TTFFTTT當(dāng)為“”，為“”時(shí)，則（）為“”，否則（）均為“”。：稱為前件、條件、前提、假設(shè)：稱為后件、結(jié)論。（）舉例： （a）P：我拿起一本書 Q：我一口氣讀完了這本書 PQ：如果我拿起一本書，則我一口氣讀完了這本書。 （b）P：月亮出來了 Q：33=9 PQ：如果月亮出來了，則 33=9。（善意推定）雙條件聯(lián)結(jié)詞雙條件聯(lián)結(jié)詞（“等價(jià)”詞、“同”聯(lián)結(jié)詞、“等同”詞）（）符號(hào)“”設(shè)、為二個(gè)命題，則讀作：“當(dāng)且僅當(dāng)”，“等價(jià)”,“是的充分必要條件”。（）定義（見真值表）：PQPQFFTFTFTFFTTT每當(dāng)和的真值相同時(shí)，則（）的真值為“”，否則（）的真值為“”。（）舉例： 春天來了當(dāng)且僅當(dāng)燕

8、子飛回來了。 平面上二直線平行，當(dāng)且僅當(dāng)這二直線不相交。 當(dāng)且僅當(dāng)雪是白色的。 （兩者沒有關(guān)系，但是確實(shí)命題）（）,中，、的地位是平等的，、交換位置不會(huì)改變真值表中的值。命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí)命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí)（）先括號(hào)內(nèi)，后括號(hào)外（）運(yùn)算時(shí)聯(lián)結(jié)詞的優(yōu)先次序?yàn)椋?（由高到低）（）聯(lián)結(jié)詞按從左到右的次序進(jìn)行運(yùn)算 （）可省去括號(hào)，因?yàn)椤啊边\(yùn)算是可結(jié)合的。（ ）可省去括號(hào)，因?yàn)榉仙鲜鲆?guī)定而（）中的括號(hào)不能省去，因?yàn)椤啊辈粷M足結(jié)合律。 （）最外層的括號(hào)一律均可省去（）可寫成命題聯(lián)結(jié)詞小結(jié)：命題聯(lián)結(jié)詞小結(jié)：（1）五個(gè)聯(lián)結(jié)詞的含義與日常生活中的聯(lián)結(jié)詞的含義大致相同。（2）“或”可分為可兼或（

9、）和異或（ ）（不可兼或） （3） 除“”為一元運(yùn)算外，其余四個(gè)均為二元運(yùn)算。（4）“”當(dāng)前件為“”時(shí)，不論后件怎樣，則單條件命題的真值均為“”。（5）命題聯(lián)結(jié)詞是命題或命題之間的聯(lián)結(jié)詞，而不是名詞之間、數(shù)字之間和動(dòng)詞之間的聯(lián)結(jié)詞。以上介紹了五種常用的聯(lián)結(jié)詞及其相應(yīng)的復(fù)合命題形式。數(shù)理邏輯的特點(diǎn)是把邏輯推理變成類似數(shù)學(xué)演算的完全形式化了的邏輯演算，為此，首先要把推理所涉及到的各命題符號(hào)化。步驟如下：找出各簡單命題，分別符號(hào)化。找出各聯(lián)結(jié)詞，把簡單命題逐個(gè)聯(lián)結(jié)起來。約定：約定： （1）我們只注意命題的真假值，而不再去注意命題的漢語意義。（2）對(duì)命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生

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

11、先用字母表示簡單命題。P：老王去上海出差。Q：小李去上海出差。也可符號(hào)化為： （PQ）（PQ）或者 （P Q） （PQ）作業(yè)：P61：a、c、d、g、i、k3：a、c、e4：b、d1.3 命題公式與真值表命題公式命題公式命題常元：表示確定的命題T，F(xiàn)。命題變?cè)阂哉婕贋槠渥冇蛑冊(cè)?，或沒有指定真值的命題。常用大寫英文字母表示。命題公式命題公式：由命題變?cè)?、常元、?lián)結(jié)詞、括號(hào)，以規(guī)定的格式聯(lián)結(jié)規(guī)定的格式聯(lián)結(jié)起來的字符串。命題公式亦可稱為合式公式合式公式。定義定義：命題演算的合式公式規(guī)定為：）單個(gè)命題變?cè)且粋€(gè)合式公式。）若是合式公式，也為合式公式。）若、是合式公式，則（）、（）、（）、（）均為合

12、式公式。 ）當(dāng)且僅當(dāng)有限次使用 （）（）（）所生成的公式才是命題公式。 （2）（）（3）即為關(guān)于聯(lián)結(jié)詞的運(yùn)算是封閉的。）即為關(guān)于聯(lián)結(jié)詞的運(yùn)算是封閉的。子公式子公式：設(shè)Ai為公式的A的一部分，且Ai是一個(gè)子公式，稱Ai是A的子公式。命題公式的真值表命題公式的真值表 :定義：命題變?cè)锰囟ǖ拿}來取代，這一過程稱為對(duì)該命題變?cè)M(jìn)行指派。指派。真指派：指定的指派使得命題變?cè)獮檎妫患僦概桑褐付ǖ闹概墒沟妹}變?cè)獮檎?。命題公式可以看成是一個(gè)以真假值為定義域和真假值為值域的一個(gè)函數(shù)。 寫成(x)例如：公式 P (Q R) 定義三元函數(shù) Y(P，Q，R) P (Q R) 定義定義：命題公式A在其所有可能的賦

13、值下取得的值列成的表稱為A的真值表。真值表中，真值T、F可分別用1、0代替構(gòu)造真值表的步驟如下：1)找出給定命題公式中所有的命題變?cè)谐鏊锌赡艿馁x值。2)按照從低到高的順序?qū)懗雒}公式的各層次。3)對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的值，直到最后計(jì)算出整個(gè)命題公式的值。例構(gòu)造命題公式（）的真值表：PQP Q（）（）FFFFTFTTFTTFTTFTTTTF個(gè)命題變?cè)薪M真值指派；個(gè)命題變?cè)?3 組真值指派，個(gè)則有個(gè)2n個(gè)真值指派命題公式的永真式、永假式和可滿足式命題公式的永真式、永假式和可滿足式定義：定義：設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為真，則稱公式A為重言式或永真式。

14、定義：定義：設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為假，則稱公式A為矛盾式或永假式定義：定義：設(shè)A為一命題公式，若A在各種真值指派下至少存在一組成真指派，則稱A為可滿足式。（可滿足式為既不是永真式又不是永假式的命題公式）討論：（）永真式的否定為永假式（）；永假式的否定為永真式（）。（）二個(gè)永真式的析取、合取、蘊(yùn)含、等價(jià)均為永真式。列出A：(PQ)(PQ) 與B：(PR)(PR)的真值表：PQ RQPQPQRPRPRABTTTFTTFTTTTTTFFTTTTTTTTFTTTTFTTTTTFFTTTTTTTTFTTFFTFFTFFFTFFFTTTFFFFFTTTFFFTFFFFFTT

15、FTTFFF1.4.1等價(jià)式定義：定義：如果對(duì)兩個(gè)公式，不論作何種指派，它們真值均相同，則稱，是邏輯等價(jià)的，亦說（）等價(jià)于（）。并記作：對(duì)合率冪等律；結(jié)合律（）（）； （）（）；交換律；分配率（）（）（）； （）（）（）吸收率（） ；（） 德摩根率（）；（）同一律； 零率；否定率 ； 定理：定理：設(shè)X是合式公式A的子公式，若有Y也是一個(gè)合式公式，且X=Y，如果將A中的X用Y置換，得到公式B，則A B。例1：證明Q （P（P Q） Q P。設(shè)：A： Q （P（P Q） 因?yàn)?P（P Q） P 故B：Q P，即A BP12例2、3、4P14 題2 a） P （Q P） P （ Q P ） （ 等值

16、公式） P （ Q P） （ 等值公式） P P Q （交換律） P （ P Q） （ 等值公式） P （ P Q ） （ 等值公式） 得證定理定理：命題公式的充要條件是為永真式證明： （）充分性：為永真式，即、有相同的真值，所以。（）必要性：，即、有相同的真值表，所以為永真式。說明：“”為等價(jià)關(guān)系符，表示和有等價(jià)關(guān)系。不為命題公式 “”為等價(jià)聯(lián)結(jié)詞（運(yùn)算符），、為命題公式，則（）也為一命題公式。1.4.2蘊(yùn)含式定義：命題公式P稱為永真蘊(yùn)含命題公式Q，當(dāng)且僅當(dāng)PQ是一個(gè)永真式， 記作：PQ，稱P蘊(yùn)含Q。 “ ”是關(guān)系符，是關(guān)系符， 不為命題公式不為命題公式例：證明： ； P（）列出真值表 證明

17、：（）和（）為永真式（）可用等價(jià)公式證：（） （） T（） （） TPQ（）（）FFF T FF T FFTF T TF T FTF T T TF T TTT T T T T T T定理：設(shè)P、Q為任意兩個(gè)命題公式，PQ的充分必要條件是PQ， Q P。證明：若P Q ，則P Q為一永真式由定律：（ P Q ）（ P Q ）（ Q P ） （ P Q ）且（ Q P ）也為一永真式 即： P Q且Q P成立反之 P Q且Q P 則PQ也成立此定理把“”和“ ”之間建立了相應(yīng)的關(guān)系。說明若是要證明PQ，只需證明P Q且Q P 證明上述永真蘊(yùn)含式的方法有三種：（）把“ ”關(guān)系符改為“”聯(lián)結(jié)詞，證明它

18、為永真式。(a)真值表法 (b)命題演算法（）若前件為真，則命題公式為“” ，只需找出使單條件命題前件為“”的所有真值指派，試看能否導(dǎo)致后件均為“”，若為“”，則永真蘊(yùn)含關(guān)系成立。（） 由于（ P Q ） （ Q P ），找出使單條件命題的后件均為“”的所有真值指派，試看前件的所有真值是否為“”，若是，則蘊(yùn)含成立。例：（） 前件為“”的所有指派為、（）均為“”，為“”，為“”，也應(yīng)為“”，（） 成立例：（） 后件為“”的所有條件是：為“”， 代入前件得（）若為，則（）為“”；（）若為，則（）為“”；（） 成立 討論一下永真式可得出三個(gè)結(jié)論：（）若一個(gè)命題公式等價(jià)于一個(gè)永真式，則該公式一定為永真

19、式。（）若一個(gè)永真的命題公式永真蘊(yùn)含一個(gè)命題公式，則此命題公式一定也為永真式。（）若一個(gè)永假的命題公式永真蘊(yùn)含一個(gè)命題公式，則該公式可能是永真式、永假式或可滿足的。 常用的蘊(yùn)含式如下：n （ ） 化簡式化簡式n（） 附加式附加式nP 變形附加式變形附加式n（） （） 變形簡化式變形簡化式5.（） 假言推論假言推論6. （） 拒取式拒取式7.（） 析取三段論析取三段論8.（）（） （） 條件三段論條件三段論9.（）（） （） 雙條件三段論雙條件三段論10.（）（） （） （）合取構(gòu)造二難）合取構(gòu)造二難11.（）（） （） （）析取構(gòu)造二難）析取構(gòu)造二難12. （） 前后件附加前后件附加13. （

20、） 前后件附加前后件附加作業(yè)：P14 1.b、d、f2.a、c、e1.5.最小聯(lián)結(jié)詞與范式任何一個(gè)命題公式都可由五個(gè)聯(lián)結(jié)詞進(jìn)行等價(jià)代換。（） （） （） （ ） （ ）由上式公式說明五個(gè)聯(lián)結(jié)詞均可以轉(zhuǎn)化為 ，或， 定義：我們把，或， 稱為命題公式或者最小聯(lián)結(jié)詞。一個(gè)命題公式的等價(jià)變換，可以有多種不同的形式表達(dá)。那如何能化成標(biāo)準(zhǔn)形式及范式的呢？定義：把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。定義：一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)他具有形式：A1 A2 An ， A1 ， A2 ，An為命題變?cè)捌浞穸ǖ乃M成的析取式。定義：一個(gè)命題公式稱析取范式，當(dāng)且僅當(dāng)他具有形式：A1 A2 An

21、 ， A1 ， A2 ，An為命題變?cè)捌浞穸ǖ乃M成的合取式。命題變?cè)奈鋈∈揭喾Q為命題變?cè)奈鋈∈揭喾Q為“和和”。合取式亦稱為。合取式亦稱為“積積”。所以：合取范式為命題變?cè)捌浞穸ǖ暮椭e；析取方式為命題變?cè)捌浞穸ǖ姆e之和。求命題公式的析取范式方法可按下列三步（或四步）進(jìn)行：（）利用等價(jià)公式：化去“”、“”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用，表達(dá)的公式。 例: ， （）（） （）（） （）將“”深入到原子命題變?cè)?，并使變?cè)白疃嘀挥幸粋€(gè)“”詞。例： （） （）利用“”對(duì)“”的分配，將公式化成為析取范式。（）除去永假項(xiàng)得最簡析取范式。（例：求（）（）的析取范式： 解：原式 (（）

22、（）) (（） （）) ( （） （）) ( （） （）) -（1）化去）化去詞詞 （ ）（）（ ） -（2）將）將“”深入到變?cè)懊妫⒆疃啾Ａ粢粋€(gè)深入到變?cè)懊?，并最多保留一個(gè) （ ）（ ）（ ）（ ）（ ）-（3）“”對(duì)對(duì)“”的分配，化成為析取范式的分配，化成為析取范式 （）（） -（4）最簡析取范式）最簡析取范式求一個(gè)命題公式的合取范式的方法和求析取范式的方法類同：第（）、（）步相同；第（）利用“”對(duì)“”的分配就行；第（）去掉永真的析取項(xiàng)。例：求（）（）的合取范式原式 （）（） 化去化去“”詞詞（ ）（ ） “”深入到變?cè)?，并最多保留一個(gè)深入到變?cè)埃⒆疃啾Ａ粢粋€(gè)（）（ ）（ ）

23、“”對(duì)對(duì)“”的分配的分配 （ ）（ ）（ ）（ ）（最簡合取范式） 定義：在個(gè)命題變?cè)暮先∈街?，若每個(gè)變?cè)捌浞穸ú⒉煌瑫r(shí)存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，稱為布爾合取或小項(xiàng)。例：命題變?cè)狿和Q，其小項(xiàng)為： P Q， P Q， P Q， P Q對(duì)三個(gè)命題變?cè)v，其小項(xiàng)為：、 、 、 、 、有上式可知，若是有2個(gè)變?cè)?，小?xiàng)有22=4個(gè)，若是有3個(gè)變?cè)№?xiàng)有23=8個(gè)。推廣到一般：個(gè)命題變?cè)獦?gòu)成的不同小項(xiàng)有2n個(gè)（nI+）。使得每個(gè)極小項(xiàng)為真的賦值僅有一個(gè)。可以用二進(jìn)制編碼表示。與分別用1、0表示。例：對(duì)三個(gè)命題變?cè)v，其小項(xiàng)為：m111=、 m110=、 m101=、m100=、 m01

24、1= 、 m010= 、m001= 、 m000= 根據(jù)書本P17，表1.5.1可知：（1）每個(gè)小項(xiàng)具有一個(gè)相應(yīng)編碼，只有編碼與其真是指派相同時(shí)，該小項(xiàng)真值為T，在其余2n-1種指派情況下為F。m011= ，只有當(dāng)、的真值分布為F、T、T是，小項(xiàng)m011= 真值為1，其余7種指派均為F。（2）任意兩個(gè)小項(xiàng)的的合取式永假；m100 m010=（）(） ( T（3）全體小項(xiàng)的析取式為用真。定義：對(duì)給定的命題公式來講，僅含有小項(xiàng)的析取的等價(jià)式稱為給定命題公式的主析取范式。主析取范式。即小項(xiàng)之“和”為主析取范式。定理：在真值表中，一個(gè)公式的真值為的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主析取范式。定理：

25、任意含n個(gè)命題變?cè)姆怯兰偈矫}公式，其主析取式是唯一的。例：求出、 （）、的主析取范式（）FFTTFTFTFTFTTFTTTFTTTFFT（ ）（ ）（） （ ）（ ）（） （） （）（）（）（）討論此定理：（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫出其主析取范式，其方法是找出該公式為“”的行，對(duì)應(yīng)寫出小項(xiàng)的析取式，且一定是唯一的。（2）若命題公式是含有n個(gè)變?cè)挠勒媸?，則它的主析取范式一定含有2n個(gè)極小項(xiàng)。（3）若二個(gè)命題公式對(duì)應(yīng)的主析取范式相同，則此二個(gè)命題公式一定是等價(jià)的。（4）命題公式的主析取范式中小項(xiàng)的個(gè)數(shù)一定等于對(duì)應(yīng)真值表中真值為“”的個(gè)數(shù)。下面介紹不用

26、真值表，直接求命題公式主析取范式的方法，分四步：（）將命題公式化歸為與其等價(jià)的析取范式； （）除去永假項(xiàng)，合并基本積中相同項(xiàng)（例：），變?yōu)樽詈單鋈》妒?。（）利用添變?cè)姆椒?，將所有析取范式變?yōu)樾№?xiàng)。例：二個(gè)變?cè)?、，利用“”?duì)或“”的分配添項(xiàng)（） （）（） （） （）（）（）合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。例1：求（）的主析取范式解：原式（）（） -（1）化為析取范式 （） -（2）消去永假項(xiàng)，變?yōu)樽詈單鋈》妒剑ǎǎǎǎǎ?-（3）添項(xiàng)（）（） -（4）合并相同最小項(xiàng)例2：證明（） 證明方法是寫出二個(gè)命題公式的主析范式，看其是否相同：（）（） （）（）（）而 （）（） （）（）（）（） （）（

27、）（）主析范式相同，有（） 定義：在個(gè)命題變?cè)奈鋈∈街?，若每個(gè)變?cè)c其否定，并不同時(shí)存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱這種布爾析取或大項(xiàng)。與分別用0、1表示例：命題變?cè)狿和Q，其大項(xiàng)為： P Q， P Q， P Q， P Q對(duì)三個(gè)命題變?cè)v，其大項(xiàng)為：M000=、 M001= 、 M010= 、M011= 、 M100= 、 M101= 、M110= 、 M111= 推廣到一般：個(gè)命題變?cè)獦?gòu)成的不同大項(xiàng)有2n個(gè)（nI+）。使得每個(gè)大項(xiàng)為真的賦值僅有一個(gè)。定理：在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。在真值表中真值為“”的個(gè)數(shù)等于主合取范式中大項(xiàng)

28、的個(gè)數(shù)。定理：任意含有n個(gè)命題變?cè)姆怯勒婷}公式A，其主合取范式是唯一的。例：求出（）、（）、（）、（）的主合取范式。直接寫出其主合取范式： （） （）（大項(xiàng)）（） （） （） （ ）（） （）（ ）（ ）（）FFFTFTFTTTFTTFTTFFTTTFTT討論（）與命題公式等價(jià)的主合范式中大項(xiàng)的個(gè)數(shù)等于其真值表中真值為“”的個(gè)數(shù)。由真值表找大項(xiàng)的方法為：將表中值為“”的對(duì)應(yīng)真值指派中，把變?cè)獙懗煞穸?，把變?cè)姆穸▽懗勺冊(cè)?。（）只要命題公式不是永真式，則一定可以寫出對(duì)應(yīng)與其等價(jià)的唯一的主合取范式。）若命題公式為含有個(gè)變?cè)挠兰偈?，則主合取范式包含了2n個(gè)大項(xiàng)的合取式。（）可用主合取范式判定二

29、個(gè)命題公式是否等價(jià)。）已知一個(gè)命題公式的主析取范式，則一定可以直接寫出與其等價(jià)的主合取范式來。反之也行。例： （ ）（）（） 主析范式 （ ） 主合取范式（）對(duì)應(yīng)于有個(gè)變?cè)拿}公式，則一定有：主析范式極主析范式極小項(xiàng)數(shù)主合范式極大項(xiàng)數(shù)小項(xiàng)數(shù)主合范式極大項(xiàng)數(shù)2n下面介紹不用真值表求一命題公式主合取范式的方法：（1）化為與命題公式等價(jià)的合取范式；（2）除去真值為“T”的析取項(xiàng)和除去析取項(xiàng)中相同變?cè)抑槐Ａ粢粋€(gè)，變?yōu)樽詈喓先∈?；?）添項(xiàng)，使析取項(xiàng)均變?yōu)闃O大項(xiàng)；例如：、為二個(gè)變?cè)?，即：（?（）（ ）（4）合并相同的極大項(xiàng)，保留一項(xiàng)。例：求（）的主合取范式 解：原式 （）（）（） （）（ ）根據(jù)小

30、項(xiàng)與大項(xiàng)的剛好相反的編碼規(guī)則，主析取式與主合取式可以寫成統(tǒng)一的編碼：（）（）（）（主析取式）=m11 m01=（1，3）（） （）（主合取式）=M 00M10 =（0，2）（） （）（）（）（主析取式）= m00 m01 m10 =（0，1，2） （ ） （主合取式）= m11 = （3）m，M的小標(biāo)為二進(jìn)制，的小標(biāo)為二進(jìn)制，而而， 的小標(biāo)為對(duì)應(yīng)的的小標(biāo)為對(duì)應(yīng)的十進(jìn)制十進(jìn)制已知A主析取式范式，如何求主合取式范式？1.求出A的主析取式中為包含小項(xiàng)的小標(biāo)。2.把1的求出的小標(biāo)寫成與之相反的對(duì)應(yīng)大項(xiàng)。3.把2中寫成的大項(xiàng)合取，幾位A的主合式范式。1.6.推理理論按公認(rèn)的推論規(guī)則，從前提集合中推導(dǎo)出一

31、個(gè)結(jié)論來，這樣的推導(dǎo)過程稱為演繹演繹，或者叫形式證明形式證明。在任何論證中，若認(rèn)定前提是真的，且從前提集合推導(dǎo)出結(jié)論的論證是遵守了邏輯規(guī)則的，則我們稱此結(jié)論是合合法的法的。根據(jù)邏輯規(guī)則推導(dǎo)出來的任何結(jié)論稱為有效結(jié)論有效結(jié)論。推論規(guī)則推論規(guī)則就是指確定論證的有效性的判據(jù)，常是用命題形式表示這些規(guī)則，而不涉及實(shí)際命題和它的真值。本節(jié)介紹的證明方法，歸納分成三類：（一）真值表技術(shù)；（二）主范式方法及等值演算法；（三）構(gòu)造論證。 真值表技術(shù)的主要依據(jù)是“”的真值表定義。若當(dāng)且僅當(dāng)（）為永真式。PQFFTFTTTFFTTT1.6.1真值表技術(shù)定義：設(shè)H1，H2,Hm,都是命題公式，當(dāng)且僅當(dāng)H1 H2 H

32、m ，才可以說是前提集合 H1，H2,Hm 的有效結(jié)論。從給定真值表常用的判斷方法有二種： （）檢查真值表中H1，H2,Hm全部為“”的所有行，看結(jié)論是否也均為“”，若均為“”，則結(jié)論有效。否則結(jié)論無效。（）看結(jié)論為“”的所有行，檢查每行前提H1，H2,Hm中是否至少有一個(gè)為，若有“”，則結(jié)論有效；若有均為“”的行，則結(jié)論無效。例：試證明下列結(jié)論是否有效，畫出真值表：PQQ （）FFTTTTTFTTTFTFTFFFTTFTTTFFFT由真值表可見：（）， 有效（）， 無效（）， （） 有效（） ， （） 有效（）， 無效例：H1：如果大連是一個(gè)大城市，則大寨是一個(gè)鄉(xiāng)村； H2：大寨是一個(gè)鄉(xiāng)村；

33、：大連是一個(gè)大城市；則：， 無效或者稱：不能從前提集合中推導(dǎo)出來。1.6.2主范式方法及等值演算法表1.6.2及表1.6.3是常用的等值公式及蘊(yùn)含公式在推理過程中，如果命題變?cè)^多，會(huì)多次使用表1.6.2及表1.6.3。每一個(gè)推理過程就是一系列命題公式序列，其中命題公式或者是已知的前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。常用的推理規(guī)則有：P規(guī)則：在推導(dǎo)的任何步驟上都可以引入前提（條件）T規(guī)則（1）在證明的任何步驟上，所證明的結(jié)論都可以作為后續(xù)證明的前提。 （2）等價(jià)的命題公式置換。例2 證明： (PQ),(P R),(Q S)SR 步驟 推理過程 規(guī)則 根據(jù) (1) (PQ) P (2) P Q T(1) E16 (3) Q S P (4) P S T(2)(3) I6 (5) S P T(4) E18 (6) P R P (7) S R T(6) I6 (8) SR T(7) E161.6.3間接證明（反證法，歸謬法）定義：由一組前提H1，H2，Hn，利用一些公認(rèn)的推理，根據(jù)已知的等價(jià)或蘊(yùn)含公式推演得到的一個(gè)結(jié)論，級(jí)命題公式C，記作： H1 H2 HnC定