离散数学习题4
第4章
1．D 对运算不封闭
2．（2）（5）（6）对运算可结合
3．1f ，2f ，3f 可交换；4f 满足幂等律；2f 有单位元；1f 有零元 4．给出的例子如下所示：
①、②、⑩
③
④
⑤
* a * 0 1
* a b
* a b
a a
0 0 0 a a b a a a 1 0 1 b b a b a a
⑥，⑦
()()b a b b a b ??≠??
⑧0,1均为左零元
⑨1为右单位元 * a b
* 0 1
* 0 1
a a b
0 0 0
0 1 0 b
a a
1 1 1
1 1 1
5．（1）可交换。是单位元。均可逆，且?a ,,,a b c d 1a a ?=;1b d ?=;1c c ?=;。 1d b ?=（2）
不可交换。b 是单位元。b 可逆，且?1b b ?=，均不可逆。
,,a c d 6．A ，C ，D 均构成半群。
7．D 构成独异点
8．，是子代数
1S 3S 9．{}0，{}0,2，{}0,1,2,3共有三个子代数
10．（1）?满足交换律。,,x y z R ?∈，因()2224446()x y z xyz xy xz yz x y z x y z ??=???+++?=?? 故满足结合律。
（2）设226x y xy x y x ?=??+=，即(2)(3)0x y ??=，故2x =或3y =，2是零元，3是单位元。
（3）对任意元素x R ∈，设，则当226x y xy x y ?=??+=32x ≠（即不为零元）时，有逆元为
23
2x y x ?=
?。 11．（1），易证，故,,a b c Q ?∈()()a b c a b c ??=??(,)Q ?是半群。因a b b a ?=?，,故?可交换。
,a b Q ?∈（2）设为其单位元，则应有：
，a e e a Q ?∈e a a ?=?=，即a e ae a +?=，由的任意性，有。所以单位元为0。
a 0e =（3）设有逆元，则应有：，故当a
b 0a b a b ab ?=+?=1a ≠时，有逆元为：1
1
a
a a ?=
?，当1a =时，没有逆元。
12．显然D 是上二元运算。对于任意的S S z y x ∈,,，有
()()()()x y z x y a z x a y a z x a y a z =??=????=????D D D ()()x a y z x y z =??=D D D
D 是可结合的，故(,也是一个半群。
)S D 13．（1）{1}（自然数集）
（2）{0
（3）{1N +=}{0}+=,2}Z +?=
（4）Z Z +=
（5）{2, （6）{6（正整数集）
3}{2,3,4,}+="}{9}18N ++∩=14．（1）；
（2）。
010100100,010001001??????
??????????
???
?023*********,000,000000001001??????
????????????????????????
（3）；
010001100010100,100,010,001001010001100????????
????????????????????????????????
15．（1）是。
（2）不是。因为当时，在0>n n P 中无逆元。
（3）是。 （4）不是。结合律不成立。
（5）是。
（6）是。
（7）不是。结合律不成立。（8）是。
（9）不是。除零次多项式外，均没有逆元。
（10）是。
16．（2）是不可结合，不是半群。除（2）外运算均满足结合律。
对（1），存在单位元１，但不是每个元素均存在逆元，故是含幺半群。 对（3），不存在单位元，故是半群。
对（4），存在单位元１，但不是每个元素均存在逆元，故是含幺半群。（可以验证） 对（5），存在单位元，且，有 1001??????101x G ???∈????111110*********x x x x ????????????=?=??????????????????
0?
??故每个元素，存在逆元101x G ??∈?
???
101x ???
?
???。是群。 17．（4）（5）（6）构成群
18．由A 生成的子群为{},{1,4,5},{2,3}?，方程{}2,3,4A X ⊕=的解为：{1,2,3,5}X =。 19．由a a ，两边同时左乘，即得a =D 1
a ?1
1a a
a a a a e ??===D D D 。
20．显然D 是二元运算，根据群的定义，需证运算满足结合律，有单位元，每个元素有逆元。
,,a b c Z ?∈，有
()2(2)24(a b c a b c a b c a b c a b c =+?=+?+?=++?=D D D D D ))=+?=D 222a a 故()，结合律成立。
(a b c a b c =D D D D 2是单位元，事实上，；222a a a a =+?=D a Z ；?∈。
a Z ?∈，由(4)(4)22a a a a ?=+??=D ；(4)(4)22a a a a ?=?+?=D 可知是的逆元。
4a ?a 由上可知是群。 ),(D Z 21．M 对运算构成群：
D 首先，，有,,,a b c d M ?<><>∈,,,a b c d R ∈，且,a c 0≠，于是,ac ad b R +∈，且，从而，D 是0ac ≠,,,a b c d ac ad b M <><>=<+>∈D M 上的二元运算。 其次，，有
,,,,,a b c d e f M ?<><><>∈()(),,,,,,a b c d e f a b c d e f <><><>=<><><>D D D D ，结合律成立。
1,0<>是M 上关于的单位元。事实上，D ,a b M ?<>∈,有
1,0,1,0,a b a a b a b <><>==<>D
,1,01,10,a b a b a b <><>==<>
D
最后，,是,a b M ?<>∈1
1
,a a b ??,a b <>的逆元。事实上，
1111,,,()1a b a a b a a a a b b ????<><>==<>D ,01,0
11111,,,a a b a b a a a b a b ?????<>==<>D
得证是群。
),(D M 22．由条件，有，由于是群，运算满足结合律和消去律，有，故
。
()()()()ab ab aa bb =()()a ba b a ab b =ab ba =23．x 和1
x ?的阶数相同。又当x 的阶数大于２时，1
x x ?≠。注意到映射1:f x x ?→是群的一个双射。从而阶数大于2的元素成对出现（x 和1
x ?是一对）
。故其个数必为偶数。 24．由于群中阶数大于2的元素个数是偶数（上题），又单位元是群中惟一的一个阶数为１的元素。而群中总元素个数（群的阶）为偶数，故阶为２的元素必有奇数个。
25．当1
x x ?≠时，x 和1
x ?在群中成对出现，其总的个数必为偶数。因此，在群中1
x x ?=，即2
x e =的元素个数也为偶数。e 满足，故除e 以外，至少还有一个，使得2
e =e e a 2
a =。
26．因为群，G ,x y G ∈，且，故1yxy x ?=2()
2
4
211112()()()2x x
yxy yxy y yxy y y xy ????====?
因是2阶元，有，且，故y 2y =e 2y e ?=4x x =，有3x e =，又x 的阶不可能为2或1。否则2
x e =，由可得1yxy x ?=2yx y =，从而x e =矛盾。故x 的阶为3。
27．由H 非空，知1
x H x ???非空。1,a b x H x ??∈??，即存在12,h h H ∈使得1112,a x h x b x h x ??=??=??，
有因1111111111
1?121212()()()()a b x h x x h x x h x x h x x h h x ???????????=?????=?????=???H 为子群，有
112h h h H ?Δ?∈，从而。所以11a b x h x x H x ???=??∈??1?1x H x ???为子群。
28．因是有限群，只需说明运算封闭就可以了。
4S （1），（4）是子群。可以举例说明（2），（3）均不为子群，对（2）或（3），如：
12341234,22413412f g A f g ???==∈=????
???D A ?
??
，对运算不封闭。 29．需证具有自反、对称、传递性。
R x G ?∈，因为1x e x e ?=??，其中e 为中单位元，故G xRx 。自反。
R ,a b G ?∈，若，即aRb G θ?∈，使1b a θθ?=??，则111()a b b θθθθ1????=??=??G ，因为群，
G θ∈，有，故。对称。
1G θ?∈bRa R ,,a b c G ?∈，若，，即aRb bRc 1G θ?∈使111b a θθ?=??，2G θ?∈，使12c b 2θθ?=??，则
，因1121122121()()c a a θθθθθθθθ???=????=????112,G θθ∈，有12G θθ?∈，故aRc 。传递。
R 得证R 等价。
30．假设A G ≠且B G ≠，则且,a A a B ?∈?,b B b A ?∈?（否则对任意的a A ∈，有，从而，即a B ∈A B ?A B B ∪=，得，矛盾）
。 B G =对元素a b ，若，因G ?∈a b A ?∈A 是子群，1
a ?A ∈，从而1()a a
b b A ???=∈，故矛盾，得。同理可证，综合有a b 。 a b A ??a b B ??A B G ??∪=综上所述，假设不成立，得证A G =或B G =。 31．不构成。
32．设的单位元为，则是的一个子群。因G e eH H =G H 的左陪集的全体构成G 的划分，即H 的左陪集或者相同，或者不相交，故其它左陪集均不含。而作为子群，至少必须含有单位元，故除e H 外，其它左陪集均不是的子群。
G 33．设为循环群，则对任意()G a =,x y G ∈，k x a =，l y a =，从而k l l k x y a a y x ++===D D ，故是循环群。 G 34．略。
35．,,x y z B ′′′?∈,因
是满射，存在f ,,x y z A ∈，使得(),(),()f x x f y y f z z ′′′===，于是，由f 是
同态，有
(*)*(()*())*()()*()(())x y z f x f y f z f x y f z f x y z ′′′===D D D
(())()*()()*(()*())*(*)f x y z f x f y z f x f y f z x y z ′′′====D D D
所以*是可结合的；
设是的单位元，，则e A ∈G ()e f e B ′=∈*()*()′x e f x f e ′=()()f x e f x x ′===D 。同理可证，
。故e x x ′′′?=e ′是的单位元。
B 又对于x B ′∈,因为111*()()*()()()x f x f x f x f x x f e e ???′′===D =；同理可证1()*f x x e ?′′=。故
是的逆元。
B x f ∈?)(1x ′综上所述，证得H 是一个群，且f 是G 到H 的同构映射，从而G 与H 同构。
36．（1）Ke ； （2）r(){0}h =Ker()h Z =；
（3）Ker()5h Z =； （4）Ker(){0}h =。 37．（1）12121212()()()f x x x x x x f x f x ===，()f x x =是到的同态。G G Im f R +=，
。
Ker(){1,1}f =?
（2）121212121212()2,()()4,()()()f x x x x f x f x x x f x x f x f x ==≠，故()2f x x =不是G 到的同态。
G （3）22212121212()()()()f x x x x x x f x f x ===，故2()f x x =是到的同态。G G Im f R +=，
。
Ker(){1,1}f =?（4）()()12121212()1()11()()f x x x x x x f x f x ===，故()1f x x =是到的同态映射。
G G Im f G =，。Ker(){1}f =f 是的自同构。
G （5）1212121212(),()()()()f x x x x f x f x x x x x =?=??=，有1212()()()f x x f x f x ≠，故()f x x =?不是到G 的同态映射。
G （6），1212()f x x x x =+11212()()(1)(1)f x f x x x =++，1212()()()f x x f x f x ≠，故()1f x x =+不是到G 的同态映射。
G 38．需证f 是双射且为同态。若()()f x f y =，即1****a x a a y a 1??=，由群的消去律可知x y =。故f 是单射；又对g G ?∈，有11(**)*(**)*1f a g a a a g a a ??g ?==，故f 是满射；因对任意的,x y G ∈，有111(*)*(*)*(**)*(**)()*()f x y a x y a a x a a y a f x f y ???===，故是自同态映射。
f
综上所述，f 是G 的自同构。
39．A 的一一变换共有3!个，它们分别是（1）()，（2）(，（3），（4）()，（5），（6）。其中只有（1）和（5）是自同构。
6=()()a b c ))abc ()()a bc acb ()()ab c ()()ac b 首先，（1）和（5）都是双射。再由于()()()(f x y f c c f x f y ?===?，故是同态映射。故只有
（1）（5）是自同构，而（2）（3）（4）（6）不是。 f
40．（1）
(对运算封闭，单位元为的逆元为，运算满足结合律。故)?},,{a e a e ,a ()?},,{a e 在下是群。
?（2）设{,，则}e a M =M 的所有右陪集有：,{,},{,}M M b a b M c b c ?=?={,}，M d c e ?=。若为群，则应满足G G G M M =?，而实际上，5G =，2M =，4G M =。故G 不是群。 41．（1）由同态基本定理的推论，()124K G h G ===；（2）4K =；（3）1243G K G K ===。
42．（1）因为对任意的11,0101x y H ????∈?
???????，有111010101x y x y H +??????
?=∈????????????
，故H 对运算是封
闭的，且因矩阵运算是可结合的，只需说明H 存在单位元，每个元素有逆元即可。
显然1001H ??∈?
???是单位元，且因，故
111110*********x x x x ????????????=?=??????????????????0?
??
1
110101x x ?????=?????????
，每个元素都存在逆元。
（2）因0101101H x R x ????????=∈???
???????????，而0111010x H x R ????????
=∈??????????????
，有；
01011010H H ????≠????????（3）因对任意的，有01/y z T y ??∈?
?
??0,01/01/y z y
yx z H y z R y y ??+??????
=≠∈??????
????????
， /0,01/0
1/y z y
z x y H y z R y y ??+??????
=≠∈??????????????
01/01/，故y z y z H H y y ????=?
??????? 由的任意性，有01/y
z T y ??∈?
???
H 是正规子群。
（4）因为对任意的，11101/y z T y ??∈?
???2
2201/y z T y ??∈???
?，有
112212
121212
1212/01/01/01/()y z y z y y y z z y h h y y ?=??11221201/01/y z y z h h y y ??????=??????????
???y y y y ???+???????=???????????????????
?????
故h 是群同态，且由h 的定义可知：Ker()h H =。 43．若H 是正规子群，则。有,aH Ha a G =?∈1
aHa
H ?=，则h H ?∈，1a h a H ???∈；
若对任意的，，则有。另一方面，对任意的，有
，其中，从而,a G h H ∈∈1
a h a H ???∈1aHa H ??h H ∈1()h a a h a a ?=????1?a G ∈1a G ?∈，则依据条件有，从而，有1a h a H ???∈111()h a a h a a aHa ???=????∈1?H aHa ?。得证1aHa H ?=。H 是正规子群。
44．因1
xHx
?是的子群。令G 1(),h xhx h H ??=?∈。易验证?是H 到1
xHx
?的双射，从而
1xHx H n ?==，即1xHx ?是G 的阶子群。由题设，这样的子群惟一，故n 1xHx H ?=。得证H 是G 的
正规子群。
45．1(())x f f a ??∈，()()f x f a =，11()(())()H f a x f a f x e ??==，其中H e 为H 的单位元。故
。于是，1k a x K ?=∈x ak aK =∈。得证1(())f f a aK ??。另一方面，k K ?∈，()f k 是的单位元，
G ()()()()f ak f a f k f a ==，故，得。得证1(())ak f f a ?∈1(())aK f f a ??1(())f f a aK ?=。
46．K 是的子群，G H 是K 的子群，则H 是的子群。由拉格朗日定理，有G G G K K =?；
G G H H =?；K K H H =?。可得G K K H H G H H ??=?，两边消去H ，可得G H G K K H =?。
47．C 构成环。
48．不难验证(,)C +是一交换群，且是一半群。且
对＋的右分配律成立，即
(,)C D D
()()()()(())(())(())()()f g h x g h f x g f x h f x f g f h x +=+=+=+D D D ，但D 对＋的左分配律不成立。
例如：2()f x x =，()g x x =，，则()1h x =()()()x 2
()()()(1)g h f x f g x h x +=+=+D 1+，但
2()()(())(())g f h f x f g x f h x x +=+=D D ，两者不等。故C 不构成环。
49．A 构成整环。
50．（1）()
,A A ?是交换群。
因是环，故是交换群。对于(,,)A ⊕?(,)A ⊕,A f g A ?∈，x A ?∈，()()()()f g x f x g x ?=⊕，
运算
封闭且满足交换律和结合律。()?()()()()()0f f x f x f x ??=⊕?=，其中()f x ?是()f x 的逆
元。由于⊕x 的任意性，得(),A A ?中，函数f 的逆元为f ?。故()
,A A ?是交换群。
（2）()
,A A ?是半群。
因(,是环，故(是半群。对于,)A ⊕?),A ?,A f g A ?∈，x A ?∈，()()()()f g x f x g x ?=?，
运算封闭且满足结合律。故(
?)
,A A ?是半群。
（3）运算?对运算
有分配律。对于?,,A f g h A ?∈，x A ?∈，?对⊕有分配律，
因
()()()()()()()()()()()()()f g h x f x g x h x f x g x f x h x ??=?⊕=?⊕?
()()()()()()()()()()f g f h x f x g x f x h x ???=?⊕?，
有 ()()()()()()f g h x f g f h x ??=???。同理，()()()()()()g h f x g f h f x ??=???。
由于x 的任意性，有()()()f g h f g f h ??=???，且()()()g h f g f h f ??=???。 故运算?对运算
的分配律成立。
?
综上所述，()
,,A A ??是环。
离散数学练习题(含答案)
离散数学试题 第一部分选择题 一、单项选择题 1．下列是两个命题变元p，q的小项是（ C ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ A ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ C ） A．┐(?x)A?(?x)┐A B．(?x)(B→A(x))?B→(?x)A(x) C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y) 5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ C ） A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z) C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z) 6．设A={a,b,c,d}，A上的等价关系R={
离散数学屈婉玲版第一章部分习题汇总
第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数.
是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
离散数学习题
第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);
离散数学试题及答案精选版
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 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＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
离散数学题目大汇总
离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若
离散数学结构 习题5
习题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)
离散数学(本)复习题
离散数学（本）复习题 1.请给出公式G=（P→（Q→P））→（?P→（P→Q））的真值表。 2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系R C。 3.R，S是集合A上的两个关系。试证明下列等式： （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R （3）(R∪S)-1= R-1∪S-1 （4）(R∩S)-1= R-1∩S-1 4.设R是集合A上的关系，令 R+={(x, y)|x∈A，y∈A，并且存在n>0，使得xR n y}， 则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。 5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。 6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，R）的Hasse图。 7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？ 9.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。 10.若R是等价关系，试证明R-1也是等价关系。 11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值： a) (P∧(Q∧R))∨?((P∨Q)∧(R∨S)) b) (?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S) c) (?(P∧Q)∨?R)∨((Q??P)→(R∨?S)) d) (P∨(Q→(R∧?P)))?(Q∨?S) 12.试将下列公式化成等价的前束范式： (1)?x(P(x)→?yQ(x，y))； (2)?x((??yP(x，y))→(?zQ(z)→R(x)))； (3)?x?y(?zP(x，y，z)∧(?uQ(x，u)→?vQ(y，v)))。 13.设S={G1，…，G n}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。 14.证明下面的等价式： (1) (?P∧(?Q∧R))∨(Q∧R)∨(P∧R)=R (2) P→(Q→P)=?P→(P→Q) (3) P→(Q∨R)=(P→Q)∨(P→R) (4) (P→Q)∧(R→Q)=(P∨R)→Q 15．找出下面公式的Skolem范式： (1)?(?xP(x)→?y?zQ(y，z))； (2)?x(?E(x，0)→(?y(E(y，g(x))∧?z(E(z，g(x))→E(y，z)))))。 16．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n≤2 C，其中2m C表示 m m中取2的组合数。
离散数学题库
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
最新离散数学习题答案
离散数学习题答案 习题一及答案：（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 →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值：
（4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： ) ()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学深刻复知识题(全)
离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，
最新离散数学试题库
15.设D的结点数大于1，D=
离散数学 练习题及答案
命题逻辑 例1: 下面哪些语句是命题 十是一个整数. 真命题 北京是一个村庄. 假命题 我学英语或法语. 复合命题 如果天气好,我就去散步. 复合命题 向右看齐! 不是命题 您吃饭了吗? 不是命题 本命题是假的. 不是命题 例2：试以符号形式写出下列命题 1） 选小王或小李中的一人当班长。 P: 小王当班长。 Q: 小李当班长。 ( P ∧ ? Q) ∨ (? P ∧ Q) 2） 小王是计算机系的学生，他生于1982年，他是一个好学生。 P: 小王是计算机系的学生。 Q: 他生于1982年。 R: 他是一名好学生。 P ∧ Q ∧ R 3） 只要我上街，我就去书店看看，除非我很累。 P: 我上街。 Q: 我去书店看看。 R: 我很累。 ? R →(P → Q) 例3 给出下列公式的真值表 成真指派：100，101，110，111 例4 试求下面公式的主析取（主合取）范式，并写出成真指派和成假指派。()()P Q Q P ?→→?∨ 例5 证明：P →Q ，?Q ∨R ，?R ，?S ∨P=>?S 证明： (1) ?R 前提 (2) ?Q ∨R 前提 (3) ?Q （1），（2） (4) P →Q 前提 (5) ?P （3），（4） P R Q P →→∧)(
(6) ?S ∨P 前提 (7) ?S （5），（6） 例6 证明：A ，A →B ，A →C ，B →(D → C) => D 证明： （1） A 前提 （2） A →B 前提 （3） B (1)，(2) （4） A →C 前提 （5） C (1)，(4) （6） B →(D →?C) 前提 （7） D →?C (3)，(6) （8） ?D (5)，(7) 例7 证明：?B ∨D ，(E →?F)→?D ，?E=>?B 证明： (1) B 附加前提 (2) ?B ∨D 前提 (3) D （1），（2） (4) (E →?F)→?D 前提 (5) ?(E →?F) （3），（4） (6) E ∧?F （5） (7) E （6） (8) ?E 前提 (9) E ∧?E （7），（8） 例8 证明： 谓词逻辑 例1 符号化下列命题 不是所有的男人都比女人高。 M(x):x 是男人，W(x):x 是女人，H(x,y):x 比y 高。 P Q Q P P Q →?∧∨→))(())) ,()(()((y x H y W y x M x →?→??
离散数学练习题及答案
离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群}
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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
离散数学习题集十五套 答案
离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集,E + 正偶数) 则 =?B A 。 2.A ，Ｂ,Ｃ表示三个集合，文图中阴影部分的集合表达式为 。 3.设P ，Q 的真值为０，R ，S 的真值为１，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4.公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 ５．若解释I 的论域D 仅包含一个元素,则 )()(x xP x xP ?→? 在Ｉ下真值为 。 6．设Ａ={１，2,3,4｝，A 上关系图为 则 R 2 = 。 ７．设Ａ={ａ，ｂ，c ，ｄ｝,其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 ９．设A ＝｛a,b,ｃ，d ｝ ，A 上二元运算如下: ＊ a b c d A B C
a b ｃ d a b c ｄ b c d a c d a b dａ b c 那么代数系统 离散数学 一、选择题 1.给出下列语句： （1）5能被2整除. （2）2是素数当且仅当三角形有三条边. （3） x+5>0. （4）4是2的倍数或是3的倍数. （5）明天我去看电影. 其中 （1）（2）（4）（5） 是命题； （2）（4） 是复合命题。 2.给出以下命题： （1）1+2=3743321)2(.743≠+→≠+≠+→. （3）743321)4(.743521=+→=+=+?≠+. 其中真值是T 的命题是 (2)(4) 。 3.给出下列语句： （1）5能被2整除. （2）雪是黑色的当且仅当太阳从西方升起. （3） x+5>0. （4）小李在宿舍里. 其中 （1）（2）（4） 是命题； （2） 是复合命题。 4.给出以下命题： （1）1+2=3743321)2(.743≠+→≠+≠+→. （3）743321=+?≠+. (4)743321=+→=+ 其中真值是F 的命题是 （1）（3） 。 5. 设C (x ): x 是国家级运动员，G (x ): x 是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( D )。 ))()(()A (x G x C x ?∧?? ))()(()B (x G x C x ?→?? ))()(()C (x G x C x ?→?? ))()(()D (x G x C x ?∧?? 6.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( C )。 (A) 1∈A (B) {1,2, 3}?A (C) {{4,5}}?A (D) ?∈A 7. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ?C )= ( A )。 (A) {<1,c >,<2,c >} (B) { 离散数学 1.在自然推理系统P 中构造下面推理的证明： 前提：,,p q r q r s ?∨∨?→ 结论：p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。 如果小张今天看到小王，则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提： ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ，并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ＝{?，1，{1}}，B ＝{0，{0}}，求P (A )、P (B )－{0}、P (B )⊕B 。 10、设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… }，R={<离散数学练习题库
离散数学题库