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

《離散數(shù)學(劉任任版)第14章答案.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學(劉任任版)第14章答案.ppt（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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