离散数学形成性考核作业9参考答案

离散数学作业9

姓 名： 学 号： 得 分： 教师签名： 离散数学数理逻辑部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。并在09任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题

1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( B )．

A．Q?P B．P?Q C．P?Q D．?P??Q

2．设命题公式G：?P?(Q?R)，则使公式G取真值为1的P，Q，R赋值分别是 (D )．

A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 0

3．下列命题公式成立的为( C )．

A．?P??Q?P?Q B．?B?A ? A?B C．P ? Q ?Q D．?A? (A?B) ?B

4．下列公式 ( C )为重言式．

A．P?Q ??P?Q B．(B?(A?B)) ?(?A?(A?B)) C．?(P?Q)??P??Q D．A??B?A?B 5．命题公式?(P?Q)的析取范式是( A )．

A．P??Q B?P?Q C．?P?Q D．P??Q 6．设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 (D )．

A．??x(C(x)??G(x)) B．??x(C(x)??G(x))

C．??x(C(x)??G(x)) D．??x(C(x)??G(x))

7．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是( B )． A．P(x, y) B．P(x, y)?Q(z) C．R(x, y) D．P(x, y)?R(x, y)

8．谓词公式?xP(x)?(?x?Q(x)???xQ(x))的类型是( A )．

1 / 6

A．永真式 B．永假式 C．非永真的可满足式 D．蕴含式

二、填空题

1．命题公式P?(Q?P)的真值是 1 ．

2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如

果他生病或出差了，我就同意他不参加学习”符号化的结果为 (P∨Q)→ R ．

3．设A，B为任意命题公式，C为重言式，若A?C?B?C，那么A?B是 言重式 式(重言式、矛盾式或可满足式) ．

4．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是 （P∧ Q∧R） ∧（P∧ Q ∧?R） ．

5．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”为 (?χ)(PCχ)→Q(χ)) ．

6．设个体域D＝{a, b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为 (A(a)∨A(b))∨(B(a)∧B(b)) ．

7．设个体域D＝{1, 2, 3, 4}，A(x)为“x小于3”，则谓词公式(?x)A(x) 的真值为 ．

8．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为 χ ．

三、公式翻译题

1．请将语句“今天是天晴”翻译成命题公式．

解: 设P: 今天晴天

则命题公式为P

2．请将语句“如果明天天下雪，我就去市里”翻译成命题公式．

解: 设P:天下雨. Q我明天去市里.

则命题公式为P→Q

3．请将语句“除非你去，否则我不去”翻译成命题公式．

解: 设P:你去.Q我去.

则命题公式为﹁P→﹁Q或Q→P

2 / 6

4．请将语句“我去书店，仅当天不下雨”翻译成命题公式．

解: 设P:我去书店. Q天不下雨

则命题公式为P→Q

5．请将语句 “有人不去工作”翻译成谓词公式．

解: 设P(χ): χ是人. Q(χ): χ去工作 .

则谓词公式为(?χ)(P (χ)∧?Q(χ))

6．请将语句“所有人都努力工作．”翻译成谓词公式．

解: 设P(χ): χ是人. Q(χ): χ努力工作 . 则谓词公式为(?χ)(P (χ)→Q(χ))

四、判断说明题（判断下列各题，并说明理由．）

1．命题公式┐P∧P的真值是1．

2．命题公式┐P∧（P→┐Q）∨P为永真式．

答：正确

┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式 如果P的值为真，则┐P∧（P→┐Q）∨P为真

如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真 也即┐P∧（P→┐Q）∨P为真。所以┐P∧（P→┐Q）∨P是永真式

3 / 6

3．谓词公式?xP(x)?(?yG(x,y)??xP(x))是永真式．

解 ?xP(x)?(?yG(x,y)??xP(x))

???xP(x)?(??yG(x,y)??xP(x)) ?(??xP(x)??xP(x))???yG(x,y) ?1???yG(x,y)?1

4．下面的推理是否正确，请给予说明．

(1) (?x)A(x) ? B(x) 前提引入

(2) A(y) ?B(y) US (1) 答：错

正确的应是：┐A（y）∨B(z)，因为约束变元与自由变元不能混淆。

五．计算题

1．求命题公式?(P?Q)?(P??Q)的主析取范式、主合取范式．

解：（1）?(P?Q)?(P??Q)??(?P?Q)?(?P??Q)

?(P??Q)?(?P??Q)?(P??Q??P)?(P??Q??Q)

?(P??Q) (主析取范式) ?(P?(Q??Q))?((P??P)??Q)

?(P?Q)?(P??Q)?(P??Q)?(?P??Q)

?(P?Q)?(P??Q)?(?P??Q) (主合取范式)

2．求命题公式(P??Q)?(R?Q)的主析取范式、主合取范式．

4 / 6

解：(P?Q)?R??(P?Q)?R

?(?P??Q)?R

??P??Q?R （析取、合取、主合取范式） ?(┐P∧(┐Q∨Q)∧(┐R∨R))∨((┐P∨P)∧┐Q∧(┐R∨R))∨((┐P∨P) ∧(┐Q∨Q)∧R)

?(┐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(y,x,z))，

?z量词的辖域为Q(y,x,z),

?y量词的辖域为R(y,z)．

（2）自由变元为(P(x,y)??zQ(y,x,z))与F(y)中的y，以及R(y,z)中的z 约束变元为(P(x,y)??zQ(y,x,z))中的x与Q(y,x,z)中的z，以及R(y,z)中的y．

4．设个体域为D={a1, a2}，求谓词公式?y?xP(x,y)消去量词后的等值式； 解：?y?xp(x,y)??xp(x,a)??xp(x,a2)?cp(a,a2)?p(a2,a1))?P(a1,a2)?p(a2,a2))

六、证明题

1．试证明 (P?(Q??R))??P?Q与?（P??Q）等值．

5 / 6

证：(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．试证明 ?xA(x)??xB(x)??x(A(x)?B(x))

分析：前提：?xA(x)??xB(x)．

结论：?x(A(x)?B(x))

证：(1) ?xA(x) P

(2) A(a) US(1) (3) ?xB(x) P (4) B(a) US(3) (5) A(a) ? B(a) T(2),(4) I

(6) ?x(A(x)?B(x)) UG(5)

6 / 6

本文来源：https://www.bwwdw.com/article/myt2.html