離散數(shù)學第1章邏輯代數(shù)（上）：命題演算離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結詞與命題公式1.2邏輯等價式和邏輯蘊涵式

1.3范式第1章邏輯代數(shù)（上）：命題演算1.4命題演算消解原理離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞例1.1（1）雪不是白的（并非雪是白的）。（2）今晚我去商店或者去打球。（3）我看完了書，并且做完了作業(yè)。（4）他去了學校，又去了工廠。（5）你織布，我耕田。（逗號也是一種連接）（6）如果我有錢，那么我替你付學費。（7）偶數(shù)a是質數(shù)，當且僅當a=2（a是常數(shù)）。1.1邏輯聯(lián)結詞與命題公式概念：邏輯聯(lián)結詞或命題聯(lián)結詞——聯(lián)接判斷的語言成分。原子命題或原子——不含邏輯聯(lián)接詞的命題。復合命題——原子命題和邏輯聯(lián)接詞共同組成的命題。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞否定詞：“并非”，用符號（或~）表示。

設p表示一命題，那么

p

表示命題p的否定。

p真時p假，而p假時p真。1.1邏輯聯(lián)結詞與命題公式pp0110例1.2

p：雪是白的。

p：并非雪是白的、雪不是白的。（假）

p：整數(shù)都是自然數(shù)。

p：并非整數(shù)都是自然數(shù)（整數(shù)不都是自然數(shù)）。真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞合取詞：“并且”，用符號∧表示。

設p，q表示兩命題，那么p∧q表示合取p和q所得的命題，即p和q同時為真時p∧q真，否則p∧q為假。1.1邏輯聯(lián)結詞與命題公式例1.3

p：你去邊疆。

q：我去海島。

p∧q：你去邊疆并且我去海島。p：你織布。

q：我耕田。

p∧q：你織布，我耕田。pq

p∧q001101010001真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞析取詞：“或”，用符號∨表示。設p，q表示兩命題，那么p∨q表示p和q的析取，即當p和q有一為真時，p∨q為真，只有當p和q均假時p∨q為假。1.1邏輯聯(lián)結詞與命題公式例1.4

p：今晚我看書。q：今晚我聽音樂。

p∨q：今晚我看書或者聽音樂。pqp∨q001101010111真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞“不可兼或”，用符號表示。當p和q都為真時pq卻為假。pqp

q0011010101101.1邏輯聯(lián)結詞與命題公式例1.4

p：吃蛋糕。q：吃冰激凌。

pq：或者吃蛋糕，或者吃冰激凌。（只吃一種零食）真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞蘊涵詞：“如果…，那么…”，用符號→表示。設p，q表示兩命題，那么p→q表示命題“如果p，那么q”。其中的p稱為蘊涵前件，q稱為蘊涵后件。1.1邏輯聯(lián)結詞與命題公式例1.5

p：我有錢。q：我替你付學費。

p→q：如果我有錢，那么我替你付學費。pqp→q001101011101真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞1.1邏輯聯(lián)結詞與命題公式實質蘊涵：不要求p→q中的p，q有什么關系，只要p，q為命題，

p→q就有意義。例如：“如果2+2=5，那么雪是黑的”是一個有意義的命題。實質蘊涵的數(shù)學應用：證明對任何集合A，

A：因為沒有任何對象x

，x(x為假)，故x蘊涵xA為真，即

A真。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.1邏輯聯(lián)結詞雙向蘊涵詞：“當且僅當”，用符號表示。設p，q為兩命題，那么pq表示命題“p當且僅當q”，“p與q等價”，即當p與q同真值時pq為真，否則為假。1.1邏輯聯(lián)結詞與命題公式例1.6

p

：△ABC

≌△A'B'C'

q

：△ABC與△A'B'C'的三邊對應相等。pqp

q001101011001真值表：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.2命題公式1.1邏輯聯(lián)結詞與命題公式符號化過程的最基本步驟：用拉丁字母p，q，r，s等表示具體命題，用f，t表示兩個特殊的常命題：常真命題和常假命題。命題常元：

p，q，r，s，f，t統(tǒng)稱為命題常元。命題變元：以“真、假”或“1，0”為取值范圍的變元，為簡單計，命題變元仍用p，q，r，s等表示。

