6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为 0(F) ．
7．谓词命题公式(?x)((A(x)?B(x)) ?C(y))中的自由变元为 y ． 8．谓词命题公式(?x)(P(x) ?Q(x) ?R(x，y))中的约束变元为 x ． 三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式． 设P：今天是晴天。 则P
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 设P：小王去旅游。 Q：小李去旅游。 则P?Q
3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 设P：明天下雪。 Q：我去滑雪。 则P?Q
4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设P：他去旅游。 Q：他有时间。 则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．命题公式?P?(P??Q)?P为永真式． 答：对。?P?（?P?Q）?P??P?P?1
3．谓词公式?xP(x)?(?yG(x,y)??xP(x))是永真式．
答：对。它同P?（Q?P）是等价形式P?（Q?P）??P?（?Q?P）
??P??Q?P?1?Q
4．下面的推理是否正确，请给予说明．
(1) (?x)A(x)? B(x) 前提引入 (2) A(y) ?B(y) US (1) 答：对。
四．计算题
1． 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． P?Q?R??P?Q?R （析取范式） ?（?P?Q?R） （合取范式） 真值表： P 0 0 0 0 1 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）
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 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 ?P 原式 1 1 1 1 0 1 1 1 极小项 ?P??Q?R 及大项 ?P?Q?R 1 1 1 1 0 0 0 0 ?P??P??P ?P?Q??R ?P?Q?R P??Q?R P?Q??R P?Q?R 原式 1 1 1 1 0 1 1 1 极小项 ?P??Q?R ?P?Q??R ?P?Q?R 及大项 ?P?Q?R 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 ?P??P??P 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)消去量词后的等值式为 （R（a,a）?R（a,b））? (R（b,a）?R（b,b）)
五、证明题
1．试证明 (P?(Q??R))??P?Q与? (P??Q)等价．
证明：(P?(Q??R))??P?Q
?? P?(Q??R))??P?Q ??P?Q
??（P??Q）
2．试证明(?x)(P(x) ?R(x))?(?x)P(x) ? (?x)R(x)．
证明：（1）?x(A(x) ?B(x)) P
（2）A（c）?B(c) ES(1) 公式 A ?B?A A ?B?B （3）A(c) T(2)
(4) ?x(A(x) EG(3)
(5) B(c) T(2) 公式 A ?B?A A ?B?B (6) ?xB(x) EG(5)
(7) (?x)A(x) ? (?x)B(x) T(4)(6) 公式 A ?B?A A ?B?B
电大离散数学作业答案3-5-7合集
