当前位置：文档库 › 离散数学练习题及答案

离散数学练习题及答案

离散数学试题

一、单项选择题

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为

（B）

A. P∧Q

B. P→Q

C. Q→P

D. P∨Q

2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m，

则各顶点的度数之和等于（ D ）。

A.n

B. m

C. 2n

D. 2m

3.下列命题为假．命题的是（A）

A.如果2是偶数，那么一个公式的析取范式惟一

B.如果2是偶数，那么一个公式的析取范式不惟一

C.如果2是奇数，那么一个公式的析取范式惟一

D.如果2是奇数，那么一个公式的析取范式不惟一

4.谓词公式?x(P(x)∨?yR(y))→Q(x) 中变元x是（D）

A.自由变元

B.约束变元

C.既不是自由变元也不是约束变元

D.既是自由变元也是约束变元

5.若个体域为整数域，下列公式中值为真的是（A）

A.?x?y(x+y=0)

B.?y?x(x+y=0)

C.?x?y(x+y=0)

D.??x?y(x+y=0)

6.下列命题中不．正确的是（D）

A.x∈{x}-{{x}}

B.{x}?{x}-{{x}}

C.A={x}∪x,则x∈A且x?A

D.A-B=??A=B

7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C）

A.P?Q

B.P?Q

C.Q?P

D.Q=P

8.下列表达式中不．成立的是（A）

A.A∪(B⊕C)=(A∪B) ⊕ (A∪C)

B.A∩(B⊕C)=(A∩B) ⊕ (A∩C)

C.(A⊕B)×C=(A×C) ⊕ (B×C)

D.(A-B) ×C=(A×C)-(B×C)

9.半群、群及独异点的关系是（A）

A.{群}?{独异点}?{半群}

B.{独异点}?{半群}?{群}

2 C.{独异点}?{群}?{半群} D.{半群}?{群}?{独异点}

10.下列集合对所给的二元运算封闭的是（ C ） A.正整数集上的减法运算

B.在正实数的集R +上规定*为a *b=ab-a-b

?a,b ∈R +

C.正整数集Z +上的二元运算*为x *y=min(x,y) ?x,y ∈Z +

D.全体n ×n 实可逆矩阵集合R n

×n

上的矩阵加法

11.设集合A={1，2，3}，下列关系R 中不．是等价关系的是（ C ） A.R={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}

C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}

12.下列函数中为双射的是（ D ） A.f ：Z →Z,f(j)=j(mod)3 B.f ：N →N,f(j)=?

??是偶数是奇数

j ,0j ,1

C.f ：Z →N,f(j)=|2j|+1

D.f ：R →R,f(r)=2r-15

13.设集合A={a,b, c}上的关系如下，具有传递性的是（ D ） A.R={,,,} B.R={,}

C.R={,,,}

D.R={}

14. 设有限集合A 的元素个数为n 个，则A 上共有（ C ）个不同的二元关系。

A ． n B. C. D. 以上都不对

15.设D 的结点数大于1，D=是强连通图，当且仅当（D ） A.D 中至少有一条通路

B.D 中至少有一条回路

C.D 中有通过每个结点至少一次的通路

D.D 中有通过每个结点至少一次的回路

15-1 . 下列公式中，（C ）是含有3个命题变项p,q,r 的极小项。

A. p ∨q

B. ? (p ∧q ∧r)

C. ?p ∧?q ∧?r

D. p ∧q ∨ r

二、填空题

请在每小题的空格中填上正确答案。错填、不填均无分。

16.设A={1,2,3}，B={3,4,5}，则A ⊕A=___________，A ⊕B=___________。

17.设A={1,2,3,4,5}，R ?A ×A ，R={<1,2>，<3,4>,<2,2>}，则R 的自反闭包r(R)=__________。

对称闭包t(R)=__________。

18.设P 、Q 为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。

3 19.对于公式?x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当个体域为{1,2}时，其真值为

_____________ ,当个体域为{0,1,2}时，其真值为_____________。

