離散數(shù)學(xué)（第二版） 課件 鄒麗娜 2.3 等值演算

離散數(shù)學(xué)第2章命題邏輯2.3命題公式的等值演算注意:“”與“”的區(qū)別：“”是邏輯聯(lián)結(jié)詞符,A

B為合式公式.“”

表示兩公式關(guān)系的符號，A

B表示兩公式等值.如何判斷兩個(gè)公式等值？真值表法等值演算法……即兩個(gè)公式對任何指派都同真假2.11

2-21運(yùn)算律（?

）雙重否定律

A

??A交換律

A

B

B

A

A

B

B

A結(jié)合律

(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)冪等律

A

A…

A

A

A

A…

A

A運(yùn)算律（?

）分配律

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律

(A

B)

A

B

(A

B)

A

B運(yùn)算律（?

）吸收律

A

(A

B)

A

A

(A

B)

A用真值表證明

ABA

BA

BA

(A

B)

A

(A

B)000000011000101011111111注意：與分配率公式區(qū)分A

(B

C)運(yùn)算律（?

）支配律

A

0

0排中律

A

?A

1矛盾律

A?A

0A

1

1同一律

A

0

A

A

1

A??????任何命題與它的否命題必有一個(gè)為真任何命題他的否命題不能同時(shí)成立A1

A2

A3

…

An

如果Ai等值于0，則該公式等值于0A1

A2

A3

…

An

如果Ai等值于1，則該公式等值于1等值式（

）蘊(yùn)涵-析取等值式

A

B

A

B

AB

A

A

BA

B00111011111000011011等值式（

）蘊(yùn)涵-析取等值式

A

B

A

B

AB

A

A

BA

B00111011111000011011逆否-蘊(yùn)涵等值式

A

B

B

A同真-雙向蘊(yùn)涵等值式

A

B

(A

B)

(B

A)；等價(jià)-否定等值式

A

B

A

B歸謬論

(A

B)

(A

B)

A置換定理，也稱置換規(guī)則如果AB則：(A

P)

(A

Q)

(B

P)

(B

Q)例如：在公式(p

q)

r中，可用

p

q置換其中的p

q(p

q)

r

(

p

q)

r

等值演算【等值演算】

利用聯(lián)結(jié)詞的運(yùn)算律、已知的等值式及置換規(guī)則進(jìn)行公式的等值變換，稱為等值演算。注意：等值演算過程中，若用到某個(gè)運(yùn)算律、等值式，都要標(biāo)出其名稱。置換規(guī)則在等值演算的每一步都會用到可省略。與公式

等值的是ABCD提交單選題1分與公式

等值的是ABCD提交單選題1分例把下列語句的確切含義表達(dá)出來（化簡公式）

1.你去不去都沒關(guān)系.p：你去.p

?p1

2.玫瑰香,牡丹香,玫瑰與牡丹都香,沒有不香的玫瑰,也沒有不香的牡丹.p：玫瑰香,q：牡丹香,p

q(p

q)?(?p)

?(?q)

p

q

玫瑰香，牡丹也香．將下面的語句化簡

3.情況并非如此：如果他不來那么我也不去p：他來q：我去原命題表示為：

?(?

p→?

q)?(??p?q)?(p?q)(?p

??q)?p

q他不來，我去證明:p

(q

r)

?p

(q

r)（蘊(yùn)涵-析取等值式

)?p

(?q

r)（蘊(yùn)涵-析取等值式，置換規(guī)則)

(?p?q)

r(結(jié)合律)?(p

q)

r（德·摩根律,置換規(guī)則

)

(p

q)

r(蘊(yùn)涵-析取等值式

)等值演算2-22

同一律

排中律，置換規(guī)則

分配律求證：證明：等值演算2-22(2)例2.23

判斷下列公式的類型(重言式，矛盾式，可滿足式)：

德?摩根律

德?摩根律

雙重否定律分配律

結(jié)合律排中律支配律

同一律重言式排中律矛盾式可滿足式例2.23判斷下列公式的類型用等值演算法判斷公式的類型p→(p

q

r)重言式矛盾式可滿足式公式值為0ABCD提交單選題1分用等值演算法判斷公式的類型(?p→q)→(q→?p)重言式矛盾式可滿足式公式值為0ABCD提交單選題1分練習(xí)：用等值演算法判斷公式的類型(1)．

