离散数学 作业及答案

2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1

1.利用素因子分解法求2545与360的最大公约数。

解：掌握两点：(1) 如何进行素因子分解

从最小素数2的素数去除n。

(2) 求最大公约数的方法

gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn)

360=2332515090

2545=2030515091

gcd(2545,360) =2030515090=5

2.求487与468的最小公倍数。

解：掌握两点：(1) 如何进行素因子分解

从最小素数2的素数去除n。

(2) 求最小公倍数的方法

lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn)

ab=gcd(a, b)﹡lcm (a, b)

487是质数，因此gcd(487,468)=1

lcm(487,468)= (487*468)/1=487*468=227916

3.设n是正整数，证明：6|n(n+1)(2n+1)

证明：用数学归纳法：

归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6

归纳假设：假设当n=m时，6|m(m+1)(2m+1)

归纳推导：当n=m+1时，

n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1]

=(m+1)(m+2)(2m+3)

= m(m+1)(2m+3)+2(m+1)(2m+3)

= m(m+1)(2m+1+2)+2(m+1)(2m+3)

= m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3)

= m(m+1)(2m+1)+ 2(m+1)(m+2m+3)

= m(m+1)(2m+1)+ 2(m+1)(3m+3)

= m(m+1)(2m+1)+ 6(m+1)2

因为由假设6|m(m+1)(2m+1)成立。

而6|6(m+1)2

所以6|m(m+1)(2m+1)+ 6(m+1)2

故当n=m+1时，命题亦成立。

所以6| n(n + 1)(2n + 1)

5-2

1 已知 6x ≡7 (mod 23),下列式子成立的是( D ):

A. x ≡7 (mod 23)

B. x ≡8 (mod 23)

C. x ≡6 (mod 23)

D. x ≡5 (mod 23)

2 如果a ≡b (mod m) , c是任意整数，则（A ）：

A. ac≡bc (mod m)

B. a=b

C. ac bc (mod m)

D. a ≠b

3 解同余方程 31 x ≡5（mod 17）。

解：

(1) 由于gcd(17,31)=1,由定理3知存在31模17的逆。

求31和17的线性组合（欧几里得逆过程）

31=1·17+14

17=1·14+3

14=4·3+2

3=1·2+1

2=1·2+0（结束）

因此，-6·31+11·17=1 ，-6是31模17的逆

(2)-6×31x ≡ -6×5（mod 17）

x≡-30 mod 17

≡4 mod 17

满足同余式的解有：…-47,-30, -13及4, 21,38, …

4用RSA密码系统为数字85加密，求加密信息并验证解密信息的正确性。

其中p=11，q=13，e=7。

解： (1)设想需要发送信息M=85。利用(n,e)=(143,7)计算出加密值：

C=M e mod n=857 mod 143=123

(2) 接下来求d：

①ed≡1 mod ((p-1)(q-1))

d=e-1 mod ((p-1)(q-1))

= 7-1 mod 120

②由于gcd(7,120)=1,由定理3知存在7模120的逆。

求7和120的线性组合（欧几里得逆过程）

120=17·7+1

7=7·1+0 （结束）

-17·7+1·120=1

因此，d=-17+120=103

(3) M=C d (mod n)=123103 mod 143=85

6-1

1. 设集合A={1,2,3,…，10}，问下面定义的二元运算?关于集合A是否封闭？

a) x?y=max(x,y) 封闭

b) x?y=min(x,y) 封闭

c) x?y=gcd(x,y) 封闭

d) x?y=lcm(x,y) 不封闭，例lcm(3,7)=21

e) x?y=质数p的个数，使得x≤p≤y 不封闭，例6?6=0

2.设代数系统 其中A={a,b,c}, ?是A上的一个二元运算。对于由以下几个表所确定的运算，试分别讨论他们的交换性、等幂性以及在A中关于?运算是否有幺元。如果有幺元，那么A中的每个元素是否有逆元。

a) b) c) d) ? a b c a b c a b c b a c c c c ?

a b c a

b

c

a b c b c a c a b ?

a b c a

b

