離散數(shù)學(xué)課件第一章(第4講)

對偶原理（對偶定律）《定義》：給定命題公式Ａ，若用Λ代換∨，用∨代換Λ，用Ｔ代換Ｆ，用Ｆ代換Ｔ，得到另一個命題公式A*，則稱Ａ和A*是互為對偶的。例：寫出下列命題公式的對偶式：Ｐ∨（ＱΛＲ）ＰΛ（Ｑ∨Ｒ）Ｐ∨Ｆ對偶式A*ＰΛＴＰ∨ＴＰΛＦ§5對偶與范式討論定義：（１）若命題公式中有聯(lián)結(jié)詞，，則必須把化成由聯(lián)結(jié)詞Λ，∨，

組成的等價的命題公式，然后求它的對偶式；例：求(P

Q)

(P

R)的對偶式(P

Q)

(P

R)

（?Ｐ∨Ｑ）

Λ（?Ｐ∨R）

則其對偶式為：（?ＰΛＱ）∨

（?ＰΛR）

（２）在寫對偶式時，原命題公式中括號不能省去，必須按優(yōu)先級的次序畫上括號，并在求其對偶式時仍將保留括號。例：（ＰΛＱ）∨Ｒ對偶式寫成（Ｐ∨Ｑ）ΛＲ，而不能寫成Ｐ∨ＱΛＲ《定理》：（摩根推廣定理）設(shè)Ａ和A*為對偶式,P1,P2．．．Pn

是出現(xiàn)在Ａ和A*中的所有原子命題變元，于是有：?Ａ（P1，P2．．．Pn）

A*

（?P1，?P2．．．?Pn）——（1）Ａ（?P1，?P2．．．?Pn）

?A*（P1，P2．．．Pn）——（２）證明：由摩根定理

?（Ｐ∨Ｑ）

?ＰΛ?Ｑ—（１）

?Ｐ∨?Ｑ

?（ＰΛＱ）—（２）

例：設(shè)Ａ（Ｐ，Ｑ，Ｒ）

?ＰΛ?

（Ｑ∨Ｒ），驗(yàn)證上述定理：證明：(１)Ａ（Ｐ，Ｑ，Ｒ）

?ＰΛ?ＱΛ?Ｒ∴?Ａ（Ｐ，Ｑ，Ｒ）

Ｐ∨Ｑ∨ＲA*（Ｐ，Ｑ，Ｒ）

?Ｐ∨?Ｑ∨?ＲA*（?Ｐ，?Ｑ，?Ｒ）

Ｐ∨Ｑ∨Ｒ有?Ａ（Ｐ，Ｑ，Ｒ）=A*（?Ｐ，?Ｑ，?Ｒ）（２）Ａ（?Ｐ，?Ｑ，?Ｒ）

ＰΛＱΛＲ?A*（Ｐ，Ｑ，Ｒ）

?

（?Ｐ∨?Ｑ∨?Ｒ）

ＰΛＱΛＲ有Ａ（?Ｐ，?Ｑ，?Ｒ）

?A*（Ｐ，Ｑ，Ｒ）《定理》：若二個命題公式互為等價，則它們的對偶式也互為等價，亦即若Ａ

Ｂ，則A*

B*成立。由Ａ

Ｂ，即Ａ（P1，P2．．．Pn）

Ｂ（P1，P2．．．Pn）∴

?Ａ（P1，P2．．．Pn）

?Ｂ（P1，P2．．．Pn）由摩根推廣定理∴Ａ*（?P1，?P2．．．?Pn）

Ｂ*（?P1，?P2．．．?Pn）證明：設(shè)：P1、P2．．．Pn

是出現(xiàn)在Ａ和Ｂ中的原子命題變元，∴Ａ*（?P1，?P2．．．?Pn）

Ｂ*（?P1,?P2．．．?Pn）為永真式由于永真式的代換實(shí)例仍為永真式，所以用?Pi代換A*和B*中的Pi

