下载文档原格式
习 题 一1. 用列举法表示下列集合：（1）1到100之间的自然数的集合； （2）小于5的正整数集合；（3）偶自然数的集合； （4）奇整数的集合.分析 本题主要考察集合的定义及怎样用列举法表示集合。
解：(1) A ={,,,,},123100 (2) B ={,,,}1234，(3) },8,6,4,2,0{ =C , (4) D =---{,,,,,,,} 531135.2. 用描述法表示下列集合：（1）偶整数的集合；（2）素数的集合；（3）自然数a 的整数幂的集合.分析 本题主要考察集合的定义及怎样用描述法表示集合。
解：(1) }2{整除的整数被是能x x E =(2) }11{数和自身整除的整且只能被是大于x x P =(3) }{是整数是自然数，n a a A n =3. 设},1,4,3},{{},4},3{,,2{a R a S ==请判断下面的写法正确与否：（1）S a ∈}{（2）R a ∈}{ （3）S a ⊆}}3{,4,{（4）R a ⊂}4,3,1},{{ （5）S R =（6）S a ⊆}{ （7）R a ⊆}{（8）R ⊆∅ （9）E R a ⊆⊆⊆∅}}{{（10）S ⊆∅}{ （11）R ∈∅ （12）}4},3{{⊆∅分析 本题主要考察集合的基本运算。
解：(1) 错; (2) 对; (3) 对; (4) 错; (5) 错; (6) 对; (7) 错; (8) 对; (9) 对; (10) 错;(11)错; (12) 对.4. 设A 、B 和C 为任意三个集合. 以下说法是否正确? 若正确则证明之, 否则举反例说明.（1）若B A ∈且C B ⊆，则C A ∈；（2）若B A ∈且C B ⊆，则C A ⊆；（3）若B A ⊆且C B ∈，则C A ∈；（4）若B A ⊆且C B ∈，则C A ⊆分析 本题主要考察集合的基本运算。
解：(1) 正确。
因B C ⊆，所以，对任何x B ∈均有x C ∈，今A B ∈，故A C ∈。
习题二十1. 由5个字母a 和8个字母b 能组成多少个非空字母集合?分析：本题主要是对每一种出现的情况分别讨论，然后根据多重集定理就可以求得。
解：此问题可化为多重集}8,5{b a S ••=，则S 的（1）1-组合有：}1,0{,}0,1{b a b a ••••，此种情况排列种数为：2!0!1!1!0!1!1=•+•，（2）2-组合有： }1,1{},0,2{,}2,0{b a b a b a ••••••，此种情况排列种数为：4211!1!1!2!0!2!2!0!2!2=++=•+•+•，（3）3-组合有：}3,0{},0,3{},1,2{,}2,1{b a b a b a b a ••••••••，此种情况排列种数为：81133!0!3!3!0!3!3!1!2!3!1!2!3=+++=•+•+•+•，（4）4-组合有：}2,2{},1,3{},3,1{},0,4{,}4,0{b a b a b a b a b a ••••••••••，此种情况排列种数为：1664411!2!2!4!1!3!4!1!3!4!0!4!4!0!4!4=++++=•+•+•+•+•，（5）5-组合有：}2,3{},3,2{},1,4{},4,1{},0,5{,}5,0{b a b a b a b a b a b a ••••••••••••，此种情况排列种数为：3210105511!2!3!5!2!3!5!1!4!5!1!4!5!0!5!5!0!5!5=+++++=•+•+•+•+•+•，（6）6-组合有：}2,4{},2,4{},4,2{},1,5{},5,1{,}6,0{b a b a b a b a b a b a ••••••••••••，此种情况排列种数为：63201515661!3!3!6!2!4!6!4!2!6!1!5!6!1!5!6!0!6!6=+++++=•+•+•+•+•+•，（7）7-组合有：}3,4{},4,3{},2,5{},5,2{},6,1{,}7,0{b a b a b a b a b a b a ••••••••••••，此种情况排列种数为：1203535212171!3!4!7!4!3!7!2!5!7!5!2!7!6!1!7!0!7!7=+++++=•+•+•+•+•+•，（8）8-组合有：aba•babab•••••，此种••••••a4{},5,4,},}3,5{3{},8,0{ba1{,}7,6,b2{},情况排列种数为：2195670562881!3!5!8!4!4!8!5!3!8!6!2!8!7!1!8!8!0!8=+++++=•+•+•+•+•+•，（9）9-组合有：}4,5{},5,4{},6,3{},7,2{},8,1{b a b a b a b a b a ••••••••••，此种情况排列种数为： 38112612684369!4!5!9!5!4!9!6!3!9!7!2!9!8!1!9=++++=•+•+•+•+•，（10）10-组合有：}5,5{},6,4{},7,3{},8,2{b a b a b a b a ••••••••，此种情况排列种数为：42725221012045!5!5!10!6!4!10!7!3!10!8!2!10=+++=•+•+•+•，（11）11-组合有：}6,5{},7,4{},8,3{b a b a b a ••••••，此种情况排列种数为：957462330165!6!5!11!7!4!11!8!3!11=++=•+•+•，（12）12-组合有：}7,5{},8,4{b a b a ••••，此种情况排列种数为：1287792495!7!5!12!8!4!12=+=•+•，（13）13-组合有：}8,5{b a ••，此种情况排列种数为：1287!8!5!13=•所以总的非空序列为所有的r-组合（13,,2,1 =r ）数目之和，即：2+4+8+16+32+63+120+219+381+427+957+1287+1287=4803.2.用字母f e d c b a ,,,,,来形成3个字母的一个序列,满足以下条件的方式各有多少种?(1)允许字母重复;(2)不允许任何字母重复;(3)含字母e 的序列不允许重复;(4)含字终e 的序列允许重复.分析：本题主要是排列组合的简单应用。
精品文档离散数学习题答案习题一及答案：（ P14-15 ）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是p（ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q （ 9）只有天下大雨，他才乘班车上班解：设 p：天下大雨； q：他乘班车上班；则命题符号化的结果是q p（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( p q)r15、设 p： 2+3=5.q：大熊猫产在中国 .r：太阳从西方升起 .求下列复合命题的真值：（ 4）(p q r )(( p q)r )解： p=1， q=1，r=0 ，(p q r )(110)1，((p q)r )((11)0)(00)1(p q r )(( p q)r ) 1 1119、用真值表判断下列公式的类型：（ 2）( p p)q解：列出公式的真值表，如下所示：p q p qp) ( p p)q( p001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：精品文档（ 4）( p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q)1p0q0q0所以公式的成真赋值有： 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 )m3m7，此即公式的主析取范式，所以成真赋值为011， 111。
6、求下列公式的主合取范式，并求成假赋值：（ 2）( p q) ( p r )解：原式( pp r ) ( p q r )( p q r )M 4，此即公式的主合取范式，所以成假赋值为 100。
第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
习题十六（整 数）1. 请推导出本节定理16.1.3中计算k S 和k T 的递推公式.分析：本题主要是考察矩阵的推导过程。
解：由（P154）T V S U q q q k k kk k ⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪121101101101 () 有T V S U T V S U q q T V T q S U S k k k k k k k k k k k k k k k k k ⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪=++⎛⎝ ⎫⎭⎪----------11111111111102 ()比较(2)式两端，可知U S V T T q T V S q S U k k k k k k k k kk k k ==⎧⎨⎩=+=+⎧⎨⎩------11111134 ()() 由(3)有U S V T k k k k ----==⎧⎨⎩1212 (5) 由(4)和(5)得S q S S T q T T k k k k k k k k =+=+⎧⎨⎩----12126 () 由(3)可令S U T V 01017==⎧⎨⎩ () 又由(1)有T V S U q 11111110⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪ 于是 S U T V S T q 0101111011====⎧⎨⎩==⎧⎨⎩ 这样，对任意k ≥2， 由(6)可求出S k 和 T k 。
2. 求1331和5709的最大公因数，并表为它们的倍数之和.分析：本题主要是考察用辗转相除法来求两个数的最大公因数。
解：用辗转相除法求最大公因数，逐次得出商及余数并计算S k 和T k 。
今列表如下： k 0 1 2 3 4 5 r k 385 176 33 11 0 q k 4 3 2 5 3S k 0 1 3 7 38 空T k 1 4 13 30 163 空 由上表知，最大公因数为 r 411=, 且有r S T 44144415709113313857091631331=-⋅+-⋅=-⨯+⨯-()() 3. 求证：任意奇数的平方减1必是8的倍数.分析：本题首先根据奇数的概念，然后进行变形即得。
习题十1．证明：若G 是简单图，则()()q p p G 2/22-≥χ.分析：()G χ指G 的点色数，显然如果()G χ=k ，则G 的顶点集可以划分为k 个独立集。
设每个独立集的顶点数为p i ，则∑=ki i p 1=p ，由柯西－施瓦丝不等式有： 且由于每个独立集中的任意两个点不邻接，所以第i 个独立集中任何一点的度不会大于p-p i ，本题的关键是利用这两个结论。
2．()k G =χ的临界图G 称为k 临界图. 证明：唯一的1临界图是1K ，唯一的2临界图是2K ，仅有的3临界图是长度为奇数3≥k 的回路.分析：若G 的每个点都是临界点，则G 称为临界图。
由于1-色图是零图，因此1-临界图仅能是1K ，2-色图是2部图，因此2-临界图仅能是2K ，3-色图恒含奇圈，且奇圈至少是3-色才能正常着色，因此3-临界图仅能是长度为奇数3≥k 的回路.证明：（1）()11=K χ，且()01=-v K χ<1，故K1是1临界图；反之，G 是1-临界图，若|V(G)|>1，则G 是零图，()1=-v G χ，所以|V(G)|=1，从而G 是平凡图K1。
（2）()22=K χ，且()1),(22=-∈∀v K K V v χ，故K2是2临界图；反之，G 是2-临界图，即()2=G χ，于是G 的顶点可划分为两个极大独立集V1和V2，若|V1|>1，则())(2),(1G v G G V V v χχ==-⊆∈∀，与G 是临界图矛盾，因此|V1|=1，同理|V2|=1。
因此G=K2。
（3）因为不含奇回路的图是二分图)2)((=G χ。
故3-色图必含奇回路。
显然，奇回路必是3-临界图。
设G 是含奇回路的3-临界图。
若G 不是奇回路，则可分两种情况讨论：)2/()( 2 2 )()(2 ,,1,| | ,, ,)( 2222221222211112221121q p p G x q p p k k p q p k p p p p p p p p p p v d q p p V k p k p p k i p V V V k G k G x ki i p i k i k i k i i i i i i i i k i i k i i i i k -≥-≥≥--≤-=-=-≤=-=⎪⎭⎫ ⎝⎛≥===∑∑∑∑∑∑∑=======故，即从而而个顶点相邻，每个顶点最多与其它且），（柯西－施瓦丝不等式因为。
习题二十一1.某年级有100个学生,其中40个学生学英语,40个学生学俄语,40个学生学日语.若分别有21个学生学习上述三种语言中的任何两种语言,有10个学生所有3种语言.问不学任何语言的学生有多少个?解：用A 1、A 2、A 3分别表示学英语、学俄语、学日语的学生集合，S 表示总学生集合，则问题变成求||321A A A ⋂⋂，利用逐步淘汰公式，分别求120404040||=++=∑iA ，∑=++=⋂+⋂+⋂=⋂63212121||||||||323121A A A A A A AA ji， ∑=⋂⋂=⋂⋂10||||321A A A A AA k ji，所以由逐步淘汰公式331063120100||||||100||321=-+-=⋂⋂-⋂+-=⋂⋂∑∑∑k j i j i i A A A A A A A A A2.有多少个小于70且与70互质的正整数?解：由于70=2×５×７，所以该题也就变成了，求所有小于７０的并且不能被２，５，７整除的正整数的个数。
设1A 、2A 、3A 分别表示1到７０之间能被２、５、7整除的整数之集合.于是,问题变成求||321A A A ⋂⋂.利用逐步淘汰公式,先分别求:59101435]770[]570[]270[||=++=++=∑iA其中][b a 表示对ba取整,下同:∑=++=⋂+⋂+⋂=⋂]]7,2[70[]]7,5[70[]]5,2[70[||||||||323121A A A A A A A Aj i14527=++其中],[b a 表示a 与b 的最小公倍数.∑===⋂⋂=⋂⋂1]7070[]]7,5,2[70[||||321A A A A A A k j i代入公式(21.1)得:=⋂⋂-⋂+-=⋂⋂∑∑∑||||||70||321k j i j i i A A A A A A A A A241145970=-+-3.在由10个数字位组成的三进制序列中,有多少个至少出现一个0,一个1和一个2的序列? 解：设只出现0、1、2中任意i 位数的三进制数的个数为N(i)个，i=1,2。
习 题 三1．下列映射哪些是单射、满射或双射.（1）()⎩⎨⎧=→.0;1,:是偶数是奇数m m m Z Z σσ （2）{}()⎩⎨⎧=→.1;0,1,0:是偶数是奇数m m m N σσ （3）()52,:-=→r r R R σσ解：(1) σ既不是单射也不是满射。
(2) 是满射但不是单射.。
(3) 双射。
2．设A 和B 是有限集，试问有多少A 到B 的不同的单射和双射.解：设 |A|=m , |B|=n .(1) 若 B A →:σ是单射, 则必有 |A|<=|B|, 即 m<=n .a) 当m= n 时, 共有m!个单射;b) 当m<n 时, 共有 !m m n C ⋅ 个单射;(2) 若B A →:σ是双射时, 则必有|A|=|B|, 即 m=n 。
于是, 共有n!个双射。
3．设()A B B A ρτσ→→:,:且定义如下：对于()(){}b x A x b B b =∈=∈στ,试证明，若σ是满射，则τ是单射，其逆成立吗？证明：设B A →:σ是满射。
任取2121,,,b b B b b ≠∈，则存在 A A A ⊆⊆∅21,, 使得 }{)(},{)(2211b A b A ==σσ。
于是, 2211)(,)(A b A b ==ττ 。
若)()(21b b ττ=, 即21A A =, 则存在 21A A a I ∈, 使得21)(,)(b a b a ==σσ,从而21b b =。
矛盾。
故21A A ≠。
.即τ是单射。
若τ是单射, 则σ不一定是满射。
例如, 令A={1,2}, B={x , y} ,∅====)(},2,1{)(,)2()1(y x x ττσσ.于是, τ是单射, 但σ不是满射。
4．设σ是A 到B 的映射，τ是B 到C 的映射，试证明：（1）若σ和τ是满射，则στ⋅是满射；（2）若σ和τ是单射，则στ⋅是单射；（3）若σ和τ是双射，则στ⋅是双射；证明：(1) 设τ和σ是满射, 则对任意的z ∈C, 有y ∈B, 使得τ(y)= z 。
1-1，1-2（1）解：a)是命题，真值为T。
b)不是命题。
c)是命题，真值要根据具体情况确定。
d)不是命题。
e)是命题，真值为T。
f)是命题，真值为T。
g)是命题，真值为F。
h)不是命题。
i)不是命题。
（2）解：原子命题：我爱北京天安门。
复合命题：如果不是练健美操，我就出外旅游拉。
（3）解：a)(┓P ∧R)→Qb)Q→Rc)┓Pd)P→┓Q（4）解：a)设Q:我将去参加舞会。
R:我有时间。
P:天下雨。
Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。
b)设R:我在看电视。
Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。
c) 设Q:一个数是奇数。
R:一个数不能被2除。
（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。
(5) 解：a)设P：王强身体很好。
Q：王强成绩很好。
P∧Qb)设P：小李看书。
Q：小李听音乐。
P∧Qc)设P：气候很好。
Q：气候很热。
P∨Qd)设P： a和b是偶数。
Q：a+b是偶数。
P→Qe)设P：四边形ABCD是平行四边形。
Q ：四边形ABCD的对边平行。
P Qf)设P：语法错误。
Q：程序错误。
R：停机。
（P∨ Q）→ R(6) 解：a)P:天气炎热。
Q:正在下雨。
P∧Qb)P:天气炎热。
R:湿度较低。
P∧Rc)R:天正在下雨。
S:湿度很高。
R∨Sd)A:刘英上山。
B:李进上山。
A∧Be)M:老王是革新者。
N:小李是革新者。
M∨Nf)L:你看电影。
M:我看电影。
┓L→┓Mg)P:我不看电视。
Q:我不外出。
R:我在睡觉。
P∧Q∧Rh)P:控制台打字机作输入设备。
Q:控制台打字机作输出设备。
P∧Q1-3（1）解：a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b)是合式公式c)不是合式公式（括弧不配对）d)不是合式公式（R和S之间缺少联结词）e)是合式公式。
（2）解：a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。
