第一章命題邏輯全

離散數(shù)學(xué)DiscreteMathematics授課學(xué)時(shí):48學(xué)時(shí)教學(xué)目標(biāo):知識(shí)、能力、素質(zhì)授課老師：張莉考試類型:閉卷成績組成:20(平時(shí)成績)+80%*卷面成績聯(lián)系方式:45231135@

教材：離散數(shù)學(xué)(第四版)----耿素云，屈婉玲，張立昂參考資料：離散數(shù)學(xué)習(xí)題解答與學(xué)習(xí)指導(dǎo)－清華大學(xué)出版社離散數(shù)學(xué)-計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)學(xué)習(xí)－陳德人，浙大版

DiscreteMathematics（ForthEdition:RichardJohnsonbaugh)

離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐步建立的，它形成于七十年代初期，是一門新興的工具性學(xué)科。

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，所以又稱為計(jì)算機(jī)數(shù)學(xué)，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心、骨干課程。它以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。內(nèi)容包含：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)與布爾代數(shù)、圖論等。

離散數(shù)學(xué)課程的學(xué)習(xí)方法:

強(qiáng)調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)：概念（正確）必須掌握好離散數(shù)學(xué)中大量的概念判斷（準(zhǔn)確）根據(jù)概念對(duì)事物的屬性進(jìn)行判斷推理（可靠）根據(jù)多個(gè)判斷推出一個(gè)新的判斷

離散數(shù)學(xué)與計(jì)算機(jī)的關(guān)系第一部分

數(shù)理邏輯計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物第二部分集合論集合：一種重要的數(shù)據(jù)結(jié)構(gòu)關(guān)系：關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)函數(shù)：所有計(jì)算機(jī)語言中不可缺少的一部分第三部分代數(shù)系統(tǒng)計(jì)算機(jī)編碼和糾錯(cuò)碼理論數(shù)字邏輯設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)使用的各種運(yùn)算第四部分圖論數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理計(jì)算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)離散數(shù)學(xué)課程設(shè)置：計(jì)算機(jī)系核心課程信息類專業(yè)必修課程其它類專業(yè)的重要選修課程離散數(shù)學(xué)的后繼課程：數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、算法分析與設(shè)計(jì)、人工智能、數(shù)據(jù)庫、……第一章命題邏輯

數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科.它采用數(shù)學(xué)符號(hào)化的方法來研究邏輯，因此也稱為符號(hào)邏輯。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題邏輯和一階邏輯(謂詞邏輯)。本書也只研究這兩個(gè)邏輯演算。數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實(shí)現(xiàn)把推理變?yōu)檠菟愕南敕?，他把?shù)學(xué)引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學(xué)科。上個(gè)世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。

1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問世。數(shù)理邏輯發(fā)展歷史

數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。本章和下一章我們只從語義出發(fā)，對(duì)數(shù)理邏輯中的命題邏輯與謂詞邏輯(一階邏輯)等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)?！?.1命題符號(hào)化及聯(lián)結(jié)詞基本概念

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

命題的真值：命題的判斷結(jié)果。真值只取兩個(gè)值：真（1）、假（0）。

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

假命題：真值為假的命題。判斷命題的兩個(gè)步驟：

1、是否為陳述句；2、是否有確定的、唯一的真值。注意:

感嘆句、祈使句、疑問句都不是命題.陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題例1.1

下列句子中那些是命題？

(1)

是無理數(shù).

(2)2+5＝8.(3)x+5＞

3.(4)今年春節(jié)大家看春晚了嗎？

(5)劉謙的魔術(shù)真是精彩呀！

(6)請(qǐng)不要講話！

(7)我正在說謊話.真命題假命題真值不確定疑問句感嘆句祈使句悖論(3)~(7)都不是命題(8)明年2月16號(hào)是晴天。命題及其真值的抽象化在本書中，用小寫英文字母p,q,r,…p1,p2,p3…

等表示命題,用“1”、“0”分別表示真值的真、假。

例1.2：

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

p3：明天天氣晴。皆為符號(hào)化的命題，其真值依次為0、1或0。若令

p：是有理數(shù)，則p的真值為0q：2+5=7，則q的真值為1命題及其真值的抽象化在本書中，用小寫英文字母p,q,r,…p1,p2,p3…

等表示命題,用“1”、“0”分別表示真值的真、假。

例1.2：

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

p3：明天天氣晴。皆為符號(hào)化的命題，其真值依次為0、1或0。若令

p：是有理數(shù)，則p的真值為0q：2+5=7，則q的真值為1命題及其真值的抽象化在本書中，用小寫英文字母p,q,r,…p1,p2,p3…