（1≤i≤n)則得：Ａ*（?

?P1，?

?P2．．．?

?Pn）

Ｂ*（?

?P1，?

?P2．．．?

?Pn）即為：Ａ*（P1，P2．．．Pn）

Ｂ*（P1，P2．．．Pn）范式把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。1．析取范式和合取范式：[定義]一個命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1∨A2∨…∨An(n≥1),其中A1，A2，…，An都是由命題變元或其否定所組成的合取式。如：（Ｐ∧Ｑ∧Ｒ）∨（?Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）是一個析取范式判定二個命題公式等價，還可以使用范式方法。（１）利用等價公式：化去“→”、“

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

例:Ｐ→Ｑ

?Ｐ∨Ｑ，Ｐ?Ｑ

（Ｐ→Ｑ）∧（Ｑ→Ｐ）

（?Ｐ∨Ｑ）∧（?Ｑ∨Ｐ）（２）將“?”深入到原子命題變元之前，并使變元之前最多只有一個“?”詞。例：?（?Ｐ∨?Ｑ）

?

?Ｐ∧?

?Ｑ

Ｐ∧Ｑ求析取范式的方法可按下列三步（或四步）進(jìn)行：（３）利用“∧”對“∨”的分配律，將公式化為析取范式。（４）除去永假項(xiàng)得最簡析取范式。例：求?(（Ｐ∧?Ｑ）→R)∨((P→?Q)

∧Q)的析取范式原式

?(?（Ｐ∧?Ｑ）∨R)

∨

(（?Ｐ∨?Ｑ）∧Q)

——化去“→”詞

(（Ｐ∧?Ｑ）∧?R)

∨(（?Ｐ∨?Ｑ）

∧Q)

——“?”深入到變元前，并最多保留一個（Ｐ∧?Ｑ∧?R)

∨（?Ｐ∧Ｑ）∨（?Q∧Ｑ）

——“∧”對“∨”的分配律（Ｐ∧?Ｑ∧?R)

∨（?Ｐ∧?Ｑ）——去掉永假的合取項(xiàng)注：給定一命題公式的析取范式不是唯一的，但同一命題公式的析取范式一定是等價的。[定義]一個命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式：A1∧A2∧…∧An(n≥1),其中A1，A2，…，An都是由命題變元或其否定所組成的析取式。如：（Ｐ∨Ｑ∨Ｒ）∧（?Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）是一個合取范式。求一個命題公式的合取范式的方法和求析取范式的方法類同：（１）利用等價公式：化去“→”、“

”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價的用{?，∧，∨}表達(dá)的公式。（２）將“?”深入到原子命題變元之前，并使變元之前最多只有一個“?”詞。（３）利用“∨”對“∧”的分配律，將公式化為合取范式；（４）去掉永真的析取項(xiàng)。例：求(Ｑ∨?（Ｐ→Ｑ）)∧?（Ｐ∧Ｑ）的合取范式原式

(Ｑ∨?（?Ｐ∨Ｑ）)∧?（Ｐ∧Ｑ）

——化去“→”詞

(Ｑ∨（Ｐ∧?Ｑ）)∧（?Ｐ∨?Ｑ）

——“?”深入到變元前，并最多保留一個（（Ｑ∨Ｐ）∧（Ｑ∨?Ｑ））∧（?Ｐ∨?Ｑ）

——“∨”對“∧”的分配（Ｑ∨Ｐ）∧（?Ｐ∨?Ｑ））——去掉永真的析取項(xiàng)注：給定一命題公式的合取范式不是唯一的，但同一命題公式的合取范式一定是等價的。2．主析取范式[定義]在ｎ個變元的合取項(xiàng)中，若每個變元及其否定并不同時存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱此合取項(xiàng)為小項(xiàng)。例:具有二個命題變元的命題公式,小項(xiàng)最多有22=4個,即Ｐ∧Ｑ、?Ｐ∧Ｑ、Ｐ∧?Ｑ、?Ｐ∧?Ｑ

