离散数学期末复习题
离散数学期末复习题
一、选择题
1、永真式的否定是（2）
(2) 永假式
2、设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，则下列真命题为(1)
(1)R Q P ∧→
3、设P ：我听课，Q ：我看小说，则命题R “我不能一边听课，一边看小说”的符号化为⑵ ⑵Q P ?→(3)
提示：()R P Q P Q ??∧?→?
4、下列表达式错误的有⑷
⑷()P P Q P Q ∧?∨?∨
5、下列表达式正确的有⑷
⑷Q Q P ??→?)(
6、下列联接词运算不可交换的是(3)
(3)→
6、设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“有的人喜欢所有的花”的逻辑符号化为⑷
⑷(()(()(,))x M x y F y H x y ?∧?→
7、设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老
师”的逻辑符号化为⑵
⑵))),()(()((y x A y J y x L x ∧?→?
8、谓词公式)())()((x Q y yR x P x →?∨?中的 x 是⑶
⑶既是自由变元又是约束变元
9、下列表达式错误的有⑴
⑴(()())()()x A x B x xA x xB x ?∨??∨?
10、下列推导错在⑶
①)(y x y x >?? P
②)(y z y >?
US ① ③)(z C z >
ES ② ④)(x x x >?
UG ③ ⑶④
11、下列推理步骤错在⑶
①(,)x yF x y ??
P ②),(y z yF ?
US ① ③),(c z F
ES ② ④),(c x xF ?
UG ③ ⑤),(y x xF y ??
EG ④
⑶③→④ 12、设个体域为{a,b}，则(),x yR x y ??去掉量词后，可表示为⑷
⑷()()()()()()b b R a b R b a R a a R ,,,,∨∧∨
提示：原式()()()()()()()()
,,,,,,yR a y yR b y R a a R a b R b a R b b ??∧??∨∧∨
二、填充题
1、一个命题含有n 个原子命题，则对其所有可能赋值有2n 种。
2、n 个命题变元可产生2n 个互不等价的极小项，其中，任意两个不同极小项的合取式为矛盾式（永假式），而全体极小项的析取式为重言式（永真式），n 个命题变元可构造包括F 的不同的主析取范式类别为22n
。
3、n 个命题变元可产生2n 个互不等价的极大项，其中，任意两个不同极大项的析取式为重言式（永真式），而全体极小项的合取式为矛盾式（永假式），n 个命题变元可构造包括T 的不同的主合取范式类别为22n 。
5、公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为()(())P Q P Q S ?∧∨∧?∨?。
6、设P ：它占据空间，Q ：它有质量，R ：它不断运动，S ：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为R Q P S ∧∧? 。
7、P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为Q P →?； “虽然你努力了，但还是失败了”的翻译为Q P ∧。
8、令)(x A ：x 会叫，)(x B ：x 是狗，)(x C ：x 会咬人，则命题“会叫的狗未必会咬人” 的符号化为))()()((x C x B x A x ?∧∧?。
9、设P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比y 重，则命题“大象比老鼠重”的符号化为)),()()((y x R y Q x P y x →∧??。
10、令A （x ）:x 是自然数，B （x,y ）：x 小于y ，则命题“存在最小的自然数” 的符号化为),()(()((x y B y A y x A x ?→???。
三、计算题
1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式
（1）（P →Q ）?（?P ∨Q ）；
（2）?（P →Q ）∧Q ；
（3）（P →Q ）∧?R ；
解 （1）、（2）和（3）的真值表如表1、表2和表3所示：
（3）的主析取范式为：(0,2,6)∑；其主合取范式为(1,3,4,5,7)π。
2、给定解释I ：D={2，3}，L （x,y ）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式),(y x xL y ??的真值。
解：(,)((2,)(3,))((2,2)(3,2))((2,3)(3,3))y xL x y y L y L y L L L L ????∧?∧∨∧ (10)(01)000?∧∨∧=∨=。
3、个体域为{1，2}，求?x ?y （x+y=4）的真值。
解：?x ?y （x+y=4）??x （（x+1=4）∨（x+2=4））
?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））
?（0∨0）∧（0∨1）?0∧1?0。
四、证明题
1、证明下列逻辑恒等式：
（1）Ｐ?Ｑ? (Ｐ→Ｑ)∧(Ｑ→Ｐ)
证明、用真值表法证明
由定义可知，这两个公式是等价的。
（2）P →(Q →P)??P →(P →?Q)
证明、P →(Q →P)??P ∨(?Q ∨P) ?P ∨(?P ∨?Q)
?P ∨(?P ∨?Q) ?P ∨(P →?Q)
??P →(P →?Q)
（3） ))(()()(Q R P Q R Q P →∨?→∧→
证明 ： 左))(())()((Q R P Q R Q P ∨?∧??∨?∧∨??
?→∨?∨∨??)())((Q R P Q R P 右
（4）求证：?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)
（5）求证：?x(P(x)→Q(x))∧?xP(x)??x(P(x)∧Q(x))
证明：左??x((P(x)→Q(x)∧P(x))??x((?P(x)∨Q(x))∧P(x))??x(P(x)∧Q(x)) ?右
（6）求证：?x ?y (P (x )→Q (y ))? ?xP (x )→?yQ (y )
证明：?x ?y (P (x )→Q (y ))??x ?y (?P (x )∨Q (y ))
??x (?P (x )∨?yQ (y ))??x ?P (x )∨?yQ (y )???xP (x )∨?yQ (y )??xP (x )→?yQ (y ) （7）求证：()()()()()(
)
x F x G x xG x xF x ??∧???→?
证明：左()()()()()()()()()x F x G x x F x G x xF x x G x ???∨????∨????∨?? ()()()xF x xG x ???∨??()()()xG x xF x ???→??右 2、用推理规则证明下列各结论是各前提的有效结论：
（1）P →Q ，?Q ∨R ，?R ，?S ∨P=>?S
证明：(1) ?R P
(2) ?Q ∨R P
(3) ?Q T （1），（2）(析取三段论)
(4) P →Q P
(5) ?P T （3），（4）(拒取式)
(6) ?S ∨P P
(7) ?S T （5），（6）(析取三段论)
（2）A →(B →C)，C →(?D ∨E)，?F →(D ∧?E),A=>B →F
证明： (1) A P
(2) A →(B →C) P
(3) B →C T （1），（2）(假言推理)
(4) B P （附加前提）
(5) C T （3），（4）(假言推理)
(6) C →(?D ∨E) 前提
(7) ?D ∨E T （5），（6）(假言推理)
(8) ?F →(D ∧?E) 前提
(9) F T （7），（8）(拒取式)
(10) B →F CP
（3）(P →Q)∧(R →S)，(Q →W)∧(S →X)，?(W ∧X)，P →R => ?P
证明：（1） P P （假设前提）
（2） P →R P
（3） R T （1），（2）(假言推理)
（4） (P →Q)∧(R →S) P
（5） P →Q T （4）(化简律)
（6） R →S T （4）(化简律)
（7） Q T （1），（5）(假言推理)
（8） S T （3），（6）(假言推理)
（9） (Q →W)∧(S →X) P
（10） Q →W T （9）(化简律)
（11） S →X T （9）(化简律)
（12） W T （7），（10）(假言推理)
（13） X T （8），（11）(假言推理)
（14） W ∧X T （12），（13）(合取引入)
（15） ?(W ∧X) P
（16） ?(W ∧X)∧(W ∧X) T （14），（15）(合取引入)
由（16）得出矛盾式，故?P 为原前提的有效结论
（4）?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))
证明(1)?xP(x) P
(2)P(a) T(1)，ES
(3)?x(P(x)→Q(y)∧R(x)) P
(4)P(a)→Q(y)∧R(a) T(3)，US
(5)Q(y)∧R(a) T(2)(4) (假言推理)
(6)Q(y) T(5) (化简律)
(7)R(a) T(5) (化简律)
(8)P(a)∧R(a) T(2)(7) (合取引入)
(9)?x(P(x)∧R(x)) T(8)，EG
(10)Q(y)∧?x(P(x)∧R(x)) T(6)(9) (合取引入)
（5）)()()()())()()((x Q x x P x x Q x P x ?→??→?
证明：①?xP(x) P （ 附加前提）
②P(e) T ①ES
③))()()((x Q x P x →? P
④)()(e Q e P → T ③US
⑤Q(e) T ②④(假言推理)
⑥)()(x Q x ? T ⑤EG
⑦)()()()(x Q x x P x ?→? CP
（6）()(()()()),(),()xP x x P x Q x R x xP x xQ x ?→?∨→???(()())x y P x R y ??∧ 证明：⑴()(()()())xP x x P x Q x R x ?→?∨→ P
⑵()xP x ? P
⑶(()()())x P x Q x R x ?∨→ T ⑴⑵(假言推理)
⑷)(e P T ⑵ES
⑸()xQ x ? P
⑹)(d Q T ⑸ES
⑺()()()P d Q d R d ∨→ T ⑶US
⑻)()(d P d Q ∨ T ⑹（附加律）
⑼)(d R T ⑺⑻(假言推理)
⑽)()(d R e P ∧ T ⑷⑼(合取引入)
⑾))()()((y R e P y ∧? T ⑽EG
⑿))()()()((y R x P y x ∧?? T ⑾EG
（7）()()())()()()(x xQ x P x x Q x P x ?∨??∨?
证明：（1）())()()()(x Q x x p x ?∨?? P （假设前提）
（2）())()(x Q x x P x ??∧?? T （1）
（3）())(x P x ?? T （2）(化简律)
（4）)(e P ? T （3）ES
（5）()()()()x P x Q x ?∨ P
（6）()())()(x Q x P x →?? T （5）
（7）)()(e Q e P →? T （6）US
（8）()e Q T (4). (7) (假言推理)
(9) ()()x Q x ?? T (2) (化简律)
(10)()e Q ? T(9)US
(11)()()e Q e Q ∧? T (8) (10) (合取引入)
由（11）得出矛盾式，故()()()x P x xQ x ?∨?为原前提的有效结论
五、将下列命题形式化，并证明结论的有效性：
1、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A 队得第一，则B 队或C 队获亚军;
(2) 若C 队获亚军，则A 队不能获冠军;
(3) 若D 队获亚军，则B 队不能获亚军;
(4) A 队获第一;
结论: (5) D 队不是亚军。
证明、设A ：A 队得第一;B: B 队获亚军;C: C 队获亚军;D: D 队获亚军;
则前提符号化为A →（B ∨C ），C →?A ，D →?B ，A ；结论符号化为 ?D 。
本题即证明 A →（B ∨C ），C →?A ，D →?B ，A ??D 。
（1） A P
（2） A →（B ∨C ） P
（3） B ∨C T （1），（2）(假言推理)
（4） C →?A P
（5） ?C T （1），（4）(拒取式)
（6） B T （3），（5）(析取三段论)
（7） D →?B P
（8） ?D T （6），（7）(拒取式)
故该结论有效
2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。
解 设P ：今天天气好，Q ：考试准时进行，A (e )：e 提前进入考场，个体域：考生的集合，则命题可符号化为：?P →?x ?A (x )，?xA (x )?Q ?Q →P 。
(1)?P →?x ?A (x ) P
(2)?P →??xA (x ) T (1)
(3)?xA (x )→P T (2)
(4)?xA (x )?Q P
(5)(?xA (x )→Q )∧(Q →?xA (x )) T (4)
(6)Q →?xA (x ) T (5) (化简律)
(7)Q →P T (6)(3) （假言三段论）
3、所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。
解：设Q(x)：x 是有理数，R(x)：x 是实数，Z(x)：x 是整数。
命题形式化：))()(()),()((x Z x Q x x R x Q x ∧?→?? ))()((x Z x R x ∧?。
证明：（1）))()((x Z x Q x ∧? P
(2) )()(a Z a Q ∧ T(1) ES
(3) )(a Q T(2) (化简律)
(4) ))()((x R x Q x →? P
(5) )()(a R a Q → T(4)US
(6) )(a R T(3)(5) (假言推理)
(7) )(a Z T(2) (化简律)
(8) )()(a Z a R ∧ T(6)(7) (合取引入)
(9) ))()((x Z x R x ∧? T (8) EG
集合、关系、函数的重要知识
一、关系的集合运算法则
设123,,,R R R R A A ??，则有
1.11()
R R --=，1-Φ=Φ，1()A A I I -=，1()A A A A -?=?，1111221()R R R R ---=
2.1111212()R R R R ---= ，1111212()R R R R ---= ，1111212()R R R R ----=-
3.123123()()R R R R R R =
4.1231213()()()R R R R R R R ? ，1231213()()()R R R R R R R =
设12,,R R R A A ??，则有
四、函数的性质
设函数:f B C →，:g A B →，
若,f g 是单射，则:f g A C → 也是单射；
若,f g 是满射，则:f g A C → 也是满射；
若,f g 是双射，则:f g A C → 也是双射；
若:f g A C → 是单射，则g 是单射；
若:f g A C → 是满射，则f 是满射；
若:f g A C → 是双射，则f 是满射，g 是单射 集合、关系、函数的重要习题
一、选择题
1、下列为真命题的是（B ）
A 、{{}}a a ∈
B 、{}{{}}a a ∈
C 、{}{{}}a a ?
D 、{}{{}}a a =
2、下列结果错误的是（B ）
A 、{}{}Φ?Φ=Φ
B 、{}{}Φ?Φ=Φ
C 、{}{}Φ-Φ=Φ
D 、{}{}Φ⊕Φ=Φ
3、非空集合X 上的空关系Φ不具备的性质是（A ）
A 、自反性
B 、反自反性
C 、对称性；
D 、传递性
4、设R 为S={1，2，3}上的关系，其关系图如下，则下列为真命题的是（C ）
A 、R 对称，但不反对称
B 、R 反对称，但不对称
C 、R 对称，又反对称
D 、R 不对称，也不反对称
5、设R 为S={1，2，3，4}上的关系，其关系图如下，则下列为假命题的是（C ）
A 、R 不自反，也不反自反
B 、R 不对称，也不反对称
C 、R 传递
D 、R 不传递
6、设R ，S 是集合A 上的关系，则下列断言正确的是（A ）
A 、若S R ,自反，则S R 自反
B 、若S R ,对称，则S R 对称；
C 、若S R ,反自反，则S R 反自反
D 、若S R ,反对称，则S R 反对称
7、设Z 为整数集，下面哪个序偶不够成偏序集（A ）
A 、)(,小于关系：<>< B 、)(,小于等于关系：≤>≤ C 、)(,于关系：等=> = 8、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“?”的哈斯图为（C ） 9、集合A={1，2，3，4}上的偏序关系图为 则它的哈斯图为（A ） 10、下列关系中能构成函数的是（B ） A 、)}10(),(|,{<+∧∈> B 、)}(),(|,{2x y R y x y x =∧∈><； C 、)}(),(|,{2 x y R y x y x =∧∈><； D 、{,|(,)(mod3)}x y x y Z x y <>∈∧≡ 11、下列函数是双射的为（A ） A 、f : Z →E , f (x) = 2x B 、f : N →N ?N, f (n) = C 、f : R →Z , f (x) = 1 D 、f : Z →N, f (x) = | x | （注：Z —整数集，E —偶数集， N —自然数集，R —实数集） 12、下面函数为单射而非满射的是（B ） A 、12)(,:2-+-=→x x x f R R f B 、x x f R Z f ln )(,:=→+； C 、:,()[]f R Z f x x →= D 、12)(,:+=→x x f R R f 13、下列命题正确的有（C ） A 、若f g 是双射，则,f g 都是单射 B 、若f g 是双射，则,f g 都是满射 C 、若f g 是双射，则f 是单射, g 是满射 D 、若f g 是双射，则f 是满射, g 是单射 二、填充题 1、设}2,121{Z x x x x M ∈≤≤=整除，被，}3,121{Z x x x x N ∈≤≤=整除，被， 则 =?N M {6，12} ，=-N M {2，4，8，10} ，M N ⊕={2，3，4，8，9，10} 2、集合}}2{},2,{{Φ=A 的幂集()A ρ=}}}2{},2,{{}},2{{}},2,{{,{ΦΦΦ 3、(())ρρΦ={,{}}ΦΦ， (({}))ρρΦ={,{},{{}},{,{}}}ΦΦΦΦΦ 4、设{}b a A ,=，则()A A ρ?= {}><><><><><><>Φ<>Φ 5、设关系A={<1,2>,<2 , 4 >,<3 , 3 >} 与 B={<1,3>,<2,4>,<4,2>}, 则A B = {< 1 , 4 > , < 2 , 2 > }，1()A B -= { < 4 , 2 > } 6、设集合A={1，2，3，4，5}上偏序关系的Hass 图为 则集合A 上的最大元为1，最小元为无，极大元为1，极小元为4,5，lub 为1，glb 为无； 其子集B={2，3，4}上的最大元为无，最小元为4，；极大元为2,3，极小元为4 ，lub 为1，glb 为4 7、偏序集,A R ≤<>的哈斯图为 则≤R = { 8、 设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A 的一个分划，则由S 导出的等价关系 R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 9、设|X|=m ，|Y|=n ，则从X 到Y 有2mn 种不同的关系，有m n 种不同的函数 10、在一个有n 个元素的集合上，可以有22n 种不同的关系，有n n 种不同的函数，有!n 种 不同的双射 11、设 f ，g 是自然数集N 上的函数x x g x x f N x 2)(,1)(, =+=∈?， 则()f g x = 21x +，()g f x = 2(1)x + 三、问答、计算、证明题 1、设R 是X ＝{1，2，3，4}上的二元关系， 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 是否是自反、反自反、对称、传递的？ 解 (1)R 的关系图如图所示： (2) R 的关系矩阵为： ?????? ? ??=0111011100000111)(R M (3)对于R 的关系矩阵，由于对角线上不全为1，R 不是自反的； 由于对角线上存在非0元，R 不是反自反的； 由于矩阵不对称，R 不是对称的； 从关系图看出，若两顶点通过中间点相联，则两顶点间必有直达边，所以R 是传递的． 2、设X 为集合，A ＝()X ρ－{?}－{X }，且A ≠?，若|X |＝n ，问 (1)偏序集是否有最大元？ (2)偏序集是否有最小元？ (3)偏序集中极大元和极小元的一般形式是什么？并说明理由。 解：考察()X ρ的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X |＝n ，则第n －1层是X 的n －1元子集，第n 层是X ． 偏序集与偏序集<()X ρ，?>相比，恰好缺少第0层和第n 层． A ≠?，则偏序集不存在最大元和最小元 而极大元恰好是比X 少一个元素，即X －{x }，x ∈X ． 3、 {1,1,1,3,2,2,3,3,3,1,3,4,4,3,4,4}R =<><><><><><><><>是集合}4,3,2,1{=A 上的关系，写出关系矩阵R M ，画出关系图，问R 是A 上的等价关系吗？ 解： ?????? ? ??=1100110100100101R M R 的关系图为 R 是自反、对称的，但不传递，故不是等价关系． 4、求S={1，2，3，4，5}上的等价关系R ，使其诱导划分{{1，2}，{3}，{4，5}}， 画出关系图． 解：R 1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R 2={3}×{3}={<3,3>} R 3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R=R 1 R 2 R 3 ={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}． 5、设{234}A =，， ，}12,10742{，，，=B ，从A 到B 的关系 },,,{b a B b A a b a R 整除且∈∈><=， 试给出R 的关系图和关系矩阵，并说明此关系R 及其逆关系1R -是否为函数？为什么？ 解：}12,4,4,4,12,3,12,2,10,2,4,2,2,2{><><><><><><><=R 则R 的关系图为： R 的关系矩阵为 110110*********R M ????=?????? 关系R 不是A 到B 的函数， 因为元素2，4的象不唯一 逆关系1 R -也不是B 到A 的函数 因为元素7的象不存在． 6、设8||=A ，R 是A 的等价关系且由R 诱导的A 的划分块数为4，则不同的R 有多少种？ 解：我们知道一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将8个元素的集合分成4份的划分种数即可。 如果4份中元素个数分别为5，1，1，1，则共有58C 种， 如果4份中元素个数分别为4，2，1，1，则共有2448C C 种， 如果4份中元素个数分别为3，3，1，1，则共有3538C C 种， 如果4份中元素个数分别为3，2，2，1，则共有2538C C 种， 如果4份中元素个数分别为2，2，2，2，则共有2628C C 种， 因此，A 上秩为4的等价关系共有58C +2448C C +3538C C +2538C C +26 28C C ． 7、设{1,2,3,4}A =，在A A ?上定义关系:,,,R a b c d R a d b c <<><>>∈?+=+，证明：R 是A A ?上的等价关系，并求出[2,3],/R A A R <>?． 证明：,,,a b c d R <<><>>∈ a d b c a b c d ?+=+?-=- 1）,,,,,,,a b A A a b a b a b a b R ?<>∈?-=-∴<<><>>∈ 即R 自反． 2）,,,,,a b c d R a b c d ?<<><>>∈-=-则从而,,,c d a b R <<><>>∈，即R 对称． 3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈则a b c d c f -=-=- ， 从而,,,,a b e f R <<><>>∈即 R 传递． 综上得出，R 是等价关系． [2,3]{,,,231}{1,2,2,3,3,4}R a b a b A A a b <>=<><>∈?-=-=-=<><><>， /{[1,1],[1,2],[1,3],[1,4],[2,1],[3,1],[4,1]}R R R R R R R A A R ?=<><><><><><><>． 8、设A={1，2，3，4}，在()A ρ上规定二元关系∈><=t s t s R ,|,{()A ρ(||||)}s t ∧=， 证明：R 是()A ρ上的等价关系，并写出[{2,3}]R ， 商集()/A R ρ． 证明：⑴∈?s ()A ρ，由于||||s s =，所以R s s >∈<,，即R 自反的． ⑵∈?t s ,()A ρ，若R t s >∈<,，则||||||||s t t s =?=，R s t >∈∴<,，R 是对称的． ⑶∈?u t s ,,()A ρ，若：R u t R t s >∈<>∈<,,且，即：||||||u t s == R u s u s >∈<=∴,|,||| 所以R 是传递的． 由⑴⑵⑶知，R 是等价关系． [{2,3}]{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}R =， ()/{[],[{1}],[{1,2}][{1,2,3}],[]}R R R R R A R A ρ=Φ． 9、若R 和S 都是非空集A 上的等价关系，则R ?S 是A 上的等价关系． 证明：?a ∈A ，因为R 和S 都是A 上的等价关系，所以xRx 且xSx 。故xR ?Sx 。从而R ?S 是自反的． ?a,b ∈A ，aR ?Sb ，即aRb 且aSb 。因为R 和S 都是A 上的等价关系，所以bRa 且bSa 。故bR ?Sa 。从而R ?S 是对称的． ?a,b,c ∈A ，aR ?Sb 且bR ?Sc ，即aRb ，aSb,bRc 且bSc 。因为R 和S 都是A 上 的等价关系，所以aRc 且aSc 。故aR ?Sc 。从而R ?S 是传递的． 故R ?S 是A 上的等价关系． 10、设R 是A 上一个二元关系，{,|,(,,)}S a b a b A c A a c R c b R =<>∈∧?∈<>∈∧<>∈， 试证明：若R 是A 上一个等价关系，则S 也是A 上的一个等价关系． 证明：（1）A a ∈?，由R 自反，则,,a a R a a R <>∈∧<>∈，S a a >∈∴<,，即S 自反． （2）,,a b S ?<>∈则,,a b c A ∈，且,,a c R c b R <>∈∧<>∈ 由R 对称，知,,b c R c a R <>∈∧<>∈，于是,b a S <>∈，即S 对称． （3）,,,a b S b c S <>∈<>∈，则,,,,a b c d e A ∈，且 ,,,,,,,a d R d b R b e R e c R <>∈<>∈<>∈<>∈ 由R 传递，知,,a b R b c R <>∈∧<>∈，于是,a c S <>∈，即S 传递的． 由（1）、（2）、（3）得，S 是等价关系． 11、设A={1，2}，A 上所有函数的集合记为A A , 是函数的复合运算，试给出A A 上运算 的 运算表，并指出A A 中是否有幺元，哪些元素有逆元？ 解：因为|A|=2，所以A 上共有22 =4个不同函数。令},,,{4321f f f f A A =，其中： 14(1)1,(2)2; (1)1,(2)1;(1)2,(2)2;(1)2,(2)1f f f f f f f f ======== 1f 为A 中的幺元，1和4有逆元． 设函数f ：R ×R →R ×R ，f 定义为：f ( (1)证明f 是双射；(2) 求逆函数f －1；(3)求f f ． 证明： (1)?x ，y ，x 1，y 1∈R ，若f ( ?∈R ×R ，令x ＝ 2w u +，y ＝2 w u -，则 w u ->＝，所以f 是满射，故为双射 (2)f －1()＝<2w u +，2w u ->。 (3)f f ( 12、设f 是A 到A 的满射，且f f f = ，证明A f I =． 证明：因为f 是满射，所以A a ∈?，存在A a ∈1使得a a f =)(1， 又因为f 是函数，所以)())((1a f a f f = 即)()(1a f a f f = 由 f f f = ，知11()()f f a f a = ，则1()()f a f a a ==，由a 的任意性知A f I =． 代数系统 一、选择题： 1、下列正整数集的子集在普通加法运算下封闭的是（ D ） A 、{30x x ≤} B 、{x x 与30互质} C 、{x x 是30的因子} D 、{x x 是30的倍数} 2、设S={1，2，…，10 }，则下面定义的运算*关于S 非封闭的有（ D ） A 、x*y=max(x ,y) B 、x*y=min(x ,y) C 、x*y=取其最大公约数 D 、x*y= 取其最小公倍 3、设集合A 的幂集为()A ρ，-? 、 、、为集合的交、并、差、笛卡尔乘积运算，则下列系统中是代数系统的为（ D ） A 、()A ρ , B 、()A ρ , C 、(),A ρ- D 、(),A ρ? 4、在自然数集上定义的下列四种运算，其中满足结合律的是（C ） A 、a b a b *=- B 、||a b a b *=- C 、max{,}a b a b *= D 、2a b a b *=+ 5、设Z +为正整数集，*表示求两数的最小公倍数，对代数系统*A Z +=,，有（ A ） A 、1是么元，无零元 B 、1是零元，无么元 C 、无零元，无么元 D 、无等幂元 6、设非空有限集S 的幂集为()S ρ，对代数系统()A S ρ= ,，有（ B ） A 、Φ是么元，S 是零元 B 、Φ是零元，S 是么元 C 、唯一等幂元 D 、无等幂元 7、在有理数集Q 上定义的二元运算*： xy y x y x -+=*，则Q 中元素满足（ C ） A 、都有逆元 B 、只有唯一逆元 C 、1x ≠时，有逆元 D 、都无逆元 8、设R 是实数集合，“?”为普通乘法，则代数系统 A 、半群 B 、独异点 C 、可交换的独异点 D 、循环独异点 9、设S={0，1}，*为普通乘法，则< S , * >（ B ） A 、是半群，但非独异点 B 、是独异点，但非群 C 、是群，但非阿贝尔群 D 、是阿贝尔群 10、任意具有多个等幂元的半群，它（A ） A 、不能构成群 B 、不一定能构成群 C 、能构成群 D 、能构成阿贝尔群 二、填充题： 1、下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足 2、设(6)。 3、设A={3,6,9}，A 上*为：a*b=min{a,b}，则在独异点 4、代数系统 5、设< {a,b,c}, * >为代数系统，* 运算如下： 则它的么元为a ；零元为c ； a 、b 、c 的逆元分别为a 、b 、无。 6、设〈G,*〉是一个群，则 (1) 若a,b,x ∈G ，a *x=b ，则x=( a *-1b)；(2) 若a,b,x ∈G ，a *x=a *b ，则x=( b )。 7、群 8、设a 是12阶群的生成元， 则2a 是(6 )阶元素，3a 是(4)阶元素。 9、设a 是10阶群的生成元， 则4a 是(5 )阶元素，3a 是(10)阶元素。 10、在一个群〈G,*〉中，若G 中的元素a 的阶是k ，则1a -的阶是(k)。 三、简答题： 1、设A={1，2}，A 上所有函数的集合记为A A , 是函数的复合运算，试给出A A 上运算 的 运算表，并指出A A 中是否有么元，哪些元素有逆元？ 答：因为|A|=2，所以A 上共有22=4个不同函数。令},,,{4321f f f f A A =，其中： 1)2(,2)1(;2)2(,2)1(;1)2(, 1)1(; 2)2(,1)1(44332211========f f f f f f f f 1f 为A 中的么元，1和4有逆元。 2、已知定义在集合},,,{d c b a 上的运算*如下表： 试问：1）>*<},,,,{d c b a 是否为代数系统？ 2）>*<},,,,{d c b a 是否为子群？ 3）>*<},,,,{d c b a 是否为群？ 4）>*<},,,,{d c b a 是否有单位元？ 5）>*<},,,,{d c b a 是否满足交换律？ 3333[][][()mod3]i j i j +=+，试给出+3的运算表，并指出 答： 四、计算题： 1、设S=Q ?Q ，Q 为有理数集合，*为S 上的二元运算：对任意(a,b)，(c,d)∈S,有 (a,b)*(c,d)=(ac,ad+b),求出S 关于二元运算*的么元，以及当a ≠0时，(a,b)关于*的逆元。 解：设S 关于*的么元为(a,b)。根据*和么元的定义，对?(x,y)∈S,有 (a,b)*(x,y)=(ax,ay+b)=(x,y), (x,y)*(a,b)=(ax,xb+y)=(x,y)。 即ax=x,ay+b=y,xb+y=y 对?x,y ∈Q 都成立。解得a=1,b=0，则S 关于*的么元为(1,0)。 当a ≠0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有 (a,b)*(c,d)= (ac,ad+b)=(1,0)，(c,d)*(a,b)= (ac,cb+d)=(1,0) 即ac=1,ad+b=0,cb+d=0。解得c=1/a,d=-b/a 。 所以(a,b)关于*的逆元为(1/a, -b/a)。 2、试求 解：0是 五、证明题： 1、 设 证明：（1） ,0*00,*000a R a a a a a a a ?∈=++?==++? 即 0**0a a a ==，0是么元 （2）由于+，·在R 封闭，则*在R 上封闭。 （3） ,,a b c R ?∈ )*(**)*()*(*)(*)(*)*(c b a c b a c b a c b c a b a c b a c b a c b a c b c a b a c b a c b a b a c b a b a c b a b a c b a =??+?+?+?+++=??+?+?+?+++=??++++?++=?++=所以 因此 ， 〈R ，*〉是独异点。 2、I 上的二元运算*定义为：?a,b ∈I ，a*b=a+b-2。试证： 证明：（1）?a,b,c ∈I ，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c) =a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。 （2）记e=2。对?a ∈I ，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I 关于运算*的单位元。 （3）对?a ∈I ，因为a*（4-a ）=a+4-a-2=2=e=4-a+a-2=(4-a)*a 。故4-a 是a 关于运算*的逆元。综上所述， 3、设*是集合A 上可结合的二元运算，且?a,b ∈A,若a*b=b*a ，则a=b 。试证明： （1）?a ∈A,a*a=a ，即a 是等幂元；（2） ?a,b ∈A,a*b*a=a 。 证明：（1）?a ∈A,记b=a*a 。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b 。由已知条件可得a=a*a 。 （2）?a,b ∈A,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a), (a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a ，从而a*b*a=a 。 4、设半群 证明： ??a,b ∈S ，（a ·b ）2=(a ·b)·(a ·b)=((a ·b)·a)·b=(a ·(b ·a))·b =(a ·(a ·b))·b=((a ·a)·b)·b=(a ·a)·(b ·b)=a 2·b 2; ? ?a,b ∈S ，因为（a ·b ）2=a 2·b 2，所以(a ·b)·(a ·b)=(a ·a)·(b ·b)。 故a ·((b ·a)·b)=a ·(a ·(b ·b))。由于·满足消去律，所以(b ·a)·b=a ·(b ·b)，即(b ·a)·b=(a ·b)·b 。从而a ·b=b ·a 。故·满足交换律。 5、若 ? a,b ∈T, =(a ?(b ?a))?b=（a ?(a ?b)）?b=((a ?a)?b)?b=(a ?a)?(b ?b)=a ?b, 即a ?b ∈T 。 故 >的子独异点。 有么元且满足消去律的有限半群一定是群。 证明 设 于是，当m ＝1时，a ＝e ，而e 是可逆的； 当m ＞1时，a *a m -1＝a m -1*a ＝e 。从而a 是可逆的，其逆元是a m -1。 总之，a 是可逆的。 6、对独异点 证明：设e 为 则*(*)*(*)*(*)*(*)**b a b a e b a b c b a b c b c e =====，则b 是a 的左逆元。 故a A ?∈，a 有唯一逆元b ，于是， 7、设群 证明：对任一a ∈G ，由已知可得a*a=e ，即a -1=a 。 对任一a,b ∈G ，因a*b=(a*b)-1=b -1*a -1=b*a ，所以*满足交换律。 从而＜G,*＞是交换群。 8、证明：（1）有限群中阶大于2的元素的个数一定是偶数。 （2）偶数阶群中阶为2 的元素的个数一定是奇数。 证明：（1）设 阶数大于2 的元素成对出现，从而其个数必为偶数。 证明：（2）设 9、设 证明：因为g 是群 。又a ＝i g --)(1， 所以g －1也是群 再证G 只有g 和g －1这两个生成元。假设h 也是G 的生成元，对G 的元素g ，存在整数 s ，使得g ＝h s 。对于h 来说，由g 是G 的生成元，存在整数t ，使得h ＝g t 。于是，g ＝h s ＝g st 。由G 中的消去律得1st g -＝e 。因为G 是无限群，必有st －1＝0。 从而有s ＝t ＝1或s ＝t ＝－1，即h ＝g 或h ＝g －1。 10、 求证： 证明：1）?a ，b ∈G ，a ?b=a*u -1*b ∈G ，运算是封闭的。 2）?a ，b ，c ∈G ，（a ?b ）?c=（a*u -1*b ）*u -1*c=a*u -1*（b*u -1*c ）=a ?（b ?c ），运算 是可结合的。 3）?a ∈G ，设E 为?的单位元，则a ?E=a*u -1*E=a ，得E=u ，存在单位元u 。 4）?a ∈G ，a ?x=a*u -1*x=E ，x=u*a -1*u ，则x ?a=u*a -1*u*u -1*a=u=E ，各元素都有逆元。 所以 11、设 证明： ? 设f 是G 的自同构。 对?a ，b ∈G ，a ·b=(b -1·a -1)-1=(f(b) ·f(a))-1=(f(b ·a))-1=((b ·a)-1)-1=b ·a 。 故运算·满足交换律 ，即G 是可交换群。 ?因为当a ≠b 时，a -1≠b -1，即f(a)≠f(b)，故f 是G 到G 中的一个单射。 又对?a ∈G ，有f(a -1)=(a -1)-1=a 。故f 是G 到G 上的满射。从而f 是G 到G 上的双射。 对?a ，b ∈G ，因为G 是可交换群，则 f(a ·b)=(a ·b)-1=(b ·a)-1=a -1·b -1=f(a)·f(b)。 故f 是G 的自同构。 图论部分 一、选择题： 1．欧拉回路是（B ） A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 2．哈密尔顿回路是（C ） A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 3．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边 4．下列哪一种图不一定是树（C ）。 A.无简单回路的连通图 B. 有n 个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图 5.下列哪个不是两个图同构的必要条件 A. 结点数目相等 B. 边数相等 C. 度数相同的结点数目相同 D. 两个图都是平面图 6．在有n 个结点的连通图中，其边数（B ） A. 最多有n-1条 B. 至少有n-1条 C. 最多有n 条 D. 至少有n 条 7．下列图为树的是（C ）。 A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G C 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a G D 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 二、填充题： 1、n 阶无向完全图K n 的边数是(2 )1(-n n )，每个结点的度数是(n-1)。 2、n 个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。 3、设有向图G = < V ，E >，},,,{4321v v v v V =的邻接矩阵?????? ? ??=0001001111011010A ， 则1v 的入度)(deg 1v -= 3 ，4v 的出度)(deg 4v +=1 ，从2v 到4v 的长度为2的路有 1 条。 4、一棵无向树的顶点数为n ，则其边数为n-1 ，其结点度数之和是2n-2。 5、一个无向图有生成树的充分必要条件是(它是连通图)。 6、设T=〈V,E 〉是一棵树，若|V|>1，则T 中至少存在(2)片树叶。 7、任何连通无向图G 至少有(1)棵生成树，当且仅当G 是(树)，G 的生成树只有一棵。 8、设T 是一棵树，则T 是一个连通且(无简单回路)的图。 9、设无向图G 有18条边且每个顶点的度数都是3，则图G 有(12)个顶点。 10、任一有向图中，度数为奇数的结点有(偶数)个。 11、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（9）。 三、问答题 1、设无向图G= 解：设G 中度数小于3的顶点有k 个，由欧拉定理24=∑∈V v v )deg(知，度数小于3 的顶点度 数之和为6。故当其余的顶点度数都为2时，G 的顶点最少。即G 中至少有9个顶点。 2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。 解：一个无向图D 是欧拉图? D 是连通的，且所有顶点的度等于偶数。 所以是欧拉图，但无哈密尔顿回路。 ? ? ? ? ? 四、计算题 1、有向图,D V E =<>，其中结点集1234{,,,}V v v v v =， 有向边集121314214243{,,,,,,,,,,,}E v v v v v v v v v v v v =<><><><><><> （1）求D 的邻接矩阵A ；（2）求D 的可达性矩阵P ； （3）说明1v 到3v 长度为4的路径有几条？ （4）说明1v 到其它各顶点长度为3的路径有几条？ 解：（1）0111100000000110A ??????=?????? （2）23443553333200002331R A A A A ??????=+++=??????，1111111100001111P ???? ??=?????? （3）1v 到3v 长度为4的路径有2条，（4）1v 到其它各顶点长度为3的路径有3条. 2、设有如下有向图G= （1）求G 的邻接矩阵；（2）G 中v 1到v 4的长度为4 的通路有多少条？（3）G 中经过v 1的长度为3 的回路有多少条？（4）G 中长度不超过4 的通路有多少条？其中有多少条通路？ v 3 解：（1）A=????????????0100100001010111，A 2=????????????1000010011111212，A 3=????????????0100100013122423，A 4=????? ???????1000010034234735 （2）G 中v 1到v 4的长度为4 的通路有4条； （3）G 中经过v 1的长度为3 的回路有3条； （4）G 中长度不超过4 的通路有72条，其中有19条回路。 五、证明题 1、设图G= 证明：由已知可知，G 中k+1度顶点为n-n k 个。再由欧拉定理可知 2m=∑∈V v v )deg(=kn k +(k+1)(n-n k )=(k+1)n-n k ，故n k =(k+1)n -2m 。 2、设G= 证明：用反证法证明。 若G 不连通，则它可分成两个独立的子图G 1和G 2，其中 |V(G 1)|+|V(G 2)|=n ，且G 1中的任一个顶点至多只和G 1中的顶点邻接，而 G 2中的任一顶点至多只和G 2中的顶点邻接。任取u ∈V(G 1),v ∈V(G 2),则 d(u)≤|V(G 1)|-1, d(v)≤|V(G 2)|-1。 故d(u)+d(v) ≤(|V(G 1)|-1)+(|V(G 2)|-1)≤|V(G 1)|+|V(G 2)|-2 =n-2，这与已知矛盾。故G 是连通图。 离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（） 离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8. C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D= D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)36的正因子集合 (３)自然数中3的倍数 (４)大于１的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } ２.确定下列结论正确与否 (１)φ∈φ× (２)φ∈｛φ｝√ (３)φ?φ√ (４)φ?｛φ｝√ (５)φ∈｛ａ｝× (６)φ?｛ａ｝√ (７)｛ａ,ｂ｝∈｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝× (８)｛ａ,ｂ｝?｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝√(９)｛ａ,ｂ｝∈｛ａ,ｂ,｛｛ａ,ｂ｝｝｝× (１０)｛ａ,ｂ｝?｛ａ,ｂ,｛｛ａ,ｂ｝｝｝√ ３.写出下列集合的幂集 (１)｛｛ａ｝｝ {φ, {{ a }}} ( 2 ) φ {φ} (３)｛φ,｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} } (４)｛φ,ａ,｛ａ,ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (５)Ｐ(Ｐ(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } ４.对任意集合Ａ,Ｂ,Ｃ,确定下列结论的正确与否(１)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ∈Ｃ√ (２)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ?Ｃ× (３)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ∈Ｃ× (４)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ?Ｃ × ５.对任意集合Ａ,Ｂ,Ｃ,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 1. 计算：2400 mod 319、2340 mod 11。 2. 设整数a 和b 不全为0，且a 和b 互素。请证明：ab 和a+b 互素。 3. 设n!的标准素因数分解式是 k k p p p εεεΛ2121 请证明： ∑∞=???? ? ?????=1s s i p n i ε，i=1,2,…,k 4. 300！末尾0的个数是？。 5. 解同余方程组：x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。 6. 求p →(p ∧(q →p))的主析取范式和主合取范式。（真值表法和等值演算法） 7. 求谓词公式?x ?y(P(x,y)?Q(x,y))→?x ?yR(x,y)的前束范式。 8. 证明下面的推理： “每个科研工作者都是努力工作的。每个努力工作而又聪明的人都取得事业的成功。某个人是科研工作者并且聪明。所以，某人事业取得成功。” 9. 设R={(1,2),(1,4),(3,3),(4,1)}是集合A={1,2,3,4}上的关系。 （1） R 是自反的吗？是对称的吗？是传递的吗？ （2） R 的自反对称闭包存在吗？ （3） R 的自反传递闭包存在吗？ （4） R 的对称传递闭包存在吗？ （5） R 的自反对称传递闭包存在吗？ （6） R 的反自反闭包存在吗？ （7） R 的反对称闭包存在吗？ 10. 设A={x|x ∈N ，且x|54}，R={(x,y)|x,y ∈A ，且x|y }。 （1） 列出集合A 和R 中的元素； （2） 给出R 的矩阵表示； （3） 证明(A,R)是偏序集，画出哈斯图； （4） 指出(A,R)中的最大元、最小元、极大元、极小元。 11. 设X={(x,y) | x 和y 是不为零的实数}，E 是X 上的关系： 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， v1.0 可编辑可修改 离散数学知识要点总结 第1章命题逻辑 1、会判断一个语句是否为命题（如P31-习题题） 练习：判断下列语句是否为命题。 (1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物； (4).你打算考硕士研究生吗 (5).9+5≤12 ； (6). 天上有三个月亮。 (7).x+5 > 6； (8).一定要努力学习！(9).2是素数； (10).x+5 > 6； (11).我正在说谎； (12).x=13. (13).这朵花多好看呀！ (14).7能被2整除. (15).我用的计算机CPU主频是 1G吗 (16).蓝色和黄色可以调成绿 色； (17). 雪是黑色的. (18). 明天会下雨吗； (19).我能进来吗 (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿 色； (22).x≤3； (23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！ (25).5能被2整除. (26).嫦娥一号太棒了！ (27).台湾是中国的一部分； (29) 你下午有会吗若无会，请 到我这儿来！ (30).请不要讲话！ (31) 5是奇数； (32). 3 2> + x 2、注意五个命题联结词的使用，会将命题进行符号化（如，，题的题型）或在判断体现逻辑联结词的逻辑有关系等。练习：将以下命题符号化 (1)如果你不去逛街，那么我也不去逛街。 (2)小李边吃饭边看电视。 (3)林芳学过英语或日语。 (4)张辉与王丽都是三好生. (5)小王住在101室或102室。 (6).2+2≠4当且仅当王红没努力学习离散数学。 (7)4或6是素数. (8).王晓聪明，但是他不用功. (9)如果今天是1号，则明天是5号。(10).小潘不能既跳舞又唱歌。 (11)如果你来了，他就唱歌而且陪你跳舞。 (12).或者雪是黑色的，或者太阳从东方升起。 (13).王晓既用功又聪明。 (14)2 + 2 ≠ 4 当且仅当美国位于非洲。 (15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。(17）.如果天气寒冷，小梅就不去游泳。 （18）小红喜欢看书和画画。 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={是可交换独异点,∴(a ?b)?(a ?b)=((a ?b)?a)?b(完整word版)离散数学期末练习题带答案
离散数学期末复习
离散数学期末试题
离散数学期末试题及答案
离散数学期末试题及答案完整版
离散数学期末复习试题及答案
离散数学期末试卷A卷及答案
离散数学期末测验试题(有几套带答案1)
离散数学本科期末复习题
离散数学期末试卷及答案
最新离散数学期末考试试题配答案
离散数学--期末复习
离散数学期末考试试题及答案
《离散数学》期末考试试题
大学离散数学期末重点知识点总结(考试专用)