离散数学 第2章 习题解答

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系离散数学习题解答习题一（第一章集合）1. 列出下述集合的全部元素：1）A={x | x ∈N∧x是偶数∧x＜15}2）B={x|x∈N∧4+x=3}3）C={x|x是十进制的数字}[解] 1）A={2，4，6，8，10，12，14}2）B=3）C={0，1，2，3，4，5，6，7，8，9}2. 用谓词法表示下列集合：1）{奇整数集合}2）{小于7的非负整数集合}3）{3，5，7，11，13，17，19，23，29}[解] 1）{n n I(m I)(n=2m+1)}；2）{n n I n0n<7}；3）{p p N p>2p<30(d N)(d1d p(k N)(p=k d))}。

3. 确定下列各命题的真假性：1）2）∈3）{}4）∈{}5）{a，b}{a，b，c，{a，b，c}}6）{a,b}∈(a，b，c，{a，b，c})7）{a，b}{a，b，{{a，b，}}}8）{a，b}∈{a，b，{{a，b，}}}[解]1）真。

因为空集是任意集合的子集；2）假。

因为空集不含任何元素；3）真。

因为空集是任意集合的子集；4）真。

因为是集合{}的元素；5）真。

因为{a，b}是集合{a，b，c，{a，b，c}}的子集；6）假。

因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；7）真。

因为{a，b}是集合{a，b，{{a，b}}}的子集；8）假。

因为{a,b}不是集合{a，b，{{a，b}}}的元素。

4. 对任意集合A，B，C，确定下列命题的真假性：1）如果A∈B∧B∈C，则A∈C。

2）如果A∈B∧B∈C，则A∈C。

3）如果A B∧B∈C，则A∈C。

[解] 1）假。

例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。

2）假。

例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A∈C。

离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

19．用真值表判断下列公式的类型：（4）(p→q) →(⌝q→⌝p)（5）(p∧r) ↔(⌝p∧⌝q)（6）((p→q) ∧(q→r)) →(p→r)答：（4）p q p→q ⌝q ⌝p ⌝q→⌝p (p→q)→(⌝q→⌝p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)⇔(p→(q∧r))(4)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)证明（2）(p→q)∧(p→r)⇔ (⌝p∨q)∧(⌝p∨r)⌝p∨(q∧r))p→(q∧r)（4）(p∧⌝q)∨(⌝p∧q)⇔(p∨(⌝p∧q)) ∧(⌝q∨(⌝p∧q)(p∨⌝p)∧(p∨q)∧(⌝q∨⌝p) ∧(⌝q∨q)1∧(p∨q)∧⌝(p∧q)∧1(p∨q)∧⌝(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p →q)→(⌝q ∨p)⌝(p ∨q)∨(⌝q ∨p)(⌝p ∧⌝q)∨(⌝q ∨p)⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)(⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(0,2,3)主合取范式：(⌝p →q)→(⌝q ∨p)⌝(p ∨q)∨(⌝q ∨p)(⌝p ∧⌝q)∨(⌝q ∨p)⇔(⌝p ∨(⌝q ∨p))∧(⌝q ∨(⌝q ∨p))⇔1∧(p ∨⌝q)⇔(p ∨⌝q) ⇔ M 1⇔∏(1)(2) 主合取范式为：⌝(p →q)∧q ∧r ⇔⌝(⌝p ∨q)∧q ∧r⇔(p ∧⌝q)∧q ∧r ⇔0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：(p ∨(q ∧r))→(p ∨q ∨r)⌝(p ∨(q ∧r))→(p ∨q ∨r)(⌝p ∧(⌝q ∨⌝r))∨(p ∨q ∨r)(⌝p ∨(p ∨q ∨r))∧((⌝q ∨⌝r))∨(p ∨q ∨r))⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r) 前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（q→t）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r) 前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案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)中为真命题。

《离散数学1-5章》练习题答案第2，3章(数理逻辑)1.答：（2），（3），（4）2.答：（2），（3），（4），（5），（6）3.答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是4.答：（4）5.答：⌝P ，Q→P6.答：P(x)∨∃yR(y)7.答：⌝∀x(R(x)→Q(x))8、c、P→(P∧(Q→P))解：P→(P∧(Q→P))⇔⌝P∨(P∧(⌝Q∨P))⇔⌝P∨P⇔ 1 (主合取范式)⇔ m0∨ m1∨m2∨ m3 （主析取范式）d、P∨(⌝P→(Q∨(⌝Q→R)))解：P∨(⌝P→(Q∨(⌝Q→R)))⇔ P∨(P∨(Q∨(Q∨R)))⇔ P∨Q∨R⇔ M0 (主合取范式)⇔ m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式) 9、b、P→(Q→R)，R→(Q→S) => P→(Q→S)证明：（1） P 附加前提（2） Q 附加前提（3） P→(Q→R) 前提（4） Q→R （1），（3）假言推理（5） R （2），（4）假言推理（6） R→(Q→S) 前提（7） Q→S （5），（6）假言推理（8） S （2），（7）假言推理d、P→⌝Q，Q∨⌝R，R∧⌝S⇒⌝P证明、(1) P 附加前提（2） P→⌝Q 前提（3）⌝Q （1），（2）假言推理（4） Q∨⌝R 前提(5) ⌝R （3），（4）析取三段论(6 ) R∧⌝S 前提（7） R （6）化简（8） R∧⌝R 矛盾（5），（7）合取所以该推理正确10.写出∀x(F(x)→G(x))→(∃xF(x) →∃xG(x))的前束范式。