c a b c a b c a b c ? a b c a b c a b c b b c c c b

解：a) 可交换，不等幂，a 为幺元，a 以自身为逆元，b 、c 互为逆元。 b) 可交换，不等幂，a 为幺元，a 、b 以自身为逆元，c 没有逆元。

c) 不可交换，等幂，没有幺元。

d) 可交换，不等幂，a 为幺元，a 以自身为逆元，b 、c 没有逆元。

3. 定义I +上的两个二元运算为：a ?b=a b , a △b=a·b, a,b ∈I +。试证明?对△是不可分配的。

a ()() ()()()() b+c

b c

b c b c b c b c a b c a a b a c a a a a a b c ?+?=?=??===? i i i 证明：由于

而不一定等于，所以对是不可分配的。

6-2

1.证明：如果f 是由到的同态映射，g 是由到的同态映射，那么g。f 是由到的同态映射。

(*)()()B ()()(),

(*)((*))(()())

=(())(())a b A f a b f a f b c d g c d g c g d a b A g f a b g f a b g f a f b g f a g f b g ∈=∈=∈=== 证明： 因为对于任意的，，有，

而对于任意的，，有所以对于任意的，有：

() ()

f a

g f b g f ? 因此，是由到的同态映射。

2. 与同构吗？

-{0}a (),()(0)(0)()(0) ()(0)()(0)(0)

(0)

b f a f a f a f b f f ×∈∈===+=×=×==+=×=×证明： 设是到的同构映射，于是

(1)对于任意的，必存在使得有：

所以是{0}, >

(0)=1. (2) --{0}c (c)-1, ()()()(-1)(-1)1,=00 f R R f f c c f c f c c c c ×∈∈=+=×=×=+=中的幺元。即应有对于 1必存在使得有：由于是同构映射，

所以必有唯一的元素0与1对应，所以，，

(0)-1

f =×由此导致的矛盾。

因此，与不可能同构。

3.证明：一个集合上任意两个同余关系的交也是一个同余关系。

121112

121,,, ,,,,,, ,,R R a b c d R R a b c d R a b c d R R R a c b d R a c ?<><>∈∩<><>∈<><>∈∈

对于任意的，有

且由于和为同余关系，所以

且1

12

, b d R a c b d R R ?>∈∈∩所以因此，一个集合上任意两个同余关系的交仍是一个同余关系。

4.考察代数系统,以下定义在I 上的二元关系R 是同余关系吗？

a) ∈R,当且仅当(x<0∧y<0)∨(x ≥0∧y ≥0)

b) ∈R,当且仅当|x-y|<10

c)∈R,当且仅当(x=y=0)∨(x ≠0∧y ≠0)

d) ∈R,当且仅当x ≥y )R -2,-2,1,4 -2+1,-2+4=<-1,2 )R )-4,6,6,6 -4+6,6-6=<2,0a R R R b c R <><>∈<>>?<>∈<>解： 首先证明是等价关系，但存在着而

，所以不是同余关系。

传递性不成立，不是等价关系，更不是同余关系。

而

)R

R R d >?，

所以不是同余关系。对称性不成立，不是等价关系，更不是同余关系。

以上只是该题的简略答案，实际解题时应该一步步进行等价关系验证， 然后再进行同余关系验证。

6-3

1.设是一个半群，a ∈S ，在S 上定义一个二元运算□，使得对于S 中的任意元素x 和y ，都有x □y=x ?a ?y ，证明二元运算是可结合的。

(( )()() ()()())()

x y z x a y z x a y a z x a y a z

x y z x y a z x a y a z x a y a z

x y z x y z =??=????=????=??=????=????= 证明：由于

所以 2.设是一个代数系统，?是R 上的一个二元运算，使得对于R 中的任意元素a ，b 都有a ?b=a+b+a ?b ，证明0是幺元且是独异点。

,

000,

000, 0=0=a ,+R R ,,, ()() a R a a a a a a a a a a a b R a b a b a b R a b c R a b c a b a b c

∈?=++=?=++=??∈?=++∈?∈??=++?i i i i i 证明：(1)对于任意的所以 ，因此0是幺元.

