离散数学作业11_谓词逻辑答案

谓词逻辑习题1. 将下列命题用谓词符号化。

（1）小王学过英语和法语。

（2）2大于3仅当2大于4。

（3）3不是偶数。

（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。

解：(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ⌝ (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨(5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ⌝→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。

（1）))()((y Q x P y x ∧∃∀ （2）))()((y Q x P y x ∨∀∀（3）)()(y yQ x xP ∀→∀（4）))()((y yQ y x P x ∃→∀，解：(1) 中))()(()(y Q x P y x A ∧∃=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧∃=，因此))()(())()((y Q y P y y Q x P y x ∧∃∧∃∀ ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧∃ ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧∃∀（2）中))()(()(y Q x P y x A ∨∀=，它对y 不是自由的，故不能用UI 规则，然而，对)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨∀，这时用UI 规则，可得：))()((y Q x P y x ∨∀∀ ))()((z Q x P z x ∨∀∀⇔ ))()((z Q x P z ∨∀ （3）略 （4）略3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。

谓词逻辑复习题答案一、选择题1. 在谓词逻辑中，以下哪个符号表示“或”？A. ∧B. ∨C. →D. ¬答案：B2. 谓词逻辑中的量词“∀”代表什么含义？A. 存在B. 全部C. 任意D. 否定答案：B3. 下列哪个表达式表示“所有的x都满足P(x)”？A. ∃x P(x)B. ∀x P(x)C. ¬∃x ¬P(x)D. ¬∀x ¬P(x)答案：B4. 谓词逻辑中的否定连接词是哪一个？A. ∧B. ∨C. ¬D. →答案：C5. 如果P(x)表示“x是学生”，Q(x)表示“x是老师”，以下哪个表达式表示“x既是学生又是老师”？A. P(x) ∧ Q(x)B. P(x) ∨ Q(x)C. P(x) → Q(x)D. ¬P(x) ∧ ¬Q(x)答案：A二、填空题6. 谓词逻辑中，表达式“∀x (P(x) ∨ Q(x))”可以解释为“对于任意的x，x满足P或Q”。

请将该表达式转换为自然语言：______________________。

答案：对于任意的x，x是P或者x是Q。

7. 如果P(x)表示“x是大的”，Q(x)表示“x是圆的”，那么表达式“∃x (P(x) ∧ Q(x))”可以解释为“存在某个x，x既大又圆”。

请将该表达式转换为自然语言：______________________。

答案：存在某个x，x既大又圆。

8. 表达式“¬∀x P(x)”可以解释为“不是所有的x都满足P(x)”。

请将该表达式转换为自然语言：______________________。

答案：不是所有的x都满足P。

三、简答题9. 解释谓词逻辑中量词“∃”和“∀”的区别。

答案：量词“∃”表示存在，即至少有一个元素满足某个性质或条件；而量词“∀”表示全部，即所有元素都满足某个性质或条件。

10. 给出一个例子，说明谓词逻辑中的“蕴含”如何使用。

离散数学习题答案习题一1. 判断下列句子是否为命题？若是命题说明是真命题还是假命题。

（1）3是正数吗？（2）x＋1=0。

（3）请穿上外衣。

（4）2＋1＝0。

（5）任一个实数的平方都是正实数。

（6）不存在最大素数。

（7）明天我去看电影。

（8）9＋5≤12。

（9）实践出真知。

（10）如果我掌握了英语、法语，那么学习其他欧洲语言就容易多了。

解：（1）、（2）、（3）不是命题。

（4）、（8）是假命题。

（5）、（6）、（9）、（10）是真命题。

（7）是命题，只是现在无法确定真值。

2. 设P表示命题“天下雪”，Q表示命题“我将去书店”，R表示命题“我有时间”，以符号形式写出下列命题。

（1）如果天不下雪并且我有时间，那么我将去书店。

（2）我将去书店，仅当我有时间。

（3）天不下雪。

（4）天下雪，我将不去书店。

解：（1）（┐P∧R）→Q。

（2）Q→R。

（3）┐P。

（4）P→┐Q。

3. 将下列命题符号化。

（1）王皓球打得好，歌也唱得好。

（2）我一边看书，一边听音乐。

（3）老张和老李都是球迷。

（4）只要努力学习，成绩会好的。

（5）只有休息好，才能工作好。

（6）如果a和b是偶数，那么a+b也是偶数。

（7）我们不能既游泳又跑步。

（8）我反悔，仅当太阳从西边出来。

（9）如果f(x)在点x0处可导，则f(x)在点x0处可微。

反之亦然。

（10）如果张老师和李老师都不讲这门课，那么王老师就讲这门课。

（11）四边形ABCD是平行四边形，当且仅当ABCD的对边平行。

（12）或者你没有给我写信，或者信在途中丢失了。

解：（1）P：王皓球打得好，Q：王皓歌唱得好。

原命题可符号化：P∧Q。

（2）P：我看书，Q：我听音乐。

原命题可符号化：P∧Q。

（3）P：老张是球迷，Q：老李是球迷。

原命题可符号化：P∧Q。

（4）P：努力学习，Q：成绩会好。

原命题可符号化：P→Q。

（5）P：休息好，Q：工作好。

原命题可符号化：Q→P。

（6）P：a是偶数，Q：b是偶数，R：a+b是偶数。

习题11.11． 若n 个顶点的简单无向图G 中至少有2个孤立点，则结论自然成立；若G 中只有一个孤立点，而2n ≥，则G 中至少有3个顶点，其中至少有2个非孤立点，可不考虑孤立点；若G 中无孤立点，则G 中n 个顶点度数均不小于1.现设G 中n 个顶点的度数均不小于1，又G 为简单图，故所有顶点的度数均不大于n-1，即n 个顶点的度数的取值只能是1，2，…，n-1,由鸽舍原理知，结论成立。

2． 设G 有x 个顶点，则92)6(36)deg(122>⇒⨯-+⨯≤=⨯∑∈x x v Vv3． m n k n k n n k n v m k k k Vv 2)1()1()()deg(2-+=⇒+⨯-+⨯==∑∈4． ∑∈∈⨯≤=≤∈⨯Vv V v v n v m V v v n })max{deg()deg(2})deg(min{故所证不等式成立。

5.（1）非同构的4个顶点的自补图只有一个；非同构的5个顶点的自补图有2个（2）G 为自补图⇒G 与G 的边数相同，设均为m ，又G 与G 的边数之和为n K 的边数2)1(-n n ，即2)1(-n n =2m ，亦即)1(-n n =4m ，故n 为4的倍数，即n=4k ，或n-1为4的倍数，即n=4k+1，+∈I k6.（1）<0,1,1,2,3,3>,<3,3,3,3>均为可图解的，其对应图为<1,3,3,3>非可图解，否则，设3)deg()deg()deg(,1)deg(4321====v v v v ，由于要构成无向简单图，故，1v ，2v ，3v ，4v 之间必定有边关联，这与1)deg(1=v 矛盾，< 2，3，4，4，5>,<2,2,4>非可图解，以为简单图中所有顶点的度数多为n-1。

<1,2,2,3,4,5>z 中有奇数个，故非可图解。

（2）充分性：<1d 2-,1d 3-,…, 1d 1d -,1d 1d 1-+,2d 1d +,…,n d >可图解⇒添加度数为1d 的顶度，与度数为1d 2-,1d 3-,…, 1d 1d -,1d 1d 1-+的顶点相邻⇒<1d ,2d ,…, n d >可图解。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

《失散数学》题库与答案一、选择或填空（数理逻辑部分）1、以下哪些公式为永真包括式？( A )(1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=>P答：在第三章里面有公式（1）是附加律，（ 4）能够由第二章的包括等值式求出（注意与吸取律差异）2、以下公式中哪些是永真式？()(1)( ┐P Q)→(Q→R) (2)P →(Q→Q) (3)(P Q)→P (4)P→(P Q)答：（ 2），（3），（4）可用包括等值式证明3、设有以下公式，请问哪几个是永真蕴涵式?()(1)P=>P Q (2) P Q=>P (3) P Q=>P Q(4)P (P →Q)=>Q (5)(P→Q)=>P (6)P (P Q)=>P答：（2）是第三章的化简律，（3）近似附加律，（4）是假言推理，（ 3），（5），（6）都可以用包括等值式来证明出是永真包括式4、公式x((A(x)B(y，x))z C(y ，z)) D(x) 中，自由变元是 ( )，拘束变元是 ( )。

答： x,y, x,z（察看定义在公式x A 和 x A 中，称x为指导变元，A为量词的辖域。

在x A 和 x A 的辖域中， x 的所有出现都称为拘束出现，即称x 为拘束变元， A 中不是拘束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和 z C(y ，z) 中 y 为自由变元， x 和 z 为拘束变元，在 D(x) 中 x 为自由变元）5、判断以下语句可否是命题。

若是，给出命题的真值。

()(1)北京是中华人民共和国的国都。

(2)陕西师大是一座工厂。

(3)你喜欢唱歌吗？(4)若 7+8＞18，则三角形有 4 条边。

(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是（命题必定满足是陈述句，不能够是疑问句也许祈使句。

谓词逻辑习题1. 将下列命题用谓词符号化。

（1）小王学过英语和法语。

（2）2大于3仅当2大于4。

（3）3不是偶数。

（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。

解：(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ⌝ (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨(5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ⌝→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。

（1）))()((y Q x P y x ∧∃∀ （2）))()((y Q x P y x ∨∀∀（3）)()(y yQ x xP ∀→∀（4）))()((y yQ y x P x ∃→∀，解：(1) 中))()(()(y Q x P y x A ∧∃=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧∃=，因此))()(())()((y Q y P y y Q x P y x ∧∃∧∃∀ ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧∃ ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧∃∀（2）中))()(()(y Q x P y x A ∨∀=，它对y 不是自由的，故不能用UI 规则，然而，对)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨∀，这时用UI 规则，可得：))()((y Q x P y x ∨∀∀ ))()((z Q x P z x ∨∀∀⇔ ))()((z Q x P z ∨∀ （3）略 （4）略3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。