1、1第八講第八講前束范式前束范式 數(shù)理邏輯習(xí)題分析數(shù)理邏輯習(xí)題分析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前束合取(析取)范式定理定理：每一個謂詞公式都可轉(zhuǎn)化為與其每一個謂詞公式都可轉(zhuǎn)化為與其等價的前束合取等價的前束合取(析取析取)范式范式。轉(zhuǎn)化的步驟：1）取消多余的量詞2）換名3）消去條件、雙條件聯(lián)結(jié)詞4）將 深入5）將量詞移至左邊12練 習(xí)課本p7513謂詞演算的推理課本p79 習(xí)題(3)14本節(jié)總結(jié)內(nèi)容內(nèi)容：謂詞公式的前束范式要求要求：能把任

10、意一個謂詞公式轉(zhuǎn)化為與之等價的前束合取（析取）范式。15重點與難點重點重點：理解前束范式的意義難點難點：前束范式與主合（析）取范式的區(qū)別16上周習(xí)題講解p23 (2) c)p23 (8) b) d)p29 (2)p39 (4)17課本練習(xí)p18習(xí)題（6）由n個命題變元組成不等價的命題公式的個數(shù)為： (a) 2n (b) 2n (c) n2 (d)18課本練習(xí)p29習(xí)題（1）b） c）p29習(xí)題（3）（4）（5）（6）p39習(xí)題（7）（8）p47習(xí)題（5）19課本練習(xí)p59習(xí)題（1）（2）p66習(xí)題（3）a）p71習(xí)題（2）（4）（5）（6）20補(bǔ)充練習(xí)將下列命題符號化：1、天下烏鴉一般黑天下烏

11、鴉一般黑； 2、任何金屬都可以溶解在某種液體中任何金屬都可以溶解在某種液體中； 3、所有人的指紋都不一樣所有人的指紋都不一樣； 21補(bǔ)充練習(xí)將下列命題符號化：金子是閃光的，閃光的不一定是金子。某些女同學(xué)比所有男孩子聰明上一句的否定（用前束范式） 22補(bǔ)充練習(xí)符號化下列論斷，并用演繹法驗證其正確性： 1、如果乙不參加籃球賽，那么甲就不參加；如果乙參加籃球賽，那么甲和丙就參加；因此，如果甲參加球賽，那么丙就參加；2、如果今天是星期二，那么我要考計算機(jī)科學(xué)或經(jīng)濟(jì)學(xué)；若經(jīng)濟(jì)學(xué)教授病了，就不考經(jīng)濟(jì)學(xué)；今天是星期二，并且經(jīng)濟(jì)學(xué)教授病了，所以我要考計算機(jī)科學(xué)。 23補(bǔ)充練習(xí)證明：(pq)(q)(p) 是重言

12、式 已知pq = (pq)，證明：q=(qq)(qq) 24補(bǔ)充練習(xí) 有甲、乙、丙三個學(xué)生，一個出生在北京，一個出生在上海，一個出生在武漢。他們中一個學(xué)國際金融專業(yè)，一個學(xué)工商管理專業(yè)，一個是學(xué)外語的。其中： 1、甲不是學(xué)國際金融的，乙不是學(xué)外語的 2、學(xué)國際金融的不出生在上海； 3、學(xué)外語的出生在北京； 4、乙不出生在武漢。問：甲、乙、丙分別在哪兒出生？學(xué)什么專業(yè)？ 25某人說：“我家的每一個成員都是在廣州出生的。”如果他說的話事實上是錯的，則下面哪一條是對的？（ ）a、他家沒有一個成員出生在廣州。b、他家至少有一個成員出生在廣州。c、他不是出生在廣州。d、他家至少有一個成員不是出生在廣州。 e、如果他出生在廣州，現(xiàn)在他僅是個兒童。補(bǔ)充練習(xí)26“沒有人愛每一個人；牛郎愛織女，織女愛每一個愛牛郎的人。” 如果以上陳述為真，則下列哪項不可能為真？（ ）1) 每一個人都愛牛郎。2) 每一個人都愛一些人。3）織女不愛牛郎。a、僅1 b、僅2 c、僅3 d、1、2 補(bǔ)充練習(xí)27補(bǔ)充練習(xí) 某報社招聘一名記者，有趙、錢、孫、李、周、吳人應(yīng)試，究竟誰能被錄用，甲、丙、丁人各抒己見：甲：趙、錢有希望；乙：孫、趙有希望；丙：周、吳有希望；丁：趙不可能。結(jié)果證明，只有一個人的預(yù)見是對的。請問，誰當(dāng)上了記者？ 28判斷以下推理