《逻辑试题2006上末答案 (2)》由会员分享,可在线阅读,更多相关《逻辑试题2006上末答案 (2)(7页珍藏版)》请在金锄头文库上搜索。
1、2006 年上学期逻辑导论期末考试系别 姓名 学号一、把下列语句翻译为谓词逻辑的公式,设个体域为全域(20 分):1北京大学是中国最好的大学。(要求:不把“最好”当性质)解:令 U 表示“中国的大学”,B 表示“比好 ”,则该语句翻译为:U(a) x(U(x) xaB(a, x)2有最小的自然数,但没有最大的自然数。解:N:自然数;R:;S:x(N(x) y(N(y)R(x, y) x(N(x)y(N(y)S(x, y)3每个人都有唯一的母亲,但并非每位母亲都有唯一的子女。解:H:人;M(x, y):x 是 y 的母亲。x(H(x)y(M(y, x)z(M(z, x)zy) x(y(M(x,
2、y)z(M(x, z)zy)4有些学生尊敬所有的老师,所以,所有老师都有学生尊敬。解:S:学生; T:老师;R:尊敬x(S(x)y(T(y) R(x, y) x(T(x)y(S(y)R(y, x)二、用一阶树形图判定下列公式或推理是不是普遍有效的(15 分):(1)x(F(x)G(x) xF(x) xG(x)解:(x(F(x)G(x)xF(x) xG(x) x(F(x)G(x)(xF(x) xG(x) xF(x) xG(x) F()G()F()G() F() G() F()G() F() G() 结论:图已经画完,有一个不闭的枝,因此,带否定号的公式可满足,原公式不是普遍有效式。(2) ( x
3、F(x)xG(x)x(F(x)yH(y)G(x)解:(xF(x) xG(x)x(F(x)yH(y)G(x) (xF(x)xG(x) (x(F(x) yH(y)G(x) (F() yH(y)G() F()yH(y) G()F()yH(y)xF(x) xG(x) F() G() 结论:图已经画完,所有的枝都是闭枝,因此,带否定号的公式不可满足,原公式是普遍有效式。(3) x(A(x)y(B(y)C(x,y) / y(B(y)x(A(x)C(x,y)解: x(A(x)y(B(y)C(x,y) y(B(y)x(A(x)C(x,y) (B()x(A(x)C(x, ) B()x(A(x)C(x, )A()
4、y(B(y)C(, y) A()y(B(y)C(, y)B()C(, ) B() C(, ) (A()C(, ) A() C(, ) 结论:图已经画完,所有的枝都是闭枝,因此,带否定号的公式不可满足,原公式是普遍有效式。三、分别构造一个相应的解释,证明(15 分):(1)xF(x)xG(x) x(F(x)G(x) 不是普遍有效的。解:个体域:N;F :偶数; G:奇数。xF(x)表示“有的自然数是偶数”,真命题;xG(x)表示“有的自然数是奇数”,真命题;因此,该蕴涵式的前件是真命题;x(F(x)G(x)表示“有的自然数既是偶数又是奇数”,假命题。整个蕴涵式前件真后件假,假命题。所以,该蕴涵式
5、不是普遍有效的。(2)(xF(x) xG(x)x(F(x)G(x) 是可满足的。解:个体域:N;F :偶数; G:奇数。xF(x)表示“所有自然数是偶数 ”,假命题;xG(x)表示“有的自然数是奇数”,真命题;故xG(x)是假命题;前件假后件假,故作为这个蕴涵式前件的那个蕴涵式是真命题;x(F(x)G(x)表示“有的自然数并非既是偶数又是奇数”,真命题;真命题蕴涵真命题,整个蕴涵式是真命题;所以,该蕴涵式是可满足的。(3)xyR(x, y) yxR(x, y)是可满足但不普遍有效的。解:(i)个体域:N;R : 。xyR(x, y)表示“所有自然数都大于等于有的自然数”,真命题;yxR(x,
6、y)表示“有的自然数(比如 1),所有自然数都大于等于它”,真命题;真命题蕴涵真命题,真命题;所以,该蕴涵式是可满足的。(ii)个体域:N;R :。xyR(x, y)表示“所有自然数都小于等于有的自然数”,即“没有最大的自然数”,真命题;yxR(x, y)表示“有的自然数,所有自然数都小于等于它”,即“有最大的自然数”,假命题;真命题蕴涵假命题,假命题;所以,该蕴涵式不是普遍有效的。四、证明下列公式或推理是自然推理系统 QN 的定理(35 分):1xF(x)xG(x),x( R(x)F(x),x(R(x)G(x) /xR(x)(证明只能使用 15 个初始规则)证明:(1)xF(x)xG(x)
7、前提(2)x( R(x)F(x) 前提(3)x( R(x)G(x) 前提(4) xF(x) 假设(5) F() (4) (6) R()F() (2) (7) R() 假设(8) F() (6)(7)(9) F() (5) (10) R() (7)(8)(9) (11)xF(x) R() (4)(10) (12)xG(x) R() 同理可证 (13)R() (1)(11)(12) (14)xR(x) (13) 2x(F(x) G(x)y(R(x, y)H(y),x(S(x)F(x) y(R(x, y) S(y),x(S(x)G(x) / x(S(x)H(x)证明:(1)x(F(x) G(x)y(R(x, y)H(y) 前提(2)x(S(x) F(x)y(R(x, y) S(y) 前提(3)x(S(x) G(x) 前提(4)(S() F()y(R(, y) S(y) (2) (5) S()F() (4) (6)y(R( , y) S(y) (4) (7)S() (5) (8)F() (5) (9) S()G() (3) (10)G( ) (7)(9) (11)F()G( ) (7)(10) (12)F()G( )y(R(, y)H(y) (1) (13)y(R( , y)H(y) (11)(12) (14)R(, ) H