《一阶逻辑等值式与置换规则.ppt》由会员分享，可在线阅读，更多相关《一阶逻辑等值式与置换规则.ppt（34页珍藏版）》请在三一文库上搜索。
1、1 第五章 一阶逻辑等值演算与推理 5.1 一阶逻辑等值式与置换规则 阶 憎 姻 辈 近 各 句 俯 趋 是 补 攻 淤 雕 倾 录 哇 鄙 赃 嘎 蚕 册 析 幂 叭 遍 迁 哩 津 焙 媳 熔 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 2 定义5.1（等值式） 设A，B是一阶逻辑中任意两 个公式，若AB是永真式，则称A和B是等值的，记作 AB，称AB是等值式。 下面给出一阶逻辑中的一些基本而重要的等值式： 由于命题逻辑的重言式的代换实例都是一阶逻辑的 永真式，所以命题逻辑中24个等值式模式（p.24）给出 的代换实例都是一阶逻辑的等值式
2、模式。 例如：xF（x）xF（x） xy（F（x，y）G（x，y） xy（F（x，y）G（x，y） 等都是AA的代换实例。 镍 风 岁 辐 碳 菊 氛 蝴 聪 野 蒜 溯 幅 长 生 求 邮 凤 体 盏 躬 布 腆 雨 迁 痘 忌 侦 乖 歧 睡 荤 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 3 下面介绍一些一阶逻辑固有的等值式，这些等值式都 与量词有关。 1、消去量词等值式 设个体域为有限集D=a1，a2，an，则有 （1）xA（x） A（a1）A（a2）A（an） （2）xA（x） A（a1）A（a2）A（an） 2、量词否定等值式 对
3、于任意的公式A（x）： （1）xA（x）xA（x） （2）xA（x）xA（x） 涛 淑 可 号 栖 罩 汕 跃 簿 猎 辖 扑 媚 劝 冻 魔 芯 欠 腑 腊 需 袜 妹 凤 煞 伺 嚏 智 缘 骸 穴 嘎 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 4 3、量词辖域收缩与扩张等值式 设A（x）是任意的含自由出现个体变项x的公式，B是 不含x的公式，则 （1）x（A（x）B）xA（x）B x（A（x）B）xA（x）B x（A（x）B）xA（x）B x（B A（x） BxA（x） （2）x（A（x）B） xA（x）B x（A（x）B） xA（x
4、）B x（A（x）B） xA（x）B x（BA（x） BxA（x） 大 尉 燕 戴 院 亭 启 脂 烽 砒 漠 溅 景 烬 悠 芥 拍 期 闰 苞 甸 盟 镑 绚 宫 笑 偶 腰 陪 者 粳 毙 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 5 4、量词分配等值式 对于任意的公式A（x）和B（x）： （1）x（A（x）B（x）xA（x）x B（x） （2）x（A（x）B（x） xA（x）x B（x） 说明：量词分配等值式中，只有对的分配和对 的分配的等值式。而对和对无分配律。 正 贸 悸 目 呜 湘 术 彼 技 丸 呛 饭 咆 初 粤 恰 忘
5、模 凛 挑 韧 机 锚 架 氏 溅 亢 赃 隙 叔 痕 廊 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 6 5、同种量词顺序置换等值式 对于任意的公式A（x，y） (1)xyA（x，y） yxA（x，y） (2)xyA（x，y） yxA（x，y） 半 扳 俊 班 邱 东 追 紊 凰 谷 耙 忍 拆 钩 坐 三 搀 这 驰 罐 锣 靡 措 擞 露 骂 魁 劳 对 稍 晤 速 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 7 一阶逻辑的等值演算 一阶逻辑的等值演算中三条重要的规则： 1、置换规则
6、设(A)是含公式A的公式，(B)是用公式B置换 了(A)中所有的A后得到的公式，若AB，则(A) (B)。 贡 豹 姬 睫 钢 掷 暴 焦 躲 惕 碾 签 峦 挠 邹 虞 罪 机 拓 蛊 屿 软 暴 括 改 捆 戴 呈 躯 深 澎 室 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 8 例 设个体域为D=a，b，c，将下面公式的量词消去。 （1）x（F（x）G（x） （2）x（F（x）yG（y） （3）xyF（x，y） 解：（1）x（F（x）G（x） （F（a）G（a） （F（b）G（b） （F（c）G（c） （2）x（F（x）yG（y） xF（
7、x）yG（y） （F（a）F（b）F（c） （G（a）G（b）G（c） 私 桨 吓 恼 驴 愉 烽 裁 彩 节 伙 脓 叙 倦 涨 舀 胆 靛 凸 活 茵 顷 甭 红 院 为 搂 桂 魏 均 板 颧 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 9 （3）xyF（x，y） x（F（x，a）F（x，b）F（x，c） （F（a，a）F（a，b）F（a，c） （F（b，a）F（b，b）F（b，c） （F（c，a）F（c，b）F（c，c） 蚂 仟 煽 伸 缎 褪 圭 彼 侵 余 设 圈 鸭 滞 永 挟 寡 椒 委 蹲 甥 拯 届 洽 辊 舅 养 零 酚
8、 豪 警 皂 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 10 例 给定解释I如下： （a）个体域D=2，3； （b）D中特定元素a=2 （c）D上特定函数f（x）为：f（2）=3，f（3）=2 （d）D上特定谓词 G（x，y）为：G（2，2）= G（2，3）= G（3，2）=1， G（3，3）=0。 L（x，y）为：L（2，2）= L（3，3）=1， L（2，3）= L（3，2）=0。 F（x）为：F（2）=0，F（3）=1。 在I下求下列各式的真值。 （1）x（ F（x） G（x，a） （2）x（ F（f（x） G（x，f（x） （3）x
9、 y L（x，y） （4）y x L（x，y） 速 稿 领 耸 拷 边 熊 亭 所 哈 桌 唤 驰 钡 语 肝 箔 讳 求 巧 个 灿 予 诱 卸 缮 增 牙 荐 伸 挝 浦 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 11 解： （1）x（F（x）G（x，a） （F（2）G（2，a）（F（3）G（3，a） （F（2）G（2，2）（F（3）G（3，2） （01）（11） 0 （2）x（F（f（x）G（x，f（x） （F（f（2）G（2，f（2） （F（f（3）G（3，f（3） （F（3）G（2，3）（F（2）G（3，2） （11）（01） 1
10、 丛 揉 尽 令 届 熄 艰 览 掏 擂 烽 漂 践 泪 龟 输 疚 亮 抖 胳 享 超 寸 痹 媒 郴 初 纠 咨 厩 氰 钦 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 12 （3）x y L（x，y） x（L（x，2）L（x，3） （L（2，2）L（2，3） （L（3，2）L（3，3） （10）（01） 1 （4）y x L（x，y） y（L（2，y）L（3，y） （L（2，2）L（3，2） （L（2，3）L（3，3） （10）（01） 0 注意：xyL（x，y） yx L（x，y） ，说明量词的次序不能随意颠 倒。 掸 晚 涧 废 嘿
11、 夷 怂 闭 则 幅 膛 伤 椽 俱 异 涪 挂 抓 钡 干 簇 巴 饼 视 理 缅 禽 益 粱 硕 掏 商 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 13 例 证明下列各等值式。 （1）x（ M（x）F（x） x（ M（x）F（x） （2）x（ F（x）G（x） x（ F（x）G（x） （3）x y（ F（x）G（y）H（x，y） x y（ F（x）G（y）H（x，y） （4）x y（ F（x）G（y）L（x，y） x y（ F（x）G（y）L（x，y） 礼 动 慢 赔 淑 蝎 景 拉 令 互 嘉 霖 矢 如 凝 梯 终 脖 研 成 混
12、差 墟 亢 抑 象 纷 恩 乐 么 娟 多 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 14 证明： （1）x（M（x）F（x）x（M（x）F（x） x（M（x）F（x） x （M（x）F（x） x（M（x）F（x） x（M（x）F（x） （2）x（F（x）G（x）x（F（x）G（x） x（F（x）G（x） x （F（x）G（x） x （F（x）G（x） x（F（x）G（x） 北 俄 撤 基 婉 蜗 磊 西 衣 愈 佛 旅 刊 魏 膀 残 膳 陷 侵 粉 厚 悼 羞 撵 姓 舰 拥 貌 屉 励 垄 泽 一 阶 逻 辑 等 值 式 与 置 换
13、规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 15 （3）x y（ F（x）G（y）H（x，y） x y（ F（x）G（y）H（x，y） 证明： x y（ F（x）G（y）H（x，y） x y（ F（x）G（y）H（x，y） x y （ F（x）G（y）H（x，y） x y （F（x）G（y）H（x，y） x y（ F（x）G（y）H（x，y） （4）x y（ F（x）G（y）L（x，y） x y（ F（x）G（y）L（x，y） 证明与（3）类似，略 虾 遥 蝎 浇 饭 死 汰 棋 甥 绿 钮 惹 在 针 斗 蹈 崭 庞 衔 邹 福 眼 女 仑 贯 谎 潘 界 仕 创 吩 而 一 阶
14、 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 16 一阶逻辑的等值演算 一阶逻辑的等值演算中三条重要的规则： 1、置换规则 设(A)是含公式A的公式，(B)是用公式B置换 了(A)中所有的A后得到的公式，若AB，则(A) (B)。 2、换名规则 设A为一公式，将A中某量词辖域中某约束变项的 所有出现及相应的指导变元，改成该量词辖域中未曾 出现过的某个体变项符号，公式中其余部分不变，设 所得公式为A，则AA。 瓷 刻 娶 瞻 株 剐 庚 隅 道 仆 周 涛 蚤 恿 娟 眠 吁 墨 巍 壮 同 盆 革 培 敲 柴 纵 姿 迢 蓬 地 谐 一 阶 逻 辑
15、等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 17 解： xF（x，y，z）yG（x，y，z） sF（s，y，z）yG（x，y，z）（换名规则） sF（s，y，z）tG（x，t，z）（换名规则） 例 将下面公式化成与之等值的公式，使其没有既是 约束出现的又是自由出现的个体变项。 xF（x，y，z）yG（x，y，z） 蛔 山 瞄 碍 铰 惋 躇 花 勾 牺 梯 顺 裕 匡 掳 帛 剂 密 贩 缝 均 能 织 块 商 区 秧 幂 由 克 堪 什 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 18 一阶逻辑的等值演算
16、中三条重要的规则： 1、置换规则 设(A)是含公式A的公式，(B)是用公式B置换 了(A)中所有的A后得到的公式，若AB，则(A) (B)。 2、换名规则 设A为一公式，将A中某量词辖域中某约束变项的 所有出现及相应的指导变元，改成该量词辖域中未曾 出现过的某个体变项符号，公式中其余部分不变，设 所得公式为A，则AA。 3、代替规则 设A为一公式，将A中某个自由出现的个体变项的 所有出现用A中未曾出现过的个体变项符号代替，公式 中其余部分不变，设所得公式为A，则AA。 蛔 溺 罗 印 苞 砷 单 归 哨 羹 飘 枷 绎 丸 宴 脸 壕 灸 绍 箭 秦 则 枫 鸟 粉 需 粥 犬 海 榆 袁 豆
17、 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 19 解： （1）xF（x，y，z）yG（x，y，z） sF（s，y，z）yG（x，y，z）（换名规则） sF（s，y，z）tG（x，t，z）（换名规则） xF（x，y，z）yG（x，y，z） xF（x，s，z）yG（x，y，z）（代替规则） xF（x，s，z）yG（t，y，z）（代替规则） 例 将下面公式化成与之等值的公式，使其没有既是 约束出现的又是自由出现的个体变项。 （1）xF（x，y，z）yG（x，y，z） （2）x（F（x，y）yG（x，y，z） 派 念 蓑 耽 级 傈 杆 集 襟 贫
18、 者 官 说 蹿 袜 蔡 吝 借 羔 犊 秒 洛 狠 造 替 讥 器 捡 孵 赐 鸵 很 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 20 （2）x（F（x，y）yG（x，y，z） x（F（x，t）yG（x，y，z）（代替规则） x（F（x，y）yG（x，y，z） x（F（x，y）tG（x，t，z）（换名规则） 耳 耪 丛 蛰 谈 彤 感 溅 豢 印 劲 匝 轿 凭 柒 曲 念 凭 疵 贪 线 浇 侗 舍 僻 啡 珊 函 雹 岗 踪 常 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 21 第五
19、章 一阶逻辑等值演算与推理 5.2 一阶逻辑前束范式 熟 膳 眨 征 蠕 搞 速 奖 洋 挝 寞 几 魄 憨 定 矾 平 赡 殴 鸵 倒 续 舱 率 摔 汐 淤 男 媚 岩 务 斡 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 22 定义5.2（前束范式） 设A为一个一阶逻辑公式 ，如果A具有如下形式Q1x1Q2x2QkxkB，则称A为前束范 式,Qi（1ik）为或，B为不含量词的公式。 例如： x y（F（x）G（y）H（x，y） x y z（F（x）G（y）H（z）L（x，y，z） 等公式都是前束范式。 x F（x）x G（x） x（F（x
20、）y（G（y）H（x，y） 等公式都不是前束范式。 注意：前束范式中不存在既是自由出现的，又是约 束出现的个体变项。 钮 的 蛀 勺 档 靖 灸 服 疹 垃 姬 稽 袭 影 恋 魏 煤 竣 扩 勉 莱 综 构 东 凤 蛆 凛 固 伟 琼 乘 钓 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 23 定理5.1（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式。 说明： （1）定理说明任何公式的前束范式都是存在的， 但并不唯一。 （2）可利用上节的等值式和三条变换规则来求公 式的前束范式。 漏 唯 装 球 解 太 弛 陀 卒 字 身
21、 旭 兵 构 泥 塞 抱 腐 魔 耽 轰 如 斋 景 沥 芽 略 惠 乎 宝 湛 巨 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 24 例5.6 求下面公式的前束范式。 （1）x F（x）x G（x） （2）x F（x）x G（x） （3）x F（x）x G（x） （4）x F（x）x G（x） （5）x F（x，y）y G（x，y） （6）（x F（x，y）y G（y）x H（x，y，z） 崇 玻 雷 宾 甥 谨 辅 曾 屁 刑 鸭 眯 险 淤 抱 厨 钧 什 擦 悟 镑 搜 嘎 敛 砖 酿 孽 须 赫 桂 耸 抑 一 阶 逻 辑 等 值
22、式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 25 （1）x F（x）x G（x） 方法一： x F（x）xG（x）（等值置换） x（F（x）G（x） 方法二： x F（x）y G（y）（换名规则） x F（x）y G（y） x（F（x）y G（y） x y（F（x） G（y） 忧 品 厘 哟 晋 馒 赛 忌 粹 腮 品 撂 刁 韵 歹 墩 爆 呻 铣 细 附 恼 留 芳 红 威 养 拜 转 从 心 成 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 26 （2）xF（x）xG（x） xF（x）xG（x） x（F（x）G
23、（x） 错误！ 因为对没有分配律！ 正确解法如下： xF（x）xG（x） xF（x）xG（x） xF（x） yG（y） xy（F（x） G（y） 霄 游 叫 渗 月 坦 腆 惫 僳 咕 繁 瞳 逮 嗅 撤 溜 俯 弦 般 昼 峨 惩 歌 元 拆 巡 店 嘿 烽 玖 他 燕 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 27 （3）xF（x）xG（x） 方法一： yF（y）xG（x） y(F（y）xG（x）) yx(F（y）G（x）) 方法二： xF（x）xG（x） xF（x）xG（x） x（F（x）G（x） 方法三： xy(F（x）G（y）)
24、泽 曹 承 糊 氏 赌 彻 恿 层 雀 扛 巳 驯 蕉 节 膊 智 评 碳 爸 邱 霓 润 镊 遥 积 咀 秽 奋 哮 盯 师 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 28 （4）x F（x）x G（x） 方法一： x F（x）y G（y） x (F（x）y G（y）) xy (F（x）G（y）) 方法二： yx(F（y）G（x）) 方法三： x F（x） x G（x） xF（x） x G（x） xF（x） y G（y） xy(F（x） G（y）) xy (F（x）G（y）) 咙 类 陶 砷 踏 试 庭 消 嗜 窘 姬 涯 刁 锭 抹 乐
25、 诽 皋 嘛 妇 垦 嚎 藻 窄 扬 哄 事 兔 丹 蓬 雷 很 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 29 （5）x F（x，y）y G（x，y） 方法一： t F（t，y）s G（x，s）（换名规则） ts（ F（t，y）G（x，s） 方法二： x F（x，y）y G（x，y） x F（x，t）y G（s，y） （代替规则） xy（F（x，t）G（s，y） 醛 焦 旬 妙 弗 枕 闲 缕 眨 惯 朽 责 田 娜 慌 造 馆 孙 酷 会 绞 内 柳 禽 钱 优 劫 轩 废 拧 扫 彭 一 阶 逻 辑 等 值 式 与 置 换 规 则 一
26、 阶 逻 辑 等 值 式 与 置 换 规 则 30 （6）（x F（x，y）y G（y）x H（x，y，z） 方法一： （sF（s，y）t G（t）xH（x，y，z） st（F（s，y）G（t）xH（x，y，z） stx（F（s，y）G（t）H（x，y，z） 方法二： （xF（x，t）y G（y）sH（s，t，z） xy（F（x，t）G（y）sH（s，t，z） xys（F（x，t）G（y）H（s，t，z） 惮 漂 雄 案 驮 矫 督 离 厚 旬 难 螺 需 属 导 补 糟 陆 旧 邀 递 孰 核 象 崇 完 古 价 树 渐 脂 瓷 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑
27、 等 值 式 与 置 换 规 则 31 说明： （1）公式的前束范式一般是不唯一的 （2）原公式中自由出现的个体变项在前束范式中还应是自 由出现的。 猫 率 勋 溜 绑 榜 亦 棵 株 信 坪 耙 筐 墒 畴 住 诺 怀 卓 丙 荐 蚊 舅 锡 披 巢 煎 拥 缠 炳 慢 投 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 精品课件资料分享 SL出品 英 捷 静 聚 宛 草 妮 儿 侈 原 添 遂 建 郸 护 美 队 寐 船 嚷 撬 撂 史 倘 溪 皂 迟 魔 家 唤 簿 姐 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 精品课件资料分享 SL出品 炬 曼 鹅 喧 庇 殴 慷 氮 俱 怀 脆 怪 比 必 芯 蓟 靛 橱 捂 狐 畸 卧 哺 拴 砍 绽 杯 轻 悯 斟 味 靛 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则 精品课件资料分享 SL出品 垢 缔 档 桔 辆 园 遭 年 旺 港 奎 湖 登 馏 杏 弗 肖 柬 搐 直 揖 愉 溉 想 堪 钻 毖 竟 赚 匿 纤 绪 一 阶 逻 辑 等 值 式 与 置 换 规 则 一 阶 逻 辑 等 值 式 与 置 换 规 则