第一章命題邏輯基本概念1

1.1命題及其符號(hào)化

［教學(xué)重點(diǎn)］命題的概念和六個(gè)聯(lián)結(jié)詞的定義

［教學(xué)H的］1：使學(xué)生了解邏輯的框架，命題邏輯的基本要素是命題。

2：通過示例理解命題的概念。

3：通過示例理解合取、析取、異或、蘊(yùn)涵、等價(jià)的含義，了解邏輯語(yǔ)言的精

確性，為學(xué)習(xí)邏輯學(xué)打好基礎(chǔ)。

4：學(xué)會(huì)命題符號(hào)化的方法。

［教學(xué)準(zhǔn)備］

［教學(xué)方法］講述法

［課時(shí)安排］二課時(shí)。

［教學(xué)過程］

講述：

邏輯是解決推理方法的學(xué)科，中心是推理，基本要素是命題，稱為命題邏輯。

數(shù)理邏輯則是用數(shù)學(xué)方法研究推理；

首先要理解命題是什么，然后了解怎樣用數(shù)學(xué)方法描述命題，甚至邏輯推理。后者式

命題符號(hào)化的問題。

板書：

第一章命題基本概念

1.1命題及其符號(hào)化

講述：

首先討論命題。

板書：

-命題

A）概念：

在二值邏輯中，命題是或真或假，而不會(huì)同時(shí)又真又假的陳述句。

判斷要點(diǎn)：

a陳述句；b或真或假，唯一真值：

講述：

例：

(1)地球是圓的；真的陳述句，是命題

⑵2+3=5；真的陳述句，是命題

(3)你知道命題邏輯嗎？非陳述句，故非命題

⑷3-x=5；陳述句，但真假隨X的變化而變化，非命題

(5)請(qǐng)安靜！非陳述句，故非命題

(6)火星表面的溫度是800℃；現(xiàn)時(shí)不知真假的陳述句，但只能要么真要

么假，故是命題

⑺明天是晴天；盡管要到第二天才能得知其真假，但的確

是要么真要么假，故是命題

2

(8)我正在說謊；無法得知其真假，這是悖論

注意到(4)不是命題，后續(xù)章節(jié)中會(huì)提到，這被稱為謂詞，命題函數(shù)或命題變項(xiàng)。

講述：

類似一般的事物，也有不同的命題，分成不同的類型。

板書：

B)分類：

a簡(jiǎn)單命題，通常用p,q,r,…，等表示命題變項(xiàng)，命題常項(xiàng)用1(T),0(F)表示；

b復(fù)合命題，由簡(jiǎn)單命題和聯(lián)結(jié)詞構(gòu)成；

講述：

簡(jiǎn)單命題可以簡(jiǎn)單地用單個(gè)字母表示，但復(fù)合命題還包含了聯(lián)結(jié)詞，多個(gè)命題變項(xiàng)由

聯(lián)結(jié)詞聯(lián)結(jié)起來成為復(fù)合命題。所以還需要考慮聯(lián)結(jié)詞的問題。

板書：

二邏輯聯(lián)結(jié)詞

講述：

首先最為簡(jiǎn)單的一種情況，就是日常語(yǔ)言中所說的“不”，這是對(duì)原有意思的的否定,

所以稱為否定式

板書：

1)否定式和否定聯(lián)結(jié)詞：

命題0的非或否定，稱為p的否定式，表示為「小符號(hào)「即為否定聯(lián)結(jié)詞。用表格表示：

Pf

TF

FT

講述：

嚴(yán)格說，「p不是復(fù)合命題。

示例：p：今天天氣好：「p：今天天氣不好

P：2+5>1；[p：2+5W1；在此情形下，p為真,為假。

講述：

問題：北京和上海都是中國(guó)的直轄市。顯然這個(gè)句子可分成兩個(gè)句子，中間由“和”、

“且”之類的聯(lián)結(jié)詞聯(lián)結(jié)。這類的聯(lián)結(jié)詞我們統(tǒng)稱為“合取”。

板書：

2)合取式和合取聯(lián)結(jié)詞

p且,稱為p國(guó)的合取式，記為符號(hào)人即為合取聯(lián)結(jié)詞。

pqp'q

TTT

TFF

FTF

FFF

邏輯“與”。

講述：

相應(yīng)的日常用語(yǔ)還有一些。

板書：

“既…又...”，“不但(僅)…而且…”，“雖然…但是…”。

講述：

3

例：

Dp：今天大太陽(yáng)，q:今天熱，p/\q；今天大太陽(yáng)且熱；

2)p:今天上課有人遲到，q:2+5>l,p八q:今天上課有人遲到且2+5>1；

講述：

注意到2)中的結(jié)果，我們可以用邏輯聯(lián)結(jié)詞來聯(lián)結(jié)兩個(gè)日常生活中無關(guān)的命題。另外

也要注意日常語(yǔ)言中的“和”，不一定都能用人表示。

示例：“新聞和報(bào)紙不分家”。

講述：

“或”也是非常常用的聯(lián)結(jié)詞。

例：

(1)文文或華華今天出差。

(2)他今天騎車或走路來上課。

(3)從理科2號(hào)樓到圖書館要3分鐘或5分鐘。

講述：

(1)一般情況下兩個(gè)人可能同時(shí)同以去出差，即可以同時(shí)為真，是相容的，所以是“相

容或”。

板書：

相容或

講述：

(2)在這兩種情況下，或者發(fā)生?種，或者都不發(fā)生(如他今天是乘公共車來上課的)，

但不可能二者同時(shí)發(fā)生，即不可能二者同時(shí)為真，所以是“相斥或”。在自然語(yǔ)言中類似的

“相斥或”是很多的，又如“劉荷或李蘭是三班班長(zhǎng)”。

板書：

相斥或

講述：

(3)也是自然語(yǔ)言中的“或”，可能并不代表相容相斥，而表示一種大約的含義，即從

理科2號(hào)樓到圖書館大約要用3到5分鐘的時(shí)間，又如：“他作了二三十道數(shù)學(xué)題”。

我們可以看到在日常語(yǔ)言中，“或”具有多義性，但我們用符號(hào)表示時(shí)，卻必須避免

