離散數(shù)學(xué)-經(jīng)典必看

2023/7/23

計(jì)算機(jī)軟件

離散數(shù)學(xué)

DiscreteMathematics主講教師：任美睿2023/7/23

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程，為計(jì)算機(jī)科學(xué)提供了有力的理論基礎(chǔ)和工具。離散數(shù)學(xué)的基本思想、概念和方法廣泛地滲透到計(jì)算機(jī)科學(xué)與技術(shù)發(fā)展的各個(gè)領(lǐng)域，而且其基本理論和研究成果更是全面而系統(tǒng)地影響和推動(dòng)著其發(fā)展。2023/7/23

離散數(shù)學(xué)的內(nèi)容十分豐富，最重要，最核心的是：數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論。本課程主要講授以上四個(gè)方面的內(nèi)容。

2023/7/23數(shù)理邏輯簡(jiǎn)介

2023/7/23

數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科，這里所指的數(shù)學(xué)方法就是引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯又稱符號(hào)邏輯。它與數(shù)學(xué)的其它分支、計(jì)算機(jī)科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切的聯(lián)系。2023/7/23數(shù)理邏輯的研究?jī)?nèi)容現(xiàn)代數(shù)理邏輯：邏輯演算、證明論、公理集合論、遞歸論和模型論。邏輯演算是數(shù)理邏輯中最成熟的部分，在計(jì)算機(jī)科學(xué)中應(yīng)用最為廣泛，其中命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分，謂詞邏輯是在它的基礎(chǔ)上發(fā)展起來的，本門課研究命題邏輯與謂詞邏輯。2023/7/23第一章命題邏輯

PropositionLogic

第1.1節(jié)命題及聯(lián)結(jié)詞2023/7/23內(nèi)容：命題，邏輯聯(lián)結(jié)詞，命題符號(hào)化

(1)掌握命題概念

(2)掌握聯(lián)結(jié)詞含義及真值表

(3)掌握命題符號(hào)化方法

重點(diǎn)：2023/7/23一、命題的概念

命題：能判斷真假的陳述句。

命題真值：命題所表達(dá)的判斷結(jié)果。真命題：真值為真的命題。

假命題：真值為假的命題。

說明：一切沒有判斷內(nèi)容的句子，無所謂是非的句子，如感嘆句、疑問句、祈使句等都不是命題。命題是研究思維規(guī)律的科學(xué)中的一項(xiàng)基本要素，它是一個(gè)判斷的語言表達(dá)。2023/7/23例1、判斷下列句子中哪些是命題。

(1)重慶是直轄市。

(2)4是素?cái)?shù)。

(4)請(qǐng)把門關(guān)上！

(6)地球外的星球上也有人。

(3)。

√T

√F

√T

×

×

√？(5)大于2023/7/23例1、判斷下列句子中哪些是命題。

(7)明天有課嗎？

(9)我正在說假話。

(8)小明和小林都是三好生。

×

×悖論,無法判斷真值

√?(10)2020年春節(jié)是晴天。

√?2023/7/23命題的判斷判斷一個(gè)語句是否為命題，關(guān)鍵：

①首先看是否為陳述句；

②再看其真值是否唯一。要注意兩點(diǎn)：①一個(gè)陳述句在客觀上能判斷真假，而不受人的知識(shí)范圍的限制；②一個(gè)陳述句暫時(shí)不能確定真值，但到了一定時(shí)候就可以確定，與一個(gè)陳述句的真值不能唯一確定是不同的。結(jié)論:1、命題一定是陳述句，陳述句未必是命題。2、命題的真值有時(shí)可以明確給出，但有時(shí)還需要依靠環(huán)境、條件和實(shí)際環(huán)境時(shí)間才能確定其真值。2023/7/23命題的記法命題的符號(hào)化：P,Q,R,…,Pi,,Qi,Ri,…真值的符號(hào)化：1/T表真，0/F表假例：P:2是素?cái)?shù)，Q:雪是黑色的

2023/7/23命題的分類例：4是合數(shù)。原子命題例：4是合數(shù)，并且3是素?cái)?shù)。復(fù)合命題例：4是合數(shù)，并且3是素?cái)?shù)，但1既不是素?cái)?shù)也不是合數(shù)。復(fù)合命題2023/7/23例：是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。解：2023/7/23二、邏輯聯(lián)結(jié)詞。

