1、姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 離散數(shù)學(xué)作業(yè)7離散數(shù)學(xué)數(shù)理邏輯部分形成性考核書(shū)面作業(yè)本課程形成性考核書(shū)面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過(guò)綜合性書(shū)面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握。本次形考書(shū)面作業(yè)是第三次作業(yè)，大家要認(rèn)真及時(shí)地完成數(shù)理邏輯部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來(lái)，并在07任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評(píng)分作業(yè)應(yīng)手工書(shū)寫(xiě)答題，字跡工整，解答題要有解答過(guò)程，完成后上交任課教師（不收電子稿）要求：將此作

2、業(yè)用A4紙打印出來(lái)，手工書(shū)寫(xiě)答題，字跡工整，解答題要有解答過(guò)程，要求2010年12月19日前完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評(píng)分。一、填空題1命題公式的真值是 1 2設(shè)P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號(hào)化的結(jié)果為 PQR 3含有三個(gè)命題變項(xiàng)P，Q，R的命題公式PQ的主析取范式是 (PQR) (PQR) 4設(shè)P(x)：x是人，Q(x)：x去上課，則命題“有人去上課” 可符號(hào)化為 x ( P ( x) Q ( x) 5設(shè)個(gè)體域Da, b,那么謂詞公式消去量詞后的等值式為

3、 (A(a) A(b) (B(a) B(b) 6設(shè)個(gè)體域D1, 2, 3，A(x)為“x大于3”，則謂詞公式($x)A(x) 的真值為 0 7謂詞命題公式(x)(A(x)B(x) C(y)中的自由變?cè)獮?y 8謂詞命題公式(x)(P(x) Q(x) R(x，y)中的約束變?cè)獮?x 三、公式翻譯題 1請(qǐng)將語(yǔ)句“今天是天晴”翻譯成命題公式解：設(shè)P：今天是天晴則該語(yǔ)句符號(hào)化為 P 2請(qǐng)將語(yǔ)句“小王去旅游，小李也去旅游”翻譯成命題公式 設(shè)P：小王去旅游，Q：小李也去旅游則該語(yǔ)句符號(hào)化為 PQ 3請(qǐng)將語(yǔ)句“如果明天天下雪，那么我就去滑雪”翻譯成命題公式解：設(shè)P：明天天下雪 Q：我就去滑雪則該語(yǔ)句符號(hào)化為

4、 PQ 4請(qǐng)將語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間”翻譯成命題公式解：設(shè)P：他去旅游 Q：他有時(shí)間則該語(yǔ)句符號(hào)化為 PQ 5請(qǐng)將語(yǔ)句 “有人不去工作”翻譯成謂詞公式解：設(shè)P(x)：x是人 Q(x)：x不去工作則謂詞公式為 (x)(P(x)Q(x) 6請(qǐng)將語(yǔ)句“所有人都努力工作”翻譯成謂詞公式解：設(shè)P(x)：x是人 Q(x)：x努力工作則謂詞公式為 (x)(P(x) Q(x)四、判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由） 1命題公式PP的真值是1不正確，PP的真值是0，它是一個(gè)永假式，命題公式中的否定律就是PP=F 2命題公式P(PQ)P為永真式 正確可以化簡(jiǎn)P（PQ）P=P（PQ）P=PP=1，所以它是永

5、真式當(dāng)然方法二是用真值表 3謂詞公式是永真式正確xP(x) (yG(x,y) xP(x)=xP(x) (yG(x,y) xP(x)=xP(x) (y(G(x,y) xP(x)=xP(x) (y(G(x,y) xP(x)=xP(x) y(G(x,y) xP(x)=xP(x) xP(x) y(G(x,y)=1y(G(x,y)=1所以該式是永真式 4下面的推理是否正確，請(qǐng)給予說(shuō)明(1) (x)A(x) B(x) 前提引入(2) A(y) B(y) US (1)不正確，(1)中()x的轄域僅是A(x)，而不是A(x) B(x)四計(jì)算題1 求PQR的析取范式，合取范式、主析取范式，主合取范式解：P(QR

6、）= PQR所以合取范式和析取范式都是PQR所以主合取范式就是PQR所以主析取范式就是(PQ R) (PQ R) (PQ R) (PQ R) (PQ R) (PQ R) (PQ R)2求命題公式(PQ)(RQ) 的主析取范式、主合取范式解：(PQ)(RQ)= (PQ) (RQ)= (PQ) (RQ)其中(PQ)= (PQ) (RR)= (PQ R) (PQ R)其中(RQ)= (RQ) (PP)= (PQ R) (PQ R)所以原式=(PQ R) (PQ R) (PQ R) (PQ R) =(PQ R) (PQ R) (PQ R) = (PQ R) (PQ R) (PQ R)=m2m3m7這就

7、是主析取范式所以主合取范式為M0 M1 M4 M5 M6可寫(xiě)為(PQR) (PQR) (PQR) (PQR) (PQR)3設(shè)謂詞公式（1）試寫(xiě)出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)猓?1)量詞$x的轄域?yàn)?P(x,y) (z)Q(y,x,z) 量詞z的轄域?yàn)镼(y,x,z) 量詞y的轄域?yàn)镽(y,x)(2) P(x,y)中的x是約束變?cè)瑈是自由變?cè)?Q(y,x,z)中的x和z是約束變?cè)瑈是自由變?cè)?R(y,x)中的x是自由變?cè)?，y是約束變?cè)?4設(shè)個(gè)體域?yàn)镈=a1, a2，求謂詞公式y(tǒng)$xP(x,y)消去量詞后的等值式；解： y$xP(x,y)= $xP(x, a1) $xP(x, a2)=( P(a1, a1) P(a2, a1) ( P(a1, a2) P(a1, a2)五、證明題 1試證明 (P(QR)PQ與 (PQ)等價(jià) 證：(P(QR)PQ(P(QR)PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律）2試證明($x)(P(x) R(x)($x)P(x) ($x)R(x)證明： (1) ($x