离散数学第一次测试（第一、二章）
一、
将下列命题符号化。（8分）
（1） 如果我吃饭前完成家庭作业，并且天不下雨的话，那么，我就去看球赛；
解 设P表示我吃饭前完成家庭作业, Q表示天不下雨, R表示我就去看球赛, 则命题可表示为(P?Q)?R.
（2） 如果你明天看不到我，那么我就去芝加哥；
解 设P表示你明天看不到我, Q表示我就去芝加哥, 则命题可表示为P?Q.
（3） 若a和b是偶数，则a + b也是偶数；
解 设P表示a和b是偶数, Q表示a + b也是偶数, 则命题可表示为P?Q
（4） 虽然天气很好，老王还是不来；
解 设P表示天气很好, Q表示老王还是不来, 则命题可表示为P?Q
二、
设P、Q的真值为0，R、S的真值为1。求下列命题的真值（10分）
（1）(P?(R?S))?((P?Q)?(R?S));
解命题的真值是1
（2）?(P?(Q?(R?P)))?(R??S)。 解命题的真值是1
三、证明。（30分）
（1）A?(B?C)?(A??B)?C；
解A?(B?C) ? ? A? B? C
?(A?? B)?C
（2）((A?B)?C)?(B?(D?C))?(B?(D?A))?C；
解((A? B) ? C) ? (B? (D? C) ?(?A??B?C) ?(?B?D?C) ?(B? (D? A)) ? C
（3）???x??P?x??Q?c?????x?P?x???Q?c?;
证: (1) (?x) P(x) P(附加前提) (2) P(a) ES (3) ?(?x)(P(x) ?Q(c)) P (4) (?x) ? (P(x) ?Q(c)) T(3),E (5) ? (P(a) ?Q(c)) US (6) ? P(a) ? ?Q(c) T(5),E (7) ?Q(c) T(2,6),I (8) (?x) P(x) ??Q(c) CP
四、求下列公式所对应的合取范式和析取范式。（12分）
（1）(P?Q) ?R;
解(P?Q) ?R?? (P?Q) ?R
??P??Q?R为合取范式也为析取范式
（2）?(P?Q) ?(P?Q);
解?(P?Q) ?(P?Q) ?（?P??Q）?（?P ?Q) 为合取范式
? (? P?Q) ? (? P?? Q) 为析取范式
五、符号化下列论断，并验证论断是否有效。（10分）
有红、黄、蓝、白四队参加足球赛。如果红队第三，则黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四。
解 设H3表示红队第三，W2黄队第二，B4蓝队第四，W1白队是第一，
前提为 H3?（W2?B4）），?W1?H3， W2 结论 W1 ?B4 容易证明论断有效。
六、用谓词和量词，将命题符号化。（10分） （1）每个实数都存在比它大的另外的实数。 解: 设R(x): x是实数, P(x,y): x>y.
则命题表示为: (?x)(R(x) ? (?y)(R(y) ?P(y,x))). （2）会叫的狗未必都咬人。
解: 设 P(x): x是会叫的狗, Q(x): x 咬人. 则命题表示为: ?(?x)(P(x) ? Q(x)). （3）每个人都有某些专长。
解: 设 M(x): x是人, P(x): x是专长, S(x,y):x拥有y. 则命题表示为: (?x) (M(x) ? (?y)(P(y) ?S(x,y))).
（4）有些液体能溶解任何金属。
解: 设 P(x): x是液体, Q(x):x是金属, S(x,y): x溶解y. 则命题表示为: (?x) (P(x) ?(?y) (Q(y) ? S(x,y))). （5）任何自然数的直接后继数必大于零。
解: 设 N(x): x是自然数, S(x,y): y是x的直接后继数,P(x,y): x>y. 则命题表示为: (?x)(N(x) ? (?y)(N(y) ? S(x,y) ? P(y,0))).
七、求下列各式的真值。（10分）
(1) (?x) (P(x) ?Q(x))，其中P(x)：x = 1；Q(x)：x = 2； 而且论域是{1, 2}；
解: 原式 ?(P(1) ?Q(1)) ? (P(2) ?Q(2))
?(T ?F) ? (F ?T) ?T.
(2) (?x)(P?Q(x)) ? R(a)， 其中P： 2 >1； Q(x)： x?3； R(x)： x?6；a = 5； 而且论域是 {?2，3，6}； 解: 原式 ? ((P →Q(-2))∧(P→Q(3))∧(P→Q(6)))∨R(5) ?((T →T)∧(T→T)∧(T→F))∨F ?(T∧T∧F)∨F
?F
八、把下列各式化为前束范式。（10分）
(1) (?x)(P(x) ?(?y)Q(x,y))； 原式 ? (?x) (?y) (P(x) ?Q(x,y)).
(2) (?x)( ?(?y)(P(x,y) ?(?z)Q(z)) ?R(x))； 解: 原式 ? (?x)( ?(?y) (?z) (P(x,y) ?Q(z)) ?R(x))
? (?x)( (?y) (?z) ? (P(x,y) ?Q(z)) ?R(x)) ? (?x)(?y)(?z)(? (P(x,y) ?Q(z)) ?R(x)).