這五種常用的聯(lián)結(jié)詞有2023/7/23真值表

1、“非”稱為的否定式，記作例如：：11是素?cái)?shù)；：11不是素?cái)?shù)取值1，取值0。01102023/7/23真值表

2、“并且”稱為的合取式，記作。例1.1，小剛和小明都是大學(xué)生000100101101：小剛是大學(xué)生，：小明是大學(xué)生解：命題符號(hào)化為：

2023/7/23注意：①自然語言中的“既…，又…”,“不但…，而且…”,“雖然…，但是…”,“一面…，一面…”,等都可符號(hào)化為，在邏輯電路中表示“與門”，在開關(guān)電路中表示“串聯(lián)”聯(lián)結(jié)方式。②但不要見到“與”或“和”就使用聯(lián)結(jié)詞2023/7/23(1)小麗既聰明又用功。

(2)小麗聰明，但不用功。

(3)小麗不但聰明，而且用功。

(4)

小麗不是不聰明，是不用功。

例2、將下面命題符號(hào)化。(5)小剛與小麗都是三好學(xué)生。

(6)小剛與王麗是同學(xué)。

：小麗用功。：小麗聰明，R:小剛是三好學(xué)生，S:小麗是三好學(xué)生。

T:小剛與王麗是同學(xué)解：設(shè)2023/7/23真值表

3、“或者”稱的析取式，記作。000101101111例1.5，今晚我在家看電視或聽音樂。：今晚我在家看電視，：今晚我在家聽音樂解：命題符號(hào)化為：

2023/7/23注意：①“∨”的邏輯關(guān)系是明確的。即P、Q二命題中至少有一個(gè)為真則析取式為真。因而，自然語言中常用的聯(lián)結(jié)詞諸如：“或者……或者……”、“可能……可能……”等，都可以符號(hào)化為“∨”。②自然語言中的“或”是具有二義性的，用“或”聯(lián)結(jié)的命題有時(shí)是具有相容性，而有時(shí)又具有排斥性，聯(lián)結(jié)詞“”在一個(gè)語句中表示“或”的含義，是相容或，它允許所聯(lián)結(jié)的兩個(gè)命題同時(shí)為真.

2023/7/23例3、將下列命題符號(hào)化⑴張曉靜愛唱歌或愛聽音樂；解：P：張曉靜愛唱歌；Q:張曉靜愛聽音樂符號(hào)化為P∨Q(2)張曉靜是江西人或安徽人；解：R：張曉靜是江西人；S:張曉靜是安徽人可符號(hào)化為(R∧￢S)∨(S∧￢R)(3)張曉靜20多歲或30來歲.解：這里的或是一個(gè)模糊的數(shù)據(jù)。

2023/7/23真值表：

4、“如果那么”稱的蘊(yùn)涵式，記作其中為前件，為后件。0001101011112023/7/23注意：①P→Q的邏輯關(guān)系是：Q是P的必要條件。在自然語言中，特別是在數(shù)學(xué)語言中，Q是P的必要條件還有許多不同的敘述方式，如：“P僅當(dāng)Q（僅當(dāng)Q，則P）”、“只有Q才P”、“只要P就Q”、“除非Q，否則非P（非P，除非Q）”等，均可符號(hào)化成P→Q的形式。②數(shù)理邏輯中的聯(lián)結(jié)詞是對(duì)日常語言中的聯(lián)結(jié)詞的一種邏輯抽象，自然語言中聯(lián)結(jié)詞所聯(lián)結(jié)的句子之間是有一定內(nèi)在聯(lián)系的，但在數(shù)理邏輯中，聯(lián)結(jié)詞所聯(lián)結(jié)的命題可以毫無關(guān)系。2023/7/23(1)如果天下雨，那么我在室內(nèi)活動(dòng)。(2)只要天下雨，我就在室內(nèi)活動(dòng)。(3)因?yàn)樘煜掠?，所以我在室?nèi)活動(dòng)。(4)除非天下雨，否則我不在室內(nèi)活動(dòng)。(5)如果天不下雨，我就不在室內(nèi)活動(dòng)。例、：天下雨，：我在室內(nèi)活動(dòng)。(6)僅當(dāng)天下雨，我才在室內(nèi)活動(dòng)。2023/7/23真值表：

