离散数学复习知识点

习知识点：

命题、真命题、假命题 命题符号化（连接词）

设P：天下大雨，Q：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为（ D ）

A．PQ B．PQ C．PQ D．PQ

设P：只有你通过了大学英语六级考试，Q：你是英语专业的学生，R：你可以选修这门课程。命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课程”( B ) A．(PQ)R C．(PQ)R 3． 4． 5．

什么是命题公式 命题公式的等价式

利用逻辑等价关系证明下面的等价关系

B．(PQ)R

D．(PQ)R

证明： 6． 7．

用真值表法求命题公式的主析取范式和主合取范式 符号化以下语句，并推证结论的有效性。

有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。

解：设论述域为全总个体域，S(x)：x是学生，T(x)：x是老师，P(x)：x是骗子，L(x,y)：x相信y。将前提和结论符号化为

（1）x(S(x)y(T(y)L(x,y))) P （2）S(a)y(T(y)L(a,y)) T1，ES （3）S(a) T2，I （4）y(T(y)L(a,y)) T2，I （5）T(b)L(a,b) T4，US （6）x(S(x)y(P(y)L(x,y))) P （7）S(a)y(P(y)L(a,y)) T6，US （8）y(P(y)L(a,y)) T3,7，I （9）P(b)L(a,b) T8，US （10）L(a,b)P(b) T9，E （11）T(b)P(b) T5,10，I （12）x(T(x)P(x)) T11，UG

侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实：

（1） 是营业员甲或营业员乙作案。 （2） 如果是甲作案，则案发在非营业时间。 （3） 如果乙提供的证词可信，则案发时货柜未上锁。 （4） 如果乙提供的证词不可信，则案发在营业时间。 （5） 货柜在案发时上锁了。

侦查员推断是营业员乙作案，请用命题逻辑判断该推断是否正确。 解：设P：甲作案；Q：乙作案；R：发在营业时间；S乙的证词可信； T：案发时货柜未上锁。

由题意可知，前提为：PQ，PR，ST，SR，T 推理过程：

（1）T P （2）ST P （3）S T1，2，I （4）SR P

（5）R T3，4，I （6）PR P （7）P T5，6，I （8）PQ P （9）PQ T8，E （10）Q T7，9，I 所以PQ，PR，ST，SR，TQ 第2章 8． 9．

谓词的定义、量词包括： 什么是谓词公式

10． 谓词公式的自由变元、约束变元、辖域

11． 自然语句的符号化：比如：所有的狼都吃人，设T(x)表示为x是狼，C(x)表示为x吃人。x(T(x)C(x))

12． 判断什么是前束范式，xyG(x,y)H(x,y)是前束范式，xy(P(x,y)Q(x))是前束范式

13． 证明x(A(x)B(x))xA(x)xB(x)

x(A(x)B(x))证明：

第31.集空集

x(A(x)B(x))xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)章

合的元素、集合的基数、集合的子集、集合的运算 的问题（空集的基数、空集与集合的子集、真子集的

关系）

幂集的问题（集合幂集的求法，幂集的基数） 下面那个命题是不正确的是（ A ） A．

B．{} C． D．{}

下面那个命题是不正确的是（ A ） A．{}

B．{}{} C．{{}} D．{}

下列命题中不正确的是（ ） A.x{x}-{{x}}

C.A={x}∪x,则xA且xA

B.{x}{x}-{{x}} D.A-B=A=B

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

B.PQ D.Q=P

设A={a,{a}}，下列命题错误的是（ B ） A．{a}(A)

B．{a}(A) C．{{a}}(A) D．{{a}}(A)

在0（ D ）之间写上正确的符号。 A．=

B．  C．  D．

判断下列命题哪个为真?（C）

A．空集只是非空集合的子集 B．空集是任何集合的真子集

C． A-B=B-AA=B D．若A的一个元素属于B，则A=B 判断下列命题哪几个正确？（ B ）

A．若A∪B＝A∪C，则B＝C B．{a, b}={b, a} C．（A∩B）（A）∩（B），（(S)表示S的幂集） D．若A为非空集，则AA∪A成立 设A={a, b}， B={c}。求下列集合：

（1）A{0, 1}B； （2）B2?A； （3）(AB)2； （4） (A)A。 解：

（1）A{0, 1}B={, , , }； （2）B2A={, }；

（3）(AB)2={, , , }； （4） (A)A={<Ф, a>, <Ф, b>, <{a}, a>, <{a}, b>, <{b}, a>, <{b}, b>, , }。 关系

1. 设A={a,b,c}，则A上的二元关系有 23*3 或512 个 。

2. 集合A={1, 2, …, 10}上的关系R={：x+y=10, x, yA}，则R 的性质为（B）