等表示命題,用“1”、“0”分別表示真值的真、假。

例1.2：

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

p3：明天天氣晴。皆為符號(hào)化的命題，其真值依次為0、1或0。若令

p：是有理數(shù)，則p的真值為0q：2+5=7，則q的真值為1命題的分類1:簡單/原子命題：不能再分解為更簡單的陳述句的陳述句。2:復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。例1.3

(1)若三角形等腰，則兩底角相等.(2)只要今天沒有大霧，飛機(jī)就不會(huì)晚點(diǎn)。

在命題邏輯的符號(hào)化過程中，通常的要求是每一個(gè)引進(jìn)的表示命題的符號(hào)都表示一個(gè)原子命題。

例如：將下列命題符號(hào)化(1)成都不是中國的首都。(2)李平雖然聰明，但不用功。

解(1)令p：成都是中國的首都。則命題“成都不是中國的首都”符號(hào)化為：┐P(2)令p：李平聰明。q：李平用功則命題“李平雖然聰明，但不用功。”符號(hào)化為：p∧┐q。

由此我們進(jìn)一步明確指出：原子命題是用肯定語氣表達(dá)的具有真假意義的簡單陳述句。上述例題中。直接令p表示“成都不是中國的首都”。來做符號(hào)化，是不符合要求的。常用聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作p，符號(hào)稱為否定聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于單目運(yùn)算符定義1.2設(shè)p,q為二命題，復(fù)合命題“p并且q”（或“p與q”）稱為p與q的合取式，記作p∧q，符號(hào)∧稱為合取聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于雙目運(yùn)算符合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算結(jié)果才為真，否則為假。自然語言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…”等都可以符號(hào)化為∧。注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞∧

！例1.4下列命題符號(hào)化(1)北京不僅是中國的首都而且是一個(gè)故都

p：北京是中國的首都。q：北京是一個(gè)故都。

p∧q：北京是中國的首都并且是一個(gè)故都。(2)張老師和周老師是好朋友。

p:張老師和周老師是好朋友

p是簡單命題定義1.3設(shè)p,q為二命題，復(fù)合命題“p或q”稱為p與q的析取式，記作p∨q，符號(hào)∨稱為析取聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于雙目運(yùn)算符例1.5將下列命題符號(hào)化

(1)2或4是素?cái)?shù).(2)2或3是素?cái)?shù).解令p:2是素?cái)?shù),q:3是素?cái)?shù),r:4是素?cái)?shù),則(1),(2)均為相容或.

分別符號(hào)化為:p∨r,p∨q,

它們的真值分別為1,1.

(3)小元元只能拿一個(gè)蘋果或一個(gè)梨.(4)王曉紅生于1975年或1976年.而(3),(4)為排斥或.令t:小元元拿一個(gè)蘋果，u:小元元拿一個(gè)梨，則(3)符號(hào)化為(t∧u)∨(t∧u).令v:王曉紅生于1975年,w:王曉紅生于1976年,則(4)符號(hào)化為(v∧w)∨(v∧w)定義1.4設(shè)p,q為二命題,復(fù)合命題“如果p則q”稱為p與q的蘊(yùn)涵式，記作pq,并稱p為蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，符號(hào)稱為蘊(yùn)涵聯(lián)結(jié)詞。與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！運(yùn)算規(guī)則：屬于雙目運(yùn)算符pq的邏輯關(guān)系：q為p的必要條件“如果p，則q”的不同表述法很多：若p，就q

只要p，就qp僅當(dāng)q

只有q才p

除非q,才p，當(dāng)p為假時(shí)，pq為真常出現(xiàn)的錯(cuò)誤：不分充分與必要條件

一定要注意到蘊(yùn)涵式的前件和后件!例1.5將下列命題符號(hào)化(5)如果22=5，則雪是黑的令p：22=5，q：雪是黑的，

于是命題符號(hào)化為pq

這是和人們?nèi)粘Ｉ钪姓Z言不一致的地方，這就是在邏輯中可以將兩個(gè)沒有關(guān)聯(lián)的事情用連接詞連接進(jìn)行討論。(6)如果我得到這部小說，那么我今夜就讀它令p1：我得到這部小說q1：我今夜就讀完它于是命題符號(hào)化為p1

q1定義1.5設(shè)p,q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱為p與q的等價(jià)式，記作pq，符號(hào)稱為等價(jià)聯(lián)結(jié)詞。說明:(1)pq的邏輯關(guān)系:p與q互為充分必要條件

(2)pq為真當(dāng)且僅當(dāng)p與q同真或同假運(yùn)算規(guī)則：屬于雙目運(yùn)算符例1.6

求下列復(fù)合命題的真值