(2)对于任意的,由于和在上封闭，所以，

，即在上封闭。

对于任意的有

( ) ()()

()

a b a b c a b a b c

a b c a b a c b c a b c

a b c a b c b c a b c b c a b c b c =++++++=++++++??=?++=++++++i i i i i i i i i i i i ()(),

a b c a b c =++++++??=????>i i i i i 运算是可结合的。

因此，是独异点。

3.设X=R-{0,1}，在X 上定义6个函数如下：对于任意x ∈X ，f 1(x)=x; f 2(x)=x -1; f 3(x)=1-x; f 4(x)=(1-x)-1; f 5(x)=(x-1)x -1; f 6(x)=x(x-1)-1

试证明是一个群。其中F={f 1，f 2，f 3，f 4，f 5，f 6}， 。是函数的复合运算.

证明：由函数复合运算的定义f 。g(x)=f(g(x)),可写出。在F 上的运算表如下：

。 f 1 f 2 f 3 f 4 f 5 f 6f 1 f 2f 3 f 4 f 5 f 6f 1 f 2 f 3 f 4 f 5 f 6f 2 f 1 f 4 f 3 f 6 f 5f 3 f 5 f 1 f 6 f 2 f 4 f 4 f 6 f 2 f 5 f 1 f 3f 5 f 3 f 6 f 1 f 4 f 2f 6 f 4 f 5 f 2 f 3 f 1 由表可知，运算。在F 上是封闭的， 运算。是可结合的， f 1是运算的幺元， f 1 f 2 f 3 f 6均以自身为逆元， f 4 f 5互为逆元。 因此，是一个群。

4.设是一个半群，

e 是幺元且对于每一个x ∈A, 存在x ∈A ，使得x x e ?= 。 a)证明：对于任意的a,b,c ∈A ，如果,c a b a c b ?=?=则。

b)通过证明e 是A 中的幺元，证明是群。

a ()()

e b e c b c x ?=???=???>??=???=?=∈ 证明：()由可得到由于是半群，满足结合律， 所以有： (，是左幺元

()对于任意的 ()() (a)()e e ()() ===x ,结合的结论有：，说明也是右幺元，故是幺元。 于是对于任意的,所以，故有，说明任意均有逆元，因此

是群。

5.设是群，对于任一a ∈G ,令H={y|y ?a=a ?y, y ∈G}, 试证明是 的子群。

证明：根据H 集合的定义知，任意的y ∈H, 一定有y ∈G ，因此H ?G 。 由于是群，?运算在G 中满足结合律，在H 中也满足结合律。 对于任意的x,y ∈H,以及任意的a ∈G ，因为

-1-1-1-1

(x y)a x y a=x a y=a x y=a (x y)

y H H **H **()() x e a a e e H x x a a x x x a x x a x x ??=?????????∈?=∈∈=???=??? 所以，说明关于是封闭的。

因为，所以。

对于任意的，由于，所以 -1-1-1

a x x a x H

?=?∈表明

综上所述，是的子群。 6.设是群，且|A|=2n ，n ∈I +。证明：在A 中至少存在a ≠e ，使得a ?a=e 。其中e 是幺元。

证明：对于任意的x ∈A ，均有它的逆元x -1∈A ，使得-1-1 x x x x e ?=?=，由于互为逆元的两个不相等的元素是成对出现的，而且群中有唯一的幺元e ，因此，至少有一个元素是以自身为逆元的。即必存在a ∈A,a ≠e,使得 a a e ?=

6-4

1. 设是一个独异点，并且对于任一x ∈G , 都有x ?x=e ，其中e 是幺元，证明是一个阿贝尔群。

2.证明任何阶数分别是1,2,3,4的群都是阿贝尔群。并举一个6阶群，它不是阿贝尔群。

-1111,,;

,,(),

x G x x e e x x a b G a b a b b a b a ???∈?==∈?=?=?=??1.证明：对于任意的有是幺元，说明每个

元素都有逆元，且对于任意的因此，是阿贝尔群。

2.证明：

(1)对于阶数为1的群，该群中仅有唯一的一个幺元e ，e ?e=e ，显然是阿贝尔群。

(2)对于阶数为2的群，该群中除幺元外，仅有一个与e 不同的元素a,且 e ?a=a ?e=a, 因为每个元素都要有逆元，因此有a ?a=e ，所有运算满足交换律，所以<{a,e},?>是阿贝尔群。

(3)对于阶数为3的群<{a,b,e},?>。若a ?b=a ，则有a -1?a ?b= a -1?a ，导致b=e 的矛盾；同理，若a ?b=b ，则导致a=e 的矛盾；所以必有a ?b=e 。又因

b ?a= b ?a ?b ?b -1=b ?e ?b -1=e ，因此群<{a,b,e},?>是阿贝尔群。

(4)对于阶数为4的群<{a,b,c,e},?>,

1) 如果a,b,c 中有两个元素互为逆元，不妨设它们是a,b, 则

