離散數學作業(yè)7答案(數理邏輯部分)(共7頁)

1、精選優(yōu)質文檔-傾情為你奉上姓 名： 學 號： 得 分： 教師簽名： 離散數學作業(yè)7離散數學數理邏輯部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內容主要分別是集合論部分、圖論部分、數理邏輯部分的綜合練習，基本上是按照考試的題型（除單項選擇題外）安排練習題目，目的是通過綜合性書面作業(yè)，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點復習，爭取盡快掌握。本次形考書面作業(yè)是第三次作業(yè)，大家要認真及時地完成數理邏輯部分的綜合練習作業(yè)。要求：將此作業(yè)用A4紙打印出來，并在07任務界面下方點擊“保存”和“交卷”按鈕，以便教師評分作業(yè)應手工書寫答題，字跡工整，解答題要有解答過程，完成后上交任課教師

2、（不收電子稿）一、填空題1命題公式的真值是 1 2設P：他生病了，Q：他出差了R：我同意他不參加學習. 則命題“如果他生病或出差了，我就同意他不參加學習”符號化的結果為 PQR 3含有三個命題變項P，Q，R的命題公式PÙQ的主析取范式是 (PÙQÙR) (PÙQÙR) 4設P(x)：x是人，Q(x)：x去上課，則命題“有人去上課” 可符號化為 x ( P ( x) Q ( x) 5設個體域Da, b,那么謂詞公式消去量詞后的等值式為 (A(a) A(b) (B(a) B(b) 6設個體域D1, 2, 3，A(x)為“x大于3”，則謂詞公式($x

3、)A(x) 的真值為 0 7謂詞命題公式("x)(A(x)ÙB(x) ÚC(y)中的自由變元為 y 8謂詞命題公式("x)(P(x) ®Q(x) ÚR(x，y)中的約束變元為 x 三、公式翻譯題 1請將語句“今天是天晴”翻譯成命題公式解：設P：今天是天晴則該語句符號化為 P 2請將語句“小王去旅游，小李也去旅游”翻譯成命題公式 設P：小王去旅游，Q：小李也去旅游則該語句符號化為 PQ 3請將語句“如果明天天下雪，那么我就去滑雪”翻譯成命題公式解：設P：明天天下雪 Q：我就去滑雪則該語句符號化為 PQ 4請將語句“他去旅游，僅當他有時間

4、”翻譯成命題公式解：設P：他去旅游 Q：他有時間則該語句符號化為 PQ 5請將語句 “有人不去工作”翻譯成謂詞公式解：設P(x)：x是人 Q(x)：x不去工作則謂詞公式為 (x)(P(x)Q(x) 6請將語句“所有人都努力工作”翻譯成謂詞公式解：設P(x)：x是人 Q(x)：x努力工作則謂詞公式為 (x)(P(x) Q(x)四、判斷說明題（判斷下列各題，并說明理由） 1命題公式ØPÙP的真值是1不正確，PP的真值是0，它是一個永假式，命題公式中的否定律就是PP=F 2命題公式ØPÙ(P®ØQ)ÚP為永真式 正確可以化簡P（P

5、Q）P=P（PQ）P=PP=1，所以它是永真式當然方法二是用真值表 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下面的推理是否正確，請給予說明(1) ("x)A(x)® B(x) 前提引入(2) A(y) ®B(y) US (1)不正確，(1)中(")x的轄域僅是A(x)，而不是A(

6、x) Ù B(x)四計算題1 求P®QÚR的析取范式，合取范式、主析取范式，主合取范式解：PÚ(QR）= PÚQR所以合取范式和析取范式都是PÚQR所以主合取范式就是PÚQR所以主析取范式就是(ØPÙØQ ÙØR) Ú(ØPÙØQÙ R) Ú (ØPÙQÙ ØR) (ØPÙQ ÙR) Ú(PÙØQÙ R) &

7、#218; (PÙQÙØ R) Ú (PÙQÙ R)2求命題公式(PÚQ)®(RÚQ) 的主析取范式、主合取范式解：(PÚØQ)®(RÙQ)= Ø(PÚØQ) Ú (RÙQ)= (ØPÙQ) Ú (RÙQ)其中(ØPÙQ)= (ØPÙQ) Ù (RÚØR)= (ØPÙQÙ R)

8、Ú(ØPÙQ ÙØR)其中(RÙQ)= (RÙQ) Ù (PÚØP)= (PÙQÙ R) Ú (ØPÙQ Ù R)所以原式=(ØPÙQÙ R) Ú(ØPÙQ ÙØR) Ú (PÙQÙ R) Ú (ØPÙQ Ù R) =(ØPÙQÙ R) Ú(

9、6;PÙQ ÙØR) Ú (PÙQÙ R) = (ØPÙQ ÙØR) Ú(ØPÙQÙ R) Ú (PÙQÙ R)=m2Úm3Úm7這就是主析取范式所以主合取范式為M0Ù M1Ù M4Ù M5Ù M6可寫為(PÚQÚR)Ù (PÚQÚØR) Ù (ØPÚØQÚR

10、) Ù (ØPÚQÚØR) Ù (ØPÚØQÚR)3設謂詞公式（1）試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元解：(1)量詞$x的轄域為 P(x,y) ®("z)Q(y,x,z) 量詞"z的轄域為Q(y,x,z) 量詞"y的轄域為R(y,x)(2) P(x,y)中的x是約束變元，y是自由變元 Q(y,x,z)中的x和z是約束變元，y是自由變元 R(y,x)中的x是自由變元，y是約束變元 4設個體域為D=a1, a2，求謂詞公式"y$x

11、P(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®(QÚØR)ÙØPÙQ與Ø (PÚØQ)等價 證：(P®(QÚØR)ÙØPÙQÛ(ØPÚ(QÚØR)Ù

12、16;PÙQ Û(ØPÚQÚØR)ÙØPÙQ Û(ØPÙØPÙQ)Ú(QÙØPÙQ)Ú(ØRÙØPÙQ) Û(ØPÙQ)Ú(ØPÙQ)Ú(ØPÙQÙØR) ÛØPÙQ （吸收律） ÛØ(PÚØQ) （摩根律）2試證明($x)(P(x) ÙR