(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)太陽從東方升起.(4)2+2＝

4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)

f(x)在x0

可導(dǎo)的充要條件是它在

x0連續(xù).

它們的真值分別為1，0，1，0，0.以上例子充分說明:等價(jià)運(yùn)算pq表示的邏輯關(guān)系是：p與q互為充分必要條件。相當(dāng)于(pq)∧(qp).以上5種最基本、最常用、最重要的聯(lián)結(jié)詞可以組成一個(gè)集合{

，∧，∨，，}，成為一個(gè)聯(lián)結(jié)詞集，其運(yùn)算的優(yōu)先級(jí)為：，∧，∨，，

，對(duì)于同一級(jí)者，先出現(xiàn)者先運(yùn)算。例1.8

求命題公式(pq)

pq真值表.

pqpqp

pq

pq

pq

00

11

1

1

01

1

1

1

1

1

0

0

0

0

1

1

1

1

0

1

1

§1.2命題公式及其分類基本概念簡單命題/命題常項(xiàng)/命題常元：真值唯一確定的陳述句。命題變項(xiàng)/命題變?cè)赫嬷悼梢宰兓年愂鼍?。命題常項(xiàng)與命題變項(xiàng)都可以用p,q,r…等表示，具體情況由上下文確定。

合式公式/命題公式：將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串。

當(dāng)使用聯(lián)結(jié)詞集{，∧，∨，，}時(shí)，合式公式定義如下：定義1.6（1）單個(gè)命題常項(xiàng)或變項(xiàng)是合式公式，并稱為原子命題公式。（2）若A是合式公式，則(A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)(AB)，(AB)也是合式公式。（4）只有有限次地應(yīng)用(1)~(3)形成的符號(hào)串才是合式公式。合式公式也稱為命題公式或命題形式，并簡稱為公式。(pq),(r∧t)∨e,p，(p)等是合式公式，而pq∨t,(p)∧q)等不是合式公式。上述歸納定義方式中的符號(hào)A,B不同于具體公式里面的p,q,r等符號(hào)，可以用來表示任意的合式公式,屬于元語言符號(hào)。定義1.7——公式層次（1）若公式A是單個(gè)的命題變項(xiàng)，則稱A為0層合式公式。（2）稱A是n+1(n≥0)層公式是指下列情況之一：

(a)A=B,B是n層公式；

(b)A=B∧C,其中B,C分別為i層和j層公式,

且n=max(i,j)；

(c)A=B∨C,其中B,C的層次及n同(b);(d)A=BC,其中B,C的層次及n同(b);(e)A=BC,其中B,C的層次及n同(b);（3）若公式A的層次為k，則稱A是k層公式。例:公式

p0層

p1層

pq2層

(pq)r3層

((pq)r)(rs)4層定義1.8——公式賦值設(shè)p1，

p2，

…，pn是出現(xiàn)在公式A中的全部的命題變項(xiàng)，給p1，

p2，

…，pn各指定一個(gè)真值，稱為對(duì)A的一個(gè)賦值或解釋。比如：對(duì)公式(pq)∧r，指定一組賦值：011(即令p=0,q=1,r=1)則公式的真值為1；指定另一組賦值：010可得真值為0；還有000，001，111……

考慮：含有n個(gè)命題變項(xiàng)的公式共有多少個(gè)不同的賦值？2n個(gè)賦值.

若指定的一組值使A的真值為1，則稱這組值為A的成真賦值。(使公式為真的賦值)

如對(duì)公式(pq)∧r賦值011，還有…???

若指定的一組值使A的真值為0，則稱這組值為A的成假賦值。(使公式為假的賦值)

如對(duì)公式(pq)∧r賦值010，還有…???真值表將命題公式A在所有賦值下取值情況列成表稱做A的真值表。對(duì)公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有的全體命題變項(xiàng)p1，

p2，

…，pn，列出2n個(gè)賦值。（2）按從低到高的順序?qū)懗龉降母鱾€(gè)層次。（3）對(duì)應(yīng)各個(gè)賦值計(jì)算出各層次的真值，直到最后計(jì)算出公式的真值。例1.9(1)求命題公式(pq)∧r的真值表公式的另一種分類方式定義1.9設(shè)A為任一命題公式，（1）若A在其各種賦值下的取值均為真，則稱A是重言式或永真式。（2）若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假式。（3）若A至少存在一組賦值是成真賦值，則稱A為可滿足式。可知,重言式一定是可滿足式,但反之不成立.真值表的作用：（1）表示出公式的成真或成假賦值。（2）判斷公式類型：

(a)若真值表最后一列全為1，則為重言式；

(b)若真值表最后一列全為0，則為矛盾式；

