离散习题(附答案) (5)
习题 5.1
1.设A=?a,b,c?，B=?1,2,3?，试说明下列A到B二元关系，哪些能构成A到B的函数？
⑴f1=?
⑵f2=?
⑶f3=?
⑷f4=?
⑸f5=?
解：⑴不能构成函数。因为
⑵能构成函数
⑶不能构成函数。因为dom f3≠A
⑷不能构成函数。因为
⑸能构成函数。
2.试说明下列A上的二元关系，哪些能构成A到A的函数？
⑴A=N(N为自然数集合)，f1=?
⑵A=R(R为实数集合)，f2=?
⑶A=R(R为实数集合)，f3=?
⑷A=N(N为自然数集合)，f4=?
⑸A=Z(Z为整数集合)，f5=?
解：⑴不能构成函数。由于1+1＜10且1+2＜10，所以<1,1>∈f1且<1,2>∈f1。
⑵能构成函数。
⑶不能构成函数。由于12=1且(-1)2=1，所以<1,1>∈f3且<1,-1>∈f3。
⑷能构成函数。
⑸能构成函数。
3. 回答下列问题。
⑴设A=?a,b?，B=?1,2,3?。求B A，验证|B A|= |B||A|。
⑵设A=?a,b?，B=?1,2?。求B A×A，验证|B A×A|=|B||A|×|A|。
解：⑴f0=?
f1=?
f2=?
f3=?
f4=?
f5=?
f6=?
f7=?
f8=?
B A=?f0,f1,f2,f3,f4,f5,f6,f7,f8?
|B A|=9=32= |B||A|
f 0=?<,1>,<,1>,<,1>,<,1>?
f 1=?<,1>,<,1>,<,1>,<,2>?
f 2=?<,1>,<,1>,<,2>,<,1>?
f 3=?<,1>,<,1>,<,2>,<,2>?
f 4=?<,1>,<,2>,<,1>,<,1>?
f 5=?<,1>,<,2>,<,1>,<,2>?
f 6=?<,1>,<,2>,<,2>,<,1>?
f 7=?<,1>,<,2>,<,2>,<,2>?
f 8=?<,2>,<,1>,<,1>,<,1>?
f 9=?<,2>,<,1>,<,1>,<,2>?
f 10=?<,2>,<,1>,<,2>,<,1>?
f 11=?<,2>,<,1>,<,2>,<,2>?
f 12=?<,2>,<,2>,<,1>,<,1>?
f 13=?<,2>,<,2>,<,1>,<,2>?
f 14=?<,2>,<,2>,<,2>,<,1>?
f 15=?<,2>,<,2>,<,2>,<,2>?
B A ×A =?f 0, f 1, f 2, f 3, f 4, f 5, f 6, f 7,f 8,f 9 f 10, f 11, f 12, f 13, f 14, f 15?
|B A ×A |=16=24=|B ||A |×|A |
4.下列函数中，哪些是单射？哪些是满射？哪些是双射？为什么？
⑴ f ：N →N ，f (x )= x 2＋1
⑵ f ：Z →Z ， f (x )=(x mod 3)(函数值为x 除以3的余数)
⑶ f ：N →N ， 为偶数若为奇数若x x x f ???=0
1
)( ⑷ f ：N →?0,1?，为偶数若为奇数若x x x f ??
?=01
)( ⑸ f ：Z ＋→R ，f (x )=3x
⑹ f ：R →R ，f (x )=x 3
解：⑴是单射，不是满射，不是双射。
当x ,y ∈A ，x ≠y ，x 2≠y 2，x 2＋1≠y 2＋1，f (x )≠f (y )。所以f ：N →N 是单射。
因为?x ∈N ，f (x )≠0∈N 。所以f ：N →N 不是满射。
因为不是满射，所以不是双射。
⑵不是单射，不是满射，不是双射。
因为6≠9，而f (6)=(6 mod 3)=0=(9 mod 3)=f (9)。所以f ：Z →Z 不是单射。
因为?x ∈Z ，f (x )≠3∈Z 。所以f ：Z →Z 不是满射。
因为不是单射且不是满射，所以不是双射。
⑶不是单射，不是满射，不是双射。
因为1≠3，而f (1)=f (3)。所以f ：N →N 不是单射。
因为?x∈Z，f(x)≠2∈N。所以f：N→N不是满射。
因为不是单射和不是满射，所以不是双射。
⑷不是单射，是满射，不是双射。
因为1≠3，而f(1)=1=f(3)。所以f：N→?0,1?不是单射。
显然，f：N→?0,1?是满射。
因为不是满射，所以不是双射。
⑸是单射，不是满射，不是双射。
f：Z＋→R，f(x)=3x是单调递增函数，所以是单射。
因为?x∈Z＋，f(x)≠0∈R。所以f：Z＋→R不是满射。
因为不是满射，所以不是双射。
⑹是单射，是满射，是双射。
f：R→R，f(x)=x3是单调递增函数，所以是单射。
因为?y∈R，有x=3y∈R，使f(x)= f(3y)=(3y)3=y。所以f：R→R，f(x)=x3是满射。
因为是单射和满射，所以是双射。
5.设A=?1,2,3,4?，A上的等价关系R为：
R=?<1,4>,<4,1>,<2,3>,<3,2>?∪I A
求自然映射f：A→A/R
解：A/R=??1,4?,?2,3??
f=?<1,?1,4?>,<2,?2,3?>,<3,?2,3?>,<4,?1,4?>?
6.设f: Z×Z→Z(Z为整数集合)，f(x,y)= x＋y；g: Z×Z→Z，g(x,y)= x×y。试证明f和g是满射函数，但不是单射函数。
证明：?x∈Z，<0,x>∈Z×Z，f (0,x)= 0＋x=x，所以f: Z×Z→Z，f(x,y)=x＋y是满射。
<1,x>∈Z×Z，f (1,x)= 1×x=x，所以g: Z×Z→Z，g(x,y)=x×y是满射。
对于<1,2>∈Z×Z，<2,1>∈Z×Z，f(1,2)=3=f(2,1)，但<1,2>≠<2,1>，所以f: Z×Z→Z，f(x,y)= x ＋y不是单射函数。
对于<3,2>∈Z×Z，<2,3>∈Z×Z，g(3,2)=6= g(2,3)，但<3,2>≠<2,3>，所以g: Z×Z→Z，g(x,y)= x×y不是单射函数。
7.设A和B是有限集合，|A|=n，|B|=m。
⑴有多少个不同的单射函数f：A→B。
解：要使f：A→B是单射函数，必须n≤m，因此，当n＞m时，无A到B的单射函数。当n≤m时，共有n m P=n(n-1)…(n-m+1)
⑵有多少个不同的双射函数f：A→B。
解：要使f：A→B是双射函数，必须n=m，此时共有m!个双射函数。请参看习题5.2的第6题。
8.设f：A→B，C?A，证明f(A)－f(C)?f(A－C)
证明：f(x)∈f(A)－f(C)?f(x)∈f(A)∧f(x)?f(C)?x∈A∧x?C?x∈A－C? f(A－C)
所以, f(A)－f(C)?f(A－C)
9.设A=?a1,a2,…,a n?，试证明任何从A到A的函数，如果它是单射，则它必是满射。反之亦真。
证明：设f：A→A是单射，下证f是满射。
反证法，设f不是满射，至少有一个元素不是f的像，设这个元素为a j，则ran f?A-?a j?，所以ran f?A，从而有|ran f|<|A|，与f是单射矛盾。
设f：A→A是满射，下证f是单射。
反证法，设f不是单射，?a i∈A，a j∈A，使f(a i)=f(a j)，而a i≠a j，构造函数
f1：A-?a i?→A，f1(x)=f(x)
因为f：A→A是满射，所以f1：A-?a i?→A也是满射。故有|A-?a i?|≥|A|。又因为a i∈A，A-?a i??A，|A-?a i?|＜|A|，所以，|A|≤|A-?a i?|＜|A|，即|A|＜|A|，矛盾。
10.设f：A→B，C?A，D?A，试证明：
⑴f(C∪D)= f(C)∪f(D)
⑵f(C∩D)?f(C)∩f(D)
证明：⑴f(x)∈f(C∪D)?x∈C∪D?x∈C∨x∈D?f(x)∈f(C)∨f(x)∈f(D)
?f(x)∈f(C)∪f(D)
即f(C∪D)= f(C)∪f(D)
⑵f(x)∈f(C∩D)?x∈C∩D?x∈C∧x∈D?f(x)∈f(C)∧f(x)∈f(D)?f(x)∈f(C)∩f(D)
即f(C∩D)?f(C)∩f(D)
11.设f：A→B。
g：B→P(A)，定义为：对于b∈B，g(b)= ?x|x∈A∧f(x)=b?。
证明：如果f是A到B的满射，则g是B到P(A)的单射。
证明：以下证明g：B→P(A)的单射。g(b)=?x|x∈A∧f(x)=b?。
设x1∈B，x2∈B且x1≠x2，因为f是A到B的满射，?y1∈A，使f(y1)=x1，?y2∈A，使f(y2)=x2。因为x1≠x2，所以f(y1)≠f(y2)，又因为f是函数，故有y1≠y2。由g的定义有，y1∈g(x1)，y2∈g(x2)。
因为f(y2)=x2≠x1，所以y2?g(x1)，故有g(x2)?g(x1)，即g(x1)≠g(x2)。
这就证明了g是B到P(A)的单射。
12.设
⑴f：A→P(A) 是单射。
⑵若a?b时，必有f(a)?f(b)
证明：⑴?a∈A，?b∈A且a≠b
当a?b时，因为a≠b，则无b?a，b?f(a)。又由偏序关系的自反性知b?b，从而b∈f(b)。f(a)
≠f(b)
当b?a时，类似的可以证明f(a)≠f(b)
⑵设a?b，x∈f(a)?x∈A∧x?a，由a?b和偏序关系的传递性?x∈A∧x?b?x∈f(b)。即
f(a)?f(b)。
习题 5.2
1.设X=?x1,x2, x3, x4?，Y=?y1,y2, y3, y4, y5?，Z=?z1,z2, z3?
f：X→Y，定义为f=?
g：Y→Z，定义为g=?
试求函数g在函数f左边的复合关系g f，验证复合关系g f是X到Z的函数。
解：g f=?
mod g f=?x1,x2,x3,x4?=X。当x1= x2时，f(x1)=f(x2)
g f：X→Z
2.设f,g,h∈R R，且f(x) =x2-2，g(x) =x＋4，h(x) =x3-1
⑴试求g f和f g
⑵g f和f g是单射？满射？双射？
⑶f,g,h中哪些有反函数？若有，求出反函数。
解：⑴g f(x)= x2+2
f g(x)=x2+8x+14
⑵g f不是单射，不是满射，不是双射。
f g不是单射，不是满射，不是双射。
⑶f不是单射，不是满射，不是双射。无反函数。
g是单射，是满射，是双射。有反函数。g-1(x)= x-4
h是单射，是满射，是双射。有反函数。h-1(x)=31+
x
3.设f：A→B，g：B→C，g和f的复合函数g f：A→C，试证明:
⑴如果g f是单射，那么f是单射。
⑵如果g f是满射，那么g是满射。
⑶如果g f是双射，那么f是单射，g是满射。
证明：⑴?x1∈B，?x2∈B且f(x1)=f(x2)，因为g是函数，g(f(x1))=g(f(x2))?g f(x1)=g f(x2)，由于g f是单射，所以x1=x2，f是单射。
⑵?c∈C，因为g f是满射，存在a∈A，使g f(a)=c，又因为f：A→B是函数，令b=f(a)，g(b)=g(f(a ))=g f(a)=c，g是满射。
⑶设g f是双射，由⑴知f是单射，由⑵知g是满射。
4.设f：A→B，f是双射，A′?A，B′?B，试证明
⑴f (f -1(B′))?B′
⑵利用f是满射，证明f (f -1(B′))=B′
⑶A′?f -1(f (A′))
⑷利用f是单射，证明A′=f -1(f (A′))
证明：⑴设f(x)∈f (f -1(B′))?x∈f -1(B′)??y∈B′使x=f -1(y)∈f -1(B′)? f(x)=y∈B′
所以，f (f -1(B′))?B′
⑵ ?y ∈B ′，因为f ：A →B 是满射，?x ∈A 使f (x )=y ? x =f -1(y )?x ∈f -1(B ′)
?y =f (x )∈f (f -1(B ′))?B ′? f (f -1(B ′))
由⑴有 f (f -1(B ′))?B ′
所以，f (f -1(B ′))=B ′
⑶ ?x ∈A ′，因为f ：A →B ，所以?y ∈B 使f (x )=y ，而y =f (x )∈f (A ′)
?x =f -1(y )∈f -1(f (A ′))，即x ∈f -1(f (A ′))?A ′?f -1(f (A ′))
⑷ ?x ∈f -1(f (A ′))，?y ∈f (A ′)使x =f -1(y )，从而y =f (x )；再由?y ∈f (A ′)，?x ′∈A ′，使y =f (x ′)。因为f ：A →B 是单射，所以，x =x ′∈A ′，故有f -1(f (A ′))?A ′
又由⑶有A ′?f -1(f (A ′))
这就证明了A ′=f -1(f (A ′))
5.设f ：A →B ，g ：B →A ，证明：
g f =I A 且f g =I B 当且仅当g =f --1且f =g -1
证明：?设g =f --1且f =g -1，下证g f =I A 且f g =I B
因为g ：B →A ，f --1：B →A ，g =f --1，所以?y ∈B ，g (y )=f -1(y )。令g (y )=f -1(y )=x ，则g (y )=x ，y =f (x )。 又由f =g -1? f ：A →B ，g -1：A →B ，且?x ∈A ，f (x )=g -1(x )。由此y =f (x )=g -1(x )?g (y )=x
所以，g f (x )=g (f (x ))=g (y )=x =I A (x )，f g (y )=f (g (y ))=f (x )=y =I B (x )
显然，g f ：A →A ，I A ：A →A ；f g ：B →B ，I B ：B →B
这就证明了g f =I A 且f g =I B
?设g f =I A 且f g =I B ，下证g =f --1且f =g -1
因为恒等函数I A 是双射，所以g f ：A →A 是双射，由习题5.2的第3题⑶，f 是单射，g 是满射。
同样，恒等函数I B 是双射，所以f g ：B →B 是双射，由习题5.2的第3题⑶，g 是单射，f 是满射。
所以，f 和g 都是双射函数，他们的反函数都存在。
g ：B →A ，f --1：B →A
?y ∈B ，由f --1：B →A ，令f --1(y )=x ∈A ?f (x )=y
g (y )=g (f (x ))=g f (x )=I A (x )=x = f --1(y )，显然，g ：B →A ，f --1：B →A
所以，g =f -1
类似的可以证明，f =g -1
6.设A =?a 1,a 2, …, a n ?，函数f ：A →A 是双射。称双射f 为集合A 上的置换，n 称为置换阶，常记为：
???
? ??=)()()(2121n n a f a f a f a a a f 由于f 是双射，f (a 1),f (a 2),…,f (a n )都是A 的元素且互不相同。因此f (a 1),f (a 2),…,f (a n )必为a 1,a 2, …, a n 的一个排列。而a 1,a 2, …, a n 的排列总数是n !个，因此集合A 上的n 阶置换的数目是n !个。即A 到A 是双射函数有n !个。
设A =?1,2,3?，集合A 上应有3!=6个3阶置换。写出集合A 上的所有3阶置换。
解：????
??321321 ???? ??231321 ???? ??312321 ???? ??132321 ???? ??213321 ???? ??123321
7.如果某人营造了n 个鸽舍，养了多于n 只鸽子，则必有一个鸽舍住有2只或2只以上的鸽子。这就是鸽舍原理。
用数学语言将这个原理抽象为：设A ，B 是有限集合，f 是A 到B 的函数，如果|A |＞|B |，则A 中至少有两个元素，其函数值相等。
更一般的情况是：当鸽舍为n 个，鸽子数大于n ×m 只时，必有一个鸽舍住有m 十1个或多于m +1个鸽子。
用数学语言抽象为：设A ，B 是有限集合，f 是A 到B 的函数，如果|A |＞n ×m ，|B |＝n ，则在A 中至少有m +1个元素，其函数值相等。
例如，有3个鸽舍，13只鸽子。A 是鸽子构成的集合，|A |=13＞3×4。B 是鸽舍构成的集合，|B |＝3。则必有一个鸽舍，住有4＋1=5个或5个以上鸽子。
利用鸽舍原理解下列各题：
⑴任意n +1个正整数，其中必有两个数之差能被n 整除。
⑵在边长为1的正三角形内，任取7个点，证明其中必有3个点联成的小三角形的面积不超过12
3。 解：⑴由于任意正整数被n 除后，其余数只能是0，1，…，n -1共n 种，所以在n +1个正整数中，必有两个数被n 除后余数相同，这两个数之差必能被n 整除。
⑵ 如图5.6所示，△ABC 是边长为1的正三角形，点O 是△ABC 的重心，连接OA 、OB ，
OC ，则将△ABC 分为面积相等的3个小三角形，每个小三角形的面积都为：31×21×23=12
3。
把小三角形作为“鸽舍”，点作为“鸽子”，则有7只鸽子，3个鸽舍。而INT(7/3)=2，由鸽舍原理，7个点中至少有3个点在同一个小三角形中，由这3个点联成的三角形的面积必小于小三角形的面积12
3。 习题 5.3
1.证明区间(0,1)和区间[0,1]等势。
证明：设f ：(0,1)→[0,1]，f (x )=x 是单射函数。|(0,1)|≤|[0,1]|。
又设g ：[0,1]→(0,1)，g (x )=4
12 x 是单射函数。|[0,1]|≤|(0,1)|。故|(0,1)|=| [0,1]|。 2.设A ,B ,C ,D 是任意集合，A ~B ，C ~D ，证明A ×C ~ B ×D
证明：因为A ~B ，所以，存在f ：A →B 是双射函数。
因为C ~D ，所以，存在g ：C →D 是双射函数。
令h ：A ×C →B ×D ，定义为：h ()=
以下证明h 是单射函数：设≠，则有下列3种情况：
⑴a 1≠a 2且c 1=c 2
因为，f ：A →B 是单射函数，所以，f (a 1)≠f (a 2)，故< f (a 1), g (c 1)>≠
⑵a 1=a 2且c 1≠c 2
类似⑴可以证明h 是单射函数。
⑶a 1≠a 2，且c 1≠c 2，
类似⑴和⑵可以证明h 是单射函数。
综上所述，h 是单射函数。
以下证明h 是满射函数：?∈B ×D ，则b ∈B ，d ∈D
因为，f ：A →B 是满射函数，所以，?a ∈A 是f (a )=b 。
因为，g ：C →D 是满射函数，所以，?c ∈C 是g (c )=d 。
h 是满射函数。
故h ：A ×C →B ×D 是双射函数。A ×C ~ B ×D
3.设N 是自然数集合，A =?x |x =n 5∧n ∈N ?，证明A 是可数集。
证明：令a i =i 5，则集合A 可用列举法表示为：
A =?05,15,25,35,… ?=? a 0,a 1,… ?
A 是能用自然数编号的无限集，根据定理5.3.5，A 是可数集。
4.设Q 是有理数集合，证明叉乘积Q ×Q 是可数集。
证明：由例5.13知Q 是可数集，Q 的元素能用自然数编号。设Q=? a 0,a 1,a 2,…?
…
…
即Q ×Q 可以表示为可数个可数集的并集。由定理5.3.8知，Q ×Q 是可数集。
5.设N 是自然数集合，证明|P (N )|=?。
证明：
⑴作函数h ：P (N )→[0,1]，h 如下定义：?S ∈P (N )
h (S )=0.x 0x 1x 2x 3…(2进制小数)，其中
S
i S i x i ?∈???=01
例如，h (?)=0， h (N )=0.1111…，h (?1,4,5?)=0.010011。
显然，h 是单射函数。|P (N )|≤|[0,1]|
⑵作函数k ：[0,1]→P (N )，k 如下定义：?x =0.x 0x 1x 2x 3…∈[0,1] (x 是2进制小数，如果x 没有唯一表示，可任意选择其中之一)
k (x )= ?i |x i =1?
例如，k (0)=?， k (1)= k (0.1111…)=N ，h (0.010011)= ?1,4,5?。
显然，k 是单射函数。|[0,1]|≤|P (N )|
由⑴和⑵得|P (N )|=|[0,1]|
6.如果A 是不可数无限集，B 是A 的可数子集，证明(A －B ) ~ A 。
证明：显然A －B 是无限集，B 是可数集。因为B 是A 的子集，所以，A =(A －B )∪B ，从而，|A |=|(A －B )∪B |，由习题5.3的第7题的结论得，|A |=|(A －B )∪B |=|A －B |，即(A －B ) ~ A 。
7.如果A 是任意无限集，M 是一个可数集，证明 (A ∪M ) ~ A
证明：如果A 是任意可数无限集，由定理5.3.8知，可数集的并集是可数集。A ∪M 是可数集。得|A ∪M | =|A |，即(A ∪M ) ~ A
如果A 是任意不可数无限集，由本习题第8题⑴和定义知：
|A ∪M | =|A |+|M | =?+?0=?=|A |，即(A ∪M ) ~ A
8.设A ,B ,D 是任意集合，A ∩B =?，A ∩D =B ∩D =?，|A |=a ，|B |=b ，|D |=d 。定义
a ＋
b =|A ∪B |，a ×b =|A ×B |
证明
⑴ ?＋?0=?。
⑵ 如果a ≤b ，则a ＋d ≤b ＋d 。
⑶ 如果a ≤b ，则a ×d ≤b ×d 。
证明：⑴令A =?x | x ∈R ∧x ≥1 ?，B =?2
1+n | n ∈N ?，显然，|A |=?，|B |=?0，A ∩B =?，A ∪B ? R 。作函数f ：A ∪B →R ，?x ∈A ∪B ，f (x )=x 。显然，f 是A ∪B 到R 的单射函数。所以|A ∪B |≤|R |=?。即|A ∪B |≤?。
又因为A ?A ∪B ，所以|A |≤|A ∪B |，即?≤|A ∪B |。
所以，|A ∪B |=?。再由本题的定义有?＋?0=|A |＋|B |=|A ∪B |=?。
⑵ 因为a ≤b ，即|A |≤|B |，有一单射函数f ：A →B ；设g ：D →D ，g (x )=x ，显然，g 是D 到D 的单射函数。定义h ：A ∪D →B ∪D 为：
h (x )=时
当时当D x A x x g x f ∈∈???)()
( ?y ∈B ∪D ，因为B ∩D =?，则y ∈B 且y ?D 或y ∈D 且y ?B 。
当y ∈B 时，y ?D ，由于f ：A →B 是单射函数和A ∩D =?，所以A 中必有唯一的x 使h (x )=f (x )=y 。 当y ∈D 时，y ?B ，由于g ：D →D ，g (x )=x ，是单射函数和A ∩D =?，所以D 中必有唯一的y 使h (y )= g (y )=y 。
所以，h ：A ∪D →B ∪D 是单射函数。故|A ∪D |≤|B ∪D |，即a ＋d ≤b ＋d
⑶ 因为a ≤b ，即|A |≤|B |，有一单射函数f ：A →B ；设g ：D →D ，g (x )=x ，显然，g 是D 到D 的单射函数。定义h ：A ×D →B ×D 为：h (
?
①x≠a，y=b，由于f：A→B是单射函数，所以f(x)≠f(a)，h(
②x=a，y≠b，由于g是D到D的单射函数，所以g(y)≠g(b)，h(
③x≠a，y≠b，可类似⑴和⑵证明。
离散数学(第五版)清华大学出版社第2章习题解答
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些就是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个就是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
离散数学第五版 模拟试题 及答案
《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
离散数学作业答案
离散数学作业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 去工作，
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( )
(1)北京是中华人民共和国的首都。(2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？(4) 若7+8＞18，则三角形有4条边。 (5) 前进！(6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x存在整数y满足x+y=0 （2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1）F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）
自考离散数学教材课后题第五章答案
习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致)
大学本科高等数学《离散数学》试题及答案
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学(第五版)清华大学出版社第1章习题解答
离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。
电大 离散数学作业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分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
屈婉玲版离散数学课后习题答案
第四章部分课后习题参考答案 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 ?，在（a）中为假命题，在 xF (b)中为真命题。 (2)在两个个体域中都解释为)(x ?，在（a）(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (2)F(x): x是卖菜的人
H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ ( ( )) ( H ) x ((y , (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x F x y G ∧ ? H ?? y→ ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 离散数学（第五版）清华大学出版社第1章习题解答1．1除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2（1）p:2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命可编辑范本 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。 离散数学作业答案 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={ 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 离散数学（第五版）清华大学出版社第6章习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对 给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定 离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 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 ( 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) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解： 1 / 15 离散数学（2）复习题 一、单项选择题 1、由集合运算定义，下列各式正确的有（ A ）。 A.X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y 2、设A B -=?，则有（ C ）。 A.B =? B.B ≠? C.A B ? D.A B ? 3、对任意的集合A 、全集U ，下列命题为假的是（ D ）。 A.A ?? ＝A ， B.A ?U = U C.A ?? = ?， D.A ?U = U 4、集合A={1，2，…，10}上的关系R={山东大学离散数学题库及答案
离散数学(第五版)清华大学出版社第
离散数学作业答案完整版
离散数学习题详细答案
离散数学(第五版)清华大学出版社第6章习题解答
离散数学作业7答案(数理逻辑部分)
021046[离散数学(2)] 天津大学机考题库答案
- 离散数学(第五版)清华大学出版社第4章习题解答
- 离散数学(第五版)清华大学出版社第1章习题解答
- 离散数学(第五版)清华大学出版社第6章习题解答
- 离散数学习题答案
- 离散数学习题及参考答案1
- 离散数学练习题及答案
- 离散数学习题详细答案
- 离散数学第五版前3章课后习题答案
- 离散数学第五版前3章课后习题答案
- 《离散数学》第五版-屈婉玲著-第1章课后习题答案
- 自考离散数学教材课后题第五章答案
- 离散数学习题答案-2015年
- 离散数学习题答案
- 离散数学(第五版)清华大学出版社第7章习题解答
- 《离散数学》第五版-屈婉玲著-第3章课后习题答案
- 离散数学(第五版)清华大学出版社第
- 离散数学期末练习题 带答案
- 离散数学课后习题及答案 左孝凌版
- 离散数学第五版清华大学出版社第1章习题解答
- 离散数学第五版课后答案