2017离散数学15)

06任务_0001

试卷总分：100 测试时间：0

一、单项选择题（共10 道试题，共100 分。）

1. 命题公式的析取范式是( )．

A.

B.

C.

D.

2. 设个体域为整数集，则公式"x$y(x+y=0)的解释可为( )．

A. 存在一整数x有整数y满足x+y=0

B. 任一整数x对任意整数y满足x+y=0

C. 对任一整数x存在整数y满足x+y=0

D.

存在一整数x对任意整数y满足x+y=0

3. 下列公式成立的为( )．

A. ?P∧?Q ?P∨Q

B. P→?Q??P→Q

C. Q→P? P

D. ?P∧(P∨Q)?Q

4. 下列公式中( )为永真式．

A. ?A∧?B ??A∨?B

B. ?A∧?B ??(A∨B)

C. ?A∧?B ?A∨B

D. ?A∧?B ??(A∧B)

5. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符

号化为( )．

A.

B.

C.

D.

6. 命题公式(P∨Q)→R的析取范式是( )

A. ?(P∨Q)∨R

B. (P∧Q)∨R

C. (P∨Q)∨R

D. (?P∧?Q)∨R

7. 命题公式（P∨Q）的合取范式是( )．

A. （P∧Q）

B. （P∧Q）∨（P∨Q）

C. （P∨Q）

D. ?（?P∧?Q）

8. 设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别

是( )．

A. 0, 0, 0

B. 0, 0, 1

C. 0, 1, 0

D. 1, 0, 0

9. 命题公式P→Q的主合取范式是( )．

A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ)

B. ?P∧Q

C. ?P∨Q

D. P∨?Q

10. 下列等价公式成立的为( )．

A. ?P∧P??Q∧Q

B. ?Q→P?P→Q

C. P∧Q?P∨Q

D. ?P∨P?Q

06任务_0002

试卷总分：100 测试时间：0

一、单项选择题（共10 道试题，共100 分。）

1. 命题公式(P∨Q)→Q为( )

A. 矛盾式

B. 可满足式

C. 重言式

D. 合取范式

2. 设个体域为整数集，则公式"x$y(x+y=0)的解释可为( )．

A. 存在一整数x有整数y满足x+y=0

B. 任一整数x对任意整数y满足x+y=0

C. 对任一整数x存在整数y满足x+y=0

D.

存在一整数x对任意整数y满足x+y=0

3. 命题公式的析取范式是( )．

A.

B.

C.

D.

4. 下列等价公式成立的为( )．

A. ?P∧P??Q∧Q

B. ?Q→P?P→Q

C. P∧Q?P∨Q

D. ?P∨P?Q

5. 设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别

是( )．

A. 0, 0, 0

B. 0, 0, 1

C. 0, 1, 0

D. 1, 0, 0

6. 在谓词公式(?x)(A(x)→B(x)∨C(x，y))中，（）．

A. x，y都是约束变元

B. x，y都是自由变元

C. x是约束变元，y都是自由变元

D. x是自由变元，y都是约束变元

7. 命题公式P→Q的主合取范式是( )．

A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ)

B. ?P∧Q

C. ?P∨Q

D. P∨?Q

8. 设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．

A. ?(x)(A(x)∧?B(x))

B. (?x)(A(x)∧B(x))

C. ?(?x)(A(x)→B(x))

D. (x)(A(x)∧B(x))

9. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符

号化为( )．

A.

B.

C.

D.

10. 命题公式(P∨Q)→R的析取范式是( )

A. ?(P∨Q)∨R

B. (P∧Q)∨R

C. (P∨Q)∨R

D. (?P∧?Q)∨R

06任务_0003

试卷总分：100 测试时间：0

一、单项选择题（共10 道试题，共100 分。）

1. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符

号化为( )．

A.

B.

C.

D.

2. 下列公式成立的为( )．

A. ?P∧?Q ?P∨Q

B. P→?Q??P→Q

C. Q→P? P

D. ?P∧(P∨Q)?Q

3. 下列公式( )为重言式．

A. ?P∧?Q?P∨Q

B. (Q→(P∨Q)) ?(?Q∧(P∨Q))

C. (P→(?Q→P))?(?P→(P→Q))

D. (?P∨(P∧Q)) ?Q

4. 命题公式(P∨Q)→R的析取范式是( )

A. ?(P∨Q)∨R

B. (P∧Q)∨R

C. (P∨Q)∨R

D. (?P∧?Q)∨R

5. 命题公式P→Q的主合取范式是( )．

A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ)

B. ?P∧Q

C. ?P∨Q

D. P∨?Q

6. 在谓词公式(?x)(A(x)→B(x)∨C(x，y))中，（）．

A. x，y都是约束变元

B. x，y都是自由变元

C. x是约束变元，y都是自由变元

D. x是自由变元，y都是约束变元

7. 下列公式中( )为永真式．

A. ?A∧?B ??A∨?B

B. ?A∧?B ??(A∨B)

C. ?A∧?B ?A∨B

D. ?A∧?B ??(A∧B)

8. 设A（x）：x是书，B（x）：x是数学书，则命题“不是所有书都是数学书”可

符号化为（）．

A. ┐(?x)(A(x)→B(x))

B. ?(x)(A(x)∧B(x))

C. (?x)(A(x)?B(x))

D. ?(x)(A(x)∧?B(x))

9. 设个体域D={a, b, c}，那么谓词公式消去量词后的等值式

为．

A. (A(a)∨A(b)∨A(c))∨(B(a)∧B(b)∧B(b))

B. (A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(b))

C. (A(a)∨A(b)∨A(c))∨(B(a)∨B(b)∨B(b))

D. (A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(b))

