離散數(shù)學(xué)（第二版） 課件 鄒麗娜 2.4 公式的范式

離散數(shù)學(xué)第2章命題邏輯((p→q)

p)→q與q

?q

?p是否等值，并判斷兩個公式的類型

公式的范式

((p→q)

p)→q

((?p

q)

p

)→q

(?p

p)

(q

p

)→q

(p

q)→q

?(p

q)

q

(?

p?q)

qq

?q?p1重言式

q?q

?p

1

?p

1

重言式判定問題：有限次步驟來判定命題公式是否為：

①永真式、永假式，可滿足的;

②二個命題公式等價;目的：討論范式和主范式就是為了進(jìn)行判定。范式：把命題公式化歸為一種標(biāo)準(zhǔn)的形式。

公式的范式

公式的范式例：設(shè)p、q為二個命題變元簡單析取式：p，q，p∨p，q∨q，?p∨q，

?q∨?p，p∨q，p∨?q簡單合取式：p，q，p∧p，q∧q，?p∧q，

?q∧?p，p∧q，p∧?q22

公式的范式(析取范式)定義2.16由有限個簡單合取式構(gòu)成的析取式稱為析取范式。析取范式同時滿足下列三個條件：(1)它是個析取式(2)式中的每個析取項(xiàng)是個合取式(3)每個合取式中只包含命題變元或其否定。例：p∨(q∧﹁r)∨r

(p∨q)∨(q→r)∨p是不是3范式存在定理定理2.2對于任何一個命題公式，都存在著與之等值的析取范式與合取范式。

()

()

(

)(

)

(

)

(

)

范式存在定理2.2：

任意命題公式都存在著與之等值的合取范式或析取范式。

求析取范式的步驟：

1.利用等值公式：化去“→”、“

”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等值的用{?，∧，∨}表達(dá)的公式。

A→B

?A∨B，A

B

(A→B)∧(B→A)

(?A∨B)∧(?B∨A)

(A∧B)∨(?B∧?A)2.將“?”深入到原子命題變元前，使變元前最多只有一個“?”。

?(?A∨?B)

?

?A∧?

?B

A∧B3.利用“∧”對“∨”的分配，將公式化成為析取范式析取范式()()(

)求析取范式例2.25

求下列公式的析取范式：(1)化去→詞(3)“∧”對“∨”分配，化為析取范式(2)將否定符深入到命題變元前：析取范式課后習(xí)題16(1)(4)析取范式課后習(xí)題16(2)析取范式課后習(xí)題16(3)析取范式課后習(xí)題16(5)析取范式課后習(xí)題16(6)公式的極小項(xiàng)((p→q)

q

?p)→(q

?p)

兩個變元的析取范式由哪些合取項(xiàng)組成？(列出所有可能)

?p

?qp

q?p

qp

?q定義2.15【公式的極小項(xiàng)】1.設(shè)是n個互不相同的命題變元。4.由產(chǎn)生的極小項(xiàng)稱為公式極小項(xiàng)。3.形如簡單合取式是極小項(xiàng)。2.令原形或否定注意：對于由n個命題變元可以產(chǎn)生個極小項(xiàng)。公式的極小項(xiàng)例：求2個命題變元p，q生產(chǎn)的所以極小項(xiàng)。極小項(xiàng)

成真賦值

記法

p

q

pqp

qpq00011011m0

m1

m2

m3

極小項(xiàng)：每個合取式稱為一個極小項(xiàng)。2個變元p

q可以產(chǎn)生22個極小項(xiàng)。

?p

?qp

q?p

qp

?q主析取范式定義2.16

設(shè)A是含n個命題變元的公式，B是A的一個析取范式，若B中每個簡單合取式都是極小項(xiàng)，則稱B是A的主析取范式。

?p

?qp

q?p

qp

?q主析取范式：

(1)它是個析取范式。

(2)在每個合取式中所有命題變元均出現(xiàn)（p

q

）。

(3)

命題變元或以其否定的形式出現(xiàn)，且僅出現(xiàn)一次。主析取范式命題公式化歸主析取范式的過程

(1)化歸為析取范式

(2)除去所有為永假的合取式。即﹁A∧A形式的項(xiàng)

(3)將相同命題變元化歸為一個命題變元利用公式A∧A=A

(4)在合取式中補(bǔ)充變元令所有命題變元均出現(xiàn)用公式A=

A∧1=A∧(B∨﹁B)，應(yīng)用分配律將其展開。

主析取范式例:試求(p∧(p→q))∨q的主析取范式(1)化歸為析取范式：m11