A．自反的 B．对称的 C．传递的，对称的 D．传递的 设A={Ф, {1}, {1, 3}, {1, 2, 3}}，则A上包含关系“”的哈斯图为（C）

{1,2,3}{1,2,3}{1}{1,3}{1}{1,3}A．

Æ B．

Æ

{1,2,3}{1,2,3}{1,3}{1}{1}{1,3} C．

Æ D．

Æ

集合A上的等价关系的三个性质是 自反性 、 对称性 和 传递性 。 集合A上的偏序关系的三个性质是自反性 、 反对称性 和 传递性 。 A上的偏序关系的Hasse图如下。

（1）下列哪些关系式成立：ab，ba，ce，ef，df，cf； （2）分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：

（a）A； （b）{b, d}； （c）{b, e}； （d）{b, d, e}。 解：

（1） ba，ce，df，cf成立；

（2）（a）的极大元为a, e, f，极小元为c；无最大元，c是最小元；

无上界，下界是c；无上确界，下确界是c。

（b）的极大元为b, d，极小元为b, d；无最大元和最小元； 上界是e，下界是c；上确界是e，下确界是c。 （c）的极大元为e，极小元为b；最大元是e，b是最小元； 上界是e，下界是b；上确界是e，下确界是b。

（d）的极大元为e，极小元为b,d；最大元是e，无最小元； 上界是e，下界是c；上确界是e，下确界是c。 设A={2，3，4}，B={2，4，7，10，12}从A到B的关系

R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系R及其逆关系R1是否为函数？为什么？

解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}，则R的关系图为：

R的关系矩阵为

A 2 3 4 B 2 4 7 10 12 关系R不是A到B的函数， 因为元素2，4的象不唯一 逆关系R1也不是B到A的函数 因为元素7的象不存在． 下列函数是双射的为（A）。

A．f : ZE , f (x) = 2x B．f : NNN, f (n) =设Z、N、E分别为整数集，自然数集，偶数集，则下列函数是双射的为（ A ） A．f : ZE , f(x)2x B．f : ZE , f(x)8x

C．f: ZZ, f(x)8 D．f : NNN, f(n)n,n1 设A{a,b,c},B{1,2,3}，则下列关系中能构成A到B函数的是（ C ） A．f1{a,1,a,2,a,3} B．f2{a,1,b,1,b,2} C．f4{a,1,b,1,c,1} D．f1{a,1,a,2,b,2,c,3} 设函数f:BC，g:AB都是单射，则fg:AC（ A ）

A．是单射 B．是满射 C．是双射 D．既非单射又非满射

设函数f:BC，g:AB都是满射，则fg:AC（ B ）

A．是单射 B．是满射 C．是双射 D．既非单射又非满射

设f,g是自然数集N上的函数,xN,f(x)x1,g(x)2x，

则fg(x)2x1，gf(x)2(x1)．

关系F={,,}是函数 （ 对 ） 关系F={,}是函数 （ 错 ） 设图G的邻接矩阵为 则G的边数为( B )．

A．6 B．5 C．4 D．3 已知图G的邻接矩阵为

则G有（ D ）．

，

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( D )．

图四

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 在自然数集N上，运算 C 是不可结合的。

A．a*b=a+b+3 B．a*b=min{a,b} C．a*b=a+2b D．a*b=a·b(mod 3)

Q是有理集，（其中*为普通乘法）不能构成（ A ）。

A．群 B．独异点 C．半群 D．交换半群 设G,是个含幺半群，则对任意的aA有aae，其中e是幺元.试证明

G,是个阿贝尔群.

证明: 首先来证明G,是个群（只需证明每个元素均可逆），由条件知，对任意的元素aG，有aaaae，所以a1a.

其次，来证明运算可交换.对任意的a,bG，所以 aba1b1(ba)1ba. 因此，G,是个阿贝尔群.

有理数集Q中的定义如下：ababab （1）Q,是半群吗？是可交换的吗？ （2）求单位元.

（3）指出哪些是可逆元，并指出其逆元是什么？ Q中是否有可逆元？若有，

解:（1）a,b,cQ， 因a*(b*c)a*(bcbc)

a(bc)(ab)c，故*是可交换的. Q,是半群.因abba,a,bQ，(2)设e为其单位元，则应有: aQ,aeeaa，即aeaea，由a的任意性，有e0.所以单位元为0.

（3）设a是可逆的，其逆元为b，则应有：ababab0，所以当a1时，有逆元，其逆元为：a1a，当a1时，没有逆元.

a1设G,是群，则a,bG，则(a*b)-1=b-1*a-1。

证明：由于G,是群，则a,bG,设a的逆元为a-1,b的逆元为b-1,则 (a*b)*( b-1*a-1)=a*(b*b-1)*a-1 =(a*e)*a-1 =a*a-1

=e 所以，(a*b)-1=b-1*a-1。