10. 前提条件的有效结论是( )．

A. P

B. ?P

C. Q

D. ?Q

06任务_0004

试卷总分：100 测试时间：0

一、单项选择题（共10 道试题，共100 分。）

1. 下列公式成立的为( )．

A. ?P∧?Q ?P∨Q

B. P→?Q??P→Q

C. Q→P? P

D. ?P∧(P∨Q)?Q

2. 命题公式(P∨Q)→R的析取范式是( )

A. ?(P∨Q)∨R

B. (P∧Q)∨R

C. (P∨Q)∨R

D. (?P∧?Q)∨R

3. 设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．

A. ?(x)(A(x)∧?B(x))

B. (?x)(A(x)∧B(x))

C. ?(?x)(A(x)→B(x))

D. (x)(A(x)∧B(x))

4. 下列公式( )为重言式．

A. ?P∧?Q?P∨Q

B. (Q→(P∨Q)) ?(?Q∧(P∨Q))

C. (P→(?Q→P))?(?P→(P→Q))

D. (?P∨(P∧Q)) ?Q

5. 表达式中的辖域是( )．

A. P(x, y)

B. P(x, y)∨Q(z)

C. R(x, y)

D. P(x, y)∧R(x, y)

6. 命题公式（P∨Q）的合取范式是( )．

A. （P∧Q）

B. （P∧Q）∨（P∨Q）

C. （P∨Q）

D. ?（?P∧?Q）

7. 下列等价公式成立的为( )．

A. ?P∧P??Q∧Q

B. ?Q→P?P→Q

C. P∧Q?P∨Q

D. ?P∨P?Q

8. 在谓词公式(?x)(A(x)→B(x)∨C(x，y))中，（）．

A. x，y都是约束变元

B. x，y都是自由变元

C. x是约束变元，y都是自由变元

D. x是自由变元，y都是约束变元

9. 命题公式(P∨Q)→Q为( )

A. 矛盾式

B. 可满足式

C. 重言式

D. 合取范式

10. 设个体域D={a, b, c}，那么谓词公式消去量词后的等值式

为．

A. (A(a)∨A(b)∨A(c))∨(B(a)∧B(b)∧B(b))

B. (A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(b))

C. (A(a)∨A(b)∨A(c))∨(B(a)∨B(b)∨B(b))

D. (A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(b))

06任务_0005

试卷总分：100 测试时间：0

一、单项选择题（共10 道试题，共100 分。）

1. 命题公式P→Q的主合取范式是( )．

A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ)

B. ?P∧Q

C. ?P∨Q

D. P∨?Q

2. 设个体域D是整数集合，则命题"x$y (x×y = y)的真值是（）．

A. T

B. F

C. 不确定

D. 以上说法都不是

3. 命题公式的析取范式是( )．

A.

B.

C.

D.

4. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符

号化为( )．

A.

B.

C.

D.

5. 设个体域为整数集，则公式"x$y(x+y=0)的解释可为( )．

A. 存在一整数x有整数y满足x+y=0

B. 任一整数x对任意整数y满足x+y=0

C. 对任一整数x存在整数y满足x+y=0

D.

存在一整数x对任意整数y满足x+y=0

6. 命题公式(P∨Q)→R的析取范式是( )

A. ?(P∨Q)∨R

B. (P∧Q)∨R

C. (P∨Q)∨R

D. (?P∧?Q)∨R

7. 下列公式成立的为( )．

A. ?P∧?Q ?P∨Q

B. P→?Q??P→Q

C. Q→P? P

D. ?P∧(P∨Q)?Q

8. 设个体域D={a, b, c}，那么谓词公式消去量词后的等值式

为．

A. (A(a)∨A(b)∨A(c))∨(B(a)∧B(b)∧B(b))

B. (A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(b))

C. (A(a)∨A(b)∨A(c))∨(B(a)∨B(b)∨B(b))

D. (A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(b))

9. 下列公式中( )为永真式．

A. ?A∧?B ??A∨?B

B. ?A∧?B ??(A∨B)

C. ?A∧?B ?A∨B

D. ?A∧?B ??(A∧B)

10. 下列等价公式成立的为( )．

A. ?P∧P??Q∧Q

B. ?Q→P?P→Q

C. P∧Q?P∨Q

D. ?P∨P?Q

离散数学试卷答案2017.6月

