当前位置：文档之家 › 《离散数学》试题及答案.pdf

《离散数学》试题及答案.pdf

  • 格式：pdf
  • 大小：199.89 KB
  • 文档页数：13

一、填空题1设集合A,B ，其中A ＝{1,2,3}, B= {1,2}, 则A - B ＝{3};(A) - (B)＝{3},{1,3},{2,3},{1,2,3}}.2. 设有限集合A, |A| = n, 则|(A ×A)| = 22n .3.设集合 A = {a, b}, B = {1, 2}, 则从A 到B 的所有映射是1= {(a,1), (b,1)}, 2= {(a,2),(b,2)},3= {(a,1), (b,2)}, 4= {(a,2), (b,1)},其中双射的是3,4.4. 已知命题公式G ＝(P Q)∧R ，则G 的主析取范式是(P ∧Q ∧R)5.设G 是完全二叉树，G 有7个点，其中4个叶点，则G 的总度数为12，分枝点数为3.6设A 、B 为两个集合, A= {1,2,4}, B = {3,4}, 则从AB ＝{4}; A B ＝{1,2,3,4};A －B ＝{1,2}.7.设R 是集合A 上的等价关系，则R 所具有的关系的三个特性是自反性, 对称性传递性.8. 设命题公式G ＝(P (Q R))，则使公式G 为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0)9. 设集合A ＝{1,2,3,4}, A 上的关系R 1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)},则R 1R 2 ={(1,3),(2,2),(3,1)} , R 2R 1 = {(2,4),(3,3),(4,2)} _R 12={(2,2),(3,3).10. 设有限集A, B ，|A| = m, |B| = n, 则| |(A B)| =nm 2.11设A,B,R 是三个集合，其中R 是实数集，A = {x | -1≤x ≤1, x R}, B = {x | 0≤x < 2, x R},则A-B = -1<=x<0, B-A ={x | 1 < x < 2, x R},A ∩B ={x | 0≤x ≤1, x R}, .13.设集合A ＝{2, 3, 4, 5, 6}，R 是A 上的整除关系，则R 以集合形式(列举法)记为{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} .14. 设一阶逻辑公式G = xP(x)xQ(x)，则G 的前束范式是x(P(x)∨Q(x)).15.设G 是具有8个顶点的树，则G 中增加21条边才能把G 变成完全图。

(完全图的边数2)1(n n ，树的边数为n-1)16.设谓词的定义域为{a, b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是_(R(a)∧R(b))→(S(a)∨S(b))_.17. 设集合A ＝{1, 2, 3, 4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)}, S ＝{(1,3),(2,3),(3,2)}。

则R S ＝{(1, 3),(2, 2)} ,R 2＝{(1, 1),(1, 2),(1, 3)}.二、选择题1设集合A={2,{a},3,4}，B = {{a},3,4,1}，E 为全集，则下列命题正确的是( C )。

(A){2}A(B){a}A(C){{a}}B E (D){{a},1,3,4}B.2设集合A={1,2,3},A 上的关系R ＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R 不具备( D ). (A)自反性(B)传递性(C)对称性(D)反对称性3 设半序集(A,≤)关系≤的哈斯图如下所示，若A 的子集B = {2,3,4,5},则元素6为B 的( B )。

(A)下界(B)上界(C)最小上界(D)以上答案都不对4下列语句中，( B )是命题。

(A)请把门关上(B)地球外的星球上也有人(C)x + 5 > 6(D)下午有会吗？5设I 是如下一个解释：D ＝{a,b},101b) P(b,a) P(b,b) P(a,),(a a P 则在解释I 下取真值为1的公式是( D).(A)x yP(x,y) (B)x yP(x,y) (C)xP(x,x) (D)x yP(x,y).6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( C ).(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7. 设G 、H 是一阶逻辑公式，P 是一个谓词，G ＝xP(x), H ＝xP(x),则一阶逻辑公式GH是( C ). (A)恒真的(B)恒假的(C)可满足的(D)前束范式.8设命题公式G ＝(P Q)，H ＝P (QP)，则G 与H 的关系是( A )。

(A)GH(B)H G (C)G ＝H (D)以上都不是. 9设A, B 为集合，当( D )时A －B ＝B.(A)A ＝B (B)AB (C)BA(D)A ＝B ＝.10 设集合 A = {1,2,3,4}, A 上的关系R ＝{(1,1),(2,3),(2,4),(3,4)}, 则R 具有( B)。

(A)自反性(B)传递性(C)对称性(D)以上答案都不对11下列关于集合的表示中正确的为(B )。

(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c} (D){a,b}{a,b,c}12命题xG(x)取真值1的充分必要条件是( A).(A)对任意x ，G(x)都取真值 1. (B)有一个x 0，使G(x 0)取真值 1. (C)有某些x ，使G(x 0)取真值 1. (D)以上答案都不对.13. 设G 是连通平面图，有5个顶点，6个面，则G 的边数是(A).(A) 9条(B) 5条(C) 6条(D) 11条.14. 设G 是5个顶点的完全图，则从G 中删去( A )条边可以得到树.(A)6(B)5(C)10(D)4.15. 设图G 的相邻矩阵为110110101110110010111110，则G 的顶点数与边数分别为( D ).(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.12345 6三、计算证明题1.设集合A ＝{1, 2, 3, 4, 6, 8, 9, 12}，R 为整除关系。

(1)画出半序集(A,R)的哈斯图；(2)写出A 的子集 B = {3,6,9,12}的上界，下界，最小上界，最大下界；(3)写出A 的最大元，最小元，极大元，极小元。

解：（1）124836129（2）B 无上界，也无最小上界。

下界1, 3; 最大下界是 3（3）A 无最大元，最小元是1，极大元8, 12, 9; 极小元是 12.设集合A ＝{1, 2, 3, 4}，A 上的关系R ＝{(x,y) | x, y A 且x y}, 求(1)画出R 的关系图；(2)写出R 的关系矩阵.解：（1）1234（2）1000110011101111RM 3.设R 是实数集合，,,是R 上的三个映射，(x) = x+3, (x) = 2x, (x) ＝x/4,试求复合映射?，?, ?, ?，??.解：(1)?＝((x))＝(x)+3＝2x+3＝2x+3. (2)?＝((x))＝(x)+3＝(x+3)+3＝x+6, (3)?＝((x))＝(x)+3＝x/4+3, (4)?＝((x))＝(x)/4＝2x/4 = x/2,(5)??＝?(?)＝?+3＝2x/4+3＝x/2+3.▲4.设I 是如下一个解释：D = {2, 3}, a b f (2) f (3) P(2, 2) P(2, 3) P(3, 2) P(3, 3) 323211试求(1) P(a, f (a))∧P(b, f (b));(2)x y P (y, x).解：(1) P(a, f (a))∧P(b, f (b)) = P(3, f (3))∧P(2, f (2))= P(3, 2)∧P(2,3)= 1∧0= 0.(2) x y P (y, x) = x (P (2, x)∨P (3, x))= (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3))= (0∨1)∧(0∨1)= 1∧1= 1.5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。

(1)画出半序集(A,R)的哈斯图；(2)写出A的最大元，最小元，极大元，极小元；(3)写出A的子集 B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.解：(1) (2)无最大元，最小元1，极大元8, 12; 极小元是 1.(3) B无上界，无最小上界。

下界1, 2; 最大下界 2.6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。

解：G = (P→Q)∨(Q∧(P→R))= (P∨Q)∨(Q∧(P∨R))= (P∧Q)∨(Q∧(P∨R))= (P∧Q)∨(Q∧P)∨(Q∧R)= (P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R) = (P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R) = m 3∨m 4∨m 5∨m 6∨m 7 = (3, 4, 5, 6, 7).7.(9分)设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G 化成前束范式.解：G = (xP(x)∨yQ(y))→xR(x)= (xP(x)∨yQ(y))∨xR(x) = (xP(x)∧yQ(y))∨xR(x)= (x P(x)∧y Q(y))∨zR(z) = x y z((P(x)∧Q(y))∨R(z))9. 设R 是集合 A = {a, b, c, d}. R 是A 上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},(1)求出r(R), s(R), t(R)；(2)画出r(R), s(R), t(R)的关系图. 解：（1）r(R)＝R ∪I A ＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)}, s(R)＝R ∪R－1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},t(R)＝R ∪R 2∪R 3∪R 4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}；(2)关系图:11. 通过求主析取范式判断下列命题公式是否等价：(1) G = (P ∧Q)∨(P ∧Q ∧R) (2) H = (P ∨(Q ∧R))∧(Q ∨(P ∧R)) 解：G ＝(P ∧Q)∨(P ∧Q ∧R)ba cdr(R)ba cds(R)ba cdt(R)＝(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R) ＝m 6∨m 7∨m 3＝ (3, 6, 7)H = (P ∨(Q ∧R))∧(Q ∨(P ∧R)) ＝(P ∧Q)∨(Q ∧R))∨(P ∧Q ∧R)＝(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R) ＝(P ∧Q ∧R)∨(P ∧Q ∧R)∨(P ∧Q ∧R) ＝m 6∨m 3∨m 7G,H 的主析取范式相同，所以G = H.13. 设R 和S 是集合A ＝{a, b, c, d}上的关系，其中R ＝{(a, a),(a, c),(b, c),(c, d)},S ＝{(a, b),(b, c),(b, d),(d, d)}. (1) 试写出R 和S 的关系矩阵；(2) 计算R?S, R ∪S, R －1, S －1?R －1. 解：(1)000100001000101RM 1000000011000010SM (2)R?S ＝{(a, b),(c, d)},R ∪S ＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R －1＝{(a, a),(c, a),(c, b),(d, c)},S －1?R －1＝{(b, a),(d, c)}.四、证明题1. 利用形式演绎法证明：{P →Q, R →S , P ∨R}蕴涵Q ∨S 。