5、“當(dāng)且僅當(dāng)”稱的等價(jià)式，記作。是的充要條件，也是的充要條件。0001101011012023/7/23解：例1.16、春天到了，燕子南飛。2023/7/236、邏輯聯(lián)結(jié)詞與自然語言中聯(lián)結(jié)詞的關(guān)系。

否定——不是，沒有，非，不。

合取——并且，同時(shí)，和，既…又…，不但…而且…，雖然…但是…。

析取——或者，或許，可能。

蘊(yùn)涵——若…則…，假如…那么…，既然…那就…，倘若…就…。

等價(jià)——當(dāng)且僅當(dāng)，充分必要，相同，一樣。

2023/7/237、運(yùn)算順序

例如：邏輯聯(lián)結(jié)詞也稱邏輯運(yùn)算符，以上五種最基本的聯(lián)結(jié)詞組成了一個(gè)集合，稱為一個(gè)聯(lián)結(jié)詞集。規(guī)定優(yōu)先級(jí)的順序?yàn)?，若有括?hào)時(shí)，先進(jìn)行括號(hào)內(nèi)運(yùn)算。

設(shè)P真值為1，Q真值為0，R真值為12023/7/23三、命題符號(hào)化。

步驟：(1)找出各簡(jiǎn)單命題，分別符號(hào)化。

(2)找出各聯(lián)結(jié)詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來。2023/7/23例、將下列命題符號(hào)化。

(1)小王是游泳冠軍或百米賽跑冠軍。

(2)小王現(xiàn)在在宿舍或在圖書館。

：小王是游泳冠軍，：小王是百米賽跑冠軍。

設(shè)原語句化為。：小王現(xiàn)在在宿舍，

：小王現(xiàn)在在圖書館。

設(shè)原語句化為2023/7/23例6、將下列命題符號(hào)化。

(3)選小王或小李中的一人當(dāng)班長(zhǎng)。

(4)如果我上街，我就去書店看看，除非我很累。

：選小王當(dāng)班長(zhǎng)，

：選小李當(dāng)班長(zhǎng)。

設(shè)原語句化為。

：我上街，：我很累。

：我去書店看看，設(shè))。原語句化為(或2023/7/23例7、P：北京比天津人口多，

Q：2+2=4R：烏鴉是白色的。求下列復(fù)合命題的真值。解：P,Q,R的真值分別為1，1，0，所以（1）的真值為1，（2）的真值為1，（3）的真值為0。2023/7/23習(xí)題解析1、指出下列語句哪些是命題，哪些不是命題，如果是命題指出真值a)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)系的一門必修課b)Π>2嗎？c)明天我去看電影d)請(qǐng)勿隨地吐痰！e)不存在最大質(zhì)數(shù)2023/7/23f)如果我掌握了英語，法語，那么學(xué)習(xí)其他歐洲的語言就容易多了g)9+5<12h)x<3i)月球上有水2023/7/232、用P表示命題“天下雪”，Q表示命題“我將去鎮(zhèn)上”，R表示命題“我有時(shí)間”。以符號(hào)形式寫出下列命題:

(a)如果天不下雪和我有時(shí)間,那么我將去鎮(zhèn)上.

(b)我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間.

(c)天不下雪

(d)天下雪,那么我不去鎮(zhèn)上

2023/7/23第1.2節(jié)

命題公式及真值表

2023/7/23內(nèi)容：命題公式，24組重要等值式，命題公式的類型重點(diǎn)：(1)掌握命題公式的定義及公式的真值表。

(2)掌握兩公式等值的定義；掌握24個(gè)重要(3)掌握重言式和矛盾式的定義及使用真值表進(jìn)行判斷。

等值式，并能利用其進(jìn)行等值演算。2023/7/23一、命題公式

1、命題常元、命題變?cè)}常元：簡(jiǎn)單命題。命題變?cè)赫嬷悼梢宰兓年愂鼍洌灿肞,Q,R,…等表示。命題變?cè)巡辉谑敲}。2023/7/232、命題公式(或合式公式)

定義1.1

通俗地說，命題公式是由命題變?cè)?，?lián)結(jié)詞，圓括號(hào)按一定邏輯關(guān)系聯(lián)結(jié)起來的字符串。

