离散数学复习资料

离散数学复习资料

一、（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

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

1

解 论域：所有人的集合。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。

2

－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

－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

－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上满足结合律。

3

－1－1

－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，即

2

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) …… 此处隐藏：3734字，全部文档内容请下载后查看。喜欢就下载吧 ……