推荐04b前束范式逻辑习题

1、1第八讲第八讲前束范式前束范式 数理逻辑习题分析数理逻辑习题分析2parsing multivariate quantificationwhen evaluating an expression such asx y z p (x,y,z ) translate the proposition in the same order to english:there is an x such that for all y there is a z such that p (x,y,z) holds.3parsing examplep (x,y,z ) = “y - x z ”there is an

2、 x such that for all y there is a z such that y - x z.there is some number x which when subtracted from any number y results in a number bigger than some number z.q: if the universe of discourse for x, y, and z is the natural numbers 0,1,2,3,4,5,6,7, whats the truth value of xy z p (x,y,z )? 4parsin

3、g 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 we need to find a positive instance z such

4、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 ?5parsing 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 x := y and z := 0 ? 6order mattersset the univ

5、erse（论域） 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?7order matters but not alwaysq: what if we have two quantifiers of the same kind? does order still matter?a: no! if we have two quantifiers of the same ki

6、nd 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”8logical equivalence with formulas def: two logical expressions possibly involving propositional f

7、ormulas 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 equivalent names of variables dont matter.eg: x y q (x,y ) and y x

8、q (x,y ) are not!9demorgan 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 negation: x p(x ) x p(x )existential negation: x p(x ) x p(x )10

9、谓词公式的前束范式一个谓词公式，如果量词都在整个式子的前头，其作用域延伸到整个谓词公式的末尾，这样的谓词公式叫前束范式前束范式。定理：定理：任意一个谓词公式，都有一个与之等任意一个谓词公式，都有一个与之等价的前束范式价的前束范式。见课本p73例题1311前束合取(析取)范式定理定理：每一个谓词公式都可转化为与其每一个谓词公式都可转化为与其等价的前束合取等价的前束合取(析取析取)范式范式。转化的步骤：1）取消多余的量词2）换名3）消去条件、双条件联结词4）将 深入5）将量词移至左边12练 习课本p7513谓词演算的推理课本p79 习题(3)14本节总结内容内容：谓词公式的前束范式要求要求：能把任

10、意一个谓词公式转化为与之等价的前束合取（析取）范式。15重点与难点重点重点：理解前束范式的意义难点难点：前束范式与主合（析）取范式的区别16上周习题讲解p23 (2) c)p23 (8) b) d)p29 (2)p39 (4)17课本练习p18习题（6）由n个命题变元组成不等价的命题公式的个数为： (a) 2n (b) 2n (c) n2 (d)18课本练习p29习题（1）b） c）p29习题（3）（4）（5）（6）p39习题（7）（8）p47习题（5）19课本练习p59习题（1）（2）p66习题（3）a）p71习题（2）（4）（5）（6）20补充练习将下列命题符号化：1、天下乌鸦一般黑天下乌

11、鸦一般黑； 2、任何金属都可以溶解在某种液体中任何金属都可以溶解在某种液体中； 3、所有人的指纹都不一样所有人的指纹都不一样； 21补充练习将下列命题符号化：金子是闪光的，闪光的不一定是金子。某些女同学比所有男孩子聪明上一句的否定（用前束范式） 22补充练习符号化下列论断，并用演绎法验证其正确性： 1、如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加；因此，如果甲参加球赛，那么丙就参加；2、如果今天是星期二，那么我要考计算机科学或经济学；若经济学教授病了，就不考经济学；今天是星期二，并且经济学教授病了，所以我要考计算机科学。 23补充练习证明：(pq)(q)(p) 是重言

12、式 已知pq = (pq)，证明：q=(qq)(qq) 24补充练习 有甲、乙、丙三个学生，一个出生在北京，一个出生在上海，一个出生在武汉。他们中一个学国际金融专业，一个学工商管理专业，一个是学外语的。其中： 1、甲不是学国际金融的，乙不是学外语的 2、学国际金融的不出生在上海； 3、学外语的出生在北京； 4、乙不出生在武汉。问：甲、乙、丙分别在哪儿出生？学什么专业？ 25某人说：“我家的每一个成员都是在广州出生的。”如果他说的话事实上是错的，则下面哪一条是对的？（ ）a、他家没有一个成员出生在广州。b、他家至少有一个成员出生在广州。c、他不是出生在广州。d、他家至少有一个成员不是出生在广州。 e、如果他出生在广州，现在他仅是个儿童。补充练习26“没有人爱每一个人；牛郎爱织女，织女爱每一个爱牛郎的人。” 如果以上陈述为真，则下列哪项不可能为真？（ ）1) 每一个人都爱牛郎。2) 每一个人都爱一些人。3）织女不爱牛郎。a、仅1 b、仅2 c、仅3 d、1、2 补充练习27补充练习 某报社招聘一名记者，有赵、钱、孙、李、周、吴人应试，究竟谁能被录用，甲、丙、丁人各抒己见：甲：赵、钱有希望；乙：孙、赵有希望；丙：周、吴有希望；丁：赵不可能。结果证明，只有一个人的预见是对的。请问，谁当上了记者？ 28判断以下推理