離散數(shù)學(xué)PPT完整全套教學(xué)課件

2023/7/41第1章1命題及聯(lián)結(jié)詞第1章2命題公式翻譯真值表第1章3真值表與等價公式第1章4蘊(yùn)含與范式第1章5范式第1章6命題邏輯的推理第2章1謂詞與量詞第2章2謂詞翻譯第2章3謂詞等價式第2章4謂詞推理第3章1集合第4章1笛卡爾積與關(guān)系第4章2關(guān)系的性質(zhì)關(guān)系的復(fù)合第4章3關(guān)系的運(yùn)算第4章4等價關(guān)系與等價類第4章5相容關(guān)系第4章6偏序關(guān)系第4章7函數(shù)的概念第4章8函數(shù)運(yùn)算第4章9基數(shù)第5章1代數(shù)系統(tǒng)的概念第5章2半群第5章3群與子群第5章4阿貝爾群循環(huán)群置換群第5章5陪集拉格朗日定理第6章1圖的基本概念第6章2圖中的路與圖的連通性第6章3圖的矩陣表示第7章1歐拉圖第7章2漢密爾頓圖第7章3二分圖第7章4平面圖第7章5圖的著色第8章1無向樹與生成樹第8章2根數(shù)及其應(yīng)用2023/7/421931年Godel不完全性定理的提出，以及遞歸函數(shù)可計算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺電子計算機(jī)問世。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書也只研究這兩個演算。數(shù)理邏輯(MathematicalLogic)2023/7/43判斷命題的兩個步驟：是否為陳述句；是否有確定的、唯一的真值。例判斷下列句子是否為命題。(1)今天天氣多好啊！(2)請你關(guān)上門.(3)Howdoyoudo?

(4)3+3=8.

(5)吸煙有害健康。T感嘆句，不是命題祈使句，不是命題疑問句，不是命題F1.1

命題及其表示方法2023/7/44(6)太陽從西方升起。(7)x+3>9(8)1+101=110(9)今天是星期三當(dāng)且僅當(dāng)2+2=4。(10)如果太陽從西方升起，那么2是奇數(shù)。

(11)今年國慶是晴天。

(12)明天我去看電影。(13)宇宙中有外星人。(14)我正在說謊。不是命題二進(jìn)制中為真，十進(jìn)制中為假FT是命題，其真值到國慶就知道是命題，客觀上能判斷真假悖論，不是命題F是命題，客觀上能判斷真假1.1

命題及其表示方法2023/7/45說明只有具有確定真值的陳述句才是命題。一切沒有判斷內(nèi)容的句子，無所謂是非的句子，如感嘆句、祁使句、疑問句等都不是命題。因?yàn)槊}只有兩種真值，所以“命題邏輯”又稱“二值邏輯”?！熬哂写_定真值”是指客觀上的具有，與我們是否知道它的真值是兩回事。如上例中的(11)(12)(13).1.1

命題及其表示方法2023/7/46二、命題的表示方法在本書中，用大寫英文字母A,B,…,P,Q或帶下標(biāo)的字母P1,P2,P3,…,或數(shù)字(1),[2],…,等表示命題，稱之為命題標(biāo)識符(PropositionIdentifier)。例如P：這節(jié)課是數(shù)學(xué)課

Q：5是負(fù)數(shù)。

P3：明天天氣晴。

(2)：太陽從西方升起。皆為符號化的命題，其真值依次為1、0、1或0、0。1.1

命題及其表示方法2023/7/47命題常量(PropositionConstant)：表示確定命題的命題標(biāo)識符。命題標(biāo)識符又有命題常量、命題變元和原子變元之分。命題變元(PropositionValiable)

：命題標(biāo)識符如僅是表示任意命題的位置標(biāo)志，就稱為命題變元。原子變元(AtomicValiable)：當(dāng)命題變元表示原子命題時，該變元稱為原子變元。1.1

命題及其表示方法2023/7/48注意：一個符號(如P)，它表示的是命題常量還是命題變元，一般由上下文來確定。命題變元可以表示任意命題，它不能確定真值，故命題變元不是命題。這與“變數(shù)x不是數(shù)”是一樣的道理。1.1

命題及其表示方法2023/7/49簡單命題(SimpleProposition)/原子命題(AtomicProposition)/本原命題(PrimitiveProposition)：不能分解為更簡單的陳述語句的命題(如上例中的命題)。三、命題的分類復(fù)合命題(CompoundProposition)

：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。1.1

命題及其表示方法2023/7/410四、小結(jié)本節(jié)主要要求大家掌握命題的定義怎樣判定一句話到底是不是命題命題的分類真值原子命題、復(fù)合命題1.1

命題及其表示方法2023/7/411離散數(shù)學(xué)

(DiscreteMathematics)2023/7/4121.2命題聯(lián)結(jié)詞(LogicalConnectives)否定聯(lián)結(jié)詞(Negation)合取聯(lián)結(jié)詞(Conjunction)析取聯(lián)結(jié)詞(Disjunction)條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Conditional)雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞Biconditional)小結(jié)2023/7/413一、否定聯(lián)結(jié)詞(Negation)?在命題邏輯中，主要研究的是復(fù)合命題，而復(fù)合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成，聯(lián)結(jié)詞是復(fù)合命題的重要組成部分。定義1-2.1

設(shè)P為一命題，P的否定是一個新的復(fù)合命題，稱為P的否定式，記作“?P”，讀作“非P”，符號“?”

稱為否定聯(lián)結(jié)詞。?P為真當(dāng)且僅當(dāng)P為假.1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/414聯(lián)結(jié)詞“?”的定義真值表P?P0110“?”屬于一元運(yùn)算符.1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/415例1P：西安是一個城市.Q：3是偶數(shù).則

?P：西安不是一個城市.

?Q：3不是偶數(shù).例2P：西安處處清潔.?P的含義是什么？

A:西安處處不清潔

B:西安不處處清潔1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/416例3

Q：在座的都是男同學(xué).?Q的含義是什么？

A:在座的各位不都是男同學(xué)。

B:在座的各位都不是男同學(xué)。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/417二、合取聯(lián)結(jié)詞(Conjunction)PQP∧Q

000010100111定義1-2.2