m01(2)去除永假項(xiàng)：(3)補(bǔ)充不足的命題變元(p∧(p→q))∨q

(p∧(﹁p∨q))∨q

(p∧﹁p)∨(p∧q)∨q

(p∧q)∨q

(p∧q)∨(q∧1)

(p∧q)∨((p∨﹁p)∧q

)

(p∧q)∨((p

∧

q)∨(﹁p∧q)

)

(p

∧

q)∨(﹁p∧q)

(4)寫出極小項(xiàng)主析取范式

(?

p

q)

(?

p

?

q)m01

m00m0m1主析取范式(

p

q)

→?

q?(

p

q)

?

q(??

p

?

q)

?

q(p

?

q)

?

qp

?

q是析取范式不是主析取范式p

?

q

(p

(q

?q

))

(

(p?p

)

?q))

(p

q

)

(p

?q

)

(p

?q

)

(

?p

?q)

(p

q

)

(p

?q

)

(

?p

?q)m11

m10

m00m3

m2

m0三個變元的極小項(xiàng)列出所有可能的析取范式(合取式)組成？

?p

?q

?r?p

?q

r?p

q

?r?p

q

r

p

?q

?rp

?q

rp

q

?rp

q

r

極小項(xiàng)：每個合取式稱為一個極小項(xiàng)。3個變元p

qr可以產(chǎn)生23個極小項(xiàng)。主析取范式：

(1)它是個析取范式。

(2)在每個合取式中所有命題變元均出現(xiàn)（p

qr

）。

(3)

命題變元或以其否定的形式出現(xiàn)，且僅出現(xiàn)一次。

極小項(xiàng)的真值極小項(xiàng)

成真賦值

記法

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111m0

m1

m2

m3

m4

m5

m6

m7

主析取范式是析取范式不是主析取范式例2.26例2.26例題2-27求公式(p→q)

r主析取范式真值表法pqrp→q

(p→q)

r0001000111010100111110001101001101011111m3m1m7m4例題2-27求公式(p→q)

r主析取范式((?p

q)

r)((?p

q)

?r)

((?p

r)(q

r))((p

q)

r)

(?p

r)(q

r)(p

q

r)0

?1?11m3m1m7主析取范式為：

m1

m3

m4

m710

0m4例題2-28求公式?(p→q)

r主析取真值表法pqrp→q

?(p→q)

?(p→q)

r000100001101010100011101100011101011110100111101m3m1m7m4m5例題2-28求公式?(p→q)

r?(?p

q)

r

(p

q)

r

1

0?m3m1m7主析取范式為：

m1

m3

m4

m5

m7m4？？1m5主析取范式總結(jié)1.由極小項(xiàng)組成

極小項(xiàng)極小項(xiàng)極小項(xiàng)極小項(xiàng)包括所有變元的簡單合取式

p

q

r

p

q

r

p

q

r

p

q

r

2.表示公式的成真賦值p

q

r

p

q

r

p

q

r

p

q

r

主析取范式總結(jié)3.主析取范式求法先演算為一般的析取范式再將每一項(xiàng)湊成極小項(xiàng)寫出編號：P取1，

P取0例題2-28求公式?(p→q)

r主析取范式?(?p

q)

r

(p

q)

r

1

0?？？1主析取范式為：

m1

m3

m4

m5

m7主析取范式的應(yīng)用(pq)(p

q)(

pq)(

pq)

無(pq)(p

q)

練習(xí)42頁182.6公式的范式(合取范式)定義2.14由有限個簡單析取式構(gòu)成的合取式稱為合取范式。合取范式同時滿足下列三個條件：(1)它是個合取式(2)式中的每個合取項(xiàng)是個析取式(3)每個析取式中只包含命題變元或其否定。范式存在定理定理2.2對于任何一個命題公式，都存在著與之等值的析取范式與合取范式。

()()(

)(

)

(

)

(

)

范式存在定理2.2：

任意命題公式都存在著與之等值的合取范式或析取范式。

求合取范式的步驟：

1.利用等值公式：化去“→”、“

”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等值的用{?，∧，∨}表達(dá)的公式。A→B

?A∨B，A?B

(A→B)∧(B→A)

(?A∨B)∧(?B∨A)2.將“?”深入到原子命題變元前，使變元前最多只有一個“?”。

?(?A∨?B)

?

?A∧?

?B

A∧B3.利用“∨”對“∧”的分配，將公式化成為合取范式合取范式(

)

(

)