解：原式⇔∀x(⌝F(x)∨G(x))→(⌝(∃x)F(x) ∨ (∃x)G(x))⇔⌝(∀x)(⌝F(x)∨G(x)) ∨(⌝(∃x)F(x) ∨ (∃x)G(x))⇔ (∃x)((F(x)∧⌝ G(x)) ∨G(x)) ∨ (∀x) ⌝F(x)⇔ (∃x)((F(x) ∨G(x)) ∨ (∀x) ⌝F(x)⇔ (∃x)((F(x) ∨G(x)) ∨ (∀y) ⌝F(y)⇔ (∃x) (∀y) (F(x) ∨G(x) ∨⌝F(y))（集合论部分）1、答：(4)2.答：323.答：（3）4. 答：（4）5.答：（2），（4）6、设Ａ，Ｂ，Ｃ是三个集合，证明：a、A⋂ (B－C)＝(A⋂B)－(A⋂C)证明：(A⋂B)－(A⋂C)= (A⋂B)⋂~（A⋂C）=(A⋂B) ⋂（~A⋃~C）=(A⋂B⋂~A)⋃(A⋂B⋂~C)= A⋂B⋂~C=A⋂（B⋂~C）=A⋂（B-C）b、(A－B)⋃(A－C)=A－(B⋂C)证明：(A-B)⋃(A-C)=(A⋂~B)⋃(A⋂⋂~C) =A⋂ (~B ⋃~C)=A⋂~（B⋂C）= A-(B⋂C)（二元关系部分）1、答：（1）R={<1,1>,<4,2>} (2) R1-={<1,1>,<2,4>}2.答：R R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝3.答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}4.答：R 的关系矩阵=⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡000000001000000001 R 1-的关系矩阵=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0000000100000000015、解：（1）R={<2,1>,<3,1>,<2,3>};M R =⎪⎪⎪⎭⎫ ⎝⎛001101000;它是反自反的、反对称的、传递的；（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};M R =⎪⎪⎪⎭⎫⎝⎛011101110;它是反自反的、对称的；（3）R={<1,2>,<2,1>,<1,3>,<3,3>};M R =⎪⎪⎪⎭⎫⎝⎛100001110;它既不是自反的、也不是反自反的、也不是对称的、也不是反对称的、也不是传递的。

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、将下列命题符号化:(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.11．将下列命题符号化。

(1) 4不是奇数。

解：设A(x)：x是奇数。

a：4。

“4不是奇数。

”符号化为：¬A(a)(2) 2是偶数且是质数。

解：设A(x)：x是偶数。

B(x)：x是质数。

a：2。

“2是偶数且是质数。

”符号化为：A(a)∧B(a)(3) 老王是山东人或河北人。

解：设A(x)：x是山东人。

B(x)：x是河北人。

a：老王。

∨“老王是山东人或河北人。

”符号化为：A(a)B(a)(4) 2与3都是偶数。

解：设A(x)：x是偶数。

a：2，b：3。

“2与3都是偶数。

”符号化为：A(a)∧A(b)(5) 5大于3。

解：设G(x,y)：x大于y。

a：5。

b：3。

“5大于3。

”符号化为：G(a,b)(6) 若m是奇数，则2m不是奇数。

解：设A(x)：x是奇数。

a：m。

b：2m。

“若m是奇数，则2m不是奇数。

”符号化为：A(a)→A(b)(7) 直线A平行于直线B当且仅当直线A不相交于直线B。

解：设C(x,y)：直线x平行于直线y。

设D(x,y)：直线x相交于直线y。

a：直线A。

b：直线B。

“直线A平行于直线B当且仅当直线A不相交于直线B。

”符号化为：C(a,b)↔¬D(x,y)(8) 小王既聪明又用功，但身体不好。

解：设A(x)：x聪明。

B(x)：x用功。

C(x)：x身体好。

a：小王。

“小王既聪明又用功，但身体不好。

”符号化为：A(a)∧B(a)∧¬C(a)(9) 秦岭隔开了渭水和汉水。

解：设A(x,y,z)：x隔开了y和z。

a：秦岭。

b：渭水。

c：汉水。

“秦岭隔开了渭水和汉水。

”符号化为：A(a,b,c)(10) 除非小李是东北人，否则她一定怕冷。

解：设A(x)：x是东北人。

B(x)：x怕冷。

a：小李。

“除非小李是东北人，否则她一定怕冷。

”符号化为：B(a)→¬A(a)2．将下列命题符号化。

并讨论它们的真值。

(1) 有些实数是有理数。

解：设R(x)：x是实数。

离散数学第四版课后答案第1章习题解答1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。

分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。

本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。

其次，4）这个句子是陈述句，但它表示的判断结果是不确定。

又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。

（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。

这里的“且”为“合取”联结词。

在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。

但要注意，有时“和”或“与”联结的是主语，构成简单命题。

例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。

1．2 （1）p: 2是无理数，p为真命题。

（2）p:5能被2整除，p为假命题。

（6）p→q。

其中，p:2是素数，q：三角形有三条边。

由于p与q都是真命题，因而p→q为假命题。

（7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。

由于p为假命题，q为真命题，因而p→q为假命题。

（8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。

（9）p：太阳系外的星球上的生物。

它的真值情况而定，是确定的。

1（10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。

离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)⇔0∨(0∧1)⇔0（2）（p?r）∧(﹁q∨s)⇔（0?1）∧(1∨1)⇔0∧1⇔0.（3）（⌝(4)（176能被2q:3r:2s:619（4）(p（5）(p（6）((p答：（pqp→q⌝0011111011011110010011110011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P qrp∨qp∧r（p∨q）→(p∧r)0000010010014.(2)(p→(4)(p∧证明（2（45.(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∧p)∨(⌝q∧⌝p)∨(p∧q)∨(p∧⌝q)⇔(⌝p∧⌝q)∨(p∧⌝q)∨(p∧q)⇔∑(0,2,3)主合取范式：(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p⇔1∧(p⇔(p∨⇔∏(2)⌝(p→q)⇔(p∧(3)⇔⌝⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r)前提引入②⌝q∨⌝r①置换③q→⌝r②蕴含等值式④r⑤⌝q⑥p→q⑦￢p（3证明（4①t②t③q④s⑤q⑥（⑦（⑧q⑨q⑩p15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p②p③﹁④￢⑤￢⑥r⑦r⑧r3.:(1)均有2=(x+)(x).(2)其中(a)(b)解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命题。

离散数学（微课版）第2章习题答案2.1 集合与运算习题1给定两个集合A={1，3，5，7，9}和B={2，4，6，8，10}，求A∪B和A∩B。

解答：集合A和B的并集（A∪B）是包含了A和B中所有元素的集合。

根据题目给出的集合A和B，可以得到并集A∪B={1，2，3，4，5，6，7，8，9，10}。

集合A和B的交集（A∩B）是包含了A和B中共有的元素的集合。

根据题目给出的集合A和B，可以得到交集A∩B={}，因为集合A和B中没有共有的元素。

习题2给定两个集合A={奇数}和B={偶数}，求A和B的交集和并集。

如果集合B改为B={2，4，6，8}，结果是否有变化？解答：集合A表示奇数，集合B表示偶数。

当集合A和B中元素的范围比较广泛时，它们的交集为{}，因为奇数和偶数没有共有的元素。

当集合B改为B={2，4，6，8}时，集合A和B中共有的元素为{}，并集为A∪B=奇数∪{2，4，6，8}={奇数，2，4，6，8}。

2.2 命题与逻辑运算习题3给定两个命题p：“小明喜欢篮球”和q：“小明是篮球队的队长”。

请判断以下复合命题是真还是假：（1）p∧q；（2）p∨q；（3）p→q。

解答：命题p：“小明喜欢篮球” 是真命题。

命题q：“小明是篮球队的队长” 是假命题。

（1）p∧q：当p和q都为真时，命题p∧q才为真。

根据题目中给出的p和q的真值，可以确定p∧q是假命题。

（2）p∨q：当p和q中至少一个为真时，命题p∨q就为真。

根据题目中给出的p和q的真值，可以确定p∨q是真命题。

（3）p→q：当p为真时，命题p→q为真，否则为假。

根据题目中给出的p和q的真值，可以确定p→q是真命题。

习题4给定一个命题p：“2是偶数”。

请判断以下复合命题是真还是假：（1）¬p；（2）p∧¬p；（3）¬p∨p。

解答：命题p：“2是偶数” 是真命题。

（1）¬p：取命题p的否定，即“2不是偶数”，根据命题p的真值，可以确定¬p是假命题。

第二章习题三一、证明如下推理式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答案(从本章起，习题答案由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)这个表达式的含义就是一个陈述句：那位大学生戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。

个体词是：那位大学生。

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

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

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

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、在下列公式中，对约束变元进行换名，对自由变量进行代入。