从上节可看到命题公式的最小联结词组为{┓, ∨}或{┓, ∧},但实际上为了使用方便,命题公式常常同时包含{┓, ∨,∧}.我们从表1-4.8可以看到命题定律除对9外都是成对出现的,其不同的只是∨和∧互换.我们把这样的公式称作具有对偶规律.
定义1-7.1 在给定的命题公式中,将联结词∨换成∧,将∧换成∨,若有特殊变元f和t亦相互取代,所得公式a*称为a的对偶.
显然a也是a*的对偶式.
例题1 写出下列表达式的对偶式.
(a) （p∨q）∧r
(b) （p∧q）∨t
(c) ┓(p∨q) ∧（p∨┓(q∧┓s)）
解 这些表达式的对偶式是:
(a) （p∧q）∨r
(b) （p∨q）∧f
(c)┓(p∧q)∨（p∧┓(q∨┓s)）
例题2 求p↑q,p↓q的对偶式
解 因为p↑q┓(p∧q)，故p↑q的对偶式为┓（p∨q），即p↓q。同理p↓q的对偶式是p↑q。
定理1-7.1 设a和a*是对偶式，p1，p2，……，pn是出现在a和a*中的原子变元，则
┓a（p1，p2，……，pn） a*（┓p1，┓p2，……，┓pn）
a（┓p1，┓p2，……，┓pn）┓a*（p1，p2，……，pn）
证明 由德摩根定律
p∧q┓(┓p∨┓q)，p∨q┓(┓p∧┓q)
故
┓a（p1，p2，……，pn） a*（┓p1，┓p2，……，┓pn）
同理
┓a*（┓p1，┓p2，……，┓pn）a（┓p1，┓p2，……，┓pn）
例题3 设a*（s，w，r）是┓s∧（┓w∨r），证明
a*（┓s，┓w，┓r）┓a（s，w，r）
证明由于a*（s，w，r）是┓s∧（┓w∨r），则a*（┓s，┓w，┓r）是s∧（w∨┓r）。但 a（s，w，r）是┓s∨（┓w∧r），故┓a（s，w，r）是┓（┓s∨（┓w∧r） s∧（w∨┓r）。
所以 a*（┓s，┓w，┓r）┓a（s，w，r）
定理1-7.2 设 p1，p2，……，pn是出现在公式a和b中的所有原子变元，如果ab，则a*b*。
证明 因为ab，即
a（p1，p2，……，pn）b（p1，p2，……，pn）
是一个重言式，故
a（┓p1，┓p2，……，┓pn）b（┓p1，┓p2，……，┓pn）也是一个重言式。即
a（┓p1，┓p2，……，┓pn）b（┓p1，┓p2，……，┓pn）
由定理1-7.1得
┓a*（p1，p2，……，pn） ┓b*（p1，p2，……，pn）
因此a*b*
例题4如果a（p，q，r）是p↑（q∧┓（r↓p）），求它的对偶式a*（p，q，r）。并求它与a及a*等价，但又包含联结词“∧”“∨”及“┓”的公式。
解 因a*（p，q，r）是p↑（q∧┓（r↓p））
故a*（p，q，r）是p↑（q服务器托管网∧┓（r↓p））
但p↑（q∧┓（r↓p））┓（p∧（q∧（r∨p）））
所以p↓（q∨┓（r↑p））┓（p∨（q∨（r∧p）））
从真值表和对偶律等可以简化或推证一些命题公式。同一命题公式可以有各种相互等价的表达形式，为了把命题公式规范化，下面讨论命题公式的范式问题。
定义1-7.2 一个命题公式称为合取范式，当且仅当它具有型式：a1∧a2∧……∧an，（n>=1）
其中a1,a2,……,an都是由命题变元或其否定所组成的析取式.
例如(p∨┓q∨r)∧(┓p∨q) ∧┓q是一个合取范式.
定义1-7.3 一个命题公式称为析取范式,当且仅当它具有型式:a1∨a2∨……∨an，（n>=1）
其中a1,a2,……,an都是由命题变元或其否定所组成的合取式.
例如 ┓p∨（p∨q ）∨(p∧┓q∧r)是析取范式.
任何一个命题公式,求它的合取范式或析取范式,可以通过下面三个步骤进行:
(1) 将公式中的联结词化归成∧, ∨及┓.
(2) 利用德摩根定律将否定符号┓直接移到各个命题变元之前.
(3) 利用分配律,结合律将公式归约为合取范式或析取范式.
例题5 求(p∧(q→r))→s的合取范式.
解(p∧(q→r))→s (p∧(┓q∨r))→s
┓(p∧(┓q∨r))→s┓p∨(q∧┓r)) ∨s
（┓p∨s）∨(q∧┓r)
（┓p∨s∨q）∧（┓p∨s∨┓r）
例题6 求┓(p∨q) (p∧q)的析取范式.
解 因为有公式（ab）（a∧b）（┓a∧┓b）
故 ┓（p∨q）（p∧q） （┓（p∨q）∧（p∧q））∨（（p∨q）∧┓（p∧q））
（┓p∧┓q∧p∧q）∨（p∨q）∧（┓p∨┓q）
（┓p∧┓q∧p∧q）∨（p∨┓p）∧（q∨┓p）∨ （p∧┓q）∨（q∧┓q）
一个命题公式的合取范式或析取范式并不是唯一的。例如p∨（ q∧r）是一个析取范式，但它亦可以写成
p∨（ q∧r）（p∨ q）∧（p∨r）
（p∧ p）∧（p∧r）∨ （q∧p）∨（q∧r）
为了使任意一个命题公式，化成唯一的等价命题的标准形式，下面介绍主范式的有关概念。
定义1-7.4n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
例如，两个命题变元p和q，其小项为：p∧q，p∧┓q，┓p∧q，┓p∧┓q。
三个命题变元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。
一般说来，n个命题变元共有2n个小项。
表7-7.1列出两个变元p和q及其小项的真值表。
从这个真值表中可以看到，没有两个小项是等价的，且每个小项都只对应p和q的一组真值指派，使得该小项的真值为t。
这个结论可以推广到三个以上的变元情况，并且由此可以作表1-7.1
|
p |
q |
p∧q |
p∧┓q |
┓p∧q |
┓p∧┓q |
|
t |
t |
t |
f |
f |
f |
|
t |
f |
f |
t |
f |
f |
|
f |
t |
f |
f |
t |
f |
|
f |
f |
f |
f |
f |
t |
表1-7.2
|
p |
q |
r |
┓p∧┓q∧┓r |
┓p∧┓q∧r |
┓p∧q∧┓r |
┓p∧q∧r |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
p |
q |
r |
p∧┓q∧┓r |
p∧┓q∧r |
p∧q∧┓r |
p∧q∧r |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
1 |
m000=┓p∧┓q∧┓r m100=p∧┓q∧┓r
m001=┓p∧┓q∧r m101=p∧┓q∧r
m010=┓p∧q∧┓r m110=p∧q∧┓r
m011=┓p∧q∧r m011=p∧q∧r
出一种编码，使n个变元的小项可以很快地写出来。现按三个变元为例说明如下。
设p，q，r为三个命题变元，其真值t和f分别记为“1”和“0”，则小项的真值表如表1-7.2所示。
小项有如下几个性质：
(1) 每一个小项当其真值指派与编码相同时，其真值为t，在其余2n-1种指派情况下均为f。
(2) 任意两个不同小项的合取式永假。例如
m001∧m100=（┓p∧┓q∧r）∧（p∧┓q∧┓r）
┓p∧p∧┓q∧r∧┓r f
(3) 全体小项的析取式永为真，记为：
2n-1
∑mi =m0∨ m1∨ m2∨…∨ m2n-1 t
i=0
定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。
一个公式的主析取范式可用构成真值表的方法予以写出。
定理1-7.3 在真值表中，一个公式的真值为t的指派所服务器托管网对应的小项的析取，即为此公式的主析取范式。
证明 设给定公式为a，其真值为t的指派所对应的小项为m1’，m2’，…… mk’，这些小项的析取式记为b，为 此要证ab，即要证a与b在相应指派下具有相同真值。
首先对a为t的某一指派，其对应的小项为mi’，则因为mi’为t，而m1‘，m2’，…… mi-1‘，mi+1‘……，mk‘均为f，故b为t。
其次，对a为f的某一指派，其对应的小项不包含在b中，即m1‘，m2’，…… mk‘均为f，故b为f。因此ab。
例题6 给定p→q，p∨q和┓（p∧q），求这些公式的主析取范式。
解 三公式的真值表如表1-7.3所示。故
p→q（┓p∧┓q）∨（┓p∧q）∨（p∧q）
p∨q（┓p∧q）∨（p∧┓q）∨（p∧q）
┓（p∧q） （┓p∧┓q）∨（┓p∧q）∨（p∧┓q）
表1-7.3
|
p |
q |
p→q |
p∨q |
┓（p∧q） |
|
t |
t |
t |
t |
f |
|
t |
f |
f |
t |
t |
|
f |
t |
t |
t |
t |
|
f |
f |
t |
f |
t |
例题7 设一公式a的真值表如表1-7.4所示。
表1-7.4
|
p |
q |
r |
a |
|
t |
t |
t |
t |
|
t |
t |
f |
f |
|
t |
f |
t |
f |
|
t |
f |
f |
t |
|
f |
t |
t |
f |
|
f |
t |
f |
f |
|
f |
f |
t |
f |
|
f |
f |
t |
t |
求公式a 的主析取范式。
解 公式a的主析取范式为：
a（ p∧q∧r）∨（p∧┓q∧┓r）∨（┓p∧┓q∧┓r）
除了用真值表方法外，也可利用等价公式构成主析取范式。
例题8求（p∧q） ∨（┓p∧r）∨（q∧r）的主析取范式。
解 原式（ p∧q∧（r∧┓r））∨（┓p∧r∧（q∨┓q））∨（q∧r∧（p∨┓p））
（ p∧q∧r）∨（p∧q∧┓r）∨（┓p∧q∧r）∨（┓p∧q∧r）
例题9试求p→（（p→q）∧┓（┓q∨┓p））的主析取范式。
解 p→（（p→q）∧┓（┓q∨┓p））
┓p∨（（┓p∨q）∧（p∧q）
┓p∨（（┓p∧q∧p）∨（q∧q∧p））
┓p∨（（┓p∧q∧p）∨（q∧p）
┓p∨（q∧p）
（┓p∧（q∨┓q））∨（q∧p）
（┓p∨q）∨（┓p∨┓q）∨（p∧q）
由上述各例我们看到，一个命题公式的主析取范式，可由两种方法构成。一是由公式的真值表得出，另一是由基本等价公式推出。其推演步骤可归纳为：
（1）化归为析取范式。
（2）除去析取范式中所有永假的析取项。
（3）将析取式中重复出现的合取项和相同的变元合并。
（4）对合取项补入没有出项的命题变元，即添加（p∨┓p）式，然后，应用分配律展开公式。
对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式便是唯一的，因此，给定任两个公式，由主析取范式可以方便地看出两个公式是否等价。
与主析取范式类似的是主合取范式。
定义1-7。6 n个明天变元的析取式，称作布尔析取或大项，其中每个变元与他的否定不能同时出现，但两者必须出现且仅出现一次。例如：
p∨q，p∨┓q，┓p∨q，┓p∨┓q
又如 p∨q∨r， p∨q∨┓r，… ┓p∨┓q∨┓r
每个大项可用n位二进制予以编码：
若n=2
m00=p∨q m01=p∨┓q
m10=┓p∨q m11=┓p∨┓q
若n=3
m000= p∨q∨r， m100= ┓p∨q∨r
m001= p∨q∨ ┓r，m101= ┓p∨q∨ ┓r
m010= p∨┓q∨r， m110=┓ p∨┓q∨r
m011= p∨┓q∨┓r， m111=┓ p∨┓q∨┓r
大项有如下性质：
（1）每一个大项当其真值指派与编码相同时，其真值为f，在其余2n-1种真值指派情况下均为t。
（2）任意两个不同大项的析取式永真。
ｍｉ∨ｍｊt (i ≠ j)
（3）全体大项的合取式永为假。 记为：
2n-1
ii mi =m0∧m1∧…∧m 2n-1 f
i=0
定义1-7.7 对于给定的命题公式a，如果有一个等价公式a’，它仅由大项的合取所组成，则称a’为a的主合取范式（majorconjunctivenormalform）。
一个公式主合取范式可以构成真值表的方法写出。
定理1-7.4在真值表中，一个公式的真值为f的指派所对应的大项的合取，即为次公式的主合取范式。
证法与定理1-7.3相同。
例题10 利用真值表技术求（p∧q）∨（┓p∧r）的主合取范式与主析取范式。
解 公式 （p∧q）∨（┓p∧r）的真值表如表1-7.5所示。
表1-7.5
|
p |
q |
r |
p∧q |
┓p∧r |
（p∧q）∨┓p∧r） |
|
t |
t |
t |
t |
f |
t |
|
t |
t |
f |
t |
f |
t |
|
t |
f |
t |
f |
f |
f |
|
t |
f |
f |
f |
f |
f |
|
f |
t |
t |
f |
t |
t |
|
f |
t |
f |
f |
f |
f |
|
f |
f |
t |
f |
t |
t |
|
f |
f |
f |
f |
f |
f |
故主合取范式为：
（p∧q）∨（┓p∧r）（┓p∨q∨┓r）∧（┓p∨q∨r）∧（p∨┓q∨r）∧（p∨q∨r）
主析取范式为：
（p∧q）∨（┓p∧r）（p∨q∨r）∨（p∨q∨┓r）∨（┓p∨q∨r）∨（┓p∨┓q∨r）
一个公式的主合取范式，亦可用基本等价式推出，其推演步骤为：
（1）化归为合取范式。
（2）除去合取范式中所有永真的合取项。
（3）将合取式中重复出现的析取项和相同的变元合并。
（4） 对析取项补入没有出现的命题变元，即添加（p ∧┐ p）式，然后，应用分配律展开公式。
例题11 化（p∧q）∨（┓p∧r）为主合取范式。
解 （p∧q）∨（┓p∧r）（p∧q）∨┓p）∧(（p∧q）∨r)
（p∧┐p）∨（┓p∧r）∧(（p∧q）∨r)
（q∨┓p）∧（p∨r）∧（q∨r）
（q∨┓p）∨（ｒ∧┓r））∧（p∨ｒ∨（ｑ∧┓q））∧（ｑ∨ｒ∨（ｐ∧┓p））
（q∨┓p∨ｒ）∧（q∨ ┓p∨┓r）∧（p∨r∨q）∧（p∨r∨┓q）∧（q∨r∨ｐ） ∧（ｑ∨ｒ∨┓ｐ）
（┓ｐ∨ｑ∨ｒ）∧（┓p∨ｑ∨ｒ）∧（p∨┓q∨ｒ）∧（ｐ∨ｑ∨ｒ）
为了使主析取范式和主合去范式表达简洁，我们今后用∑i，j，k，既表示mi∨mj∨mk；用ii表示大项的合取，iii，j，k表示mi∧mj∧mk，由这样的约定，例题10可以表达为：
（p∧q）∨（┓p∧r）m001∨m011∨m110∨m111=∑1，3，6，7 （p∧q）∨（┓p∧r）m000∧m010∧m100∧m101=ii0，2，4，5
可以证明，如果命题公式p的主析取范式为：
∑i1，i2，ik
则p的主合取范式为：
ii0，1，2，…，i1-1，i1+1，…，ik-1，ik+1，…，2n-1
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 如何在long-running task中调用async方法
什么是 long-running thread long-running task 是指那些长时间运行的任务，比如在一个 while True 中执行耗时较长的同步处理。 下面的例子中，我们不断从队列中尝试取出数据，并对这些数据进行处理，这样的任务就适合交给一…
