邏輯部分作業(yè)輔導(dǎo)

1、離散數(shù)學(xué)2012春學(xué)期數(shù)理邏輯部分形考作業(yè)輔導(dǎo)下面是本學(xué)期第6，7次形考作業(yè)中的部分題目一、單項(xiàng)選擇題單項(xiàng)選擇題主要是第6次形考作業(yè)的部分題目第6次作業(yè)還是由10個(gè)單項(xiàng)選擇題組成，每小題10分，滿(mǎn)分100分在每次作業(yè)在關(guān)閉之前，允許大家反復(fù)多次練習(xí)，系統(tǒng)將保留您的最好成績(jī)，希望大家要多練幾次，爭(zhēng)取好成績(jī)需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣，請(qǐng)大家一定要認(rèn)真閱讀題目1設(shè)P：我將去打球，Q：我有時(shí)間命題“我將去打球，僅當(dāng)我有時(shí)間時(shí)”符號(hào)化為( )A B C D 因?yàn)檎Z(yǔ)句“僅當(dāng)我有時(shí)間時(shí)”是“我將去打球”的必要條件，一般地，當(dāng)語(yǔ)句是由“，僅當(dāng)”組成，它的符號(hào)化用條件聯(lián)結(jié)詞®所以選項(xiàng)

2、B是正確的正確答案：B問(wèn)：如果把“我將去打球”改成“我將去學(xué)習(xí)”、“我將去旅游”等，怎么符號(hào)化呢？2命題公式PÚQ的合取范式是 ( )APÙQ B（PÙQ）Ú（PÚQ）CPÚQ DØ（ØPÙØQ）復(fù)習(xí)合取范式的定義：定義 一個(gè)命題公式稱(chēng)為合取范式，當(dāng)且僅當(dāng)它具有形式： A1A2An ， （n1）其中A1，A2，An均是由命題變?cè)蚱浞穸ㄋM成的析取式由此可知，選項(xiàng)B和D是錯(cuò)的又因?yàn)镻ÙQ 與PÚQ不是等價(jià)的，選項(xiàng)A是錯(cuò)的所以，選項(xiàng)C是正確的正確答案：C 3命題公式的析取范式是

3、( ) A B C D復(fù)習(xí)析取范式的定義：定義 一個(gè)命題公式稱(chēng)為析取范式，當(dāng)且僅當(dāng)它具有形式： A1A2An ， （n1）其中A1，A2，An均是有命題變?cè)蚱浞穸ㄋM成的合取式 由教材第167頁(yè)中的蘊(yùn)含等價(jià)式知道，公式與是等價(jià)的，滿(mǎn)足析取范式的定義，所以，選項(xiàng)A是正確的正確答案：A注：第2，3題復(fù)習(xí)了合取范式和析取范式的概念，大家一定要記住的。如果題目改為求一個(gè)變?cè)≒或ØP）命題公式的合取范式或析取范式，那么答案是什么？4下列公式成立的為( )AØPÙØQ Û PÚQ BP®ØQ Û ØP&

4、#174;Q CQ®P Þ P DØPÙ(PÚQ)ÞQ 因?yàn)椋?ØPÙ(PÚQ)ÞQ（析取三段論，P171公式(10)） 所以，選項(xiàng)D是正確的正確答案：D 5下列公式 ( )為重言式AØPÙØQ«PÚQ B(Q®(PÚQ) «(ØQÙ(PÚQ) C(P®(ØQ®P)«(ØP®(P®Q) D(ØPÚ(

