离散数学复习资料

更新时间：2024-04-26 23:19:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

离散数学知识点笔记推荐度：
相关推荐

离散数学复习资料

一、（1）证明(P?Q)∧(Q?R)?(P?R)

（2）求(P∨Q)?R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。解：（1）因为((P?Q)∧(Q?R))?(P?R)

??((?P∨Q)∧(?Q∨R))∨(?P∨R) ?(P∧?Q)∨(Q∧?R)∨?P∨R

?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R)) ?(P∧?Q)∨(Q∨?P∨R)

?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R) ?T

所以，(P?Q)∧(Q?R)?(P?R)。

（2）(P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R

?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)

?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R) ?M2∧M4∧M6 ?m0∨m1∨m3∨m5

所以，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。二、分别找出使公式?x(P(x)??y(Q(y)∧R(x，y)))为真的解释和为假的解释。

解：设论域为{1，2}。

若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，则 ?x(P(x)??y(Q(y)∧R(x，y)))

??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))

?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) ?(T?((F∧F)∨(F∧F)))∧(T?((F∧F)∨(F∧F))) ?(T?F)∧(T?F) ?F

若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，则 ?x(P(x)??y(Q(y)∧R(x，y)))

??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))

?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) ?(T?((T∧T)∨(T∧T)))∧(T?((T∧T)∨(T∧T))) ?(T?T)∧(T?T) ?T

三、在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

解论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为：

?x(A(x)??B(x))，?x(B(x)∨C(x))，??xC(x)?x?A(x)

下面给出证明：

(1)??xC(x) P (2)?x?C(x) T(1)，E (3)?C(c) T(2)，ES (4)?x(B(x)∨C(x)) P (5)B(c)∨C(c) T(4)，US (6)B(c) T(3)(5)，I (7)?x(A(x)??B(x)) P

(8)A(c)??B(c) T(7)，US (9)?A(c) T(6)(8)，I (10)?x?A(x) T(9) ，EG 四、下列论断是否正确？为什么？

(1)若A∪B＝A∪C，则B＝C。 (2)若A∩B＝A∩C，则B＝C。 (3)若A?B＝A?C，则B＝C。

解 (1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。 (2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。 (3)成立。因为若A?B＝A?C，对任意的x∈B，当x∈A时，有x∈A∩B?x?A?B?x?A?C＝(A∪C)－(A∩C)?x∈A∩C?x∈C，所以B?C；当x?A时，有x?A∩B，而x∈B?x∈A∪B，所以x∈A∪B－A∩B＝A?B?x∈A?C，但x? A，于是x∈C，所以B?C。

同理可证，C ?B。

因此，当A?B＝A?C时，必有B＝C。

五、若R是集合A上的自反和传递关系，则对任意的正整数n，Rn＝R。

证明当n＝1时，结论显然成立。设n＝k时，Rk＝R。当n＝k＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。

由传递性得R*R?R。另一方面，对任意的∈R，由R自反得∈R，再由关系的复合得∈R*R，从而R?R*R。因此，R＝R*R。

由数学归纳法知，对任意的正整数n，Rn＝R。

六、设函数f：R×R?R×R，f定义为：f()＝。

(1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。

－1

(4)求复合函数f?f和f?f。

证明 (1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

(2)对任意的∈R×R，令x＝

－1

u?wu?wu?wu?wu?w

，y＝，则f()＝<＋，－22222

u?w

>＝，所以f是满射。 2

(3)f()＝<

－1－1

u?wu?w

，>。 22

－1

(4)f?f()＝f(f())＝f()＝<

x?y?x?yx?y?(x?y)，>＝

22f?f()＝f(f())＝f()＝＝<2x，2y>。七、设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是否是自反、反自反、对称、传递的。解 (1)R的关系图如图所示： (2) R的关系矩阵为：

?1??0M(R)??1??1?反自反的；由于矩阵不对称，R不是对称的；

经过计算可得

101110110??0? ?0?0??(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是

?1??02M(R)??1??1?101110110??0??M(R)，所以R是传递的。 ?0?0??－1

－1

八、若是群，H是G的非空子集，则是的子群?对任意的a、b∈H有a*b∈H。

证明必要性：对任意的a、b∈H，由是的子群，必有b∈H，从而a*b∈H。充分性：由H非空，必存在a∈H。于是e＝a*a∈H。任取a∈H，由e、a∈H得a＝e*a∈H。

对于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因为H是G非空子集，所以*在H上满足结合律。

－1－1

－1

综上可知，是的子群。

九、给定二部图G＝，且|V1∪V2|＝m，|E|＝n，证明n≤m/4。

2证明设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m1。因为(?m1)2?0，即

m2m222，所以n≤m/4。?mm1?m14

十、用公式法判断下列公式的类型：

(1)(?P∨?Q)?(P??Q) (2)(P?Q)?(P∧?(Q∨?R))

解：（1）因为(?P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)

?(P∧Q)∨(P∧?Q)∨(?P∧Q) ?m1∨m2∨m3 ?M0

所以，公式(?P∨?Q)?(P??Q)为可满足式。

（2）因为(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) ?M0∧M1

?m2∨m3∨m4∨m5∨m6∨m7

所以，公式(P?Q)?(P∧?(Q∨?R))为可满足式。

十一、在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。

解：论域：所有人的集合。Q(x)：x是勤奋的；H(x)：x是身体健康的；S(x)：x是科学家；C(x)：

x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：

?x(S(x)?Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧H(x))?x(C(x)∨F(x))

下面给出证明：

(1)?x(S(x)∧H(x)) P (2)S(a)∧H(a) T(1)，ES (3)?x(S(x)?Q(x)) P

(4)S(a)?Q(a) T(1)，US (5)S(a) T(2)，I (6)Q(a) T(4)(5)，I

(7)H(a) T(2)，I (8)Q(a)∧H(a) T(6)(7)，I (9)?x(Q(x)∧H(x)?C(x)) P (10)Q(a)∧H(a)?C(a) T(9)，Us (11)C(a) T(8)(10)，I (12)?xC(x) T(11)，EG (13)?x(C(x)∨F(x)) T(12)，I

十二、设A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。

解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}} 四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？ (1)若R和S是自反的，则R*S也是自反的。 (2)若R和S是反自反的，则R*S也是反自反的。 (3)若R和S是对称的，则R*S也是对称的。 (4)若R和S是传递的，则R*S也是传递的。 (5)若R和S是自反的，则R∩S是自反的。 (6)若R和S是传递的，则R∪S是传递的。

解 (1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是

a>∈R*S，故R*S也是自反的。

(2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

(3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。

(4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。

(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。

十三、令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问

(1)有多少个不同的由X到Y的函数？

(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？ (3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？

解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，

m故不同的单射有Cnm!＝n(n－1)(n―m―1)个。