設(shè)P,Q為命題，復(fù)合命題“P并且Q”(或“P與Q”)稱為P與Q的合取式，記作P∧Q，符號“∧”稱為合取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q同時為真時P∧Q為真。聯(lián)結(jié)詞“∧”的定義真值表1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/418“∧”屬于二元(binary)運(yùn)算符.合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時，運(yùn)算結(jié)果才為真，否則為假。自然語言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…”、“…和…”、“…與…”等都可以符號化為∧。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/41919例3

將下列命題符號化.(1)張三既聰明又用功.

(2)張三雖然聰明，但不用功.(3)張三不但聰明，而且用功.(4)張三不是不聰明，而是不用功.不要見到“與”或“和”就使用聯(lián)結(jié)詞∧。例如:“我與你是兄弟”是合取式嗎？

A:是B：不是，是原子命題

解解設(shè)P：張三聰明。Q：張三用功。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)則(2)P∧?Q(3)P∧Q(4)?(?P)∧?Q(1)P∧Q2023/7/420“∧”與自然語言中“與”“和”的不同之處：1.2

命題聯(lián)結(jié)詞(LogicalConnectives)(2)自然語言中有時在各種不同意義上使用聯(lián)結(jié)詞“與”，“和”，不能一概用表示，有時是原子命題。2023/7/421三、析取聯(lián)結(jié)詞(Disjunction)∨PQP∨Q000011101111定義1-2.3

設(shè)P,Q為命題，復(fù)合命題“P或Q”稱為P與Q的析取式，記作P∨Q，符號∨稱為析取聯(lián)結(jié)詞.P∨Q為真當(dāng)且僅當(dāng)P與Q中至少有一個為真.聯(lián)結(jié)詞“∨”的定義真值表1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/422“∨”屬于二元(binary)運(yùn)算符.析取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為假時，運(yùn)算結(jié)果才為假，否則為真。由析取聯(lián)結(jié)詞的定義可以看出，“∨”與漢語中的聯(lián)結(jié)詞“或”意義相近，但又不完全相同。在現(xiàn)代漢語中，聯(lián)結(jié)詞的“或”實(shí)際上有“可兼或”和“排斥或”之分。考察下面命題：(1)小王愛打球或愛跑步。設(shè)P：小王愛打球。Q：小王愛跑步。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)（可兼或）則上述命題可符號化為：P∨Q2023/7/423(4)人固有一死，或重于泰山或輕于鴻毛.(2)張三學(xué)過英語或法語。設(shè)P：張三學(xué)過英語。Q：張三學(xué)過法語(3)派小王或小李中的一人去開會。設(shè)P：派小王去開會。Q：派小李去開會。(5)ab=0,即a=0或b=0.由此可見,“P∨Q”表示的是“可兼或”.則上述命題可符號化為：P∨Q則上述命題可符號化為：(P∧?Q)∨(?P∧Q)1.2

命題聯(lián)結(jié)詞(LogicalConnectives)（可兼或）（排斥或）（排斥或）（可兼或）2023/7/424注意：當(dāng)P和Q客觀上不能同時發(fā)生時，“P或Q”可以符號化為“P∨Q”?！啊拧迸c自然語言中“或”的不同之處：例如：小王現(xiàn)在在宿舍或在圖書館。設(shè)P：小王現(xiàn)在在宿舍。Q：小王現(xiàn)在在圖書館。則上述命題可符號化為：P∨Q。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)

1、不能看到或就寫成析取

2、或有時可以表示“約數(shù)”，要注意區(qū)分“小王或小李有且僅有一個是大學(xué)生”A:可兼或B:排斥或2023/7/425四、條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Conditional)→PQP→

Q001011100111定義1-2.4

設(shè)P,Q為命題，復(fù)合命題“如果P那么Q(若P則Q)”稱為P與Q的條件命題，記作PQ.PQ為假當(dāng)且僅當(dāng)P為真且Q為假。稱符號“”為條件聯(lián)結(jié)詞。并稱P為前件，Q為后件.聯(lián)結(jié)詞“”的定義真值表1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/426

如果天下雨，那么地面濕。設(shè)P：天下雨。Q：地面濕。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)PQP→Q0001101111012023/7/427PQ表示的基本邏輯關(guān)系是：Q是P的必要條件或P是Q的充分條件.因此復(fù)合命題“只要P就Q”、“因?yàn)镻，所以Q”、“僅當(dāng)Q則P”、“當(dāng)P則Q”、“只有Q才P”等都可以符號化為PQ的形式?！啊睂儆诙?binary)運(yùn)算符。例5

將下列命題符號化。(1)天不下雨，則草木枯黃。設(shè)P：天下雨。Q：草木枯黃。則原命題可表示為：?P→Q。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/428(2)如果小明學(xué)日語，小華學(xué)英語，則小芳學(xué)德語。

設(shè)P：小明學(xué)日語Q：小華學(xué)英語R：小芳學(xué)德語(3)只要不下雨，我就騎自行車上班。(4)只有不下雨，我才騎自行車上班。設(shè)P：天下雨。Q：我騎自行車上班。設(shè)P：天下雨。Q：我騎自行車上班。則原命題可表示為：(P∧Q)→R則原命題可表示為：?P→Q則原命題可表示為：Q→?P。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/429例6

設(shè)P：2+2=4

Q：太陽從東方升起R：太陽從西方升起符號化下列命題，并判斷命題的真值：(1)如果2+2=4，則太陽從東方升起。(2)如果2+2=4，則太陽從西方升起。(3)如果2+2≠4，則太陽從東方升起。(4)如果2+2≠4，則太陽從西方升起。解(1)P→Q，T1.2

命題聯(lián)結(jié)詞(LogicalConnectives)(2)P→R，F(xiàn)(3)?P→Q，T(4)?P→R，T2023/7/430注意:與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！在數(shù)學(xué)中，“若P則Q”往往表示前件P為真，則后件Q為真的推理關(guān)系.但數(shù)理邏輯中，當(dāng)前件P為假時，P→Q的真值為真。1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/431五、雙條件聯(lián)結(jié)詞(等值聯(lián)結(jié)詞Biconditional)PQPQ001010100111定義1-2.5設(shè)P,Q為命題，復(fù)合命題“P當(dāng)且僅當(dāng)Q”稱為P與Q的雙條件命題，記作PiffQ或PQ，符號稱為雙條件（等值）聯(lián)結(jié)詞。PQ為真當(dāng)且僅當(dāng)P與Q的真值相同。聯(lián)結(jié)詞“”的定義真值表1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/432“P當(dāng)且僅當(dāng)Q”可譯為說明:1.2