浙江农林大学暨阳学院 2016 - 2017 学年第 二 学期考试卷答案 课程名称： 离散数学 课程类别： 必修 考试方式： 闭卷 适用专业： 计算机151-152 注意事项：1、本试卷满分100分。 2、考试时间 120分钟。 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案， 并将正确答案的选项填在题后的括号内。每小题2分，共8分） 1. 公式q p p ?→?→)(的类型是 ( C ) A. 重言式 B. 矛盾式 C. 非重言式的可满足式 D. 以上均不对 2. |A |=n , |B |=m , 且m , n >0, 则|B A |= ( D ) A.m 2 B. 2n C. n m D. m n 3. 集合的广义并}},{},,,{},,,{{d a d c a c b a ?= ( B ) A.},,{c b a B.},,,{d c b a C.},,{d c a D.}{a 4. f ：R→R, f (x )=-x 2+2x -1，则f 是 ( D ) A. 单射 B. 满射 C. 双射 D. 以上均不对 系（部） ： 专业班级： 姓名： 学号： 装 订 线 内 不 要 答 题

二、填空题（每小题3分，共36分） 1. 令p:吴颖用功, q:吴颖聪明，吴颖既用功又聪明符号化为__q p ∧_____ 2. 如果2 <1,则23≥的真值为___1___ 3. (q →p ) ∧q →p 的成真赋值为 ___00,01,10,11_ __ 4. (p →?q)→r ? 13567m m m m m ∨∨∨∨的成假赋值为__000,010,100_ 5. 设A 有3个命题变项, 且已知A= m 2∨m 4∨m 5∨m 6，A 的主合取范式为 ___7310M M M M A ∧∧∧= 6. 设D 为人类集合，G(x)：x 用左手写字，则一阶逻辑中命题有人用左手写字符号 化为__)(x xG ?__ _ 7. 给定解释 I 如下： (a) 个体域 D=R (b) 0a = (c) (,),(,)f x y x y g x y x y =+=? (d) (,):F x y x y = 则公式?xF (g (x ,y ),a ) 在I 下的解释为__)0(=??y x x _____ 8. R = {<1,2>, <2,3>, <1,4>, <2,2>}，S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}， 则S ?R = __{1,2,1,4,3,3,3,2}<><><><>__ 9. 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R ?{2} = ___}4,2,2,2{><><___ 10. 设R 为A 上的关系, 则有R 的对称闭包s(R)=__ 1-?R R ____ 11. 设G=为任意无向图，V={v 1,v 2,…,v n }, |E|=m, 则 _m 2___ 12. 无向图G 是欧拉图当且仅当__ G 是连通图且无奇度顶点 三、名词解释（每小题3分，共18分） 1. R 为 A 上递推关系的定义为： 设R 为A 上的关系,若 ),,,,,(R z x R z y R y x A z y x z y x >∈→<>∈<∧>∈<∧∈??? 则称R 为A 上的传递关系 2. R 为A 上的偏序关系的定义为： 如果R 是自反的、反对称的和传递的，则称R 为A 上的偏序关系 3. F 为单射函数的定义为： =∑=n i i v d 1 )(

离散数学-刘任任版 第15章习题答案

第十五章习题解答 1. ()()x xS x xR ?∧?)1( ())()()()()()()(c S b S a S c R b R a R ∨∨∧∧∧解： ())()()2(x Q x P x →? ))((()()()()())()(c Q c P b Q b P a Q a P →∧→∧→解： )()()3(x xP x P x ?∨?? )(()()()())()()(c P b P a P c P b P a P ∧∧∨?∧?∧?解： 2. 指出下列命题的真值： ??-=>=>∨→?}6,3,2{,5:,"5:")(,"3:")(,"23:",)())(((1)D e x x R x x Q P e R x Q P x 论域其中 ).2.(:时不成立为当假解-x 。论域其中，}2{,"4:")(,"3:")() ()(()2(==>→?D x x Q x x P x Q x P x 解：真。 3. 在一阶逻辑中，将下列命题符号化： （1）凡有理数均可表示为分数。 解：P(x)： x 是有理数； Q （x ）:x 可表示为分数。 ))()((x Q x P x →?

())())()((. :,:)(,:)(:. ,)4()) ()((. :)(:)()3()(:)(:)()2(x S x P x W W x x S x x P x Q x P x x x Q x x P x Q x P y x x Q x x P ∧?→→??∧??明天天气好是学生是公园解有一些学生将去公园如果明天天气好是有理数是实数，解：数。 并非所有实数都是有理。 是有理数。 是实数，解：有些实数是有理数。 );()), ()((,,:) ()())()(()1(. ,.4|))) )()(|,(),(()()0,(() ,(:)(,:),(:. |)()(|: ,),,(,0)6())). ,()(()((:),(,:)(:)()5(00000x R x Q x P x x z z Q x xR x Q x P x x f x f G N n G n N x S G x b a x x S y x y x G x f x f N n N b a x x y G y Q y x P x y x y x G x x Q x x P n n 第二个是的作用域是第一个约束变元自由变元解并指出各量词的作用域变元和约束变元指出下列公式中的自由解时有使当都存在对任意给是实数是正实数，解：在大于该实数的实数。 对任意的正实数，都存∧?∧?→∧?-∧??→ ∧??∈><->∈>∧?→?>εεεεε (2)))()(())(()((z Q x xP y Q y x P x →?∨?∧? 解：自由变元z ，约束为元：x ，y 。第一个的作用域为 第二个的作用域为第二个P(x)；第二个的作用域的作用域为 Q(y) （3）)()())()((z s y yR x Q x P x ∧?∧?? 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 y ?的作用域为R(y)

2017离散数学答案(6--10)

04任务_0006 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )． A. （a）只是弱连通的 B. （b）只是弱连通的 C. （c）只是弱连通的 D. （d）只是弱连通的 2. 设无向图G的邻接矩阵为 ， 则G的边数为( )． A. 1 B. 6 C. 7 D. 14

3. 设无向图G的邻接矩阵为，则G的边数为( )． A. 6 B. 5 C. 4 D. 3 4. 无向简单图G是棵树，当且仅当( )． A. G连通且边数比结点数少1 B. G连通且结点数比边数少1 C. G的边数比结点数少1 D. G中没有回路． 5. 图G如图三所示，以下说法正确的是 ( ) ． A. {(a, d)}是割边 B. {(a, d)}是边割集 C. {(a, d) ,(b, d)}是边割集 D. {(b, d)}是边割集 6. 若G是一个汉密尔顿图，则G一定是( )． A. 平面图

B. 对偶图 C. 欧拉图 D. 连通图 7. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 8. 无向完全图K4是（）． A. 欧拉图 B. 汉密尔顿图 C. 非平面图 D. 树 9. 设图G＝，v V，则下列结论成立的是 ( ) ． A. deg(v)=2|E| B. deg(v)=|E| C. D. 10. 以下结论正确的是( )． A. 无向完全图都是欧拉图 B. 有n个结点n－1条边的无向图都是树 C. 无向完全图都是平面图 D. 树的每条边都是割边 04任务_0007

离散数学第10章

第十章 3. 在R 中定义二元运算，使得,a b R ?∈有 *a b a b ab =++ 证明构成独异点 解：（1）,,R a b R φ≠?∈，存在唯一*a b a b ab R =++∈，所以为代数系统。 (2) Z z y x ∈?,,,有(*)**(*)x y z x y z xy yz xz xyz x y z =++++++=，所以结合律成立。 (3) 设存在幺元为e R ∈，对x R ?∈，幺元应满足 e x e x ex x =++= x e x e xe x =++= 所以幺元为0R ∈。 所以构成独异点 8. 设{}0,1,2,3G =,若4?为模4乘法，则4,?G 构成什么？ （2）零元为0，幺元为1，且运算表对称，结合律考虑4种情况 222,333,223,233,结合律成立。 （3）幺元为1 （4）零元为0，所以0的逆元不存在。 所以4,?G 构成半群，独异点，不能构成群。 10. 设{0,1}A x x R x =∈≠且，在A 上定义了六个函数如下： 11231 1 1 456(),(),()1()(1),()(1),()(1) f x x f x x f x x f x x f x x x f x x x ----===-=-=-=- 令F 为这6个函数构成的集合， 运算为函数合成运算 (1) 给出运算的运算表 (2) 验证,F <> 是一个群。 解：(1)

(2) a) 由运算表可得：运算封闭，且F 不是空集，所以,F <> 为一个代数系统。 b) 函数复合运算满足结合律。 c) 单位元为f1 d) f1-1=f1, f2-1=f2, f3-1=f3, f4-1=f5, f5-1=f4, f6-1 =f6, 所以,F <> 为群