合集下载

离散数学考试试题（A、B卷及答案）

离散数学考试试题（A、B卷及答案）

离散数学考试试题（A、B卷及答案）离散数学考试试题(A卷及答案)一、证明题(10分)1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→C。

P<->Q=(p->Q)合取(Q->p)证明: (P∧Q∧A→C)∧(A→P∨Q∨C)(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律((P∧Q∧A)∨(A∧?P∧?Q))∨C( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律( A∧(P?Q))∨C(A∧(P?Q))→C2) ?(P↑Q)??P↓?Q。

证明:?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。

二、分别用真值表法与公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式,并写出其相应的成真赋值与成假赋值(15分)。

主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。

主析取范式可由析取范式经等值演算法算得。

证明:公式法:因为(P→(Q∨R))∧(?P∨(Q?R))(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R))(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P ∨R∨?R) (?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)4M使(非P析取Q析取R)为0所赋真值,即100,二进制为4M∧6M∧50m∨1m∨2m∨3m∨7m所以,公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。

真值表法:0 0 1 0 1 00 1 11 0 0 1 0 1 1 1 0 1 1 1 0111111111111111111为000、001、010、011、111:成假赋值为:100、101、110。

离散数学试题与参考答案

离散数学试题与参考答案

离散数学试题与参考答案(总4页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《离散数学》试题及答案一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1. 命题公式Q Q P →∨)(为 ( )(A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式2．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。

(A)． P Q →； (B)．P Q ∧； (C)．P Q ⌝→⌝； (D)．P Q ⌝∨．3.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( ) (A) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >} (C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>} 5. 设G 如右图：那么G 不是( ). (A)哈密顿图； (B)完全图；(C)欧拉图； (D) 平面图.二、填空题：本大题共5小题，每小题4分，共20分。

把答案填在对应题号后的横线上。

6. 设集合A ={,{a }}，则A 的幂集P (A )=7. 设集合A ={1,2,3,4 }, B ={6,8,12}, A 到B 的关系R ＝},,2,{B y A x x y y x ∈∈=><, 那么R －1＝8. 在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系. 9. 写出一个不含“→”的逻辑联结词的完备集 . 10.设X ＝{a ,b ,c }，R 是X 上的二元关系，其关系矩阵为M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001001101，那么R 的关系图为三、证明题（共30分）11. （10分）已知A 、B 、C 是三个集合，证明A ∩(B ∪C)=(A ∩B)∪(A ∩C) 12. （10分）构造证明：(P (Q S))∧(R ∨P)∧Q R S13.（10分）证明（0,1）与[0,1)，[0,1)与[0,1]等势。

《离散数学》考试试卷（试卷库20卷）及答案

《离散数学》考试试卷（试卷库20卷）及答案

《离散数学》考试试卷（试卷库20卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库20卷）试题总分： 100 分考试时限：120 分钟、选择题（每题2分，共20分）1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，则“人总是要死的”谓词公式表示为( )（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧（C ）))()((x Mortal x M x →?（D ）))()((x Mortal x M x ∧?2. 判断下列命题哪个正确？( )（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集）（D ）若A 为非空集，则A ≠A∪A 成立3. 集合},2{N n x x A n∈==对( )运算封闭（A ）乘法（B ）减法（C ）加法（D ）y x -4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则N b a ∈?,有=∨b a ( )（A ）a（B ）b（C ）min(a ，b)（D ） max(a ，b)5. 有向图D=，则41v v 到长度为2的通路有( )条（A ）0 （B ）1 （C ）2 （D ）36. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点（A ）10 （B ）4 （C ）8 （D ）127. 下面哪一种图不一定是树？（）（A ）无回路的连通图（B ）有n 个结点n-1条边的连通图（C ）每对结点间都有通路的图（D ）连通但删去一条边则不连通的图 8. 设P ：我将去镇上,Q ：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）（A ）P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代数系统中,其中*是加法运算,（）不是群。

(完整版)离散数学题目及答案

(完整版)离散数学题目及答案

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。