5、PÙQ) «Q由教材第167頁(yè)中的蘊(yùn)含等價(jià)式，得 (P®(ØQ®P) ÛØPÚ(QÚ P)，(ØP®(P®Q) Û PÚ (ØPÚQ) 所以，C是重言式，也就是永真式正確答案：C說(shuō)明：如果題目改為“下列公式 ( )為永真式”，應(yīng)該是一樣的6設(shè)A（x）：x是人，B（x）：x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號(hào)化為（ ）A(x)(A(x)ÙB(x) BØ(x)(A(x)ÙB(x) CØ(&quo

6、t;x)(A(x)®B(x) DØ(x)(A(x)ÙØB(x) 由題設(shè)知道，A(x)®B(x)表示只要是人，就是學(xué)生，而“不是所有”應(yīng)該用全稱(chēng)量詞的否定，即Ø"x，得到公式C正確答案：C7設(shè)A（x）：x是人，B（x）：x是工人，則命題“有人是工人”可符號(hào)化為（ ）A($x)(A(x)ÙB(x) B("x)(A(x)ÙB(x)CØ("x)(A(x)®B(x) DØ($x)(A(x)ÙØB(x) 選項(xiàng)A中的A(x)ÙB(x)表示x

7、是人，而且是工人，$x 表示存在一個(gè)人，有一個(gè)人，因此($x)(A(x)ÙB(x)表示“有人是工人”正確答案：A 8表達(dá)式中的轄域是( ) AP(x, y) BP(x, y)ÚQ(z) CR(x, y) DP(x, y)ÙR(x, y) 所謂轄域是指“緊接于量詞之后最小的子公式稱(chēng)為量詞的轄域”那么看題中緊接于量詞"x之后最小的子公式是什么呢？顯然是P(x, y)ÚQ(z)，因此，選項(xiàng)B是正確的正確答案：B注：如果該題改為判斷題，即 表達(dá)式中的轄域是P(x, y)如何判斷并說(shuō)明理由呢？9在謂詞公式("x)(A(x)B(x)ÚC

8、(x，y)中，（ ）Ax，y都是約束變?cè)?Bx，y都是自由變?cè)?Cx是約束變?cè)瑈都是自由變?cè)?Dx是自由變?cè)?，y都是約束變?cè)?約束變?cè)褪鞘芟鄳?yīng)的量詞約束的變?cè)杂勺冊(cè)褪遣皇苋魏瘟吭~約束的變?cè)赃x項(xiàng)C是正確的正確答案：C注：如果該題改為填寫(xiě)約束變?cè)蜃杂勺冊(cè)奶羁疹}，大家也應(yīng)該掌握補(bǔ)充題：設(shè)個(gè)體域?yàn)樽匀粩?shù)集合，下列公式中是真命題的為 ( )A B C D因?yàn)檫x項(xiàng)A表示：對(duì)任一自然數(shù)x存在自然數(shù)y滿(mǎn)足xy=1，這樣的y是不存在的 選項(xiàng)B表示：對(duì)任一自然數(shù)x存在自然數(shù)y滿(mǎn)足x+y=0，這樣的y也是不存在的 選項(xiàng)C表示：存在一自然數(shù)x自然數(shù)對(duì)任意自然數(shù)y滿(mǎn)足xy=x，取x=0即可，故選項(xiàng)C正

9、確正確答案：C 下面的內(nèi)容主要是第7次形考作業(yè)的部分題目 二、填空題1命題公式的真值是 因?yàn)?#219;ØPÚ(QÚP) Û1，所以應(yīng)該填寫(xiě)：1應(yīng)該填寫(xiě)：1問(wèn)：命題公式、的真值是什么？2設(shè)P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號(hào)化的結(jié)果為 一般地，當(dāng)語(yǔ)句是由“如果，那么”，或“若，則”組成，它的符號(hào)化用條件聯(lián)結(jié)詞®應(yīng)該填寫(xiě)：(PÚQ)®R3含有三個(gè)命題變項(xiàng)P，Q，R的命題公式PÙQ的主析取范式是 復(fù)習(xí)主析取范式的定義：定義 對(duì)于給定的命題變?cè)?，如果?/p>

