離散數(shù)學(xué)(劉任任版)第14章答案.ppt

離散數(shù)學(xué) 習(xí)題解答 1 2 指出下列命題的真值 3 在一階邏輯中 將下列命題符號(hào)化 1 凡有理數(shù)均可表示為分?jǐn)?shù) 解 P x x是有理數(shù) Q x x可表示為分?jǐn)?shù) 在謂詞邏輯中基本語(yǔ)句的形式化 1 D中所有x都有性質(zhì)F 2 D中有的x具有性質(zhì)F 3 D中所有x而言 如果x有性質(zhì)F 則x就有性質(zhì)G 4 D中有的x具有性質(zhì)F 又有性質(zhì)G 設(shè)D是論域 5 對(duì)于D中的所有x和y而言 若x有性質(zhì)F y有性質(zhì)G 則x與y有關(guān)系H 6 對(duì)于D中的所有x而言 若x有性質(zhì)F 就存在y有性質(zhì)G 并且x與y有關(guān)系H 7 存在D中的x有性質(zhì)F 并且對(duì)D中所有y而言 如果y有性質(zhì)G 則x與y就有關(guān)系H 8 D中存在著x與y x有性質(zhì)F y有性質(zhì)G 并且x與y有關(guān)系H 解 自由變?cè)獄 約束為元 x y 第一個(gè)的作用域?yàn)?2 第二個(gè)的作用域?yàn)榈诙€(gè)P x 第二個(gè)的作用域的作用域?yàn)镼 y 3 解 自由變?cè)獄 約束為元 x y 的作用域?yàn)镽 y 解 無(wú)自由變?cè)?約束為元 x y 4 的作用域?yàn)?的作用域?yàn)?H x y 5 解 自由變?cè)?y與G x y 中的x 約束變?cè)?F x 中的x 解 自由變?cè)?Z與H x y 中的y 約束變?cè)?x y 的作用域 F x 6 和 的作用域 的作用域 5 設(shè)謂詞公式 判定以下改名是否正確 1 2 3 4 5 錯(cuò)誤 正確 錯(cuò)誤 錯(cuò)誤 錯(cuò)誤 6 1 解 真 2 解 假 3 解 真 4 解 真 7 判斷下列公式的恒真性和恒假性 1 解 恒真 2 解 恒真 3 解 恒真 4 解 恒假 5 解 滿足 8 1 2 證明 1 證明 2 9 證 設(shè)D是論域 I是G x y 的一個(gè)解釋 a 若 1 在I下的為真 則在I下 對(duì)任意的 即 是真命題 b 若 在I下的為假 則在I下 必存在 使得G x0 y 或G x y0 為假 于是 此xo或yo亦弄假 證 設(shè)D是論域 I是G x y 的一個(gè)解釋 2 a 若 也是真命題 反之亦然 在I下的為真 則在I下 有 使G x0 y0 為真命題 于是 3 解 4 解 11 給出下面公式的skolem范式 1 所求為 解 原式 2 即為所求 3 解 12 假設(shè)是公式G的前束范式 其中M x y 是僅僅包含變量x y的母式 設(shè)f是不出現(xiàn)在M x y 中的函數(shù)符號(hào) 證明 G恒真當(dāng)且僅當(dāng)恒真 證 設(shè)恒真 若不真 則存在一個(gè)解釋I 使得對(duì)任意的 論域 為假 于是 G在I下也為假 此為矛盾 反之 設(shè)恒真 若不是恒真 則存在一個(gè)解釋I 使得對(duì)任意 存在 使為假 由于f是不出現(xiàn)在中的函數(shù)符號(hào) 故可定義函數(shù) 使得 于是 在I 下為假 矛盾 故結(jié)論成立 證明 1 2 3 4 5 6 前提引入 13 證明 假言推理 2 4 UG 5 US 1 前提引入 US 3 前提 結(jié)論 證明 1 2 等值替換 1 3 4 5 6 前提引入 14 構(gòu)造下面推理的證明 US 5 假言推理 2 4 等值替換 2 US 3 解 4 錯(cuò)誤 F y 中的變?cè)獃與 2 中的變?cè)孛?15 指出下面兩個(gè)推理的錯(cuò)誤 1 6 5 G y 假言推理 2 4 3 2 UG 5 前提引入 US 1 前提引入 4 F y ES 3 解 3 錯(cuò)誤 在 2 中還有自由變?cè)獃 1 5 3 2 EG 4 前提引入 US 1 4 ES 2 US 3 在推理過(guò)程中 指出下面各證明序列中的錯(cuò)誤 F c G c 1 F x 2 F y G y F c G c 3 前提引入 EG規(guī)則 前提引入 ES規(guī)則 前提引入 ES規(guī)則 4 F c G b 5 F c G c 前提引入 前提引入 UG規(guī)則 EG規(guī)則 16 每個(gè)學(xué)術(shù)會(huì)的成員都是知識(shí)分子并且是專家 有些成員是青年人 證明 有的成員是青年專家 解 P x x是學(xué)術(shù)會(huì)的成員 E x x是專家 G x x是知識(shí)分子 Y x x是青年人 前提 結(jié)論 前提 結(jié)論 1 前提引入 2 US 1 3 4 5 P c 6 7 E c 8 Y c 9 10 前提引入 ES 3 化簡(jiǎn) 4 假言推理 2 5 化簡(jiǎn) 6 化簡(jiǎn) 4 合并 7 8 EG 9