离散件1-与命题逻辑(离散数学课件) .ppt

P Q R | （P ? ? Q） ? ? （ P ? R ） 0 0 0 | 0 0 0 1 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0 | 1 1 0 1 | 0 1 1 0 | 1 1 1 | 1 从表中可知，有 5种解释使公式取值0，它们分别是 0 0 0，0 0 1，0 1 0，0 1 1，1 0 1 根据极大项性质 3），可以得到相应的 5个极大项： P ? Q ? R， P ? Q ? ? R， P ? ? Q ? R， P ? ? Q ? ? R， ? P ? Q ? ? R 因而，公式（P ? ? Q） ? ? （ P ? R ）的主合取范式为 ：（P?Q?R）?（P?Q??R）?（P??Q?R） ?（P??Q? ?R）?（?P?Q? ?R） 等价变换法：先把公式化成等价的合取范式，如果某个子式中不含原子 X 及其否定? X，则在这个子式中增加一个永假式（X ? ? X），并按分配律展开，最后按幂等律合并相同极大项即可。 例：采用等价变换法求公式 （P ? ? Q） ? ? （ P ? R ) 的主合取范式。 解： （P ? ? Q） ? ? （ P ? R ） ? ?（?P ? ? Q）? ?（ ? P ? R ） ? （P ? Q）?（ P ? ? R ） ? P ?（Q ? ? R ） （合取范式） ?（P ?（Q ? ? Q）?（R ? ? R））? （（P ? ? P） ? Q ? ? R ） ?（P?Q? R）?（P?Q? ? R）?（P? ? Q? R） ?（P? ?Q? ?R） ?（?P?Q??R） 可见，这个结果与采用真值表法完全相同。 3。主析取范式 1）定义：如果一个公式的析取范式是由极小项构成的，则称这个范式为主析取范式。 2）求一个公式的主析取范式的方法 真值表法：根据极小项的性质 3），在公式的真值表中找出对应于公式值为 1的全部解释，构造相应的极小项，由这些极小项构成主析取范式。 例：利用真值表法求公式 （P ? ? Q） ? ? （ P ? R ） 的主析取范式。 解：构造真值表如下： P Q R | （P ? ? Q） ? ? （ P ? R ） 0 0 0 | 0 0 0 1 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0 | 1 1 0 1 | 0 1 1 0 | 1 1 1 | 1 从表中可知，有3种解释使公式取值1，分别是 1 0 0， 1 1 0， 1 1 1, 根据极小项性质3），可得到相应的极小项是： P ? ? Q ? ? R， P ? Q ? ? R， P ? Q ? R 因而，公式（P? ? Q）? ?（P ? R）的主析取范式为 （P? ?Q? ?R）?（P?Q? ?R）?（P? Q? R） 等价变换法：先把公式化成等价的析取范式，如果某个短语中不含原子 X 及其否定 ? X， 则在这个短语中增加一个永真式（X? ? X），并按分配律展开，最后按幂等律合并相同极 小项即可。 例：求公式 （P ? ? Q