离散数学课件第一章(第4讲)

对偶原理（对偶定律）《定义》：给定命题公式Ａ，若用Λ代换∨，用∨代换Λ，用Ｔ代换Ｆ，用Ｆ代换Ｔ，得到另一个命题公式A*，则称Ａ和A*是互为对偶的。例：写出下列命题公式的对偶式：Ｐ∨（ＱΛＲ）ＰΛ（Ｑ∨Ｒ）Ｐ∨Ｆ对偶式A*ＰΛＴＰ∨ＴＰΛＦ§5对偶与范式讨论定义：（１）若命题公式中有联结词，，则必须把化成由联结词Λ，∨，

组成的等价的命题公式，然后求它的对偶式；例：求(P

Q)

(P

R)的对偶式(P

Q)

(P

R)

（¬Ｐ∨Ｑ）

Λ（¬Ｐ∨R）

则其对偶式为：（¬ＰΛＱ）∨

（¬ＰΛR）

（２）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。例：（ＰΛＱ）∨Ｒ对偶式写成（Ｐ∨Ｑ）ΛＲ，而不能写成Ｐ∨ＱΛＲ《定理》：（摩根推广定理）设Ａ和A*为对偶式,P1,P2．．．Pn

是出现在Ａ和A*中的所有原子命题变元，于是有：¬Ａ（P1，P2．．．Pn）

A*

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

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

¬（Ｐ∨Ｑ）

¬ＰΛ¬Ｑ—（１）

¬Ｐ∨¬Ｑ

¬（ＰΛＱ）—（２）

例：设Ａ（Ｐ，Ｑ，Ｒ）

¬ＰΛ¬

（Ｑ∨Ｒ），验证上述定理：证明：(１)Ａ（Ｐ，Ｑ，Ｒ）

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

Ｐ∨Ｑ∨Ｒ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）证明：设：P1、P2．．．Pn

是出现在Ａ和Ｂ中的原子命题变元，∴Ａ*（¬P1，¬P2．．．¬Pn）

Ｂ*（¬P1,¬P2．．．¬Pn）为永真式由于永真式的代换实例仍为永真式，所以用¬Pi代换A*和B*中的Pi

（1≤i≤n)则得：Ａ*（¬

¬P1，¬

¬P2．．．¬

¬Pn）

Ｂ*（¬

¬P1，¬

¬P2．．．¬

¬Pn）即为：Ａ*（P1，P2．．．Pn）

Ｂ*（P1，P2．．．Pn）范式把命题公式化归为一种标准的形式，称此标准形式为范式。1．析取范式和合取范式：[定义]一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨…∨An(n≥1),其中A1，A2，…，An都是由命题变元或其否定所组成的合取式。如：（Ｐ∧Ｑ∧Ｒ）∨（¬Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）是一个析取范式判定二个命题公式等价，还可以使用范式方法。（１）利用等价公式：化去“→”、“

”联结词，把命题公式变为与其等价的用{¬，∧，∨}表达的公式。

例:Ｐ→Ｑ

¬Ｐ∨Ｑ，Ｐ↔Ｑ

（Ｐ→Ｑ）∧（Ｑ→Ｐ）

（¬Ｐ∨Ｑ）∧（¬Ｑ∨Ｐ）（２）将“¬”深入到原子命题变元之前，并使变元之前最多只有一个“¬”词。例：¬（¬Ｐ∨¬Ｑ）

¬

¬Ｐ∧¬

¬Ｑ

Ｐ∧Ｑ求析取范式的方法可按下列三步（或四步）进行：（３）利用“∧”对“∨”的分配律，将公式化为析取范式。（４）除去永假项得最简析取范式。例：求¬(（Ｐ∧¬Ｑ）→R)∨((P→¬Q)

∧Q)的析取范式原式

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

∨

(（¬Ｐ∨¬Ｑ）∧Q)

——化去“→”词

(（Ｐ∧¬Ｑ）∧¬R)

∨(（¬Ｐ∨¬Ｑ）

∧Q)

——“¬”深入到变元前，并最多保留一个（Ｐ∧¬Ｑ∧¬R)

∨（¬Ｐ∧Ｑ）∨（¬Q∧Ｑ）

——“∧”对“∨”的分配律（Ｐ∧¬Ｑ∧¬R)

∨（¬Ｐ∧¬Ｑ）——去掉永假的合取项注：给定一命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。[定义]一个命题公式称为合取范式，当且仅当它具有形式：A1∧A2∧…∧An(n≥1),其中A1，A2，…，An都是由命题变元或其否定所组成的析取式。如：（Ｐ∨Ｑ∨Ｒ）∧（¬Ｐ∨Ｑ）∧（Ｐ∨¬Ｑ）是一个合取范式。求一个命题公式的合取范式的方法和求析取范式的方法类同：（１）利用等价公式：化去“→”、“