(1)單個(gè)命題變?cè)敲}公式,并稱為原子公式.(2)若A是命題公式,則￢A也稱為命題公式.(3)若A，B是命題公式,則(A∧B),

(A∨B),

(A→B),(AB)也是命題公式.(4)只有有限次地應(yīng)用(1)～(3)形成的符號(hào)串才是合式公式.2023/7/23

①

命題公式本身不是命題，沒有真值，只有對(duì)其命題變?cè)M(jìn)行賦值后，它才有真值。②公式中最外層的括號(hào)，及的括號(hào)可省略。

注意：2023/7/23例1、判斷以下字符串中哪些是命題公式。

(1)(2)(3)(4)(5)(6)解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。

2023/7/233、命題公式的解釋或賦值，如公式，110(按字典序)為的成假賦值，111，011，010……等是的成真賦值。個(gè)命題變項(xiàng)的命題公式，共有含組不同賦值。公式的解釋或賦值:定義1.2將公式A中的全部命題變?cè)髦付ㄒ粋€(gè)真值。2023/7/234、真值表(2)對(duì)應(yīng)每個(gè)賦值，計(jì)算公式的值。的真值表——指在所有賦值之下取值列成的表。

構(gòu)造的真值表步驟：(1)列出所有命題變?cè)乃匈x值(個(gè)，掌握)。一般從00…0到11…1

。2023/7/23例、給定命題公式如下，它們中哪些具有相同的真值表

(1)(2)(3)(4)(5)00011011（1）（2）（3）（4）（5）111111010000001111112023/7/23例、求下列命題公式的真值表。

(1)解：

000001110100111110010111011101112023/7/23二、兩命題公式間的等值關(guān)系1、定義：設(shè)為兩命題公式，在A和B中的所有命題變?cè)?。如果?duì)于顯然，當(dāng)且僅當(dāng)A和B真值表完全相同時(shí)，A和B是等值的公式。的每一種賦值，A的真值和B的真值都相同，則稱公式A等價(jià)于（或等值于）公式B。是出現(xiàn)2023/7/23(1)，

例1、判斷兩公式是否等值。2023/7/232、重要等值式4)、結(jié)合律3)、交換律1)、雙重否定律

2)、等冪律2023/7/232、重要等值式(續(xù))6)、德摩根律7)、吸收律5)、分配律2023/7/2310)、否定律8)、零律9)、同一律2、重要等值式(續(xù))2023/7/2311)、蘊(yùn)涵等值式

12)、等價(jià)等值式

13)、假言易位

14)、等價(jià)否定等值式

15)、歸謬論

2、重要等值式(續(xù))2023/7/233、等值演算（已知等值式推演出另外等值式的過程）。

例1.20、驗(yàn)證下列等值式。

(1)(2)(3)定義1.4（子公式）：設(shè)A是命題公式,A’

是A的一部分，A’

也是一個(gè)命題公式，則稱A’是A的子公式。定理1.1（置換規(guī)則）：設(shè)A’是命題公式A的子公式，B’是一命題公式,且A’

B’,將A中的A’用B’來置換,所得的是一個(gè)新公式,記為B,則AB。2023/7/23三、重言式、矛盾式，可滿足式例00011011（1）（2）111100002023/7/23三、重言式、矛盾式，可滿足式2、判定方法:真值表法1、定義

2023/7/23問題：給定n個(gè)命題變?cè)?按命題公式的形成規(guī)則,自然可以形成無窮多種形式各異的公式.那么,這些公式的真值表是否也有無窮多種不同的情況?個(gè)命題變項(xiàng)的命題公式，共有含組不同賦值。而任何公式在每種賦值下只能取兩個(gè)值：0或1，于是含n個(gè)命題變項(xiàng)的公式的真值表只有____種不同的情況，因而必有無窮多種公式具有相同的真值表.2023/7/23作業(yè):p242,3,42023/7/23第1.3節(jié)命題公式的范式和主范式NormalFormandDisjunctive&ConjunctiveNormalForm2023/7/23內(nèi)容：命題公式的范式。

重點(diǎn)：(1)掌握析取范式和合取范式的定義和求法步驟。

(2)掌握極小項(xiàng)，極大項(xiàng)的概念及下角標(biāo)與成真賦值、成假賦值的關(guān)系。(3)掌握主范式的求法。

2023/7/23一、析取范式與合取范式。

