16.2 析取范式与合取范式
本章目录 · 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否定”。
【定理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。⊕表示异或,不能误读为普通或。
全加器输入x,y,,输出s,。原书输入名c′只是与输出c区别的名称,撇号在这里不是对输出取反;现用下标明确。
按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∧,再把两个进位送入或门。
半加器也给出完整的二位二进制结果,只是没有进位输入,不能说其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可相互确定。
