则P?Q
3．请将语句“他去旅游，仅当他有时间”翻译成命题公式． 设P：他去旅游。 Q：他有时间。 则P?Q
4．请将语句“41次列车下午五点开或六点开．”翻译成命题公式． 设P：41次列车下午五点。 Q：41次列车下午六点开。 则P或Q
5．请将语句 “有人不去工作”翻译成谓词公式． 设 A（x）：x是人
B（x）：去工作 ?x(A(x) ??B(x))
6．请将语句“所有人都努力工作．”翻译成谓词公式． 设 A（x）：x是人 B（x）：努力工作 ?x(A(x) ?B(x))
四、判断说明题（判断下列各题，并说明理由．）
1．命题公式?P?P的真值是1。
答：错误。因为P和P的否不能同时为真。
2．命题公式中的约束变元为y。 （?x）P(x)?Q(y)?R(z)）
答：错误。该式中的约束元为x。
3．谓词公式（?x）P(x，y)?(?z)Q(x,y,z)中?x量词的辖域为 P(x,y) ?(?z)Q(x,y,z) 。
答：错误。谓词公式（?x）P(x，y)?(?z)Q(x,y,z)中?x量词的辖域为P(x,y)。 若谓词公式（?x）P(x，y)?(?z)Q(x,y,z)变为（?x）P(x，y)?(?z)Q(x,y,z)），?x量词的辖域为P(x,y) ?(?z)Q(x,y,z)。
4．下面的推理是否正确，请给予说明．
(1) (?x)A(x)? B(x) 前提引入 (2) A(y) ?B(y) US (1)
答：错误。
因为B(x)不受全称量词?x的约束，不能使用全称指定规则。 （2）应为A(y) ?B(x)，换名时，约束元与自由变元不能混淆。 四．计算题
1． 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． P?Q?R??P?Q?R （析取范式） ?（?P?Q?R） （合取范式） 真值表： P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 ?P 1 1 1 1 0 0 0 0 原式 1 1 1 1 0 1 1 1 极小项 极大项 ?P??P??P ?P??Q?R ?P?Q??R ?P?Q?R P??Q?R P?Q??R P?Q?R ?P?Q?R
主析取范式（?P??P??P）?（?P??Q?R）?（?P?Q??R）?（?P?Q?R）?（P??Q?R）?（P?Q??R）?（P?Q?R） 主合取范式（?P?Q?R）
2．求命题公式(P?Q)?(R?Q) 的主析取范式、主合取范式． 真值表： P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 ?（P?Q） R?Q 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 原式 1 1 1 1 0 1 1 1 极小项 极大项 ?P??P??P ?P??Q?R ?P?Q??R ?P?Q?R P??Q?R P?Q??R P?Q?R ?P?Q?R
主析取范式（?P??P??P）?（?P??Q?R）?（?P?Q??R）?（?P?Q?R）?（P??Q?R）?（P?Q??R）?（P?Q?R）
主合取范式（?P?Q?R）
3．设谓词公式(?x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z)． （1）试写出量词的辖域；
（2）指出该公式的自由变元和约束变元． 答：（1）?x的辖域为P（x,y）??zQ(x,y,z)
?z的辖域为Q(x,y,z) ?y的辖域为R(y,z) (2) 约束变元为
P（x,y）??zQ(x,y,z)中的x
Q(x,y,z) 中的 z
R(y,z) 中的y
自由变元为
P（x,y）??zQ(x,y,z)中的y
R(y,z)中的z
4．设个体域为D={a1, a2}，求谓词公式?y?xP(x,y)消去量词后的等值式；
答：谓词公式?y?xP(x,y)消去量词后的等值式为
=?xP（x, a1）??xP（x, a2）
=P (a1, a2）? P (a1, a2）?(P(a1, a2）? P (a1, a2))
五、证明题
1．试证明 (P?(Q??R))??P?Q与? (P??Q)等价． 证明：(P?(Q??R))??P?Q
?? P?(Q??R))??P?Q ??P?Q
??（P??Q）
2．试证明?(A??B) ?(?B?C) ??C??A
证明：?(A??B) ?(?B?C) ??C ?(?A?B) ?(?B?C) ??C
?(?A?B) ?(?B ??C) ?(C ??C) ?(?A?B) ?((?B??C) ?? ?0) ?(?A?B) ?(?B??C)
?(?A ? (?B ??C) )?( B ?(?B ??C)) ?(?A ? (?B ??C) )?0 ??A ? (?B ??C)
??(A ?B ?C)
故由左边不可推出右边?A
离散数学形考任务1-7试题及答案合集
