则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试题及答案合集
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)