(c)若真值表最后一列至少有一個(gè)1，則為可滿足式；有很多公式具有相同的真值表。如：還有p∨q、pq等§1.3等值演算定義1.10

設(shè)A,B是兩個(gè)命題公式，若A，B構(gòu)成的等價(jià)式AB為重言式，則稱A與B是等值的記作AB.

即AB的充要條件是AB為重言式判斷兩個(gè)公式等值的方法1：真值表法。例1.10

判斷公式p(qr)與(p∧q)r是否等價(jià)等值演算：由已知的等值式推演出另外一些等值式的過程。等值演算中使用的一條重要規(guī)則：置換規(guī)則定理1.1

設(shè)Φ(A)是含公式A的命題公式,Φ(B)是用公式B置換了Φ(A)中所有的A后得到的命題公式，若BA，則Φ(A)Φ(B)。雙重否定律:AA等冪律：AAA,AAA交換律:ABBA,ABBA結(jié)合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)德·摩根律

:(AB)AB

(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA0蘊(yùn)涵等值式:ABAB等價(jià)等值式:AB(AB)(BA)假言易位:ABBA等價(jià)否定等值式:ABAB歸謬論:(AB)(AB)A等值演算與置換規(guī)則

等值演算:

由已知的等值式推演出新的等值式的過程置換規(guī)則：若AB,則(B)(A)

等值演算的基礎(chǔ)：

(1)等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞

(2)基本的等值式

(3)置換規(guī)則等值演算的用途一：證明等值式。例1.10驗(yàn)證p(qr)(p∧q)r

右(p∧q)∨r

蘊(yùn)涵等值式

p∨q∨r德摩根律

p∨(q∨r)結(jié)合律

p∨(qr)蘊(yùn)涵等值式

p(qr)蘊(yùn)涵等值式注:ABA∨B

例1.14：判斷公式

(pq)r的類型(自學(xué))

解：列出真值表如下，可知其是可滿足式的等值演算的用途三：文字?jǐn)喟竼栴}。例：參見教材p11

例1.11解：設(shè)pi,qi,ri,si分別表示A第i名,B第i名,C第i名,D第i名,由題意可知下列命題成立。①(r1∧?q2)∨(?r1∧q2)1②(r2∧?s3)∨(?r2∧s3)1③(p2∧?s4)∨(?p2∧s4)11①∧②[(r1∧?q2)∨(?r1∧q2)]∧[(r2∧?s3)∨(?r2∧s3)][(r1∧?q2)∧(r2∧?s3)]∨[(?r1∧q2)∧(r2∧?s3)]∨[(r1∧?q2)∧(?r2∧s3)]∨[(?r1∧q2)∧(?r2∧s3)]這里用到分配率公式(A∨B)∧(C∨D)=[(A∧C)∨(B∧C)]∨[(A∧D)∨(B∧D)

]由于C不能既第一又第二,又B和C不能都第二,故(r1∧?q2)∧(r2∧?s3)0(?r1∧q2)∧(r2∧?s3)0①(r1∧?q2)∨(?r1∧q2)1②(r2∧?s3)∨(?r2∧s3)1③(p2∧?s4)∨(?p2∧s4)11①∧②④(r1∧?q2)∧(r2∧?s3)∨(?r1∧q2)∧(?r2∧s3)11③∧④⑤

1p2∧?q2∧r1∧?r2∧s3∧?s4由上式可知r1,

p2,s3是真命題，即C第一，A第二，D第三，B只能第四了。例：參見教材p11

例1.11解：設(shè)pi,qi,ri,si分別表示A第i名,B第i名,C第i名,D第i名,由題意可知下列命題成立。Theend§1.4聯(lián)結(jié)詞全功能集定義1.11

設(shè)p，q是兩個(gè)命題，復(fù)合命題“p,q之中恰有一個(gè)成立”稱為p與q的排斥或或異或，記作pq，稱作排斥或或異或聯(lián)結(jié)詞。Pq為真當(dāng)且僅當(dāng)p，q中恰有一個(gè)為真。Pqpq00001101110例：小李現(xiàn)在在宿舍或在圖書館里令p:小李在宿舍

q:小李在圖書館里該命題可表示為Pq定義1.12

設(shè)p，q是兩個(gè)命題，復(fù)合命題“p與q的否定”稱為p與q的與非式，記作pq?！啊狈Q作與非聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p，q不同時(shí)為真.

由定義可知：

pq=(pq)。

pqpq

001011101110定義1.13

設(shè)p，q是兩個(gè)命題，復(fù)合命題“p或q的否定”稱為p與q的或非式，記作pq，

