一、单项选择题（共 10 道试题，共 100 分
离散数学作业6
姓 名： 学 号： 得 分： 教师签名： 离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业．
要求：学生提交作业有以下三种方式可供选择：
1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．
2. 在线提交word文档
3. 自备答题纸张，将答题过程手工书写，并拍照上传．
一、填空题
1．命题公式P?(Q?P)的真值是 1或T ．
2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如
果他生病或出差了，我就同意他不参加学习”符号化的结果为 P∨Q→R
． 3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 (PQ┐R) ∨(PQR)
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”，则谓词公式(真值为 0 ． 7．谓词命题公式(y ．
8．谓词命题公式(x ．
x)A(x) 的
x)((A(x)B(x)) C(y))中的自由变元为 x)(P(x) Q(x) R(x，y))中的约束变元为
页脚内容
1
一、单项选择题（共 10 道试题，共 100 分
三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式．
解：设P：今天是天晴 则该语句符号化为 P
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
解：设P：小王去旅游，Q：小李也去旅游 则该语句符号化为 P∧Q
3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
解：设P：他去旅游 Q：他有时间 则该语句符号化为 P→Q
4．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．
解：命题P：41次列车下午5点开； 命题Q：41次列车下午6点开； P或Q.
5．请将语句 “有人不去工作”翻译成谓词公式．
解：设P(x)：x是人 Q(x)：x不去工作 则谓词公式为 (?x)(P(x)∧Q(x))
6．请将语句“所有人都努力工作．”翻译成谓词公式．
解：设P(x)：x是人 Q(x)：x努力工作
页脚内容
2
一、单项选择题（共 10 道试题，共 100 分
则谓词公式为 (?x)(P(x) →Q(x))
四、判断说明题（判断下列各题，并说明理由．） 1．命题公式
解：不正确，┐P∧P的真值是0，它是一个永假式，命题公式中的否定律
就是┐P∧P=F
2．(
解：不正确。该式中的约束变元为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）。
4．下面的推理是否正确，请给予说明．
(1) (x)A(x) B(x) 前提引入 (2) A(y) B(y) US (1)
解：不正确，(1)中()x的辖域仅是A(x)，而不是A(x) B(x)。
PP的真值是1．
x)(P(x)→Q(y)∧R(z))中的约束变元为y．
页脚内容
3
一、单项选择题（共 10 道试题，共 100 分
四．计算题 1． 求P
解：┐P
QR的析取范式，合取范式、主析取范式，主合取范式． (Q∨R）= ┐P
Q∨R
Q∨R
所以合取范式和析取范式都是┐P
所以主合取范式就是┐P
所以主析取范式就是(R) (PQ R) (P
2．求命题公式(PQ∨R
PQ Q R) R) ( (PQPQ R) (PQ R) (PQ R)
Q)(RQ) 的主析取范式、主合取范式．
解：(PQ)(RQ)= (PQ) (RQ)= (PQ) (RQ) 其中(PQ)= (PQ) (RR)= (PQ R) (PQ R) 其中(RQ)= (RQ) (PP)= (PQ R) (PQ R) 所以原式=(PQ R) (PQ R) (PQ R) (PQ R)
=(PQ R) ( = (PQ R) 这就是主析取范式
PQ R) (PQ R)
(PQ R) (PQ R)=m2m3m7
(
所以主合取范式为M0 M1 M4 M5 M6 可写为(PQR) (PQR) (PPQR)
QR) (PQR)
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)
页脚内容
4
一、单项选择题（共 10 道试题，共 100 分
量词 量词
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}，求谓词公式yxP(x,y)消去量词后的等值式；
解：yxP(x,y)= xP(x, a1) xP(x, a2)
=( P(a1, a1) P(a2, a1)) ( P(a1, a2) P(a1, a2))
五、证明题 1．试证明 (P(QR))PQ与 (PQ)等价．
证明：(P(QR))PQ(P(QR))PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律）
2．试证明：┐（A∧┐B）∧（┐B∨C）∧┐C
证明：┐（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．
页脚内容
5
相关推荐：
loading