数理逻辑复习题

更新时间:2024-04-10 17:45:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

1 离散数学期末复习题 2012-6-16

1.“太阳系以外的星球上有生命。”是命题。 ( T ) 2.?(???)=?(A)? ?(B) ( F )

?(?∩?)=?(A)∩?(B) ( T ) 3.一个命题的合取范式不是唯一的。 ( T ) 4.等价式?(?x)A(x)?(?x)?A(x)成立。 ( T ) 5.(?x)(P(x)?Q(x))? R(x)是命题。 ( F )

8.对于一个谓词公式,指定不同的个体域,则其真值不一定相同.T 9. 若命题公式A的主析取范式包含全部的极小项,则A为永真式T 10.命题“他在教室看书或在宿舍看书。”可以符号化为P∨ S。F 11.当个体域S={a,b,c}消去公式(?x) P(x)∨(?x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F

12. 设P、Q是两个命题,当且仅当P、Q的真值均相同时,P ? Q的值为T. T 13. 命题公式(P∧(P→ Q)) → Q是永真式. T

14. 命题联结词集{∨、∧ }是极小功能完备的联结词集. F

15.(A ? Φ) ? (B ? Φ) ? (A ? B ?Φ ) F 16. (P ? Q)? ┐( P ∨Q) 是矛盾式。 F 17. ?xA(x) ∨ ?x B(x) ? ?x ( A(x) ∨ B(x)) T 19. 若关系R不具有对称性则R一定具有反对称性 F 22. 设A、B、C是任意集合,且C-B = C-A,则A=B 。 F 23. 设A、B和C为任意集合,且A∪B=A∪C,则B=C. F 24.若R和S是X上具有对称性的关系,则R o S也具有对称性。F 25.若R和S是X上的具有对称性的关系,则R ∩S具有对称性。 T 26.?xA(x)∨?x B(x)? ?x ( A(x) ∨ B(x)) (F ) 27. (P ? Q)? ┐( P ∨Q) 是可满足式。 ( F) 28. { }={φ} ( F )

二、填空题

1.已知B={ {a,b},c},

则B的幂集?(B)= { B , Φ,{{a,b}},{c} }

2.已知A={1,2,3,4,5,6,7},B={2,4,6,8,10},则

A?B= {1,3,5,7,} ,A + B= {1,3,5,7, 8,10} 。

3.设A、B是有穷集合,?A=n,?B=m,那么??(A)= 2n ,

?(A×B)= n*n ,??(A×B)= 2n*n ,

4.R是集合X上的关系。如果R满足 自反 , 对称 , 传递 ,

则R是X上的等价关系。

2

5.如果关系矩阵中主对角线上的元素都是1,则此关系一定具有__自反_性。

6. 两个重言式的析取是 重言式 ,一个重言式与一个矛盾式的析取是 重言式 .

7. 公式(P∨Q) ? R的只含联结词{┐、∧}的等值式 ,

8.设谓词Q(x): x < 5,以及个体域是{-1,0,1,3,5,7}

则(?x)Q(x)真值为__F____, (?x)Q(x)真值为__T_____ . 9.已知 A ?(~ B) = { a, b, c, d } A ? B = { e, f }

A = __{ a, b, c, d, e, f }____________

10. 谓词公式 ?xF(x,y) → ? ?y G(x,y)的前束范式为

?x ? y ( F(x,t) → ? G(s,y))______ .

11.设P(x):x是金子,Q(x):x是闪光的,则命题“金子是闪光的,但闪光的不

一定是金子”符号化的谓词公式 . 12. 设F(x):x是北京人,G(x):x是在北京工作。

则命题“在北京工作的并非是北京人”符号化的谓词公式为_____________

13、设个体为自然数集,N(x):x是自然数,L(x,y):x>y

则命题“不存在最大的自然数”形式化为: .

14.判断下列公式的类型或真值:(永真式,矛盾式,可满足式、T、F)

1) ? (p? q? r ) ? (? p ? ?q ? ?r ) ( T ) 2)?x A(x) ? ?xA(x) ( T ) 3)(P ? Q) ? (Q ?P) ( 可满足 ) 4)? (?x A(x) ??yB(y)) ? ?y B(y) ( F )

