实用标准
离散数学作业7
离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题
1．命题公式P?(Q?P)的真值是 1或T ．
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(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．请将语句“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 文案大全
Q 0 0 1 1 0 0 R 0 1 0 1 0 1 ?（P?Q） R?Q 1 1 0 0 0 0 0 1 1 1 0 1 原式 1 1 1 1 0 1 极小项 极大项 ?P??P??P ?P??Q?R ?P?Q??R ?P?Q?R P??Q?R ?P?Q?R 实用标准
1 1 1 1 0 1 0 0 1 1 1 1 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试地题目及问题详解完整版
