16.2 析取范式与合取范式

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【16.2 析取范式与合取范式】文字指变项或其否定,例如p、¬q。有限个文字的析取称简单析取式(子句),有限个文字的合取称简单合取式(项)。单个文字同时属于两类;否定若作用于复合式,则必须先内移,才能成为文字。

【定义16.2.1及定理16.2.1】非空简单析取式永真,当且仅当含某个p及¬p;非空简单合取式永假,当且仅当含某个p及¬p。若没有互补对,前者可把每个文字置假,后者可把每个文字置真。重复文字p、p不算互补对。

【定义16.2.2及定理16.2.2】项的析取为析取范式DNF;子句的合取为合取范式CNF。DNF恒假当且仅当每项恒假;CNF恒真当且仅当每个子句恒真。反向的两个类比不成立,例如p∨¬p由两个非永真的项组成却永真,p∧¬p由两个可满足子句组成却不可满足。

例如(p∧¬q)∨(¬q∧¬r)∨p为DNF,(p∨q∨r)∧(¬p∨¬q)∧r为CNF;单个项、单个子句可同时看作两类范式的一种退化表示。

【定理16.2.3 范式存在性】任意命题公式均有等值DNF和CNF。步骤一消去→、↔;步骤二用双重否定、德摩根把¬推到变项前;步骤三求DNF时用∧对∨分配,求CNF时用∨对∧分配;再消重复和互补项。一般DNF、CNF不唯一,最简性也没有由“是范式”自动保证;展开可能导致式子显著增长。

【例16.2.1】F=(p→q)↔r,注意主联结词是↔,不是→。

F⇔((p∧¬q)∨r)∧(¬p∨q∨¬r),继续分配得到CNF:

另一方向展开并删去矛盾项得到DNF:

可逐项检验:第一项对应p→q假、r假;后两项对应p→q真、r真。(例完)

【定义16.2.3 极小项与极大项】先固定全体n个变项及顺序。每个变项以肯定或否定出现恰一次,所有文字合取为极小项mᵢ,所有文字析取为极大项Mᵢ。mᵢ唯一成真赋值是i的n位二进制串;Mᵢ唯一成假赋值也是该串。因此极小项取“1原形、0否定”,极大项正好反过来,取“0原形、1否定”。

i000m0¬p∧¬qM0p∨q101m1¬p∧qM1p∨¬q210m2p∧¬qM2¬p∨q311m3p∧qM3¬p∨¬q
表16.2.1 pq的全部极小项与极大项
i0000m0¬p∧¬q∧¬rM0p∨q∨r1001m1¬p∧¬q∧rM1p∨q∨¬r2010m2¬p∧q∧¬rM2p∨¬q∨r3011m3¬p∧q∧rM3p∨¬q∨¬r4100m4p∧¬q∧¬rM4¬p∨q∨r5101m5p∧¬q∧rM5¬p∨q∨¬r6110m6p∧q∧¬rM6¬p∨¬q∨r7111m7p∧q∧rM7¬p∨¬q∨¬r
表16.2.2 pqr的全部极小项与极大项

【定理16.2.4】¬mᵢ⇔Mᵢ,¬Mᵢ⇔mᵢ,必须使用相同变量集、同一排序及同一个下标i。由德摩根把每个文字取补即得。

【定义16.2.4及定理16.2.5】极小项的析取为主析取范式,极大项的合取为主合取范式。固定变量集及顺序后,每个公式的两种主范式唯一,忽略重复项及无关括号,并按下标递增排列。存在性:DNF中缺p时补乘(p∨¬p),分配至每项含全变量;CNF中缺p时补析取(p∧¬p)。唯一性:若两个主DNF有某个mᵢ只出现于一个,则赋值i使两者一真一假,矛盾;CNF对偶。

规定空析取为0、空合取为1,覆盖矛盾式、重言式边界。主范式的唯一性不意味着任意变量集下写出的下标都相同:将p从一变量扩到pq,主DNF就从m₁变成m₂∨m₃。

【例16.2.2】F=(p→q)↔r。上一例中¬p∧r扩为m₁∨m₃,q∧r扩为m₃∨m₇,第一项已为m₄。删重复得到主DNF:m₁∨m₃∨m₄∨m₇。

