大连大连理工大学软件学院离散数学第二章谓词逻辑2nd.ppt

*/43 谓词逻辑求解实际问题 第二步，符号化问题 */43 谓词逻辑求解实际问题 第三步，证明 */43 谓词逻辑求解实际问题 接上页 */43 谓词逻辑求解实际问题 例11：所有的蜂鸟都五彩斑斓；没有大鸟以蜜为生；不以蜜为生的鸟都色彩单调；因此，蜂鸟都是小鸟。 解：定义谓词如下： P(x)：x是只蜂鸟； Q(x)：x是大鸟； R(x)：x是以蜜为生的鸟； S(x)：x五彩斑斓。 */43 谓词逻辑求解实际问题 证明： */43 随堂练习 练习：符号化下列命题，并利用推理规则论证结论。 所有牛都有角，有些动物是牛，所以有些动物有角 */43 2.3谓词公式的范式 命题逻辑中的两种范式都可以直接推广到谓词逻辑中来，只要把原子命题公式换成原子谓词公式即可， 根据量词在公式中出现的情况不同，又可分为前束范式和斯柯林范式。 */43 前束范式 定义：对任一谓词公式F，如果其中所有量词均非否定的出现在公式的最前面，且它们的辖域为整个公式，则称公式F为前束范式。 */43 前束范式 任意一个公式都可以转化成与之等价的前束范式，方法如下： 消去公式中的联结词 和→，例如 将公式内的否定符号深入到谓词变元前并化简到谓词变元前只有一个否定号； 利用改名、代入规则使所有的约束变元均不同名，且使自由变元与约束变元亦不同名； 扩充量词的辖域至整个公式。 */43 前束范式 例：将下列公式转化成前束范式。 解： */43 斯柯林范式 定义：如果前束范式中所有的存在量词均在全称量词之前，则称这种形式为斯柯林范式。 */43 斯柯林范式 任何一个公式都可以化为与之等价的斯柯林范式，方法如下： 先将给定公式化为前束范式； 将前束范式中的所有自由变元用全称量词（UG）约束； 若经上述改造后的公式A中，第一个量词不是存在量词，则可以将等价变换成如下形式 如果前束范式是由n个存在量词开始，然后是m个全称量词，后面还跟有存在量词，则可以利用下述等价式将这些全称量词逐一移到存在量词之后去： */43 斯柯林范式 例：将公式 化成斯柯林范式。 解： */43 作业 P39 2（2） 3(2)(4)(5) P40， 4（1、2, 3） 5 6（1） P42，1（1、2） 2（1、3） 3（2） 补充 符号化下列命题并推证其结论 1.已知某些病人喜欢所有的医生，所有病人都不喜欢任一骗子，证明任何一个医生都不是骗子。 */43 2 * 上面的例子告诉我们在证明的过程中，若有带存在量词的前提要首先引入，即规则尽量提前使用，以保证规则使用的有效性。 2/44 离散数学 第二章 谓词逻辑 */43 回顾 谓词、个体、量词 一元、多元、域、全称、存在 合式谓词公式 定义： 5条 自由变元和约束变元 含有量词的等价式和永真蕴含式 谓词公式的解释 */43 记忆规律 */43 2.2谓词逻辑中的推理规则 推理规则 */43 规则1：约束变元的改名规则 对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现。规则如下： 欲改名之变元应是某量词作用范围内的变元，且应同时更改该变元在此量词辖域内的所有约束出现，而公式的其余部分不变。 新的变元符号应是此量词辖域内原先没有使用过的，最好是公式中未出现过的符号。 */43 规则1：约束变元的改名规则 例：对公式 进行换名，使各变元只呈一种形式出现。 解： 需要对约束变元x，y进行换名 不对的： ~ ~ */43 规则2：自由变元的代入规则 对公式中自由变元的更改叫做代入。规则如下： 欲改变自由变元的名，必改在公式中的每一处自由出现。 新变元不应在原公式中以任何约束形式出现。 例：对公式 的变元 x,y的自由出现用w,t代入，得 */43 例如 对公式 ( x) (P(x) →Q(x))∨( x) (P(x) →R(x)) 为清楚起见，可对第二个约束变元x进行换名 ( x) (P(x) →Q(x))∨( y) (P(y) →R(y)) 又例如 对公式 ( x) (P(x) →R(x,y)) ∧Q(x,y