命題聯(lián)結(jié)詞(LogicalConnectives)PQ“”屬于二元(binary)運(yùn)算符。雙條件命題PQ所表達(dá)的邏輯關(guān)系是，P與Q互為充分必要條件，相當(dāng)于(PQ)∧(QP).只要P與Q的真值同為1或同為0，PQ的真值就為1，否則PQ的真值為0。雙條件聯(lián)結(jié)詞連接的兩個命題之間可以沒有因果關(guān)系。2023/7/433例6

分析下列命題的真值(P:2+2=4Q:3是奇數(shù))(1)2+2=4當(dāng)且僅當(dāng)3是奇數(shù).(2)2+2=4當(dāng)且僅當(dāng)3不是奇數(shù).(3)2+2≠4當(dāng)且僅當(dāng)3是奇數(shù).(4)2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù).P?Q，約定:運(yùn)算次序優(yōu)先級：?，，，→，.相同的運(yùn)算符按從左至右次序計算，否則要加上括號。最外層圓括號可省去。PQ，?PQ，?P?Q，1.2

命題聯(lián)結(jié)詞(LogicalConnectives)TFFT2023/7/434六、小結(jié)本節(jié)介紹了五種聯(lián)結(jié)詞(?，，，→，)。重點(diǎn)是理解和掌握五種聯(lián)結(jié)詞的內(nèi)涵及它們與自然語言中相應(yīng)聯(lián)結(jié)詞的不同之處.1.2

命題聯(lián)結(jié)詞(LogicalConnectives)2023/7/435離散數(shù)學(xué)

(DiscreteMathematics)命題公式與翻譯2023/7/4361.3命題公式與翻譯命題公式的定義復(fù)合命題的符號化(翻譯)小結(jié)2023/7/437一、命題公式(PropositionFormula)的定義定義1-3.1

單個命題變元和命題常量稱為原子公式。定義1-3.2

命題演算的合式公式(wff：Well-formedformula)，規(guī)定為：(1)原子公式是合式公式。(2)若A是合式公式，則(?A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。(4)當(dāng)且僅當(dāng)有限次地應(yīng)用(1)~(3)所得到的包含原子公式、聯(lián)結(jié)詞和括號的符號串是合式公式。1.3命題公式與翻譯2023/7/438命題演算的合式公式是由命題變元、命題常量、聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串，是以遞歸的形式來定義的合式公式也稱為命題公式，并簡稱為公式。命題公式一般不是命題，僅當(dāng)公式中的命題變元用確定的命題代入時，才得到一個命題。其真值依賴于代換變元的那些命題的真值。1.3命題公式與翻譯2023/7/4391.3命題公式與翻譯約定：運(yùn)算次序優(yōu)先級：?，，，→，.相同的運(yùn)算符按從左至右次序計算，否則要加上括號。最外層圓括號可省去。2023/7/440例1

指出(P→(PQ))是否是命題公式，如果是，則具體說明。解①P是wff由(1)②Q是wff由(1)③PQ是wff由(3)④(P→(PQ))由(3)例2(PQ),(R∧S)∨?Q,P，?P等均為合式公式，而PQ∨S,(PW)Q)等不是合式公式。1.3命題公式與翻譯2023/7/441二、復(fù)合命題的符號化(翻譯)有了命題演算的合式公式的概念，我們可以把自然語言中的有些語句(復(fù)合命題)，翻譯成數(shù)理邏輯中的符號形式?；静襟E如下：(1)分析出各原子命題，將它們符號化；(2)使用合適的聯(lián)結(jié)詞，把簡單命題逐個的聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示.1.3命題公式與翻譯2023/7/442例3

符號化下列命題：(1)盡管他有病，但他仍堅(jiān)持工作。設(shè)P：他有病。Q：他堅(jiān)持工作。則該命題可以表示為：P∧Q(2)說數(shù)理邏輯枯燥無味或毫無價值，那是不對的。設(shè)P：數(shù)理邏輯枯燥無味。Q：數(shù)理邏輯毫無價值。則該命題可以表示為：?(P∨Q)(3)張三與李四組成一個學(xué)習(xí)小組。設(shè)P：張三與李四組成一個學(xué)習(xí)小組。則該命題可以表示為：P1.3命題公式與翻譯2023/7/443(4)假如上午不下雨，我去看電影，否則就在家里讀書或看報。設(shè)P：上午下雨。Q：我去看電影。R：我在家讀書。S：我在家看報。則該命題可以表示為：(?PQ)∧(P(R∨S))(5)除非你通知我，否則我不開會。設(shè)P：你通知我。Q：我開會。則該命題可以表示為：

A:?P?Q

B:PQ

1.3命題公式與翻譯除非=如果不2023/7/444(6)除非你努力，否則你將失敗。設(shè)P：你努力。Q：你將失敗。則該命題可以表示為：A:

P?Q

B:

?PQ1.3命題公式與翻譯除非=如果不2023/7/445(7)一個人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”；后來他改說：“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴査昂笾鲝埖牟町愒谑裁吹胤?，試以命題形式進(jìn)行分析。設(shè)P：它占據(jù)空間。Q：它有質(zhì)量。R：它不斷變化。W：它是物質(zhì)。則第一句話可表示為：(P∧Q∧R)W第一句話可表示為：(P∧QW)∧(WR)(8)只要我還有一口氣，我就要戰(zhàn)斗。設(shè)P：我有一口氣。Q：我要戰(zhàn)斗。