2、簡(jiǎn)單析取式，簡(jiǎn)單合取式。

簡(jiǎn)單析取式(simple

disjunctiveform):僅由有限個(gè)文字構(gòu)成的析取式。簡(jiǎn)單合取式(simple

conjunctiveform

):僅由有限個(gè)文字構(gòu)成的合取式。例如：等都是簡(jiǎn)單析取式。，，，例如：等都是簡(jiǎn)單合取式。

，，，1、文字(literal)：命題變?cè)捌浞穸ā?/p>

2023/7/23性質(zhì)定理：(1)一個(gè)文字既是簡(jiǎn)單析取式又是簡(jiǎn)單合取式。(2)一個(gè)簡(jiǎn)單析取式是重言式，當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定。(3)一個(gè)簡(jiǎn)單合取式是矛盾式，當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定。0011為A的成假賦值。2023/7/233、析取范式，合取范式DisjunctiveNormalForm、ConjunctiveNormalForm。

例如：

為析取范式，

為合取范式。

定義：由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱作析取范式。由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱作合取范式。2023/7/23范式性質(zhì)定理：(1)一個(gè)文字既是一析取范式又是一合取范式。

(2)一個(gè)析取范式為矛盾式，

當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式是矛盾式。

(3)一個(gè)合取范式為重言式，

當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式是重言式。

2023/7/233、析取范式，合取范式。

范式存在定理：任一命題公式都存在與之等值的析取范式和合取范式。2023/7/23證明：對(duì)于任一公式，可用下面的方法構(gòu)造出與其等值的范式：（1）利用等值式AB(A→B)∧(B→A）；

A→B

?A∨B

使公式中僅含聯(lián)結(jié)詞?

、∧、∨。（2）利用德·摩根律和雙重否定律

?(A∨B)

?A∧?B

?(A∧B)

?A∨

?B

??A

A

將否定符移至命題變項(xiàng)符前，并去掉多余的否定符?（3）利用分配律A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)

將公式化成析取范式或合取范式。2023/7/23求范式步驟：

(2)否定消去或內(nèi)移。

(3)利用分配律：利用對(duì)的分配律求析取范式，

對(duì)的分配律求合取范式。

(1)消去聯(lián)結(jié)詞

2023/7/23解：原式

消去

內(nèi)移

消去

上式即析取范式

例1、求公式的析取范式和合取范式。分配律

對(duì)(分配)2023/7/23解：原式

析取范式

析取范式（交換、吸收律）合取范式

原式合取范式（冪等律）

例1、求公式的析取范式和合取范式。

2023/7/23三、主范式(UniqueNormalForm)。

1、極小項(xiàng)，極大項(xiàng)。

(ExtremalSmallItem，ExtremalLargeItem)定義：設(shè)命題公式含這個(gè)命題變項(xiàng)，則和分別稱為極小項(xiàng)和極大項(xiàng)，其中為或。2023/7/23都是極小項(xiàng)，

都是極大項(xiàng)，

例如，對(duì)只含變項(xiàng)的命題公式中，但不是極小項(xiàng)。但不是極大項(xiàng)。2023/7/23

每個(gè)命題變項(xiàng)在極小項(xiàng)中以原形或否定形式出現(xiàn)且僅出現(xiàn)一次，因而n個(gè)命題變項(xiàng)可產(chǎn)生2n個(gè)不同的極小項(xiàng)，其中每個(gè)極小項(xiàng)都有且僅有一個(gè)成真賦值。若成真賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)i，就將所對(duì)應(yīng)極小項(xiàng)記為mi。

n個(gè)命題變項(xiàng)可產(chǎn)生2n個(gè)不同的極大項(xiàng)，其中每個(gè)極大項(xiàng)都有且僅有一個(gè)成假賦值。若成假賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為i，就將所對(duì)應(yīng)極大項(xiàng)記為M

i。2、極小項(xiàng)，極大項(xiàng)的表示極大項(xiàng)，極小項(xiàng)。下面分別討論，即個(gè)命題變項(xiàng)的2023/7/23極小項(xiàng)成真賦值(二進(jìn)制數(shù))000001010011100101110111對(duì)應(yīng)十進(jìn)制數(shù)01234567記法2023/7/23極大項(xiàng)成假賦值

