离散数学复习知识点

1、点八、1命题、真命题、假命题2命题符号化(连接词)设P:天下大雨，Q:他在室内运动，命题“除非天下大雨，否那么他不在室内运动可符合化为( D )A P Q B P Q C P QD PQ设P:只有你通过了大学英语六级考试，Q:你是英语专业的学生，R:你可以选修这门课程。命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课 程 ( B )A (P Q) RB (P Q) RC (P Q) RD(P Q) R3什么是命题公式4命题公式的等价式5利用逻辑等价关系证明下面的等价关系证明：6用真值表法求命题公式的主析取范式和主合取范式7符号化以下语句，并推证结论的有效性有些学生相信

2、所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。解：设论述域为全总个体域，S(x) : x是学生，T(x) : x是老师，P(x) : x是骗子，L(x,y)x相信y。将前提和结论符号化为1) x(S(x) y(T(y) L(x, y)P2) S(a)y(T(y) L(a, y)T1， ES3) S(a)T2， I4) y(T(y) L(a, y)T2， I5) T(b)L(a, b)T4， US6) x(S(x) y(P(y) L(x, y)P7) S(a)y(P(y) L(a, y)T6， US8) y(P(y)L(a, y)T3,7， I9) P(b)L(a,b)T8， US1

3、0) L(a,b)P(b)T9， E11) T(b) P(b)T5,10， IT11， UG12) x(T(x) P(x)侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实： 1 是营业员甲或营业员乙作案。 2 如果是甲作案，那么案发在非营业时间。 3 如果乙提供的证词可信，那么案发时货柜未上锁。 4 如果乙提供的证词不可信，那么案发在营业时间。 5 货柜在案发时上锁了。侦查员推断是营业员乙作案，请用命题逻辑判断该推断是否正确。解：设P:甲作案；Q乙作案；R发在营业时间；S乙的证词可信;T:案发时货柜未上锁由题意可知，前提为： P Q， PR，S T ， S R， TPPT

4、1，2，I推理过程：1T2S T3S4S R(7)PT5 ，6，I(8)PQP(9)PQT8，E(10)QT7，9，I所以 PQ， PR，ST ， S R， T Q第2章谓词的定义、量词包括：9什么是谓词公式C(x) 表示为 x10 谓词公式的自由变元、约束变元、辖域11 自然语句的符号化：比方：所有的狼都吃人，设 T(x) 表示为 x 是狼，Q(x) 是前束范吃人。 x(T(x) C(x)12 判断什么是前束范式，x yG(x, y) H(x, y) 是前束范式， x y(P(x,y)式13 证明 x(A(x) B(x) xA(x) xB(x)证 明： x(A(x) B(x)x( A(x)B

5、(x)x A(x)xB(x)xA(x)xB(x)xA(x)xB(x)第31. 集合的元素、集合的基数、集合的子集、集合的运算空集的问题空集的基数、空集与集合的子集、真子集的关系幂集的问题集合幂集的求法，幂集的基数下面那个命题是不正确的选项是AA?B?C?D ?下面那个命题是不正确的选项是AA?B?C?D?以下命题中不正确的选项是A.x?x-xB.x?x-xC.A=x U x,贝U x?A且 x?AD.A-B=?A=B22设P=x|(x+1) <4 , Q=x|x +16?5x,那么以下选项正确的选项是()A.P?QB.P?QC.Q?PD.Q=P设 A=a,a ，以下命题错误的选项是 B

6、Aa?(A)Ba?(A)Ca?(A)Da?(A)在 0 D ?之间写上正确的符号A. =B. ?C.?D. ?判断以下命题哪个为真 ? CA.空集只是非空集合的子集B空集是任何集合的真子集C. A-B=B-A?A=BD.假设A的一个兀素属于B,那么A=B判断以下命题哪几个正确？B )A.假设 AU B= AU C,贝U B= CB.a, b=b, aC. ? (An B) ? (A)n ? (B),( ?(S)表示 S 的幕集)D. 假设A为非空集，那么A?AU A成立设 A=a, b ， B=c 。求以下集合：22( 1) A?0, 1?B ； (2) B2?A； ( 3) (A?B)2；

7、( 4) ? (A)?A 。解：( 1) A?0, 1?B=<a, 0, c>, <a, 1, c>, <b, 0, c>, <b, 1, c>；( 2) B2?A=<c, c, a>, <c, c, b>；2( 3) (A?B) =<a, c, a, c>, <a, c, b, c>, <b, c, a, c>, <b, c, b, c>(4) ? (A)?A=< ,a>, < ,b>, <a, a>, <a, b>, <

8、;b, a>, <b, b>, <a, a>, <a, b>关系1. 设A=a,b,c，那么A上的二元关系有 2 3*3或512 个。2. 集合 A=1,2,10上的关系 R=<x, y> : x+y=10, x, y?A，那么 R 的性质为BA.自反的 B .对称的C .传递的，对称的D.传递的设 A=,1, 1, 3, 1,2, 3，那么A上包含关系“ ？的哈斯图为CA.C.1,31,3B. 1,2,32(1,3D.集合A上的等价关系的三个性质是1,3自反性、 对称性和传递性。集合A上的偏序关系的三个性质是自反性反对称性和传递性。A上的

9、偏序关系 的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，下确界是 co(c) 的极大元为e,极小元为b；最大元是e，b是

10、最小元； 上界是e，下界是b；上确界是e，下确界是bo(d) 的极大元为e,极小元为b,d ;最大元是e,无最小元； 上界是 e,下界是 c；上确界是 e,下确界是 co设 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,42,10, 2,12 ,3,12 ,4,44,12 ，贝U R的关系图为：R的关系矩阵为2210关系R不是A到B的函数,因为元素 2，4 的象不唯逆关系R1也不是B到A的函数因为元素 7 的象不存在以下函数

11、是双射的为( A)。Af : Z?E , f (x) = 2xBf : N?N?N, f (n) =<nCf : R?Z , f (x) = xDf : Z?N, f (x) = | x |(注：Z整数集，E偶数集，N 自然数集，F实数集)设 Z、N、E 分别为整数集，自然数集，偶数集，那么以下函数是双射的为(A )A f : Z E , f (x) 2x B f : Z E , f (x) 8xC f : Z Z , f(x) 8 D f : N N N , f(n) n,n 1设A a,b,c,B 1,2,3，贝U以下关系中能构成 A到B函数的是(C)A f1 a,1, a,2, a

12、,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 :BC， g:A B都是单射，那么fog: AC(A )A.是单射B .是满射C.是双射D既非单射又非满射设函数f :B C，g: A B都是满射，那么f og : A C ( B )A.是单射 B.是满射C.是双射.既非单射又非满射设f,g是自然数集N上的函数,x N, f(x) x 1, g(x) 2x, 那么 fog(x) 2x 1 , gof(x) 2(x 1).关系 F=vxi,y i>,<x2,y 2>,<X3

13、,y 2>是函数对)关系 F=<xi,y i>,<xi,y 2>是函数错)设图G的邻接矩阵为那么G的边数为B .A. 6B. 5C.4D.3图G的邻接矩阵为910 1 I1100 0 1000 1 1i01 0 1iI11 1 0那么6有D .A. 5点，8边B6点，7边C. 6点，8边D5点，7边设有向图a、b、c与d如图四所示，那么以下结论成立的是(D )图四(b)是强连通的A . (a)是强连通的C. (c)是强连通的D. (d)是强连通的在自然数集N上，运算C是不可结合的。A. a*b=a+b+3 B . a*b=mina,bC . a*b=a+2b D

14、. a*b=a b(mod 3)Q是有理集，<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，故*是可交换的. 设e为其单位元，那么应有：a Q,a e e a a，即a e ae a，由a的任意性，有e