l a a 。
>∈
也是t 的倍数，所以H a l ∈，K a l
∈，即K H a l ∈。
8. 设5阶置换为
?
???
??=4513254321α
?
??? ??=2543154321β
计算αβ，βα，1
-α，βαα1-，αββ1-。
解 略
9. 设}4321
{，，，=S ，写出S 上的所有4元置换。 解 略
10. 列出4元对称群>< ，
4S 的运算表，求出单位元，每个元的逆元，每个元的次数以及它的所有子群
§4.5 陪集与商群
习题4.5
1. 集合}19210{20，，，，
=Z 在“模20加法20+”下构成群。设H 是由元素5生成的20Z 的子群。 （1）求H 的每个元素及其次数。
（2）求H 在20Z 中的所有左陪集。
解 （1）}151050{，，
，=H ，151050，，，的次数分别为：1，4，2，4。 （2）H 在20Z 中的所有左陪集如下：
}151050{，，，=H ，}161161{1，，，=H ，}171272{2，，，=H
}181383{3，，，=H ，}191494{4，，，=H
2. 求12阶循环群}{11432a a a a a e G ，，
，，，， =的子群}{8
4a a e H ，，=在G 中的所有左陪集。
解 所有左陪集如下：
}{84a a e H ，，=，}{95a a a aH ，，=，}{10622a a a H a ，，=
3. 设H 是群>*<，
G 的子群，证明H 的所有不同左陪集（右陪集）中有且仅又一个在*下构成>*<，
G 的子群。 解 略
4. 证明6阶群必含有3次元。
解 略
5. 证明偶数阶群必含2次元。
解 设>*<，
G 是偶数阶群，若它无二次元，则对G 中的非单位元a ，有 1-≠a a
所以，G 中的元素，除单位元外，其他都是成对出现的，所以G 中的元素是偶数个，矛盾。
故偶数阶群必含2次元。 6. 证明在有限群中次数大于2的元素的个数必定是偶数。
解 略
7. 设>*<，
G 是一个阶数为p 的有限群，其中p 是质数，证明G 是循环群并求它的所有子群。
解 略 8. 设H 和K 分别是群>*<，
G 的s r ，阶子群，若s r ，互质，证明}{e K H = 。
解 略
9. 设i 为虚数单位，即12
-=i ，令
??
???????? ??±???? ??-±???? ??-±???? ?
?±=000110001001i i i i G ，，， 证明G 在矩阵乘法下构成群，并 （1）给出G 的运算表。
（2）找出G 的所有子群。
（3）证明G 的所有子群都是正规子群。
解 略
10. 设>*<，
G 是群，H 和K 是其子群，若H 或K 是正规子群，则KH HK =，其中
}|{K k H h k h HK ∈∧∈*=，
}|{H h K k h k KH ∈∧∈*=
解 略
11. 设>*<，
G 是群，H 是其子群，证明H 是正规子群当且仅当对任意的G a ∈，都有H aHa =-1
。 解 略
12. 令>+=<，Z G 是整数加群。求商群Z Z 4/，Z Z 12/和Z Z 12/4，其中，集合
}|4{4Z Z ∈?=z z ，}|12{12Z Z ∈?=z z 。
解 略
习题4.6
1. 对以下各小题给定的群1G 和2G 以及映射?，说明?是否为群1G 到2G 的同态。如
果是，说明是否为单同态，满同态和同构，并求同态像)(1G ?和同态核)ker(
?。 （1）>+=<，
Z 1G ，>?=<*，R 2G ，其中*R 为非零实数的集合，＋和×分别表示实数加法和实数乘法运算。
??
?-=→*
是奇数是偶数
，：x x x 11)(??R Z
（2）>+=<，
Z 1G ，>?=<，A G 2，其中}1|||{=∧∈=x x x A C ，C 为复数集合，＋和×分别表示实数加法和实数乘法运算。 x i x x A sin cos )(+=→??，：Z
（3）>+=<，R 1G ，>?=<，A G 2，其中A ，＋和×的定义同（2）。
x i x x A sin cos )(+=→??，：R
解 （1）因为，当x ，y 都为偶数，有2)(=+y x ?，2)()(=+y x ?? 当x ，y 都为奇数，有2)(=+y x ?，2)()(-=+y x ??
当x ，y 一个为偶数一个为奇数，有1)(-=+y x ?，0)()(=+y x ?? 所以?不是群1G 到2G 的同态。
（2）因为，)sin()cos()(y x i y x y x +++=+?，
y i y x i x y x sin cos sin cos )()(+++=+??
从而，1sin 1cos )01sin()01cos(
)01(i i +=+++=+? 1sin 1cos 10sin 0cos 1sin 1cos )0()1(i i i ++=+++=+??
所以?不是群1G 到2G 的同态。
（3）根据（2），?也不是群1G 到2G 的同态。
2. >?<，
Z ，>?<，A 都是有么半群，其中}10{，=A ，×表示实数乘法运算。 ??
?∈==→其它情况时
当，：0)(21)(N Z k x x A k ??
证明?是从Z 到A 的同态映射。
解 略
3. >+<，
R ，>?<，R 都是有么半群，＋和×分别表示实数加法和实数乘法运算。x x 10)(=→??，：R R
证明?是从>+<，
R 到>?<，R 的单同态，但不是同构。 解 略
4. >+<，
Z 是整数加法群，>*<，G 是任意一个群，对于G 中的任一固定元素a ，令)()(Z ∈=n a n g n ，证明g 是从Z 到G 的同态映射，并求同态核。
解 略
5. >+<，
R 是实数加法群，>?<，1C 是模为1的复数对于乘法运算的群，这两个群同态吗？同构吗？请说明理由。
解 略
6. >+<+，Z 和>?<+，Z 分别是正整数对于加法和乘法构成的半群，试问从>+<+，Z 到>?<+
，
Z ，从>?<+，Z 到>+<+，Z 都存在同态映射吗？说明理由。
解 >+<+，
Z →>?<+
，Z 的同态映射如下： +∈?=Z n n f ,1)(
而>?<+
，
Z →>+<+
，Z 不存在同态映射，这可用反证法进行证明。 若存在>?<+
，
Z →>+<+
，Z 的同态映射g ，则有： +∈?+=+Z n m n g m g n m g ,),()()(
特别地令1==n m ，则得到0)1(=g ，这与g 是>?<+
，Z →>+<+，Z 的映射矛盾，所以>?<+，Z →>+<+，Z 不存在同态映射。
7. 设f 是从群>*<，
G 到群>?<，H 的同态映射，g 是从群>?<，H 到群>?<，K 的同态映射，证明复合函数g f 是从群>*<，G 到群>?<，K 的同态映射。
解 略
8. 设>*<，
G 、>?<，H 是代数系统，?*，都是二元运算，φ是从G 到H 的同态映射，则
（1）?是)(G φ上的运算，即>?<，)(G ?是代数系统。 （2）如果*在G 上满足交换律，则?在)(G φ上也满足交换律。 （3）如果*在G 上满足结合律，则?在)(G φ上也满足结合律。 （4）如果*在G 上满足等幂律，则?在)(G φ上也满足等幂律。
（5）如果θ是>*<，
G 的零元，则)(θφ是>?<，)(G ?的零元。 解 略
9. 设>*'*<，，
G 、>?'?<，，H 是代数系统，?'?*'*，，，都是二元运算， φ是从G 到H 的同态映射，证明如果在G 上，*和*'满足吸收律，则在)(G φ上，?和?'也满足吸收律。
解 略
10. 设>*<，
G 是群，定义映射G G →：?为1
)(-=x x ?，证明?是G 的自同构当且仅当G 是交换群。
解 略
11. 设?是从群>*<，
G 到群>?<，H 的同态映射，证明若G 是循环群，则)(G ?也是循环群。
解 略
12. 设>*<，G 和>?<，H 分别是m 阶群和n 阶群，若从G 到H 存在单同态，证明n m |，即m 是n 的因子。
解 略
13. 设?是从群>*<，
G 到群>?<，H 的同态映射，对任意的G a ∈，记)(a b ?=，试问b 和a 的次数是否一定相同？如果不同，它们之间有何关系？
解 略
14. 给出群>+<6，
6Z 的全部自同态。 解 略
习题4.7
1. 设}1|{2
-=∈+=i Z b a bi a A ，，。证明A 关于复数的加法和乘法构成环，称为高斯整数环。 2. 设n n
n a a a x a x a x a a x f ，，，， 212210)(++++=为实数，称)(x f 为实数域
上的n 次多项式，令
})(|)({N n x f x f A n ∈=，次多项式为实数域上的。
证明A 关于多项式的加法和乘法构成环，称为实数域上的多项式环。 3. 判断下列集合和给定运算是否构成环、整环和域，如果不能构成，请说明理由。 （1）}1|{2
-=∈+=i b a bi a A ，，Q ，运算为复数的加法和乘法。 （2）}|12{Z ∈+=z z A ，运算为实数的加法和乘法。 （3）}|2{Z ∈=z z A ，运算为实数的加法和乘法。 （4）}0|{Z ∈∧≥=x x x A ，运算为实数的加法和乘法。
（5）
}|5{4Q ∈+=b a b a A ，，运算为实数的加法和乘法。 4. 设>?+<，，
R 是环，证明 （1）000==∈?a a R a ，
（2）)()()(ab b a b a R b a -=-=-∈?，，
（3）ca ba a c b ac ab c b a R c b a -=--=-∈?)()(，，，，
5. 设>?+<，，
R 是环，令 )}(|{ax xa R a R x x C =∈?∧∈=
C 称作环R 的中心，证明C 是R 的子环。
6. 设a 和b 是含么环中的两个可逆元，证明：
（1）a -可逆，且1
1)(---=-a a
（2）ab 可逆，且1
11)(---=a b ab
7. 在域
>?+<555，，Z 中解下列方程和方程组：
（1）23=x
（2）
??
?
??=+=+=+122212y x z y z x
8. 类似于子环，给出子整环和子域的定义
习题5.1
1. 下面哪些集合是偏序集？
（1）=><，Z （2）≠><，Z （3）≥><，
Z
（4）>/<|，
Z
解 （1）是偏序集，（2）不是偏序集，（3）是偏序集，（4）不是偏序集
2. 确定由下面的关系图5.6表示的表示的3个关系是否为偏序？并列出这些关系中的所有序偶来进行验证。
解 略
图5.6 习题2的图
3. 确定由下面的关系矩阵表示的关系是否为偏序？
（1）?
????
??
???100011101
（2）?
????
??
???101010001
（3）????
??
?
???????1011110001100101
解 略
4. 画出在下述集合上的整除关系的哈斯图。
（1）}87654321
{，，，，，，， （2）}131175321
{，，，，，， （3）}483624126321
{，，，，，，，
（4）}6432168421
{，，，，，， 解 （1）、（2）的哈斯图如下：
（3）、（4）略
5. 在下面偏序集中找出两个不可比的元素。
d
c
b
a
d
c
b
a
b
a
d
c
(a)
(c)
(b)
(a)
5
4
8
3
2 6
7
1
11
7 3 2 5 13
1
（1）?><，，，
})210{(p
（2）><|}86421{，，
，， 解 略
6. ><|}452415953{，，，，，，
是偏序集。 （1）求极大元素和极小元素。
（2）存在最大元素吗？存在最小元素吗？如果存在，请求出。
（3）找出子集}53{，的所有上界。如果它的上确界存在的话，上确界。
（4）找出子集}4515
{，的所有下界。如果它的下确界存在的话，求出下确界。 解 （1）极大元素为9，15，24和45，极小元素为3和5。 （2）不存在最大元素，也不存在最小元素。 （3）子集}53{，的上界有15和45，上确界是15。
（4）子集}4515
{，的下界有3，5和15，下确界是15。
7. ?><，，，，，，，，，，，，，，，，，
}}432{}431{}43{}42{}41{}21{}4{}2{}1{{是偏序集。
（1）求极大元素和极小元素。
（2）存在最大元素吗？存在最小元素吗？
（3）找出子集}}4{}2{{，
的所有上界。如果它的上确界存在的话，上确界。 （4）找出子集}}432{}321
{{，，，，，的所有下界。如果它的下确界存在的话，求出下确界。
解 略
8. 给出满足下列性质的偏序集。 （1）有一个极小元素但没有极大元素。 （2）有一个极大元素但没有极小元素。
（3）既没有极大元素也没有极小元素。 解 略
9. 设R 是集合X 上的半序。 （1）证明1
-R R 是等价关系。
（2）定义商集)/(1
-=R R X Y 上的关系S ：Y D C ∈?，，S D C >∈<，当且仅当在C 、D 中分别存在元素d c 、使得R d c >∈<，。证明S 是商集Y 上的偏序。
解 略
10. 给出下面小写英文字母串的字典序。
（1）quack ，quick ，quicksilver ，quicksand ，quacking （2）open ，opener ，opera ，operand ，opened （3）zoo ，zero ，zoom ，zoology ，zoological 解 略
11. 给出二进制串0，01，11，001，010，011，0001和0101的基于10<的字典顺序。 解 略
12. 假设><11 ，X 和><22 ，X 是两个偏序集。在笛卡儿积21X X ?上定义一个关系：><><2121b b a a ，， 当且仅当111b a 且222b a 。证明这样定义的关系 是集合21X X ?上的偏序关系。
解 略
13. 求一个与集合}36241286321
{，，，，，，，上的整除关系相容的全序。 14. 如果表示建筑一座房子所需任务的哈斯图如下图5.7所示，通过制定这些任务的顺序来安排他们。
解 略
15. 对一个软件项目的任务进行排序，关于这个项目任务的哈斯图给在图5.8中。
图5.8 习题15的图 解 对一个软件项目的任务排序如下：
模块集成
α测试 β测试
完成
建立测试点
写文档
编写功能需求 确定用户需求 开发系统需求
确定用户需求，编写功能需求，开发系统需求，建立测试点，开发模块A ，开发模块B ，开发模块C ，模块集成，写文档，α测试，β测试，完成。
习题5.2
1. 确定具有下面图5.11所示哈斯图的偏序集是否为格，
习题5.3
1. 对以下各小题给定的集合和运算判断它们是哪一类代数系统（半群、有么半群、群、环、域、格、布尔代数），并说明理由。
（1）}
441
3312211{1，，，，，，=S ，*为普通乘法。
（2）
}{212n a a a S ，，， =，i j i j i a a a S a a =*∈?，，2。这里的n 是给定正整数，且2≥n 。
（3）
}10{3，=S ，*为普通乘法。
（4）}6321
{4，，，=S ，4S y x ∈?，，y x *和y x ?分别表示求x 和y 的最小公倍数和最大公因数。
（5）
}10{5，=S ，*为模2加法，?为模2乘法。
解 （1）}
4413312211{1，，，，，，=S ，*为普通乘法。是群。
（2）
}{212n a a a S ，，， =，i j i j i a a a S a a =*∈?，，2。这里的n 是给定正整数，且2≥n 。是半群（无单位元）。
（3）
}10{3，=S ，*为普通乘法。是有幺半群（0没有逆元）
。
（4）}6321
{4，，，=S ，4S y x ∈?，，y x *和y x ?分别表示求x 和y 的最小公倍数和最大公因数。是布尔代数。
（5）
}10{5，=S ，*为模2加法，?为模2乘法。是布尔代数。
2. 在布尔代数中证明
01=??=⊕?c c b a b a b a
解 略
3. 对于54321
，，，，=n ，给出所有不同构的n 元格，并说明其中那些是分配格、有补格和布尔格。
解 略
4. 设>?⊕<10，，，，，
c
B 是布尔代数，在B 上定义二元运算*，B y x ∈?，有 )()(y x y x y x c c ?⊕?=*
问>*<，B 能否构成代数系统？如果能，指出是哪一种代数系统。为什么？
解 略
5. 在布尔代数中化简下列式子
（1）)()()(c b c b a b a c
c ?⊕??⊕? （2）c b a c b a c
c
?⊕?⊕?)())(( （3）)()()(c b c b a b a c
?⊕??⊕? （4）c c
b a b a )()(⊕⊕?
（5）
)0()1(c
a a ?⊕? （6）)()()(c
c c c c c c b a c b a c b a ??⊕??⊕?? 解 略
6. 在布尔代数中证明下列等式
（1）b a b a a c
⊕=?⊕)( （2）b a b a a c ?=⊕?)(
（3）
)()()()()(b a c a c b b a c a c c ?⊕?=?⊕?⊕? （4）)()()()()()(a c c b b a a c c b b a c
c c c c c ⊕?⊕?⊕=⊕?⊕?⊕
（5）
c b a c b c a b a c c ⊕?=?⊕?⊕?)()()()( 解 略
7. 设φ是从布尔代数>?⊕<10，，，，，
c B 到布尔代数>?'⊕'<'1'0''，，，，，c
B 的同态映射，证明)(B φ构成'B 的子布尔代数。
解 略
图5.11 习题1的图
解 图(a)是格，图(b)是格，图(c)是格。
2. 在一个公司里用信息流的格模型控制敏感信息，公司的每个部门都具有由有序对
)(C A ，表示的安全类别，其中A 是权限级别，C 是种类。这里，权限级别A 可以是0（非
私有的），1（私有的），2（受限制的）或3（注册的）。种类C 是集合{猎豹，黑鹰，美洲狮}
d
a
c
e f
b
b
d f h g c
e a
b
d f h
g c
e a
i
(a)
(b)
(c)
的子集（在公司里常常使用动物的名字作为项目的代码名字）。试问 （1）信息允许从（私有的，{猎豹，美洲狮}）流向（受限制的，{美洲狮}）吗？ （2）信息允许从（受限制的，{猎豹}）流向（注册的，{猎豹，黑鹰}）吗？ （3）信息从（私有的，{猎豹，美洲狮}）允许流向哪些安全类？
（4）信息允许从那些安全类流向（受限制的，{黑鹰，美洲狮}）？ 解 略
3. 证明每个有限格都有一个最小元素和一个最大元素。 解 略
4. 给出一个无限格的例子，使得 （1）既没有最小元素也没有最大元素。 （2）有最小元素但没有最大元素。 （3）有最大元素但没有最小元素。 （4）有最小元素也有最大元素。 解 略
5. 设>< ，L 是格，其哈斯图如图5.12所示，取
图5.12 习题5的图
}{1d c b a S ，，，=，}{2f d b a S ，，，=，}{3f e d c S ，，，=，}{4g f b a S ，，，=。
试问><11 ，S ，><22 ，S ，><33 ，S ，><44 ，S 中哪些是格，哪些是>< ，L 的
子格，这里关系)(i i i S S ?= ，4321
，，，=i 。 解 略
6. 设><|，L 和≤><，S 是两个格，其中}16842{，，
，=L ，}10321{，，，， =S ，“|”是数的整除关系，“≤”是数的小于等于关系。试给出从L 到S 上的两个不同的格同态映射。
解 略
7. 设φ是从格><11 ，L 到格><22 ，L 的满同态映射，若><11 ，L 是有界格，证明><22 ，L 也是有界格。
b
a
d
e
g
c
f
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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】
第四章部分课后习题参考答案 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)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) xG ?，在（a）(b)中均为真命题。 (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ?? x ? ( ) ( (x H (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快
命题符号化为: ))),()(()((y x H x F x y G y →?∧?? 9.给定解释I 如下: (a) 个体域D 为实数集合R. (b) D 中特定元素=0. (c) 特定函数(x,y)=xy,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x离散数学答案屈婉玲版第二版 高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（pr）∧(﹁q∨s) ?（01）∧(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?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例）
第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p)
离散数学第三版课后习题答案
离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论
离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；
7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 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.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.
（2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表：
大学本科高等数学《离散数学》试题及答案
本科高等数学离散数学试题及答案 一、填空题 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变成完全图。
吉林大学离散数学课后习题答案
第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每
一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故
G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空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是阿贝尔群的元素，则-(a+b+c)= 。 10、一个图的哈密尔顿路是。 11、不能再分解的命题称为，至少包含一个联结词的命题称 为。 12、命题是。 13、如果p表示王强是一名大学生，则┐p表示。 14、与一个个体相关联的谓词叫做。 15、量词分两种：和。 16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。
19、代数系统是指由及其上的或 组成的系统。 20、设是代数系统，其中是*1,*2二元运算符，如果*1,*2都满 足、，并且*1和*2满足，则称是格。 21、集合A={a,b,c,d}，B={b }，则A \ B= 。 22、设A={1, 2}, 则∣A∣= 。 23、在有向图中，结点v的出度deg+(v)表示，入度deg-(v)表示 以。 24、一个图的欧拉回路是。 25、不含回路的连通图是。 26、不与任何结点相邻接的结点称为。 27、推理理论中的四个推理规则 是、、、。 二、判断题（每题2分，共20分） 1、空集是唯一的。 2、对任意的集合A，A包含A。 3、恒等关系不是对称的，也不是反对称的。 4、集合{1,2,3,3}和{1,2,2,3}是同一集合。 5、图G中，与顶点v关联的边数称为点v的度数，记作deg(v)。 6、在实数集上，普通加法和普通乘法不是可结合运算。 7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。 8、设（A,*）是代数系统，a∈A，如果a*a＝a，则称a为（A，*）的等幂元。 9、设f：A→B，g：B→C。若f，g都是双射，则gf不是双射。 10、无向图的邻接矩阵是对称阵。 11、一个集合不可以是另一个集合的元素。 12、映射也可以称为函数，是一种特殊的二元关系。 13、群中每个元素的逆元都不是惟一的。
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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
离散数学答案(尹宝林版)第一章习题解答
第一章 命题逻辑 习题与解答 ⒈ 判断下列语句是否为命题，并讨论命题的真值。 ⑴ 2x - 3 = 0。 ⑵ 前进！ ⑶ 如果8 + 7 > 20，则三角形有四条边。 ⑷ 请勿吸烟！ ⑸ 你喜欢鲁迅的作品吗？ ⑹ 如果太阳从西方升起，你就可以长生不老。 ⑺ 如果太阳从东方升起，你就可以长生不老。 解 ⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。 ⒉ 将下列命题符号化： ⑴ 逻辑不是枯燥无味的。 ⑵ 我看见的既不是小张也不是老李。 ⑶ 他生于1963年或1964年。 ⑷ 只有不怕困难，才能战胜困难。 ⑸ 只要上街，我就去书店。 ⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 ⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。 ⑻ 三角形三条边相等是三个角相等的充分条件。 ⑼ 我进城的必要条件是我有时间。 ⑽ 他唱歌的充分必要条件是心情愉快。 ⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。 解 ⑴ p ：逻辑是枯燥无味的。 “逻辑不是枯燥无味的”符号化为 ?p 。 ⑵ p ：我看见的是小张。q ：我看见的是老李。 “我看见的既不是小张也不是老李”符号化为q p ?∧?。 ⑶ p ：他生于1963年。q ：他生于1964年。 “他生于1963年或1964年”符号化为p ⊕ q 。 ⑷ p ：害怕困难。q ：战胜困难。 “只有不怕困难，才能战胜困难”符号化为q → ? p 。 ⑸ p ：我上街。q ：我去书店。 “只要上街，我就去书店”符号化为p → q 。 ⑹ p ：小杨晚上做完了作业。q ：小杨晚上没有其它事情。 r ：小杨晚上看电视。s ：小杨晚上听音乐。 “如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为s r q p ∨→∧。 ⑺ p ：林芳在家里。q ：林芳做作业。r ：林芳看电视。 “如果林芳在家里，那么他不是在做作业就是在看电视”符号化为r q p ∨→。 ⑻ p ：三角形三条边相等。q ：三角形三个角相等。
离散数学课后答案
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学课后习题答案(左孝凌版)
离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：
最新离散数学习题答案
离散数学习题答案 习题一及答案：（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、用真值表法求下面公式的主析取范式：
021046[离散数学(2)] 天津大学机考题库答案
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={|x+y=10,x ∈A,y ∈A},则R 的性质为（ B ）。 A.自反的 B.对称的 C.传递的，对称的 D.反自反的，传递的 5、设R 和S 是集合A 上的任意关系，则下列命题为真的是（ A ）。 A.若R 和S 是自反的，则R S 也是自反的 B.若R 和S 是反自反的，则R S 也是反自反的 C.若R 和S 是对称的，则R S 也是对称的 D.若R 和S 是传递的，则R S 也是传递的 6、设R 和S 是非空集合A 上的等价关系，则下面是A 上的等价关系的是（ D ）。 A.()A A R ?- B.S R ? C.S R - D.S R ? 7、设函数f ：N→N （N 为自然数集），f(n)=n+1，下面四个命题为真的是（ A ）。 A.f 是单射 B.f 是满射 C.f 是双射的 D.f 非单射非满射 8、图G 和'G 的结点和边分别存在一一对应关系是G 和'G 同构的（ B ）。 A.充分条件 B.必要条件 C.充要条件 D.既不充分也不必要条件 9、平面图(如下)的三个面的次数分别是（ A ）。 A ．11，3，4 B ．11，3，5 C ．12，3，6 D ．10，4，3 10、G 是连通平面图，有5个顶点、6个面，则G 的边数为（ D ）。
离散数学课后习题答案_(左孝凌版)
1-1，1-2 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P：a和b是偶数。Q：a+b是偶数。P→Q
e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨Q）→R (6) 解： a)P:天气炎热。Q:正在下雨。P∧Q b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。S:湿度很高。R∨S d)A:刘英上山。B:李进上山。A∧B e)M:老王是革新者。N:小李是革新者。M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。R:我在睡觉。P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（括弧不配对） d)不是合式公式（R和S之间缺少联结词） e)是合式公式。 （2）解： a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。这个过程可以简记为：A；(A∨B)；(A→(A∨B)) 同理可记 b）A；┓A ；(┓A∧B) ；((┓A∧B)∧A) c）A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d）A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) （3）解： a）((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b）((B→A)∨(A→B))。 （4）解： a) 是由c) 式进行代换得到，在c) 中用Q代换P, (P→P)代换Q.
