析取范式
析取范式
在离散数学中,仅由有限个文字构成的合取式称为简单合取式,而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的存在性:任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。
简单析取式
析取
析取是最常用的逻辑联结词之一,表示“或”的意思。析取是逻辑和数学概念中的一个二元逻辑算符。其运算方法是:如果其两个变量中有一个真值为“真”,其结果为“真”,两个变量同时为假,其结果为“假”。析取在数据挖掘和数据库等很多领域都有广泛应用。
定义
命题变项及其否定统称作文字,仅由有限个文字构成的析取式称为简单析取式;仅由有限个文字构成的合取式称为简单合取式
例如, 等为一个文字构成的简单析取式。一个文字既是简单析取式,又是简单合取式。
简单析取式:
简单合取式:
定理
(1)一个简单析取式重言式当且仅当它同时含某个命题变项及它的否定。
(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。
析取范式
定义
(1)由有限个简单合取式构成的析取式称为析取范式。
(2)由有限个简单析取式构成的合取式称为合取范式
(3)析取范式与合取范式统称为范式。
设 为简单的合取式,则 为析取范式。
例如,析取范式:
合取范式:
定理
(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。
(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
存在性
范式存在定理:任一命题公式都存在着与之等值的析取范式与合取范式。
注意:命题公式的析取范式与合取范式都不是唯一的。
证明:
1、由蕴涵等值式和等价等值式可知,
因而,在等值的条件下,可消去任何公式中的联结词 和
2、用双重否定率和德摩根律,可得
3、利用分配律,可得
求析取范式
步骤
第一步:消去联结词和;
第二步:消去否定号 ;
第三步:利用分配律。
示例
求公式 的析取范式与合取范式。
解:
(1)合取范式:
(2)析取范式
主析取范式
设由n个命题变项构成的析取范式中所有简单合取项都是极小项,则称该析取范式为主析取范式。主析取范式存在且惟一。
参考资料
最新修订时间:2022-08-26 11:35
目录
概述
简单析取式
参考资料