a ?b=

b ?a =e 。

于是必有c ?c= e, a ?c ≠e( c 的唯一逆元是c)，所以a ?c=b 。（假设a ?c=a ，代入a ?b=b ?a ，有a ?c ?b=b ?a ?c ，就有

a ?c ?b=e ?c=c=a ?

b ，与a ?b =e 矛盾。假设a ?c=

c ，由c ?c = e 有：

c ?c =(a ?c)?c=a ?(c ?c)=a ?e=a ,推出矛盾。因此只能是a ?c=b ）。同理可

证c ?a=b ，故a ?c=c ?a 。

同理可证b ?c=c ?b 。

2) 若a,b,c 中的每一个元素都以自身为逆元，则必有a ?b=b ?a =c ，

a ?c=c ?a=

b ，b ?c=

c ?b=a 。

因此，不论哪种情况，都表明<{a,b,c,e},?>是阿贝尔群。

(5) 定义在集合S={a,b,c}上的所有双射函数为：

f 0：f 0(a)=a, f 0(b)=b, f 0(c)=c;

f 1：f 1(a)=a, f 1(b)=c, f 1(c)=b;

f 2：f 2(a)=b, f 2(b)=a, f 2(c)=c;

f 3：f 3(a)=b, f 3(b)=c, f 3(c)=a;

f 4：f 4(a)=c, f 4(b)=a, f 4(c)=b;

f 5：f 5(a)=c, f 5(b)=b, f 5(c)=a;

于是集合F={f 1，f 2，f 3，f 4，f 5，f 6}关于函数的复合运算。构成群，群的阶数为6，其运算如下表所示。显然，它不是阿贝尔群。

。f 0 f 1 f 2 f 3 f 4 f 5 f 0f 1 f 2f 3 f 4 f 5f 0 f 1 f 2 f 3 f 4 f 5 f 1 f 0 f 4 f 5 f 2 f 3f 2 f 3 f 0 f 1 f 5 f 4 f 3 f 2 f 5 f 4 f 0 f 1f 4 f 5 f 1 f 0 f 3 f 2 f 5 f 4 f 3 f 2 f 1 f 0

第5页习题3中的6阶群也不是阿贝尔群，也可以该习题3为例来证明该题目。

6-5

1.设是一个代数系统，其中+, ?为普通的加法和乘法运算，A 为下列集合： a) A={x|x=2n,n ∈I} 不是，没有乘法幺元

b) A={x|x=2n+1,n ∈I} 不是，对于加法不封闭

c) A={x|x≥0,且x ∈I} 不是，对于任意x ≠0，不存在加法逆元

d) R}∈ 是整环

e) R}∈ 是整环 问是整环吗？为什么？

是整环的题目，要有验证过程。

2. 设是一个环，并且对于任意的a ∈A 都有a ?a=a，证明：

a)对于任意的a∈A ，都有a+a =θ，其中θ是加法幺元。

b ）是可交换环。

a)a A a+a A ()() = b) a,b A a+b A ()()a a a a a a

a a a a a a a a a a

a a a a a a

a a a

b a b θ