這種歧義性。通常把相容或稱為“析取”，而相斥或則稱為“異或”。

板書：

3)析取式和析取聯(lián)結(jié)詞

P或者g稱為小g的析取式，記為pVq；符號(hào)v即為析取聯(lián)結(jié)詞。

pq

TTT

TFT

FTT

FFF

邏輯“或”

4)異或式和異或聯(lián)結(jié)詞

p或者(7中只能一個(gè)為真稱為的異或式，記為pvq；符號(hào)v即為異或聯(lián)結(jié)詞。

Pqp斗q

TTF

TFT

4

FTIT

FF|F

講述：

“如果…則…”也是一類常見的聯(lián)結(jié)詞。這是有條件和結(jié)論的一類，稱為“條件式”,

也稱為“蘊(yùn)涵式”。

板書：

4)蘊(yùn)涵式和蘊(yùn)涵聯(lián)結(jié)詞

如果p則q稱作p、q的蘊(yùn)涵式，記為f為蘊(yùn)涵聯(lián)結(jié)詞，p、q分別為蘊(yùn)

涵式的前件和后件。

講述：

示例:

一位父親對(duì)兒子說：“如果星期天天氣好，就一定帶你去動(dòng)物園。”問：在什么情況下父親

食言？

父親的可能情況有如下四種：

(1)星期天天氣好，帶兒子去了動(dòng)物園；

(2)星期天天氣好，卻沒帶兒子去動(dòng)物園；

(3)星期天天氣不好，卻帶兒子去了動(dòng)物園；

(4)星期天天氣不好，也沒帶兒子去動(dòng)物園。

顯然，(1),(4)兩種情況父親都沒有食言；(3)這種情況和父親原來的話沒有相抵觸的地

方，當(dāng)然也不算食言；只有(2)這種情況，答應(yīng)的事卻沒有做，應(yīng)該算是食言了。(2)對(duì)應(yīng)著

“前件真后件假”的情況，使得蘊(yùn)涵式為假，而其它三種情況都使得蘊(yùn)涵式為真。

板書：

Pqprq

TTT

TFF

FTT

FFT

講述：

這里注意到：在蘊(yùn)涵式p-4中，。是夕的充分條件，夕是p的必要條件。這類的聯(lián)結(jié)

詞還有：

板書：

pf/"只要p就夕”，“p僅當(dāng)“只有g(shù)才p”等

講述：

蘊(yùn)涵式的一個(gè)應(yīng)用：數(shù)學(xué)歸納法

(1)證明P(〃o)成立；(2)證明當(dāng)時(shí)P(A)-P伏+1)總是成立。

在⑵中，P(k)-P(k+1)總、是成立,意味著P/)fP(%+l)的真值為T,從而只可能是表1.5

中的第1,2,4種情形，而(1)中證明了前件為真，所以后件也一定為真。

講述：

前面講述描述了充分條件或必要條件的表示，現(xiàn)在我們可以表示充要條件了：

“P是q的充要條件”，“p是q的充分條件”且“p是q的必要條件”，可以用蘊(yùn)涵和

合取兩者描述。

板書：

5

講述：

這個(gè)表達(dá)式較為復(fù)雜，所以用一個(gè)聯(lián)結(jié)詞“等價(jià)”簡(jiǎn)單表示。

板書：

5)等價(jià)式和等價(jià)聯(lián)結(jié)詞

p當(dāng)且僅當(dāng)q稱作p、q的等價(jià)式，記為p—q。一稱為等價(jià)聯(lián)結(jié)詞。

pqpaq

TTT

TFF

FTF

FFT

講述：

以上介紹了六種常用的邏輯聯(lián)結(jié)詞以及與之相關(guān)的復(fù)合命題。這些聯(lián)結(jié)詞反映了復(fù)合

命題及其支命題之間抽象的邏輯關(guān)系。復(fù)合命題的符號(hào)化一般可以根據(jù)上述定義進(jìn)行，基

本步驟如下：

板書：

符號(hào)化基本步驟：

1)找出各個(gè)支命題，并逐個(gè)符號(hào)化；

2)找出各個(gè)連接詞，符號(hào)成相應(yīng)聯(lián)結(jié)詞；

3)用聯(lián)結(jié)詞將各支命題逐個(gè)聯(lián)結(jié)起來；

示例：將下列命題符號(hào)化：

(1)李明是計(jì)算機(jī)系的學(xué)生，他住在312室或313室.

(2)辱罵和恐嚇決不是戰(zhàn)斗；

(3)李瑞和李珊是姐妹。

(4)除非天氣好，否則我是不會(huì)去公園的：

講述：

分析并符號(hào)化，強(qiáng)調(diào)在進(jìn)行命題符號(hào)化以前，必須明確含義，刪除歧義，這是命題翻

譯的關(guān)鍵之點(diǎn)。

(1)P-.李明是計(jì)算機(jī)系的學(xué)生；

q：李明住在312室；

r：李明住在313室。

因?yàn)槔蠲鞑豢赡芗茸≡?12室又住在313室，所以這里應(yīng)該用*,而不用V,符號(hào)化

為pA(g-V-r)?

(2)p-.辱罵是戰(zhàn)斗；

q：恐嚇是戰(zhàn)斗。

符號(hào)化為可八-ig。

(3)p：李瑞和李珊是姐妹。

符號(hào)化為p。

(4)p：今天天氣好：

q：我去公園。

符號(hào)化為qfp。

作業(yè)：

習(xí)題1.1,1.2

6

1.2合式公式和真值賦值

［教學(xué)重點(diǎn)］合式公式及層次，解釋的含義，真值表的構(gòu)成。

［教學(xué)目的］1：使學(xué)生了解合式公式和公式層次的定義，理解遞歸定義法的方法。

2：學(xué)會(huì)描述公式的形成過程。

3：理解解釋的含義，領(lǐng)會(huì)公式分類的要點(diǎn)。

4：使學(xué)生了解并學(xué)會(huì)應(yīng)用真值表的構(gòu)成方法。

5：理解真值函數(shù)的含義，理解命題的多種形式的實(shí)質(zhì)本質(zhì)。

6：復(fù)習(xí)并進(jìn)一步理解命題邏輯的基本概念。

