《离散数学》习题与解答
第一篇数理逻辑
第一章命题逻辑
1-1(1)指出下列语句哪些是命题,哪些不是命题,如果是命题指出他的真值
a)离散数学是计算机科学系的一门必修棵
b)∏> 2 吗?
c)明天我去看电影
d)请勿随地吐痰
e)不存在最大质数
f)如果我掌握了英语,法语,那么学习其他欧洲的语言就容易多了
g)9+5<12
h)x<3
i)月球上有水
j)我正在说假话
[解]
a)不是命题
b)是命题,真值视具体情况而定
c)不是命题
d)是命题,真值为t
e)是命题,真值为t
f)是命题,真值为f
g)不是命题
h)是命题, 真值视具体情况而定
i)不是命题
1-2(1)用P表示命题“天下雪”,(又表示命题“我将去镇上”,R表示命题“我有时间”.以符号形式写出下列命题:
(a)如果天不下雪和我有时间,那么我将去镇上.
(b)我将去镇上,仅当我有时间.
(c)天不下雪
(d)天下雪,那么我不去镇上
[解]
a)(┐P∧R)→Q
b)Q→R
c)┐P
d)P→┐Q
1-2(2)将下面这段述中所出现的原子命题符号化,并指出他们的真值,然后将这段述中的每一命题符号化 2 是有理数是不对的.2是偶素数.2或4是素数.如果2是素数则3也是素数.2是素数当且仅当3也是素数.
[解]:述中出现5个原子命题,将他们符号化为:
P: 2 是有理数其真值为F
Q:2是素数其真值为T
R:2是偶数其真值为T
S:3是素数其真值为T
U:4是素数其真值为F
述中各命题符号化为:
┐P;Q∧R;Q∨U;Q→S;Q<=>S
1-2(3)将下列命题符号化
a)如果3+3=6,则雪是白色的.
b)如果3+3≠6,则雪是白色的
c)如果3+3=6,则雪不是白色的.
d)如果3+3≠6,则雪不是白色的
e)王强身体很好,成绩也很好.
f)四边形ABCD是平行四边形,仅当其对边平行
[解]:设P:3+3=6 Q:雪是白色的
R:王强成绩很好S:王强身体很好
U: 四边形ABCD是平行四边形V: 四边形ABCD的对边是平行的于是:
a)可表示为:P→Q
b)可表示为: ┐P→Q
c)可表示为: P→┐Q
d)可表示为:┐P→┐Q
e)可表示为:S∧R
f)可表示为:U<=>V
1-3(1)判别下列公式中哪些是合式公式,那些不是合式公式
a) (Q→R∧S)
b) (P<=>(R→S))
c) ((┐P→Q)→(Q→P)))
d) (RS→T)
e)((P→(Q→R))→((P→Q)→(P→R)))
[解]:
a)不是合式公式(若规定运算符优先级后也可以作为合式公式)
b)是合式公式
c)不是合式公式(括号不配对)
d)不是合式公式
e)是合式公式
1-3(2)对下列各式用指定的公式进行代换:
a) (((A→B)→B)→A),用(A→C)代换A,用((B∧C)→A代换B。
b)((A→B)∨(B→A),用B代换A,A代换B.
[解]:a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))
b)((B→A)∨(A→B))
1-3(3)用符号形式写出下列命题
a)假如上午不下雨,我去看电影;否则就在家里读书或看报.
b)我今天进城,除非下雨.
c)仅当你走,我将留下.
[解]a)设P:上午天下雨. Q:我去看电影
R:我在家读书S:我在家看报
原命题可译为:(┐P→Q)∧(P→(R∨S))
b)设:P:我今天进城Q:天下雨
原命题可译为:┐Q→P
c)设:P:你走Q:我留下
原命题可译为:Q→P
1-3(4)称┐P→┐Q为条件命题P→Q的反换式
Q→P为条件命题P→Q的逆换式
┐Q→┐P为条件命题P→Q的逆反式
试写出如下条件命题的反换式,逆换式,逆反式。
(a)如果他有勇气,则他将得胜。
(b)如果天下雨,我不去。
[解](a)设P:他有勇气,Q:他将得胜
原条件命题可译为:P→Q
反换式:┐P→┐Q,表示:如果他没有勇气,则他将不能获胜。
逆换式:Q→P,表示:如果他将得胜,则他有勇气。
逆反式:┐Q→┐P,表示:如果他不获胜,则他没有勇气。
(b)设P:天下雨,Q:我去
原条件命题可译为:P→┐Q
反换式:┐P→Q,表示:如果如果天不下雨,则我去。
逆换式:Q→P,表示:如果我不去,则天下雨。
逆反式:┐Q→┐P,表示:如果我去,则天不下雨。
1-4(1)试求下列各命题公式的真值表并解释其结果
(a)(P→Q)∧(Q→P);
(b)(P∧Q)→P;
(c)Q→(P∨Q);
(d)(P→Q)<=>(┐P∨Q);
(e)(┐P∨Q)∧(┐(┐P∧┐Q));
(f)┐(P→Q)∧Q∧R 。
[解] (a)从真值表1-1中可看出:(P→Q)∧(Q→P)<=>(P<=>Q)
(b) 从真值表1-2中可看出:(P∧Q)→P是永真式
(c) 从真值表1-3中可看出:Q→(P∨Q)是永真式
(d) 从真值表1-4中可看出:(P→Q)<=>(┐P∨Q)是永真式
(e) 从真值表1-5中可看出:(┐P∨Q)∧(┐(┐P∧┐Q))
<=>┐P∨Q
<=>P→Q
<=>┐(P∧┐Q)
(f) 从真值表1-6中可看出:┐(P→Q)∧Q∧R是永真式
表1-1
表1-2
表1-3
表1-4
表1-6
1- 4(2)用真值表判断下列各组公式是否等价:
(a ) P →(Q →R)与(P ∧Q )→R (b ) (P →Q )→R 与(P ∧Q )→R
[解]由表1-7可知P→(Q→R) <=>(P∧Q)→R
而(P→Q)→R<≠>(P∧Q)→R
表1-7
1-4(3)试以真值表证明下列命题:
(a)合取运算的结合律
(b)德摩根定律
[解] (a)如表1-8,(P∧Q)∧R<=>
(b)如表1-9,┐(P∧Q)<=>┐P∨┐Q
┐(P∨Q)<=>┐P∧┐Q
2-4(4)证明下列等价式:
(a)A→(B→A)<=>┐A→(A→┐B);
(b)(A∨B)→C<=>(A→C)∧(B→C);
(c) ┐(A<=>B)<=>(A∧┐B)∨(┐A∧B);
(d) (((A∧B)∧C)→D)∧(C→(A∨(B∨D)))<=>(C∧(A<=>B))→D
[证](a)A→(B→A)<=>┐A∨(┐B ∨A)
<=>(┐B ∨A)∨┐A
<=>(A∨┐B)∨┐A
<=>A∨(┐B∨┐A)
<=>A∨(┐A∨┐B)
<=>A∨(A→┐B)
<=>┐A→(A→┐B)
(b)(A→C)∧(B→C)<=>(┐A∨C)∧(┐B∨C)
<=>(┐A∧┐B)∨C
<=>┐(A∨B)∨C
<=>(A∨B)C
(c)┐(A<=>B)<=>┐((A→B)∧(B→A))
<=>┐((┐A∨B)∧(┐B∨A))
<=>┐(┐A∨B)∨┐(┐B∨A))
<=>(A∧┐B)∨(B∧┐A))(d)(((A∧B)∧C)→D)∧(C→(A∨(B∨D)))
<=>((┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D)))
<=>(┐A∨┐B∨┐C∨D)(┐C∨A∨B∨D)
<=>(┐C∨D)∨((┐A∨┐B)∧(A∨B))
<=>(┐C∨D)∨((A∧┐B)∨(B∧┐A))
<=>(┐C∨D)∨┐((┐A∨B)∧(┐B∨A))
<=>(┐C∨┐((┐A∨B)∧(┐B∨A)))∨D
<=>┐(C∧(┐A∨B)∧(┐B∨A))∨D
<=>┐(C∧(A→B)∧(B→A))∨D
<=>┐(C∧(A<=>B))∨D
<=>(C∧(A<=>B))→D
1-4(5)判断下列命题公式的类型(永真;永假;非永真,也非永假):(a)((P→Q)∧P)→Q;
(b)┐(P→(P ∨Q))∧R;
(c)P ∧(((P ∨Q) ∧┐P) →Q).
[解] (a)((P→Q)∧P)→Q
<=>((┐P∨Q)∧P)→Q
<=>┐((┐P∨Q)∧P)∨Q
<=>(┐(┐P∨Q)∨┐P)∨Q
<=>((P∧┐Q)∨┐P)∨Q
<=>((P∨┐P)∧(┐Q∨┐P))∨Q
<=>(┐Q∨┐P)∨Q
<=>T∨┐P
<=>T
∴(a)为永真式
(b)┐(P→(P ∨Q))∧R
<=>┐(┐P∨P ∨Q)∧R
<=>(P∧┐P ∧┐Q)∧R
<=>F∧R
<=>F
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y,按照一定的顺序组成的 二元组称为有序对,记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集,则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
离散数学试题(A卷及答案) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分) 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数,证明:在任取m+1个整数中,至少有两个整数,它们的差是m的整数倍 证明设 1 a,2a,…,1+m a为任取的m+1个整数,用m去除它们所得余数 只能是0,1,…,m-1,由抽屉原理可知, 1 a,2a,…,1+m a这m+1个整 数中至少存在两个数 s a和t a,它们被m除所得余数相同,因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (15分)证明∵x∈ A-(B∪C)? x∈ A∧x?(B∪C)? x∈ A∧(x?B∧x?C)?(x∈ A∧x?B)∧(x∈ A∧x?C)? x∈(A-B)∧x∈(A-C)? x∈(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误!未找到引用源。2=(x+错误!未找到引用源。)(x 错误!未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解: F(x): 错误!未找到引用源。2=(x+错误!未找到引用源。)(x 错误!未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?,在(a )中为假命题,在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?,在(a )(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误!未找到引用源。=0. (c) 特定函数错误!未找到引用源。(x,y)=x错误!未找到引用源。y,x,y D ∈错误!未找到引用源。. (d) 特定谓词错误!未找到引用源。(x,y):x=y,错误!未找到引用源。(x,y):x 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。 (1)p∨(q∧r)?0∨(0∧1) ?0 (2)(p?r)∧(﹁q∨s) ?(0?1)∧(1∨1) ?0∧1?0. (3)(?p∧?q∧r)?(p∧q∧﹁r) ?(1∧1∧1)? (0∧0∧0)?0 (4)(?r∧s)→(p∧?q) ?(0∧1)→(1∧0) ?0→0?1 17.判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2也是无理数。另外6能被2整除,6才能被4整除。” 答:p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型: (4)(p→q) →(?q→?p) (5)(p∧r) ?(?p∧?q) (6)((p→q) ∧(q→r)) →(p→r) 答:(4) p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 (5)公式类型为可满足式(方法如上例) (6)公式类型为永真式(方法如上例) 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答:(2)(p→(p∨q))∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r (p∨q)→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式: (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明(2)(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) (4)(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式,并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 习题5 1.设个体域D={a,b,c},消去下列各式的量词: (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 答案 (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2.设个体域D={1,2},请给出两种不同的解释I1和I2,使得下面公式在I1下都是真命题,而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) .(1) 答案 I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真,所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真,而G(1),G(2)均为假, x(F(x)→G(x))为假。 (2)留给读者自己做。 3.给定解释I如下: (a) 个体域D={3,4}。 (b) (x)为(3)=4,(4)=3。 (c) (x,y)为(3,3)=(4,4)=0,(3,4)=(4,3)=1。 答案 试求下列公式在I下的真值: (1) x yF(x,y) (2) x yF(x,y) 离散数学证明题 离散数学证明题离散数学证明题:链为分配格 证明设a,b均是链A的元素,因为链中任意两个元素均可比较,即有a≤b或a≤b,如果a≤b,则a,b的最大下界是a,最小上界是b,如果b≤a,则a,b的最大下界是b,最小上界是a,故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或c≤a ⑵a≤b且a≤c 如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c) 如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c) 无论那种情况分配律均成立,故A是分配格. 一.线性插值(一次插值) 已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。 1. 插值函数和插值基函数 由直线的点斜式公式可知: 把此式按照 yk 和yk+1 写成两项: 记 并称它们为一次插值基函数。该基函数的特点如下表: 从而 P1 (x) = yk lk (x) + yk+1 lk+1 (x) 此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关,而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 . 例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。 解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设 x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010 则插值基函数为: 于是, 拉格朗日型一次插值多项式为: 故 : 即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792). 二.二次插值多项式 已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足, P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 . 其几何意义为:已知平面上的三个点 (xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ), 第5章 一.填空题 1. 群中有唯一的()。 2. 如果群运算是可交换的,则群为()。 3. 设*是定义在集合A上的二元运算,如果对于A中任意的两个元素x,y,都有x*y∈A,则称二元运算*在A上是()。 4. 设*是定义在集合A上的二元运算,如果对于A中任意的两个元素x,y,都有x*y=y*x,则称二元运算*在A上是()。 5. 设★是定义在有理数集合Q上的二元运算,如果对于Q中任意的两个元素x,y,都有x★y=x+y-x*y,其中*表示普通乘法元算,则二元运算★在Q 上是()。(填写可交互/不可交换) 6. 设*是定义在集合A上的二元运算,如果对于A中任意的元素x,y,z,都有(x*y)*z=x*(y*z) ,则称二元运算*在A上是()。 7. 设★是定义在非空集合A上的二元运算,如果对于A中任意的两个元素x,y,都有x*y=y, 则二元运算★在A上是()。(填写可结合/不可结合) 8. 设*,★是定义在集合A上的两个二元运算,如果对于A中任意的元素x,y,z,都有(x*y) ★z=(x★z)*(y★z),z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是()。 9. 设*,★是定义在集合A上的两个可交换的二元运算,如果对于A中任意的元素x,y,都有x*(x★y)=x, x★(x*y)=x,则称二元运算*对于★在A上满 足()。 10. 设*是定义在集合A上的二元运算,如果对于A中任意的元素x,都有x*x=x,则称二元运算*是()。 11. 设*是定义在集合A上的二元运算,如果在A中存在元素el,对于A中任意的元素x,都有el*x=x,则称el为A中关于运算*的()。 12. 设*是定义在集合A上的二元运算,如果在A中存在元素ol,对于A中任意的元素x,都有ol*x=x,则称ol为A中关于运算*的()。 13. 设*是定义在集合A上的二元运算,如果在A中存在元素er,对于A中任意的元素x,都有x*erl =x,则称er为A中关于运算*的()。 14. 设*是定义在集合A上的二元运算,如果在A中存在元素or,对于A中任意的元素x,都有x*or=x,则称or为A中关于运算*的()。 15. 如果对于集合中的二元运算*,存在左零元和右零元,且左零元等于右零元,则零元是()。 16. 如果对于集合中的二元运算*,存在左么元和右么元,且左么元等于右么元,则么元是()。 17. 设*是定义在集合A上的二元运算,且e是A中关于运算*的么元,如果对于A中的元素x,存在A中的元素y,有y*x=e,则称y为x的 ()。 18. 对于实数域上的乘法元算,每个元素()逆元。(填写一定有/不一定有) 19. 对于实数域上的加法运算,()零元。(填写存在/不存在) 20. 对于整数域上的加法运算,()么元。(填写存在/不存在) 21. 对于非空集合S上二元运算*,是封闭且可结合的,那么 五、证明题 1.设G 是一个n 阶无向简单图,n 是大于等于3的奇数.证明图G 与它的补图G 中的奇数度顶点个数相等. 证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边删去E 所得到的.所以对于任意结 点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于3的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等. 2.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图. 证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数. 又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图. 故最少要加2 k 条边到图G 才能使其成为欧拉图. 五、证明题 1.试证明集合等式:A ? (B ?C )=(A ?B ) ? (A ?C ). 证:若x ∈A ? (B ?C ),则x ∈A 或x ∈B ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C . 即x ∈A ?B 且x ∈A ?C , 即x ∈T =(A ?B ) ? (A ?C ), 所以A ? (B ?C )? (A ?B ) ? (A ?C ). 反之,若x ∈(A ?B ) ? (A ?C ),则x ∈A ?B 且x ∈A ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C , 即x ∈A 或x ∈B ?C , 即x ∈A ? (B ?C ), 所以(A ?B ) ? (A ?C )? A ? (B ?C ). 因此.A ? (B ?C )=(A ?B ) ? (A ?C ). 2.对任意三个集合A , B 和C ,试证明:若A ?B = A ?C ,且A ≠?,则B = C . 证明:设x ∈A ,y ∈B ,则 第6章 函数 一、选择题(每题3分) 1、设{,,},{1,2,3}A a b c B ==,则下列关系中能构成A 到B 函数的是( C ) A 、1{,1,,2,,3}f a a a =<><><> B 、2{,1,,1,,2}f a b b =<><><> C 、4{,1,,1,,1}f a b c =<><><> D 、1{,1,,2,,2,,3}f a a b c =<><><><> 2、设R Z N 、、分别为实数集、整数集,自然数集,则下列关系中能构成函数的是( B ) A 、)}10(),(|,{<+∧∈> 离散数学试题(B卷答案1) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E,?E→(A∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2),I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4), I (6) C∨D P (7) R∨S T(5),I 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 全国2010年7月自学考试离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是..命题的是( D ) A .中华人民共和国的首都是北京 B .张三是学生 C .雪是黑色的 D .太好了! 2.下列式子不是..谓词合式公式的是( B ) A .(?x )P (x )→R (y ) B .(?x ) ┐P (x )?(?x )(P (x )→Q (x )) C .(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D .(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3.下列式子为重言式的是( ) A .(┐P ∧R )→Q B .P ∨Q ∧R →┐R C .P ∨(P ∧Q ) D .(┐P ∨Q )?(P →Q ) 4.在指定的解释下,下列公式为真的是( ) A .(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B .(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C .(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D .(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5.对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y ),下列说法正确的是( ) A .y 是自由变元 B .y 是约束变元 C .(?x )的辖域是R(x , y ) D .(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6.设论域为{1,2},与公式(?x )A (x )等价的是( ) A .A (1)∨A (2) B .A (1)→A (2) C .A (1)∧A (2) D .A (2)→A (1) 7.设Z +是正整数集,R 是实数集,f :Z +→R , f (n )=log 2n ,则f ( ) A .仅是入射 B .仅是满射 C .是双射 D .不是函数 8.下列关系矩阵所对应的关系具有反对称性的是( ) A .???? ? ?????001110101 B .???? ? ?????101110001 离散数学试题(A卷答案) 一、(10分)证明?(A∨B)→?(P∨Q),P,(B→A)∨?P A。 证明:(1)?(A∨B)→?(P∨Q)P (2)(P∨Q)→(A∨B) T(1),E (3)P P (4)A∨B T(2)(3),I (5)(B→A)∨?P P (6)B→A T(3)(5),I (7)A∨?B T(6),E (8)(A∨B)∧(A∨?B) T(4)(7),I (9)A∧(B∨?B) T(8),E (10)A T(9),E 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题,设A:甲参加了比赛;B:乙参加了比赛;C:丙参加了比赛;D:丁参加了比赛。 依题意有, (1)甲和乙只有一人参加,符号化为A⊕B?(?A∧B)∨(A∧?B); (2)丙参加,丁必参加,符号化为C→D; (3)乙或丁至多参加一人,符号化为?(B∧D); (4)丁不参加,甲也不会参加,符号化为?D→?A。 所以原命题为:(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件,有且仅有两人参加竞赛,故?A∧B∧?C∧?D为F。所以只有:(A∧?B∧?C∧ D)∨(A∧?B∧D)?T,即甲、丁参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误?为什么?给出正确的推理形式。 (1)?x(P(x)→Q(x)) P 离散数学课后习题答案(左孝凌版) 1-1,1-2解: a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解: a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q (4)解: a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 (Q→R)∧(R→Q):一个数是奇数,则它不能被2整除并且一个数不能被2整除,则它是奇数。 (5) 解: a)设P:王强身体很好。Q:王强成绩很好。P∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P: a和b是偶数。Q:a+b是偶数。P→Q e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解: 说明: 定义:红色表示。 定理性质:橙色表示。 公式:蓝色表示。 算法:绿色表示 页码:灰色表示 数理逻辑: 1.命题公式:命题,联结词(,,,,),合式公式,子公式 2.公式的真值:赋值,求值函数,真值表,等值式,重言式,矛盾式 3.范式:析取范式,极小项,主析取范式,合取范式,极大项,主合取范式 4.联结词的完备集:真值函数,异或,条件否定,与非,或非,联结词完备集 5.推理理论:重言蕴含式,有效结论,P规则,T规则, CP规则,推理 6.谓词与量词:谓词,个体词,论域,全称量词,存在量词 7.项与公式:项,原子公式,合式公式,自由变元,约束变元,辖域,换名,代入 8.公式语义:解释,赋值,有效的,可满足的,不可满足的 9.前束范式:前束范式 10.推理理论:逻辑蕴含式,有效结论,-规则(US),+规则(UG),-规则(ES), +规则(EG), 推理 集合论: 1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差 2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关 系 3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R), 对称闭包 s(R), 传递闭包 t(R) 4.等价关系: 等价关系, 等价类, 商集, 划分 5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下 界 6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射,反函数, 复合函数 7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集 代数结构: 1.运算及其性质:运算,封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的,幺 元,零元,逆元 2.代数系统:代数系统,子代数,积代数,同态,同构。 3.群与子群:半群,子半群,元素的幂,独异点,群,群的阶数,子群,平凡子群,陪集, 拉格朗日(Lagrange)定理 4.阿贝尔群和循环群:阿贝尔群(交换群),循环群,生成元 5.环与域:环,交换环,含幺环,整环,域 6.格与布尔代数:格,对偶原理,子格,分配格,有界格,有补格,布尔代数,有限 布尔代数的表示定理 图论: 1.图的基本概念:无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、 补图,握手定理,图的同构 2.图的连通性:通路,回路,简单通路,简单回路(迹)初级通路(路径),初级回路 (圈),点连通,连通图,点割集,割点,边割集,割边,点连通度,边连通度,弱连通图,单向连通图,强连通图,二部图(二分图) 3.图的矩阵表示:关联矩阵,邻接矩阵,可达矩阵 4.欧拉图与哈密顿图:欧拉通路、欧拉回路、欧拉图、半欧拉图,哈密顿通路、哈密 顿回路、哈密顿图、半哈密顿图 5.无向树与根树:无向树,生成树,最小生成树,Kruskal,根树,m叉树,最优二叉 树,Huffman算法 6.平面图:平面图,面,欧拉公式,Kuratoski定理 习题13参考答案 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 图13.9 答案:(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案:(1)不是格,其他都是。 3.(1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 答案:(1) (2) (3) 4.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 答案:(1) a∨(a∧b) a (2) a∧(b∨c)(a∧b)∨(a∧c) (3) b∧(c∨a)(b∧c)∨a 5.设L是格,a,b,c∈L,且a b c,证明 a∨b=b∧c 答案:a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.10 答案: L1的子格:{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格:{a1},{d1},L2 L3的子格:{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。 答案:(1)a与d互补;b,c没有补元。 (3)a与f互补;b的补元为c,d;c的补元为b,e;d的补元为b,e;e的补元为c,d. (6)a与f互补;b的补元为e;c和d没有补元;e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。 答案: (1)是分配格,因为不包含与钻石格和五角格同构的子格;不是有补格和布尔格,b,c没有补元。 (3)不是分配格,不是布尔格,因为包含五角格作为子格;是有补格,a与f互补,b和e的补元有c,d;c,d的补元有b,e. (6)是分配格,因为没有5元子格与钻石格或五角格同构;不是有 习题8 1. 设f:N→N,且 求f(0),f({0}),f(1),f({1}),f({0,2,4,6,…}),f({4,6,8}),f({1,3,5,7})。 2. 设A={1,2},B={a,b,c},求B A。 3.给定函数f和集合A,B如下: (1) f:R→R,f(x)=x,A={8},B={4} (2) f:R→R+,f(x)=2x,A={1},B={1,2} (3) f:N→N×N,f(x)=离散数学答案解析屈婉玲版第二版高等教育出版社课后答案解析
离散数学结构 习题5
离散数学证明题
离散数学结构试题集5-7
叫做()。 22. 正整数上的加法运算()半群。(填写是/不是) 23. 实数域上的除法运算()半群。(填写是/不是) 24. 整数域上的加法运算()群。(填写是/不是) 25. .如果群的运算满足交换率,则这个群叫()。 26. 循环群()生成元。(填写必有/不一定有) 27. 设f是由到的一个同态,如果f( ),则称f为满同态的。 28. 设f是由到的一个同态,如果f( ),则称f为同构的。 29. 设f是群到的一个同态映射,如果e’是B中的么元,Ker(f)=( ),则称Ker(f)为同态映射f的核。 30. 设R是代数系统上的一个等价关系,如果当,电大离散数学证明题参考题
离散数学函数复习题答案
离散数学期末考试试题及答案
离散数学及答案
离散数学题目5
离散数学课后习题答案(左孝凌版)
离散数学知识点
离散数学结构 习题13
离散数学结构 习题8