則該命題可以表示為：PQ1.3命題公式與翻譯2023/7/446(9)只要功夫深，鐵杵磨成針。設(shè)P：功夫深。Q：鐵杵磨成針。則該命題可以表示為：PQ(10)只有睡覺才能恢復(fù)體力。設(shè)P：睡覺。Q：恢復(fù)體力。則該命題可以表示為：QP(11)小王晚上回家，除非下大雨。設(shè)P：小王晚上回家。Q：下大雨。則該命題可以表示為：?QP1.3命題公式與翻譯(12)若要人不知，除非己莫為。設(shè)P：人知。Q：己為。則該命題可以表示為：QP2023/7/447(13)除非天氣好，我才騎自行車上班。設(shè)P：天氣好。Q：我騎自行車上班。則該命題可以表示為：?P?Q(14)除非你陪我或代我叫輛車子，否則我不出去。設(shè)P：你陪我。Q：你代我叫輛車。R：我出去。則該命題可以表示為：?(P∨Q)?R1.3命題公式與翻譯(15)天黑了，我得回家了。設(shè)P：天黑了。Q：我回家。則該命題可以表示為：PQ2023/7/448(16)北京到上海的14次列車是下午5點(diǎn)半開或6點(diǎn)開。設(shè)P：北京到上海的14次列車是下午5點(diǎn)半開。

Q：北京到上海的14次列車是下午6點(diǎn)開。1.3命題公式與翻譯PQP☆Q0001101101101001P☆Q2023/7/449(17)張三與李四有且僅有一人是大學(xué)生。設(shè)P：張三是大學(xué)生。Q：李四是大學(xué)生。則該命題可以表示為：?(PQ)(18)張三正在游泳或正在睡覺。設(shè)P：張三正在游泳。Q：張三正在睡覺。則該命題可以表示為：?(PQ)(19)天黑了，我得回家了。設(shè)P：天黑了。Q：我回家。則該命題可以表示為：PQ1.3命題公式與翻譯2023/7/450三、小結(jié)本節(jié)介了命題公式的概念及復(fù)合命題的符號化。重點(diǎn)是理解命題公式的遞歸定義，掌握復(fù)合命題的符號化方法.翻譯的步驟：找出原子命題，分析邏輯關(guān)系，找出合適的聯(lián)結(jié)詞，注意括號。重點(diǎn)是條件式的翻譯只要，只有，除非，每當(dāng)，僅當(dāng)，當(dāng)且僅當(dāng)1.3命題公式與翻譯2023/7/451離散數(shù)學(xué)

(DiscreteMathematics)2023/7/4PQ000110110110101110001.4真值表與等價公式復(fù)習(xí)符號化命題：我們不能既劃船又跑步P：我們劃船Q：我們跑步翻譯

A:

B:

C:2023/7/4PQP☆Q000110111.4真值表與等價公式復(fù)習(xí)符號化命題：或者你沒給我寫信或者信丟了P：你給我寫信了Q：信丟了A:

B:

10012023/7/4541.4真值表與等價公式真值表(TruthTable)等價公式(PropositionalEquivalences)小結(jié)2023/7/455一、真值表定義1-4.1

設(shè)P1,P2,…,Pn是出現(xiàn)在公式A中的全部的命題變元，給P1,P2,…,Pn

各指定一個真值，稱為對A的一個真值指派或賦值(Assigment)或解釋。若指定的一組值使A的真值為真(假)，稱這組值為A的成真(假)指派.前面在定義聯(lián)結(jié)詞時，曾經(jīng)使用過真值表，本節(jié)給出真值表的定義。1.4真值表與等價公式2023/7/456比如:對公式(PQ)∧R，賦值011(即令P=0，Q=1，R=1)為(PQ)∧R的成真賦值；另一組賦值010為(PQ)∧R的成假賦值；還有000，001，111……考慮：含有n個命題變元的公式共有多少組不同的賦值？定義1-4.2

在命題公式A中，對于命題變元的每一種可能的真值指派和由它們所確定的命題公式A的真值列成表，稱做命題公式A的真值表。1.4真值表與等價公式2023/7/457對公式A構(gòu)造真值表的具體步驟為：(1)找出公式中所有命題變元P1,P2,…,Pn。

(2)按從小到大的順序列出命題變元P1,P2,…,Pn的全部2n組賦值。(3)對應(yīng)各組賦值計算出公式A的真值，并將其列在對應(yīng)賦值的后面。1.4真值表與等價公式2023/7/458PQPQ?(PQ)?P?Q?(PQ)(?P?Q)00011011例1給出?(PQ)(?P?Q)的真值表。1.4真值表與等價公式00011110111011112023/7/459PQRPQ(PQ)∧R000001010011100101110111例2構(gòu)造公式(PQ)∧R的真值表。1.4真值表與等價公式11110011010100012023/7/4601.4真值表與等價公式練習(xí)1構(gòu)造公式(PQ)(?Q?P)的真值表。練習(xí)2構(gòu)造公式?(PQ)∧Q的真值表。2023/7/461練習(xí)1構(gòu)造公式(PQ)(?Q?P)的真值表。PQ?P?QPQ?Q?P(PQ)(?Q?P)000110111.4真值表與等價公式110010101101110111112023/7/462PQ

P

Q?(P

Q)?(P

Q)∧Q00011011練習(xí)2構(gòu)造公式?(PQ)∧Q的真值表。1.4真值表與等價公式1101001000002023/7/463給定n個命題變元，按合式公式的形成規(guī)則可以形成無數(shù)多個命題公式,但這些無窮盡的命題公式中，有些具有相同的真值表?？紤]：由n個命題變元能生成多少種真值(表)不同的命題公式？二、等價公式1.4真值表與等價公式PQA

000110112023/7/464定義1-4.3

給定兩個命題公式A和B，設(shè)P1,P2,…,Pn為出現(xiàn)于A和B中的所有原子變元，若給P1,P2,…,Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等，記作AB。“”不是邏輯聯(lián)結(jié)詞.命題公式之間的邏輯相等關(guān)系具有：

(1)自反性：AA；

(2)對稱性：若AB，則BA；

(3)傳遞性：若AB且BC，則AC。1.4真值表與等價公式2023/7/465PQPQQ→PP→Q(P→Q)(Q→P)00011011證明公式等價的方法：真值表法等值演算法1、真值表法

例3

證明:PQ(P→Q)(Q→P)1.4真值表與等價公式10011011110110012023/7/466例4