稱作或非聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p，q同時(shí)為假。由定義可知：

pq=(pq)

pqpq

001010100110定義1.14

一個(gè)n(n1)維卡氏積{0,1}n到{0,1}的函數(shù)稱為一個(gè)n元真值函數(shù)。設(shè)F是一個(gè)n元真值函數(shù)，則可記為F：{0,1}n{0,1}n個(gè)命題變項(xiàng)，共有2n個(gè)可能的賦值，對(duì)于每個(gè)賦值真值函數(shù)的函數(shù)值非0即1，于是n個(gè)命題變?cè)部梢孕纬?2個(gè)不同的真值函數(shù)。見教材P13表1.6

n命題公式與真值函數(shù)

對(duì)于任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式A，都存在惟一的一個(gè)n元真值函數(shù)F為A的真值表.等值的公式對(duì)應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對(duì)應(yīng)的真值表,每一個(gè)含2個(gè)命題變項(xiàng)的公式的真值表都可以在下表中找到.

例如：pq,pq,(pq)((pq)q)等都對(duì)應(yīng)表中的2元真值函數(shù)對(duì)應(yīng)的真值表其實(shí)，每個(gè)真值函數(shù)可對(duì)應(yīng)無窮多個(gè)命題公式，它們彼此都是等值的，有很多公式具有相同的真值表。如：……………還有p∨q、pq等定義1.15

在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨(dú)立的聯(lián)結(jié)詞。前面給出的5個(gè)聯(lián)結(jié)詞組成的聯(lián)結(jié)詞集為{，，，，}，由于

pqp

q

p

q(pq)(qp)(p

q)(q

p

)所以，都是冗余的，又{，，，}中，由于p

q(pq)(pq)所以可看成是冗余的，但在{,}中無冗余的聯(lián)結(jié)詞定義1.16

若任一真值函數(shù)都可以用僅含某一聯(lián)結(jié)詞的命題公式表示，則稱該聯(lián)結(jié)詞集為全功能集。若一個(gè)聯(lián)結(jié)詞集的全功能集中不含冗余的的聯(lián)結(jié)詞，則稱它為極小全功能集例1.13

若已知{，}是全功能集，證明{，}也是

全功能集證明由于{，}是全功能集，因而任一真值函數(shù)均可由僅含{，}中的聯(lián)結(jié)詞的命題公式表示，而對(duì)于任意的命題形式A，B，有

ABAB因而任一真值函數(shù)均可由含{，}中的聯(lián)結(jié)詞的命題公式表示，所以它是全功能集。聯(lián)結(jié)詞的全功能集實(shí)例

(1)S1={,,,}(2)S2={,,,,}

(3)S3={,}(4)S4={,}(5)S5={,}(6)S6={}(7)S7={}

定義1.1.7

在僅含聯(lián)結(jié)詞,,的命題公式A中，將換成，換成,若A中含0或1，就將0換成1，1換成0，所得命題公式稱為A的對(duì)偶式，記作A*。從定義不難看出，(A*)*=A如:公式P(QF)的對(duì)偶公式為P(QF)定理1.2

設(shè)A和A*互為對(duì)偶式，設(shè)p1,…,pn是出現(xiàn)在A和A*

中的全部的命題變項(xiàng)，若將A和A*

寫成n元函數(shù)形式，則①

A(P1,P2,…,Pn)A*(P1,P2,…,Pn);②

A(P1,P2,…,Pn)A*(P1,P2,…,Pn).§1.5對(duì)偶與范式定理1.3

(對(duì)偶原理)

設(shè)A、B為兩命題公式，若AB，則A*B*

其中A*，B*

分別為A，B的對(duì)偶式。由對(duì)偶原理可知，若A為重言式，則A*必為矛盾式，反之亦然.

給定一個(gè)命題公式，判斷它是重言式、矛盾式、還是可滿足式，這類問題稱為判定問題。

判定的方法都有哪些？析取范式與合取范式

———含n個(gè)命題變項(xiàng)的公式兩種規(guī)范表示方法定義1.18文字：命題變項(xiàng)及其否定統(tǒng)稱為文字。如：p,

q簡單析取式：僅有有限個(gè)文字組成的析取式。如：p,

q,p∨q,p∨

q∨r簡單合取式：僅有有限個(gè)文字組成的合取式。如：p,

q,p∧q,p∧

q∧r

命題公式是千變?nèi)f化的，這給研究命題演算帶來困難，這里我們研究如何由一個(gè)命題公式化歸為一個(gè)標(biāo)準(zhǔn)形式的問題，這樣命題演算的研究問題就歸結(jié)為對(duì)標(biāo)準(zhǔn)形式的研究問題，這種標(biāo)準(zhǔn)形式就叫范式。析取范式(參考課本上的定義)

