离散数学——范式(一)定义与求解
概览
-
范式的定义
-
范式的求解
范式的定义
1.引入范式
对于真值表,n个命题变元,真值表要列出2的n次方个解释。当n的数值过大时,真值表就不再简便,因此引入范式。
范式的定义自下而上, 正如语文中字组成词,词组成句。
命题变元或命题变元的否定称为文字
有限个文字的析取称为简单析取式(子句),要注意有限个包括一个,因此单独的文字也可以称为简单析取式(子句)。
同理,单独的一个文字也可以称为简单合取式(短语)。
2,范式的命名
有限个包括一个,因此一个短语也可以称为析取范式,又因为单独的文字也属于是短语,所以单独的文字也可以称为析取范式。
同理,单独的子句或文字也可以称为是合取范式。
例题解析.(2)将整个命题变元看做一个子句,则这个命题变元又可以称为合取范式;将P,Q,非R都看做短语(文字可以是短语),则整个命题变元可以称为析取范式
(3)将整个命题变元看做一个短语,则这个命题变元又可以称为是析取范式:若把非P,Q,R都看做子句(文字可以是子句),则整个命题变元可以称为合取范式
注意:当整体加上括号后,只能整体来论,不能拆开
因此整体加上括号后的(2)不能称为析取范式;整体加上括号后的(3)不能称为合取范式。
(4)括号内的是一个整体,是子句,把p看做子句,子句和子句的析取啥也不是
范式的求解
1.范式存在定理
熟记逻辑等价公式才能准确快速地将命题公式化成与其等价的析取范式和合取范式
转化的步骤一般为
- 转化蕴涵关系等价关系
- 否定连接词的转移
- 利用其他逻辑公式将命题公式装化成析取范式或合取范式
2范式求解定理
步骤解析
- 消去蕴含关系,等价关系
- 使用分配律
- 去掉大括号里面的小括号
- 合并(析取或合取)相同的命题变元(或其否定)
- 一路转化得到最终结果
一般而言,最终得到的合取范式或析取范式都是最简式。