［教學(xué)準(zhǔn)備］

［教學(xué)方法］講述法

［課時(shí)安排］二課時(shí)。

［教學(xué)過程］

講述：

復(fù)習(xí)并示例：判斷是否式命題，如果是，則符號(hào)化。

1)922+97+1；

2)x+5>6

3)理發(fā)師只給所有那些不給自己理發(fā)的人理發(fā)；

4)李蘭現(xiàn)在在宿舍或在圖書館里；

5)藍(lán)色和黃色可以調(diào)配成綠色；

6)如果晚上小王做完了做業(yè)并且沒有其他事情，他就看電視或看電影。

問題：

在6)中獲得一個(gè)長(zhǎng)串的字符串，這里當(dāng)然表示了一個(gè)命題，但是不是任何一個(gè)字符串

能表示一個(gè)命題呢？或者稱為命題形式呢？

命題形式：各種復(fù)合命題的符號(hào)化表達(dá)式，即為此命題的命題形式，它給出的是復(fù)合

命題及其簡(jiǎn)單命題之間真值關(guān)系的邏輯骨架。

實(shí)際上，只有那些稱為“公式”的字符串才能表示命題。而一個(gè)公式還必須給定一個(gè)

解釋，才能得知具體的含義。

板書

1.2合式公式及其解釋

講述：

首先自然先要了解什么公式。

板書：

一合式公式

命題形式必定是合式公式。

1)合式公式：

(1)p,q,r,...,1,0是合式公式；

(2)如果A是合式公式，則rA也是；

(3)如果A和B是合式公式，則由邏輯聯(lián)結(jié)詞聯(lián)結(jié)A和B的符號(hào)串也是；

7

(4)有限次應(yīng)用(1)-(3)構(gòu)成的符號(hào)串才是合式公式。

講述：

上述定義方法稱為遞歸定義法，遞歸法定義是離散數(shù)學(xué)中常用的方法。其中，1)是遞

歸定義的基礎(chǔ)，直接規(guī)定簡(jiǎn)單的內(nèi)容；2),3)是遞歸定義的歸納，規(guī)定了是由簡(jiǎn)單到復(fù)雜的

過程；4)是遞歸定義的界限，規(guī)定了滿足前述1)?3)條件的最小范圍。

板書：

遞歸定義法：遞歸基礎(chǔ)、遞歸歸納、遞歸界限

講述

在一個(gè)復(fù)雜的公式中，為了避免歧義需要引進(jìn)許多的括號(hào)，但如果括號(hào)太多會(huì)使人眼

花繚亂，如((pA(qvr))—((pvq)A(rvs))),共有6對(duì)括號(hào)，書寫簡(jiǎn)單，可以省略括號(hào)

板書：

省略括號(hào)的約定：

(1)公式最外層的括號(hào)可以省略；

(2)規(guī)定聯(lián)結(jié)詞的運(yùn)算優(yōu)先級(jí)別由高到低是：「、人、v、V,一、一，若無括號(hào)，優(yōu)先

級(jí)高的先運(yùn)算；

(3)若同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括號(hào)，則按從左到右的順序運(yùn)算。

講述：

按照上述約定,((pA(qvr))-?((pvq)A(rvs)))省略■了三對(duì)括號(hào)簡(jiǎn)化為pA(qvr)->(pvq)A(rvs)o

省略括號(hào)只是讓公式書寫簡(jiǎn)便，但并不能改變起復(fù)雜性。

示例

(1)((g-4)八(夕-r))-?(pVr))

p、g是公式，S—q)是公式；外,,是公式，(qf)是公式；((p->g)A(qf))是公式；p、

，是公式，(pVr)是公式；(((pfq)八(qfr))r))是公式。

這樣一個(gè)命題公式的形成過程簡(jiǎn)單表述為：

p,q,(pfq);q,r,(?->廠)；((p->?)A(9->r));p,r,(pVr)；(((p-?q)A(qf))->(p

Vr))?