CNF中的p∨r扩为M₀∧M₂,¬q∨r扩为M₂∧M₆,末项为M₅,故主CNF=M₀∧M₂∧M₅∧M₆。真赋值001、011、100、111;假赋值000、010、101、110。(例完)

【例16.2.3】p→q⇔¬p∨q=M₂;主DNF=m₀∨m₁∨m₃。它只有一个成假赋值10,三种成真00、01、11。这里极小、极大项都只有两个文字,不能沿用三变量表下标。(例完)

【主范式的用途】主DNF中出现的m下标就是所有成真行,未出现的就是成假行;全部2ⁿ个m都出现为永真,一个也没有为永假,介于两者为偶然式。主CNF的M下标列出所有成假行。比较两公式是否等值,必须先按共同变量集列主范式,再比较下标集合。

【例16.2.4】(1)¬(p→q)∧q⇔p∧¬q∧q⇔0,主DNF为空,矛盾式。(2)p→(p∨q)⇔1,主DNF含m₀,m₁,m₂,m₃,重言式。(3)(p∨q)→r⇔(¬p∧¬q)∨r,按pqr主DNF为m₀∨m₁∨m₃∨m₅∨m₇,是偶然式。(例完)

【例16.2.5】(1)按pq,p与(p∧q)∨(p∧¬q)都为m₂∨m₃,等值。(2)按pqr,(p→q)→r为m₁∨m₃∨m₄∨m₅∨m₇;(p∧q)→r为m₀∨m₁∨m₂∨m₃∨m₄∨m₅∨m₇,不等值。此题是单向外层→,不要与例16.2.1的↔r混用。(例完)

【例16.2.6 选派进修】p、q、r分别表示派A、B、C。要求选1—2人,A去则C同去,B去则C不去;将原题“若C不去,A或B可以去”按其解题意图明确为“C不去时至少派A、B中的一人”,否则纯粹许可并不等于必须选派。

约束T=(p→r)∧(q→¬r)∧(¬r→(p∨q)),其主DNF=m₁∨m₂∨m₅;这些行也满足选派人数1—2。方案为仅C、仅B、A与C同去,共三种。若把人数约束显式加入,也得到同样三行。(例完)

【例16.2.7 半加器与全加器】半加器输入x,y,半和h=x⊕y=(¬x∧y)∨(x∧¬y),进位d=x∧y。⊕表示异或,不能误读为普通或。

xyhd0000011010101101
表16.2.3 半加器:x+y=h+2d

全加器输入x,y,,输出s,。原书输入名c′只是与输出c区别的名称,撇号在这里不是对输出取反;现用下标明确。

xyc_ins0000000110010100110110010101011100111111
表16.2.4 全加器:x+y+=s+2

按x,y,次序,s的主DNF为m₁∨m₂∨m₄∨m₇,的主DNF为m₃∨m₅∨m₆∨m₇;即s在奇数个输入1时为1,进位在至少两个1时为1。

令h=x⊕y、d=x∧y,则s=(h∧¬)∨(¬h∧)=h⊕,=(h∧)∨d。由两个半加器及一个或门实现:第一半加器算h、d,第二算s及h∧,再把两个进位送入或门。

HA1HA2xyc_ins
图16.2.1 两个半加器和一个或门构成全加器,端口与连线逐一标注

半加器也给出完整的二位二进制结果,只是没有进位输入,不能说其h、d本身“不是最终计算结果”。(例完)

【主DNF与主CNF互换】同一公式的m下标集合I与M下标集合J,在{0,…,2ⁿ−1}中互补;不需逐项否定原式,更不能把相同下标的m直接换成M。

【例16.2.8】(1)pq上A=m₁∨m₂,主CNF=M₀∧M₃。(2)pqr上B=m₁∨m₂∨m₃,主CNF=M₀∧M₄∧M₅∧M₆∧M₇。(例完)

重言式主CNF为空合取1;矛盾式主CNF含全部2ⁿ个极大项。两类主范式各有 种,与真值函数一一对应。固定输入顺序,真值表、主DNF、主CNF可相互确定。