離散數(shù)學(xué)屈婉玲版課后答案

3習(xí)題一 1.1 略 1.2 略 1.3 略 1.4 略 1.5 略 1.6 略 1.7 略 1.8 略 1.9 略 1.10 1.11 1.12 略 略 將下列 命題符號(hào)化, 并給出各命題的 真值: (1)2+24當(dāng)且僅當(dāng)3+36. (2)2+24的充要條件是3+36. (3)2+24與3+36互為充要條件. (4)若2+24, 則3+36, 反之亦然. (1)pq, 其中, p: 2+24, q: 3+36, 真值為1. (2)pq, 其中, p: 2+24, q: 3+36, 真值為0. (3) pq, 其中, p: 2+24, q: 3+36, 真值為0. (4) pq, 其中, p: 2+24, q: 3+36, 真值為1. 將下列命題符號(hào)化, 并給出各命題的真值: (1)若今天是星期一, 則明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一當(dāng)且僅當(dāng)明天是星期二. (4)若今天是星期一, 則明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) pq 1. (2) qp 1. (3) pq 1. (4) pr當(dāng)p 0時(shí)為真; p 1 時(shí)為假. 將下列 命題符號(hào)化. (1) 劉曉月跑得快, 跳得高. (2)老王是山東人或河北人. (3)因?yàn)樘鞖饫? 所以我穿了羽絨服. (4)王歡與李樂(lè)組成一個(gè)小組. (5)李辛與李末是兄弟. (6)王強(qiáng)與劉威都學(xué)過(guò)法語(yǔ). (7)他一面吃飯, 一面聽(tīng)音樂(lè). (8)如果天下大雨, 他就乘班車上班. (9)只有天下大雨, 他才乘班車上班. (10)除非天下大雨, 他才乘班車上班. (11)下雪路滑, 他遲到了. (12)2與4都是素?cái)?shù), 這是不對(duì)的. (13)“2或4是素?cái)?shù), 這是不對(duì)的”是不對(duì)的. 4 (1)pq, 其中, p: 劉曉月跑得快, q: 劉曉月跳得高. (2)pq, 其中, p: 老王是山東人, q: 老王是河北人. (3)pq, 其中, p: 天氣冷, q: 我穿了羽絨服. (4)p, 其中, p: 王歡與李樂(lè)組成一個(gè)小組, 是簡(jiǎn)單命題. (5)p, 其中, p: 李辛與李末是兄弟. (6)pq, 其中, p: 王強(qiáng)學(xué)過(guò)法語(yǔ), q: 劉威學(xué)過(guò)法語(yǔ). (7)pq, 其中, p: 他吃飯, q: 他聽(tīng)音樂(lè). (8)pq, 其中, p: 天下大雨, q: 他乘班車上班. (9)pq, 其中, p: 他乘班車上班, q: 天下大雨. (10)pq, 其中, p: 他乘班車上班, q: 天下大雨. (11)pq, 其中, p: 下雪路滑, q: 他遲到了. (12) (pq)或pq, 其中, p: 2是素?cái)?shù), q: 4是素?cái)?shù). (13) (pq)或pq, 其中, p: 2是素?cái)?shù), q: 4是素?cái)?shù). 設(shè)p: 2+3=5. q: 大熊貓產(chǎn)在中國(guó). r: 復(fù)旦大學(xué)在廣州. 求下列復(fù)合命題的真值: (1)(pq) r (2)(r (pq) p (3) r (pqr) (4)(pqr) ( pq) r) (1)真值為0. (2)真值為0. (3)真值為0. (4)真值為1. 注意: p, q是真命題, r是假命題. 1.16 1.17 1.18 1.19 略 略 略 用真值表判斷下列公式的類型: (1)p (pqr) (2)(pq) q (3) (qr) r (4)(pq) (qp) (5)(pr) ( pq) (6)(pq) (qr) (pr) (7)(pq) (rs) 5 (1), (4), (6)為重言式. (3)為矛盾式. (2), (5), (7)為可滿足式. 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 略 略 略 略 略 略 略 略 略 略 略 將下列 命題符號(hào)化, 并給出各命題的 真值: (1)若3+4, 則地球是靜止不動(dòng)的. (2)若3+24, 則地球是運(yùn)動(dòng)不止的. (3)若地球上沒(méi)有樹(shù)木, 則人類不能生存. (4)若地球上沒(méi)有水, 則3是無(wú)理數(shù). (1)pq, 其中, p: 2+24, q: 地球靜止不動(dòng), 真值為0. (2)pq, 其中, p: 2+24, q: 地球運(yùn)動(dòng)不止, 真值為1. (3) pq, 其中, p: 地球上有樹(shù)木, q: 人類能生存, 真值為1. (4) pq, 其中, p: 地球上有水, q: 3是無(wú)理數(shù), 真值為1. 6 習(xí)題二 2.1. 設(shè)公式 A = pq, B = pq, 用真值表驗(yàn)證公式 A 和 B 適合德摩根律: (AB) AB. A =pq B =pq (AB) AB0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 因?yàn)?AB)和AB的真值表相同, 所以它們等值. 2.2. 略 2.3. 用等值演算法判斷下列公式的類型, 對(duì)不是重言式的可滿足式, 再用真值表法求出成真賦值. (1) (pqq) (2)(p (pq) (pr) (3)(pq) (pr) (1) (pqq) (pq) q) (p q q) pqq p0 0 0. 矛盾式. (2)重言式. (3) (pq) (pr) (pq) (pr) pq pr易見(jiàn), 是可滿足式, 但不是重言式. 成真賦值為: 000, 001, 101, 111 p q pr1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 2.4. 用等值演算法證明下面等值式: (1) p (pq) (pq) (3) (pq) (pq) (pq) (4) (pq) (pq) (pq) (pq) (1) (pq) (pq) p (qq) p 1 p. (3) (pq) p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 7 (pq) (qp) (pq) (qp) (pq) (qp) (pq) (pp) (qq) (pq) (pq) (pq) (4) (pq) (pq) (pp) (pq) (qp) (qq) (pq) (pq) 2.5. 求下列公式的主析取范式, 并求成真賦值: (1)( pq) (qp) (2) (pq) qr (3)(p (qr) (pqr) (1)(pq) (qp) (pq) (qp) pq q p pq q p(吸收律) (pp)q p(qq) pq pq pq pq m10 m00 m11 m10 m0 m2 m3 (0, 2, 3). 成真賦值為 00, 10, 11. (2)主析取范式為0, 無(wú)成真賦值, 為矛盾式. (3)m0m1m2m3m4m5m6m7 , 為重言式. 2.6. 求下列公式的主合取范式, 并求成假賦值: (1) (qp) p (2)(pq) (pr) (3)(p (pq) r (1) (qp) p (qp) p qp p q0 0 M0M1M2M3 這是矛盾式. 成假賦值為 00, 01, 10, 11. (2)M4 , 成假賦值為100. (3)主合取范式為1, 為重言式. 82.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(pq) r (2)(pq) (qr) (1)m1m3m5m6m7M0M2M4 (2)m0m1m3m7M2M4M5M6 2.8. 略 2.9. 用真值表求下面公式的主析取范式. (2) (pq) (pq) (2)從真值表可見(jiàn)成真賦值為01, 10. 于是(p q) (p q) m1 m2 . 2.10. 略 2.11. 略 2.12. 略 2.13. 略 2.14. 略 2.15. 用主析取范式判斷下列公式是否等值: (1) (pq) r與q (pr) (2)(pq) r (pq) r (pq) r pq r pq(rr) (pp) (qq)r pqr pqr pqr pqr pqr pqr = m101 m100 m111 m101 m011 m001 m1 m3 m4 m5 m7 = (1, 3, 4, 5, 7). 而 q(pr) q (pr) q p r (pp)q(rr) p(qq)(rr) (pp)(qq)r (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)(pqr) p q ( p q ) ( p q ) 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 9(pqr)(pqr)(pqr)(pqr) = m0 m1 m4 m5 m0 m1 m2 m3 m1 m3 m5 m7 m0 m1 m2 m3 m4 m5 m7 (0, 1, 2, 3, 4, 5, 7). 兩個(gè)公式的主吸取范式不同, 所以(pq) r2.16. 用主析取范式判斷下列公式是否等值: (1)(pq) r與q (pr) (2) (pq)與 (pq) (1) (pq) r) m1m3m4m5m7 q (pr) m0m1m2m3m4m5m7 所以(pq) r) q (pr) (2) (pq) m0m1m2 (pq) m0 所以 (pq) (pq) 2.17. 用主合取范式判斷下列公式是否等值: (1)p (qr)與 (pq) r (2)p (qr)與(pq) r (1) p (qr) M6 (pq) rM6 所以p (qr) (pq) r (2) p (qr) M6 (pq) rM0M1M2M6 所以p (qr) (pq) r 2.18. 略 2.19. 略 q (pr). 2.20. 將下列公式化成與之等值且僅含 , 中聯(lián)結(jié)詞的公式. (3) (pq)r. 注意到AB (AB)(BA)和 AB (AB) (AB)以及 AB AB. (pq)r 10 (pq r) (r pq) (pq) r) (r (pq) (pq) r) (r (pq) 注聯(lián)結(jié)詞越少, 公式越長(zhǎng). 2.21. 證明: (1) (pq) (qp), (pq) (qp). (pq) (pq) (qp) (qp). (pq) (pq) (qp) (qp). 2.22. 略 2.23. 略 2.24. 略 2.25. 設(shè)A, B, C為任意的命題公式. (1)若ACBC, 舉例說(shuō)明 AB不一定成立. (2)已知ACBC, 舉例說(shuō)明AB不一定成立. (3)已知AB, 問(wèn): AB一定成立嗎? (1) 取 A = p, B = q, C = 1 (重言式), 有 AC BC, 但 A B. (2) 取 A = p, B = q, C = 0 (矛盾式), 有 AC BC, 但 A B. 好的例子是簡(jiǎn)單, 具體, 而又說(shuō)明問(wèn)題的. (3)一定. 2.26. 略 2.27. 某電路中有一個(gè)燈泡和三個(gè)開(kāi)關(guān)A,B,C. 已知在且僅在下述四種情況下燈亮: (1)C的扳鍵向上, A,B的扳鍵向下. (2)A的扳鍵向上, B,C的扳鍵向下. (3)B,C的扳鍵向上, A的扳鍵向下. (4)A,B的扳鍵向上, C的扳鍵向下. 設(shè)F為1表示燈亮, p,q,r分別表示A,B,C的扳鍵向上. (a)求F的主析取范式. (b)在聯(lián)結(jié)詞完備集, 上構(gòu)造F. (c)在聯(lián)結(jié)詞完備集, ,上構(gòu)造F. (a)由條件(1)-(4)可知, F的主析取范式為 F (pqr) (pqr) (pqr) (pqr) m1m4m3m6 m1m3m4m6 11 (b)先化簡(jiǎn)公式 F (pqr) (pqr) (pqr) (pqr) q (pr) (pr) q (pr) (pr) (qq) (pr) (pr) (pr) (pr) ( (pr) (pr) (已為, 中公式) (c) F (pr) (pr) (pr) (pr) (pr) (pr) (pr) (pr) (rp) (pr) (已為, ,中公式) 2.28. 一個(gè)排隊(duì)線路, 輸入為A,B,C, 其輸出分別為F A,F B,F C. 本線路中, 在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過(guò), 若同時(shí)有兩個(gè)和兩個(gè)以上信號(hào)申請(qǐng)輸出時(shí), 則按A,B,C的順序輸出. 寫(xiě)出F A,F B,F C在聯(lián)結(jié)詞完備集, 中的表達(dá)式. 根據(jù)題目中的要求, 先寫(xiě)出F A,F B,F C的真值表(自己寫(xiě)) 由真值表可先求出他們的主析取范式, 然后化成, 中的公式 F Am4m5m6m7 p F Bm2m3 pq F Cm1 pqr 2.29. 略 2.30. 略 (已為, 中公式) (已為, 中公式) (已為, 中公式) 12 習(xí)題三 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判斷下面推理是否正確. 先將簡(jiǎn)單命題符號(hào)化, 再寫(xiě)出前提, 結(jié)論, 推理的形式結(jié)構(gòu)(以蘊(yùn)涵式的形式給 出)和判斷過(guò)程(至少給出兩種判斷方法): (1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 則明天是星期二或星期三. (6)今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三. 設(shè)p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式結(jié)構(gòu)為 (pr) pr 此形式結(jié)構(gòu)為重言式, 即 (pr) pr 所以推理正確. (2)推理的形式結(jié)構(gòu)為 (pq) qp 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (3)推理形式結(jié)構(gòu)為 (pr) rp 此形式結(jié)構(gòu)為重言式, 即 (pr) rp 故推理正確. (4)推理形式結(jié)構(gòu)為 (pq) pq 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (5)推理形式結(jié)構(gòu)為 p (qr) 它不是重言式, 故推理不正確. (6)推理形式結(jié)構(gòu)為 (pr) pr 13此形式結(jié)構(gòu)為重言式, 即 (pr) pr 故推理正確. 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構(gòu)造證明法. 下面用構(gòu)造證明法證明(6)推理正確. 前提: pr, p 結(jié)論: r 證明: pr (pr) (rp) rp p r 所以, 推理正確. 3.7. 略 3.8. 略 前提引入 置換 化簡(jiǎn)律 前提引入 拒取式 3.9. 用三種方法(真值表法, 等值演算法, 主析取范式法)證明下面推理是正確的: 若 a 是奇數(shù), 則 a 不能被2 整除. 若 a 是偶數(shù), 則 a 能被 2 整除. 因此, 如果 a 是偶數(shù), 則 a 不是奇數(shù). 令 p: a 是奇數(shù); q: a 能被2 整除; r: a 是偶數(shù). 前提: p q, r q. 結(jié)論: r p. 形式結(jié)構(gòu): (p q) (r q) (r p). 3.10.略 3.11.略 3.12.略 3.13.略 3.14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: (1)前提: p (qr), p, q 結(jié)論: rs (2)前提: pq, (qr), r 結(jié)論: p (3)前提: pq 結(jié)論: p (pq) (4)前提: qp, qs, st, tr 結(jié)論: pq (5)前提: pr, qs, pq 14 結(jié)論: rs (6)前提: pr, qs, pq 結(jié)論: t (rs) (1)證明: p(qr) p qr q r rs (2)證明: (qr) qr r q pq p (3)證明: pq pq 前提引入 假言推理 前提引入 假言推理 附加律 前提引入 置換 前提引入 析取三段論 前提引入 拒取式 前提引入 置換 (pq) (pp) p (pq) p (pq) 也可以用附加前提證明法, 更簡(jiǎn)單些. (4)證明: st (st) (ts) ts tr t s qs (sq) (qs) sq q 化簡(jiǎn) 假言推理 前提引入 置換 化簡(jiǎn) 假言推理 15q p 12 p pq 13 (5)證明: pr 前提引入 qs 前提引入 pq 前提引入 化簡(jiǎn) p 化簡(jiǎn) q 假言推理 11合取 12 r s rs (6)證明: t pr pq p r rs 假言推理 假言推理 合取 附加前提引入 前提引入 前提引入 化簡(jiǎn) 析取三段論 附加 說(shuō)明: 證明中, 附加提前t, 前提qs沒(méi)用上. 這仍是正確的推理. 3.15.在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1)前提: p (qr), sp, q 結(jié)論: sr (2)前提: (pq) (rs), (st) u 結(jié)論: pu (1)證明: s sp p p (qr) qr q r 附加前提引入 前提引入 假言推理 前提引入 假言推理 前提引入 假言推理 16 (2)證明: P pq (pq) (rs) rs S st (st) u u 附加前提引入 附加 前提引入 假言推理 化簡(jiǎn) 附加 前提引入 假言推理 3.16.在自然推理系統(tǒng)P中用歸謬法證明下面推理: (1)前提: pq, rq, rs 結(jié)論: p (2)前提: pq, pr, qs 結(jié)論: rs (1)證明: P pq q rq r rs r rr 結(jié)論否定引入 前提引入 假言推理 前提引入 析取三段論 前提引入 化簡(jiǎn) 合取 為矛盾式, 由歸謬法可知, 推理正確. (2)證明: (rs) pq pr qs rs (rs) (rs) 17 為矛盾式, 所以推理正確. 3.17.P53 17. 在自然推理系統(tǒng) P 中構(gòu)造下面推理的證明: 只要 A 曾到過(guò)受害者房間并且11點(diǎn)以前沒(méi)用離開(kāi), A 就犯了謀殺罪. A 曾到過(guò)受害者房間. 如果 A 在11點(diǎn)以前離開(kāi), 看門人會(huì)看到他. 看門人沒(méi)有看到他. 所以 A 犯了謀殺罪. 令 p: A 曾到過(guò)受害者房間; q: A 在11點(diǎn)以前離開(kāi)了; r: A 就犯了謀殺罪; s:看門人看到 A. 前提: pq r, p, q s, s. 結(jié)論: r. 前提: pq r, p, q s, s; 證明: s 前提引入 q s 前提引入 q 拒取 前提引入 p pq 合取 pq r 前提引入 r 假言推理 結(jié)論: r. 3.18.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明. (1)如果今天是星期六, 我們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六. 頤和園游人太多. 所以我們?nèi)A明園玩. (2)如果小王是理科學(xué)生, 他的數(shù)學(xué)成績(jī)一定很好. 如果小王不是文科生, 他必是理科生. 小王的數(shù)學(xué)成 績(jī)不好. 所以小王是文科學(xué)生. (3)明天是晴天, 或是雨天；若明天是晴天, 我就去看電影；若我看電影, 我就不看書(shū). 所以, 如果我看書(shū), 則明天是雨天. (1)令 p: 今天是星期六; q: 我們要到頤和園玩; r: 我們要到圓明園玩; s:頤和園游人太多. 前提: p (qr), s q, p, s. 結(jié)論: r. p pqr qr s s q q r 前提引入 pqr s q ps 前提引入 qr q 假言推理 前提引入 r前提引入 (1)的證明樹(shù) 假言推理 析取三段論 18 (2) 令p: 小王是理科生, q: 小王是文科生, r: 小王的數(shù)學(xué)成績(jī)很好. 前提: pr, qp, r 結(jié)論: q 證明: pr qr 前提引入 p 拒取式 p qp 前提引入 (2)的證明樹(shù) 拒取式 q (3)令p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書(shū). 前提: pq, pr, rs 結(jié)論: sq 證明: 附加前提引入 s rs 前提引入 r 拒取式 pr 前提引入 p 拒取式 pq 前提引入 析取三段論 q pq rpr19 習(xí)題四 4.1. 將下面命題用0元謂詞符號(hào)化: (1)小王學(xué)過(guò)英語(yǔ)和法語(yǔ). (2)除非李建是東北人, 否則他一定怕冷. (1) 令 F(x): x 學(xué)過(guò)英語(yǔ); F(x): x 學(xué)過(guò)法語(yǔ); a: 小王. 符號(hào)化為 F(a)F(b). 或進(jìn)一步細(xì)分, 令 L(x, y): x 學(xué)過(guò) y; a: 小王; b1 : 英語(yǔ); b2 : 法語(yǔ). 則符號(hào)化為 L(a, b1 )L(a, b2 ). (2) 令 F(x): x 是東北人; G(x): x 怕冷; a: 李建. 符號(hào)化為 F(a)G(a) 或 G(a)F(a). 或進(jìn)一步細(xì)分, 令 H(x, y): x 是 y 地方人; G(x): x 怕冷; a: 小王; b: 東北. 則符號(hào)化為 H(a, b)G(a) 或 G(a) H(a, b). 4.2. 在一階邏輯中將下面命題符號(hào)化, 并分別討論個(gè)體域限制為(a),(b)時(shí)命題的真值: (1)凡有理數(shù)都能被2整除. (2)有的有理數(shù)能被2整除. 其中(a)個(gè)體域?yàn)橛欣頂?shù)集合, (b)個(gè)體域?yàn)閷?shí)數(shù)集合. (1)(a)中, xF(x), 其中, F(x): x能被2整除, 真值為0. (b)中, x(G(x) F(x), 其中, G(x): x為有理數(shù), F(x)同(a)中, 真值為0. (2)(a)中, xF(x), 其中, F(x): x能被2整除, 真值為1. (b)中, x(G(x) F(x), 其中, F(x)同(a)中, G(x): x為有理數(shù), 真值為1. 4.3. 在一階邏輯中將下面命題符號(hào)化, 并分別討論個(gè)體域限制為(a),(b)時(shí)命題的真值: (1)對(duì)于任意的x, 均有x22=(x+ 2 )(x2 ). (2)存在x, 使得x+5=9. 其中(a)個(gè)體域?yàn)樽匀粩?shù)集合, (b)個(gè)體域?yàn)閷?shí)數(shù)集合. (1)(a)中, x(x22=(x+ 2 )(x2 ), 真值為1. (b)中, x(F(x) (x22=(x+ 2 )(x2 ), 其中, F(x): x為實(shí)數(shù), 真值為1. (2)(a)中, x(x+5=9), 真值為1. (b)中, x(F(x) (x+5=9), 其中, F(x): x為實(shí)數(shù), 真值為1. 4.4. 在一階邏輯中將下列命題符號(hào)化: (1)沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù). (2)在北京賣菜的人不全是外地人. 20 (3)烏鴉都是黑色的. (4)有的人天天鍛煉身體. 沒(méi)指定個(gè)體域, 因而使用全總個(gè)體域. (1) x(F(x) G(x)或x(F(x) G(x), 其中, F(x): x為有理數(shù), G(x): x能表示成分?jǐn)?shù). (2) x(F(x) G(x)或x(F(x) G(x), 其中, F(x): x在北京賣菜, G(x): x是外地人. (3) x(F(x) G(x), 其中, F(x): x是烏鴉, G(x): x是黑色的. (4) x(F(x) G(x), 其中, F(x): x是人, G(x): x天天鍛煉身體. 4.5. 在一階邏輯中將下列命題符號(hào)化: (1)火車都比輪船快. (2)有的火車比有的汽車快. (3)不存在比所有火車都快的汽車. (4)“凡是汽車就比火車慢”是不對(duì)的. 因?yàn)闆](méi)指明個(gè)體域, 因而使用全總個(gè)體域 (1) xy(F(x) G(y) H(x,y), 其中, F(x): x是火車, G(y): y是輪船, H(x,y):x比y快. (2) xy(F(x) G(y) H(x,y), 其中, F(x): x是火車, G(y): y是汽車, H(x,y):x比y快. (3) x(F(x) y(G(y) H(x,y) 或x(F(x) y(G(y) H(x,y), 其中, F(x): x是汽車, G(y): y是火車, H(x,y):x比y快. (4) xy(F(x) G(y) H(x,y) 或xy(F(x) G(y) H(x,y) ), 其中, F(x): x是汽車, G(y): y是火車, H(x,y):x比y慢. 4.6. 略 4.7. 將下列各公式翻譯成自然語(yǔ)言, 個(gè)體域?yàn)檎麛?shù)集 , 并判斷各命題的真假. (1) xyz(x y = z); (2) xy(xy = 1). (1) 可選的翻譯: “任意兩個(gè)整數(shù)的差是整數(shù).” “對(duì)于任意兩個(gè)整數(shù), 都存在第三個(gè)整數(shù), 它等于這兩個(gè)整數(shù)相減.” “對(duì)于任意整數(shù) x 和 y, 都存在整數(shù) z, 使得 x y = z.” 選, 直接翻譯, 無(wú)需數(shù)理邏輯以外的知識(shí). 以下翻譯意思相同, 都是錯(cuò)的: “有個(gè)整數(shù), 它是任意兩個(gè)整數(shù)的差.” “存在一個(gè)整數(shù), 對(duì)于任意兩個(gè)整數(shù), 第一個(gè)整數(shù)都等于這兩個(gè)整數(shù)相減.” “存在整數(shù) z, 使得對(duì)于任意整數(shù) x 和 y, 都有 x y = z.” 這3個(gè)句子都可以符號(hào)化為 zxy(x y = z). 量詞順序不可隨意調(diào)換. (2) 可選的翻譯: 21 “每個(gè)整數(shù)都有一個(gè)倒數(shù).” “對(duì)于每個(gè)整數(shù), 都能找到另一個(gè)整數(shù), 它們相乘結(jié)果是零.” “對(duì)于任意整數(shù) x, 都存在整數(shù) y, 使得 xy = z.” 選, 是直接翻譯, 無(wú)需數(shù)理邏輯以外的知識(shí). 4.8. 指出下列公式中的指導(dǎo)變?cè)? 量詞的轄域, 各個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn): (3)xy(F(x, y) G(y, z) xH(x, y, z) xy(F(x, y) G(y, z) ) x H(x, y, z) 前件 xy(F(x, y)G(y, z) 中, 的指導(dǎo)變?cè)?x, 的轄域是 y(F(x, y)G(y, z); 的指導(dǎo)變?cè)?y, 的轄域 是 (F(x, y)G(y, z). 后件 xH(x, y, z) 中, 的指導(dǎo)變?cè)?x, 的轄域是 H(x, y, z). 整個(gè)公式中, x 約束出現(xiàn)兩次, y 約束出現(xiàn)兩次, 自由出現(xiàn)一次; z 自由出現(xiàn)兩次. 4.9. 給定解釋I如下: (a)個(gè)體域D I為實(shí)數(shù)集合. (b)D I中特定元素a =0. (c)特定函數(shù)f (x,y)=xy, x,yD I. (d)特定謂詞F(x,y): x=y,G(x,y): x<y, x,yD I. 說(shuō)明下列公式在I下的含義, 并指出各公式的真值: (1) xy(G(x,y) F(x,y) (2) xy(F(f(x,y),a) G(x,y) (3) xy(G(x,y) F(f(x,y),a) (4) xy(G(f(x,y),a) F(x,y) (1) xy(x<yxy), 真值為1. (2) xy(xy=0) x<y), 真值為0. (3) xy(x<y) (xy0), 真值為1. (4) xy(xy<0) (x=y), 真值為0. 4.10.給定解釋I如下: (a)個(gè)體域D=(為自然數(shù)). (b)D中特定元素a=2. (c)D上函數(shù)f (x,y)=x+y,g (x,y)=xy. (d)D上謂詞F (x,y): x=y. 說(shuō)明下列公式在I下的含義, 并指出各公式的真值: (1) xF(g(x,a),x) (2) xy(F(f(x,a),y) F(f(y,a),x) (3) xyz(F(f(x,y),z) (4) xF(f(x,x),g(x,x) 22 (1) x(x2=x), 真值為0. (2) xy(x+2=y) (y+2=x), 真值為0. (3) xyz(x+y=z),真值為1. (4) x(x+x=xx),真值為1. 4.11.判斷下列各式的類型: (1) F(x, y) (G(x, y) F(x, y). (3) xyF(x, y) xyF(x, y). (5) xy(F(x, y) F(y, x). (1) 是命題重言式 p (q p) 的代換實(shí)例, 所以是永真式. (3) 在某些解釋下為假(舉例), 在某些解釋下為真(舉例), 所以是非永真式的可滿足式. (5) 同(3). 4.12.P69 12. 設(shè) I 為一個(gè)任意的解釋, 在解釋 I 下, 下面哪些公式一定是命題? (1) xF(x, y) yG(x, y). (2) x(F(x) G(x) y(F( y) H( y). (3) x(yF(x, y) yG(x, y). (4) x(F(x) G(x) H( y). (2), (3) 一定是命題, 因?yàn)樗鼈兪情]式. 4.13.略 4.14.證明下面公式既不是永真式也不是矛盾式: (1) x(F(x) y(G(y) H(x,y) (2) xy(F(x) G(y) H(x,y) (1) 取個(gè)體域?yàn)槿倐€(gè)體域. 解釋I1 : F(x): x為有理數(shù), G(y): y為整數(shù), H(x,y): x<y 在I1下: x(F(x) y(G(y) H(x,y)為真命題, 所以該公式不是矛盾式. 解釋I2 : F(x),G(y)同I1 , H(x,y): y整除x. 在I2下: x(F(x) y(G(y) H(x,y)為假命題, 所以該公式不是永真式. (2) 請(qǐng)讀者給出不同解釋, 使其分別為成真和成假的命題即可. 4.15.(1) 給出一個(gè)非閉式的永真式. (2) 給出一個(gè)非閉式的永假式. (3) 給出一個(gè)非閉式的可滿足式, 但不是永真式. (1) F(x) F(x). (2) F(x) F(x). (3) x(F(x, y) F(y, x). 23習(xí)題五 5.1. 略 5.2. 設(shè)個(gè)體域D=a,b,c, 消去下列各式的量詞: (1) xy(F(x) G(y) (2) xy(F(x) G(y) (3) xF(x) yG(y) (4) x(F(x,y) yG(y) (1) xy(F(x) G(y) xF(x) yG(y) (F(a) F(b) F(c) (G(a) G(b) G(c) (2) xy(F(x) G(y) xF(x) yG(y) (F(a) F(b) F(c) (G(a) G(b) G(c) (3) xF(x) yG(y) (F(a) F(b) F(c) (G(a) G(b) G(c) (4) x(F(x,y) yG(y) xF(x,y) yG(y) (F(a,y) F(b,y) F(c,y) (G(a) G(b) G(c) 5.3. 設(shè)個(gè)體域D=1,2, 請(qǐng)給出兩種不同的解釋I1和I2 , 使得下面公式在I1下都是真命題, 而在I2下都是假 命題. (1) x(F(x) G(x) (2) x(F(x) G(x) (1)I1 : F(x):x2,G(x):x3 F(1),F(2),G(1),G(2)均為真, 所以 x(F(x) G(x) (F(1) G(1) (F(2) G(2)為真. I2 : F(x)同I1 ,G(x):x0 則F(1),F(2)均為真, 而G(1),G(2)均為假, x(F(x) G(x)為假. (2)留給讀者自己做. 5.4. 略 5.5. 給定解釋I如下: (a) 個(gè)體域D=3,4. (b)f (x)為f (3)=4,f (4)=3. (c)F(x,y)為F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1. 24試求下列公式在I下的真值: (1) xyF(x,y) (2) xyF(x,y) (3) xy(F(x,y) F(f(x),f(y) (1) xyF(x,y) (F(3,3) F(3,4) (F(4,3) F(4,4) (01) (10) 1 (2) xyF(x,y) (F(3,3) F(3,4) (F(4,3) F(4,4) (01) (10) 0 (3) xy(F(x,y) F(f(x),f(y) (F(3,3) F(f(3),f(3) (F(4,3) F(f(4),f(3) (F(3,4) F(f(3),f(4) (F(4,4) F(f(4),f(4) (00) (11) (11) (00) 1 5.6. 略 5.7. 略 5.8. 在一階邏輯中將下列命題符號(hào)化, 要求用兩種不同的等值形式. (1) 沒(méi)有小于負(fù)數(shù)的正數(shù). (2) 相等的兩個(gè)角未必都是對(duì)頂角. (1) 令 F(x): x 小于負(fù)數(shù), G(x): x 是正數(shù). 符合化為: x(F(x) G(x) x(G(x) G(x). (2) 令 F(x): x 是角, H(x, y): x 和 y 是相等的, L(x, y): x 與 y 是對(duì)頂角. 符合化為: xy(F(x) F(y) H(x, y) L(x, y) xy(F(x) F(y) H(x, y) L(x, y) x(F(x) (y(F(y) H(x, y) L(x, y). 5.9. 略 5.10.略 5.11.略 5.12.求下列各式的前束范式. (1) xF(x) yG(x, y); (3) xF(x, y) xG(x, y); (5) x1F(x1 , x2 ) (F(x1 ) x2G(x1 , x2 ). 前束范式不是唯一的. (1) xF(x) yG(x, y) x(F(x) yG(x, y) 25 xy(F(x) G(x, y). (3) xF(x, y) xG(x, y) (xF(x, y) xG(x, y) (xG(x, y) xF(x, y) (x1F(x1 , y) x2G(x2 , y) (x3G(x3 , y)