(但不使用f，t)

離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.2命題公式1.1邏輯聯(lián)結詞與命題公式定義1.1命題公式的歸納定義：

(1)

命題常元和命題變元是命題公式，也稱為原子公式或原子。(2)

如果A，B是命題公式，那么(A),(A∧B),(A∨B),(A→B)，(AB)也是命題公式。(3)

只有有限步引用條款(1)，(2)所組成的符號串是命題公式。命題公式簡稱公式，常用大寫字母A、B、C等表示。

子公式：如果B是公式A中的字母相互毗連的一部分，且B自身為一公式，則B稱為公式A的子公式。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算約定：（1）公式最外層括號一律可省略。（2）聯(lián)結詞的結合能力強弱依次為

，(∧，∨)，→，結合能力平等的聯(lián)結詞采用左結合約定，當運算從左向右依次實施時，可省略其括號。1.1.2命題公式1.1邏輯聯(lián)結詞與命題公式例1.7

（1）((p→(q∧r)))是命題公式，表示為(p→q∧r)。（2）p→q∨(r∧qs)表示((p)→(q∨((r∧q)s)))離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.2命題公式1.1邏輯聯(lián)結詞與命題公式定義1.2

設公式A含有命題變元p1，p2，…，pn，稱p1，p2，

…，pn每一取值狀況為一個指派，用希臘字母，等表示，當A對取值狀況

為真時，稱指派弄真A，或

是A的弄真指派，記為(A)=1；反之稱指派弄假A，或是A的弄假指派，記為(A)=0。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.2命題公式1.1邏輯聯(lián)結詞與命題公式

p

q

r

q∧r

p→(q∧r)(p→(q∧r))

00001111

00110011

01010101

000100011111000100001110例1.8

作出公式(p→(q∧r))的真值表。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.3語句的形式化1.1邏輯聯(lián)結詞與命題公式例1.9

將下列語句形式化，并表示為命題公式(1)

我和他既是弟兄又是同學。

p∧q其中p：我和他是弟兄。q：我和他是同學。(2)

我和你之間至少有一個要去海島。

p∨q其中p：我去海島。q：你去海島。(3)

狗急跳墻。

p→q其中p：狗急了。q：狗跳墻。(4)

那只狗急了，跳墻了。

p∧q其中p：那只狗急了。q：那只狗跳墻了。形式化：用符號語言將自然語言語句符號化。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.3語句的形式化1.1邏輯聯(lián)結詞與命題公式

(5)

除非他來，否則我不同他談判。

pq或(p→q)∧(p→q)其中p：他來。q：我與他談判。(6)

如果他沒來見你，那么他或者是生病了，或者是不想見你。

p→(q∨r)其中p：他來見你，q：他生病，

r：他想見你。(7)

如果袁翼和王虎不都是傻子，那么他們倆都不會去。

(p∧q)→(r∧s)其中p：袁翼是傻子，q：王虎是傻子，

r：袁翼會去，s：王虎會去。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算

1.1.3語句的形式化1.1邏輯聯(lián)結詞與命題公式(8)

因為天下雨,所以地皮濕。

p→q

其中p：天下雨，q：地皮濕。(9)只要認真讀書，就能考出好成績；只有集中精力，才能認真讀書。

(p→q)∧(p→r)

其中p：認真讀書，q：考出好成績，r：集中精力。(10)

風雨無阻，我去北京。

(p∧q→r)∧(p∧q→r)∧(p∧q→r)∧(p∧q→r)

其中p：天刮風，q：天下雨，r：我去北京離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.1.3語句的形式化1.1邏輯聯(lián)結詞與命題公式語句形式化應注意的問題：要善于確定原子命題，不要把一個概念硬拆成幾個概念。要注意語句的語用，不同的語用有不同的邏輯含義。要善于識別自然語言中的聯(lián)結詞(有時它們被省略)。否定詞的位置要放準確。需要的括號不能省略;可以省略的括號，在需要提高公式可讀性時亦可不省略。注意“只要，就”“只有，才”的正確理解。

語句的形式化未必是唯一的。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.10

設p:“是偶數(shù)”，q:“是奇數(shù)”，r:“是質數(shù)”，s:“=2”，那么，可如下理解各命題公式：(1)p∨q