∈∈+?+=+?+?+?+?=++++=++∈∈+?+=证明：对于任意的，都有，所以有

由此可知，对于任意的，都有，所以有

=,= - a) - = a b a a a b b a b b a b

a a

b b a b a b

a b b a a b b a

b a b a a b b a θ+?+?+?+?=++?+?+=+?+????=????由此可知，即由的结果知 ，所以有。因此是可交换环。

3.设是一个域，S 1?F ，S 2?F ，且，都构成域，证明也构成一个域。

证明：因为< S 1,+>，都是的子群，且都是阿贝尔群；

又因为< S 1, ?>，都是的子群，且都是阿贝尔群；

所以和分别是和的子群，且都是阿贝尔群。

在< S 1,+, ?>中，运算?对+是可分配的；

在< S 2,+, ?>中，运算?对+也是可分配的；

所以，在中，运算?对+也是可分配的。

因此，也构成一个域。

7-2

1. 求布尔函数F(w,x,y,z)的积之和展开式，F(w,x,y,z)=1当且仅当w,x,y 和z 中有奇数个变元的值为1。

2.证明： ) )()() )()()a x x x b xy x x y y c x y x y x y =↓=↓↓↓+=↓↓↓

3.试设计一个电路来实现5个人的多数表决票。

4.证明可以使用全加器和半加器来计算两个5位二进制整数的和。

解答：

1.()

=+++++++ ,,,

F w x y z wxy z wx yz w xyz wxyz wx y z w x yz w xy z w x y z

2. (1) 运用定律进行逻辑推理或者

(2) 真值表法

在此给出真值表的证明方法：

4.

3.

(完整版)离散数学作业答案一

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式

离散数学作业答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，

离散数学形成性考核作业4题目与答案

离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ

3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={|x∈A，y∈A且x+y≤4}，S={|x∈A，y∈A且x+y<0}，试求R，S，R?S，S?R，R-1，S-1，r(S)，s(R)． 解： R＝{<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} S=空集 R?S=空集 S?R =空集 R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>} S-1=空集 r(S) ={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R) ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} 3．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}． (1) 写出关系R的表示式；(2) 画出关系R的哈斯图； (3) 求出集合B的最大元、最小元．

离散数学(大作业)与答案

一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}

{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)

电大 离散数学作业7答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：

吉林大学离散数学课后习题答案

第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故

G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G

离散数学作业答案完整版

离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是没有任何性质． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素{,} ，则新得到的关系就具有对 称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个． 8．设A={1, 2}上的二元关系为R={|x?A，y?A, x+y =10}，则R的自反闭 包为 {<1,1>,<2,2>} ． 9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含 <1,1>,<2,2>,<3,3> 等元素． 10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是 {<1,a>,<2,b>}或{<1,b>,<2,a>} ． 二、判断说明题（判断下列各题，并说明理由．）

慕课 离散数学 电子科技大学 课后习题十 答案

作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G=，其中： V={a,b,c,d,e,f,g} E={(u,v)|u,v∈V,且u和v有共同语言} 从而图G如下图所示。 a b c d e f g 将这7个人围圆桌排位，使得每个人都能与他两边的人交谈，就是在图G 中找哈密顿回路，经观察上图可得到两条可能的哈密顿回路，即两种方案：abdfgeca和acbdfgea。 3.证明（法一）：根据已知条件，每个结点的度数均为n，则任何两个不相邻 的结点v i,v j的度数之和为2n，而图中总共有2n个结点，即deg(v i)+ deg(v j)?2n，满足哈密顿图的充分条件，从而图中存在一条哈密顿回路，当然，这就说明图G是连通图。 证明（法二）：用反证法，假设G不是连通图，设H是G的一个连通分支，由于图G是简单图且每个结点的度数为n，则子图H与G-H中均至少有n+1个结点。所以G的结点数大于等于2n+2，这与G中结点数为2n矛盾。所以假设不成立，从而G是连通图。 4.将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在 代表他们的结点之间连一条线，得到一个偶图G，假设它的互补结点子集V1、V2分别表示n位男士和n位女士，由题意可知V1中的每个结点度 1

