写成CNF的语句形如((AVIP免费

6 .0 3 4 笔记：1 0 .1 部分 幻灯片 1 0 .1 .1 写成CNF的语句形如((A or B or not C) and (B or D) and (not A) and (B or C)). 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨ 幻灯片 1 0 .1 .2 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：•是一个子句()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨()ABC∨∨ ¬它的最外层结构是一个多重单元的连接。这些单元称做字句。 幻灯片 1 0 .1 .3 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：•构成一个子句。它是一些文字的析取。• A, B, 和C是文字。()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨()ABC∨∨ ¬¬一个字句是很多东西的析取，构成字句的单元叫做文字。 幻灯片 1 0 .1 .4 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：•构成一个子句。它是一些文字的析取。• A, B, 和C是文字。它们是一个变量或是变量的否定。()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨()ABC∨∨ ¬¬文字是一个变量或是变量的非。 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：•构成一个子句。它是一些文字的析取。• A, B, 和C是文字。它们是一个变量或是变量的否定。• 每个子句都是一个条件。它必须而且可以有多种方式得以满足。()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨()ABC∨∨ ¬¬幻灯片 1 0 .1 .5 这样你就有了一种哪里的否定被插入得最集中的表达方式，你也就有了或和且的关系。着就好比说没一个分配必须满足一系列的要求。你可以把每一个字句看成一个要求。这样一来，第一条字句要先被满足，着有很多方式，第二条也要被满足，接着是第三条，依次类推。 幻灯片 1 0 .1 .6 命题逻辑中的每一个语句都可以写成CNF的形式 合取范式• 合取范式（conju nctiv e normal form, CNF）公式：•构成一个子句。它是一些文字的析取。• A, B, 和C是文字。它们是一个变量或是变量的否定。• 每个子句都是一个条件。它必须而且可以有多种方式得以满足。• 命题逻辑中的每一个语句都可以写成CNF的形式。()()()()ABCBDABC∨∨ ¬∧∨∧ ¬∧∨()ABC∨∨ ¬¬ 幻灯片 1 0 .1 .7 这里是把语句转化成CNF的过程。 转换为CNF 幻灯片 1 0 .1 .8 第一步是根据定义消去单箭头或双...