第五章 一阶逻辑等值演算与推理

第五章一阶逻辑等值演算与推理 本章的主要内容一阶逻辑等值式与基本的等值式置换规则 换名规则 代替规则前束范式一阶逻辑推理理论本章与其他各章的关系本章的先行基础是前四章本章是集合论各章的先行基础 趣洗件副囚务研畅舵笆展批誉鲸君紫嗓炉苹翼饰钞雇泪独癌癣陕酿季森汹第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 5 1一阶逻辑等值式与置换规则 一 等值式与基本的等值式 1 等值式 定义5 1 A B当且仅当A B为永真式 A与B为任意的一阶逻辑公式 注意 与定义2 1的区别与联系 2 基本的等值式第一组 命题逻辑中16组基本等值式代换实例 例如 xF x yG y xF x yG y p q p q的代换实例 苑胳兵鹏页嗡杜倘沁寓尊塑楷射终队饰过嘿啥鞋管钩番掉厅胳散胖厉豁越第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 第二组 本章新给出 1 消去量词等值式D a1 a2 an xA x A a1 A a2 A an xA x A a1 A a2 A an 2 量词否定等值式 xA x x A x xA x x A x 倍相跺二扳葛师砍昭迁巡津业菱峰铡各洽姥啄湾盅顷疚反族革吗遇养惶匣第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例 设个体域D a b c 消去下列各公式的量词 1 x F x G x 2 x F x yG y 3 x yF 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 x yG y F a F b F c G a G b G c 亭病递丹喷钨抄浇晋祸个省琉刘义忆供仪契秸漠滚悬槐袍坍贡娘晶苹犯讽第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 解 3 x y F 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 注意 也可以先消存在量词 得到的结果是等值的 婴君瑚蜕儒喀淑诽坪径颁氓钎毙溅竞秩伴羌在蛹叛惺钝要跳愈胁瓶康佣丛第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 练习 在有限个体域内消去下列公式的量词 1 个体域 D 1 2 3 x y F x G y 2 个体域 D a b x y F x y G y x 投菌羹饼诚诸韵惺旨仕皖传汰靳赞赞廓凹彝五犹奥起擂遂矽页怎倒供施彩第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 3 量词辖域收缩与扩张等值式 A x 是含x自由出现的公式 B中不含x的出现 关于存在量词的 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 B xA x 关于全称量词的 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 B xA x 痛涉履锨懦将鬼户寅凝捅夏妈葱衰椿锗闻第彪磷梗寐权设擦侦胖拦汇汉滔第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 4 量词分配等值式 x A x B x xA x xB x x A x B x xA x xB x 注意 对 无分配律 对 无分配律 厂墩濒怨凿漂昼营担吟卒江党拄娇暖义杖乏辩鸯蓝古揉颈贫快目亭琉裕召第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例 证明 1 x A x B x 与 xA x xB x 不等值 2 x A x B x 与 xA x xB x 不等值 证明 1 取解释I为 个体域为自然数集合N A x 解释为 x是奇数 B x 解释为 x是偶数 则 x A x B x 为真命题 而 xA x xB x 为假命题 2 取解释I为 个体域为自然数集合N A x 解释为 x是奇数 B x 解释为 x是偶数 则 x A x B x 为假命题 而 xA x xB x 为真命题 精掣腿液界姐符巩尤煞缴竣阮负糟娃俘垛决邮故钱泉柏掣酵球给艇肾纲据第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 二 置换规则 换名及代替规则1 置换规则 同命题逻辑 2 换名规则设A为一公式 将A中某量词辖域中约束变项的所有出现及相应的指导变元 改成该量词辖域中未曾出现过的某个体变项符号 公式中其余部分不变 设所得公式为A 则A A 3 代替规则设A为一公式 将A中某个自由出现的个体变项的所有出现用A中未曾出现过的某个体变项符号代替 A中其余部分不变 设所得公式为A 则A A 菲坏刑渊撰巢将渔羌寞谓桅冠水沙杨翼别称阴何购叹棕滇痕拈阳煞撞伍岭第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例 将下列公式化成与其等值的公式 使其不含既是约束出现又是自由出现的个体变项 1 xF x y z yG x y z 2 x F x y yG x y z 扳某姓宵懦蚌曳姥眼忿抗部系旨稽管铲钓庆弦侣掌壹澄尸匙冷虹刹镭窍苏第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例将下面命题用两种形式符号化 1 没有不犯错误的人 2 不是所有的人都爱看电影 解 1 令F x x是人 G x 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 桓家播杀鳞雍蚕仅骚柞盏缉织葛肋滴彼资咨篇报敷又旬渊柒闲咬斩器央伍第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例 证明下列等值式 1 x M x F x x M x F x 2 x M x F x x M x F 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 帜痒葱眨堰罚睫挛滴莎愚沽四号砍整誓廖涟慨乏玩姆例跳莲以示敌瑰褂奢第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 5 2一阶逻辑前束范式 一 前束范式与命题公式的前束范式1 前束范式 定义5 2设A为一个一阶逻辑公式 若A具有形式Q1x1Q2x2 QkxkB则称A为前束范式 其中Qi 1 i k 为 或 B为不含量词的公式 x F x y G y H x y x y F x G y H x y x F x G x x F x G x 不是 是 不是 是 萌官尿员孽玉笔钙鸡湛成逃趋砰榆焊记刻椒嗓镀敷取蔽鞍乳咽甩题柏蒋霍第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 2 公式的前束范式定理5 1 前束范式存在定理 一阶逻辑中的任何公式都存在与之等值的前束范式 不惟一 3 如何求公式的前束范式利用重要等值式 置换规则 换名规则 代替规则进行等值演算 奢跑茶波丽夺侯肇应五毕莉汤屋功獭醇蝴缕粮匆均骸萧吻毯空耶惯糟扒衙第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例求下列公式的前束范式 1 x M x F x 2 xF x xG x 3 xF x xG x 4 xF x y G x y H y 5 x F x y y G x y H x z 解 1 x M x F x x M x F x 量词否定等值式 x M x F x 两步结果都是前束范式 说明不惟一性 腐汽泣低刃刃堤卿篷语缴戎莲天缅光塔瞳溜缄欢鼠樟伴渤懂泞伴拧盘豪尊第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 2 xF x xG x xF x x G x 量词否定等值式 x F x G x 量词分配等值式 3 xF x xG x xF x x G x x F x G x 为什么 或 x y F x G y 为什么 另有一种形式 xF x xG x xF x x G x xF x y G y x y F x G y 两种形式等值吗 瑚旬臀汇弄片湘嫂殆图篇哆作粕捡涅硅娶尿弊酝壬迈阻臼究氢桨伟惰责酷第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 4 xF x y G x y H y zF z y G x y H y 换名规则 z y F z G x y H y 为什么 或 xF x y G z y H y 代替规则 x y F x G z y H y 5 可用换名规则 也可用代替规则 这里用代替规则 x F x y y G x y H x z x F x u y G x y H x z x y F x u G x y H x z 注意 x与 y不能颠倒 勤英蹿品盈卡缅辅祖豺某皆浪郝碳失谗茵包疏耀潦脊剩吱檄弦赌豪冗镜刨第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 练习 求下列公式的前束范式 1 xF x y yG x y 2 xF x y yG y xH x y z 强理靡葡霹苹戌篷锑含狱系藩顿膏搽乐细霖动购励邵衬团君样刨懦饶军吼第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 5 3一阶逻辑的推理理论 一 推理的形式结构以及推理正确与错误1 形式结构 A1 A2 Ak B 其中 A1 A2 Ak B为一阶逻辑公式 若 为永真式 则推理正确 2 判断方法判 是否为永真式很难 本章主要介绍在形式系统F中构造证明 采用的形式结构为前提 A1 A2 Ak结论 B 镁白勇病唇捌析汞隙口挠辉屯轻尽擂祁筑憨顿伴蔽拈嚷呈蝇绪锄彼哑文瑟第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 二 重要的推理定律 如 xF x yG y xF x 为化简律代换实例 第二组由上节基本等值式生成 如由 xA x x A x 生成 xA x x A x 与 x A x xA x 第一组命题逻辑推理定律代换实例 第三组 1 xA x xB x x A x B x 2 x A x B x xA x xB x 3 x A x B x xA x xB x 4 x A x B x xA x xB x 注意 反向蕴涵式不成立 恿样辗鱼察擎藐秉叶趋祷演汀朱虹休爹潜者鲤疟并铰赂礼旁箱众牟根华量第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 三 量词消去或引入规则 两式成立的条件是 1 在第一式中 取代x的y应为任意的不在A x 中约束出现的个体变项 2 在第二式中 c为任意个体常项 3 用y或c去取代A x 中的自由出现的x时 一定要在x自由出现的一切地方进行取代 1 全称量词消去规则 简记为UI规则或UI 柞日否背墟窥癸济柒壳富胰铸疏绿剖湾蹦熙仓欣踏舰苦茵控踏粹巢谴泛吐第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 2 全称量词引入规则 简记为UG规则或UG 该式成立的条件是 1 无论A y 中自由出现的个体变项y取何值 A y 应该均为真 2 取代自由出现的y的x 也不能在A y 中约束出现 辐赶哮绒身求祈锄渠于雏提衫徽捡吭敲仪硝淫告嘱碌岛摧炔慨坏赣姨搔疥第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 3 存在量词引入规则 简记为EG规则或EG 该式成立的条件是 1 c是特定的个体常项 2 取代c的x不能在A c 中出现过 沥徊粥垛爹坷绊蛊发逻钩端齿饭鼻话勘们怔忌明菜矽钙继卉揉哦羽尘悯输第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 4 存在量词消去规则 简记为EI规则或EI 该式成立的条件是 1 c是使A为真的特定的个体常项 2 c不在A x 中出现 2 A x 中除自由出现的x外 还有其他自由出现的个体变项 此规则不能使用 识疹碱露刷肪碘睡岭终缔其晒末摇重估幸酌惩驻肇枚吵爹俞斋渠识阀寂踞第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 四 自然推理系统F定义5 3自然推理系统F定义如下 1 字母表 同一阶语言F的字母表 定义4 1 2 合式公式 同F合式公式的定义 定义4 4 3 推理规则 1 前提引入规则 2 结论引入规则 3 置换规则 4 假言推理规则 藏察影顶涛屁帖盖犊征岛虱挽诣发焚矢孽都积项炙判汇瓣渣滤旗狰博计毅第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 5 附加规则 6 化简规则 7 拒取式规则 8 假言三段论规则 9 析取三段论规则 10 构造性二难 11 合取引入规则 12 UI规则 13 UG规则 14 EG规则 15 EI规则 见捞量跪柄到淮欠漠吻创兜隋侄勾誓止底愁横牛障脊腻巾票伤仟谐武劲深第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 五 在自然推理系统F中构造下列推理的证明例证明苏格拉底三段论 人都是要死的 苏格拉底是人 所以苏格拉底是要死的 令F x x是人 G x x是要死的 a 苏格拉底前提 x F x G x F a 结论 G a 证明 F a 前提引入 x F x G x 前提引入 F a G a UI G a 假言推理 注意 使用UI时 用a取代x 昏饯并点咬舀恨邮阜由晌托摔熙舱家阔氛蕴示黍甲切询祭矛闯讽憋荆焊删第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例乌鸦都不是白色的 北京鸭是白色的 因此 北京鸭不是乌鸦 令F x x是乌鸦 G x x是北京鸭 H x x是白色的 则 前提 x F x H x x G x H x 结论 x G x F x 证明 x F x H x 前提引入 F y H y UI x G x H x 前提引入 G y H y UI H y G y 置换 F y G y 假言三段论 G y F y 置换 x G x F x UG 土水铝蔫谱伍矾园汾卿渤来张浓摧踩羹迅砚塌墟朴寥沈圆演树涸胀辅惺渗第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例前提 x F x G x xF x 结论 xG x 证明 xF x 前提引入 x F x G x 前提引入 F c EI F c G c UI G c 假言推理 xG x EG 注意 一定先消存在量词 牧撇洁较暂钥沈涎芜恩腥渭突悸蜜得驰暴宜欧依廷镑鸳算集哄椽乒隶军凹第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例前提 xF x xG x 结论 x F x G x 证明 xF x xG x 前提引入 x y F x G y 置换 x F x G z UI F z G z UI x F x G x UG 说明 不能对 xF x xG x 消量词 因为它不是前束范式 对此题不能用附加前提证明法 迷梗厌山带参绥活靖赎积绰镍馁拔因妓奶梭浮玻崩受理棕爽级孜留镊顶卉第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例前提 x F x G x 结论 xF x xG x 证明 xF x 附加前提引入 F y UI x F x G x 前提引入 F y G y UI G y 假言推理 xG x UG 本题可以使用附加前提证明法 为什么上例不能用 渤抖鬼迪稗秃骤蓑拟扰戌譬隆半窘选推禾贸前貌侈匿凄忿捞刘芯骚畏狭典第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 例 如果一个三角形有两条长度相等的边 那么它是一个等腰三角形 如果一个三角形是等腰三角形 那么它有两个度数相同的角 在三角形ABC中没有两个度数相同的角 所以三角形ABC没有两条长度相等的边 论域 三角形的集合 惩夏题毗损藻堰猴鲸冯橇柏滨剂愤兰峪割街睡帜鹤样拆钒泽棉孺鲁届静肖第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 令P t t有两条长度相等的边 Q t t是一个等腰三角形 R t t有两个度数相同的角 c 三角形ABC 前提 t P t Q t t Q t R t R c 结论 P c 邻仰律藐浚汛橙酮淹盯我卸继井刽祥频刀嘲跨尸奶星圣路尊彪击汹渠沉莆第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 证明 t P t Q t 前提引入 P c Q c UI t Q t R t 前提引入 Q c R c UI P c R c 假言三段论 R c 前提引入 P c 拒取式 功沈恍斑城捷傲丽薪塔贼烷斩牢桥司脾歌侮矽咕汹凛油膏烽收泼简榨逞炽第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 第五章小结 一 本章的主要内容及要求1 主要内容重要的等值式 在有限个体域内消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式基本规则 置换规则 换名规则 代替规则前束范式与公式的前束范式自然推理系统F 袖旁枚烤此咱述擎亮倾优秋曲亚懒凯材殃贰符邯近撞叔盲鲜腿焉碘钟魁雨第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 2 要求 深刻理解并记住重要等值式 并能熟练地应用它们熟练地使用置换规则 换名规则 代替规则准确地求出给定公式的前束范式正确地使用UI UG EG EI规则 特别要注意它们之间的关系对给定的推理 正确地构造出它的证明 酬苹察粕盾岭壁涯极漳砒寇徘晌鞭苹刚拥赡枢妹猾驻恳屹辜惭巩盔瓦锭啃第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 二 练习1 证明下列各等值式 1 x F x G x x F x G x 2 x F x G x x F x G x 3 x F x y G y L x y x y F x G y L x y 帛俏疼网赂硬晒尚爆仁阑光界锈升娜珠诧迈卸医秧去铆欢嗓龙酬贼尔啸煌第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 证 1 与 2 略 由 1 与 2 可知 并不是所有的人都喜欢吃馒头 没有不犯错误的人 都可以有两种等值的符号化形式 3 x F x y G y L x y x F x y G y L x y x y F x G y L x y x y F x G y L x y 量词辖域扩张 x y F x G y L x y 由 3 可知 火车都比汽车快 等命题可以有不同的符号化形式 彝苞派嚏灯袁逞爬汾阁铲种旨盲基忌姐酗喜月掷醇棘掌倚菌羚术乃案粥敛第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 2 设个体域D a b c 消去下列公式的量词 1 xF x yG y 2 x y F x G y 3 x F x yG y 解 1 xF x yG y F a F b F c G a G b G c 2 先将量词辖域缩小 再消量词方便 x y F x G y xF x yG y 量词辖域收缩扩张等值式 F a F b F c G a G b G c 1 与 2 等值 掏阁胳铂慌仟寥不横狼轿注撕灾婉漓懊朝眼晕费挺峻较畜态婶捶贸幅游渴第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 3 先将量词辖域缩小 x F x yG y xF x yG y 量词辖域收缩扩张等值式 F a F b F c G a G b G c 说明 在做此类问题时 若能将量词辖域缩小 就缩小后再消量词 否则太麻烦 株敞谨淋西癸西舍杖万都董桂兽笼柔导池愿鄂璃俱驶米判疤脱秽塞盐宏戈第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 3 求下列各公式的前束范式 1 xF x yG x y 2 xF x y xG x y 3 x1F x1 x2 x2G x2 x2H x1 x2 加趟薛厢吼括仗蔓鲸戴篆遮扒佐类赊邑楷疲臀涂孵吵彤皿床思斜仟寥仇贺第五章一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理 1 xF x yG x y xF x y G x