交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt
《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt》由会员分享,可在线阅读,更多相关《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt(13页珍藏版)》请在装配图网上搜索。
第5章谓词逻辑的等值和推理演算 5 1否定型等值式5 2量词分配等值式5 3范式5 4基本的推理公式5 5推理演算5 6谓词逻辑的归结推理法 5 1否定型等值式 等值设P Q是任意两个谓词公式 若P Q为普遍有效式 则称P与Q是等值的 记作P Q 或P Q 由命题公式移植来的等值式若将命题公式的等值式 直接以谓词公式代入命题变项便可得谓词等值式如由 P Q P Q 得 x F x y G y x F x y G y 如由 P Q P Q x F x y G y x F x y G y 5 1 2否定型等值式 设P x 是含自由变项x的任意谓词公式 则 x P x x P x x P x x P x 从语义上说明 x P x 并非所有的x都具有性质P 相当于至少存在一个x不具有性质P 即 x P x 所以 x P x x P x x P x 并不存在一个x具有性质P相当于没有x具有性质P 即 x P x 所以 x P x x P x 设个体域为实数RP x x是有理数 设个体域为自然数NP x x是奇数和偶数 否定型等值式的分析 设P x 是含自由变项x的任意谓词公式 则 x P x x P x x P x x P x 在 1 2 域上分析 x P x P 1 P 2 P 1 P 2 x P x 可见 否定词越过量词的内移规律 就是摩根律的推广 x P x P 1 P 2 P 1 P 2 x P x 否定型等值式的证明 设P x 是含自由变项x的任意谓词公式 则 x P x x P x x P x x P x 在语义上证明A真 B真设任一解释I下有 x P x T则 x P x F即存在一个x0 使P x0 F于是 P x0 T 在解释I下 x P x T B真 A真设任一解释I下有 x P x T即存在一个x0 使 P x0 T于是 P x0 F则 x P x F即 x P x T 依据 若存在一个解释I 使A真B就真 B真A就真 则A B 否定型等值式举例 天下乌鸦一般黑 的表示设F x x是乌鸦 G x y x与y是一般黑 原句可表示成 若x是任一乌鸦 y是任一乌鸦 则x和y是一样黑的 x y F x F y G x y x y F x F y G x y x y F x F y G x y x y F x F y G x y x y F x F y G x y 不存在乌鸦x和乌鸦y 它们是不一样黑的 5 2量词分配等值式 量词对 的分配律 x P x q x P x q x P x q x P x q x P x q x P x q x P x q x P x q设 P x 是含自由变元x的任意谓词公式 q是不含变元x的谓词公式 量词分配等值式的证明 x P x q x P x q 依据 若存在一个解释I 使A真B就真 B真A就真 则A B B真 A真设任一解释I下有 x P x q T 设q T 则 x P x q T 若q F 必有 x P x T从而对任一个x 有P x T于是 对任一x有P x q T x P x q T A真 B真设在一解释I下 有 x P x q T从而对任一个x 使P x q T又 设q T 有 x P x q T 若q F 从而对任一x 有P x T即 x P x T x P x q T 量词分配等值式 量词对 的分配律 x P x q x P x q x P x q x P x q x q P x q x P x x q P x q x P x 设 P x 是含自由变元x的任意谓词公式 q是不含变元x的谓词公式 x P x q x P x q x P x q x P x q x P x q x P x q x P x q 量词分配等值式 量词 对 的分配律 x P x Q x x P x x Q x 注意 对 无分配律从 1 2 域上分析 x P x x Q x P 1 P 2 Q 1 Q 2 x P x Q x P 1 Q 1 P 2 Q 2 P 1 P 2 P 1 Q 2 Q 1 P 2 Q 1 Q 2 x P x x Q x P 1 Q 2 Q 1 P 2 x P x x Q x x P x Q x 量词分配等值式 量词 对 的分配律 x P x Q x x P x x Q x 注意 对 无分配律由前面证明代换得 x P x x Q x x P x Q x 而 x P x x Q x x P x x Q x x P x x Q x x P x Q x x P x Q x x P x Q x x P x x Q x x P x Q x x P x x Q x x P x Q x 例将下面命题用两种形式符号化 1 没有不犯错误的人解 设F x x是人 G x x犯错误 x F x G x x F x G x x F x G x x F x G x 2 不是所有的人都爱看电影解 令F x x是人 G x 爱看电影 x F x G x x F x G x x F x G x x F x G x x P x x P x x P x x P x 只要的人 他就会犯错误 有的人不爱看电影 作业6 P68 7 7 8 2 10 1 P84 1 1 7 2 1 2 3 1- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 交大 数理逻辑 课件 谓词 逻辑 等值 推理 演算
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文