一个公式的析取范式唯一
假设有一个公式F,它的析取范式可以表示为D1或D2或...或Dn(其中Di表示一个由原子命题或它们的否定组成的合取式),并且还有另外一种析取范式E1或E2或...或Em可以表示F。
我们需要证明的是,这两种析取范式是等价的,即它们表示的是同一个逻辑表达式。
首先,我们注意到每个合取式Di和Ej都表示F的一个真值赋值,因为它们都是F的合取式,而每个真值赋值要么满足至少一个Di,要么满足至少一个Ej。因此,我们可以得到以下两个结论:
-
对于任何真值赋值,如果它满足某个Di,则它必须不满足所有的Ej(因为Ej表示的真值赋值不包含在Di中)。
-
对于任何真值赋值,如果它满足某个Ej,则它必须不满足所有的Di(因为Di表示的真值赋值不包含在Ej中)。
接下来,我们假设存在一个真值赋值,它既满足某个Di,又满足某个Ej。这意味着它是F的两个真值赋值,这与F的析取范式唯一性相矛盾。因此,不存在这样的真值赋值,即Di和Ej中的任意两个合取式表示的真值赋值是不相交的。
由于Di和Ej的真值赋值是不相交的,我们可以将它们合并成一个新的析取范式D1或D2或...或Dn或E1或E2或...或Em。这个新的析取范式与F等价,因为它包含了所有满足F的真值赋值,而且不包含任何不满足F的真值赋值。因此,我们得出结论:F的析取范式唯一
原文地址: https://www.cveoy.top/t/topic/hxs1 著作权归作者所有。请勿转载和采集!