(

)例2.25

求下列公式的合取范式：求合取范式(1)化去→詞(3)“∨”對“∧”分配，化為合取范式：(2)將否定符深入到命題變元前：公式的極大項(xiàng)列出所有可能的合取范式(析取項(xiàng))組成？定義2.17【公式的極大項(xiàng)】1.設(shè)是n個互不相同的命題變元。4.由產(chǎn)生的極大項(xiàng)稱為公式極大項(xiàng)。2.令原形或否定。注意：對于由n個命題變元可以產(chǎn)生個極大項(xiàng)。?p

?qp

q?p

qp

?q

3.形如簡單析取式是極大項(xiàng)。練習(xí)例

求3個命題變元p,q,r產(chǎn)生的所有極大項(xiàng)。極大項(xiàng)

成0賦值

記法

p

q

r

p

q

rp

q

rp

q

r

p

q

r

p

q

r

p

q

r

p

q

r000001010011100101110111M0

M1

M2

M3

M4

M5

M6

M7

主合取范式?p

?qp

q?p

qp

?q

主合取范式：

(1)它是個合取范式。

(2)在每個析取式中所有命題變元均出現(xiàn)（p

q）。

(3)

命題變元或以其否定的形式出現(xiàn)，且僅出現(xiàn)一次。定義2.18

設(shè)A是含n個命題變元的公式，B是A的一個合取范式，若B中每個簡單析取式都是極大項(xiàng)，則稱B是A的主合取范式。主合取范式命題公式化歸主合取范式的過程

(1)化歸為合取范式

(2)除去所有為永真的析取項(xiàng)。即﹁A∨A形式的項(xiàng)

(3)將相同命題變元化歸為一個命題變元利用公式A∨A=A

(4)在析取項(xiàng)中補(bǔ)充變元令所有命題變元均出現(xiàn)用公式A

=A∨0=A∨(B∧﹁B)，應(yīng)用分配律將其展開。

主合取范式例試求公式(﹁p→r∨p)∧(q

p)的主合取范式(1)化歸為合取范式：(﹁p→r∨p)∧(q

p)=(p∨r∨p)∧(﹁q∨p)∧(﹁p∨q)(2)去除永真項(xiàng)：無(3)在析取式中，將多個相同命題變元化歸為一個命題變元(p∨r∨p)∧(﹁q∨p)∧(﹁p∨q)=(p∨r)∧(p∨﹁

q)∧(﹁p∨q)(4)補(bǔ)充不足的命題變元(p∨r)∧(p∨﹁

q)∧(﹁p∨q)

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

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

q∨﹁r)∧(﹁p∨q∨﹁r)公式的主合取范式與真值表之間的關(guān)系主合取范式極大項(xiàng)對應(yīng)著真值表中使結(jié)果為0的賦值組合。主析取范式極小項(xiàng)對應(yīng)著真值表中使結(jié)果為1的賦值組合。主析取范式和主合取范式的關(guān)系主析取范式為：主合取范式為：有主合取范式可以判斷公式的成假賦值,而主析取范式可以判斷公式的成真賦值，所以兩種范式正好相反.課后練習(xí)主合取范式00?0?1001011

(p

q)

(p

?r)0000019例題2-30求公式(p→q)

r主合取范式真值表法pqrp→q

(p→q)

r0001000111010100111110001101001101011111M2M0M6M5例題2-31求公式?(p→q)

r主合取真值表法pqrp→q

?(p→q)

?(p→q)

r000100001101010100011101100011101011110100111101M2M0M6主合取范式總結(jié)1.由極大項(xiàng)組成

極大項(xiàng)極大項(xiàng)極大項(xiàng)極大項(xiàng)包括所有變元的簡單析取式p

q

rp

q

rp

q

rp

q

r

2.表示公式的成假賦值

p

q

r

p

q

r

p

q

r

p

q

r主合取范式總結(jié)3.主合取范式求法先演算為一般的合取范式再將每一項(xiàng)湊成極大項(xiàng)寫出編號：P取0，

P取1例題2-28求公式?(p→q)

r主合取范式?(?p

q)

r

(p

q)

r(p

r)

(q

r)

0？0？10主析取范式為：

M0

M2

M6主合取范式的應(yīng)用例29求（（p

q）

r）

p的成真賦值和成假賦值

（?（p

q）

r）

p?（?（p

q）

r）

p

（p

q）

?r）

p

（p

?r

）

（

q

?r

）

pm110

m101m010

m100m111m2m4m5m6m7

110.101.010.100.