1.3.1 对偶与蕴涵.ppt

对偶 蕴涵其他联结词 授课教师 程文刚wgcheng 复习 等价公式命题定律代入和置换原则 本节内容 对偶定理蕴涵式蕴涵式的证明方法其他联结词联结词功能完全组 对偶 对偶定理 蕴涵式 定义设A和B是两个命题公式 若A B是永真式 则称A蕴涵B 记作A B 称A B为蕴涵式或永真条件式 符号 和 的区别与联系区别 是逻辑联结词 属于对象语言中的符号 是公式中的符号 而 不是联结词 属于元语言中的符号 表示两个公式之间的关系 不是两公式中符号 联系 A B成立 其充要条件A B是永真式 蕴涵式的性质 自反性 即对任意公式A 有A A 传递性 即对任意公式A B和C 若A B B C 则A C 对任意公式A B和C 若A B A C 则A B C 对任意公式A B和C 若A C B C 则A B C 传递性的证明 设A B B C 则A B 1 B C 1 A B C A B C A B C A B C 1 C A 1 1 1 1 因此A C 于是A C A C A C B B 等价式与蕴涵式 蕴含式的判别判定 A B 是否成立的问题可转化为判定A B是否为重言式 有下述判定方法 1 真值表 2 等值演算 3 假定前件A为真 4 假定后件B为假 1 真值表方法 例证明 P Q P R Q R R 证明令公式F P Q P R Q R R 其真值表如下 公式F对任意的一组真值指派取值均为1 故F是重言式 2 等值演算方法 证明P P Q Q P P Q QE11 P P Q QE10 P Q P Q E2 1代入规则 E5因此P P Q Q 3 假定前件A真 假定前件A为真 检查在此情况下 其后件B是否也为真 4 假定后件B假 假定后件B为假 检查在此情况下 其前件A是否也为假 例证明 联结词的扩充与功能完全组 联结词的扩充定义设P和Q是任两个原子命题 由合取非联结词 和P Q连接成P Q 称它为P和Q的合取非式复合命题 读作 P合取非Q P Q的真值由命题P和Q的真值确定 当且仅当P和Q均为 时 P Q为 否则P Q为 合取非 又常称为 与非 由析取非联结词 和P Q连接成P Q 称它为P和Q的析取非式复合命题 读作 P析取非Q P Q的真值由P和Q的真值确定 当且仅当P和Q均为 时 P Q为 否则P Q为 析取非 又常称为 或非 由条件非联结词 和P Q连接成P Q 称它为P和Q的条件非式复合命题 读作 P条件非Q P Q的真值由P和Q的真值确定 当且仅当P为 而Q为 时 P Q为 否则P Q为 由双条件非联结词 把P Q连接成P Q 称它为P和Q的双条件非式复合命题 读作 P双条件非Q P Q的真值由P和Q的真值确定 当且仅当P和Q的真值不同时 P Q为 否则P Q为 双条件非 又常称为 异或 也常用符号 表示之 上面4个联结词构成的复合命题 其真值表如下 由表可知 P Q P Q P Q P Q P Q P Q P Q P Q 与非 或非和异或的性质令P Q和R是原子命题变元 与非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 或非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q从上述的性质可知 联结词 和 可分别用联结词 或者 取代 和 都不满足结合律 异或的性质 a P Q Q P b P Q R P Q R c P Q R P Q P R d P P F F P P T P P e 若P Q R 则Q R P P P Q 且P Q R F 两上命题变元P和Q 与9个联结词一共可构成类命题公式 如下表所示 l l l l 从列表可知 除命题常元F T及命题变元本身外 命题联结词一共有9个就够了 为了方便 可规定其优先级 由高到低次序为 等 联结词功能完全组 已知有9个联结词就够用了 能不能少呢 若能少 表明有些联结词的逻辑功能可由其他联结词替代 事实上 也确实如此 因为有下列等价式 P Q P Q P Q P Q P Q P Q P Q P Q 可见 扩充的4个联结词 和 能由原有5个联结词分别替代之 又由命题定律 P Q P Q Q P P Q P QP Q P Q P Q P Q 可知 原有5个联结词 和 又能由联结词组 或 取代 那么 究竟最少用几个联结词 就是说 用最少的几个联结词就能等价表示所有的命题公式 或者说 用最少的几个联结词就能替代所有联结词的功能 这便是所要定义的联结词功能完全组 定义称G为联结词功能完全组 如果G满足下列两条件 由G中联结词构成的公式能等价表示任意命题公式 G中的任一联结词不能用其余的联结词等价表示 可以证明 都是联结词功能完全组 而 都不是联结词功能完全组 但为了表示方便 仍经常使用联结词组 练习题 凭栏人 寄征衣 元 姚燧欲寄君衣君不还 不寄君衣君又寒 寄与不寄间 妾身千万难 赏析 这两句曲词写一个征人的妻子在给丈夫寄衣时的复杂心情 她担心丈夫在边疆上冻坏身子 想给他把寒衣寄去 可又怕他有了寒衣就