(2)((p八

p，q，(p八q);q，r,qr不是；((pAq)f")不是。

講述：

顯然，有些公式的字符串很長(zhǎng)，有些很短，甚至只有單個(gè)字母，這樣公式的復(fù)雜性必

然有所不同，為了描述這種復(fù)雜性，引入公式層次來描述。

板書：

二合式公式的層次：

(1)如果A是單個(gè)命題常項(xiàng)或命題變項(xiàng)p,q,r,s,...,0,1,則稱A是0層公式；

(2)稱A是n+l(n20)層公式，是指A符合下列情況之一：

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

(b)A=(AAB),其中B、C分別是i層和j層公式，且11=11^(q)；

(c)A=(AvB),其中B、C的層次同(b)；

(d)A=(AvB),其中B、C的層次同(b)；

(e)A=(A-B),其中B、C的層次同(b)；

(f)A=(AcB),其中B、C的層次同(b)；

(3)若A的最高層次為k,則稱A是k層公式。

8

講述:

敘述中出現(xiàn)的“=”即為通常意義上的等號(hào)。

上述兩個(gè)定義中，不僅有p,q,r,s,…,0,1等，而且引入了大寫的A、B、C等代表任意

的合式公式，不同于p,q,r,…，及聯(lián)結(jié)詞構(gòu)成的表示某個(gè)具體的公式，兩者是命題邏輯中不

同層次上的語(yǔ)言。

示例：

(l)(p^WA(pV5))(2)[4](pVs)

(l)p,s是0層公式，p\/s是1層公式;，是0層公式,rA(p\/s)是2層公式；是0層

公式，但是1層公式；(p^^)V(rA(pV5))是3層公式。公式層次是3。

(2)g是0層公式,是1層公式；p,s是0層公式，p\Js是1層公式;->(pVs)是2層

公式；但Vs)不是公式。

講述：

一般來說，一個(gè)含有命題變項(xiàng)的命題形式，其真值是不確定的。只有給其每個(gè)命題變

項(xiàng)都指定確定的真值，命題形式才會(huì)有確定的真值。

給定一個(gè)真值，就是給命題變項(xiàng)一個(gè)賦值，相當(dāng)于給定一個(gè)日常語(yǔ)言中某個(gè)具體的句

子，即給定一個(gè)解釋。

板書：

三真值賦值

令A(yù)是命題形式，PI，P2,…Pn是出現(xiàn)在A中的所有命題變項(xiàng)，給PI，P2,…Pn指派一組

真值，稱為對(duì)A的一個(gè)賦值，也稱為一個(gè)解釋。

成真賦值：若一個(gè)賦值使得A的真值為真，此賦值滿足A；

成假賦值：若一個(gè)賦值使得A的值為假，此賦值不滿足A,

一個(gè)含有n個(gè)命題變項(xiàng)的命題形式，共有2n個(gè)賦值。

示例

例已知A是含命題變項(xiàng)p,q,r的命題形式，其成真賦值為000,010,101,求「A的成真

賦值和成假賦值。

「A的成真賦值為:001,011,100,110,111；成假賦值為:000,010,101.

例已知A、B是含命題變項(xiàng)p,q,r的命題形式，A成真賦值為000,Oil,111,B成真

賦值為000,010,100，求N—B、B的成真賦值。

Z—B：000,001,010,100,101,110,111

Z—B：000,001,101,110

講述：

上面是用具體的真值來指定，如果用另外的命題形式來指定，這時(shí)再不能稱為賦值了，

這稱為替換。

板書：

替換實(shí)例：用命題形式B1,B2,…Bn分別替換命題形式A中的命題變項(xiàng)必，P2,…Pn得到

的新的命題形式。

示例：

例如,pf(->p->q),以p—q替換p,以r替換q,則得到原式的一個(gè)替換實(shí)例為(p->q)f(->

(pfq)f)。

講述：

我們知道一個(gè)公式有多個(gè)賦值，一般來說既有成真賦值，又有成假賦值，但完全可能

9

只有成真賦值，或全是成假賦值，

根據(jù)這種不同，我們將公式分成不同類型。

板書：

命題形式的分類：

①重言式：值總是為真的命題形式。

講述：

如果一個(gè)蘊(yùn)涵式AfB是重言式，則記作A=B,表示由A可推導(dǎo)出B；同樣如

果一個(gè)等價(jià)式A―B是重言式，則記作AoB,表示A和B等值。

注意：=和=不是邏輯聯(lián)結(jié)詞，它們表示的分別是邏輯推理和邏輯等值運(yùn)算，下

面的章節(jié)將分別討論。

板書：

②矛盾式：值總是為假的命題形式。

③可滿足式。

講述：

從定義看來，重言式也是可滿足式，不過還是將命題形式分成三類：重言式、矛盾式、

可滿足式；即可滿足式不包含重言式。這種分類主要是為了體現(xiàn)重言式的重要性，實(shí)際上

在命題邏輯中公理、定理都是重言式，在自然推理的過程中，一個(gè)正確的推理也必須是重

言式。

板書：

設(shè)A命題形式，則

(1)若A是重言式，則A的任何替換實(shí)例都是重言式；

(2)若A是矛盾式，則A的任何替換實(shí)例都是矛盾式；

示例：

例合式公式⑦八g)V-<p/\q)、仍八都是p7rp的一個(gè)替換實(shí)例，

而是重言式，所以它們也是重言式。

板書：

1.3真值表和真值函數(shù)

四真值表

1)定義：命題形式在其命題變項(xiàng)取所有可能真值時(shí)對(duì)應(yīng)的真值列成的表。

講述：

所有命題變項(xiàng)取一組值，即是命題形式的一個(gè)煦值，所以真值表包含了所有賦值情況

下的公式所取得的值。

而一個(gè)賦值使得公式為真，就稱為成真賦值，為假就是成假賦值，所以從真值表可以

直接獲得一個(gè)命題公式的成真賦值、成假賦值。

板書：

2)構(gòu)成方法：

①找出給定命題形式中的所有命題變項(xiàng)，列出所有可能的取值：

10

②由低到高列出命題形式的各層次；

③計(jì)算各層次的的值，直至最后計(jì)算命題形式的值。

示例

例1.16構(gòu)造合式公式(pv(p八q))(pVq)的真值表:

真值表：

pqp/\qpV(pAq)pVqTpVq)(pV(pAq))-TpVq)

0000011

0100101

1001100

1111100

講述：上述真值表的構(gòu)成方法中，如果公式層次比較高，則表的寬度將變得很寬，甚至無

法寫下，因此可采用另一種形式，

板書：

②按照公式形成過程，標(biāo)出各層對(duì)應(yīng)的聯(lián)結(jié)詞所對(duì)應(yīng)的真值；

③直至最后計(jì)算命題形式的值。

示例：

pq(pV(pAq))-?(pVq)

0000110

0100101

1010001

1111001

步驟②?③②?

板書：

五真值函數(shù)：

一個(gè)n元真值函數(shù)是指F：{0,1}"f{(),1},(n》l),即此函數(shù)以n個(gè)命題變項(xiàng)為變

元，其定義域和值域均由真、假兩值構(gòu)成。

講述：

真值函數(shù)同樣可以用真值表表示，這是真值函數(shù)在其命題變項(xiàng)所有可能取值下得到的值

列成的表。對(duì)于n個(gè)命題變項(xiàng)，可能的賦值有2n個(gè)。對(duì)于每個(gè)賦值，真值函數(shù)的取值

又有真、假兩種可能。因此，對(duì)于n個(gè)命題變項(xiàng)來說，它們可以構(gòu)成的不同的其值函數(shù)

有22"個(gè)。

示例:

11

如n=0,兩個(gè)0元函數(shù)為0,l;n=l,有四個(gè)一元真值函數(shù),n=2時(shí)有16個(gè)，下表中列出其中

的幾個(gè)：

PqFGHRS

0000111

0100101

1001001

1101111

F：-.(p^q)Aq-?(Pvrp)A-.(qv-.q)

G:pv(qv->q)PA(qv-.q)

H:pfqTPvq)

R:p<->q

s：(pfq)Vp

復(fù)習(xí)并板書：

本章要點(diǎn)：

?命題：或真或假的陳述句，不能又是真又是假；

?復(fù)合命題：用聯(lián)結(jié)詞將若干個(gè)簡(jiǎn)單陳述句組合成的復(fù)合陳述句；