它是這樣一種標(biāo)準(zhǔn)形式，在此式內(nèi)不出現(xiàn)聯(lián)結(jié)詞及，否定符號(hào)只出現(xiàn)在命題變?cè)啊Ｋ且粋€(gè)析取式，式中的每個(gè)析取項(xiàng)是個(gè)合取式，每個(gè)合取式中只包含命題變?cè)蛎}變?cè)姆穸ā＠鏿∨(p∧q)∨(q∧r)

此式即具有析取范式之形式注意:一個(gè)公式的析取范式并不唯一，如p∨(r∧q),可以寫成(p∧p)∨(r∧q)合取范式它是這樣一種標(biāo)準(zhǔn)形式，在此式內(nèi)不出現(xiàn)聯(lián)結(jié)詞及，否定符號(hào)只出現(xiàn)在命題變?cè)啊Ｋ且粋€(gè)合取式，式中的每個(gè)合取項(xiàng)是個(gè)析取式，每個(gè)析取式中只包含命題變?cè)蛎}變?cè)姆穸?。例如p∧(p∨q)∧

(q∨r)

此式即具有合取范式之形式注意:一個(gè)公式的合取范式并不唯一，如p∧

(r∨

q)

可以寫成(p∨p)∧(r∨

q)定義1.9析取范式：由有限個(gè)簡單合取式構(gòu)成的析取式。如：p∨

q,(p

∧q)∨(p∧

q∧r)合取范式：由有限個(gè)簡單析取式構(gòu)成的合取式。如：p∧q,（p∨q）∧（

p∨q∨r）范式：析取范式與合取范式統(tǒng)稱為范式。設(shè)Ai(i=1,2,3,…n)為簡單合取式，則A=A1∨A2∨……∨An

就是析取范式，而B=A1∧A2∧……∧An

就是合取范式。析取范式和合取范式有下列性質(zhì)：

（1）一個(gè)析取范式是矛盾式它的每個(gè)簡單合取式都是矛盾式。（2）一個(gè)合取范式是重言式它的每個(gè)簡單析取式都是重言式。定理1.4(范式存在定理)

任一個(gè)命題公式都存在著與之等值的析取范式與合取范式。求范式的具體步驟：（1）消去對(duì){,∧,∨,}來說冗余的聯(lián)結(jié)詞，即{，}。利用下列等值式：

AB(A∨B)AB(A∨B)∧(A∨

B)（2）否定詞的消去或內(nèi)移。

利用下列等值式：

AB(A∨B)

(A∨B)A∧B

(A∧B)A∨B（3）利用分配律：

C∧(A∨B)（C∧A）∨（C∧B）

C∨(A∧B)（C∨A）∧（C∨B）例1.14求下列公式的析取范式與合取范式(1)A=(pq)r解(pq)r(pq)r

（消去）

pqr

（結(jié)合律）

這既是A的析取范式（由3個(gè)簡單合取式組成的析取式），又是A的合取范式（由一個(gè)簡單析取式組成的合取式）(2)B=(pq)r解(pq)r(pq)r

（消去第一個(gè)）

(pq)r

（消去第二個(gè)）

(pq)r

（否定號(hào)內(nèi)移——德摩根律）這一步已為析取范式（兩個(gè)簡單合取式構(gòu)成）繼續(xù)：(pq)r

(pr)(qr)（對(duì)分配律）這一步得到合取范式（由兩個(gè)簡單析取式構(gòu)成）(3)

求(pq)∧(pr)的析取范式。解：(pq)∧(pr)

(p∨q)∧(p∨r)((p∨q)∧p)

∨((p∨q)∧r)((p∧p)∨(q∧p))∨((p∧r)∨(q∧r))(q∧p)∨(p∧r)∨(q∧r)(4)

求(pq)∧(pr)的合取范式。解：(pq)∧(pr)

(p∨q)∧(p∨r)定義1.20極小項(xiàng)/極大項(xiàng)在含有n個(gè)命題變項(xiàng)的簡單合取式(簡單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）.由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

M0M1M2M3

p

qp

qp

qp

q名稱公式

00011011p

q

p

q

p

q

p

q

m0m1m2m3

00011011成假賦值公式名稱成真賦值極大項(xiàng)

極小項(xiàng)

說明：

1:n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)

2:2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值

3:用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示;4:用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示;

mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

極小項(xiàng)與極大項(xiàng)關(guān)系設(shè)mi和Mi是命題變項(xiàng)p1

，

p2

，…pn形成的極小項(xiàng)和極大項(xiàng)，則

mi

Mi

，

Mi

