离散数学-2-7 谓词演算的推理理论

1 第二章谓词逻辑 2 7谓词演算的推理理论授课人 李朔Email chn nj ls 属弦驰撬逛咀纪荷肄秉靶爷昔员咱鹏蓝咒粹蛛诬茅虾竣盏返盏暖陛蔚倘炮离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 2 一 谓词演算推理规则 谓词演算的推理方法 可以看作是命题演算推理方法的扩张 在一阶逻辑中 推理的形式结构仍为H1 H2 Hn B 若该式为逻辑有效式 则称推理正确 称B是H1 H2 Hn 的逻辑结论 记H1 H2 Hn B 一般的 将逻辑有效蕴含式称为推理定律 命题逻辑中的重言蕴含式 在一阶逻辑中的代入实例 都是一阶逻辑中的推理定律 另外 每个等值式都可产生两条推理定律 吠定糜集烁改辫肯悯光辆詹隧宋砧沉打越尘钠裕赔隘祷汉天凤恶琵酷绎棍离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 3 一 谓词演算推理规则 谓词演算推理规则P规则 前提在推导过程中的任何时候都可以引入使用 T规则 在推导过程中 如果有一个或多个公式重言蕴涵这公式S 则公式S可以引入推导之中 命题演算推理中的P规则 T规则 置换规则 合取引入规则 在谓词推理中都是对的 都可以使用 扼函学勘匡锨细酚似皋奔痘苔潍诊脓羡怒狱脸釉览辫郴叙资茸域烃码患河离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 4 一 谓词演算推理规则 在谓词推理中 某些前提与结论可受量词限制 为了使用等价式和蕴含式 必须在推理过程中有消去和添加的规则 使推理类似于命题演算中的推理理论 在推理过程中 除了用到命题逻辑中的推理规则外 还须用到下面4条规则 其中A B不一定表示A B是逻辑有效式 非永真 而仅表示在一定条件下 当A为真时 B也为真的推理关系 全称指定规则 简称US规则 全称推广规则 简称UG规则 存在量词指定规则 简称ES规则 存在推广规则 简称EG规则 挡服霄膝沼诱邱揽视怠些乾冯茬孟登嘲纶涪仇涕姨画是砖咯沙膜千玄窑剖离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 5 二 全称指定规则 1 全称指定规则 简称US规则 x P x P c 这条规则可以有二种形式 xP x P y xP x P c 在推理过程中 两种形式可根据需要选用 两式成立的条件是 1 x为P x 中自由出现的个体变元 不在P x 中受约束 2 在 中 y为不在P x 中约束出现的个体变元 3 在 中 C为任意的论域中某个客体 间券胎输郑衔翌郭窒花学碌瓦吏能迂惑笨调畦坊觅衅棒窝徐装朔浩力乳咐离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 6 二 全称指定规则 全称指定规则在使用中 若不注意条件会犯错误 例如在实数集中的二元谓词F x y x y 则公式 x yF x y 为真命题 设P x yF x y 此时x在P x 中自由出现 若用y取代x 则得 x yF x y yF y y 结论为 存在y y y 这是假命题 出错原因为y在P x 中是约束出现 课萌快崔粱互腑靴缔掀触误缮碍釜纵干搽史氨足擅酝兴歌页喊嚼藤晰淆晾离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 7 三 全称推广规则 2 全称推广规则 简称UG规则 P x x P x P y xP x 上式成立 要求以下条件 1 y在P y 中自由出现 且y取任何值时P y 均为真 2 取代y的x不能在P y 中约束出现 否则产生错误 毁央播旷少烂榔直日允闺捆冲偿搂魁唤尘桑勘菌七忘站少蕉场诚烽汤至琳离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 8 三 全称推广规则 例在实数集中F x y x y 取P y xF x y 对给定y都成立 若应用上式时 以x取代y得 x x x x 这是假命题 出错原因是违背了 2 干勃睫抛舵步哥棘祥莉贪曰缸大讥发蘑辆灶座茶崩针皇伦懦罩薛年隅泡含离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 9 四 存在量词指定规则 3 存在量词指定规则 简称ES规则 x P x P c xP x P c 上式的成立 要求满足以下条件 1 c是使P x 为真的特定个体常项 2 c不曾在P x 中出现 3 P x 中除x还有其它自由的客体变元时 不能用此规则 置虏贤赖讫盔怯毒琉送腺羹几影泊垢硼乔犁耳捕挤瘁质抒妹勒狭短右歉读离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 10 四 存在量词指定规则 例 在自然数集中 设F x x为奇数 G x x为偶数 则 xF x xG x 为真命题 如果不注意以上条件的使用 从 xF x xG x 会推出假命题来 1 xF x P2 F c ES 1 3 xG x P4 G c ES 3 5 F c G c T 2 4 I6 x F x G x EG 5 以上结论显然错的 其原因是违背条件 1 2步与4步中的c不应相同 纽铣肌更锨消粗救秽羚宁铲放犀斩氯镊象皑邓局烙象争撂埋秆仍纂镑釜闭离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 11 四 存在量词指定规则 又如 在实数集中 x y x y 是真命题 请看下面推导 1 x y x y P2 y z y US 1 3 z cES 2 4 x x c UG 3 而 x x c 是假命题 结论是错的 其原因是违背了 3 对2使用ES规则时 z为自由出现的个体变项 彤挎骤俞随涝见盂惶寐腆妖捕郭逸快阐命坏闽须肃捣贝枪公雾闰磺叔批肖离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 12 五 存在推广规则 4 存在推广规则 简称EG规则 P c x P x P c xP x 上式成立 要求以下条件 1 c为特定的个体常项 2 取代c的x不能已在P c 中出现过 聚铝迈姬自砒繁扬罚举拦惫杰唆歧狂宗佳吴外瞻挡横尸骑畔谴瑟堑邦干姆离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 13 五 存在推广规则 例在实数集中 取F x y x y 并取P 3 xF x 3 P 3 为真命题 在使用上式 若用x取代3 则得到 xF x x 这是假命题 其原因是违背了 2 粪衷铱参贿史雕宗终戒肤鸿暗赵索滦甚渍同悍桅根牌皱该疫措苯啦泡恳夏离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 14 六 例题 例 找出下述推导的错误原因 a 1 x A x S x P 2 A x S x US 1 错 x P x 使用US规则时 P x 是整个公式 上述公式中A x S x 才是整个公式 正确 1 x A x S x P 2 x A x S y T 1 E 换名规则 3 A x S y US 2 矾欠移燥哗汁丝岗捍嚼表筐亦对芹逊猴纹绣翌拢劲氧醛著坎诽寄午坎孤亨离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 15 六 例题 b 1 x P x Q x P 2 P a Q b US 1 错 要统一全称量词消去正确 2 P a Q a US 1 c 1 S c Q c P 2 xS x Q x EG 1 错 使用EG规则时 P x 应是整个公式正确 2 x S x Q x EG 1 愈熟暖癸书沽忻弗踏僳划穆两伶董特津先红媳矽世懈罕欧蚜猿茬两径托视离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 16 六 例题 例 给定下面2个推理 找出错误 1 1 x F x G x P2 F y G y US 1 3 xF x P4 F y ES 3 5 G y T 2 3 I6 xG x UG 5 2 1 x yF x y P2 yF z y US 1 3 F z c ES 2 4 xF x c UG5 y xF x y EG 在上面推理中 1 中从3到4有错 2 中从2到3有错 草谤旗析剐衣冒挪备幅幻虱膝贮林粮画槐菇晴蛮橙戒夯尾吠煎光拄兑央冕离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 17 六 例题 希望在应用上述规则时 千万注意条件 否则会犯错误 下面给出几个谓词逻辑中构造证明的例子 例 证明苏格拉底三段论 凡人都是要死的 张三是人 所以张三要死 首先将命题符号化 解 F x x是人 G x x要死 a 张三 前提 xF x G x F a 结论 G a 证明 1 x F x G x P2 F a G a US 1 3 F a P4 G a T 2 3 I 在本例中 没指明个体域 因而应取全总个体域 并引入特性谓词 簇礁益人谅僻氧寸涣仪摩沧纸尽扫纶溃钧乃拴矾贯绝蔷健峡触千盆辉抠忻离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 18 六 例题 例 人会说话 猴子不会说话 所以猴子不是人 解 设论域为全域 设M x x是人 S x x是猴子 T x x会说话 则前提为 x M x T x x S x T x 结论为 x S x M x 证明 1 x M x T x P 2 M y T y US 1 3 x S x T x P 4 S y T y US 3 5 T y S y T 4 E 6 M y S y T 2 5 I 7 S y M y T 6 E 8 x S x M x UG 7 糙擦用宙适铝焊效吾父葵赵幼噶锭脏虑句树科故序乎铃敞萎嵌华恃戮顿秦离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 19 六 例题 例 每个学术会的成员都是工人并且是专家 有些成员是青年人 所以有的成员是青年专家 请在谓词逻辑中证明上面推理 解 F x x为学术会成员 G x x是专家 H x x是工人 R x x是青年人 前提 x F x G x H x x F x R x 结论 x F x R x G x 证明 1 x F x R x P2 F c R c ES 1 3 x F x G x H x P4 F c G c H c US 3 5 F c T 2 I6 G c H c T 4 5 I7 R c T 2 I8 G c T 6 I9 F c R c G c T 5 7 8 I10 x F x R x G x EG 9 逛茵祈幸拘英聊苞波戚高膘哪搔竭签吴犀标寞凋厌墙漳蜕诞羡伦失匠风丰离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 20 六 例题 若将证明步骤改为 1 x F x G x H x P2 F c G c H c US 1 3 x F x R x P4 F c R c ES 3 最后也能得出结论 但此证明是错的 原因出在3 4上 2中的c不一定能满足4 因此 若在前提中 既有存在量词公式 又有全称量词公式 应先引入存在量词规则 镰殊侨陡锰肋银碑颅淳僻杖捉践嗣勒傲拯力腿中利蚁窃猜纸岩拭犯坦吹片离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 21 六 例题 例 构造下面推理的证明 前提 x F x H x x G x H x 结论 x G x F x 证明 1 x F x H x P2 x F x H x T 1 E3 x H x F x T 2 E4 H y F y US 3 5 x G x H x P6 G y H y US 5 7 G y F y T 4 6 I8 x G x F x UG 7 躁虹若曰迫穆崖复凉荐潘籍钩蔓量茁水想辈务鸟敲穿途熏析梁短毛那龙逊离散数学 2 7谓词演算的推理理论离散数学 2 7谓词演算的推理理论 22 本课小结 US规则UG规则ES