?合取式：p/\Q,邏輯“與"，p、q同時(shí)為真，合取式才為真；

?析取式：pVq,邏輯“或”，p、g同時(shí)為假，析取式才為真；

?異或式：pWy,p、g不同時(shí).異或式才為真；

?蘊(yùn)涵式：piq,前件p為真后件g為假時(shí)條件式才為假：

?等價(jià)式：pcq,P、夕相同時(shí)等價(jià)式才為真，也稱"同或"；

?合式公式：遞歸定義參見定義1.7；

?公式層次：遞歸定義參見定義1.8；

?賦值：給合式公式中的所有命題變項(xiàng)指定一組真值，有成真賦值、成假賦值；

?公式分類：重言式、矛盾式和可滿足式；

?替換實(shí)例：用多個(gè)命題公式分別處處替換命題公式A中對(duì)應(yīng)命題變項(xiàng)所得新的命題公

式；

?真值表：命題形式/在其所有可能的賦值下取得的值列成的表；

?〃元真值函數(shù)：F:{0,1}0-{0,1}(?>1)?

作業(yè)：

習(xí)題1.82),4),6),8)

習(xí)題1.9H,S

習(xí)題1.41),3),5),7)

習(xí)題1.5

習(xí)題1.61),2)

習(xí)題1.7

12

2.1等值關(guān)系及聯(lián)結(jié)詞全功能集

［教學(xué)重點(diǎn)］等值關(guān)系及演算的規(guī)則

［教學(xué)目的］1：使學(xué)生了解等值算是邏輯理論的一個(gè)基本內(nèi)容。

2：理解等值關(guān)系的含義，并理解等值式模式及其重要性。

3：理解并熟記等值演算的規(guī)則

4：理解全功能集的含義記應(yīng)用。

［教學(xué)準(zhǔn)備］

［教學(xué)方法］講述法

［課時(shí)安排］二課時(shí)。

［教學(xué)過程］

講述：

前面已經(jīng)提到，等價(jià)式A-B為重言式，記為AoB,稱為等值關(guān)系。并提到這是邏

輯理論的一個(gè)基本內(nèi)容。

本章將主要討論等值關(guān)系的有關(guān)內(nèi)容，本節(jié)首先討論了解什么等價(jià)關(guān)系，并詳細(xì)闡述

等值演算的各種規(guī)則，然后再談?wù)劼?lián)結(jié)詞的有關(guān)問題。

板書：

第二章命題邏輯等值演算

'等值關(guān)系

1概念：

如果兩個(gè)邏輯形式對(duì)其中的命題變項(xiàng)的任何取值，都具有相同的值，則稱它們是相

等的。另一種說法即為前面所提到的，A、B等值是指等價(jià)式A-B為重言式，記為AoB。

講述：

兩個(gè)命題形式是否等值可以通過真值表來判斷或驗(yàn)證。下面給出一些常用的等值式,

其中很多正是通常所說的的布爾代數(shù)或邏輯代數(shù)的主要組成部分。

板書:

2各種等值關(guān)系模式：(只列出部分)

(1)雙重否定律：A=「「A

(2)等幕律:(2a)Ao(AAA)(2b)Ao(AvA)

(3)交換律：(3a)(AAB)O(BAA)(3b)(AVB)O(BVA)

(4)結(jié)合律：(4a)((AAB)AC)?(AA(BAC))(4b)((AVB)VC)O(AV(BVC))

(5)分配律：(5a)(AV(BAC))O((AVB)A(AVC))(5b)(AA(BVC))<=>((AAB)V(AAC))

(6)德?摩根律:(6a)-I(AAB)(―iBv—iA)(6b)-i(AvB)<z>(―IBA-iA)

(7)吸收律：(7a)(AV(AAB))OA(7b)(AA(AVB))?A

(7c)(AV(-.AAB))?AVB(7d)(AA(->AVB))<=>AAB

(8)零律：(8a)(Avl)o1(8b)(AAO)O0

(9)同一律:(9a)(AvO)oA(9b)(AA1)<=>A

(10)排中律:(Av―iA)1

13

(11)矛盾式：(AMA)OO

(12)蘊(yùn)涵等值式：(AfB)oJAvB)

(13)等價(jià)等值式：(AcB)o((A->B)A(BfA))

(14)假言易位：(A-B)o(「Bf「A)

(15)等價(jià)否定等值式：(A—B)o(「A>B)

(16)歸謬律：((A—B)A(A-[B))o-1A

(17)香農(nóng)定理：

(「尸(X],%2,X",1,0，人,v))OF,0,1,V,A))

示例：香農(nóng)定理應(yīng)用

對(duì)于公式…,p“,0,1,八，V)，完全可能省略了括號(hào)，這時(shí)應(yīng)用香農(nóng)定理時(shí)要

注意將省略的括號(hào)添加上，否則等值演算會(huì)出問題。

如：-.(pV^Ar)o->(/?V(^Ar))<=>但如果不將省略的括號(hào)添上，就演

算成顯然該式是先運(yùn)算而不是先運(yùn)算結(jié)果不正確。

板書：

(18)對(duì)偶定理

對(duì)偶式：

公式A僅含有聯(lián)結(jié)詞「，A,V,則將A中的人，v,0,1分別換以v,A,1,0

后得到的公式為A的對(duì)偶式A*。

a)香農(nóng)定理用對(duì)偶式表示即為：

(「E(X|,…,X“))O(尸*(7],72，…，))

b)如果AoB,則A*oB*。(對(duì)偶定理)

注意(17)(18)中的A、B、F均僅含有聯(lián)結(jié)詞「，A,V。

示例：類似香農(nóng)定理應(yīng)用，也要注意括號(hào)問題。

講述：

根據(jù)已知的等值式，可以推演出另外許多的等值式，這種推演過程稱為等值演算。

板書：

3等值演算

講述：在等值演算時(shí)，除了要用到上面給出的等值式外，通常還用到一些重要的演算規(guī)則

板書：

(1)等值式模式

(2)重:言式替換規(guī)則

(3)置換規(guī)則

置換規(guī)則：設(shè)中是含有公式A的命題形式，3是用公式B置換①中的公式A(不一定是

每一處)而得到的命題形式，如果AoB,則①。中。

