應用離散數學 謂詞邏輯第2章：謂詞邏輯2.1 個體詞、謂詞與量詞習題2.11. 將下列命題用0元謂詞符號化。（1）小王學過英語和法語。（2）2大于3僅當2大于4。（3）3不是偶數。（4）2或3是質數。（5）除非李鍵是東北人，否則他一定怕冷。解： (1) 令：x學過英語，Q(x)：x學過法語，c：小王，命題符號化為(2) 令：x大于y, 命題符號化為(3) 令：x是偶數，命題符號化為(4) 令：x是質數，命題符號化為(5) 令：x是北方人；：x怕冷；：李鍵；命題符號化為2. 設個體域，消去下列各式的量詞。（1）（2）（3）（4）解：(1) 中，顯然對y是自由的，故可使用UE規則，得到 ，因此，再用ES規則， ，所以（2）中，它對y不是自由的，故不能用UI規則，然而，對中約束變元y改名z，得到，這時用UI規則，可得： （3）略（4）略3. 設謂詞表示“等于”，個體變元和的個體域都是。求下列各式的真值。（1）（2）（3）（4）（5）（6）解：（1） 當時可使式子成立，所以為Ture。（2） 當時就不成立，所以為False。 （3） 任意的x,y使得，顯然有的情況出現，所以為False。(4)存在x,y使得，顯然當時是一種情況，所以為Ture。 (5)存在x，任意的y使得成立，顯然不成立，所以為False。 (6)任意的y ，存在x ，使得成立，顯然不成立，所以為False。4. 設下面所有的個體變元的個體域都是整數集合，用自然語言表達下列各式并確定其真值。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）解：(1) 任意的整數n使得成立。因為是永真式，所以其值為Ture。 (2) 存在這樣的整數n使得成立。因為不存在整數使得成立，所以其值為 False 。 (3) 任意的整數n使得成立。因為n是整數，所以恒成立，所以其值為Ture。(4) 任意的整數n，存在m使得成立。只要就能使式子恒成立，所以其值為Ture。 (5) 任意的整數m，存在n使得成立。只要就能使式子恒成立，所以其值為Ture。 (6) 任意的整數n，存在m使得成立。只要就能使式子恒成立，所以其值為Ture。 (7) 任意的整數m，存在n使得成立。只要就能使式子恒成立，所以其值為Ture。 (8) 存在這樣的整數n，m使得成立。顯然存在這樣的整數m,n，當時即可使式子成立，所以其值為Ture。 (9) 存在這樣的整數n，m使得成立，通過分析可知不存在這樣的m,n,所以其值為False。(10) 任意的整數m，存在n使得同時成立，只要，任意的n都不能使式子成立，所以其值為False 。 (11) 任意的整數m，存在n使得同時成立，只要，任意的n都不能使式子成立，所以其值為False 。 (12) 任意的整數m,n，存在整數k使得成立，因為只要m,n一個為偶數，另一個為奇數，就使得k為非整數，所以其值為False。5. 令謂詞表示“訪問過”，其中的個體域是學校全體學生，的個體域是所有網站的集合。用自然語言表達下列各式。（1）。（2）。（3）。（4）。（5）。（6）。解：（1）方華已經訪問過。 （2）至少有一人已經訪問過。 （3）馮友已經至少訪問過一個網站了。 （4）至少友一個網站是吳笛和錢華都訪問過的。 （5）除了黃帥以外還有一個人訪問過黃帥已經訪問過的所有網站。 （6）有兩個不同的人已經訪問過完全同樣的網站。6. 令謂詞表示“說德語”，表示“了解計算機語言C+”，個體域為杭電全體學生的集合。用、量詞和邏輯聯接詞符號化下列語句。（1）杭電有個學生既會說德語又了解C+。（2）杭電有個學生會說德語，但不了解C+。（3）杭電所有學生或會說德語，或了解C+。（4）杭電沒有學生會說德語或了解C+。假設個體域為全總個體域，謂詞表示“是杭電學生”。用、量詞和邏輯聯接詞再次符號化上面的4條語句。解：（）個體域為杭電全體學生的集合時：（1）（2）（3）（4） （）假設個體域為全總個體域，謂詞表示“是杭電學生”時：（1）（2）（3）（4）7. 令謂詞表示“愛”，其中和的個體域都是全世界所有人的集合。用、量詞和邏輯聯接詞符號化下列語句。（1）每個人都愛王平。（2）每個人都愛某個人。（3）有個人人都愛的人。（4）沒有人愛所有的人。（5）有個張鍵不愛的人。（6）有個人人都不愛的人。（7）恰有一個人人都愛的人。（8）成龍愛的人恰有兩個。（9）每個人都愛自己。（10）有人除自己以外誰都不愛。解：王平 ：張鍵 ：張龍(1) (2)(3) (4)(5) (6)(7)(8)(9) (10)8. 令謂詞表示“給發過電子郵件”，表示“給打過電話”，其中和的個體域都是實驗班所有同學。用、量詞和邏輯聯接詞符號化下列語句。（1）周葉從未給李強發過電子郵件。（2）方芳從未給萬華發過電子郵件，或打過電話。（3）實驗班每個同學都給余濤發過電子郵件。（4）實驗班沒有人給呂鍵打過電話。（5）實驗班每個人或給肖琴打過電話或給他發過電子郵件。（6）實驗班有個學生給班上其他人都發過電子郵件。（7）實驗班有個學生給班上其他人或打過電話，或發過電子郵件。（8）實驗班有兩個學生互發過電子郵件。（9）實驗班有個學生給自己發過電子郵件。（10）實驗班至少有兩個學生，一個給另一個發過電子郵件，而另一個給這個打過電話。解： ：周葉 ：李強 ：方芳 ：萬華 ：余濤 呂健 肖琴（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）2.2 謂詞公式及其解釋習題2.21. 指出下列謂詞公式的指導變元、量詞轄域、約束變元和自由變元。（1）（2）（3）解： （1）x是指導變元，的轄域是，對于的轄域而言，x是約束變元，y是自由變元。（2）x,y都為指導變元，的轄域是，的轄域是；對于的轄域而言，x,y都為約束變元，對于的轄域而言，x是自由變元，y是約束變元。（3）x,y為指導變元，的轄域是，的轄域是，的轄域是；對于的轄域而言，x,y為約束變元，z為自由變元，對于的轄域而言，z為自由變元，y為約束變元，x即為約束變元也為自由變元，對于的轄域而言，x為約束變元，y,z是自由變元。在整個公式中，x,y即為約束變元又為自由變元，z為自由變元。2. 設個體域，請給出兩種不同的解釋和，使得下面謂詞公式在下都是真命題，而在下都是假命題。（1）（2）解：解釋：個體域，。 解釋：個體域，。3. 對下面的謂詞公式，分別給出一個使其為真和為假的解釋。（1）（2）解： （1）成真解釋：個體域D1,2,3,其中i,j 是D中的元素。 成假解釋：個體域D1,2,3,，其中i,j 是D中的元素。 （2）成真解釋：個體域D1,2,3，其中i,j 是D中的元素。 成假解釋：個體域D1,2,3,，其中i,j 是D中的元素。4. 給定解釋如下：個體域（這里為實數集合）。個體常元。二元函數。二元謂詞，。在解釋下，下列公式的含義是什么？哪些成為命題哪些不成為？成為命題的其真值又如何？（1）（2） （3）（4）解：（1）公式被解釋成“”，為真命題。 （2）公式被解釋成“”，它沒有確切的真值，不是命題。（3）公式被解釋成“”，為真命題。（4）公式被解釋成“”，它沒有確切的真值，不是命題。5. 判斷下列謂詞公式哪些是永真式，哪些是永假式，哪些是可滿足式，并說明理由。（1） （2）（3） （4）（5）（6）（7）（8）（9）（10）解：（1）易知公式是 的代換實例，而 是永真式，所以公式為永真式。 （2）6. 判斷下列謂詞公式哪些是永真式，哪些是永假式，哪些是可滿足式，并說明理由。（1）（2）（3）（4）（5）（6）（7）解：（1）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （2）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （3）易知公式是的代換實例，而 是永假式，所以公式是永假式。 （4）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （5）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （6）易知公式是的代換實例，而 是永假式，所以公式是永假式。 （7）易知公式是的代換實例，而 是可滿足式，所以公式是可滿足式。7. 給出一個非閉式的永真式，給出一個非閉式的永假式，給出一個非閉式的可滿足式。2.3 謂詞公式的等價演算與范式習題2.31. 將下列命題符號化，要求用兩種不同的等價形式。（1）沒有小于負數的正數。（2）相等的兩個角未必都是對頂角。解：（1）：x為負數，：x是正數，：x小于y，命題可符號化為：或 （2）略2. 利用非形式化方法證明下列等價式。（1）（2）（3）（4）（5）證明：（5）在任意解釋I下，不妨設個體域為D。 1）當時，則，使得，所以，因而所以 2）當時，則，都有，所以，因而，所以3.設、和都是謂詞，證明下列各等價式（1）（2）（3）（4）證明：（1）左邊右邊 （2）左邊 右邊 （3）左邊 右邊 （4）左邊 右邊4. 求下列謂詞公式的前束析取范式和前束合取范式。（1）（2）（3）（4）解：（1） 前束析取范式 前束合取范式（2）原式前束析取范式 前束合取范式（3）原式 前束析取范式 前束合取范式（4）原式 5. 將下列命題符號化，要求符號化的公式為前束范式。（1）有的汽車比有的火車跑的快。（2）有的火車比所有的汽車跑的快。（3）說“所有的火車比所有的汽車都跑的快”是不對的。（4）說“有的飛機比有的汽車慢”是不對的。2.4 謂詞公式的推理演算習題2.41. 利用非形式化證明方法或等價演算法證明如下推理關系：（1）（2）（3）（4）（5）（6）證明：（1）左邊 2. 指出下面演繹推理中的錯誤，并給出正確的推導過程。（1） P規則US規則：（2） P規則US規則：（3） P規則ES規則：（4） P規則 UG規則：（5） P規則 EG規則：（6） P規則 EG規則：解：（1）錯，使用US,UG,ES,EG規則應對前束范式，而中公式不是前束范式，所以不能用US規則。 (2)錯，中公式為，這時，因而使用US規則時，應得A(a)(或A(y),故應有，而不能為。3. 指出下面演繹推理中的錯誤，并給出正確的推導過程。（1） P規則（2）US規則：（1）（3） ES規則：（2）（4）UG規則：（3）（5）US規則：（4）4. 指出下面演繹推理中的錯誤，并給出正確的推導過程。（1） P規則（2） US規則：（1）（3）P規則（4）ES規則：（3）（5）T規則：（2），（4）（6）EG規則：（5）5. 用演繹法證明下列推理式（1）（2）（3）（4）6. 用演繹法證明下列推理式（1）（2）（3）（4）證明：（1） 前提引入 ES 前提引入 T US T T EG7. 將下列命題符號化，并用演繹推理法證明其結論是有效的。（1）有理數、無理數都是實數；虛數不是實數。因此，虛數既不是有理數，也不是無理數。（個體域取全總個體域）（2）所有的舞蹈者都很有風度；萬英是個學生并且是個舞蹈者。因此，有些學生很有風度。（個體域取人類全體組成的集合）（3）每個喜歡步行的人都不喜歡騎自行車；每個人或者喜歡騎自行車或者喜歡乘汽車；有的人不喜歡乘汽車。所以有的人不喜歡步行。（個體域取人類全體組成的集合）（4）每個旅客或者坐頭等艙或者坐經濟艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐經濟艙。（個體域取全體旅客組成的集合）解：（3）命題符號化為：F(x)：x喜歡步行,G(x)：x喜歡騎自行車，H(x)：x喜歡坐汽車。 前提：， 結論：. 證明： 前提引入 ES 前提引入 US 析取三斷論 前提引入 US 拒取式 EG（4）命題符號化為：F(x)：x坐頭等艙, G(x)：x坐經濟艙，H(x)：x富裕。 前提：， 結論：. 證明： 前提引入 ES 前提引入 US T 前提引入 US T EG8. 令謂詞、和分別表示“是教授”，“無知”和“愛虛榮”，個體域為所有人的集合。用、量詞和邏輯聯接詞符號化下列語句。（1）沒有無知的教授。（2）所有無知者均愛虛榮。（3）沒有愛虛榮的教授。請問，能從（1）和（2）推出（3）嗎？若不能，請寫出（1）和（2）的一個有效結論，并用演繹推理法證明之。解：（1） （2） （3） 得不出結論，也許有愛虛榮的教授，因為前提并不排除在無知者之外還有愛虛榮的人。9. 令謂詞、和分別表示“是嬰兒”，表示“的行為符合邏輯”、“能管理鱷魚”和“被人輕視”，