16.设A={1,2,3,{1,2},{3}},B={ {1},2,3,{2,3},}

A –(B∩A) = { 1, {1,2},{3} }

B 十 A = {1,{1,2},{3},{1}, {2,3} }

16.已知A={1,2,3,4,5},B={a,b,c,d},则

定义在A到B的不同关系R有___220_________种.

定义在A到B的不同函数F有___45_________种. 设A={1,2,3},B={a,b,2},则

求 A?B=

3 P(A)∪P(B)= P(A?B) =

17.关系R={ ?a,b?,?b,c?,?d,d?,?a,a? }

关系R具有哪些性质? ______反对称、__________________.

r(R)= R ∪ { ?b,b?,?c,c? }。

s(R) = R ∪{ ?c,b?,?b,a? }。

t(R) = R ∪ { ?a,c? }。

21.给定命题公式(P ? Q) ? R,该公式在全功能集合{?,?}中的形式

为: ___________________________. 27. 命题公式((p ∧ q) → r ) ∧( p → ?( q ∧ r ) )

该公式的主析取范式为 ____________________

该公式的主合取范式为 __(?p ∨? q ∨ r ) ∧_(?p ∨? q ∨? r )__

三、选择题(有多选题)

1.选出下列语句中的命题 ( C D ) A.天气多麽晴朗啊! B.我正在说谎。 C.雪是黑色的。 D.我做完作业了。

4 .下列等价式中错误的是 ( C ) A. (?x)(A(x)?p)?(?x)A(x)?p B. (?x)A(x)?p ?(?x)(A(x)?p)

C. (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) D. (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) 5.下列各式中哪个是不成立的: ( A B C ) A: p → q ? ┐p → ┐q

B: (?x)(P(x)∨Q(x)) ? (?x)P(x)∨(?x)Q(x); C: (p → q) ∧ ┐q ? ┐p ;

4 D: (?x)(P(x)∨Q(x)) ? ( ? x)P(x)∨(?x)Q(x); 7.下面哪组命题公式是等值的;( A C D )

A: ┐(A →B),A∧┐B; B: A→ (B∨C), ┐A∧(B∨C); C: ┐(A ? B),(A∧┐B)∨(┐A∧B); D: A → (B∨C), (A∧┐B) → C. 8. P ? Q 的等价说法有( A B D )。

A) P ? ?Q 是永假式 B) Q 是 P的有效结论。 C) P是Q的有效结论 D) P ? Q 为永真式

9. 下列推理式是正确的有( B )

A) ? P ? ( Q? P) ? ? Q B) (P ? Q) ? P? Q C) P? Q ? ? Q? P

D) (Q ? (P ? ?P)) ? (R ?(P ? ?P)) ? R ? Q 10. 设A={{1,2,3},{4,5},{6,7,8},3},下式哪个式子为真( C D ) A: φ ?A; B: {6,7,8}? A; C: {{4,5}}? A; D: 3 ?A. 11. 设F(x):为有理数,G(x):为自然数,

命题“有理数不全是自然数”的符号化形式为( A B )

A) ?┐ ?x(F(x) ? G(x)) B) ? ?x(F(x) ?┐ G(x)) C) ? ?x(F(x) ? G(x)) D) ?x(F(x) ? ? G(x)) 12. 设 P:2是素数, Q:5是素数, R: π是有理数。下面复合命题中为假的是(B C )

A) (P ? Q ) ∨ R B) R ? (P ∨ Q )

C)( P ? R)? Q D) (P ? R) ? Q 16.设个体域A={a,b},公式(?x)P(x)∨(?x)S(x)在A上消去量词后为( B D ) A) P(x)∧S(x); B) P(a) ∨ P(b) ∨S(a) ∧ S(b);