示例等值演算

例證明AfBVC=AA「BFC

講述：

證明的方法當(dāng)然可以用真值表方法，但是直接應(yīng)用等值式及替換和置換規(guī)則通常會(huì)簡(jiǎn)

單的多。

證明：A->BvCo「Av(BvC)蘊(yùn)涵等值式

14

=(-iAvB)vC結(jié)合律

—?(AA—iB)vC德?摩根律

u>(AA「B)-C置換規(guī)則和蘊(yùn)涵等值式

邏輯等值演算不僅僅停留在符號(hào)級(jí),總要用來解決實(shí)際問題，如簡(jiǎn)化語(yǔ)句，確定?些

命題的真值等等，可以首先符號(hào)化命題，然后由已知條件列出這些命題應(yīng)該滿足的方程組,

從而達(dá)到要求。

例化簡(jiǎn)語(yǔ)句：“情況并非如此：如果他不來，那么我也不去”。

解：設(shè)p:他來，q：我去；上述語(yǔ)句符號(hào)化為

「(「pT「q)將詞進(jìn)行等值化簡(jiǎn)得

-!(->p-?-.q)=-i(-upv->q)

0r(Pv-.q)

<=>-ipAq

化簡(jiǎn)后語(yǔ)句為：“我去了，而他每來”。

例2.3小李或小張是先進(jìn)工作者；如果小李是先進(jìn)工作者，你是會(huì)知道的；如果小張

是先進(jìn)工作者，小趙也是；你不知道小李是先進(jìn)工作者，問誰(shuí)是先進(jìn)工作者。

解：設(shè)p:小李是先進(jìn)工作者；q:小張是先進(jìn)工作者；

r你知道小李是先進(jìn)工作者；s:小趙是先進(jìn)工作者

貝II(pvq)A(p->r)人(q—s)八一>r=1

其中左邊=(pvq)A(-,pvr)A(-,qvs)A->r

=(pvq)A(->qvs)A((->pvr)A-Ir)

<=>(pvq)A(->qvs)A(->PA->r)(吸收律)

=(-ipA(pvq))A(-.qvs)A->r

o(->pAq)A(->qvs)A->r

=->pA(qA(-.qvs))A->r

o-.pA(qAs)A->r

0->pAqAsA->r

o1

顯然p=O,q=l,s=l,r=O；即小張和小趙是先進(jìn)工作者。

講述：

從前面給出的等值式模式可以發(fā)現(xiàn)，常用的六種聯(lián)結(jié)詞不是相互獨(dú)立的，在表示邏輯

關(guān)系時(shí)并不都是缺一不可的。其中有些聯(lián)結(jié)詞的邏輯功能可以用其它聯(lián)結(jié)詞代替，如：

A->B-iAVB,

46B=(4-B)A(8?)o(-v4V8)A(-.5VJ),

A￥B=(4八V(FAB)。

這里我們討論聯(lián)結(jié)詞集合問題。我們把兒個(gè)聯(lián)結(jié)詞放在?起，稱為一個(gè)聯(lián)結(jié)詞集合。

板書：

二聯(lián)結(jié)詞的全功能集

講述：

正如前面所講述的，在聯(lián)結(jié)詞集合中，?般?些聯(lián)結(jié)詞可以用另外的聯(lián)結(jié)詞來表示，

這就是說有冗余聯(lián)結(jié)詞和獨(dú)立聯(lián)結(jié)詞之分。

聯(lián)結(jié)詞組成?個(gè)集合，如果一個(gè)聯(lián)結(jié)詞可由集合中的其它聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞

15

為冗余聯(lián)結(jié)詞，否則稱為獨(dú)立聯(lián)結(jié)詞

板書：

1冗余聯(lián)結(jié)詞，獨(dú)立聯(lián)結(jié)詞

冗余聯(lián)結(jié)詞是可以由集合中的獨(dú)立聯(lián)結(jié)詞來定義。

講述：

而個(gè)聯(lián)結(jié)詞集合稱為全功能的是指任意真值函數(shù)僅用此集合中聯(lián)結(jié)詞的命題形式就

可以表示。如果全功能聯(lián)結(jié)詞集合不含冗余聯(lián)結(jié)詞則是極小全功能。

板書：

2全功能集及極小全功能集：

全功能集：任意真值函數(shù)僅用此集合中聯(lián)結(jié)詞的命題形式就可以表示

極小全功能集：不含冗余聯(lián)結(jié)詞的全功能集。

講述

一個(gè)聯(lián)結(jié)詞集合到底是不是全功能集，甚至是否極小全功能集，必須通過證明，即通

過證明任何的真值函數(shù)都可用該集合中的聯(lián)結(jié)詞表示。

板書：

(1)任何真值函數(shù)都能表示；

(2)定理：如果一個(gè)全功能集&中的所有聯(lián)結(jié)詞都可由一個(gè)聯(lián)結(jié)詞集合S2定義，則

$2也是全功能集

示例：

｛r,A,V｝是全功能集，

｛「,A｝,｛「,V｝,｛f｝都是極小全功能集

講述：

｛「，八｝,｛「，V｝都是極小全功能集，等價(jià)聯(lián)結(jié)詞定義蘊(yùn)涵和合取兩個(gè)聯(lián)結(jié)詞所描述的

一種命題，類似，也用一個(gè)聯(lián)結(jié)詞分別定義，

板書：

3新聯(lián)結(jié)詞

非聯(lián)結(jié)詞T

非聯(lián)結(jié)詞J

講述：

由于=-1gAp)=pTp

p/\q<=>-?-,(/?A!?)<=>-<=>(pTq)T(pTq),

->q)0-1PT-1go(pfp)T(qfq)，

即八，v都可由T定義，因?yàn)椋?八，V｝是全功能集，所以｛T｝也是全功能集。又由

于其中有且僅有-個(gè)聯(lián)結(jié)詞，故｛T｝是極小全功能集。

同理可證｛5｝也是極小全功能集，其中

—<p=->(pV/?)=p，p,

p\!q=->->(/?V^)==(pJq)J(P54)，

p[\q==仍Jp)J(q%)。

板書：

｛?｝>｛“都是極小全功能集。