具有三個命題變元的命題公式，小項(xiàng)最多有23=8個，即：Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧?Ｒ、Ｐ∧?Ｑ∧Ｒ、Ｐ∧?Ｑ∧?Ｒ、?Ｐ∧Ｑ∧Ｒ、?Ｐ∧Ｑ∧?Ｒ、?Ｐ∧?Ｑ∧Ｒ、?Ｐ∧?Ｑ∧?Ｒ推廣：具有ｎ個命題變元的命題公式的小項(xiàng)最多有2n個（n∈I+）。[定義]對于給定的命題公式，若干個小項(xiàng)的析取稱為該命題公式的主析取范式。[定理]在真值表中，一個命題公式的所有真值為Ｔ的指派所對應(yīng)的小項(xiàng)的析取，即為此命題公式的主析取范式。例：根據(jù)真值表，分別求出Ｐ→Ｑ、Ｐ∨?Ｑ、Ｐ

Ｑ的主析取范式。TTTTTFFTFTTFFTFTTTFFＰ→ＱP

QＰ∨?ＱＱＰ則根據(jù)真值表可直接寫出各命題公式的主析取范式：Ｐ→Ｑ

（?Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）∨（Ｐ∧Ｑ）Ｐ∨?Ｑ

（?Ｐ∧?Ｑ）∨（Ｐ∧?Ｑ）∨（Ｐ∧Ｑ）P

Q

（?Ｐ∧?Ｑ）∨（Ｐ∧Ｑ）討論此定理：（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫出其主析取范式，其方法是找出該命題公式真值為“Ｔ”的行，對應(yīng)寫出小項(xiàng)的析取式，命題公式的主析取范式一定是唯一的。（2）由真值表找小項(xiàng)的方法為：將表中值為“T”所對應(yīng)的真值指派中，T對應(yīng)變元本身，F(xiàn)對應(yīng)變元的否定。（3）命題公式的主析取范式中小項(xiàng)的個數(shù)一定等于對應(yīng)真值表中真值為“Ｔ”的個數(shù)。（4）若二個命題公式對應(yīng)的主析取范式相同，則此二個命題公式一定是等價的。

下面介紹不用真值表，直接求命題公式主析取范式的方法，分四步：（１）將命題公式化為與其等價的析取范式；

（２）除去永假項(xiàng)，合并合取項(xiàng)中相同項(xiàng)例：Ｐ∧?Ｐ∧Ｑ為永假項(xiàng)，去掉。Ｐ∧Ｐ∧Ｑ

Ｐ∧Ｑ，合并合取項(xiàng)中相同項(xiàng)（３）對合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加（合取）例如（Ｐ∨?P）的形式，并應(yīng)用∧對∨的分配律展開公式。例：若命題公式有二個變元Ｐ、Ｑ，當(dāng)析取范式中的某一項(xiàng)缺少變元時，利用“∧”對“∨”的分配律添項(xiàng)：Ｐ

Ｐ∧（Ｑ∨?Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）Ｑ

Ｑ∧（Ｐ∨?Ｐ）

（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）（４）合并相同的小項(xiàng)。

（Ｐ∧Ｑ）∨Ｑ

----（2）消去永假項(xiàng)，變?yōu)樽詈單鋈》妒?/p>

（Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨?Ｐ））----（3）添項(xiàng)

（Ｐ∧Ｑ）∨（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）

----（4）合并相同小項(xiàng)例：求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式解：原式

（Ｐ∧?Ｐ）∨（Ｐ∧Ｑ）∨Ｑ

----（1）化為析取范式例：證明Ｐ∨（?Ｐ∧Ｑ）

Ｐ∨Ｑ證明方法是寫出二命題公式的主析取范式，看其是否相同：Ｐ∨（?Ｐ∧Ｑ）

Ｐ∧（Ｑ∨?Ｑ）∨（?Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）Ｐ∨Ｑ