mi定義1.21

設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的析（合）取范式中所有的簡單合（析）取式都是極小（大）項(xiàng)，則稱該析（合）取范式為主析（合）取范式。由不同最小項(xiàng)所組成的析取式稱為主析取范式由不同最大項(xiàng)所組成的合取式稱為主合取范式定理

1.5任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.

用等值演算法求公式的主范式的步驟：

(1)先求析取范式（合取范式）

(2)將不是極小項(xiàng)（極大項(xiàng)）的簡單合取式（簡單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析?。O大項(xiàng)的合?。枰猛宦桑懵桑?、排中律（矛盾律）、分配律、冪等律等.(3)極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序.

例1.15某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí).選派必須滿足以下條件：

(1)若趙去，錢也去；

(2)李、周兩人中至少有一人去；

(3)錢、孫兩人中有一人去且僅去一人；

(4)孫、李兩人同去或同不去；

(5)若周去，則趙、錢也去.

試用主析取范式法分析該公司如何選派他們出國？解此類問題的步驟為：①將簡單命題符號(hào)化②寫出各復(fù)合命題③寫出由②中復(fù)合命題組成的合取式④求③中所得公式的主析取范式解

①

設(shè)p：派趙去，q：派錢去，r：派孫去，s：派李去，u：派周去.②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))

③(1)~(5)構(gòu)成的合取式為

A=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))

④A(pqrsu)(pqrsu)結(jié)論：由④可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）.

A的演算過程如下:A

(pq)((qr)(qr))(su)(u(pq))((rs)(rs))（交換律)B1=(pq)((qr)(qr))((pqr)(pqr)(qr))(分配律)B2=(su)(u(pq))((su)(pqs)(pqu))（分配律）B1B2(pqrsu)(pqrsu)(qrsu)(pqrs)(pqru)再令

B3=((rs)(rs))得A

B1B2B3(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律要求：自己演算一遍

例1.17

求(pq)∧(pr)的主析取范式。解法1：

Pqrppqpr(pq)∧(pr)00010100

0

11010010111101111111000100101011111001001110111所以：(pq)∧(pr)m2∨m3∨m5∨m7(2,3,5,7)解法2：

(pq)∧(pr)(q∧p)∨(p∧r)∨(q∧r)(析取范式)((p∧r)∧(q∨q))∨((p∧q)∧(r∨r))

∨((q∧r)∧(p∨p))……(p∧q∧r)∨

(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)

(主析取范式)m2∨m3∨m5∨m7(2,3,5,7)例1.20判斷命題公式(p∨(q∧r))(p∨q∨r)的類型解：(p∨(q∧

r))(p∨

q

∨

r)(p∨(q∧

r))∨(p∨

q

∨

r)(

p∧

(q∧

r))∨p∨

q

∨

r(

p∧(q

∨

r))∨p∨

q

∨

r((

p∧

q)

∨

(

p∧

r))

∨p∨

q

∨

rm0∨m1∨m2∨m3

∨m4∨m5

m6∨m7成真賦值：000、001、010、011、100、101、110、111該命題公式為重言式提示:用真值表判斷命題公式的類型是最常用的方法主析取范式的用途（主合取范式類似討論）：1、求公式的成真/成假賦值：若公式A中含有n個(gè)命題變項(xiàng)，且A的主析取范式含s個(gè)極小項(xiàng)，則A有s個(gè)成真賦值，有2n-s個(gè)成假賦值。2、判斷公式的類型：設(shè)公式A中含有n個(gè)命題變項(xiàng)，則：（1）A為重言式A的主析取范式含全部2n個(gè)極小項(xiàng)。（2）A為矛盾式A的主析取范式不含任何極小項(xiàng)，記A的主析取范式為0。（3）A為可滿足式A的主析取范式至少含一個(gè)極小項(xiàng)。3、判斷兩個(gè)命題是否等值：設(shè)公式A、B中共含有n個(gè)命題變項(xiàng)，按n個(gè)命題變項(xiàng)求出A、B的主析取范式A`、B`。若A`=B`，則AB，否則A、B不等值。例1.21

判斷下列命題公式是否等值

(1)(pq)∧(p

r)與

p(q∧r)(2)p(q∧r)與p∨(qr)

pqr

q∧r

pqp

r(pq)∧(p

r)

p(q∧r)

0000111100101111010011110111111110000000101001001100100011111111命題公式(pq)∧(p

r)與p(q∧r)等值

pqr

q∧rqr

p(q∧r)

p∨(qr)

00001110010111010001001111111000101101010111000011111111命題公式p(q∧r)與p∨(qr)不等值注意：

AB

當(dāng)且僅當(dāng)

A、B含有相同的真值表或A、B有相同的主析（合）取范式。§1.6推理理論

推理是從前提推出結(jié)論的思維過程，前提是指已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式，前提可多個(gè).由前提A1，A2，…Ak推出結(jié)論B的嚴(yán)格定義如下：定義1.24

若(A1∧A2∧…∧Ak)B為重言式，則稱A1，A2，…Ak，推出結(jié)論B的推理正確，B是A1，A2，…Ak，的邏輯結(jié)論或有效結(jié)論，稱(A1∧A2∧…∧Ak)B為由前提A1，A2，…Ak推結(jié)論B的推理的形式結(jié)構(gòu)。用“AB”表示“AB”是重言式，由前提A1，A2，…Ak推B的推理正確,也記:(A1∧A2∧…∧Ak)B

對(duì)于任一組賦值，前提和結(jié)論的取值有以下四種情況：

①{A1，A2，…Ak}為0，B為0?！挞趝A1，A2，…Ak}為0，B為1。√③{A1，A2，…Ak}為1，B為0。×④{A1，A2，…Ak}為1，B為1?！掏评淼牧硪环N形式：命題公式A1，A2，…Ak推B的推理正確當(dāng)且僅當(dāng)