判斷公式P(QR)、(P∧Q)R是否等價。PQRP∧QQRP(QR)(P

∧

Q)R000001010011100101110111由真值表可知，兩個公式為等價式。1.4真值表與等價公式000000111111110111011101111111012023/7/4672、等值演算法(EquivalentCaculation)命題定律即常見的等價式：1.4真值表與等價公式2023/7/4682、等值演算法(EquivalentCaculation)重要的等價式(補(bǔ)充)：14.雙條件否定等價式：PQ?P?Q15.歸謬律：(PQ)(P?Q)?P1.4真值表與等價公式PQPQ?P?Q?P?Q0011110101001000101110012023/7/469置換/替換規(guī)則(RuleofReplacement)：等值演算中使用的一條重要規(guī)則。定義1-4.4(子公式)如果X是wffA的一部分，且X本身也是wff，則稱X是A的子公式(Subformula)。例如，P(PQ)為Q(P(PQ))的子公式。1.4真值表與等價公式2023/7/470定理1-4.1(置換定理Axiomofreplacement)

設(shè)X是wffA的子wff，若XY，則若將A中的X用Y來置換，所得公式B與A等價，即AB。證：因?yàn)閷ψ冊娜我恢概?，X與Y真值相同，所以Y取代X后，公式B與公式A對變元的任一指派真值也相同，所以AB?！鯘M足定理1-4.1條件的置換稱為等價置換(或等價代換).定義1-4.5(等值演算)

根據(jù)已知的等價公式，推演出另外一些等價公式的過程稱為等值演算.1.4真值表與等價公式2023/7/471例6

證明(P?Q)Q

PQ例5證明Q→(P(PQ))Q→P證Q→(P(PQ))Q→P(吸收律)證

(P?Q)Q(PQ)(?QQ)(PQ)TPQ1.4真值表與等價公式2023/7/472例7證明（P→Q）→（QR）

PQR證(P→Q)→(QR)

(?PQ)→(QR)?(?PQ)(QR)(P?Q)(QR)

(PQR)(?QQR)

PQR1.4真值表與等價公式2023/7/473例8驗(yàn)證P(QR)(P

∧

Q)R練習(xí)：(1)((PQ)∧(PR))P(Q

∧R)(2)(P∧?Q)∨(?P∧

Q)(P∨

Q)∧?(P∧

Q)證(P

∧

Q)R?(P

∧

Q)∨R?P

∨?Q

∨R?P

∨(?Q

∨R)?P

∨(QR))P(QR)1.4真值表與等價公式2023/7/474等值演算在計算機(jī)硬件設(shè)計中,在開關(guān)理論和電子元器件中都占有重要地位.三、小結(jié)

本節(jié)介紹了真值表、公式等價、等值演算和等價置換等概念，給出了常用的重要等價公式重點(diǎn)掌握用真值表法驗(yàn)證公式的等價性和等值演算法推演兩個公式等價。1.4真值表與等價公式2023/7/475離散數(shù)學(xué)

(DiscreteMathematics)2023/7/4761.5重言式與蘊(yùn)含式命題公式的分類重言式(Tautology)的性質(zhì)蘊(yùn)含式(Implication)小結(jié)2023/7/477命題公式的分類重言式(Tautology)/永真式矛盾式(Contradiction)/永假式(Absurdity)可滿足式(Satisfactory)僅可滿足式/偶然式(Contingency)1.5重言式與蘊(yùn)含式2023/7/478定義1.5.1

設(shè)A為任一命題公式，(1)若A在其各種賦值下的取值均為真，則稱A是重言式或永真式，記為T或1。(2)若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假式，記為F或0。(3)若A不是矛盾式則稱A為可滿足式。(4)既不是重言式，也不是矛盾式，稱為僅可滿足式或偶然式。1.5重言式與蘊(yùn)含式2023/7/479判別命題公式的類型的方法:真值表法等值演算法：將所給命題公式通過等值演算化為最簡單的形式,然后再進(jìn)行判別.(重言式)例1判別下列命題公式的類型.(1)Q∨?((?P∨Q)∧P)(2)(P∨?P)(Q∧?Q)∧R(3)(PQ)∧?P(矛盾式)(可滿足式)1.5重言式與蘊(yùn)含式2023/7/480重言式的性質(zhì)定理1.5.1

任何兩個重言式的合取或析取，仍然是一重言式.證明設(shè)A和B為兩個重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故A∧BT，A∨BT1.5重言式與蘊(yùn)含式2023/7/481定理1.5.2

一個重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。證明：由于重言式(矛盾式)的真值與對變元的賦值無關(guān)，故對同一變元以任何合式公式置換后，重言式(矛盾式)的真值仍永為T（F）。1.5重言式與蘊(yùn)含式2023/7/482定理1.5.3

A，B是兩個命題公式，AB的充要條件是AB為重言式。證明若AB為重言式，則AB永為T，即A，B的真值表相同，所以AB。反之，若AB，則A，B真值表相同，所以AB永為T，從而AB為重言式。1.5重言式與蘊(yùn)含式PQ001110111110001111112023/7/483蘊(yùn)含式(Implication)定義1.5.2

當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱“P蘊(yùn)含Q”，并記作PQ.設(shè)原命題為PQ，則逆換式：QP反換式：?P?Q逆反式：?Q?P1.5重言式與蘊(yùn)含式2023/7/484它們之間具有如下關(guān)系:PQ

?Q?PQP

?P?Q證明PQ的三種方法：真值表法：即列出PQ的真值表，觀察其是否為永真。直接證法：假定前件P是真，推出后件Q是真。間接證法：假定后件是假，推出前件是假，即證?Q?P。1.5重言式與蘊(yùn)含式PQ0010111001112023/7/485例1

證明?Q（P→Q）?P證法1：真值表法(略)證法2：若?Q(P→Q)為真，證法3：若?P為假，則P為真，再分二種情況：①若Q為真，則?Q為假，從而?Q(P→Q)為假；②若Q為假，則P→Q為假，從而?Q(P→Q)為假，根據(jù)①②，有?Q(P→Q)?P。1.5重言式與蘊(yùn)含式則?Q，P→Q為真，所以Q為假，P為假，所以?P為真。2023/7/486P21表1-5.2給出了14個蘊(yùn)含式。1.5重言式與蘊(yùn)含式1PQP化簡式2PQQ化簡式3PPQ附加式4?PPQ5QPQ6?(PQ)P7?(PQ)?Q2023/7/487P21表1-5.2給出了14個蘊(yùn)含式。1.5重言式與蘊(yùn)含式8P(PQ)Q假言推理9?Q(PQ)?P拒取式10?P(PQ)Q析取三段論11(PQ)(QR)PR假言三段論12(PQ)(PR)(QR)R二難推理13(PQ)(RS)(PR)(QS)14(PQ)(QR)PR等價三段論2023/7/488等價式與蘊(yùn)含式的關(guān)系：定理1.5.4

