离散数学第二章作业

第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式. 等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律 真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔¬( (p→q)∧(q→p) )等价等值式⇔¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔ (p∨q)→(¬q∨p)蕴含等值式⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔ (¬p∧¬q)∨¬q ∨ p结合律⇔ p∨¬q吸收律, 交换律⇔ M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设 (¬p→q)∧(q∧r) =1, 则¬p→q=1且 q∧r=1,解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(p q)(q r) 蕴含等值式(p q r)(q r) 对分配律, 幂等律(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配律m7 m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((p q)(q p))r 等价等值式((p q)(q p))r 蕴含等值式(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT)(p q r)(q p r) 对分配律, 矛盾律, 同一律M0 M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(p q)(q r) 蕴含等值式(p q)(p r)(q r) 对分配律, 矛盾律, 同一律(p q r)(p q r) (p q r)(p q r)(p q r)(p q r)m1 m0 m3 m7主合取范式为M2 M4 M5 M6.解逻辑方程法设 (p q) (q r) = 1, 则p q =1 且 q r =1.前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m0m1m3m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q) (q r) 真值表如下:p q r(p q) (qr)00010011010001111000101011001111013724 M5 M6.。

第二章习题1 填空题(每小题5，共30分)⑴设A 为含命题变项p、q、r 的重言式,则公式A Ú((p∧q)®r)的类型为__________⑵设B为含命题变项p、q、r 的矛盾式，则公式B∧((p«q)®r)的类型为_________⑶设p、q为命题变项，则有(Øp«q)的成真赋值为________⑷设p、q为真命题，r、s为假命题，则复合命题(p«r)«(Øq®s)的真值为_________⑸矛盾式的主析取范式为_________⑹设公式A含命题变项p、q、r，又已知A的主合取范式为M O∧M2∧M3∧M5,则A的主析取范式为_________2 用等值演算法求公式的主析取范式或主合取范式(每小题10，共30分)⑴求公式p®((q∧r)∧(pÚ(Øq∧Ør)))的主析取范式⑵求公式Ø(Ø(p®q)) Ú(Øq®Øp)的主取合范式⑶求公式((pÚq) ∧(p®q)) «(q®p)的主析取范式，再由主析取范式求出主合取范3 用真值表求公式(p®q) «r的主析取范式(10分)4 将公式p®(q®r)化成与之等值且仅含{Ø,∧}中的联结词的公式(10分)5 用主析取范式判断Ø(p «q)与((pÚq) ∧Ø (p∧q))是否等值(10分)6 用消解原理证明p∧(ØpÚq) ∧(Ør) ∧(ØpÚØqÚr)是矛盾式(10分)。

-离散数学 专业班级 学号 姓名 第一章 命题逻辑的基本概念一、单项选择题1．下列语句中不是命题的有（ ）.A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗？D.我要努力学习。