(A1∧

A2∧

…∧Ak)B為重言式。于是推理的一般形式可轉(zhuǎn)化為：

(A1

∧A2

∧…∧Ak)B推理正確轉(zhuǎn)化為：

A1

∧A2

∧…∧Ak

B于是，以后推理的形式就寫作：前提：p,pq

結(jié)論：q推理的形式結(jié)構(gòu)：

(p

∧(pq))q即只需證明蘊(yùn)涵式(p∧(pq))q為重言式。三種方法：

1、真值表法；

2、等值演算法；

3、主析取范式法。例1.23：判斷下列推理是否正確。1.今天小張或去網(wǎng)吧或去教室。他沒去教室，所以他去網(wǎng)吧了。設(shè)p：小張去網(wǎng)吧。q：小張去教室。則，前提：p∨q,?q

結(jié)論：p

推理的形式結(jié)構(gòu)：

((p∨q)

∧?q)p解法1：真值表法該命題公式為重言式，說明推理正確，所以小張去網(wǎng)吧解法2：等值演算法：((p∨q)

∧?q)p

((p∧?q)∨(q∧?q))p(p∧

?

q)p

?

(p∧

?

q)∨

p

?p

∨

q

∨

p

1所以，推理正確，即（(p∨q)

∧?q)

p推理定律——重言蘊(yùn)涵式

重要的推理定律

(1)A

T(AúB)附加律

(2)(AùB)T

A

化簡律

(3)(A?B)ùA

T

B

假言推理

(4)(A?B)ù?B

T

?A

拒取式

(5)(AúB)ù?B

T

A

析取三段論

(6)(A?B)ù(B?C)T(A?C)假言三段論

(7)(A?B)ù(B?C)T(A?C)等價(jià)三段論

(8)(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難(3)(?A∨B)∧A(?A∧A)∨(A∧B)(A∧B)A推理定律(續(xù))(9)(A?B)ù(?A?B)ù(Aú?A)T

B

構(gòu)造性二難（特殊形式）(10)(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難說明：

A,B,C為元語言符號(hào)若某推理符合某條推理定律，則它自然是正確的A?B產(chǎn)生兩條推理定律:ATB,BTA構(gòu)造證明——直接證明法例1.27構(gòu)造下面推理的證明：若明天是星期一或星期三，我就有課.若有課，今天必備課.我今天下午沒備課.所以，明天不是星期一和星期三.解

設(shè)p：明天是星期一，q：明天是星期三，

r：我有課，s：我備課形式結(jié)構(gòu)為前提：(púq)?r,r?s,?s

結(jié)論：?pù?q

形式結(jié)構(gòu)為前提：(púq)?r,r?s,?s

結(jié)論：?pù?q證明

①r?s

前提引入

②?s

前提引入

③?r①②拒取式

④(púq)?r

前提引入

⑤?(púq)③④拒取式

⑥?pù?q⑤置換直接證明法(續(xù))根據(jù)前面八條推理定律，可得下面推理規(guī)則。用A1，A2，…Ak|=B表示B是A1，A2，…Ak的邏輯結(jié)論。(1)A

B,

A|=

B假言推理規(guī)則(2)A|=

A∨B附加規(guī)則(3)A∧B|=

A化簡規(guī)則(4)A

B,

?

B

|=

?

A

拒取式規(guī)則(5)AB,BC|=AC假言三段論規(guī)則(6)A∨

B,

?

A

|=

B析取三