講述：

上述等值式都是成對(duì)出現(xiàn)的，有著對(duì)偶的特性，事實(shí)上正是對(duì)偶的，

16

4對(duì)偶式的擴(kuò)展

A*(pi,p2,0,1,A,V,T,—O/(P1，P2,...,pn,1,0,V,A,4<,T)?示例：

示例

l)g/\q)T(ipA^Ar)2)(pJq)八(f/T-ig)

1)(pVq)1(-ipV^rVr)2)(pT4)VJpJrO

作業(yè):

習(xí)題2.21)(1)(4)(5);2)(2)(3)(6)2.8

17

2.3范式

［教學(xué)重點(diǎn)］范式的定義和應(yīng)用

［教學(xué)目的］1：使學(xué)生引入范式的意義。

2：理解合取范式和析取范式的概念。

3：熟練應(yīng)用主合取方式和主析取方式的求法及互化

4：理解卡諾圖及其在等值演算中應(yīng)用。

［教學(xué)準(zhǔn)備］

［教學(xué)方法］講述法

［課時(shí)安排］二課時(shí)。

［教學(xué)過程］

講述：

判斷兩個(gè)命題公式是否等值，前面已經(jīng)介紹了真值表法和等值演算法。相比較而言，

等值演算法可能簡(jiǎn)單得多，特別是在命題變項(xiàng)數(shù)目較多的時(shí)候。然而有時(shí)想將?個(gè)命題形

式等值變換成另一個(gè)，卻可能很難找到適當(dāng)?shù)倪^程。

一個(gè)有效的方法式將兩個(gè)命題公式等值演算某種標(biāo)準(zhǔn)形式，然后在比較，這種標(biāo)準(zhǔn)就

稱為范式。

板書：

2.3范式

1基本概念：

文字：命題變項(xiàng)及其否定的統(tǒng)稱。

簡(jiǎn)單析取式：由有限個(gè)命題變項(xiàng)及其否定構(gòu)成的析取式。

一個(gè)簡(jiǎn)單合取式是矛盾式，當(dāng)且僅當(dāng)其含有一個(gè)文字及其否定

簡(jiǎn)單合取式：由有限個(gè)命題變項(xiàng)及其否定構(gòu)成的合取式.

一個(gè)簡(jiǎn)單析取式是重言式，當(dāng)且僅當(dāng)其含有一個(gè)文字及其否定

講述：

示例例如pAq,p/\q/\->p,p/\q/\r/\s等都是簡(jiǎn)單合取式，pVq,p\Jp7pVr

等都是簡(jiǎn)單析取式。單個(gè)文字既可看作是簡(jiǎn)單合取式，也可看作是簡(jiǎn)單析取式。

板書：

2析取范式與合取范式

A定義

析取范式：簡(jiǎn)單合取式的析取

合取范式：簡(jiǎn)單析取式的合取

示例：

板書：

B性質(zhì)

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

C范式的獲得

講述：

18

任何一個(gè)命題形式都可以等值演算成合取范式和析取范式，

板書：

具體步驟：

1)利用等值式模式將其它聯(lián)結(jié)詞轉(zhuǎn)化成A,V；

2)簡(jiǎn)化雙重否定號(hào)，并利用香農(nóng)定理將所有「寫到文字里；

3)利用分配律，將4最終變成合取范式和析取范式。

示例

例通過等值演算將((pVg)-r)-p化成合取范式和析取范式。

解：((pVg)->r)=->(-1(/?Vq)Vr)Vp

=((pV^)A-nr)Vp

=V(q/\f)Vp(析取范式)

<=>((/?A->r)Vp)V(q八一>r)

opV(q/\f)(析取范式)

o(p'Vq)A(pY「r)。(合取范式)

板書

方法2:

1)連續(xù)利用展開定理，轉(zhuǎn)化成「,八，V形成的公式

2)最后應(yīng)用分配定理，將一個(gè)命題形式等值演算成范式形式。

示例：

講述：

一個(gè)命題形式的析取范式不是唯一的，同樣，合取范式也不是唯一的。這就給我們想通

過比較標(biāo)準(zhǔn)形式的異同判斷命題形式是否等值的要求帶來困難，因此不能將析取范式和合

取范式作為標(biāo)準(zhǔn)形式。

板書

1)主析取范式與主合取范式：

A極小項(xiàng)：

在含有〃個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中，每個(gè)命題變項(xiàng)作為文字出現(xiàn)且僅出現(xiàn)一次。

主要性質(zhì)：

(1)每個(gè)極小項(xiàng)的成真賦值僅有一個(gè)；

(2)兩個(gè)不同的極小項(xiàng)的合取構(gòu)成的命題形式為矛盾式；

(3)所有個(gè)極小項(xiàng)的析取構(gòu)成的命題形式為重言式。

講述：

為了書寫方便，通常用m,表示某個(gè)極小項(xiàng)，下標(biāo)i的規(guī)定如下：極小項(xiàng)的命題變項(xiàng)

按一定的次序排好后，下標(biāo)i化為二進(jìn)制后正是該極。這樣每個(gè)師與其成真賦值建立了?

一對(duì)應(yīng)的關(guān)系。

示例：

三個(gè)變量的極小項(xiàng)m7=pAqAr,m5=pA->q人r,

B主析取范式

極小項(xiàng)的析取

性質(zhì)：

(1)如mi是主析取范式A的一個(gè)極小項(xiàng)，則mi的成真賦值一定是A的成真賦值；

(2)A、B是相同的n個(gè)命題變項(xiàng)的主析取范式，則AvB將包含A和B的所有極小項(xiàng);

19

AAB將包含A和B的所有的公共極小項(xiàng);

(3)「A包含主析取范式A的所有極小項(xiàng)之外的全部極小項(xiàng)。

表示：

(1)命題形式

(2)簡(jiǎn)寫:

板書：

mivmjVmk

v(mj,mj,m?；颉?m1,mj,mk)

(3)卡諾圖法

示例講述：

卡諾圖的構(gòu)成規(guī)律：

1)含有〃個(gè)命題變項(xiàng)，若〃是偶數(shù)，則斜線左右命題變項(xiàng)數(shù)目相同；若〃是奇數(shù)，斜