离散数学第八章一些特殊的图知识点总结

图论部分 第八章、一些特殊的图 8.1 二部图 二部图：定义设无向图G=, 若能将V 划分成V1 和V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为, 称V1和V2为互补顶点子集. 完全二部图：又若G是简单图, 且V1中每个顶点都与V2中每个顶点相邻, 则称G为完全二部图, 记为K r,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图. 匹配：设G=, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为β1 例下述3个图的匹配数依次为3, 3, 4.

设M为G中一个匹配 v i与v j被M匹配: (v i,v j)∈M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 定理(Hall定理) 设二部图G=中，|V1|≤|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配. 定理设二部图G=中, 如果存在t≥1, 使得V1中每个顶点至少关联t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配.

Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为t 条件. 满足t 条件的二部图一定满足相异性条件. 8.2 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.

2017离散数学答案(1--5)

02任务_0001 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A. {a，{a}}A B. {1，2}A C. {a}A D. A 4. 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}， 则h =（）． A. f?g B. g?f C. f?f D. g?g

5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（）． A. 1024 B. 10 C. 100 D. 1 9. 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A. 0 B. 2

2017离散数学答案1--5)(2)

06任务_0001 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 命题公式的析取范式是( )． A. B. C. D. 2. 设个体域为整数集，则公式"x$y(x+y=0)的解释可为( )． A. 存在一整数x有整数y满足x+y=0 B. 任一整数x对任意整数y满足x+y=0 C. 对任一整数x存在整数y满足x+y=0 D. 存在一整数x对任意整数y满足x+y=0 3. 下列公式成立的为( )． A. ?P∧?Q ?P∨Q B. P→?Q??P→Q C. Q→P? P D. ?P∧(P∨Q)?Q 4. 下列公式中( )为永真式． A. ?A∧?B ??A∨?B B. ?A∧?B ??(A∨B) C. ?A∧?B ?A∨B

D. ?A∧?B ??(A∧B) 5. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符 号化为( )． A. B. C. D. 6. 命题公式(P∨Q)→R的析取范式是( ) A. ?(P∨Q)∨R B. (P∧Q)∨R C. (P∨Q)∨R D. (?P∧?Q)∨R 7. 命题公式（P∨Q）的合取范式是( )． A. （P∧Q） B. （P∧Q）∨（P∨Q） C. （P∨Q） D. ?（?P∧?Q） 8. 设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别 是( )． A. 0, 0, 0 B. 0, 0, 1 C. 0, 1, 0 D. 1, 0, 0 9. 命题公式P→Q的主合取范式是( )． A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ)

B. ?P∧Q C. ?P∨Q D. P∨?Q 10. 下列等价公式成立的为( )． A. ?P∧P??Q∧Q B. ?Q→P?P→Q C. P∧Q?P∨Q D. ?P∨P?Q

离散数学2017秋综合练习题