設(shè)P，Q為任意兩個命題公式，PQ的充要條件為PQ且QP.證若PQ，則PQ為永真式，因?yàn)镻Q（P→Q）（Q→P），所以P→Q，Q→P為永真式，從而PQ，QP.反之，若PQ，QP，則P→Q，Q→P為永真式，所以（P→Q）（Q→P）為永真式，從而PQ為永真式，即PQ.1.5重言式與蘊(yùn)含式2023/7/489蘊(yùn)含的性質(zhì)：設(shè)A，B，C為任意wff,(1)若AB，且A為永真式，則B必為永真式.(2)若AB，BC，則AC.(3)若AB，AC，則ABC.(4)若AB且CB，則ACB.1.5重言式與蘊(yùn)含式2023/7/490小結(jié)本節(jié)介紹了命題公式的分類，重言式、矛盾式與蘊(yùn)含式的概念及其性質(zhì)，等價式與蘊(yùn)涵式的關(guān)系。重點(diǎn)掌握：(1)用等值演算法判別命題公式的類型。(2)重言式、矛盾式與蘊(yùn)涵式的性質(zhì)。(3)等價式與蘊(yùn)涵式的關(guān)系。1.5重言式與蘊(yùn)含式2023/7/491離散數(shù)學(xué)

(DiscreteMathematics)2023/7/492復(fù)習(xí)1.5重言式與蘊(yùn)含式判斷公式類型：Q∨?((?P∨Q)∧P)2023/7/493蘊(yùn)含式(Implication)定義1.5.2

當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱“P蘊(yùn)含Q”，并記作PQ.設(shè)原命題為PQ，則逆換式：QP反換式：?P?Q逆反式：?Q?P1.5重言式與蘊(yùn)含式2023/7/494它們之間具有如下關(guān)系:PQ

?Q?PQP

?P?Q證明PQ的三種方法：真值表法：即列出PQ的真值表，觀察其是否為永真。直接證法：假定前件P是真，推出后件Q是真。間接證法：假定后件是假，推出前件是假，即證?Q?P。1.5重言式與蘊(yùn)含式PQ0010111001112023/7/495例1

證明?Q（P→Q）?P證法1：真值表法(略)證法2：若?Q(P→Q)為真，證法3：若?P為假，則P為真，再分二種情況：①若Q為真，則?Q為假，從而?Q(P→Q)為假；②若Q為假，則P→Q為假，從而?Q(P→Q)為假，根據(jù)①②，有?Q(P→Q)?P。1.5重言式與蘊(yùn)含式則?Q，P→Q為真，所以Q為假，P為假，所以?P為真。2023/7/41.5重言式與蘊(yùn)含式2023/7/41.5重言式與蘊(yùn)含式2023/7/41.5重言式與蘊(yùn)含式2023/7/499等價式與蘊(yùn)含式的關(guān)系：定理1.5.4

設(shè)P，Q為任意兩個命題公式，PQ的充要條件為PQ且QP.證若PQ，則PQ為永真式，因?yàn)镻Q（P→Q）（Q→P），所以P→Q，Q→P為永真式，從而PQ，QP.反之，若PQ，QP，則P→Q，Q→P為永真式，所以（P→Q）（Q→P）為永真式，從而PQ為永真式，即PQ.1.5重言式與蘊(yùn)含式2023/7/4100蘊(yùn)含的性質(zhì)：設(shè)A，B，C為任意wff,(1)若AB，且A為永真式，則B必為永真式.(2)若AB，BC，則AC.(3)若AB，AC，則ABC.(4)若AB且CB，則ACB.1.5重言式與蘊(yùn)含式2023/7/4101小結(jié)本節(jié)介紹了命題公式的分類，重言式、矛盾式與蘊(yùn)含式的概念及其性質(zhì)，等價式與蘊(yùn)涵式的關(guān)系。重點(diǎn)掌握：(1)用等值演算法判別命題公式的類型。(2)重言式、矛盾式與蘊(yùn)涵式的性質(zhì)。(3)等價式與蘊(yùn)涵式的關(guān)系。1.5重言式與蘊(yùn)含式2023/7/4102離散數(shù)學(xué)

