《04b前束范式+逻辑习题[课资资源]》由会员分享，可在线阅读，更多相关《04b前束范式+逻辑习题[课资资源]（29页珍藏版）》请在金锄头文库上搜索。
1、第八讲第八讲前束范式前束范式 数理逻辑习题分析数理逻辑习题分析1骄阳书屋Parsing ExampleA: True.For any “exists” we need to find a positive instance.Since x is the first variable in the expression and is “existential”, we need a number that works for all other y, z. Set x = 0 (want to ensure that y -x is not too small).Now for each y w
2、e need to find a positive instance z such that y - x z holds. Plugging in x = 0 we need to satisfy y z so set z := y.Q: Did we have to set z := y ?4骄阳书屋Parsing ExampleA: No. Could also have used the constant z := 0. Many other valid solutions.Q: Isnt it simpler to satisfy x y z (y - x z )by setting
3、x := y and z := 0 ? 5骄阳书屋Order mattersSet the universe（论域） of discourse to be all natural numbers 0, 1, 2, 3, .Let R (x,y ) = “x y”.Q1: What does x y R (x,y ) mean?Q2: What does y x R (x,y ) mean?6骄阳书屋Order matters but not alwaysQ: What if we have two quantifiers of the same kind? Does order still m
4、atter?A: No! If we have two quantifiers of the same kind order is irrelevent.x y is the same as y x because these are both interpreted as “for every combination of x and y”x y is the same as y x because these are both interpreted as “there is a pair x , y”7骄阳书屋Logical Equivalence with Formulas DEF:
5、Two logical expressions possibly involving propositional formulas and quantifiers are said to be logically equivalent if no-matter what universe and what particular propositional formulas are plugged in, the expressions always have the same truth value.EG: x y Q (x,y ) and y x Q (y,x ) are equivalen
6、t names of variables dont matter.EG: x y Q (x,y ) and y x Q (x,y ) are not!8骄阳书屋DeMorgan RevisitedRecall DeMorgans identities:Conjunctional negation:(p1p2pn) (p1p2pn)Disjunctional negation:(p1p2pn) (p1p2pn)Since the quantifiers are the same as taking a bunch of ANDs () or ORs () we have:Universal ne
7、gation: x P(x ) x P(x )Existential negation: x P(x ) x P(x )9骄阳书屋谓词公式的前束范式一个谓词公式，如果量词都在整个式子的前头，其作用域延伸到整个谓词公式的末尾，这样的谓词公式叫前束范式前束范式。定理：定理：任意一个谓词公式，都有一个与之等价任意一个谓词公式，都有一个与之等价的前束范式的前束范式。见课本P73例题1310骄阳书屋前束合取(析取)范式定理定理：每一个谓词公式都可转化为与其每一个谓词公式都可转化为与其等价的前束合取等价的前束合取(析取析取)范式范式。转化的步骤：1）取消多余的量词2）换名3）消去条件、双条件联结词4）将
8、深入5）将量词移至左边11骄阳书屋练 习课本P7512骄阳书屋谓词演算的推理课本P79 习题(3)13骄阳书屋本节总结内容内容：谓词公式的前束范式要求要求：能把任意一个谓词公式转化为与之等价的前束合取（析取）范式。14骄阳书屋重点与难点重点重点：理解前束范式的意义难点难点：前束范式与主合（析）取范式的区别15骄阳书屋上周习题讲解P23 (2) C)P23 (8) B) D)P29 (2)P39 (4)16骄阳书屋课本练习P18习题（6）由n个命题变元组成不等价的命题公式的个数为： (A) 2n (B) 2n (C) n2 (D)17骄阳书屋课本练习P29习题（1）B） C）P29习题（3）（4
9、）（5）（6）P39习题（7）（8）P47习题（5）18骄阳书屋课本练习P59习题（1）（2）P66习题（3）A）P71习题（2）（4）（5）（6）19骄阳书屋补充练习将下列命题符号化：1、天下乌鸦一般黑天下乌鸦一般黑； 2、任何金属都可以溶解在某种液体中任何金属都可以溶解在某种液体中； 3、所有人的指纹都不一样所有人的指纹都不一样； 20骄阳书屋补充练习将下列命题符号化：金子是闪光的，闪光的不一定是金子。某些女同学比所有男孩子聪明上一句的否定（用前束范式） 21骄阳书屋补充练习符号化下列论断，并用演绎法验证其正确性： 1、如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加
10、；因此，如果甲参加球赛，那么丙就参加； 2、如果今天是星期二，那么我要考计算机科学或经济学；若经济学教授病了，就不考经济学；今天是星期二，并且经济学教授病了，所以我要考计算机科学。 22骄阳书屋补充练习证明：(PQ)(Q)(P) 是重言式 已知PQ = (PQ)，证明：Q=(QQ)(QQ) 23骄阳书屋补充练习 有甲、乙、丙三个学生，一个出生在北京，一个出生在上海，一个出生在武汉。他们中一个学国际金融专业，一个学工商管理专业，一个是学外语的。其中： 1、甲不是学国际金融的，乙不是学外语的 2、学国际金融的不出生在上海； 3、学外语的出生在北京； 4、乙不出生在武汉。问：甲、乙、丙分别在哪儿出生
11、？学什么专业？ 24骄阳书屋某人说：“我家的每一个成员都是在广州出生的。”如果他说的话事实上是错的，则下面哪一条是对的？（ ）A、他家没有一个成员出生在广州。B、他家至少有一个成员出生在广州。C、他不是出生在广州。D、他家至少有一个成员不是出生在广州。 E、如果他出生在广州，现在他仅是个儿童。补充练习25骄阳书屋“没有人爱每一个人；牛郎爱织女，织女爱每一个爱牛郎的人。” 如果以上陈述为真，则下列哪项不可能为真？（ ）1) 每一个人都爱牛郎。2) 每一个人都爱一些人。3）织女不爱牛郎。A、仅1 B、仅2 C、仅3 D、1、2 补充练习26骄阳书屋补充练习 某报社招聘一名记者，有赵、钱、孙、李、周
12、、吴人应试，究竟谁能被录用，甲、丙、丁人各抒己见：甲：赵、钱有希望；乙：孙、赵有希望；丙：周、吴有希望；丁：赵不可能。结果证明，只有一个人的预见是对的。请问，谁当上了记者？ 27骄阳书屋判断以下推理是否正确：（ ）三角函数都是周期函数，一些三角函数是连续函数，所以一些周期函数是连续函数；（ ）不存在白色的乌鸦，北京鸭是白色的，所以北京鸭不是乌鸦；（ ）所有的舞蹈者都很有风度，王小姐是个学生并且是个舞蹈者，因此有些学生很有风度；（ ）没有不守信用的人是可以信赖的，有些可以信赖的人是受过教育的，因此，有些受过教育的人是守信用的；28骄阳书屋课 后 任 务复习复习：第一、二章*思考：思考：整理“数理逻辑”的脉络 29骄阳书屋