p→(p

q

r)(2)．(?p→q)→(q→?p)雙重否定律

A??A交換律

A

B

B

AA

B

B

A結(jié)合律

(A

B)CA

(BC)(A

B)CA

(BC)冪等律

A

A…

A

AA

A…

A

A分配律

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律

(A

B)

A

B

(A

B)

A

B吸收律

A

(A

B)

AA

(A

B)

A支配律A

0

0A

1

1同一律A

0

AA

1

A排中律A?A

1矛盾律A?A

0蘊(yùn)涵-析取A

B

A

B

逆否-蘊(yùn)涵

A

B

B

A同真-雙向蘊(yùn)涵

A

B

(A

B)

(B

A)

等價(jià)-否定A

B

A

B歸謬論

(A

B)

(A

B)

A練習(xí)：用等值演算法判斷公式的類型(1)．

p→(p

q

r)?p

(p

q

r)

(蘊(yùn)涵等值式)

(?p

p)

q

r

(結(jié)合律)

1

q

r

(排中律)

1

(零律)(1)為重言式．練習(xí)：用等值演算法判斷公式的類型(2)．(?p→q)→(q→?p)

(p

q)→(?q

?p)

(蘊(yùn)涵等值式)

?(p

q)

(?q

?p)

(蘊(yùn)涵等值式)

(?p

?q)

(?q

?p)

(德·摩根律)((?p

?q)

?q)

?p

(結(jié)合律)

?q

?p

(吸收律)

11為該公式的成假賦值，01為該公式的成真賦值，故可滿足式．12如果明天晴天，如果我有空，那么我就請你吃飯PQRp

(q

r)(p

q)

r（p

q

）

rp

q

rABCD練習(xí)(2)．(?p→q)→(q→?p)

(p

q)

(?q

?p)

(德·摩根律)((?p(?q

?p)

(蘊(yùn)涵等值式)

?(p

q)

(?q

?p)

(蘊(yùn)涵等值式)

(?p

?q)

(?q

?p)

(德·摩根律)((?p

?q)

?q)

?p

(結(jié)合律)

?q

?p

(吸收律)

11為該公式的成假賦值，01為該公式的成真賦值，故可滿足式．雙重否定律

A??A交換律

A

B

B

AA

B

B

A結(jié)合律

(A

B)CA

(BC)(A

B)CA

(BC)冪等律

A

A…

A

AA

A…

A

A分配律

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律

(A

B)

A

B

(A

B)

A

B吸收律

A

(A

B)

AA

(A

B)

A支配律A

0

0A

1

1同一律A

0

AA

1

A排中律A?A

1矛盾律A?A

0蘊(yùn)涵-析取A

B

A

B

蘊(yùn)涵-析取A

B

A

B

逆否-蘊(yùn)涵

A

B

B

A同真-雙向蘊(yùn)涵A

B

(A

B)

(B

A)

等價(jià)-否定A

B

A

B歸謬論

(A

B)

(A

B)

A等值演算的應(yīng)用2-24

(1)(2)(3)等值演算的應(yīng)用((c1∧?b2)∨(?c1∧

b2))∧((c2∧?d3)∨(?c2∧

d3))

∧((a2∧?d4)∨(?a2∧

d4))1

(c1∧?b2)∨(?c1∧

b2)1(c2∧?d3)∨(?c2∧

d3)1(a2∧?d4)∨(?a2∧

d4)1c1b2c2d3a2d4(1)∧(2)

∧(3)1

設(shè)aibicidi（i取值于1,2,3,4）分別表示四個(gè)人名次，例如b2表示b第二邏輯值運(yùn)算結(jié)果c1b2c2d3a2d4可以確定C第1名，A第2名，D第3名，B第4名。(1)∧(2)

∧(3)

41頁14.某工廠要從A、B、C、D、E五種新型產(chǎn)品中選擇幾種產(chǎn)品投產(chǎn)，根據(jù)該廠的實(shí)際生產(chǎn)條件及市場需求的調(diào)查分析結(jié)果，選擇時(shí)必須滿足以下條件：(1)若選擇A，則必須選擇B；(2)D、E兩種產(chǎn)品至少選擇一種；(3)B、C兩種產(chǎn)品只選擇一種；(4)C、D兩種產(chǎn)品都選擇或都不選擇；(5)若選E，則必須選擇A和B。請