04b前束范式+邏輯習題

第八講前束范式數(shù)理邏輯習題分析104b前束范式+邏輯習題ParsingMultivariateQuantificationWhenevaluatinganexpressionsuchasxyzP(x,y,z)

translatethepropositioninthesameordertoEnglish:ThereisanxsuchthatforallythereisazsuchthatP(x,y,z)holds.204b前束范式+邏輯習題ParsingExampleP(x,y,z)

=“y-x≥z”Thereisanxsuchthatforallythereisazsuchthaty-x≥z.Thereissomenumberxwhichwhensubtractedfromanynumberyresultsinanumberbiggerthansomenumberz.Q:Iftheuniverseofdiscourseforx,y,andzisthenaturalnumbers{0,1,2,3,4,5,6,7,…}what’sthetruthvalueofxyzP(x,y,z)?

304b前束范式+邏輯習題ParsingExampleA:True.Forany“exists”weneedtofindapositiveinstance.Sincexisthefirstvariableintheexpressionandis“existential”,weneedanumberthatworksforallothery,z.Setx=0(wanttoensurethaty-xisnottoosmall).Nowforeachyweneedtofindapositiveinstancezsuchthat

y-x≥zholds.Plugginginx=0weneedtosatisfyy≥zsosetz:=y.Q:Didwehavetosetz:=y?404b前束范式+邏輯習題ParsingExampleA:No.Couldalsohaveusedtheconstantz:=0.Manyothervalidsolutions.Q:Isn’titsimplertosatisfyxyz(y-x≥z) bysettingx:=yandz:=0?504b前束范式+邏輯習題OrdermattersSettheuniverse（論域）ofdiscoursetobeallnaturalnumbers{0,1,2,3,…}.LetR(x,y)=“x<y”.Q1:WhatdoesxyR(x,y)mean?Q2:WhatdoesyxR(x,y)mean?604b前束范式+邏輯習題Ordermatters–butnotalwaysQ:Whatifwehavetwoquantifiersofthesamekind?Doesorderstillmatter?A:No!Ifwehavetwoquantifiersofthesamekindorderisirrelevent.xyisthesameasyxbecausethesearebothinterpretedas“foreverycombinationofxandy…”xyisthesameasyxbecausethesearebothinterpretedas“thereisapairx,y…”704b前束范式+邏輯習題LogicalEquivalencewithFormulasDEF:Twologicalexpressionspossiblyinvolvingpropositionalformulasandquantifiersaresaidtobelogicallyequivalentifno-matterwhatuniverseandwhatparticularpropositionalformulasarepluggedin,theexpressionsalwayshavethesametruthvalue.EG:xyQ(x,y)andyxQ(y,x)areequivalent–namesofvariablesdon’tmatter.EG:xyQ(x,y)andyxQ(x,y)arenot!804b前束范式+邏輯習題DeMorganRevisitedRecallDeMorgan’sidentities:Conjunctionalnegation:(p1p2…pn)(p1p2…pn)Disjunctionalnegation:(p1p2…pn)(p1p2…pn)SincethequantifiersarethesameastakingabunchofAND’s()orOR’s()wehave:Universalnegation:xP(x)xP(x)Existentialnegation:xP(x)xP(x)904b前束范式+邏輯習題謂詞公式的前束范式

一個謂詞公式，如果量詞都在整個式子的前頭，其作用域延伸到整個謂詞公式的末尾，這樣的謂詞公式叫前束范式。定理：

任意一個謂詞公式，都有一個與之等價的前束范式。 見課本P73例題1~31004b前束范式+邏輯習題前束合取(析取)范式定理：

每一個謂詞公式都可轉(zhuǎn)化為與其等價的前束合取(析取)范式。轉(zhuǎn)化的步驟：

1）取消多余的量詞

2）換名

3）消去條件、雙條件聯(lián)結(jié)詞

4）將┑深入

