离散数学课件 第二章 谓词逻辑-2nd.pdf

第二章谓词逻辑 大连理工大学软件学院 陈志奎 教授 办公室：综合楼411 ，Tel 实验室：教学楼A318/A323 ，Tel 24 Mobile: Email: zkchen@ zkchen00@ 43 回顾 •谓词、个体、量词 – 一元、多元、域、全称、存在 •合式谓词公式 – 定义：5条 • 自由变元和约束变元 •含有量词的等价式和永真蕴含式 •谓词公式的解释 43 记忆规律 (∀x )(∀y ) (∀y )(∀x ) B1 B2 B3 (∃y )(∀x ) (∃x )(∀y ) B4 B5 (∀x )(∃y ) (∀y )(∃x ) B 6 B7 B8 (∃y )(∃x ) (∃x )(∃y ) 43 2.2谓词逻辑中的推理规则 •推理规则 43 规则1：约束变元的改名规则 (∀x )P (x ) 等价于 (∀y )P (y ) •对约束变元进行换名，使得一个变元在一 个公式中只呈一种形式出现。规则如下： – 欲改名之变元应是某量词作用范围内的变 元，且应同时更改该变元在此量词辖域内的 所有约束出现，而公式的其余部分不变。 – 新的变元符号应是此量词辖域内原先没有使 用过的，最好是公式中未出现过的符号。 43 规则1：约束变元的改名规则 •例：对公式∀x(P(x, y) →∃yQ(x, y,z)) ∧ S (x, z)进 行换名，使各变元只呈一种形式出现。 解： 需要对约束变元x ，y 进行换名 ∀u(P(u, y) →∃vQ(u, v,z)) ∧S(x,z) 不对的： ∀u(P(u, v) →∃vQ(u, v,z)) ∧S(x, z) u(P(u, y) zQ(u, , z)) S(x,∀z) →∃ z ∧