20.设f ∶R →R,f(x)=x+3,g ∶R →R,g(x)=2x+1,则复合函数____________))(g (f =x ,

__________________)x )(f (g = 。（此题两个答案颠倒一下） 22.无向图G=如左所示，则G 的最大度

Δ(G)=_____________，G 的最小度δ(G)=_____________。 23.设图G,V={v 1,v 2,v 3,v 4},若G 的邻接矩阵?

???

????

???=0001

00111101

1010

A ，则deg -(v 1)=_ ________, deg +(v 4)=____________。

25.给定集合A={1,2,3,4,5}，在集合A 上定义两种关系：R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>}，则_______________S R = ，_______________R S = 。

答案：

三、计算题

26.设A={a,b,c,d}，A 上的等价关系R={,,,}∪I A ，画出R 的关系图，并求出A 中各元素的等价类。

28.求下列公式的主析取范式：P→（（Q→P）∧（?P∧Q））

解：

原式??P ∨（（?Q∨P）∧（?P∧Q））

??P ∨((?Q∧?P∧Q) ∨(P∧?P∧Q))

??P∨(0∨0)

??P

?(?P∧?Q)∨(?P∧Q)

?m0∨m1

29.设A={a, b, c, d, e}，R为A上的关系，R={，，, , ,,

e>}∪I A，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。

解：

四、证明题

32.设R是A上的自反和传递关系，如下定义A上的关系T，使得?x, y∈A，∈T?∈R∧(y, x)∈R。

证明T是A上的等价关系。

离散数学题库及答案

数理逻辑部分选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。

《离散数学》考试题库及答案(三)

《离散数学》考试题库及答案一、填空 10% （每小题 2分） 1、若P ，Q 为二命题，Q P ?真值为1，当且仅当。 2、对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的公式为。 3、 )) (()(x xG x xF ??∧?的前束范式为。 4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则被称为全称量词消去规则，记为US 。 5、与非门的逻辑网络为。二、选择 30% （每小题 3分） 1、下列各符号串，不是合式公式的有（）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、下列语句是命题的有（）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、下列公式是重言式的有（）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、下列问题成立的有（）。 A 、若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、命题逻辑演绎的CP 规则为（）。 A 、在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；

2016离散数学练习题 (答案修改)

2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 A. (()((),0))x P x L f x ?∧ B. (()((),0))x P x L f x ?→ C. ()((),0)xP x L f x ?∧ D. ()((),0)xP x L f x ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G 一共有（ C ）个顶点。

离散数学试题与答案

试卷二试题与参考答案一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等性 ;就是否有对称性。 6、4阶群必就是群或群。 7、下面偏序格就是分配格的就是。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学习题

第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。（2）5能被2整除。（3）现在开会吗？（4）x+5>0 （5）这朵花真是好看！（6）2是素数当且仅当三角形有三条边。（7）雪是黑色的当且仅当太阳是从东方升起。（8）2000年10月1日天气晴好。（9）太阳系以外的星球上有生物。（10）小李在宿舍里。（11）全体起立。（12）4是2的倍数或是3的倍数。（13）4是偶数且是奇数。（14）李明和王华是同学。（15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。（1）若2+2=4，则3+3=6；（2）若2+2=4，则3+3≠6；（3）若2+2≠=4，则3+3=6；（4）若2+2≠=4，则3+3≠=6；（5）2+2=4，当且仅当3+3=6；（6）2+2=4，当且仅当3+3≠6；（7）2+2≠4，当且仅当3+3=6；（8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。（1）如果今天是1号，则明天是2号；（2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。（1）2是偶数不是素数；（2）小王不但聪明而且用功；（3）虽然天气冷。老王还是来了；（4）他一边吃饭，一边看电视；（5）如果天下大雨，他就乘公交汽车来；（6）只有天下大雨，他才乘公交汽车来；（7）除非天下大雨，否则他不乘公交汽车来；（8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);

离散数学习题三含答案

离散数学习题三 11、填充下面推理证明中没有写出的推理规则。前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。（2）证明从此前提出发，推任何结论的推理都是正确的。证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??

②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。（2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明：（1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理：前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理即根据附加前提证明法，推理正确。

离散数学复习题及答案

离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]

1. 写出命题公式﹁（P →（P ∨ Q ））的真值表。答案： 2.证明答案： 3. 证明以下蕴涵关系成立：答案： 4. 写出下列式子的主析取范式：答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化：所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?