(二進(jìn)制數(shù))000001010011100101110111對(duì)應(yīng)十進(jìn)制數(shù)01234567記法2023/7/233、極小項(xiàng)，極大項(xiàng)的關(guān)系2023/7/234、主析取范式，主合取范式。（Uniquedisjunctive/conjunctive

normalform）主析取范式——每個(gè)簡(jiǎn)單合取式都是極小項(xiàng)的析取范式。

主合取范式——每個(gè)簡(jiǎn)單析取式都是極大項(xiàng)的合取范式。

定理：任何命題公式的主析取范式、主合取范式都存在且都是唯一的。兩種求法，等值式法和真值表法。

2023/7/23步驟：

(3)消去重復(fù)的及永假項(xiàng)。如用p代替pp,mi代替mimi,

0代替矛盾律4.1、利用等值式法求命題公式的主析取范式。(1)求，的析取范式(2)利用

補(bǔ)充變?cè)?4)按角碼順序排序。2023/7/23解：由例1的析取范式為

例2、求公式的主析取范式。(吸收律)2023/7/23解：由例1的析取范式為

例2、求公式的主析取范式。2023/7/23真值表與范式（1）

若公式A中含n個(gè)命題變項(xiàng)，A的主析取范式含s（0s2n)個(gè)極小項(xiàng)，則A有s個(gè)成真賦值。它們是所含極小項(xiàng)角標(biāo)的二進(jìn)制表示，其余2n-s個(gè)賦值都是成假賦值。例如：在例2中成真賦值為010，100，101，110，111，成假賦值為000，001，0112023/7/23真值表與范式（2）

若公式A中含n個(gè)命題變項(xiàng)，A的主合取范式含s（0s2n)個(gè)極大項(xiàng)，則A有s個(gè)成假賦值。它們是所含極大項(xiàng)角標(biāo)的二進(jìn)制表示，其余2n-s個(gè)賦值都是成真賦值。例如：在例2中成假賦值為000，001，011；成真賦值為010，100，101，110，111，2023/7/23真值表與范式（3）

AB當(dāng)且僅當(dāng)A與B有相同的真值表，又當(dāng)且僅當(dāng)A與B有相同的主析取范式（主合取范式）。因而可以這樣說，真值表與主析取范式（主合取范式）是描述命題公式標(biāo)準(zhǔn)形式的兩種不同的等價(jià)形式。因而可以互相確定。2023/7/23步驟：

(3)求每個(gè)成真賦值對(duì)應(yīng)的十進(jìn)制數(shù)，即極小項(xiàng)的角碼，將極小項(xiàng)按序析取即成。2.2、利用真值表求命題公式的主析取范式。(1)列出的真值表，(2)找出的所有成真賦值，2023/7/23解：(1)列真值表

例3、用真值表求的主析取范式。2023/7/23解：(2)的成真賦值有010，100，101，110，111(3)對(duì)應(yīng)的十進(jìn)制數(shù)為2，4，5，6，7所以的主析取范式為

例3、用真值表求的主析取范式。2023/7/23步驟：(3)消去重復(fù)的及永真項(xiàng)；

4.3、利用等值式法求命題公式的主合取范式。

(1)求；的合取范式(2)利用

補(bǔ)充變?cè)?4)按角碼順序排序。2023/7/23解：由例1，合取范式

例4、求公式的主合取范式。

2023/7/23解：由例1，例4、求公式的主合取范式。2023/7/232.4、利用真值表求命題公式的主合取范式。

步驟：

(3)求每個(gè)成假賦值對(duì)應(yīng)的十進(jìn)制數(shù)，即極大項(xiàng)的角碼，將極大項(xiàng)按序合取即成。(1)列出的真值表，(2)找出的所有成假賦值，2023/7/23例5、用真值表求的主合取范式。解：(1)由例3知真值表，的2023/7/23(3)對(duì)應(yīng)的十進(jìn)制數(shù)為0，1，3。

例5、用真值表求的主合取范式。解：(2)的成假賦值有000，001，011，A=M0M1M3所以的主合取范式：思考：命題公式間有什么聯(lián)系，能否通過其中一個(gè)求另一個(gè)？(觀察例3，例5)的主合取范式，主析取范式2023/7/23由例3、例5知：A

M0M1M32023/7/232.5、已知命題公式的主析取范式(主合取范式