”联结词，把命题公式变为与其等价的用{¬，∧，∨}表达的公式。（２）将“¬”深入到原子命题变元之前，并使变元之前最多只有一个“¬”词。（３）利用“∨”对“∧”的分配律，将公式化为合取范式；（４）去掉永真的析取项。例：求(Ｑ∨¬（Ｐ→Ｑ）)∧¬（Ｐ∧Ｑ）的合取范式原式

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

——化去“→”词

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

——“¬”深入到变元前，并最多保留一个（（Ｑ∨Ｐ）∧（Ｑ∨¬Ｑ））∧（¬Ｐ∨¬Ｑ）

——“∨”对“∧”的分配（Ｑ∨Ｐ）∧（¬Ｐ∨¬Ｑ））——去掉永真的析取项注：给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。2．主析取范式[定义]在ｎ个变元的合取项中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此合取项为小项。例:具有二个命题变元的命题公式,小项最多有22=4个,即Ｐ∧Ｑ、¬Ｐ∧Ｑ、Ｐ∧¬Ｑ、¬Ｐ∧¬Ｑ

具有三个命题变元的命题公式，小项最多有23=8个，即：Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧¬Ｒ、Ｐ∧¬Ｑ∧Ｒ、Ｐ∧¬Ｑ∧¬Ｒ、¬Ｐ∧Ｑ∧Ｒ、¬Ｐ∧Ｑ∧¬Ｒ、¬Ｐ∧¬Ｑ∧Ｒ、¬Ｐ∧¬Ｑ∧¬Ｒ推广：具有ｎ个命题变元的命题公式的小项最多有2n个（n∈I+）。[定义]对于给定的命题公式，若干个小项的析取称为该命题公式的主析取范式。[定理]在真值表中，一个命题公式的所有真值为Ｔ的指派所对应的小项的析取，即为此命题公式的主析取范式。例：根据真值表，分别求出Ｐ→Ｑ、Ｐ∨¬Ｑ、Ｐ

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

QＰ∨¬ＱＱＰ则根据真值表可直接写出各命题公式的主析取范式：Ｐ→Ｑ

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

（¬Ｐ∧¬Ｑ）∨（Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）P

Q

（¬Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）讨论此定理：（1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该命题公式真值为“Ｔ”的行，对应写出小项的析取式，命题公式的主析取范式一定是唯一的。（2）由真值表找小项的方法为：将表中值为“T”所对应的真值指派中，T对应变元本身，F对应变元的否定。（3）命题公式的主析取范式中小项的个数一定等于对应真值表中真值为“Ｔ”的个数。（4）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。

下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：（１）将命题公式化为与其等价的析取范式；

（２）除去永假项，合并合取项中相同项例：Ｐ∧¬Ｐ∧Ｑ为永假项，去掉。Ｐ∧Ｐ∧Ｑ

Ｐ∧Ｑ，合并合取项中相同项（３）对合取项补入没有出现的命题变元，即添加（合取）例如（Ｐ∨¬P）的形式，并应用∧对∨的分配律展开公式。例：若命题公式有二个变元Ｐ、Ｑ，当析取范式中的某一项缺少变元时，利用“∧”对“∨”的分配律添项：Ｐ

Ｐ∧（Ｑ∨¬Ｑ）

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

Ｑ∧（Ｐ∨¬Ｐ）

（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）（４）合并相同的小项。

（Ｐ∧Ｑ）∨Ｑ

----（2）消去永假项，变为最简析取范式

（Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨¬Ｐ））----（3）添项

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

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

----（4）合并相同小项例：求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式解：原式

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

----（1）化为析取范式例：证明Ｐ∨（¬Ｐ∧Ｑ）

Ｐ∨Ｑ证明方法是写出二命题公式的主析取范式，看其是否相同：Ｐ∨（¬Ｐ∧Ｑ）

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

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

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

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

（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）两个命题公式主析范式相同，∴Ｐ∨（¬Ｐ∧Ｑ）

Ｐ∨Ｑ3．主合取范式[定义]在ｎ个变元的析取项中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种析取项为大项。例：具有二个变元Ｐ,Ｑ的命题公式，其大项最多有22=4个：（Ｐ∨Ｑ）、（Ｐ∨¬Ｑ）、（¬Ｐ∨Ｑ）、（¬Ｐ∨¬Ｑ）具有ｎ个变元的命题公式，其大项最多有2n个（n∈I+）。[定义]对于给定的命题公式，若干个大项的合取称为该命题公式的主合取范式。[定理]在真值表中，一个命题公式的所有真值为F的指派所对应的大项的合取，即为此命题公式的主合取范式。

在真值表中真值为“Ｆ”的个数等于主合取范式中大项的个数。Ｐ