C) P(a)∧S(b); D) P(a) ∨P(b) ∨(S(a) ∧ S(b)). 17.下面哪些命题是真命题( B C D )

A) 如果2是偶数,那么一个命题公式的合取范式唯一; B)如果2是偶数,那么一个命题公式的主析取范式唯一; C)如果2是奇数,那么一个命题公式的析取范式唯一; D)如果2是奇数,那么一个命题公式的主合取范式不唯一。 18 设A={1,2,3,4,5,6}上的关系为R ={(i,z)|i>z},

则R的逆关系的性质有( C D )

A) 对称的; B) 自反的; C) 反自反的,可传递的; D) 反对称的. C) 7; D) 10.

22. 给定下列联结词集合,哪个可构成联结词完备集( B D )

A) { ∨,∧,┐} B) {↑ }

5 C) {┐, →, ↓} D) {┐,∧}

四、运算题

(1)求命题公式((P?Q)?(?┐ Q? ┐P)) ∧S 的最简等值式.

(2)命题公式(p → q) ? r

该公式的主析取范式为 __________________________________.

该公式的主合取范式为 __________________________________. 1 0 0 1 (3) 设集合X={ a , b , c , d } , 0 0 1 0 集合X上的关系R和S的关系矩阵为MR= 1 0 0 1 1 1 0 1 1 0 1 0 MS= 0 1 0 0 1)给出关系R和S的集合表示 0 0 1 0 1 0 0 0 2)画出R?S的关系图

3)求出R?S的逆关系的关系矩阵

(7)求(P?Q)?( ?P?R) ?(Q?R)的主析取范式。

? (P?Q?R )?( P?Q ??R) ?( ?P? Q ?R) ?(?P? ?Q ?R) ? m1 ? m3 ? m6 ? m7

主合取范式 =

(9)给定集合X={a,b,c},且R是X中的二元关系。R的关系矩阵是

1 1 1 MR= 0 1 1 试求出R,R, R?R的关系矩阵。 1 0 1

(12)设A={0,1,2}到B ={0,2,4}的关系为

R={|a,b?A∩B},

则R = { ?0,0?,?2,2?,?0,2?,?2,0? } 。

(13)设集合A={1,2,3}上的关系R={<1,1>,<2,2>,<1,3>,<3,3>}, 该关系具有什么性质?

确定该关系的自反闭包、对称闭包、传递闭包 五、证明题

(1)用推理规则证明?t?m是前提条件:p? (q?m), ?t?p, q的有效结论

(2)用形式推理规则证明:

~2~

6 结论 (?x )( C(x) ? ? A(x))是

前提条件: ?x (A(x) ?B (x)), ?x (C(x) ??B(x))的有效结论

(3)证明(? x)? A(x)

是前提(?x)(A(x)→? B(x)),(? x)(B(x)∨ C(x)),

(?x)? C(x)的有效结论。

(4) 设 A,B是集合,证明 P(A ∩B) = P(A) ∩ P(B)

(5)给定集合X,且R是X中的二元关系。试证明, R2 ? R,当且仅当关系R是可传递的。

(6)给定集合X,且R和S是X中具有传递性的二元关系。试证明R∩S也是可

传递的二元关系。

6 结论 (?x )( C(x) ? ? A(x))是

前提条件: ?x (A(x) ?B (x)), ?x (C(x) ??B(x))的有效结论

(3)证明(? x)? A(x)

是前提(?x)(A(x)→? B(x)),(? x)(B(x)∨ C(x)),

(?x)? C(x)的有效结论。

(4) 设 A,B是集合,证明 P(A ∩B) = P(A) ∩ P(B)

(5)给定集合X,且R是X中的二元关系。试证明, R2 ? R,当且仅当关系R是可传递的。

(6)给定集合X,且R和S是X中具有传递性的二元关系。试证明R∩S也是可

传递的二元关系。

本文来源:https://www.bwwdw.com/article/vjur.html

微信扫码分享

《数理逻辑复习题.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档
下载全文
范文搜索
下载文档
Top