04b前束范式+邏輯習(xí)題

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

translatethepropositioninthesameordertoEnglish:ThereisanxsuchthatforallythereisazsuchthatP(x,y,z)holds.204b前束范式+邏輯習(xí)題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前束范式+邏輯習(xí)題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前束范式+邏輯習(xí)題ParsingExampleA:No.Couldalsohaveusedtheconstantz:=0.Manyothervalidsolutions.Q:Isn’titsimplertosatisfyxyz(y-x≥z) bysettingx:=yandz:=0?504b前束范式+邏輯習(xí)題OrdermattersSettheuniverse（論域）ofdiscoursetobeallnaturalnumbers{0,1,2,3,…}.LetR(x,y)=“x<y”.Q1:WhatdoesxyR(x,y)mean?Q2:WhatdoesyxR(x,y)mean?604b前束范式+邏輯習(xí)題Ordermatters–butnotalwaysQ:Whatifwehavetwoquantifiersofthesamekind?Doesorderstillmatter?A:No!Ifwehavetwoquantifiersofthesamekindorderisirrelevent.xyisthesameasyxbecausethesearebothinterpretedas“foreverycombinationofxandy…”xyisthesameasyxbecausethesearebothinterpretedas“thereisapairx,y…”704b前束范式+邏輯習(xí)題LogicalEquivalencewithFormulasDEF:Twologicalexpressionspossiblyinvolvingpropositionalformulasandquantifiersaresaidtobelogicallyequivalentifno-matterwhatuniverseandwhatparticularpropositionalformulasarepluggedin,theexpressionsalwayshavethesametruthvalue.EG:xyQ(x,y)andyxQ(y,x)areequivalent–namesofvariablesdon’tmatter.EG:xyQ(x,y)andyxQ(x,y)arenot!804b前束范式+邏輯習(xí)題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前束范式+邏輯習(xí)題謂詞公式的前束范式

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

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

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

1）取消多余的量詞

2）換名

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

4）將┑深入

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

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

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

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

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

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

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

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

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

1、甲不是學(xué)國(guó)際金融的，乙不是學(xué)外語(yǔ)的

2、學(xué)國(guó)際金融的不出生在上海；

3、學(xué)外語(yǔ)的出生在北京；

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

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