数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2

离散数学作业答案

第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试

3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章

国开放大学离散数学本离散数学作业答案

国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021

离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题

1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是反自反性． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素 , ，则新得到的关系就具有对称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2 个．

离散数学作业标准答案

离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )

北京大学2017秋课件作业【离散数学】及答案

2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。

离散数学 作业及答案

2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：

离散数学第三次在线作业

第三次在线作业 1.（ 2.5分）不能再分解的命题称为原子命题，至少包含一个联结词的命题称为复合命题 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）命题是能够表达判断（分辩其真假）的陈述语句 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）一个命题可赋予一个值，称为真值 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）复合命题是由连结词、标点符号和原子命题复合构成的命题 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）在条件命题P→Q中，命题P称为P→Q的前件或前提，命题Q称为P→Q的后件或结论 ?正确 ?错误 我的答案：正确此题得分：2.5分

6.（2.5分）给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为T，则称该 命题公式为重言式或永真公式 ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分）给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为F，则称该命题公式为矛盾式或永假公式 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）任何两个重言式的合取或析取仍然是一个重言式 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）一个命题称为合取范式，当且仅当它具有如下的形式： A1∧A2∧…∧An，(n≥1)其中A1A2…An都是由命题变元或其否定所组成的析取式 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个命题称为析取范式，当且仅当它具有如下的形式： A1∨A2∨ … ∨An，(n≥1)其中A1A2…An都是由命题变元或其否定所组成的合取式 ?正确

离散数学 作业 3~4 答案

『离散数学』课程 作业3： P64：3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。 解：直接使用容斥原理。我们做如下设定： A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2 由容斥原理: |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6-6-5-4+2=19 —————————————————————————————————————— 但相当一部分同学没有直接使用容斥原理， 而是画了文氏图。 使用文氏图的方法，会发现此题存在问题： 表示只会打网球的同学是-1人， 此种情况与实际不符。 这可能是作者的疏忽，该教材第一版中， “已知6个会打网球的人中有4人会打排球。” 一句是写作 “已知6个会打网球的人都会打篮球或排球。” 则用容斥原理或文氏图，都可以得到5的结果。 A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2 因为“会打网球的人都会打篮球或排球。” 所以C =（A∩C）∪（B∩C） 由容斥原理: |C|=|（A∩C）∪（B∩C）| = |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）| 可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）| = 6-5+2=3 |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C| =14+12+6-6-5-3+2=20

吉林大学离散数学课后习题答案

第一章集合论基础 §1.1 基本要求 1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系 的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。 2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基 本算律，能够利用它们来证明更复杂的集合等式。 3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质： 自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。 4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。 5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最 大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。 6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数 集合的判定方法。 7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

§1.2 主要解题方法 1.2.1 证明集合的包含关系 方法一.用定义来证明集合的包含关系是最常用也是最基本的一种方法。要证明A?B，首先任取x∈A，再演绎地证出x∈B成立。由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。当A是无限集时，因为我们不能对x∈A，逐一地证明x∈B成立，所以证明时的假设“x是任取的”就特别重要。 例1.2.1 设A，B，C，D是任意四个非空集合，若A?C，B?D，则A×B?C×D。 证明：任取(x，y) ∈A×B，往证(x，y) ∈C×D。 由(x，y) ∈A×B知，x∈A，且y∈B。又由A?C，B?D知，x∈C，且y∈D，因此，(x，y) ∈C×D。故，A×B?C×D。 方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质 A?B?A?B=A?A?B=B 以及一些已经证出的集合等式。现在我们就用此方法将上例再证一次。 由下面例1.2.2证明的结论有（A×B）?（C×D）=（A?C）×（B?D），若A?C，B?D，则A?C=A，B?D=B，因此，（A×B）?（C×D）=A×B。因此，A×B?C×D。 1.2.2 证明集合的相等 方法一.若A，B 是有限集，要证明集合A=B当然可以通过逐一比较两集合所有元素均一一对应相等即可，但当A，B 是无限集时，一般通过证明集合包含关系的方法证得A?B，B?A即可。 例1.2.2 设A，B，C，D是任意四个集合，求证（A×B）?（C×D）=（A?C）×（B?D）。 证明：首先证明（A×B）?（C×D）?（A?C）×（B?D）。任取（x,y）∈（A×B）?（C×D），则（x,y）∈（A×B），且（x,y）∈（C×D），故x∈A，y∈B，x∈C，y∈D，即x∈A?C，y∈B?D，因此，（x,y）∈（A?C）×（B?D）。 由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得（A?C）×（B?D）?（A×B）?（C×D）。 因此，（A×B）?（C×D）=（A?C）×（B?D）。 方法二. 还有一种证明集合相等的方法，可以通过已证出的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。 例1.2.2 设A，B，C是三个集合，已知A?B=A?C，A?B=A?C，求证B=C。 证法1：使用反证法。假设B≠C，则必存在x，满足x∈B，且x?C，或者x?B，且x∈C。不妨设x∈B，且x?C，

