第2篇数理逻辑ch3命题逻辑.ppt

联结词的优先级 命题公式外层的括号可以省略； 联结词的优先级：┐、∧、∨、→、?。 利用加括号的方法可以提高优先级。 范例：如下的Wff ： P∧Q→R 等价于Wff ： （（P∧Q）→R ） 等价于Wff ： （P∧Q）→R 不等价于Wff ： P∧（Q→R） 全真为假 见假为真。 全假为真 见真为假。 （3）与非 定义3-6.3 设P和Q是两个命题公式， P和Q的与非是一个新命题公式，记作P ? Q。当且仅当P和Q的真值都为 T时， P ? Q 为F ，其他情况下P ? Q的真值都是T 。 根据此定义，可知 P ? Q ? ┐（P∧Q） P ? Q的3个 性质见P-26页。 T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p ? q q p 表3-6.3 与非词“?”的意义 （4）或非 定义3-6.4 设P和Q是两个命题公式， P和Q的或非是一个新命题公式，记作P ? Q。当且仅当P和Q的真值都为 F 时， P ? Q 为T ，其他情况下P ? Q的真值都是F 。 根据此定义，可知 P ? Q ? ┐（P ∨ Q） P ? Q的 性质与联结词性质留给大家自己推算。 表3-6.4 或非词“?”的意义 T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p ? q q p 3-7 对偶与范式 定义3-7.1 设给定的命题公式A仅含联结词 ┐，∧，∨，A*为将A中符号∧，∨，t，f分别改换为∨，∧，f，t后所得的公式，那么称A*为A的对偶式（dual）。 显然， A 也为A*的对偶式。 定理3-7.1 设公式A和A*中仅含命题变元p1,…,pn，及联结词┐，∧，∨；则 ┐A(p1， p2 …, pn) ?A*(┐p1， ┐p2 …, ┐pn) A(┐p1， ┐p2 …, ┐pn)? ┐ A*(p1， p2 …, pn)  证明思路：利用德摩根定律 P∨Q ? ┐（┐P∧┐Q） A ? ┐ A* 推广到p1， p2 …, pn  定理3-7.2 设公式A和B中仅含命题变元p1,…,pn， 如果A?B，则A*?B*。 文字(letters)：指命题常元、变元及它们的否定， 前者又称正文字，后者则称负文字。 析取子句(disjunctive clauses)：指文字或若干文字的析取。 合取子句(conjunctive clauses)：指文字或若干文字的合取。 互补文字对(complemental pairs of letters) ： 指形如L，┐L（L为文字）的一对字符。 定义3-7.2 命题公式A‘称为公式A的合取范式 （conjunctive normal form）如果 （1）A ? A （2）A‘为一析取子句或若干析取子句的合取。 A‘形如：A1∧A2∧…∧An (n?1) 定义3-7.3命题公式A‘称为公式A的析取范式 （disjunctive normal form），如果 （1）A ? A （2）A‘为一合取子句或若干合取子句的析取。 A‘形如：A1∨A2∨…∨An (n?1) 求一个命题公式的合取范式或析取范式的步骤： ?. 将公式中的联结词化归成仅含∨ 、∧、┐； ?. 利用德 . 摩根定律将否定符号┐直接内移到各个命题变元之前； ?. 利用分配律、结合律将公式归约为合取范式或析取范式。 定义3-7.4 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时出现，但两者必须出现且仅出现一次。 一般来说，n个命题变元共有2n个小项。 根据定义可知，没有两个小项是等价的，且每个小项都只对应P和Q的一组真值指派，使得该小项的真值为T。 以上结论可推广到三个以上的变元情况，并且由此可以作出一种编码，使n个变元的小项可以很快地写出来。 小项有如下性质： ?. 每一个