(是偶數(shù)或是奇數(shù))(2)p∧r→s

(若是偶質數(shù)，則=2)(3)p→(r→s)

(若是偶數(shù)，那么當是質數(shù)時，=2)(4)r∧s→q

(若是不等于2的質數(shù)，則為奇數(shù))(5)q∧┐s→r(若不是奇數(shù)且2，則不是質數(shù))(6)(q∨s)→r(若“是奇數(shù)與=2之一真”不成立，則非質數(shù))(7)r→(q∨s)(若是質數(shù)，則是奇數(shù)與=2之一真)(8)rq∨s(是質數(shù)當且僅當是奇數(shù)或=2)1.1.3語句的形式化1.1邏輯聯(lián)結詞與命題公式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.1重言式1.2邏輯等價式和邏輯蘊含式定義1.3如果對命題公式A中命題變元的一切指派均弄真A，那么，稱A為重言式

；重言式又稱永真式；如果至少有一個這樣的指派弄真A，那么，稱A為可滿足式，否則稱A為不可滿足式或永假式、矛盾式。例1.11

對任何公式A，

A∨A是重言式,A∧A是矛盾式。對任何原子命題p，p與p都是可滿足式。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算由表的最后一列可以看出，原式為重言式。1.2.1重言式可用真值表驗證重言式、矛盾式、可滿足式。例1.12

用真值表證明(p∨q)∧p→q為重言式。證：建立待證公式的真值表1.2邏輯等價式和邏輯蘊含式

p

q

p∨q

p

(p∨q)∧p(p∨q)∧p→q

0011

0101

0111

110001001111注意：用真值表驗證重言式時，表中任何一列都不能省略。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式定義1.4

當命題公式AB為永真式時，稱A邏輯等價于B，記為A╞╡B，它又稱為邏輯等價式。A╞╡B的理解：（1）AB是重言式。（2）A，B等值。當A真時B亦真，當A假時B也假；由A真可推出B真，且由B真可推出A真。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算重要的邏輯等價式:E1

A╞╡A

雙重否定律E2

A∨A╞╡A

，A∧A╞╡A

冪等律E3

A∨B╞╡B∨A

，A∧B╞╡B∧A

交換律E4

(A∨B)∨C╞╡A∨(B∨C)結合律

(A∧B)∧C╞╡A∧(B∧C)結合律E5

A∧(B∨C)╞╡(A∧B)∨(A∧C)分配律

A∨(B∧C)╞╡(A∨B)∧(A∨C)1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算E6

(A∨B)╞╡A∧B

德摩根律

(A∧B)╞╡A∨B

E7

A∨(A∧B)╞╡A

吸收律

A∧(A∨B)╞╡A

E8

A→B╞╡A∨B

E9

A

B╞╡(A→B)∧(B→A)E10

A∨t╞╡t

，A∧f╞╡f1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算E11

A∨f╞╡A

，A∧t╞╡A

E12

A∨A╞╡t

，A∧A╞╡fE13

t╞╡f,f╞╡tE14

A∧B→C╞╡A→(B→C)E15

A∨B→C╞╡(A→C)∧(B→C)E16

A→B╞╡┐B→AE17

(A→B)∧(A→B)╞╡AE17

A

B╞╡(A∧B)∨(A∧B)1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定義1.5當命題公式A→B為永真式時，稱A邏輯蘊涵B，記為A╞B，它又稱為邏輯蘊涵式。A╞B的理解：（1）

A→B為永真式。（2）

弄真A的指派均弄真B；

“由A真可推得B真”或“由B假可推得A假”，但反之不然。1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算重要的邏輯蘊涵式：I1

A╞A∨B，B╞A∨B

I2

A∧B╞A，A∧B╞BI3

B╞A→B

I4

A∧(A→B)╞B

I5

(A→B)∧┐B╞┐A

I6

A∧(A∨B)╞B，B∧(A∨B)╞A

I7(A→B)∧(B→C)╞A→C

I8

(A→B)∧(C→D)╞(A∧C)→(B∧D)

I9(AB)∧(BC)╞AC

I10

A╞t;f╞A1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定理1.1對任意命題公式A，B，C，A'，B'，