离散数学综合练习题 一、判断下列命题是否正确．如果正确，在题后括号内填“\/”； 否则，填“?” （1）空集是任何集合的真子集． （ ） （2）{ }φ是空集． （ ） （3）{}{ }a a a },{∈ （ ） （4）如果B A a ??，则A a ?或B a ?． （ ） （5）设集合},,{321a a a A =，},,{321b b b B =，则 },,,,,{332211><><><=?b a b a b a B A （ ） （6）设集合}1,0{=A ，则 }1},0{,0},0{,1,,0,{><><><><=φφρ 是A 2到A 的关系． （ ） （7）关系的复合运算满足交换律． （ ） （8）设21,ρρ为集合 A 上的等价关系, 则21ρρ?也是集合 A 上的等价关系 ( ) （9）设ρ是集合A 上的等价关系, 则当ρ>∈?<,G 是群．如果对于任意G b a ∈,，有 222)(b a b a ?=? 则>?<,G 是阿贝尔群． （ ） （14）设a 是群>?<,G 的元素，记 }|{y a a y G y y H ?=?∈=且 则>?<,H 是>?<,G 的子群． （ ） （15）<{0，1，2，3，4}，max ，min>是格． （ ） （16）设a ，b 是格>∧∨<,,L 的任意两个元素，则 a b a b b a =∧?=∨． （ ） （17）设>∧∨<,,,B 是布尔代数，则>∧∨<,,B 是格． （ ） （18）设集合},{b a A =，则>??<,},},{},{,{A b a φ是格． （ ） （19）设>∧∨<,,,B 是布尔代数，则对任意B b a ∈,，有 b a b a ∨=∧． （ ） （20）设>∧∨<,,,B 是布尔代数，则对任意B a ∈，都有B b ∈，使得 0,1=∧=∨b a b a ． （ ） （21）n 阶完全图的任意两个不同结点的距离都为1. （ ） （22）在有向图中，结点i v 到结点j v 的有向短程即为j v 到i v

离散数学 章节练习 1 KEY

离散数学 章节练习 1 范围：命题逻辑 班级：________________ 学号：________________ 姓名： ________________ 一、单项选择题 1.给定如下4个语句，其中是命题的是 ( ) A.现在开始考试！ B. 我正在考试。 C.我正在说谎话。 D. 你是大学生吗? 2. 设p:17=5,q 地球是方的,r ：4×4>8,s 现在是夏季,结果为真 的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 3.给定如下4个语句，其中是复合命题的是 ( ) A. 我会游泳。 B.如果天不下雨,我就去踢足球。 C.新闻联播每天都有。 D.火星上有人吗? 4.命题公式(p ∧q)→q 为 ( ) A.矛盾式； B.可满足式； C.重言式； D.合取范式。 5．设P ：我是青年学生，Q ：我有社会责任感。命题：“除非 我不是青年学生，否则我有社会责任感”符号化正确的是 ( ) A ．?P ∧Q B ． P →?Q C ．?P →?Q D ．?Q →?P 6. 下列命题公式为重言式的是 ( ) A ．(P ∨?P)→Q B ．P →(P ∨Q) C ．Q ∧?Q D ．P →?Q 7.命题逻辑中一组公式H 1，H 2， ···,H n .，C ，存在关系H 1∧ H 2∧···∧H n ?C 当且仅当H 1∧H 2∧···∧H n →C 是 ( ) A. 矛盾式。 B. 永假式。 C. 可满足式。 D. 永真式。 8.给定如下4个语句，其中是不是命题的是 ( ) A.我现在在考试 B. 今天没有下雨 C.如果你来，我就来 D. 2X+3>8 9. 设p:现在是白天,q ：1中国比日本人口少，,r ：猪是可以飞 的,s 我是女生,结果为真的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s ∨q →q ∧r D. (p ∧r)∨(q ∧s) 10.公式p ∧ q ∨ r 合取范式是 ( ) A. (p ∧r)∨(q ∧r) B. (p ∨r) ∧ (q ∨r) C. (p ∨q) ∧ (q ∨r)) D. (p ∨q) ∧ (p ∨r)) 11. 命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为 ( ) A ．0 B ．1 C ．2 D ．3 。 12. 下列语句中，是命题的是。 ( ) A 请把门关上 B 地球外的星球上也有人 C x + 5 > 6 D 下午有会吗？ 13. 设p:17>5,q:正常人会走路,r ：美国不在亚洲,s:太阳比月亮 小，结果为假的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (?p ∧r)∨( ?q ∧s) 14. 命题公式((p →q) →(?q →?p)) ∨r 的类型是 ( ) A. 永真式。 B.永假式。 C. 非永真式可满足式。 D. 重言式 15.给定如下4个语句，其中是真命题的是 ( ) A.冬天会下雪 B. 请给我一个苹果 C.我正在说谎话。 D. 3+4<20 16.下烈公式中是矛盾式的是 ( ) A ． r →p ∧s B. p ∨?p → p ∧?p C. s →q ∧r D. (p ∧r)∨(q ∧s) 17. 对命题“除非交通阻塞，否则他不会迟到”符号化（p ：交通阻塞，q:他迟到）后的公式正确的是 ( ) A. p →?q B. p →q C.q →p D. ? p →q 18.给定如下4个语句，其中是命题的是 ( ) A.2055年元旦会下雪。 B. 我是一名在校大学生？ C.我现在说的不是真话。D. 请向国旗敬礼！ 19. 设p:我是少先队员,q 太阳每天从东方升起,r ：黄山是世界上最高的山,s 所有人都喜欢中国,结果为假的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 20.公式(p ∧r)∨(p ∧s)的主析取范式中有几个最小项 ( ) A.1 B. 3 C. 5 D.7 21. 下列是真命题的有 ( ) A ．3>7； B ．不是每一个人都会飞； C ．你不能说假话； D ．有的人会飞。 22. 下列公式中为永真式的公式是 ( ) A ． r → r ∨（p ∧s ） B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 23.给定如下4个语句，其中是假命题的是 ( ) A.这次，我一定要考好！ B. “15>27”是错的 C.我正在说谎话。 D.15>27 24.下列公式为永假式的是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r) ∧ (?p ∧s) 25. 设 p ：天冷，q ：小王穿羽绒服，命题“除非天冷，小王 才穿羽绒服”.符号化为 ( ) A ．p →q B. q →p C ．?q →p D . q →?p 26.下列公式中，不是p →(q →p)的代换实例的是 ( ) A. F(x,y)→(G(x,y)→F(x,y)) B. F(x,y)→G(x,y)→F(x,y) C. F(y,x)→(G(x,y)→F(x,y)) D. F(x,y)→(G(x,y)→F(y,x)) 27.给定如下4个语句，其中是假命题的是 ( ) A.请来北京参加会议！ B. 北京是中国的首都。 C 上海人口比长沙多 D. 中国人均身高2.48米 28. 下面那个公式不是可满足式 ( ) A ． r →p ∧s B. p →q ∧r