ＱＰ∧ＱＱＰTTTTTFFFFTTFFTFTTFFF例：根据真值表，分别求出Ｐ→Ｑ、Ｐ∧Ｑ、Ｐ

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

（Ｐ∨Ｑ）∧（Ｐ∨¬Ｑ）∧（¬Ｐ∨Ｑ）根据真值表，可直接写出各命题公式的主合取范式：Ｐ→Ｑ

¬Ｐ∨ＱＰ

Ｑ

（Ｐ∨¬Ｑ）∧（¬Ｐ∨Ｑ）讨论：（1）该命题公式的主合范式中大项的个数等于其真值表中真值为“Ｆ”的个数。（2）由真值表找大项的方法为：将表中值为“Ｆ”所对应的真值指派中，T对应变元的否定，F对应变元本身。（3）只要命题公式不是永真式，则一定可以写出与其等价的唯一的主合取范式。（4）可用主合取范式判定二个命题公式是否等价。（5）对应于有ｎ个变元的命题公式，则一定有：主析范式小项数＋主合范式大项数＝2n下面介绍不用真值表求一命题公式主合取范式的方法：（1）将命题公式化为与其等价的合取范式；（2）除去永真项，合并析取项中相同变元，变为最简合取式；例：Ｐ∨¬Ｐ∨Ｑ为永真项，去掉。Ｐ∨Ｐ∨Ｑ

Ｐ∨Ｑ，合并析取项中相同变元。

（3）对析取项补入没有出现的命题变元，即添加(析取)例如（Ｐ∧¬P）的形式，并应用∨对∧的分配律展开公式。例：若命题公式有二个变元Ｐ、Ｑ，当合取范式中的某一项缺少变元时，利用“∨”对“∧”的分配律添项：即：Ｐ

Ｐ∨（Ｑ∧

Ｑ）

（Ｐ∨Ｑ）∧（Ｐ∨

Ｑ）（4）合并相同的大项。

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

Ｐ∧（¬Ｐ∨Ｑ）∨Ｑ

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

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

----合并析取项中相同变元，化为最简合取范式

（Ｐ∨Ｑ）∧(Ｑ∨（

Ｐ∧Ｐ）)

----添项

（Ｐ∨Ｑ）∧（

Ｐ∨Ｑ）∧（Ｐ∨Ｑ）

（Ｐ∨Ｑ）∧（

Ｐ∨Ｑ）

----合并相同大项4．主析(合)取范式的编码表示为了能够用编码的形式表达主析(合)取范式，作如下规定：小项和大项中的各命题变元的出现位置必须安排一固定次序。（１）小项的编码对于有ｎ个变元的命题公式，则最多可有2n个小项，用mi表示小项，用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小项表示二进制数十进制数m(i)十下面表格列出三个变元，且Ｐ、Ｑ、Ｒ的位置已固定，小项表达如下：对主析取范式编码的方法：(1)将小项中的变元按照固定次序排列；(2)用二进制表示出其对应的小项，将小项中变元的肯定用1表示，变元的否定用0表示；(3)将二进制转变为十进制，用mi表示小项；(4)将mi表示的各小项，用析取符号连接，得到编码表示的主析取范式；(5)取各小项下标的十进制数字，按照顺序置于

符号后，可进一步简化编码表示主析取范式。解：原式

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

Ｒ）

∨（

Ｐ∧

Ｑ∧Ｒ）∨（

Ｐ∧Ｑ∧Ｒ）

m(111)∨

m(110)∨

m(001)∨

m(011)

m7∨

m6∨

m1∨

m3

m1,m3,m6,m7

1,3,6,7

例：求（Ｐ∧Ｑ）∨（

Ｐ∧Ｒ）的主析取范式的编码表达式：（设小项按照Ｐ、Ｑ、Ｒ次序固定）（2）大项的编码对于有ｎ个变元的命题公式，则最多可有2n个大项，用Mi表示大项，用M0

∨M1…

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

P∨

Q∨

R1117M7

P∨

Q∨R1106M6

P∨Q∨

R1015M5

P∨Q∨R1004M4P∨

Q∨

R0113M3P∨

Q∨R0102M2P∨Q∨

R0011M1P∨Q∨R0000M0大项表示二进制数十进制数M(i)十下面表格列出三个变元，且Ｐ、Ｑ、Ｒ的位置已固定，大项表达如下：对主合取范式编码的方法：(1)将大项中的变元按照固定次序排列；(2)用二进制表示出其对应的大项，将大项中变元的肯定用0表示，变元的否定用1表示；(3)将二进制转变为十进制，用Mi表示大项；(4)将Mi表示的各大项，用合取符号连接，得到编码表示的主合取范式；(5)取各大项下标的十进制数字，按照顺序置