答案：令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的则上述命题符号化为 10. 请将下列命题符号化：对于所有的正实数x,y，都有x+y≥x。答案：令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化：每个人都要参加一些课外活动。答案：令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化：某些人对某些药物过敏。答案：

令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式：答案： 15. 证明：答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明：前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?

离散数学例题整理

第一章定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律）证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)

离散数学考试题

离散数学测试题一．选择题（10*2） 1.设L (x )：x 是演员，J (y )：y 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( ) (A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→? (C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 2.令F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为（） A.?x(F(x)∧G(x))∧?x(G(x)→?F(x)) B.?x(F(x)→G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)→G(x))∧?x(G(x)→?F(x)) 3．设R 是集合A={a,b,c,d}上的二元关系， R={,,,,,,}，则R 具有关系的哪些性质（） A.自反性、反对称性 B.反自反性、传递性 C.自反性、对称性 D.反对称性、传递性 4．设A ＝{1，2}，B ＝{a,b,c}，C ＝{c,d}，则A ×（B ∩C ）为（） A ．{},1,2,c c <><> B ．{}1,,2,c c <><> C ．{},1,,2c c <><> D ．{}1,,,2c c <><> 5．设A={a,b,c,d}，A 上的等价关系R={,,,}∪I A ，则对应于R 的A 的划分是（） A ．{{a},{b,c},{d}} B ．{{a,b},{c},{d}} C ．{{a},{b},{c},{d}} D ．{{a,b},{c,d}} 6．设A ＝{a,b}，则A 的幂集P （A ）为（） A ．{a,b} B ．{Φ,{a},{b}} C ．{Φ,{a,}} D ．{Φ,{a},{b},{a,b}} 7、设A , B , C 都是集合，如果A ?C ＝B ?C ，则有( ) (A) A ＝B (B) A ≠B (C) 当A －C ＝B －C 时,有A =B (D) 当C =U 时, 有A ≠B 8．集合A ＝{1,2,3，4，5，6，7，8，9，10}，A 上的整除关系是一个偏序关系，则元素10是集合A 的（）． A ．最大元； B ．最小元； C ．极大元； D ．极小元 9．设R 为实数集，映射f ：R →R ，f （x ）＝-x 2+2x-1，则f 是（） A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不

离散数学试题及答案(1)

离散数学试题及答案一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

离散数学题目大汇总

离散数学试题一（A 卷答案）一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。七、（15分）若是群，H 是G 的非空子集，则是的子群对任意的a 、b ∈H 有 a * b －1∈H 。八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗离散数学试题一（B 卷答案）一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w

离散数学复习题及标准答案

1. 写出命题公式﹁（P →（P ∨ Q)）的真值表。答案： 2.证明答案: 3. 证明以下蕴涵关系成立：答案：４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?

5．构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ答案: ①s →ｔ前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨

７. 请将下列命题符号化：所有鱼都生活在水中。答案：令 F （ x )：ｘ是鱼Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8．请将下列命题符号化: 存在着不是有理数的实数。答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令Ｍ(ｘ)：x 是人Ｃ（x):x 是聪明的则上述命题符号化为１０. 请将下列命题符号化：对于所有的正实数x,y ，都有x+y ≥ｘ。答案: 令P(x):x 是正实数Ｓ（ｘ,y): x+y ≥x １１．请将下列命题符号化：每个人都要参加一些课外活动。答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??

离散数学期末练习题-(带答案)

离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）

离散数学章练习题及答案

离散数学练习题第一章一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。二．将下列命题符合化 1. 7不是无理数是不对的。解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r

离散数学复习题及答案

1. 写出命题公式﹁（P →（P ∨ Q ））的真值表。答案： 2.证明答案： 3. 证明以下蕴涵关系成立：答案： 4. 写出下列式子的主析取范式：答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?

5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨

7. 请将下列命题符号化：所有鱼都生活在水中。答案：令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的则上述命题符号化为 10. 请将下列命题符号化：对于所有的正实数x,y ，都有x+y ≥x 。答案：令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化：每个人都要参加一些课外活动。答案：令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??

离散数学复习题

一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B.

《离散数学》试习题及答案