2017离散数学答案(1--5)

02 任务_0001 试卷总分：100 测试时间：0 单项选择题 一、单项选择题(共10道试题，共100 分。) 1. 设集合A = {1, a },则P(A)=( ). A {{1}, { a}} 厂 B. {0{1}, { a}} 厂 C. {{1}, { a}, {1, a }} P D. EU, { a}, {1, a }} 2. 集合A={1,2, 3, 4} 上的关系R={<χ，y>∣χ=y且x, y A},则R的性质为 ( )? A. 不是自反的 厂B.不是对称的 R C.传递的 D.反自反 3. 若集合A= { a , {a}, {1 , 2}},贝U下列表述正确的是()? A. {a, {a}} A C B. {1 , 2}H A * C. {a}l」A 厂D.佻A 4. 设集合A ={1 , 2, 3} 上的函数分别为：f = {<1,2> , <2, 1> , <3, 3>} , g = {<1, 3>, <2, 2> , <3, 2>} , h = {<1,3> , <2, 1> , <3, 1>}, 则h =( ). * A. f?g B. g?f 厂 C. f?f C D. g?g

4. 设集合 A={1 , 2 , 3 , 4}上的二元关系 R={<1, 1>, <2, 2>, <2, 3>, <4, 4>}, S={<1, 1>, <2, 2>, <2, 3>, <3, 2>, <4, 4>},则 S 是 R 的（ ）闭包. A.自反 B.传递 C.极大元 .极小元 8. 若集合A 的元素个数为10,则其幕集的元素个数为（ .1024 9. 如果R i 和R 是A 上的自反关系，则R U R b R ∩ R ,R-R 中自反关系有（ ） 个. A. 0 B. 2 C.对称 设集合A ={1 , 2, 3, 4, 5},偏序关系■<是 A 上的整除关系，则偏序集

离散数学复习

离散数学复习 第一章命题逻辑基本概念 1．掌握命题及相关概念 2．理解各联结词的逻辑关系 3．会将复合命题符号化 4．会求公式的真值表，并用它求公式的成真赋值、成假赋值及判断公式的类型 第二章命题逻辑等值演算 1．记住基本等值式，会应用它们进行公式的等值演算 2．了解简单析取式、简单合取式、析取范式、合取范式的概念 3．理解极大项、极小项的概念 4．掌握求主析取范式和主合取范式的方法(等值演算和真值表法) 5．会用主范式判断公式的类型及进行简单应用 6．了解联结词完备集的概念 第三章命题逻辑的推理理论 1．理解并记住推理形式结构的两种形式： (1) A1∧A2∧…∧A k→B (2) 前提：A1, A2, … , A k 结论：B 2．掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）3．记住自然推理系统P系统中的推理规则 4．掌握自然推理系统P系统中的推理方法 第四章一阶逻辑基本概念 1．会进行命题的符号化 2．理解公式的解释 3．理解永真式、矛盾式、可满足式的概念及相互之间的关系 4．对于给定的解释会判断公式的真值，或判定真值不确定（即仍不是命题） 第五章一阶逻辑等值演算与推理 1．理解并记住重要等值式，并能熟练地应用它们 2．会使用置换规则、换名规则(约束条变项)、代替规则(自由变项) 3．会求给定公式的前束范式 4．正确地使用UI, UG, EG, EI规则，特别要注意它们之间的关系 5．在F系统，对给定的推理，正确地构造出它的证明 第六章集合代数 1. 掌握集合的表示法 2．能够判别元素是否属于给定的集合 3．能够判别两个集合之间是否存在包含、相等、真包含等关系 第七章二元关系 1. 掌握二元关系、空关系、全域关系、恒等关系、关系的定义域、值域、域、逆关系、 左复合、右复合、限制、像的概念； 2．掌握关系的集合表达式、关系矩阵和关系图三种表示法； 3．掌握关系的基本运算和关系的幂的运算性质，掌握关系的五个性质：自反性、反自反性、对称性、反对称性和传递性等五个性质； 4．掌握关系的闭包的概念，会应用关系的性质求出关系的闭包（自反闭包、对称闭包和传递闭包）；

2017离散数学答案(6--10)

02任务_0006 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（） 个． A. 0 B. 2 C. 1 D. 3 2. 设A、B是两个任意集合，侧A-B =??( )． A. A=B B. A?B C. A?B D. B=? 3. 设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={, }，从B到C 的函数g={<1，5>, <2，4>}，则下列表述正确的是（）． A. f°g={, } B. g° f ={, } C. f°g={<5，a >, <4，b >} D. g° f ={<5，a >, <4，b >} 4. 设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的关系R={| y = x +1｝，则R= ( )． A. {<2, 3>, <4, 5>, <6, 7>}

B. {<2, 1>, <4, 3>, <6, 5>} C. {<2, 1>, <3, 2>, <4, 3>} D. {<2, 2>, <3, 3>, <4, 6>} 5. 设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如右图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）． A. 下界 B. 最小上界 C. 最大下界 D. 最小元 6. 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}， 则h =（）． A. f?g B. g?f C. f?f D. g?g 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集上的元素5 是集合A的（）． A. 最大元

离散数学第10章习题答案