离散数学形成性考核作业7答案

一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P∨Q )→R ．3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是 (P∧Q∧R)∨(P∧Q∧┐R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为x P Q x∧ ?． (x ( )) ( ) 5．设个体域D＝{a, b},那么谓词公式) x ∨ ?消去量词后的等值式为 xA? yB ) ( (y b B a A B ∨． ∨ A∧ a ) (b ( )) ( ( ) ) ( 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解：设P：今天是晴天， 命题“今天是晴天”翻译成命题公式为P。 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P：小王去旅游，Q：小李去旅游． 命题“小王去旅游，小李也去旅游”翻译成命题公式为P∧Q。 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P：明天天下雪，Q：我就去滑雪． 命题“如果明天天下雪，我就去滑雪”翻译成命题公式为P→Q。 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

西南大学《离散数学》网上作业题及答案

[0004]《离散数学》网上作业题答案 第1次作业 [论述题]第1次作业 一、填空题 1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射. 2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ). 3. 设X 是非空集合，则X 的幂集P (X )关于集合的?运算的单位元是( )，零元是( )，P (X )关于集合的?运算的单位元是( ). 4. 6阶非Abel 群的2阶子群共有( )个，3阶子群共有( )个，4阶子群共有( )个. 5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图. 二、单选题 1. 幂集P (P (P (?))) 为( ) (A){{?}, {?, {?}}}. (B){?, {?, {?}}, {?}}. (C){ ?, {?, {?}}, {{?}}, {?}} (D){ ?, {?, {?}}}. 2. 设R 是集合A 上的偏序关系，则1 -?R R 是( ). (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的. (A))(B A →?与B A ?∧. (B) )(B A ??与)()(B A B A ∧?∨?∧. (C))(C B A ∨→与C B A →?∧)(. (D))(C B A ∨→与)(C B A ∨∧?. 4.下列代数结构(G , *)中，( )是群. (A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法. (C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图4K 中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2

离散数学(第2版)_在线作业_4

离散数学(第2版)_在线作业 _4 交卷时间：2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设，下列式子正确的是( )。

纠错 得分： 5 知识点： 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点， 条边和个面的连通平面图，则 等于( )。

? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合，函数，则是( )。

? A. 11，3，4 ? B. 10，4，3 ? C. 11，3，5 ? D. 12，3，6 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y)，即x,y 的最大公约数 ? B. x*y=lcm(x,y)，即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分： 5 知识点： 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？( )。

离散数学作业答案

离散数学作业答案 TYYGROUP system office room 【TYYUA16H-TYY-TYYYUA8Q8-

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式() P Q P →∨的真值是 1 ． 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为(x)(P(x) →Q(x))． 5．设个体域D＝{a, b},那么谓词公式) ∨ xA? ?消去量词后的等值式为 ) ( x (y yB (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x) 的真值为． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为． 8．谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式．1．解：设P：今天是天晴； 则 P． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P：小王去旅游，Q：小李去旅游， 则 PQ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪。 Q:我去滑雪 则 P Q． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P：他去旅游，Q：他有时间，