10、一個(gè)等價(jià)公式，它僅僅有小項(xiàng)的析取組成，則該等價(jià)式稱(chēng)為原式的主析取范式而小項(xiàng)的定義是：定義 n個(gè)命題變?cè)暮先∈剑Q(chēng)為布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次由小項(xiàng)的定義知道，命題公式PÙQ中缺少命題變項(xiàng)R與它的否定，因此，應(yīng)該補(bǔ)上，即PÙQÛPÙQÙ (RÚØR) Û(PÙQÙ R) Ú(PÙQÙØR)得到命題公式PÙQ的主析取范式應(yīng)該填寫(xiě)：(PÙQÙR)Ú (PÙQ&

11、#217;ØR)4設(shè)個(gè)體域Da, b,那么謂詞公式消去量詞后的等值式為 因?yàn)樵谟邢迋€(gè)體域下，消除量詞的規(guī)則為：設(shè)Da1, a2, , an，則所以，應(yīng)該填寫(xiě)：(A(a)Ú A(b)Ú (B(a)Ù B(b)應(yīng)該填寫(xiě)：(A(a)Ú A(b)Ú (B(a)Ù B(b)注：如果個(gè)體域是D1, 2，D=a, b, c, 或謂詞公式變?yōu)椋趺醋?5設(shè)個(gè)體域D1, 2, 3，A(x)為“x小于3”，則謂詞公式($x)A(x) 的真值為 因?yàn)?($x)A(x)ÛA(1)ÚA(2)ÚA(3)Û1

12、18;1Ú0Û1應(yīng)該填寫(xiě)：1注：若個(gè)體域D1, 2，A(x)為“x小于3”，則謂詞公式($x)A(x) 的真值是什么？或：設(shè)個(gè)體域D1, 2, 3，A(x)為“x是奇數(shù)”，則謂詞公式($x)A(x) 的真值是什么？6謂詞命題公式("x)(A(x)ÙB(x) ÚC(y)中的自由變?cè)獮?因?yàn)樽杂勺冊(cè)褪遣皇苋魏瘟吭~約束的變?cè)?，在公?"x)(A(x)ÙB(x) ÚC(y)中，y是不受全稱(chēng)量詞"約束的變?cè)詰?yīng)該填寫(xiě)：y應(yīng)該填寫(xiě)：y問(wèn): 公式中的約束變?cè)鞘裁?判斷：謂詞命題公式("x)(A(x)&#

13、217;B(x) ÚC(y)中的自由變?cè)獮閤，是否正確?為什么?三、公式翻譯題 1請(qǐng)將語(yǔ)句“今天是天晴”翻譯成命題公式解：設(shè)P：今天是天晴； 則命題公式為： P 問(wèn)：“今天不是天晴”的命題公式是什么？ 2請(qǐng)將語(yǔ)句“小王去旅游，小李也去旅游”翻譯成命題公式 解：設(shè) P：小王去旅游，Q：小李去旅游， 則命題公式為：P ÙQ 注：語(yǔ)句中包含“也”、“且”、“但”等連接詞，命題公式要用合取“Ù” 3請(qǐng)將語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間”翻譯成命題公式解：設(shè) P：他去旅游，Q：他有時(shí)間， 則命題公式為：P ®Q 注：命題公式的翻譯還要注意“不可兼或”的表示 例如，教材

14、第164頁(yè)的例6 “T2次列車(chē)5點(diǎn)或6點(diǎn)鐘開(kāi)”怎么翻譯成命題公式？這里的“或”為不可兼或 4請(qǐng)將語(yǔ)句“所有人都努力工作”翻譯成謂詞公式 解：設(shè)P(x)：x是人，Q(x)：x努力工作 謂詞公式為： ("x)(P(x)® Q(x)四、判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由） 1命題公式的真值是1解 錯(cuò)誤因?yàn)槭怯兰偈剑ń滩?67頁(yè)的否定律）2命題公式ØP(P®ØQ)P為永真式 解：正確 因?yàn)?，由真值表PQØPØQP®ØQØP(PØQ)P001111011011100111110001可知，該命

15、題公式為永真式注：如果題目改為該命題公式為永假式，如何判斷并說(shuō)明理由？ 3下面的推理是否正確，請(qǐng)給予說(shuō)明 (1) ("x)A(x) Ù B(x) 前提引入(2) A(y) ÙB(y) US (1) 解：錯(cuò)第2步應(yīng)為：A(y) Ù B(x)因?yàn)锳(x)中的x是約束變?cè)?，而B(niǎo)(x)中的x是自由變?cè)瑩Q名時(shí)，約束變?cè)c自由變?cè)荒芑煜逵?jì)算題1求P®QÚR的析取范式，合取范式、主析取范式，主合取范式分析： 定義 對(duì)于給定的命題變?cè)?，如果有一個(gè)等價(jià)公式，它僅僅有大項(xiàng)的合取組成，則該等價(jià)式稱(chēng)為原式的主合取范式 定義 n個(gè)命題變?cè)奈鋈∈剑Q(chēng)為布

16、爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次解 析取范式，合取范式、主析取范式的定義前面復(fù)習(xí)過(guò)了，由教材167的蘊(yùn)含等價(jià)式P®QÚR ÛØPÚQÚR （析取范式、合取范式、主合取范式）Û(ØPÙ(QÚØQ)Ù(RÚØR)Ú(PÚØP)ÙQÙ(RÚØR)Ú(PÚØP)Ù(QÚØQ)ÙR)（

17、補(bǔ)齊命題變項(xiàng)）Û(ØPÙQÙR)Ú(ØPÙQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙØQÙØR)Ú(PÙQÙR)Ú(PÙQÙØR)Ú(ØPÙQÙR)Ú(ØPÙQÙØR)Ú(PÙQÙR)Ú(PÙ

18、ØQÙR)Ú(ØPÙQÙR)Ú(ØPÙØQÙR) （Ù對(duì)Ú的分配律）Û(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙR)Ú(PÙQÙØR)

19、18;(PÙQÙR) （主析取范式）注：如果題目只是求“析取范式”或“合取范式”，大家一定不要再進(jìn)一步求“主析取范式”或“主合取范式” 例如：求（PÚQ）R 或(PÚQ)®(RÚQ)，P®QÙR的合取范式、析取范式2設(shè)謂詞公式（1）試寫(xiě)出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)?（1）量詞的轄域?yàn)?，的轄域?yàn)椋妮犛驗(yàn)椋?）自由變?cè)獮橹械膟，中的z約束變?cè)獮橹械膞，中的z，中的y 3設(shè)個(gè)體域?yàn)镈=a1, a2，求謂詞公式"y$xP(x,y)消去量詞后的等值式解："y$xP(x, y) &

20、#219;($xP(x, a1)Ù($xP(x, a2) Û(P(a1, a1)ÚP(a2, a1)Ù(P(a1, a2)ÚP(a2, a2) 六、證明題 1試證明命題公式 (P®(QÚØR)ÙØPÙQ與Ø（PÚØQ）等價(jià) 證：(P®(QÚØR)ÙØPÙQÛ(ØPÚ(QÚØR)ÙØPÙQ Û(ØP&

21、#218;QÚØR)ÙØP)ÙQ ÛØPÙQ （吸收律） ÛØ(PÚØQ) （摩根律）注意，教材第6章的學(xué)習(xí)指導(dǎo)中的例題要認(rèn)真學(xué)習(xí)，尤其是例5大家一定要重視。2試證明($x)(P(x)ÙR(x)Þ($x)P(x)Ù($x)R(x)分析：前提：($x)(P(x)ÙR(x)， 結(jié)論：($x)P(x)Ù($x)R(x) 證明 (1) ($x)(P(x)ÙR(x) P(2) P(a)ÙR(a) ES(1) (存在指定規(guī)則)(3) P(