線左邊命題變項(xiàng)的數(shù)目多一個(gè)；按照排列順序，依次從外到里，從斜線左邊到右邊；

2)命題變項(xiàng)的賦值，位于最外層的總是從上往下、從左到右依次為0,1；位于里層的，

則按照其相鄰?fù)鈱拥南噜弮蓚€(gè)賦值0,1,從上往下、從左到右依次擴(kuò)展為0,1,1,0。

講述:

卡諾圖可用表示主析取范式，也可以用于化簡(jiǎn)命題形式的表達(dá)式:

板書：

用于化簡(jiǎn)表達(dá)式：利用卡諾圖化簡(jiǎn)，將相鄰的“1”合并。

相鄰：

(1)任何水平和垂直方向上幾何相鄰的單元；

(2)圖形兩端的單元；

(3)關(guān)于對(duì)稱軸對(duì)稱的單元；

示例：

化簡(jiǎn)V(0,1,4,5,6,11,12,14,16,20,22,28,30,31)

板書：

唯一性

任何一個(gè)命題形式都存在一個(gè)且唯一一個(gè)主析取范式或

主合取范式

講述：

任何一個(gè)命題形式可以等值演算成合取范式和析取范式。

板書：

演算步驟:

20

(1)等值演算變換成析取范式，不妨設(shè)S2V...VS?(?>1)?

(2)不是極小項(xiàng)的簡(jiǎn)單合取式，如不含有p的文字，則等值演算：

BQ/\1<=>5,A(pV-i/j)■?V(S,A->p),

其所缺少的命題變項(xiàng)重復(fù)上述過程，直到所有簡(jiǎn)單合取式都是極小項(xiàng)為止。

(3)將所有相同的極小項(xiàng)合并。

板書：

C主合取范式

板書：

極大項(xiàng)

對(duì)比極小項(xiàng)講述：極大項(xiàng)定義，性質(zhì)

在含有〃個(gè)命題變項(xiàng)的簡(jiǎn)單析取式中，每個(gè)命題變項(xiàng)作為文字出現(xiàn)且僅出現(xiàn)一次。

性質(zhì)：

1)每個(gè)極大項(xiàng)的成假賦值有且僅有一個(gè)；

2)兩個(gè)不同的極大項(xiàng)的析取構(gòu)成的命題形式為重言式；

3)所有極大項(xiàng)的合取構(gòu)成的命題形式為矛盾式。

簡(jiǎn)單表示：

三個(gè)變量的極大項(xiàng)M7=->pv-.qv-1r,M5=-ipvqv->r,

板書

主合取范式：極大項(xiàng)的合取

對(duì)比主析取范式講述：

性質(zhì)，表示，唯一性，演算過程

板書：

表示：

MiAMjAMk

人(i,j,k)或n(i,j,k)

唯一性

演算過程

講述：

我們已經(jīng)討論了兩個(gè)主范式，在演算過程中，為了方便，可以以任何一種范式作為基

礎(chǔ)，實(shí)際上兩種范式是相通的。

板書：

D兩種主范式的互換

和M之間的關(guān)系：

M,0—i/n,,m*。一>Mg

主范式關(guān)系：

主析取范式不包含的極小項(xiàng)標(biāo)號(hào)正是其主合取范式所包含的極大項(xiàng)標(biāo)號(hào)。

A(i|,ji,=A(i2,)2,k2,...)(ii#i2,小刊2,k|^k2,...)

示例：

m2Vm4Vm5Vm6Vm7

0MoAMiAM3

21

講述：

最后，復(fù)習(xí)一下本章所講述的內(nèi)容。

復(fù)習(xí)講述，板書：

本章要點(diǎn)：

?等值：兩個(gè)命題形式具有相等的值，或等價(jià)式為重言式；

?等值式模式：常用的等值式；

?等值演算：由已知等值式推演新的等值式的過程；

?等值演算常用規(guī)則定理：等值式模式、替換規(guī)則、置換規(guī)則、香農(nóng)定理、對(duì)偶定理、展

開定理；

?與非聯(lián)結(jié)詞色命題P與4的否定；

?或非聯(lián)結(jié)詞L命題p或4的否定；

?對(duì)偶式：僅含有聯(lián)結(jié)詞「，A,和J的命題公式，將其中的八，V,U,0,1分別換以V,

0后得到的公式稱為原式的對(duì)偶式；

?聯(lián)結(jié)詞全功能集：任何真值函數(shù)都可僅用其中的聯(lián)結(jié)詞表示；

?冗余聯(lián)結(jié)詞：可用其它聯(lián)結(jié)詞定義的聯(lián)結(jié)詞；

?極小全功能集：不含冗余聯(lián)結(jié)詞的全功能集；

?文字：命題變項(xiàng)及其否定；

?簡(jiǎn)單合取式：有限個(gè)文字的合取式；

?極小項(xiàng)：每個(gè)命題變項(xiàng)形成的文字出現(xiàn)且僅出現(xiàn)一次的簡(jiǎn)單合取式；

?簡(jiǎn)單析取式：有限個(gè)文字的析取式;；

?極大項(xiàng)：每個(gè)命題變項(xiàng)形成的文字出現(xiàn)且僅出現(xiàn)一次的簡(jiǎn)單析取式；

?范式：有限個(gè)簡(jiǎn)單析取式的合取為合取范式，有限個(gè)簡(jiǎn)單合取式的析取為析取范式；

?主范式：極小項(xiàng)的合取范式為主合取范式，極大項(xiàng)的析取范式為主析取范式。

?獲得主范式方法：等值演算法，真值表獲得成真賦值法、卡諾圖法。

?范式特性：范式的多樣性和主范式的唯一性；

?卡諾圖：參見圖2.1；

作業(yè)：

習(xí)題2.10(2)(3)

習(xí)題2.12

22

第三章命題邏輯自然推理

［教學(xué)重點(diǎn)］推理系統(tǒng)及證明的構(gòu)造，歸繆法、CP規(guī)則

［教學(xué)目的］1:使學(xué)生理解推理的含義。

2：了解推理系統(tǒng)，理解并識(shí)記各推理規(guī)則。

3：熟練掌握自然推理系統(tǒng)P