第10章习题答案 1.解 (1)设G 有m 条边，由握手定理得2m ＝∑∈V v v d )(＝2＋2＋3＋3＋4＝14，所以G 的边数7条。 (2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得∑∈V v v d )(＝2m ＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有， 其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G 中至多有9个结点。 2.证明 设1v 、2v 、…、n v 表示任给的n 个人，以1v 、2v 、…、n v 为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G 。由握手定理知 ∑=n k k v d 1 )(＝3n 必为偶数，从而n 必为偶数。 3. 解 由于非负整数列d ＝(d 1，d 2，…，d n )是可图化的当且仅当∑=n i i d 1 ≡0(mod 2)，所以(1)、(2)、 (3)、(5)能构成无向图的度数列。 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为1v 、2v 、 3v 、4v ，且d(1v )＝1，d(2v )＝d(3v )＝d(4v )＝3。而1v 只能与2v 、3v 、4v 之一相邻，设1v 与2v 相邻，于 是d(3v )＝d(4v )＝3不成立，矛盾。 4.证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。 5. 解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)~(16)为其生成子图。 6. 解 (1)G 的所有子图如图所示。 (1)(3)(5) (6) (9)(10) (13) (14)

华东师范大学离散数学章炯民课后习题第10章答案

P179 1. 给出下列序列的一个递推关系： （4）{n 2+3n} （6）{1+(-1)n } 解： (4) a n =a n-1+2n+2(n>0)，a 0=0 (6) a n =a n-1+2(-1)n (n>0)，a 0=2 或110 220n n n a a a --=?=?=?，a 0=2 3. 设含连续三个0的n 位二进制串的数目是s n ，请给出{s n }的递推关系和初始条件。 解：a n = a n-1 +a n-2 +a n-3+2n-3 (n≥3)，a 0=0，a 1=0，a 2=0 4. 设{1,2,…,n}的错排列数是D n ，请给出{D n }的递推关系和初始条件。 解：D n =(n-1)(D n-1+D n-2)，D 1=0，D 2=1 10（2）求初值问题的通项公式：a n =10a n-1-25a n-2；a 0=-7，a 1=15。 解： 特征方程：r 2-10r+25=0，特征根：r 2=r 1=5 通解：a n =(α+βn)5n 由a 0=α50=α=-7和a 1= (-7+β)51 =15解得：α=-7，β=10 初值问题的解：a n =(-7+10n)2n *12（2）. 求递推关系的一个特解： a n ＝8a n-2-16a n-4+n 24n 。 解： 特征方程：x 4=8x 2-16，特征根：x 1=-2，x 2=2 一个特解：T n =n 0(a+bn+cn 2) 4n = (a+bn+cn 2)4n 代入递推关系：(a+bn+cn 2)4n =8(a+b(n-2)+c(n-2)2)4n-2-16(a+b(n-4)+c(n-4)2)4n-4 即9cn 2+(9b+8c)n+(8a+4b-16+c)=0 9c=0 9b+8c=0 8a+4b-16+c=0 解得：c=0,b=0,a=2 特解：2n 24n 13（2）. 写出序列{1,0,1,0,1,0,…}的生成函数。 解：1+x 2+x 4+x 6+…=2i 2i 01x 1x ∞ ==-∑

离散数学结构 第15章 欧拉图与哈密顿图

第十五章欧拉图与哈密顿图 15.1 欧拉图 (2) 一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义 (3) 二、判别定理 (4) 三、求欧拉图中欧拉回路的算法 (6) 1．Fleury算法，能不走桥就不走桥： (6) 2．逐步插入回路法 (7) 四、中国邮路问题 (8) 练习题： (9) 15.2哈密顿图 (11) 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 (12) 二、哈密顿图与半哈密顿图的一些必要与充分条件 (12) 练习题 (18) 15.3 带权图与货郎担问题 (24) 一、带权图 (24) 二、货郎担问题 (24)

15.1 欧拉图 主要内容： 1. 欧拉通路、欧拉回路、欧拉图、半欧拉图的定义。 2. 判别定理。 3. 求欧拉图中欧拉回路的算法。 学习要求： 1. 深刻理解欧拉通路与欧拉回路的定义以及它们的区别与联系。 2. 以无向欧拉图为例，进一步理解欧拉图的结构，即，欧拉图是若干个边不重的圈之并。 让我们先从两个例子出发，获得有关图的一些直观认识。 图论的研究起源于哥尼斯堡七桥问题。哥尼斯堡城位于Pnsel河畔，河中有两个岛，有7座桥与4块陆地彼此相连，如上图所示。 居住于该城的居民想做这样的游戏：从4块陆地的任一块出发，经过每座桥一次且仅一次，最后返回原出发地。当地的人们进行了许多次尝试，都没有成功。后来，欧拉给出了问题的解。首先欧拉将4块陆地表示成4个结点，凡陆地间有桥相连的，便在两点间连一条边，从而可将左图改画为右图如下：这样，哥尼斯堡七桥问题可描述为：能否有从A、B、C、D任一点出发，经过每条边一次且仅一次而返回出发点的回路? 欧拉证明了这样的回路是不存在的。他的理由是，从图任一点出发，要回到原出发点，要求与每个点关联的边的数目为偶数，才能保证从一条边进入某点再从另一条边出去，一进一出才能回到原出发点。而图中的顶点A、B、C和D均有奇数条边与其相关联，显然这样的回路是不存在的。 另一个例子是20世纪40年代的一个数学游戏。

离散数学答案 第十章 格和布尔代数

第十章 格和布尔代数 习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界； ⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界； ⑶是，与⑵同理； ⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。 2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。故a ∨b=b ∧c ； ⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ； 又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。即 (a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。 习题10.2 1．解 由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ?S 1; ＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ?S 2; ＜S 3,≤＞是＜L,≤＞的子格. 2．解 S 24的包含5个元素的子格有如下的8个： S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24}, S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}. 3．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是的子集，即是的子代数，故是子格。 4．证明 由(10-4)有，a ∧b ≤a ,由已知a ≤c ,由偏序关系的传递性有，a ∧b ≤c ； 同理 a ∧b ≤d 。 由(10-5)和以上两式有，a ∧b ≤c ∧d . 5．证明 因为由(10-4)有，a ∧b ≤a ，因此， (a ∧b )∨(c ∧d )≤a ∨(c ∧d ) ① 由分配不等式有， a ∨(c ∧d )≤(a ∨c )∧(a ∨d ) ② 再由由(10-4)有， (a ∨c )∧(a ∨d ) ≤a ∨c ③ 由偏序关系的传递性和①②③则有， (a ∧b )∨(c ∧d )≤a ∨c 同理 (a ∧b )∨(c ∧d )≤b ∨d 因此有， (a ∧b )∨(c ∧d )≤(a ∨c ) ∧(b ∨d )。 习题10.3 1．解 ⑴ 是，全上界是24，全下界是1； ⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。 图1 图2