（Ｐ∧（Ｑ∨?Ｑ））∨（Ｑ∧（Ｐ∨?Ｐ））

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）兩個命題公式主析范式相同，∴Ｐ∨（?Ｐ∧Ｑ）

Ｐ∨Ｑ3．主合取范式[定義]在ｎ個變元的析取項(xiàng)中，若每個變元與其否定，并不同時存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱這種析取項(xiàng)為大項(xiàng)。例：具有二個變元Ｐ,Ｑ的命題公式，其大項(xiàng)最多有22=4個：（Ｐ∨Ｑ）、（Ｐ∨?Ｑ）、（?Ｐ∨Ｑ）、（?Ｐ∨?Ｑ）具有ｎ個變元的命題公式，其大項(xiàng)最多有2n個（n∈I+）。[定義]對于給定的命題公式，若干個大項(xiàng)的合取稱為該命題公式的主合取范式。[定理]在真值表中，一個命題公式的所有真值為F的指派所對應(yīng)的大項(xiàng)的合取，即為此命題公式的主合取范式。

在真值表中真值為“Ｆ”的個數(shù)等于主合取范式中大項(xiàng)的個數(shù)。Ｐ

ＱＰ∧ＱＱＰTTTTTFFFFTTFFTFTTFFF例：根據(jù)真值表，分別求出Ｐ→Ｑ、Ｐ∧Ｑ、Ｐ

Ｑ的主合取范式。Ｐ→ＱＰ∧Ｑ

（Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）∧（?Ｐ∨Ｑ）根據(jù)真值表，可直接寫出各命題公式的主合取范式：Ｐ→Ｑ

?Ｐ∨ＱＰ

Ｑ

（Ｐ∨?Ｑ）∧（?Ｐ∨Ｑ）討論：（1）該命題公式的主合范式中大項(xiàng)的個數(shù)等于其真值表中真值為“Ｆ”的個數(shù)。（2）由真值表找大項(xiàng)的方法為：將表中值為“Ｆ”所對應(yīng)的真值指派中，T對應(yīng)變元的否定，F(xiàn)對應(yīng)變元本身。（3）只要命題公式不是永真式，則一定可以寫出與其等價的唯一的主合取范式。（4）可用主合取范式判定二個命題公式是否等價。（5）對應(yīng)于有ｎ個變元的命題公式，則一定有：主析范式小項(xiàng)數(shù)＋主合范式大項(xiàng)數(shù)＝2n下面介紹不用真值表求一命題公式主合取范式的方法：（1）將命題公式化為與其等價的合取范式；（2）除去永真項(xiàng)，合并析取項(xiàng)中相同變元，變?yōu)樽詈喓先∈?；例：Ｐ?Ｐ∨Ｑ為永真項(xiàng)，去掉。Ｐ∨Ｐ∨Ｑ

Ｐ∨Ｑ，合并析取項(xiàng)中相同變元。

（3）對析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加(析取)例如（Ｐ∧?P）的形式，并應(yīng)用∨對∧的分配律展開公式。例：若命題公式有二個變元Ｐ、Ｑ，當(dāng)合取范式中的某一項(xiàng)缺少變元時，利用“∨”對“∧”的分配律添項(xiàng)：即：Ｐ

Ｐ∨（Ｑ∧

Ｑ）

（Ｐ∨Ｑ）∧（Ｐ∨

Ｑ）（4）合并相同的大項(xiàng)。

例：求Ｐ∧（Ｐ→Ｑ）∨Ｑ的主合取范式解：原式

Ｐ∧（?Ｐ∨Ｑ）∨Ｑ

（Ｐ∧?Ｐ）∨（Ｐ∧Ｑ）∨Ｑ

（Ｐ∧Ｑ）∨Ｑ（Ｐ∨Ｑ）∧（Ｑ∨Ｑ）（Ｐ∨Ｑ）∧Ｑ

----合并析取項(xiàng)中相同變元，化為最簡合取范式