(DiscreteMathematics)2023/7/41031.6其它聯(lián)結(jié)詞不可兼析取(排斥或/異或)(Exclusiveor)與非聯(lián)結(jié)詞(Nand)或非聯(lián)結(jié)詞(Nor)條件否定聯(lián)結(jié)詞(Non-conditional)最小聯(lián)結(jié)詞組(Theminimalsetofconnectives)小結(jié)2023/7/4104在第二節(jié)(1.2)中我們定義了五種基本的聯(lián)結(jié)詞?，，，，，但在命題邏輯中，這些聯(lián)結(jié)詞還不能很廣泛地直接表達(dá)命題之間的聯(lián)系(例如,“P異或Q”只能間接地表示為(P?Q)(?PQ)，為此本節(jié)再給出邏輯設(shè)計中常用的另外四種聯(lián)結(jié)詞.1.6

其它聯(lián)結(jié)詞2023/7/4105一、不可兼析取/排斥或/異或(Exclusive-OR，)定義1.6.1

設(shè)P、Q為兩個命題，復(fù)合命題“P、Q之中恰有一個為真”稱為P與Q的不可兼析取，記作PQ，符號“”稱為異或聯(lián)結(jié)詞。PQ為真當(dāng)且僅當(dāng)P和Q的真值不同.PQP

Q0000111011101.6

其它聯(lián)結(jié)詞2023/7/4106例派小王或小李中的一人去開會。（排斥或）定義了聯(lián)結(jié)詞“”后，命題邏輯中的有些命題就可以符號化為非常簡捷的形式.設(shè)P：派小王去開會。Q：派小李去開會。則上述命題可符號化為：PQ1.6

其它聯(lián)結(jié)詞2023/7/4107“”屬于二元(binary)運(yùn)算符。1.6其它聯(lián)結(jié)詞聯(lián)結(jié)詞的性質(zhì)：設(shè)P，Q，R為命題公式，則有(1)PQQP(交換律)(2)(PQ)RP(QR)(結(jié)合律)(3)P∧(QR)(P∧Q)(P∧R)(分配律)(4)(PQ)(P∧?Q)∨(?P∧Q)(5)(PQ)

?(PQ)(6)PPF,FPP,TP

?P2023/7/4108定理1.6.1

設(shè)P，Q，R為命題公式，

如果PQR，則PRQ，QRP，且PQR為一矛盾式.證如果PQR，則

PRP(PQ)(PP)QFQQQRQ(PQ)FPPPQRRRF1.6其它聯(lián)結(jié)詞2023/7/4109條件否定聯(lián)結(jié)詞(Non-conditional，)定義1.6.2

設(shè)P，Q為二命題，復(fù)合命題“PQ”稱為命題P與Q的條件否定式PQ為真當(dāng)且僅當(dāng)P為真且Q為假.1.6其它聯(lián)結(jié)詞PQPQ000010101110由定義可知，PQ?(PQ)“”屬于二元(binary)運(yùn)算符.2023/7/4110與非聯(lián)結(jié)詞(NAND，↑)PQP↑Q001011101110定義1.6.2

設(shè)P,Q為二命題，復(fù)合命題“P與Q的否定”稱為P與Q的與非式，記作P↑Q，符號“↑”稱為與非聯(lián)結(jié)詞。P↑Q為真當(dāng)且僅當(dāng)P和Q不同時為真.1.6其它聯(lián)結(jié)詞與全功能集2023/7/4111由定義可知，P↑Q?(P∧Q)“↑”屬于二元(binary)運(yùn)算符聯(lián)結(jié)詞“↑”的性質(zhì)：(1)P↑P?(P∧P)?P(2)(P↑Q)↑(P↑Q)?(P↑Q)(P∧Q)

(3)(P↑P)↑(Q↑Q)?P↑?Q?(?P∧?Q)P∨Q1.6其它聯(lián)結(jié)詞2023/7/4112定義1.6.3

設(shè)P,Q為二命題，復(fù)合命題“P或Q的否定”稱為P與Q的或非式，記作P↓Q，符號“↓”稱為或非聯(lián)結(jié)詞.P↓Q為真當(dāng)且僅當(dāng)P與Q同為假.PQP↓Q001010100110或非聯(lián)結(jié)詞(NOR，↓)1.6其它聯(lián)結(jié)詞2023/7/4113由定義可知，P↓Q?(P∨Q)“↓”屬于二元(binary)運(yùn)算符聯(lián)結(jié)詞“↓”的性質(zhì)：(1)P↓P?(P∨P)?P(2)(P↓Q)↓(P↓Q)?(P↓Q)(P∨Q)(3)(P↓P)↓(Q↓Q)?P↓?Q?(?P∨?Q)P∧Q1.6其它聯(lián)結(jié)詞2023/7/4114至此，對于一元和二元邏輯運(yùn)算，我們一共定義了9個聯(lián)結(jié)詞，為了直接表達(dá)命題之間的聯(lián)系，是否還需要定義其它聯(lián)結(jié)詞呢?如果不需要定義其他聯(lián)結(jié)詞，那這9個聯(lián)結(jié)詞是否都是必須的？哪些是必須的？五、聯(lián)結(jié)詞全功能集(Theminimalsetofconnectives)1.6其它聯(lián)結(jié)詞下面以含兩個命題變元P、Q的所有互不等價的命題公式為例，來說明這一問題。2023/7/4115PQFP∧QP→QPQ→PQPQP∨Q0000000000010000111110001100111101010101PQP↓QPQ?QQ→P?PP→QP↑QT0011111111010000111110001100111101010101由兩個命題變元P，Q所構(gòu)成的互不等價的24個命題公式如下：1.6其它聯(lián)結(jié)詞2023/7/4116

由上表可知，9個聯(lián)結(jié)詞足以直接表達(dá)命題之間的各種聯(lián)系，所有的邏輯含義，均可由這9個聯(lián)結(jié)詞直接表達(dá)，不需要定義其他聯(lián)結(jié)詞。1.6其它聯(lián)結(jié)詞在二元運(yùn)算中，9個聯(lián)結(jié)詞并不都是必要的。為此，我們定義最小聯(lián)結(jié)詞組。2023/7/4117定義1.6.5

一個聯(lián)結(jié)詞集合，如果用其中聯(lián)結(jié)詞足以把任何命題公式等價地表示出來，而去掉其中任何一個聯(lián)結(jié)詞則不能，我們稱這個聯(lián)結(jié)詞集合為聯(lián)結(jié)詞全功能集(Theminimalsetofconnectives)聯(lián)結(jié)詞全功能集具有：(1)完備性(2)最小性1.6其它聯(lián)結(jié)詞2023/7/4118對于9個聯(lián)結(jié)詞的集合{?,,,,,,↑,↓,}，(1)PQ(P→Q)(Q→P)(2)PQ?PQ(3)PQ?(?P?Q)(4)PQ?(?P?Q)(5)(PQ)?(PQ)(6)P↑Q?(P∧Q)(7)P↓Q?(P∨Q)(8)PQ?(PQ)1.6其它聯(lián)結(jié)詞2023/7/4119任意命題公式都可由僅包含{?，}或{?，

}的命題公式等價代換，即9個聯(lián)結(jié)詞的集合中至少有七個冗余聯(lián)結(jié)詞。而聯(lián)結(jié)詞{?，}和{?，

}不再有冗余聯(lián)結(jié)詞，故{?，}或{?，

}為最小聯(lián)結(jié)詞組。實(shí)際中為了使用方便,命題公式常常同時包含{?，，

}.1.6其它聯(lián)結(jié)詞其他最小聯(lián)結(jié)詞組：{↑}，{↓}，{?，→}，{?，}2023/7/4120?P?(PP)P↑PPQ??(PQ)?(P↑Q)(P↑Q)↑(P↑Q)PQ?(?P?Q)?((P↑P)(Q↑Q))(P↑P)↑(Q↑Q)例1試證{↑}是最小聯(lián)結(jié)詞組.證例2

試證{?，→}是最小聯(lián)結(jié)詞組證1.6其它聯(lián)結(jié)詞PQ?(?P?Q)?(P→?Q)PQ?(?P)Q?P→Q2023/7/4121本節(jié)主要介紹了四種新的聯(lián)結(jié)詞及最小聯(lián)結(jié)詞組.小結(jié)1.6其它聯(lián)結(jié)詞2023/7/4122離散數(shù)學(xué)

(DiscreteMathematics)2023/7/41231.7對偶與范式(Dual&NormalForm)對偶式與對偶原理(DualisticFormula&DualityPrinciple)命題公式的析(合)取范式(TheDisjunctive&ConjunctiveNormalFormsofaPropositionalFormula)命題公式的主析(合)取范式(ThePrincipalDisjunctive&ConjunctiveNormalFormofaPropositionalFormula)小結(jié)2023/7/4124一、對偶式與對偶原理在§1.4中我們給出了命題定律，其中多數(shù)等價公式（僅含聯(lián)結(jié)詞?，，）都是成對出現(xiàn)的，每一對公式的不同之處是將與互換，T與F互換，我們把這樣的公式稱為是對偶的.1.7對偶與范式(Dual&NormalForm)2023/7/4125例11.7對偶與范式(Dual&NormalForm)(?P(QR))*=?P(QR)

((PQ)1)*=((PQ)0)

由P↑Q?(P∧Q)和P↓Q?(P∨Q)可知

(P↑Q)*=P↓Q定義1.7.1

設(shè)命題公式A僅含有聯(lián)結(jié)詞?、、，在A中將、、F、T分別換以、、T、F，得出公式A*，則A*稱為A的對偶公式。

(A*)*=A2023/7/4126關(guān)于對偶式我們有如下兩個定理:定理1.7.1

設(shè)A，A*是對偶式，P1，P2，…，Pn是出現(xiàn)于A和A*中的所有原子變元，則(1)?A(P1,P2,…,Pn)A*(?P1,?P2,…,?Pn)(2)A(?P1,?P2,…,?Pn)?A*(P1,P2,…,Pn)證明因?yàn)?(PQ)?P?Q，?(PQ)?P?Q所以?A(P1,P2,…,Pn)A*(?P1,?P2,…,?Pn)同理?A*(P1,P2,…,Pn)A(?P1,?P2,…,?Pn)。1.7對偶與范式(Dual&NormalForm)2023/7/4127定理1.7.2(對偶原理)設(shè)A，B為兩個僅含有聯(lián)結(jié)詞?，，的命題公式，若AB，則A*B*。證設(shè)P1,P2,…,Pn是出現(xiàn)于A和B中的所有原子變元.因?yàn)锳(P1,P2,…,Pn)B(P1,P2,…,Pn)所以A(P1,P2,…,Pn)B(P1,P2,…,Pn)永真.故A(?P1,?P2,…,?Pn)B(?P1,?P2,…,?Pn)永真.由定理1-7.1得