2017-2018离散数学A+答案

第 1 页 共 4 页 20 - 20学年度第 学期试卷 A (闭卷) 课程名称 离散数学 二级学院 专业 计算机科学与技术 年级、班级 学号 姓名 一、填空题：（每空2分，共20分） 1．若4阶无向图G （V,E ）为完全图，则|V|= ，|E|= 2. 无向连通图G 有欧拉回路，当且仅当 。 3. 设Ａ={a,b},R={，}，求r(R) , s(R) , t(R) 。 4. 设有限集合A, |A| = 3, 则 |P(A)| = ____ ,P (A)∩A= 。 5．设有向图G=，则图G 顶点的出度和= ， 度和为 。 二、选择题：（每题2分，共10分） 1．若4阶无向图G （V,E ）为完全简单图，则包含多少条环（ ）。 （A ）5 （B ）3 （C ）6 （D ）0 2. R 是A 上关系，则R 是具有自反关系的，充要分条件是（ ）。 （A ）r(R)=R. （B ）t(R)=R （C ）s(R)=R （D ）R=I A 3. 对公式((,)(,))x y P x y Q x z ??→的说法正确的是（ ）。 （A ）x 是约束出现，y 是自由出现，z 是约束出现 （B ）x 是约束出现，y 既是约束出现又是自由出现，z 是自由出现 （C ）x 是约束出现，y 是约束出现，z 是自由出现 （D ）x 是约束出现，y 既是约束出现又是自由出现，z 是约束出现 4. 设G 、H 是一阶逻辑公式，P 是一个谓词，G ＝?xP(x), H ＝?xQ(x),则一阶逻辑公式G →H 是( )。 (A) 永真式 (B) 矛盾式 (C) 可满足的 (D) 前束范式. 5. 设A, B 为集合，当( )时A －B ＝?。 (A) A ∩B ＝? (B) A ∩B=A (C) B ?A (D) A ∩B=B. 三、计算题：（5小题，共50分） 1. (本题10分 )构造(P ∧?Q)∨R 的真值表,并说明其类别。

第十章 习题答案

第十章 博弈论初步 1.什么是纳什均衡？纳什均衡一定是最优的吗？ 解答：(1)所谓纳什均衡，是参与人的一种策略组合，在该策略组合上，任何参与人单独改变策略都不会得到好处。 (2)不一定。纳什均衡可能是最优的，也可能不是最优的。例如，在存在多个纳什均衡的情况下，其中有一些纳什均衡就不是最优的；即使在纳什均衡是唯一时，它也可能不是最优的——因为与它相对应的支付组合可能会小于与其他策略组合相对应的支付组合。 2.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡最多可有几个？为什么？ 解答：在只有两个参与人(如A 和B)且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡最多可有四个。例如，当A 与B 的支付矩阵可分别表示如下时，总的支付矩阵中所有四个单元格的两个数字均有下划线，从而，总共有四个纳什均衡。 A 的支付矩阵＝??????22211211 a a a a B 的支付矩阵＝?? ????22211211b b b b 3.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡可能有三个。试举一例说明。 解答：例如，当参与人A 与B 的支付矩阵可分别表示如下时，总的支付矩阵中恰好有三个单元格的两个数字均有下划线，从而，总共有三个纳什均衡。 A 的支付矩阵＝ ??????22211211a a a a B 的支付矩阵＝?? ????22211211b b b b 4.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，如何找到所有的纯策略纳什均衡？ 解答：可使用条件策略下划线法。具体步骤如下：首先，设两个参与人分别为左参与人和上参与人，并把整个的支付矩阵分解为这两个参与人的支付矩阵；其次，在左参与人的支付矩阵中，找出每一列的最大者，并在其下划线；再次，在上参与人的支付矩阵中，找出每一行的最大者，并在其下划线；再再次，将已经划好线的两个参与人的支付矩阵再合并起来，得到带有下划线的整个支付矩阵；最后，在带有下划线的整个支付矩阵中，找到两个数字之下均划有线的所有的支付组合。这些支付组合所代表的策略组合就是纳什均衡。 5.设有A 、B 两个参与人。对于参与人A 的每一个策略，参与人B 的条件策略有无可能不止一个。试举一例说明。 解答：例如，在如下的二人同时博弈中，当参与人A 选择上策略时，参与人B 既可以选择左策略，也可以选择右策略，因为他此时选择这两个策略的支付是完全一样的。因此，对于参与人A 的上策略，参与人B 的条件策略有两个，即左策略和右策略。 6.如果无论其他人选择什么策略，某个参与人都只选择某个策略，则该策略就是该参与人的绝对优势策略(简称优势策略)。试举一例说明某个参与人具有某个优势策略的情况。