离散数学()复习题.doc

离散数学（2）-1复习题 一、证明题 1．利用真值表证明公式 (Q→P)?(?P?Q) 为矛盾式。 解 令β=(Q→P)?(?P?Q)，公式β的真值表如表所示。 公式β的真值表 P?? Q Q→P ?P?Q β 0?? 0 0?? 1 1?? 0 1?? 1 1 0 1 1 0 1 0 0 0 0 0 0 ?因为公式β的真值表的最后一列全为0，所以该公式为矛盾式。 2. 证明整数集I上的模m同余关系R={x,y|x?y(mod m)}是等价关系。其中，x?y(mod m)的含义是x-y可以被m整除。 证明：1）?x∈I，因为（x-x）/m=0，所以x?x(mod m)，即xRx。 2）?x,y∈I，若xRy，则x?y(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k∈I，所以y?x(mod m)，即yRx。 3）?x,y,z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。 3．利用真值表证明?(P?Q)与?P??Q这两个命题公式是等值的。 解：要判断?(P?Q)与?P??Q这两个命题公式是否等值，即用真值表法判断?(P?Q)与??P???Q是否为重言式，此等价式的真值表如表所示。 公式?(P?Q) 与??P??Q的真值表 P?? Q ?(P?Q) ?P??Q ?(P?Q)?(?P??Q) 0?? 0 0?? 1 1?? 0 1?? 1 1 0 0 0 1 0 0 0 1 1 1 1 从表1.10可知?(P?Q)?(?P??Q)是重言式，因而?(P?Q)与?P??Q等值。 4. G,*是个群，u∈G，定义G中的运算“?”为a?b=a*u-1*b，对任意a,b∈G，求证：G, ?也是个群。 证明：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，存在单位元。 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，每个元素都有逆元。 所以G, ?也是个群。 5. 证明下列等值式：(P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。 证明: (P∧Q∧A?C)∧(A?P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))?C 6. 推理证明题 ?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)?Q(y)∧R(x)) (4)P(a)?Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 7. 证明下列等值式：((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T。 证明: ((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R) ?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入) 8. 推理证明题 ?P∨Q，?Q∨R，R?SP?S。 证明：(1)P 附加前提 (2)?P∨Q P (3)Q T(1)(2)，I (4)?Q∨R P (5)R T(3)(4)，I (6)R?S P (7)S T(5)(6)，I (8)P?S CP 9. 证明：R是传递的?R*R?R。 证明 若R是传递的，则x，y∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是传递的得xRy，即有x，y∈R，所以R*R?R。 反