5）將量詞移至左邊1104b前束范式+邏輯習題練習課本P751204b前束范式+邏輯習題謂詞演算的推理課本P79習題(3)1304b前束范式+邏輯習題本節(jié)總結(jié)內(nèi)容：

謂詞公式的前束范式要求： 能把任意一個謂詞公式轉(zhuǎn)化為與之等價的前束合?。ㄎ鋈。┓妒?。1404b前束范式+邏輯習題重點與難點重點： 理解前束范式的意義難點： 前束范式與主合（析）取范式的區(qū)別1504b前束范式+邏輯習題上周習題講解P23(2)C)P23(8)B)D)P29(2)P39(4)1604b前束范式+邏輯習題課本練習P18習題（6）由n個命題變元組成不等價的命題公式的個數(shù)為：

(A)2n(B)2n(C)n2(D)1704b前束范式+邏輯習題課本練習P29習題（1）B）C）P29習題（3）（4）（5）（6）P39習題（7）（8）P47習題（5）1804b前束范式+邏輯習題課本練習P59習題（1）（2）P66習題（3）A）P71習題（2）（4）（5）（6）1904b前束范式+邏輯習題補充練習將下列命題符號化：1、天下烏鴉一般黑；

2、任何金屬都可以溶解在某種液體中；

3、所有人的指紋都不一樣；

2004b前束范式+邏輯習題補充練習將下列命題符號化：金子是閃光的，閃光的不一定是金子。某些女同學比所有男孩子聰明上一句的否定（用前束范式）2104b前束范式+邏輯習題補充練習符號化下列論斷，并用演繹法驗證其正確性：

1、如果乙不參加籃球賽，那么甲就不參加；如果乙參加籃球賽，那么甲和丙就參加；因此，如果甲參加球賽，那么丙就參加；

2、如果今天是星期二，那么我要考計算機科學或經(jīng)濟學；若經(jīng)濟學教授病了，就不考經(jīng)濟學；今天是星期二，并且經(jīng)濟學教授病了，所以我要考計算機科學。2204b前束范式+邏輯習題補充練習證明：(PQ)(Q)(P)是重言式已知PQ=(PQ)，證明：Q=(QQ)(QQ)2304b前束范式+邏輯習題補充練習

有甲、乙、丙三個學生，一個出生在北京，一個出生在上海，一個出生在武漢。他們中一個學國際金融專業(yè)，一個學工商管理專業(yè)，一個是學外語的。其中：

1、甲不是學國際金融的，乙不是學外語的

2、學國際金融的不出生在上海；

3、學外語的出生在北京；

4、乙不出生在武漢。問：甲、乙、丙分別在哪兒出生？學什么專業(yè)？2404b前束范式+邏輯習題某人說：“我家的每一個成員都是在廣州出生的?！比绻f的話事實上是錯的，則下面哪一條是對的？（）A、他家沒有一個成員出生在廣州。B、他家至少有一個成員出生在廣州。C、他不是出生在廣州。D、他家至少有一個成員不是出生在廣州。E、如果他出生在廣州，現(xiàn)在他僅是個兒童。補充練習2504b前束范式+邏輯習題“沒有人愛每一個人；牛郎愛織女，織女愛每一個愛牛郎的人?！比绻陨详愂鰹檎?，則下列哪項不可能為真？（）1)每一個人都愛牛郎。2)每一個人都愛一些人。3）織女不愛牛郎。A、僅1B、僅2C、僅3D、1、2補充練習2604b前束范式+邏輯習題補充練習

某報社招聘一名記者，有趙、錢、孫、李、周、吳６人應(yīng)試，究竟誰能被錄用，甲、丙、?。慈烁魇慵阂姡杭祝黑w、錢有希望；乙：孫、趙有希望；丙：周、吳有希望；?。黑w不可能。 結(jié)果證明，只有一個人的預(yù)見是對的。請問，誰當上了記者？2704b前束范式+邏輯習題判斷以下推理是否正確：（）三角函數(shù)都