《數(shù)理邏輯》期末考試試題

1、(A卷)()中山大學授予學士學位工作細則 考試作弊不授予學士學位。年級：2008級班級：A,B,C,E班(共202分)1. 設(shè)A是含命題變量p q rA(p q)2. 設(shè)公式A含變量p q rM M M Mr)的類型是矛盾式。m。mmm23514673. 設(shè)F(x)表x是實數(shù)G(x)表x是有理數(shù)”，則命題“實數(shù)不都是有理數(shù)”符號化為x(F(x)G(x)。4. 公式xF(x)yG(x y)的前束范式是xy(F(x)G(z y)。5.6. 設(shè)F(x)xG(x)x x(F(x)G(x)7. 設(shè)p r為真命題，q s(p8. 求與公式F = x(A(x) B(x y)xtz(A(x) B(x y) (

2、C(t)D(y z)9. 令L(x)表示x是人，E(x)表示x是食物，F(xiàn)(x y)表示x對y公式(pq)r的主析取范式是m m m m m13567。q) (rs)的真值為0。(yC(y) zD(y z)等值的一個前束范式是：。xy(L(x)E(y)F(x y)。10. 公式(yG(x)xF(x)yG(y)xF(x)的類型是永真式。(8分)(1) 請指出公式x(P(x)xQ(x)(xH(x) G(x)中各量詞的轄域；解答：第一個量詞x的轄域是(P(x)(x)Q(x)x的轄域是Q(x)，第二個量詞x的轄域是P(x。(2) 請給出公式y(tǒng)(A(x y)xB(x y) zC(x y z)中每個變量符號

3、的出現(xiàn)身份，即是指導變元、還是自由出現(xiàn)或約束出現(xiàn)。解答y中的y是指導變元，A(x y)中的y是約束出現(xiàn)，而x是自由出現(xiàn)，x中的x是指導變元，而B(x y)中的x和y都是約束出現(xiàn)，z中的zC(x y z)中的zx和y都是自由出現(xiàn)。(3) 請指出變量x和y分別是公式x(A(x y)變量；B(y z)yxC(x y z)的自由變量還是約束解答xy是該公式的自由變量。(4) 請使用約束變量改名規(guī)則或自由變量替換規(guī)則將公式x(A(x y)yB(y z)yC(x y z)變換成語法等價但所有量詞的指導變元不同，且沒有變量符號既自由出現(xiàn)又約束出現(xiàn)的公式形式。注意，請依次選擇個體變量符號x y z u v w

4、 r s t等等。解答x(A(x y)uB(u z)vC(w v z)(16分)1(1) 給定解釋I = 2 4P(x)為真當且僅當x是素數(shù)，D(x y)為真當且僅當x可整除yE(x y)為真當且僅當x+y = xyxy(P(x)D(x y)E(x y)在解釋I下的真值。解答1.(2) 給定解釋I fE(x y)的解釋是x = y，請給出公式xyE(f(x y) y)的直觀含義，并根據(jù)常識確定其真值。解答：該公式的直觀含義是：存在一個整數(shù)和任意另一整數(shù)的和都等于另一整數(shù)，其真值為1，因為對任意的整數(shù)xx+0 = 。(3) 給定論域 = a bxy(P(x y)P(y x)中的量詞。解答：xy(

5、P(x y)P(y x)P(y a)y(P(b y) y(P(a y)P(y b) (P(a a)(P(b a)P(a a)(P(a b)P(a b)(P(b b)P(b a) P(b b)(4) 利用一階邏輯的基本等值式證明x(F(x)G(x) (xG(x)xF(x)；證明(xG(x)xF(x) (xG(x)xF(x) xG(x)xF(x)/ 蘊涵等值式/ 德摩根律 xG(x)xF(x)/ 量詞否定等值式/ 量詞分配等值式 x(F(x)G(x)四、求解下面有關(guān)一階邏輯公式自然推理的題目。注意下列題目中必須寫出詳細的證明序列，并注明所使用的自然推理規(guī)則。(38分)(1) 待驗證的推理是：x(A

6、(x)B(x) xA(x)xB(x)，請指出下面證明序列中的錯誤，(6分)(1) x(A(x)B(x)B(a)/ 前提引入(2) A(a)/ (1)全稱量詞消除/ 附加前提引入(3) xA(x)(4) A(a)/ (3)存在量詞消除/ (2),(4)蘊涵消除/ (5)存在量詞引入/ (3),(6)附加前提證明法(5) B(a)(6) xB(x)(7) xA(x)xB(x)解答(3)步到第(4)步使用存在量詞消除規(guī)則錯誤，常量符號a已經(jīng)在前面的證明序列出2現(xiàn)過，正確的證明序列如下：(1) xA(x)(2) A(a)/ 附加前提引入/ (1)存在量詞消除/ 前提引入(3) x(A(x)B(x)B(

7、a)(4) A(a)/ (3)全稱量詞消除/ (2),(4)蘊涵消除/ (5)存在量詞引入/ (3),(6)附加前提證明法(5) B(a)(6) xB(x)(7) xA(x)xB(x)(2) 在一階邏輯中驗證推理：(10分)xP(x) x(P(x)Q(x)R(x) xP(x) xQ(x) xy(R(x)R(y)證明(1) xP(x)(2) xP(x)x(P(x)Q(x)R(x)/ 前提引入/ 前提引入(3) x(P(x)Q(x)(4) P(a)R(x)/ (1),(2)蘊涵消除/ (2)存在量詞消除/ 附加律(5) P(a)Q(a)(6) P(a)Q(a)(7) R(a)R(a)/ (3)全稱

8、量詞消除/ (5),(6)蘊涵消除/ 前提引入(8) xQ(x)(9) Q(b)/ (8)存在量詞消除/ 附加律(10) P(b)Q(b)(11) P(b)Q(b)(12) R(b)R(b)/ (3)全稱量詞消除/ (10),(11)蘊涵消除/ (7),(12)合取引入/ (13)存在量詞引入/ (14)存在量詞引入(13) R(a)R(b)(14) y(R(a)R(y)(15) xy(R(x)R(y)(3) 在一階邏輯中驗證推理：x(C(x)D(x) x(B(x)C(x) x(D(x)B(x)(10分)3證明(1) x(C(x)D(x)D(y)/ 前提引入(2) C(y)/ (1)全稱量詞消

9、除/ 前提引入(3) x(B(x)C(x)(4) B(y)C(y)(5) D(y)/ (3)全稱量詞消除/ 附加前提引入/ (2),(5)拒取式(6) C(y)(7) B(y)/ (4),(6)析取三段論/ (5),(7)附加前提證明法/ (8)全稱量詞引入(8) D(y)B(y)B(x)(9) x(D(x)(4) 符號化下面的推理，并在一階邏輯中驗證其正確性：每一個自然數(shù)不是奇數(shù)就是偶數(shù)，自然數(shù)是偶數(shù)當且僅當它能被2整除，并不是所有的自然數(shù)都能被2整除，因此有的自然數(shù)是奇數(shù)。（提示：令個體域是自然數(shù)集合，Q(x)表示x是奇數(shù)，P(x)表示x是偶數(shù)，R(x)表示x能被2整除）(12分)證明 首

10、先將前提和結(jié)論進行符號化，得到要驗證的推理是：x(Q(x)P(x) x(P(x) R(x) xR(x) Q(x)而驗證該推理的證明序列如下：(1) xR(x)/ 前提引入(2) xR(x)/ (1)量詞否定等值式/ (2)存在量詞消除/ 前提引入(3) R(c)(4) x(P(x) R(x)(5) P(c) R(c)/ (4)全稱量詞消除/ (5)等價消除(6) P(c)R(c)(7) P(c)/ (3),(6)拒取式/ 前提引入(8) x(Q(x)P(x)(9) Q(c)P(c)(10) Q(c)/ (8)全稱量詞消除/ (7),(9)析取三段論/ (10)存在量詞引入(11) xQ(x)(

11、18分)(1) 在命題邏輯中證明等值式：(10分)(pq)(q r)(r p) (pq)(q r)(r p)4我們通過求左邊公式的主合取范式，以及右邊公式的主析取范式，再進行比較而證明：(pq)(q r)(r p)/ 極大項擴展/ 極大項編碼 (pq r)(pqr)(pq r)(pq r) M M M M142(pq)(q r)(r p)/ 極小項擴展/ 極小項編碼 (pq r)(pq r)(pq r)(pq r) m m m m7635由主析取范式和主合取范式之間的關(guān)系有M M M M m m m m1243567材的主范式編碼稍有不同，因此有必要時可說明主范式的編碼及主析取范式和主合取范式之間的關(guān)(2) 在命題邏輯中驗證推理（可使用帶前提集的證明序列