?A*(P1,P2,…,Pn)?B*(P1,P2,…,Pn).因此A*B*。1.7對偶與范式(Dual&NormalForm)2023/7/4128例2

因?yàn)?/p>

P(PQ)P由對偶原理，有

P(PQ)P.

例3

若A1則A*(1)*即A*0.例4

設(shè)A為(PQ)(?P(?PQ))，B為?PQ，且AB，則A*B*即

(PQ)(?P(?PQ))

?PQ。1.7對偶與范式(Dual&NormalForm)2023/7/4129設(shè)A，B為兩個僅含有聯(lián)結(jié)詞?，，的命題公式，若AB，則B*A*。證設(shè)P1，P2，…，Pn是出現(xiàn)于A和B中的所有原子變元.因?yàn)锳(P1,P2,…,Pn)B(P1,P2,…,Pn)

所以A(P1,P2,…,Pn)→B(P1,P2,…,Pn)永真.從而?B(P1,P2,…,Pn)→?A(P1,P2,…,Pn)永真.1.7對偶與范式(Dual&NormalForm)2023/7/4130即B*(?P1,?P2,…,?Pn)→A*(?P1,?P2,…,?Pn)永真.以Pi代?Pi

(i=1，2………n)，得B*(P1,P2,…,Pn)→A*(P1,P2,…,Pn)永真.所以B*A*.1.7對偶與范式(Dual&NormalForm)

設(shè)A，B為兩個僅含有聯(lián)結(jié)詞?，，的命題公式，若AB，則B*A*。2023/7/4131二、命題公式的析(合)取范式從前面的討論可知，存在大量互不相同的命題公式，實(shí)際上互為等價，因此，有必要引入命題公式的標(biāo)準(zhǔn)形式，使得相互等價的命題公式具有相同的標(biāo)準(zhǔn)形式。這無疑對判別兩個命題公式是否等價以及判定命題公式的類型是一種好方法，同時對命題公式的簡化和推證也是十分有益的。1.7對偶與范式(Dual&NormalForm)2023/7/4132定義1.7.2(1)文字：命題變元及其否定統(tǒng)稱為文字(如P,?P).(2)簡單析取式：僅有有限個文字組成的析取式。如P，?PQ，P?P，QP?P，P?QR?S.(3)簡單合取式：僅有有限個文字組成的合取式。如P，?Q，Q?P，P?P，QP?P，p∧?Q∧R.一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定式。一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定式。1.7對偶與范式(Dual&NormalForm)2023/7/4133定義1.7.3(1)析取范式：一個命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1∨A2∨……∨An(n大于等于1)其中Ai(i=1,2,3,…n)為簡單合取式。如：P∨?Q，(P∧Q)∨(P∧?Q∧R)，Q∧?P.(2)合取范式：一個命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式：A1∧A2∧……∧An(n大于等于1)其中Ai(i=1,2,3,…n)為簡單析取式。如：P∧?Q，(P∨Q)∧(P∨?Q∨R)，Q∧?P.(3)范式：析取范式與合取范式統(tǒng)稱為范式。1.7對偶與范式(Dual&NormalForm)2023/7/4134析取范式與合取范式的性質(zhì)：(1)一個析取范式是矛盾式，當(dāng)且僅當(dāng)它的每一個簡單合取式都是矛盾式；(2)一個合取范式是重言式，當(dāng)且僅當(dāng)它的每一個簡單析取式都是重言式。定理1.7.3(范式存在定理)任一個命題公式都存在著