离散数学同步练习-解答

第二章谓词逻辑
一填空题 （1）若个体域是含三个元素的有限域{a，b，c}，则 xA(x) A(a) A(b) A(c)
（2）取全总个体域，令 F(x)：x 为人,G(x)：x 爱看电影。则命题“没有不爱 看电影的人。 ”可符号化为___(x(F(x) G(x)))____。 （3）若个体域是含三个元素的有限域{a，b，c}，则 xA(x) A(a) A(b) A(c) 。
二．判断题 1. 2. 3. 4. 5. 6. 7. 8. 9. 设 A，B 是命题公式，则蕴涵等值式为 ABAB。 命题公式pqr 是析取范式。 陈述句“x + y > 5” 是命题。 110 (p=1,q=1, r=0)是命题公式 (((pq))r)q 的成真赋值。 命题公式 p(pq) 是重言式。 设 A，B 都是合式公式，则 ABB 也是合式公式。 A(BC)( AB)(AC)。 陈述句“我学英语，或者我学法语” 是命题。 命题“如果雪是黑的，那么太阳从西方出”是假命题。 （ ） （ √ ） （ ）
华南理工大学网络教育学院 《离散数学》练习题
第一章命题逻辑
一填空题 （1）设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化 为： (pq) (pq) T 。 。
（2）设A，B都是命题公式，AB，则AB的真值是
（3）设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题： “刘平不但不聪明，而且不用功” 可符号化为： （4）设 A , B 代表任意的命题公式，则蕴涵等值式为 A BA B 。 p q 。
（8）设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。 ” 可符号化为： （9） 对于命题公式 A， B， 当且仅当 并记为 AB。 （10）设：P：我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑步。 ” 可符号化为： （11）设 P , Q 是命题公式，德·摩根律为： （P Q） P Q） 。 （12）设 P：你努力。Q：你失败。在命题逻辑中，命题： “除非你努力，否则 你将失败。 ” 可符号化为： PQ 。 (P Q) 。 A B P Q 。
p T T T T F F F F q T T F F T T F F r T F T F T F T F p→q T T F F T T T T T T T T T F T F pr
（p q）（p r）
T T F F T F T F
（2） （p q）（p r） （pq）（p r） ((pq)p )((pq)r) ((pp ) (qp))((pr) (qr)) (qp)(pr) (qr)
(1 ) 如果天气好，那么我去散步。 (3 ) x=3。
在上面句子中 13．
设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成 （4） 。
绩也很好。 ”在命题逻辑中可符号化为 （1）P Q （3）P Q
（2）P Q （4）P Q
四、解答题 1．设命题公式为（pq）（qp） 。 （1）求此命题公式的真值表； （2）给出它的析取范式；
﹁P∨（﹁﹁Q∧﹁R）∨S ﹁P∨（Q∧﹁R）∨S
5．设命题公式为（P （P Q） ） Q。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （1）
P T T F F Q T F T F P→Q T F T T P ∧ （P→Q） T F F F
（P （P Q） ） Q
(2 ) 在实数范围内，x+y〈3。 (3 ) 请回答这个问题！ (4 ) 明天下午有课吗？ 在上面句子中，是命题的只有 (1 ) 。 (4 ) 。
3．命题公式 A 与 B 是等值的，是指 （1） A 与 B 有相同的命题变元 （2） AB 是可满足式 （3） AB 为重言式 （4） AB 为重言式 4．(1 ) 雪是黑色的。 (2 ) 这朵花多好看呀！ 。 (3 ) 请回答这个问题！ (4 ) 明天下午有会吗？ 在上面句子中，是命题的是 (1 )
（4）取全总个体域，令 M(x)：x 是人,G(y)：y 是花, H(x,y)：x 喜欢 y。则命 题 “有些人喜欢所有的花。 ” 可符号化为 x(M(x)(y(G(y) H(x,y))))。 （5）取个体域为全体人的集合。令 F(x)：x 在广州工作,G(x)：x 是广州人。 在一阶逻辑中，命题“在广州工作的人未必都是广州人。 ”可符号化为 _______﹁x(F(x) G(x))_____。 （6）P(x)：x 是学生，Q(x)：x 要参加考试。在谓词逻辑中，命题： “每个学生都要参加考试” 可符号化为： x(P(x) Q(x)) 。
（2） 解： （ （P Q）P） Q ﹁（ （P Q）P）∨Q （﹁（P Q）∨（﹁﹁P） ）∨Q ﹁P∨﹁Q）∨P∨Q T 7．用直接证法证明 前提：P Q，P R，Q S 结论：S∨ R 证明： 1）P∨Q 2） ﹁P→Q 3）Q→S 4）﹁P→S 5）﹁S→P 6）P→R 7）﹁S→R 8）S∨R P T P T T P T T
（1）
p T T F F q T F T F ﹁p F F T T ﹁p→q T T T F q→﹁p F T T T
（pq）（qp）
F T T T
（2） （pq）（qp） ﹁（pq）∨（qp） ﹁（p∨q）∨（q∨p） （﹁p∧﹁q）∨q∨p
ቤተ መጻሕፍቲ ባይዱ
2．设命题公式为（p q）（p r） 。 （1）求此命题公式的真值表； （2）给出它的析取范式； （1）
（2） （P （Q R） ） （4） Q R （2） 中国人民是伟大的。 （4） 计算机机房有空位吗？ （2） 。
11．
设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。 ” 在命题逻辑中可符号化为 （3） 。
（1）P Q （3）P Q 12．
（2）P Q （4）P Q (2 ) 天气多好呀！ (4 ) 明天下午有会吗？ (1 ) 是命题。
1）E 2）3）I 4）E 5）6）I 7）E
8．用直接证法证明 前提：P (Q R)，S Q，P，S。 结论：R 证明： 1）P (Q R) 2） P 3）(Q R) 4）S Q 5）S 6） Q 7）R P P T 2）3）I P P T 4）5）I T 3）6）E
（ √ ） （ ）
（ √ ）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入 下列叙述中的 内。
1．设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。 ” 可符号化为 （1）PQ （2）Q P （3） Q P （4）Q P 2．(1 ) 明年国庆节是晴天。 （2） 。
（7）M(x)：x 是人，B(x)：x 勇敢。则命题“有人勇敢，但不是所有的人都勇 敢”谓词符号化为 ____x(M(x) B(x)) ﹁x(M(x) B(x))_______。 （8）P(x)：x 是人，M(x)：x 聪明。则命题“尽管有人聪明，但不是一切人都 聪明”谓词符号化为 ______x(P(x) M(x)) ﹁x(P(x) M(x))___。 （9）I(x)：x 是实数，R(x)：x 是正数，N(x)：x 是负数。在谓词逻辑中，命题： “任何实数或是正的或是负的”可符号化为： x(I(x) (R(x) N(x)) 。 （10）P(x)：x 是学生，Q(x)：x 要参加考试。在谓词逻辑中，命题： “每个学生都要参加考试” 可符号化为： x(P(x) Q(x)) 。
（5）设，p：径一事；q：长一智。在命题逻辑中，命题： “不径一事，不长一智。 ” 可符号化为： pq 。
（6）设 A , B 代表任意的命题公式，则德 摩根律为 （A B） A B） 。
“选小王或小李中的 （7）设，p：选小王当班长；q：选小李当班长。则命题： 一人当班长。 ” 可符号化为： (pq) (pq) 。
（11）令 M(x)：x 是大学生,P(y)：y 是运动员, H(x, y)：x 钦佩 y。则命题“有 些大学生不钦佩所有运动员。 ” 可 符 号 化 为 ____x(M(x)(y(P(y) H(x,y)))___。
二．判断题 1. 设 A， B 都是谓词公式， 则x AB 也是谓词公式。 （ √ ）
是重言式时， 称“A 蕴含 B”，
（13）设 p：小王是 100 米赛跑冠军。q：小王是 400 米赛跑冠军。在命题逻 辑中，命题： “小王是 100 米或 400 米赛跑冠军。 ” 可符号化为： p q 。 AC 为一重言式
（14）设 A，C 为两个命题公式，当且仅当 时，称 C 可由 A 逻辑地推出。
（2）P Q （4）Q P
8．设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。 ” 可符号化为 （1）PQ （3） Q P 9．下列式子是合式公式的是 （1） （P Q） （3） （P Q） 10． （1）1＋101＝110 （3） 全体起立！ 在上面句子中，是命题的是 （2） （1） （2）Q P （4）Q P 。
3．设命题公式为 ( Q （P Q）) P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式；
(1)
P T T F F Q T F T F ﹁Q F T F T P→Q T F T T ﹁P F F T T ﹁Q ∧ （P→Q） F F F T (﹁Q∧（P→Q）)→﹁P T T T T
(2) 解：( Q （P Q）) P ( Q （﹁P∨Q） ） P ﹁( Q （﹁P∨Q） ）∨ P （﹁ Q ∨﹁（﹁P∨Q） ）∨ P Q ∨（P﹁Q）∨ P
4．完成下列问题 求命题公式（P∧（Q→R） ）→S 的析取范式。 解： （P∧（Q→R） ）→S （P∧（﹁Q∨R） ）→S ﹁（P∧（﹁Q∨R） ）∨S （﹁P∨﹁（﹁Q∨R） ）∨S
T T T T
（2） 解： （P∧（P→Q） ）→Q （P∧（﹁P∨Q） ）→Q ﹁（P∧（﹁P∨Q） ）∨Q （﹁P∨﹁（﹁P∨Q） ）∨Q ﹁P∨（﹁﹁P∧﹁Q）∨Q ﹁P∨（P∧﹁Q）∨Q
6．设命题公式为（ （P Q）P） Q。 （1）求此命题公式的真值表； （2）给出它的析取范式； （1） P Q P∨Q T T T F F F F T T T F T ﹁P F F T T （P∨Q）∧﹁P F F F T （ （P∨Q）∧﹁P）→Q T T T T
（ √ ） （ ） （ √） （ ）
（√ ） （ （ （ ） ） ）
10. “请不要随地吐痰！ ” 是命题。 11. P Q P Q 。 12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 13. 命题公式（PQ）（RT）是析取范式。 14. 命题公式 (PQ) R (PQ) 是析取范式。
。
5．设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就 乘公共汽车上班。 ” 可符号化为 （1）QP （2）P Q （3） Q P （4）Q P 6．设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。 ” 在命题逻辑中可符号化为 （1）QP （3） P Q 7．(1 ) 现在开会吗？ (2 ) 在实数范围内，x+y 5。 (3 ) 这朵花多好看呀！ (4 ) 离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有 (4 ) 。 （3） 。 （2） 。