（Ｐ∨Ｑ）∧(Ｑ∨（

Ｐ∧Ｐ）)

----添項(xiàng)

（Ｐ∨Ｑ）∧（

Ｐ∨Ｑ）∧（Ｐ∨Ｑ）

（Ｐ∨Ｑ）∧（

Ｐ∨Ｑ）

----合并相同大項(xiàng)4．主析(合)取范式的編碼表示為了能夠用編碼的形式表達(dá)主析(合)取范式，作如下規(guī)定：小項(xiàng)和大項(xiàng)中的各命題變元的出現(xiàn)位置必須安排一固定次序。（１）小項(xiàng)的編碼對于有ｎ個變元的命題公式，則最多可有2n個小項(xiàng)，用mi表示小項(xiàng)，用m0

∨m1…

∨m2n-1來表示主析取范式。

P∧Q∧R1117m7P∧Q∧

R1106m6P∧

Q∧R1015m5P∧

Q∧

R1004m4

P∧Q∧R0113m3

P∧Q∧

R0102m2

P∧

Q∧R0011m1

P∧

Q∧

R0000m0小項(xiàng)表示二進(jìn)制數(shù)十進(jìn)制數(shù)m(i)十下面表格列出三個變元，且Ｐ、Ｑ、Ｒ的位置已固定，小項(xiàng)表達(dá)如下：對主析取范式編碼的方法：(1)將小項(xiàng)中的變元按照固定次序排列；(2)用二進(jìn)制表示出其對應(yīng)的小項(xiàng)，將小項(xiàng)中變元的肯定用1表示，變元的否定用0表示；(3)將二進(jìn)制轉(zhuǎn)變?yōu)槭M(jìn)制，用mi表示小項(xiàng)；(4)將mi表示的各小項(xiàng)，用析取符號連接，得到編碼表示的主析取范式；(5)取各小項(xiàng)下標(biāo)的十進(jìn)制數(shù)字，按照順序置于

符號后，可進(jìn)一步簡化編碼表示主析取范式。解：原式

（Ｐ∧Ｑ∧Ｒ）∨（Ｐ∧Ｑ∧

Ｒ）

∨（

Ｐ∧

Ｑ∧Ｒ）∨（

Ｐ∧Ｑ∧Ｒ）

m(111)∨

m(110)∨

m(001)∨

m(011)

m7∨

m6∨

m1∨

m3

m1,m3,m6,m7

1,3,6,7

例：求（Ｐ∧Ｑ）∨（

Ｐ∧Ｒ）的主析取范式的編碼表達(dá)式：（設(shè)小項(xiàng)按照Ｐ、Ｑ、Ｒ次序固定）（2）大項(xiàng)的編碼對于有ｎ個變元的命題公式，則最多可有2n個大項(xiàng)，用Mi表示大項(xiàng)，用M0

∨M1…

∨M2n-1來表示主合取范式。

P∨

Q∨

R1117M7

P∨

Q∨R1106M6

P∨Q∨

R1015M5

P∨Q∨R1004M4P∨

Q∨

R0113M3P∨

Q∨R0102M2P∨Q∨

R0011M1P∨Q∨R0000M0大項(xiàng)表示二進(jìn)制數(shù)十進(jìn)制數(shù)M(i)十下面表格列出三個變元，且Ｐ、Ｑ、Ｒ的位置已固定，大項(xiàng)表達(dá)如下：對主合取范式編碼的方法：(1)將大項(xiàng)中的變元按照固定次序排列；(2)用二進(jìn)制表示出其對應(yīng)的大項(xiàng)，將大項(xiàng)中變元的肯定用0表示，變元的否定用1表示；(3)將二進(jìn)制轉(zhuǎn)變?yōu)槭M(jìn)制，用Mi表示大項(xiàng)；(4)將Mi表示的各大項(xiàng)，用合取符號連接，得到編碼表示的主合取范式；(5)取各大項(xiàng)下標(biāo)的十進(jìn)制數(shù)字，按照順序置