謂詞邏輯習題及答案.doc

謂詞邏輯習題1. 將下列命題用謂詞符號化。（1）小王學過英語和法語。（2）2大于3僅當2大于4。（3）3不是偶數(shù)。（4）2或3是質(zhì)數(shù)。（5）除非李鍵是東北人，否則他一定怕冷。解： (1) 令：x學過英語，Q(x)：x學過法語，c：小王，命題符號化為(2) 令：x大于y, 命題符號化為(3) 令：x是偶數(shù)，命題符號化為(4) 令：x是質(zhì)數(shù)，命題符號化為(5) 令：x是北方人；：x怕冷；：李鍵；命題符號化為2. 設個體域，消去下列各式的量詞。（1）（2）（3）（4）解：(1) 中，顯然對y是自由的，故可使用UE規(guī)則，得到 ，因此，再用ES規(guī)則， ，所以（2）中，它對y不是自由的，故不能用UI規(guī)則，然而，對中約束變元y改名z，得到，這時用UI規(guī)則，可得： （3）略（4）略3. 設謂詞表示“等于”，個體變元和的個體域都是。求下列各式的真值。（1）（2）（3）（4）（5）（6）解：(2) 當時可使式子成立，所以為Ture。(3) 當時就不成立，所以為False。 (4) 任意的x,y使得，顯然有的情況出現(xiàn)，所以為False。(4)存在x,y使得，顯然當時是一種情況，所以為Ture。 (5)存在x，任意的y使得成立，顯然不成立，所以為False。 (6)任意的y ，存在x ，使得成立，顯然不成立，所以為False。4. 令謂詞表示“說德語”，表示“了解計算機語言C+”，個體域為杭電全體學生的集合。用、量詞和邏輯聯(lián)接詞符號化下列語句。（1）杭電有個學生既會說德語又了解C+。（2）杭電有個學生會說德語，但不了解C+。（3）杭電所有學生或會說德語，或了解C+。（4）杭電沒有學生會說德語或了解C+。假設個體域為全總個體域，謂詞表示“是杭電學生”。用、量詞和邏輯聯(lián)接詞再次符號化上面的4條語句。解：（）個體域為杭電全體學生的集合時：（1）（2）（3）（4） （）假設個體域為全總個體域，謂詞表示“是杭電學生”時：（1）（2）（3）（4）5. 令謂詞表示“愛”，其中和的個體域都是全世界所有人的集合。用、量詞和邏輯聯(lián)接詞符號化下列語句。（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）（4）（5）（6）（7）解：（1）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （2）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （3）易知公式是的代換實例，而 是永假式，所以公式是永假式。 （4）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （5）易知公式是的代換實例，而 是永真式，所以公式是永真式。 （6）易知公式是的代換實例，而 是永假式，所以公式是永假式。 （7）易知公式是的代換實例，而 是可滿足式，所以公式是可滿足式。2.3 謂詞公式的等價演算與范式習題2.31. 將下列命題符號化，要求用兩種不同的等價形式。（1）沒有小于負數(shù)的正數(shù)。（2）相等的兩個角未必都是對頂角。解：（1）：x為負數(shù)，：x是正數(shù)，：x小于y，命題可符號化為：或 （2）略2.設、和都是謂詞，證明下列各等價式（1）（2）（3）（4）證明：（1）左邊右邊 （2）左邊 右邊 （3）左邊 右邊 （4）左邊 右邊3. 求下列謂詞公式的前束析取范式和前束合取范式。（1）（2）（3）（4）解：（1） 前束析取范式 前束合取范式（2）原式前束析取范式 前束合取范式（3）原式 前束析取范式 前束合取范式（4）原式 2.4 謂詞公式的推理演算習題2.41.證明：證明：（1）左邊 2. 指出下面演繹推理中的錯誤，并給出正確的推導過程。（1） P規(guī)則US規(guī)則：（2） P規(guī)則US規(guī)則：（3） P規(guī)則ES規(guī)則：（4） P規(guī)則 UG規(guī)則：（5） P規(guī)則 EG規(guī)則：（6） P規(guī)則 EG規(guī)則：解：（1）錯，使用US,UG,ES,EG規(guī)則應對前束范式，而中公式不是前束范式，所以不能用US規(guī)則。 (2)錯，中公式為，這時，因而使用US規(guī)則時，應得A(a)(或A(y),故應有，而不能為。3.用演繹法證明下列推理式證明： 前提引入 ES 前提引入 T US T T EG 4. 將下列命題符號化，并用演繹推理法證明其結(jié)論是有效的。（1）有理數(shù)、無理數(shù)都是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無理數(shù)。（個體域取全總個體域）（2）所有的舞蹈者都很有風度；萬英是個學生并且是個舞蹈者。因此，有些學生很有風度。（個體域取人類全體組成的集合）（3）每個喜歡步行的人都不喜歡騎自行車；每個人或者喜歡騎自行車或者喜歡乘汽車；有的人不喜歡乘汽車。所以有的人不喜歡步行。（個體域取人類全體組成的集合）（4）每個旅客或者坐頭等艙或者坐經(jīng)濟艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐經(jīng)濟艙。（個體域取全體旅客組成的集合）解：(2)證明：設P(x)：x 是個舞蹈者； Q(x) ：x很有風度； S(x)：x是個學生； a：王華上述句子符號化為：前提：、 結(jié)論： （1）P（2）P（3）US（2）（4）T（1）I （5）T（3）（4）I（6）T（1）I（7）T（5）（6）I（8）EG（7）（3）命題符號化為：F(x)：x喜歡步行,G(x)：x喜歡騎自行車，H(x)：x喜歡坐汽車。 前提：， 結(jié)論：. 證明：(1) P (2) ES(1) (3) P (4) US(3) (5) T(2)(4) I (6) P(7) US(6)(8) T(5)(7) I (9) EG(8)（4）命題符號化為：F(x)：x坐頭等艙, G(x)：x坐經(jīng)濟艙，H(x)：x富裕。 前提：， 結(jié)論：. 證明：(1) P (2) ES(1) (3) P (4) US(3) (5) T(2)(4)I (6) P(7) US(6)(8) T(5)(7)I(9) EG(8)5. 令謂詞、和分別表示“是嬰兒”，表示“的行為符合邏輯”、“能管理鱷魚”和“被人輕視”，個體域為所有人的集合。用、量詞和邏輯聯(lián)接詞符號化下列語句。（1）嬰兒行為不合邏輯。（2）能管理鱷魚的人不被人輕視。（3）行為不合邏輯的人被人輕視。（4）嬰兒不能管理鱷魚。請問，能從（1）、（2）和（3）推出（4）嗎？若不能，