★ 形成性考核作业 ★
离散数学作业6
姓 名： 桑慧 学 号1914001208707 得 分： 教师签名： 离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业．
要求：学生提交作业有以下三种方式可供选择：
1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．
2. 在线提交word文档
3. 自备答题纸张，将答题过程手工书写，并拍照上传．
一、填空题
1．命题公式P?(Q?P)的真值是 1 ．
2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 P?Q→?R ．
3．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是 (P?Q?R)?(P?Q?R) ．
4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．” 可符号化为 ?x(P(x)?Q(x)) ．
5．设个体域D＝{a, b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为 (A(a)?A(b))?(B(a)?B(b)) ．
6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为 0 ．
7．谓词命题公式(?x)((A(x)?B(x)) ?C(y))中的自由变元为 y ． 8．谓词命题公式(?x)(P(x) ?Q(x) ?R(x，y))中的约束变元为 x ．
三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式．
1
★ 形成性考核作业 ★
解：设P：今天是天晴，则该语句符号化为P；
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P：小王去旅游，Q：小李也去旅游，则该语句符号化为P?Q；
3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
解：设P：他去旅游，Q：他有时间，则该语句符号化为P→Q；
4．将语句“41次列车下午五点开或者六点开．”翻译成命题公式． 解：设P：41次列车下午五点开，Q：41次列车下午六点开，则该语句符号化为P?Q；
5．请将语句 “有人不去工作”翻译成谓词公式．
解：设P(x)：x是人，Q(x)：x不去工作，则谓词公式为(?x)(P(x)?Q(x));
6．请将语句“所有人都努力工作．”翻译成谓词公式．
解：设P(x)：x是人，Q(x)：x努力工作，则谓词公式为(?x)(P(x)→Q(x))；
四、判断说明题（判断下列各题，并说明理由．）
1．命题公式?P?P的真值是1．
答：不正确；
?P?P的真值是0，它是一个永假式，命题公式中的否定律是?P?P=F；
2
★ 形成性考核作业 ★
2．(?x)(P(x)→Q(y)∧R(z))中的约束变元为y．
答：不正确；
该式中的约束变元为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)
答：不正确
(1)中(?)x的辖域仅是A(x)，而不是A(x)→B(x)；
3
★ 形成性考核作业 ★
四．计算题
1． 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式．
解：由于P→Q?R <=> ?P?Q?R
所以合取范式和析取范式都是?P?Q?R 所以主合取范式就是?P?Q?R 所以主析取范式就是
(?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?Q)→(R?Q) <=> ?(P?Q)?(R?Q)
<=> (?P??Q)?(R?Q)
<=> (?P?R?Q)?(?Q?R?Q) <=> (?P?R?Q)?1 <=> ?P?R?Q 即为M4
所以主析取范式为：m0?m1?m2?m3?m5?m6?m7
4
★ 形成性考核作业 ★
3．设谓词公式(?x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z)． （1）试写出量词的辖域；
（2）指出该公式的自由变元和约束变元．
解： （1）
量词?x的辖域为P(x, y)→(?z)Q(y, x, z) 量词?z的辖域为Q(y, x, z) 量词?y的辖域为R(y, x) （2）
P(x, y)中的x是约束变元，y是自由变元
Q(y, x, z)中的x和z是约束变元，y是自由变元 R(y, x)中的x是自由变元，y是约束变元
4．设个体域为D={a1, a2}，求谓词公式?y?xP(x,y)消去量词后的等值式；
解：
?y?xP(x,y)=?xP(x,a1)??xP(x,a2)=(P(a1,a1)?P(a2,a1))?(P(a1,a2)?P(a1,a2))
5
★ 形成性考核作业 ★
五、证明题
1．试证明 (P?(Q??R))??P?Q与? (P??Q)等价． 证明：
(P→(Q??R))??P?Q
<=> (?P?(Q??R))??P?Q <=> (?P?Q??R)??P?Q
<=> (?P??P?Q)?(Q??P?Q)?(?R??P?Q) <=> (?P?Q)?(?P?Q)?(?P?Q??R) <=> ?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
6
离散数学网络课程形成性考核第6次形考任务