2. 下列语句是真命题为( )．A. 1+2=5当且仅当2是偶数B. 如果1+2=3，则2是奇数C. 如果1+2=5，则2是奇数D. 你上网了吗？3. 设命题公式)(r q p∧→⌝,则使公式取真值为1的p ，q ，r 赋值分别是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 4. 命题公式q q p →∨)(为 ( )(A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式5. 设p:我将去市里,q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为为( )q p q p q p p q ⌝∨⌝↔→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ）A. Q P ⌝→ ；B. Q P →⌝；C. P Q ⌝∧⌝ ；D. )(Q P ∧⌝二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化（1）中国有四大发明。

（2）2是有理数。

（3）“请进！”（4）刘红和魏新是同学。

（5）a+b（6）如果买不到飞机票，我哪儿也不去。

（8）侈而惰者贫，而力而俭者富。

（韩非：《韩非子∙显学》）（9）火星上有生命。

（10）这朵玫瑰花多美丽啊！二、将下列命题符号化，其中p:2<1,q:3<2（1）只要2<1，就有3<2。

（2）如果2<1，则3≥2。

（3）只有2<1，才有3≥2。

（4）除非2<1，才有3≥2。

（5）除非2<1，否则3≥2。

（6）2<1仅当3<2。

离散数学专业班级学号姓名三、将下列命题符号化(1)小丽只能从筐里拿一个苹果或一个梨。

离散数学(屈婉玲版)第二章习题答案2.13 设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X≤3，G （X）：X>5,R(X):X≤7。

在I下求下列各式的真值。

（1）∀x(F(x)∧G(x))解：∀x(F(x)∧G(x))⇔(F(-2) ∧G(-2)) ∧(F(3) ∧G(3)) ∧(F(6) ∧G(6))⇔((-2≤3) ∧(-2>5)) ∧((3≤3) ∧(3>5)) ∧((6≤3) ∧(6<5))⇔((1 ∧0))∧((1 ∧0)) ∧((0 ∧0))⇔0∧0∧0⇔0(2) ∀x(R(x)→F(x))∨G(5)解：∀x(R(x)→F(x))∨G(5)⇔(R(-2)→F(-2))∧ (R(3)→F(3))∧ (R(6)→F(6))∨ G(5)⇔((-2≤7) →(-2≤3))∧ (( 3≤7) →(3≤3))∧ (( 6≤7) →(6≤3)) ∨ (5>5)⇔(1 →1)∧ (1 →1)∧ (1→0) ∨ 0⇔1∧ 1∧ 0 ∨ 0⇔0(3)∃x(F(x)∨G(x))解：∃x(F(x)∨G(x))⇔(F(-2) ∨ G(-2)) ∨ (F(3) ∨G(3)) ∨ (F(6) ∨G(6))⇔((-2≤3) ∨ (-2>5)) ∨ ((3≤3) ∨ (3>5)) ∨ ((6≤3) ∨ (6>5))⇔(1 ∨ 0) ∨ (1 ∨ 0) ∨ (0 ∨ 1)⇔1 ∨ 1 ∨ 1⇔12.14 求下列各式的前束范式，要求使用约束变项换名规则。

（1）⌝∃xF(x)→∀yG(x,y)(2) ⌝（∀xF(x,y) ∨∃yG(x,y) ）解：（1）⌝∃xF(x)→∀yG(x,y)⇔⌝∃xF(x)→∀yG(z,y) 代替规则⇔∀x⌝F(x)→∀yG(z,y) 定理2.1（2 ）⇔∃x(⌝F(x)→∀yG(z,y) 定理2.2（2）③⇔∃x∀y(⌝F(x)→G(z,y)) 定理2.2（1）④（2）⌝（∀xF(x,y) ∨∃yG(x,y) ）⇔⌝(∀zF(z,y) ∨∃tG(x,t)) 换名规则⇔⌝(∀zF(z,y) )∧⌝(∃tG(x,t) )⇔∃z⌝F(z,y) ∧∀t⌝G(x,z)⇔∃z (⌝F(z,y) ∧∀t⌝G(x,z))⇔∃z ∀t(⌝F(z,y) ∧⌝G(x,t))2.15 求下列各式的前束范式，要求使用自由变项换名规则。

第二章习题三一、证明如下推理式1、∃xF(x)→∀y((F(y)∨G(y))→R(y))，∃xF(x) ⇒∃xR(x)(1)∃xF(x) 前提条件(2)∃xF(x) →∀y((F(y) ∨G(y)) →R(y)) 前提条件(3)∀y((F(y) ∨G(y)) →R(y)) (1)(2)假言推理(4)F(c) (1)存在量词指定(5)F(c) ∨G(c) (4)及析取的定义(6)(F(c) ∨G(c)) →R(c) (3)全称量词指定(7)R(c) (5)(6)假言推理(8)∃xR(x) (7)存在推广2、∀x(F(x)→(G(a) ∧R(x)))，∃xF(x) ⇒∃x(F(x) ∧R(x))(1)∃xF(x) 前提条件(2)F(c) (1)存在量词指定(3)∀x(F(x)→G(a) ∧R(x))) 前提条件(4)F(c)→G(a)∧R(c)) (3)全称指定，尤其x=c应成立(5)G(a)∧R(c) (2)(4)假言推理或分离原则(6)R(c) (5)与合取的定义(2)(6)与合取的定义(7)F(c)∧R(c)(8)∃x(F(x)∧R(x) (7)存在推广3、∀x(F(x)∨G(x))，¬∃xG(x) ⇒∃xF(x)(1)¬∃xG(x) 前提条件(2)∀x¬G(x) (1)的等值(3)¬G(x0) (2)全称指定，x0为任意变元(4)∀x(F(x) ∨G(x)) 前提条件(4)全称指定为x0(5)(F(x0) ∨G(x0))(6)¬G(x0) →F(x0) (5)等值变换(7)F(x0) (3)(6)分离原则或假言推理(8)∃xF(x) (7)存在推广4、∀x(F(x) ∨G(x))，∀x(¬R(x) ∨¬G(x))，∀xR(x) ⇒∃xF(x)(1)∀x(F(x) ∨G(x)) 前提条件(2)(F(x0) ∨G(x0)) (1)全称指定，x0为任意变元(3)∀x(¬R(x) ∨¬G(x)) 前提条件(4)(¬R(x0) ∨¬G(x0)) (3)全称指定，变元x指定为(2)中确定的变元x0，即是同一个x0(5)∀xR(x) 前提条件(6)R(x0) (5)全称指定，与(2)中的x0为同一个(4)的等值变换(7)R(x0) →¬G(x0)(8)¬G(x0) (6)(7)分离原则或假言推理(9)¬G(x0) → F(x0) (2)的等值变换(10)F(x0) (8)(9)分离原则或假言推理(11)∃xF(x) (10)存在推广。

第2章习题答案1. 解 (1)设F(x)表示“x犯错误”，N(x)表示“x为人”，则此语句符号化为：⌝∃x(N(x)∧⌝F(x))。

(2)设F(x)表示“x是推理”，M(x)表示“x是计算机”，H(x，y)表示“x能由y完成”，则此语句符号化为：⌝∀x(F(x)→∃ y M(y)∧H(x，y))。

(3)设C(x)表示“x是计算机系的学生”，D(x)表示“x学习离散数学”，则此语句符号化为：∀x(C(x)→D(x))。

(4)因原语句与“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任意自然数x，当y 和z都是x的后继时，则有y＝z”的意思相同，所以原语句可符号化为：∀x(N(x)→∃ y(N(y)∧M(x，y)))∧∀x∀y∀z(N(x)∧N(y)∧N(z)→(M(x，y)∧M(x，z)→( y＝z))) 其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。

(5)设S(x，y，z)表示“x＋y＝z”，则此语句符号化为：∀x∀y∃z S(x，y，z)。

(6)设Z(x)表示“x是整数”，S(x，y)表示“xy＝0”，T(x，y)表示“x＝y”，则此语句符号化为：∀x∀y(Z(x)∧Z(y)→(S(x，y)→ T(x，0)∨T(y，0)))。

(7)设E(x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“x＝y”，则此语句符号化为：∀x(E(x)∧P(x)→∀y(E(y)∧P(y)→ S(x，y)))。

(8)设E(x)表示“x是偶数”，O(x)表示“x是奇数”，N(x)表示“x是自然数”，则此语句符号化为：⌝∃x(E(x)∧O(x)∧N(x))。

(9)设R(x)表示“x是实数”，Q(x)表示“x是有理数”，Z(x)表示“x是整数”，则此语句符号化为：∃x(R(x)∧Q(x)∧⌝Z(x))。

(10)设R(x)表示“x是实数”，Q(x，y)表示“y大于x”，则此语句符号化为：∀x(R(x)→∃⌝y(R(y)∧Q(x，y)))。

离散数学答案第二章习题解答第二章谓词逻辑习题与解答1、将下列命题符号化:(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。

(3) 至少有一种金属可以溶解在所有液体中。

(4) 每个人都有自己喜欢的职业。

(5) 有些职业就是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。

令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。

(2) 取论域为所有物质的集合。

令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y xD y L y x M x ∧?→?。

(3) 论域与谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。

(4) 取论域为所有事物的集合。

令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?(5)论域与谓词与(4)同。

“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。

2、取论域为正整数集,用函数+(加法),?(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不就是偶数。

解先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =??。

第二章 谓词逻辑习题与解答1、 将下列命题符号化:(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。

(3) 至少有一种金属可以溶解在所有液体中。

(4) 每个人都有自己喜欢的职业。

(5) 有些职业就是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。

令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧∃→∀。

(2) 取论域为所有物质的集合。

令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧∃→∀。

(3) 论域与谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →∀∧∃。

(4) 取论域为所有事物的集合。

令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧∃→∀(5)论域与谓词与(4)同。

“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →∀∧∃。

2、 取论域为正整数集,用函数+(加法),•(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不就是偶数。

解 先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =•∃。

x x J :)(就是奇数,)(x J 可表示为)2(x v v =•⌝∃。

国家开放大学电大本科《离散数学》网络课形考任务2作业及答案此任务2 g选择题题目1 无向完全图K4是()、选择一项：A、树 B、欧拉图 C、汉密尔顿图 D、非平面图题目2 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为()、选择一项： A、4 B、8 C、3 D、5 题目3 设无向图G的邻接矩阵为 011111 0 0111 0 0 0 011 0 011 01 0 则G 的边数为( 选择一项： A、7 B、14 C、6 D、1 题目4 如图一所示，以下说法正确的是()、选择一项： A、 ((a, e), (b, c)｝是边割集 B、｛(a, e)｝是边割集 C、｛（d, e）｝是边割集 D、（（a, e）｝是割边题目5 以下结论正确的是（）、选择一项： A、有n个结点n-l条边的无向图都是树B、无向完全图都是平面图 C、树的每条边都是割边 D、无向完全图都是欧拉图题目6 若G是一个欧拉图，则G一定是（）、选择一项： A、汉密尔顿图 B、连通图 C、平面图 D、对偶图题目7 设图G=, vGV,则下列结论成立的是（）、选择一项：A、云 d做、）=2|% B、2>“ = |司 w C、 deg（v）=2|S| D、deg（v）=|E| 题目8 图G如图三所示，以下说法正确的是（）、选择一项： A、（b, d｝是点割集 B、｛c｝是点割集 C、｛b, c｝是点割集 D、 a是割点题目9 设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是（）、选择一项： (a)是费连通的 B、 (d)是强连通的 C、 (c)是强连通的D、 (b)是强连通的题目10 设有向图(a)、(b)、(c)与(d)如图六所示，则下列结论成立的是()、选择一项： A、 (b)只是弱连通的 B、 (c)只是弱连通的 C、 (a)只是弱连通的 D、 (d)只是弱连通的判断逝题目11 设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去4条边后使之变成树、()选择一项：对错题目12 汉密尔顿图一定是欧拉图、()选择一项：对错题目13 设连通平面图G的结点数为5,边数为6,则面数为4、()选择一项：对错题目14 设G是一个有7个结点16条边的连通图，则G为平面图、()选择一项：对错题目15 如图八所示的图G存在一条欧拉回路、()选择一项：对错题目16 设图G如图七所示，则图G的点割集是{f}、()选择一项：对错题目172>瞒)=2圜设G是一个图，结点集合为V,边集合为E,则代衫()选择一项：对错题目18 设图G是有5个结点的连通图，结点度数总和为10,则可从G中删去6条边后使之变成树、()选择一项：对错题目19 如图九所示的图G不是欧拉图而是汉密尔顿图、()选择一项：对错题目20 若图 G=,其中 V=( a, b, c, d }, E={ (a, b), (a, d), (b, c), (b, d)},则该图中的割边为(b, c)、()选择一项：对。

第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。

(xxF(2)在两个个体域中都解释为)(x∃，在（a）(b)中均为真命题。

xG4. 在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数H(x): x是有理数命题符号化为: ))xx∧⌝⌝∃F()((xH(2)F(x): x是北京卖菜的人H(x): x是外地人命题符号化为: ))xFHx→⌝∀(x)((5. 在一阶逻辑将下列命题符号化:(1) 火车都比轮船快.(3) 不存在比所有火车都快的汽车.解:(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快命题符号化为: ))FxGyx→∀∀y∧))(,()x((y(H(2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快命题符号化为: )))yxFGy→⌝∃∧∀x()(,H(x)(y(9.给定解释I如下:(a) 个体域D为实数集合R.(b) D中特定元素=0.(c) 特定函数(x,y)=x y,x,y D∈.(d) 特定谓词(x,y):x=y,(x,y):x<y,x,y D∈.说明下列公式在I下的含义,并指出各公式的真值:(1)))yGx⌝→∀∀yx,)(((y,xF(2)))xyafF∀x→yG∀)x,),((y,((答:(1) 对于任意两个实数x,y,如果x<y, 那么x≠y. 真值1.(2) 对于任意两个实数x,y,如果x-y=0, 那么x<y. 真值0.10. 给定解释I如下：（a）个体域D=N(N为自然数集合).（b） D中特定元素=2.（c） D上函数=x+y,(x,y)=xy.（d） D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1)xF(g(x,a),x)(2)x y(F(f(x,a),y)→F(f(y,a),x)答:(1) 对于任意自然数x, 都有2x=x, 真值0.(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判断下列各式的类型:(1)(3) yF(x,y).解:(1)因为1q→p→ppp为永真式；q⇔))((⇔∨∨⌝⌝所以为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数x存在实数y使x+y=5，前件真；后件为存在实数x对任意实数y都有x+y=5，后件假，]此时为假命题再取解释I个体域为自然数N，F(x,y)：:x+y=5所以,前件为任意自然数x存在自然数y使x+y=5，前件假。

习题答案(从本章起，习题答案由jhju提供，晓津补充。

如有问题或不同意见，欢迎到分课论坛发表)1、用谓词表达式写出下列命题a)小张不是研究生；解：设A(x)：x是研究生；a:小张；|A(a)。

b)他是跳高或篮球运动员；解：设A(x):x是跳高运动员；B(x):x是篮球运动员；a: 他；A(a)∨B(a) 。

c)晓莉非常聪明和能干；解：设 A(x):x非常聪明；B(x):x能干；l: 晓莉；A(l)∧B(l)d)若m是奇数则2m是偶数解：设 A(x): x是奇数B(y):y是偶数m:某数A(m)→ B(2m)2、将下列命题符号化并要分析到个体词及谓词a)长江流经四川省；解：B(x,y):x流经y；a:长江 b:四川省B(a,b)。

个体词：长江、四川省谓词：流经b)这架新式歼击机击沉了那艘老式快艇解：设A(x,y):x击沉了ya:新式歼击机 b:老式快艇A(a,b).个体词：歼击机、快艇谓词：击沉3、用谓词表达式符号化下列命题。

那位戴眼镜穿西服的大学生在看一本英文杂志。

解：设：A(x): x戴眼镜；B(x): x穿西服；C(x): x在看英文杂志；a: 那位大学生A(a)∧B(a)∧C(a)这个表达式的含义就是一个陈述句：那位大学生戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。

个体词是：那位大学生。

谓词有：戴眼镜、穿西服、在看英文杂志。

习题答案(从本章起，习题答案由jhju提供，晓津补充。

如有问题或不同意见，欢迎到分课论坛发表)题号：1 2 3 4 5 61、对下列公式指出约束变元和自由变元，并指明量词的辖域。

a,(x)(P(x)—→Q(x))∧(x)R(x,y)；(x)的指导变元是x,其辖域是(P(x)—→Q(x))(x)的指导变元是x,其辖域是R(x,y)对于(x)来说，x是约束出现，y则是自由出现。

b,(x)(y)(P(x)∨Q(y))—→(x)(R(x)∧S(z))；(x)和(y)的指导变元是x,y,其辖域是(P(x)∨Q(y))(x)的指导变元是x,其辖域是(R(x)∧S(z))x,y在辖域是约束出现，z则是自由出现(注，教材中本题原来是多一个括号的(或者说少一个)，现在jhju将它改成这个样子，请大家仔细在书中找BUG)c,(x)(y)(P(x,y)∧Q(z))(x)(y)的指导变元是x,y,自由变元是z,其辖域是P(x,y)∧Q(z)2、在下列公式中，对约束变元进行换名，对自由变量进行代入。

第二章习题二解答1、求证∀x∀y(P(x)→Q(y))⇔∃xP(x)→∀yQ(y)证：∀x∀y (P(x)→Q(y))⇔∀x∀y (¬P(x)∨Q(y)) 条件式等值式⇔∀x(¬P(x)∨∀yQ(y)) 量词辖域的扩充收缩律⇔∀x¬P(x)∨∀yQ(y) 量词辖域的扩充收缩律⇔¬∃xP(x)∨∀yQ(y) 量词的德摩律⇔∃xP(x)→∀yQ(y) 条件式等值式2、把下列各式转换为前束范式(1) ∃x(¬ (∃yP(x,y)→(∃zQ(z)→R(x)) ) )⇔∃x(¬ (¬∃yP(x,y)∨(¬∃zQ(z)∨R(x)) ) 条件式等值式⇔∃x ( (∃yP(x,y)∧(∃zQ(z)∧¬R(x)) ) 德摩律⇔∃x∃y（P(x,y)∧(∃zQ(z)∧¬R(x))) 量词辖域的扩充收缩律⇔∃x∃y (P(x,y)∧∃z (Q(z)∧¬R(x)) ) 量词辖域的扩充收缩律⇔∃x∃y∃z (P(x,y)∧Q(z)∧¬R(x)) 量词辖域的扩充收缩律(2) ∀x∀y((∃zP(x,y,z)∧∃uQ(x,u))→∃vQ(y,v))⇔∀x∀y(¬ (∃zP(x,y,z)∧∃uQ(x,u)) ∨∃vQ(y,v)) 条件式等值式⇔∀x∀y( (¬∃zP(x,y,z) ∨¬∃uQ(x,u)) ∨∃vQ(y,v)) 德摩律⇔∀x∀y( (∀z¬P(x,y,z) ∨∀u¬Q(x,u)) ∨∃vQ(y,v)) 德摩律⇔∀x∀y∀z∀u∃v ( ¬P(x,y,z) ∨¬Q(x,u)∨Q(y,v)) 量词辖域的扩充收缩律(用了三次)(3) ∀xF(x) →∀yP(x,y)⇔∀zF(z) →∀yP(x,y) 约束变元与自由变元同名，故约束变元改名⇔¬∀zF(z)∨∀yP(x,y) 条件式等值式⇔∃z¬F(z)∨∀yP(x,y) 德摩律⇔∃z∀y(¬F(z)∨P(x,y)) 德摩律(4) ∀x(P(x,y)→∃yQ(x,y,z)) 注意约束变元y 与自由变元y 同名⇔∀x(P(x,y)→∃sQ(x,s,z)) 约束变元y改名s⇔∀x(¬P(x,y)∨∃sQ(x,s,z)) 条件式的等值式⇔∀x∃s(¬P(x,y)∨Q(x,s,z)) 量词辖域的扩充收缩律(5) ∀x(P(x,y)↔∃yQ(x,y,z)) 注意约束变元y 与自由变元y 同名⇔∀x(P(x,y)↔∃sQ(x,s,z)) 约束变元y改名s⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃sQ(x,s,z)→P(x,y))) 双条件的等值式⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃tQ(x,t,z)→P(x,y))) 后约束变元s因同名而改名t⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(¬∃tQ(x,t,z)∨P(x,y))) 条件式等值式⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(∀t¬Q(x,t,z)∨P(x,y))) 德摩律⇔∀x∃s∀t((¬P(x,y)∨Q(x,s,z))∧(¬Q(x,t,z)∨P(x,y))) 量词辖域的扩充收缩律(用了四次)(6) ∀x(F(x) →G(x,y)) →(∃yH(y) →∃zL(y,z))⇔∀x(F(x) →G(x,y)) →(∃sH(s) →∃zL(y,z)) 约束变元改名⇔¬∀x(¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 条件式等值式⇔∃x(F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 德摩律⇔∃x(F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 否定的否定⇔∃x∀s∃z(F(x)∧¬G(x,y))∨(¬H(s)∨L(y,z)) 量词辖域的扩充收缩律(用了三次)(7) ∃xF(x,y) →(F(x) →¬∀yG(x,y))⇔∃sF(s,y) →(F(x) →¬∀yG(x,y)) 约束变元x改名s⇔∃sF(s,y)→(F(x)→¬∀tG(x,t)) 约束变元y改名t⇔¬∃sF(s,y)∨(¬F(x)∨¬∀tG(x,t)) 条件式等值式⇔∀s¬F(s,y)∨(¬F(x)∨∃t¬G(x,t)) 德摩律⇔∀s∃t(¬F(s,y)∨(¬F(x)∨¬G(x,t)) 量词辖域的扩充收缩律(用了二次) ⇔∀s∃t(¬F(s,y)∨¬F(x)∨¬G(x,t) ) 结合律。

一、单项选择题1、三个结点最多可以构成__________个非同构的无向简单图。

A ．1B ．2C ．3D ．42. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（ ）A. 1,1,1,3，B.3,2,2,3C. 2,2,2,2，D. 1,2,3,43．无向图的关联矩阵中，每行的元素之和为（ ）。

A ．边数的2倍B ．2C ．顶点数D ．顶点的度数4、二部图（偶图）K 2,3是（ ）。

A ．欧拉图B ．哈密顿图C ．非平面图D ．平面图5．3阶无向完全图（K 3）不是以下哪种图？（ ）A ．欧拉图B ．平面图C ．二部图D ．哈密顿图二、填空题1． 一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是_______。

2、无向完全图K 4要成为欧拉图至少要添加_____________条边。

3．完全二部图K 2,3是平面图，它的平面嵌入共有______________个面。

4. 一棵无向树T 有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T 中有_____________片树叶。

三、设无向图G 有12条边，2个4度顶点，其余顶点度数均为3或2。

（1）计算该图最少有多少个顶点？（2）画出一棵具有最少顶点的无向图。

四、以下是具有结点V 1，V 2，V 3，V 4的有向图的邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1001200010100110 （1）画出该图； （2）求长度为2的通路总数和回路总数；（3）该图是否为欧拉图?五、右图是具有四个结点的有向图：（1）写出该图的邻接矩阵、可达矩阵；（2）求长度为2的通路总数。

（3）判断该图为单向连通还是强连通？六、右下图为无向图：（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。

（2）判断该图是否为哈密尔顿图？请说明理由。

（3）判断该图是否为二部图？请说明理由。

七. 图G是一个简单的连通的平面图，顶点数为8为四边形（次数为4），计算平面图G的边数和面数。

第二章习题 1． 填空（1）)(x A ，)(y B （2）))()((x A x C x →∀ （3）))()((y B x A x →∀（4）)),()()((y x H y F x F y x ⌝→∧∀∀ （5）))()((x G x F x ⌝∧∃ （6）T（7）)),(),((z y Q y x P y ∧∀，),(),(z y Q y x P ∧，),(y x P （8）))()((!x P x Q x ∧∃ ))()((!!x P x Q x ∧∃ （9）x y ,和z（10）))()((y R x Q x →∀，))(Z )(Q (x x x ∧∃，))()(R )(Q (x Z x x x ⌝∧∧∃ 2．选择题（1）B （2）B （3）A （4）B （5）C （6）C （7）B （8）B （9）B （10）D （11）C （12）A 3．下列哪些是谓词公式解：公式（1）—（8）均为谓词公式。

4．在谓词逻辑中将下列命题符号化 （1）有些汽车比所有火车都跑得慢；解：令)(x A ：x 是汽车，)(x B ：x 是火车，),(y x C ：x 比y 跑得慢。

符号化为)))),()((()((y x C y B y x A x →∀∧∃ （2）会叫的狗未必会咬人；解：令)(x A ：x 会叫，)(x B ：x 是狗，)(x C ：x 会咬人符号化为))()()((x C x B x A x ⌝∧∧∃ （3）存在最小自然数解：令A （x ）:x 是自然数，B （x,y ）：x 小于y 符号化为),()(()((x y B y A y x A x ⌝→∀⋂∃（4）对于每个实数都存在比它大的有理数解：令A （x ）:x 是实数，B （x ）:x 是有理数，R （x,y ）：x 比y 大 符号化为),()(()((x y R y B y x A x ⋂∃→∀（5）每个自然数都有唯一的后继 解：令A （x ）:x 是自然数，B （x,y ）：x 是y 的后继 符号化为),()((!)((x y B y A y x A x ⋂∃→∀） （6）没有以0为后继的自然树解：令A （x ）:x 是自然数，B （x,y ）：x 是y 的后继 符号化为),0()((x B x A x ⋂⌝∃（7）存在唯一的偶实数解：令A （x ）:x 是偶数，令B （x ）:x 是素数 符号化为)()((!x B x A x ⋂∃(8)没有即是奇数也是偶数的数解：令A （x ）:x 是奇数，令B （x ）:x 是偶数 符号化为)()((x B x A x ⋂⌝∃（9）天下乌鸦一般黑解：令A （x ）:x 是乌鸦，令B （x ）:x 是黑的 符号化为)()((x B x A x →∀（10）一个数是素数当且仅当它只能被1和它自身整除解：;:)(;:),(;.:),(B ;.:)(是实数相等与整除被是素数x x D y x y x C y x y x x x A 符号化为：)))),()1,(()),()((()((x y C y C y x B y D y x A x ∨→∧∃↔∀ 5、利用所给定命题和谓词，将下列诸命题符号化。