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

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

2、B是正確的正確答案：B問：如果把“我將去打球”改成“我將去學(xué)習(xí)”、“我將去旅游”等，怎么符號化呢？2命題公式PÚQ的合取范式是 ( )APÙQ B（PÙQ）Ú（PÚQ）CPÚQ DØ（ØPÙØQ）復(fù)習(xí)合取范式的定義：定義 一個命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式： A1A2An ， （n1）其中A1，A2，An均是由命題變元或其否定所組成的析取式由此可知，選項B和D是錯的又因為PÙQ 與PÚQ不是等價的，選項A是錯的所以，選項C是正確的正確答案：C 3命題公式的析取范式是

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

4、#174;Q CQ®P Þ P DØPÙ(PÚQ)ÞQ 因為： ØPÙ(PÚQ)ÞQ（析取三段論，P171公式(10)） 所以，選項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頁中的蘊含等價式，得 (P®(ØQ®P) ÛØPÚ(QÚ P)，(ØP®(P®Q) Û PÚ (ØPÚQ) 所以，C是重言式，也就是永真式正確答案：C說明：如果題目改為“下列公式 ( )為永真式”，應(yīng)該是一樣的6設(shè)A（x）：x是人，B（x）：x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號化為（ ）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)該用全稱量詞的否定，即Ø"x，得到公式C正確答案：C7設(shè)A（x）：x是人，B（x）：x是工人，則命題“有人是工人”可符號化為（ ）A($x)(A(x)ÙB(x) B("x)(A(x)ÙB(x)CØ("x)(A(x)®B(x) DØ($x)(A(x)ÙØB(x) 選項A中的A(x)ÙB(x)表示x

7、是人，而且是工人，$x 表示存在一個人，有一個人，因此($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) 所謂轄域是指“緊接于量詞之后最小的子公式稱為量詞的轄域”那么看題中緊接于量詞"x之后最小的子公式是什么呢？顯然是P(x, y)ÚQ(z)，因此，選項B是正確的正確答案：B注：如果該題改為判斷題，即 表達(dá)式中的轄域是P(x, y)如何判斷并說明理由呢？9在謂詞公式("x)(A(x)B(x)ÚC

8、(x，y)中，（ ）Ax，y都是約束變元 Bx，y都是自由變元 Cx是約束變元，y都是自由變元 Dx是自由變元，y都是約束變元 約束變元就是受相應(yīng)的量詞約束的變元而自由變元就是不受任何量詞約束的變元所以選項C是正確的正確答案：C注：如果該題改為填寫約束變元或自由變元的填空題，大家也應(yīng)該掌握補充題：設(shè)個體域為自然數(shù)集合，下列公式中是真命題的為 ( )A B C D因為選項A表示：對任一自然數(shù)x存在自然數(shù)y滿足xy=1，這樣的y是不存在的 選項B表示：對任一自然數(shù)x存在自然數(shù)y滿足x+y=0，這樣的y也是不存在的 選項C表示：存在一自然數(shù)x自然數(shù)對任意自然數(shù)y滿足xy=x，取x=0即可，故選項C正

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

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

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

12、18;1Ú0Û1應(yīng)該填寫：1注：若個體域D1, 2，A(x)為“x小于3”，則謂詞公式($x)A(x) 的真值是什么？或：設(shè)個體域D1, 2, 3，A(x)為“x是奇數(shù)”，則謂詞公式($x)A(x) 的真值是什么？6謂詞命題公式("x)(A(x)ÙB(x) ÚC(y)中的自由變元為 因為自由變元就是不受任何量詞約束的變元，在公式("x)(A(x)ÙB(x) ÚC(y)中，y是不受全稱量詞"約束的變元所以應(yīng)該填寫：y應(yīng)該填寫：y問: 公式中的約束變元是什么?判斷：謂詞命題公式("x)(A(x)&#

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

14、第164頁的例6 “T2次列車5點或6點鐘開”怎么翻譯成命題公式？這里的“或”為不可兼或 4請將語句“所有人都努力工作”翻譯成謂詞公式 解：設(shè)P(x)：x是人，Q(x)：x努力工作 謂詞公式為： ("x)(P(x)® Q(x)四、判斷說明題（判斷下列各題，并說明理由） 1命題公式的真值是1解 錯誤因為是永假式（教材167頁的否定律）2命題公式ØP(P®ØQ)P為永真式 解：正確 因為，由真值表PQØPØQP®ØQØP(PØQ)P001111011011100111110001可知，該命

15、題公式為永真式注：如果題目改為該命題公式為永假式，如何判斷并說明理由？ 3下面的推理是否正確，請給予說明 (1) ("x)A(x) Ù B(x) 前提引入(2) A(y) ÙB(y) US (1) 解：錯第2步應(yīng)為：A(y) Ù B(x)因為A(x)中的x是約束變元，而B(x)中的x是自由變元，換名時，約束變元與自由變元不能混淆五計算題1求P®QÚR的析取范式，合取范式、主析取范式，主合取范式分析： 定義 對于給定的命題變元，如果有一個等價公式，它僅僅有大項的合取組成，則該等價式稱為原式的主合取范式 定義 n個命題變元的析取式，稱為布

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

17、補齊命題變項）Û(Ø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) （Ù對Ú的分配律）Û(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙR)Ú(PÙQÙØR)

19、18;(PÙQÙR) （主析取范式）注：如果題目只是求“析取范式”或“合取范式”，大家一定不要再進一步求“主析取范式”或“主合取范式” 例如：求（PÚQ）R 或(PÚQ)®(RÚQ)，P®QÙR的合取范式、析取范式2設(shè)謂詞公式（1）試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元解 （1）量詞的轄域為，的轄域為，的轄域為（2）自由變元為中的y，中的z約束變元為中的x，中的z，中的y 3設(shè)個體域為D=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）等價 證：(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(