(1)A╞╡B當且僅當╞

AB(2)A╞B當且僅當╞

A→B(3)若A╞╡B，則B╞╡A(4)若A╞╡B，B╞╡C，則A╞╡C(5)若A╞B，則B╞A(6)若A╞B，B╞C，則A╞C(7)若A╞B，A╞╡A'，B╞╡B'，則A'╞B'1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定理1.2(代入原理RS)

設A為永真式，p為A中命題變元，A(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式(稱為A的一個代入實例)，那么A(B/p)亦為永真式。定理1.3(替換原理RR)

設A為一命題公式，C為A的子公式，且C╞╡D。若將A中子公式C的某些(未必全部)出現(xiàn)替換為D后得到的公式記為B，那么A╞╡B。1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算RSRR使用對象任意永真式任一命題公式代換對象任一命題變元任一子公式代換物任一命題公式任一與代換對象等價的命題公式代換方式代換同一命題變元的所有出現(xiàn)代換子公式的某些出現(xiàn)代換結果仍為永真式與原公式等價代入原理和替換原理的區(qū)別：1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算證明邏輯等價式及邏輯蘊涵式的方法：（1）真值表法。

（2）對指派進行討論。（3）利用已知的永真式、邏輯等價式、邏輯蘊涵式以及代入、替換原理進行推演。1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.13：試證對任意公式A，B，C，有

(A∨B)→C╞╡(A→C)∧(B→C)證1：先證(A∨B)→C╞(A→C)∧(B→C)。

設為弄真(A∨B)→C的任一指派，那么有以下兩種情況：

(a)(A∨B)=0。于是

(A)=(B)=0，從而

(A→C)=(B→C)=1，故

((A→C)∧(B→C))=1。

(b)

(C)=1且

(A∨B)=1。于是

(A→C)=

(B→C)=1，因而又有

((A→C)∧(B→C))=1

據(jù)(a)，(b)可知，必弄真(A→C)∧(B→C)，

因此，(A∨B)→C╞

(A→C)∧(B→C)得證。1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.13（續(xù)）：再證(A→C)∧(B→C)╞(A∨B)→C。

設為弄假(A∨B)→C的任一指派，那么

(A∨B)=1且

(C)=0。

(a)當

(A)=1，

(C)=0時，

(A→C)=0，進而有

((A→C)∧(B→C))=0；

(b)當

(B)=1，

(C)=0時，

(B→C)=0，從而也有

((A→C)∧(B→C))=0，據(jù)(a)，(b)可知，弄假(A→C)∧(B→C)。

于是(A→C)∧(B→C)╞(A∨B)→C得證。所以，(A∨B)→C╞╡(A→C)∧(B→C)1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.13（續(xù)）證2（利用代入、替換原理）

：

(A∨B)→C╞╡(A∨B)∨C

對E8用RS╞╡(A∧B)∨C

據(jù)E6用RR╞╡(A∨C)∧(B∨C)對E5用RS╞╡(A→C)∧(B∨C)據(jù)E8用RR╞╡(A→C)∧(B→C)據(jù)E8用RR

1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.14

對任意公式A，B，C，證明：

A∧B

╞

A→(C→B)

證

A∧B╞

B

據(jù)I2

╞

C∨B

對I1用RS

╞

C→B

對E8用RS

╞

A∨(C→B)對I1用RS

╞

A→(C→B)對E8用RS1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.15

證明下列推理是無效的：證令p表示“狗急”，q表示“狗跳墻”那么前提是pq

和

p，結論是

q

。取指派，使得(p)=0,(q)=1。那么，(pq)=1，(p)=1,但(q)=0。因此，本推理無效。1.2.2邏輯等價式和邏輯蘊涵式1.2邏輯等價式和邏輯蘊含式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.3對偶原理1.2邏輯等價式和邏輯蘊含式定義1.6

設公式A僅含聯(lián)結詞┐，∧，∨，A*為將A中符號∧，∨，t，f分別改換為∨，∧，f，t后所得的公式，那么稱A*為A的對偶。顯然，A與A*互為對偶，即(A*)*=A例1.16

p∨p

與p∧p

對偶

p∨q

與p∧q

對偶

(t∧p)∨q

與(f∨p)∧q對偶離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.3對偶原理1.2邏輯等價式和邏輯蘊含式定理1.4（對偶原理）設公式A中僅含命題變元p1,…,pn，及聯(lián)結詞┐，∧，∨，那么

A┝┥A*(p1／p1，…，pn／pn)

這里，A*(p1／p1，…，pn／pn)表示在A*中對p1,…,pn

分別作代入p1,…,pn后所得的公式。例1.17

已知p∨q與p∧q互為對偶，在后者中用p，q代入p，q

，再取否定后得((p)∧(q))，容易驗證它與p∨q邏輯等價。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.3對偶原理1.2邏輯等價式和邏輯蘊含式定理1.5（對偶原理）設A，B為僅含聯(lián)結詞┐，∧，∨和命題變元

p1,…,pn的命題公式，且滿足A┝B，那么有B*┝A*。進而當A┝┥B時有A*┝┥B*。證據(jù)定理1.4及題設A┝B可知

A*(p1/p1,…,pn/pn)┝B*(p1/p1,…,

pn/pn)從而B*(

p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)

又據(jù)代入原理，有

B*(

p1/p1,…,pn/pn)(p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)(p1/p1,…,pn/pn)即B*(p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)據(jù)E1及替換原理即得B*┝A*。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.3對偶原理1.2邏輯等價式和邏輯蘊含式定義1.7

B*┝A*，A*┝┥B*分別稱為A┝B和A┝┥B的對偶式。例1.18對偶式

A┝A∨B

與A∧B┝A

A∨(B∧C)┝┥(A∨B)∧(A∨C)與A∧(B∨C)┝┥(A∧B)∨(A∧C)當已知(p∧q)∨(p∨(p∨q))┝┥p∨q時，可推得(p∨q)∧(p∧(p∧q))┝┥p∧q。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.4實用邏輯1.2邏輯等價式和邏輯蘊含式例1.19

某倉庫失竊，甲、乙、丙、丁四人涉嫌被拘留審查。他們的口供筆錄如下：甲：丙是案犯。乙：案犯是丁無疑。丙：如果我作案，那么丁是主犯。?。鹤靼傅臎Q不是我。如果偵探得知四人中只有一個人說了假話，你能判定誰是案犯，誰說了假話嗎？離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.4實用邏輯1.2邏輯等價式和邏輯蘊含式例1.20

偵探調查了與案件相關的四個證人，分別是管家、廚師、園丁、清潔工。偵探經調查得到以下結論：

（1）如果管家說的是真話，那么廚師說的也是真話。（2）廚師和園丁說的不可能都是真話。（3）園丁和清潔工沒有都說謊。（4）如果清潔工說的是真話，那么廚師在說謊。你能從中判定說真話和說謊的人嗎？離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.4實用邏輯1.2邏輯等價式和邏輯蘊含式解：

p，q，r，s分別是管家、廚師、園丁、清潔工說真話，上述結論的形式化表示為：

（1）pq

（如果管家說的是真話，那么廚師說的也是真話。）（2）(qr)（廚師和園丁說的不可能都是真話。）（3）(rs)（園丁和清潔工沒有都說謊。）（4）sq

（如果清潔工說的是真話，那么廚師在說謊。）結論：管家和廚師都說謊了，對園丁和清潔工是否說謊還無從考證。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.4實用邏輯1.2邏輯等價式和邏輯蘊含式例1.21

有3個小孩在一起玩，在額頭上都弄上了泥巴。他們的父親對他們說：“你們中至少有一個人額頭上有泥巴?！苯又赣H問：“你們知道自己的額頭上有沒有泥巴？”三個孩子齊搖頭；父親又問同樣的問題，三個孩子又齊搖頭；可是當父親第三次問同樣的問題時，三個孩子都回答“知道（自己的額頭上有泥巴）”。分析三個孩子最終能做出正確判斷的原因。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.2.4實用邏輯1.2邏輯等價式和邏輯蘊含式例1.22

A國只有兩種人，一種永遠說真話，一種永遠說假話。你來到A國，并在一個二叉路口不知如何走才能到達首都。守衛(wèi)路口的士兵只準你問一個問題，而且他只答“是”或“不是”。你應該如何發(fā)問，才能從士兵處獲知去首都的道路。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.1析取范式和合取范式1.3范式文字：命題常元、變元及它們的否定，

前者又稱正文字，后者則稱負文字。析取子句：文字或若干文字的析取。例如：p,p∨q,p∨q∨r

合取子句：文字或若干文字的合取。例如：p,p∧q,p∧q∧r

互補文字對：形如L、L（L為文字）的一對字符。術語：離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定義1.8

命題公式A'稱為公式A的析取范式，如果

(1)A'╞╡A(2)A'為一合取子句或若干合取子句的析取。例1.19

p→q的析取范式：p∨q

((p→q)∧p)∨q的析取范式：p∨(q∧p)∨q1.3.1析取范式和合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.1析取范式和合取范式1.3范式定義1.9

命題公式A'稱為公式A的合取范式，如果(1)A'╞╡A(2)A'為一析取子句或若干析取子句的合取。例1.20

p→q

的合取范式：p∨q(析取子句)，((p→q)∧p)∨q的合取范式：(p∨t)∧(p∨q)

或p∨q

離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.21

求p→(p→q)的析取范式及合取范式。解：

p→(p→q)╞╡p∨(p∨q)

╞╡p∨(p∧q)(╞╡p)析取范式

╞╡(p∨p)∧(p∨q)╞╡p∧(p∨q)(╞╡p)合取范式例1.22永真式、永假式的識別

(1)

p→(p→q)既非永真式，亦非永假式（等價于p）。1.3.1析取范式和合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算(2)(p→(q→r))→((p→q)→(p→r))為永真式。

(p→(q→r))→((p→q)→(p→r))╞╡(p∨q∨r)∨((p∨q)∨(p∨r))╞╡(p∧q∧r)∨(p∧q)∨(p∨r)╞╡(p∧q∧r)∨((p∨p∨r)∧(q∨p∨r))╞╡(p∧q∧r)∨(t∧(q∨p∨r))╞╡(p∧q∧r)∨(q∨p∨r)╞╡(p∨q∨p∨r)∧(q∨q∨p∨r)∧(r∨q∨p∨r)╞╡t∧t∧t╞╡t1.3.1析取范式和合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算(3)(q∧(p→q)→p)∧(q→p)為永假式。

(q∧(p→q)→p)∧(q→p)╞╡((q∧(p∨q))∨p)∧(q∨p)╞╡(q∨(p∧q)∨p)∧(q∧p)╞╡(q∧q∧p)∨(p∧q∧q∧p)∨(p∧q∧p)╞╡f∨f∨f╞╡f1.3.1析取范式和合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算命題公式化為與其等價的析取范式和合取范式的方法步驟：第一步，消去公式中的聯(lián)結詞和：把公式中的A→B化為A∨B；

把公式中的AB化為(A∨B)∧(B∨A)或(A∧B)∨(A∧B)；第二步，將否定聯(lián)結詞向內深入，使之只作用于命題變元或命題變元的否定，然后將A化為A；第三步，利用分配律，將公式進一步化為所需要的范式。第四步，據(jù)問題的要求對已做出的范式作所要求的簡化。1.3范式1.3.1析取范式和合取范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算一公式的析取范式和合取范式都不是唯一的。例如

p∨(p∧q)┝┥(p∧(q∨q))∨(p∧q)┝┥(p∧q)∨(p∧q)┝┥p

p∧(p∨q)┝┥(p∨(q∧q))∧(p∨q)┝┥(p∨q)∧(p∨q)┝┥p一公式的合取范式與析取范式又可能是同一的。例如

p是p→(p→q)的合取范式、析取范式。

p∨q為p→q的析取范式、合取范式。1.3.1析取范式和合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定義1.10

設A為恰含命題變元p1,…,pn的公式。公式A’稱為A的主析取范式，如果A’是A的析取范式，并且其每個合取子句中p1,…,pn均恰出現(xiàn)一次。公式A’稱為A的主合取范式，如果A’是A的合取范式，并且其每個析取子句中p1,…,pn均恰出現(xiàn)一次。例1.23

求公式(p∧q)∨r

的主析取范式及主合取范式(p∧q)∨r╞╡(p∧q∧(r∨r))∨((p∨p)∧(q∨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∧r)∨(p∧q∧r)

1.3.2主析取范式和主合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算(p∧q)∨r╞╡(p∨r)∧(q∨r)╞╡(p∨(q∧q)∨r)∧((p∧p)∨q∨r)╞╡(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)╞╡(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)1.3.2主析取范式和主合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算求公式的主析（合）取范式的方法步驟：第一步：求出該公式的析（合）取范式；第二步：簡化各子句，除去范式中所有恒假（真）的合（析）取子句，即化掉含有互補文字對的合（析）取子句；同時，將合（析）取子句中同一文字的多個出現(xiàn)合并為一個；第三步：對并非每一變元都出現(xiàn)的析（合）取范式中的合（析）取子句，利用p╞╡p∧t╞╡p∧(q∨q)或p╞╡p∨f

╞╡p∨(q∧q)把未出現(xiàn)的變元(q)補進來，并用分配律將其展開，最后得到給定公式的主析（合）取范式。第四步：作必要的化簡，合并相同的變元或常元，消去f，t。1.3.2主析取范式和主合取范式1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.2主析取范式和主合取范式1.3范式結論：(1)每一公式的主析取范式和主合取范式都是唯一確定的。(2)永真式沒有主合取范式，因為它沒有弄假指派。永真式只有主析取范式，它包含所有可能的合取子句，因為一切指派均弄真它。約定——永真式的主合取范式為t。(3)永假式沒有主析取范式，因為它沒有弄真指派。永假式只有主合取范式，它包含所有可能的析取子句，因為一切指派均弄假它。約定——永假式的主析取范式為f。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.2主析取范式和主合取范式1.3范式(4)n個命題變元的主析取范式及主合取范式都有

個，因為不同的合取子句及析取子句都是2n

個。從真值表的角度看也是如此。一張真值表(確定了弄真指派和弄假指派)恰對應一個主析(合)取范式。因此，n個變元的真值表有多少種，便相應地有多少n個變元的主析(合)取范式。事實上，n個變元的真值表必有2n行，對應于2n個可能的指派，而最后一列的每一行有0，1兩個可能的值，因而這一列可能的取值狀況有種，從而生成張不同的真值表。(5)由于每一公式均有主析(合)取范式，因此，無限多的含n個變元的公式可以分作(有限)個類，每一類公式都邏輯等價于它們共同的主析(合)取范式。離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.3聯(lián)結詞的擴充和歸約四個一元聯(lián)結詞：對任意命題p，常聯(lián)結詞△1，△4：△1(p)┝┥f△4(p)┝┥t幺聯(lián)結詞△2：△2(p)┝┥p

否定詞△3：△3(p)┝┥p1.3范式

p

△1(p)

△2(p)

△3(p)△4(p)

01

00

01

1011離散數(shù)學第1章邏輯代數(shù)（上）：命題演算1.3.3聯(lián)結詞的擴充和歸約16個二元聯(lián)結詞：1.3范式p

qp*1qp*2qp*3qp*4qp*5qp*6qp*7qp*8q00011011

0000

0001合取詞

0010

0011

0100

0101

0110

0111析取詞p

qp*9qp*10qp*11qp*12qp*13qp*14qp*15qp*16q00011011

1000

1001等價詞

1010

1011蘊涵詞

1100

1101蘊涵詞

1110

1111離散數(shù)學第1章邏輯代數(shù)（上）：命題演算定義1.11

稱n元聯(lián)結詞h是用m

個聯(lián)結詞g1,g2,…,gm

可表示的，如果

h(p1,p2,...,pn)┝┥A而A中所含聯(lián)結詞僅取自g1,g2,...,gm。定義1.12

當聯(lián)結詞組{g1,g2,...,gm}可表示所有一元、二元聯(lián)結詞時，稱其為完備聯(lián)結詞組。1.3.3聯(lián)結詞的擴充和歸約1.3范式離散數(shù)學第1章邏輯代數(shù)（上）：命題演算例1.24

證明或非詞單獨構成完備聯(lián)結詞組。證我們用分別表示┐,∨中的每一個：

p┝┥(p∨p)┝┥pp

p∨q┝┥((p∨q))┝┥