屈婉玲版离散数学课后习题答案【4】（最终五篇）

第一篇：屈婉玲版离散数学课后习题答案【4】

屈婉玲版离散数学课后习题答案

第十章部分课后习题参考答案

4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。

封闭,不满足交换律和结合律，无零元和单位元

（2）非零整数集合错误！未找到引用源。普通的除法运算。不封闭

（3）全体nn实矩阵集合错误！未找到引用源。（R）和矩阵加法及乘法运算，其中n错误！未找到引用源。2。

封闭

均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

（4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误！未找到引用源。2。不封闭

（5）正实数集合错误！未找到引用源。和错误！未找到引用源。运算，其中错误！未找到引用源。运算定义为：

错误！未找到引用源。

不封闭

因为 1111111R

（6）n错误！未找到引用源。关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（n1），零元是

0；n1单位元是1

（7）A = {a1,a2,,an} 错误！未找到引用源。n错误！未找到引用源。运算定义如下：

错误！未找到引用源。

封闭 不满足交换律，满足结合律，（8）S = 错误！未找到引用源。关于普通的加法和乘法运算。封闭

均满足交换律，结合律，乘法对加法满足分配律（9）S = {0,1},S是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满足交换律，结合律

（10）S = 错误！未找到引用源。,S关于普通的加法和乘法运算。屈婉玲版离散数学课后习题答案

加法不封闭，乘法封闭，乘法满足交换律，结合律

5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。

见上题

7． 设 * 为Z错误！未找到引用源。上的二元运算x,yZ，X * Y = min(x，y),即x和y之中较小的数.(1)求4 * 6，7 * 3。

4，(2)* 在Z上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律

(3)求*运算的单位元，零元及Z中所有可逆元素的逆元。单位元无，零元1, 所有元素无逆元

8．SQQ Q为有理数集，*为S上的二元运算，错误！未找到引用源。,错误！未找到引用源。S有

< a，b >* =

（1）*运算在S上是否可交换，可结合？是否为幂等的？

不可交换：*= < a，b >* 可结合：(*)*=*= *(*)=*=(*)*=*(*)不是幂等的

（2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。设是单位元，错误！未找到引用源。错误！未找到引用源。S，*= *= 则==，解的=<1,0>，即为单位。

屈婉玲版离散数学课后习题答案

设是零元，错误！未找到引用源。错误！未找到引用源。S，*= *= 则==，无解。即无零元。

错误！未找到引用源。错误！未找到引用源。S，设是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以当x0时，x,y11x,yx

10．令S={a，b}，S上有四个运算：*，错误！未找到引用源。分别有表10.8确定。

(a)

(b)

(c)

(d)

(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a)交换律，结合律，幂等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元

a1a,b1b

(c)满足交换律,不满足幂等律,不满足结合律

a(bb)a(bb)aab,(ab)b(ab)baba

没有单位元, 没有零元

(d)不满足交换律，满足结合律和幂等律

没有单位元, 没有零元

(2)求每个运算的单位元，零元以及每一个可逆元素的逆元。见上

16．设V=〈 N，+，错误！未找到引用源。〉，其中+，错误！未找到引用源。分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？

（1）S1=错误！未找到引用源。是 屈婉玲版离散数学课后习题答案

（2）S2=错误！未找到引用源。

不是 加法不封闭（3）S3 = {-1，0，1} 不是，加法不封闭

第十一章部分课后习题参考答案

8.设S={0，1，2，3}，为模4乘法，即

y=(xy)mod 4 “x,y∈S, x问〈S，〉是否构成群？为什么？

y=(xy)mod 4S解：(1)x,y∈S, x,是S上的代数运算。

(2)x,y,z∈S,设xy=4k+r 0(xy)z =((xy)mod 4)

r3

z=rz=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1

(y

z)，结合律成立。所以，(x(3)x∈S,(x(4)111,31x)=x,，所以1是单位元。

3, 0和2没有逆元

所以，〈S，〉不构成群

9.设Z为整数集合，在Z上定义二元运算。如下： ” x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群？为什么？ 解：(1)x,y∈Z, xoy= x+y-2(2)x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。

(3)设e是单位元，x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)x∈Z , 设x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x1y4xZ,o是Z上的代数运算。

所以〈Z，o〉构成群 屈婉玲版离散数学课后习题答案

11.设1G=00,1100,1100,11001，证明G关于矩阵乘法构成一个群．

解：(1)x,y∈G, 易知xy∈G,乘法是Z上的代数运算。

(2)矩阵乘法满足结合律(3)设1001是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．

14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。证明:x,y∈G，设x xyaaaklkla,lkkyaaall，则

yxak

所以，G是交换群

17.设G为群，证明e为G中唯一的幂等元。证明:设e0

18.设G为群，a,b,c∈G,证明

∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc设(abc)kG也是幂等元，则e02e0，即e02e0e，由消去律知e0e)ke(bca)ke

e,则(abc)(abc)(abc)(abc)e，a(bc)(abc)(abc)a(bc)aa1即

e

左边同乘a1，右边同乘a得

(bca)(bca)(bca)(bca)(bac)kkka1eae

反过来，设(bac)e,则(abc)e.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 屈婉玲版离散数学课后习题答案

19.证明：偶数阶群G必含2阶元。

证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元

20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba.证明：先证明G含至少含3阶元。

若G只含1阶元,则G={e},G为Abel群矛盾； 若G除了1阶元e外,其余元a均为2阶元，则a2a,bG,a1e1，a1a，a,b1b,(ab)1ab,所以aba1b(ba)1ba与G为Abel群矛盾；

所以，G含至少含一个3阶元，设为a，则a令ba2a2，且a2aaa2。的证。

21.设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。（1）全体对称矩阵 是子群（2）全体对角矩阵 是子群

（3）全体行列式大于等于0的矩阵.不是子群（4）全体上（下）三角矩阵。是子群

22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即

N（a）={x∣x∈G∧xa=ax} 证明N（a）构成G的子群。证明：ea=ae,ex,yN(a),N(a) ,所以xy1则axxa,ayya a(xy)(ax)y(xa)yx(ay)x(ya)(xy)aN(a)

由axxa，得x1axx1x1xax1,x1aeeax，即x1aax1，所以x1N(a)

所以N（a）构成G的子群

31.设1是群G1到G2的同态，2是G2到G3的同态，证明12

是G1到G3的同态。

屈婉玲版离散数学课后习题答案

证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。

a,bG1,(12)(ab)(2(1(a)))(2(1(b)))2(1(ab))2(1(a)1(b))(12)(a)(12)(b)

所以:1·2是G1到G3的同态。

33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。

证明：设G是循环群,令G=,x,yG,令xxyaaaklkla,yakl,那么

alkaalkyx,G是阿贝尔群

克莱因四元群,G{e,a,b,c}

eabceeabcaaecbbbceaccbae

是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设,是5元置换，且

2121344551，332435415 2(1)计算(2)将,,11,1,1； ,,1表示成不交的轮换之积。

(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1)411253533434251 4112324313142435552 1142531425 312215 41511

(2)(3) 1(1425)(14253)(143)(25)

(14)(12)(15)奇置换，(14)(12)(15)(13)偶置换 (14)(13)(25)奇置换 1

第二篇：屈婉玲版离散数学课后习题答案【1】

屈婉玲版离散数学课后习题答案

第一章部分课后习题参考答案 设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1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”

答：p: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除t: 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

0

0

0

0

0

0

0

0

所以公式类型为永真式 //最后一列全为1（5）公式类型为可满足式（方法如上例）//最后一列至少有一个1（6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1 屈婉玲版离散数学课后习题答案

(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

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 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)m0m2m3

∑(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) M1

∏(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 ⑤⑥拒取式

证明（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】

屈婉玲版离散数学课后习题答案 第四章部分课后习题参考答案

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)在两个个体域中都解释为xF(x)，在（a）中为假命题，在(b)中为真命题。

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

4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: x(F(x)(2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: x(F(x)H(x))H(x))

5.在一阶逻辑将下列命题符号化:(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解:(1)F(x): x是火车;G(x): x是轮船;H(x,y): x比y快 屈婉玲版离散数学课后习题答案 命题符号化为: xy((F(x)G(y))H(x,y))

(2)(1)F(x): x是火车;G(x): x是汽车;H(x,y): x比y快 命题符号化为: y(G(y)x(F(x)9.给定解释I如下:(a)个体域D为实数集合R.(b)D中特定元素错误！未找到引用源。=0.(c)特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y未找到引用源。.(d)特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x

错误！.说明下列公式在I下的含义,并指出各公式的真值:(1)xy(G(x,y)(2)F(x,y))

xy(F(f(x,y),a)G(x,y))答:(1)对于任意两个实数x,y,如果x

（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)因为 p(qp)p(qp)1 为永真式；

所以 错误！未找到引用源。为永真式； 屈婉玲版离散数学课后习题答案(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，前件假。此时为假命题。

此公式为非永真式的可满足式。13.给定下列各公式一个成真的解释，一个成假的解释。

(1)错误！未找到引用源。(F(x)错误！未找到引用源。

(2)错误！未找到引用源。x(F(x)错误！未找到引用源。G(x)错误！未找到引用源。H(x))解:(1)个体域:本班同学

F(x)：x会吃饭, G(x)：x会睡觉.成真解释

F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰山学院的学生

F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案

5.给定解释Ｉ如下:(a)个体域D={3,4};(b)f(x)错误！未找到引用源。为f(3)4,f(4)3错误！未找到引用源。

(c)F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1错误！未找到引用源。.试求下列公式在Ｉ下的真值.(1)xyF(x,y)

F(f(x),f(y)))(3)xy(F(x,y)解:(1)xyF(x,y)x(F(x,3)F(x,4))屈婉玲版离散数学课后习题答案 (F(3,3)F(3,4))(F(4,3)F(4,4))

(01)(10)1

(2)xy(F(x,y)F(f(x),f(y)))

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))

x((F(x,3)F(f(x),4))(F(x,4)F(f(x),3)))((F(3,3)F(f(3),4))(F(3,4)F(f(3),3)))

((F(4,3)F(f(4),4))(F(4,4)F(f(4),3)))((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3)))(00)(11)(11)(00)1

12.求下列各式的前束范式。

(1)xF(x)yG(x,y)

(5)x1F(x1,x2)解:(1)xF(H(x1)x2G(x1,x2))(本题课本上有错误)(x)yG(x,y)xF(x)yG(t,y)xy(F(x)G(t,y))

(5)x1F(x1,x2)(H(x1)x2G(x1,x2))

x1F(x1,x2)(H(x3)x2G(x3,x2))x1F(x1,x4)x2(H(x3)G(x3,x2))x1x2(F(x1,x4)(H(x3)G(x3,x2)))15.在自然数推理系统F中,构造下面推理的证明:(1)前提: xF(x)y((F(y)G(y))R(y)),xF(x)

结论: xR(x)(2)前提: x(F(x)→(G(a)∧R(x))), 错误！未找到引用源。xF(x)结论:错误！未找到引用源。x(F(x)∧R(x))证明(1)①xF(x)前提引入

②F(c)①EI ③xF(x)y((F(y)G(y))R(y))G(y))R(y))前提引入

④y((F(y) ①③假言推理

⑤(F(c)∨G(c))→R(c))④UI 屈婉玲版离散数学课后习题答案 ⑥F(c)∨G(c)②附加

⑦R(c)⑤⑥假言推理

⑧xR(x)⑦EG(2)①xF(x)前提引入 ②F(c)①EI ③x(F(x)→(G(a)∧R(x)))④F(c)→(G(a)∧R(c))⑤G(a)∧R(c)⑥R(c)⑦F(c)∧R(c)⑧x(F(x)∧R(x))

前提引入 ③UI ②④假言推理⑤化简 ②⑥合取引入

第四篇：离散数学(屈婉玲)答案_1-5章

第一章部分课后习题参考答案 设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1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”

答：p: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除t: 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

0

0

0

0

0

0

0

0

所以公式类型为永真式 //最后一列全为1（5）公式类型为可满足式（方法如上例）//最后一列至少有一个1（6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(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

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 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)m0m2m3

∑(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) M1

∏(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 ⑤⑥拒取式

证明（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中用附加前提法证明下面各推理：

4(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错误！未找到引用源。).5(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：

F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x错误！未找到引用源。).G(x): x+5=9.(1)在两个个体域中都解释为xF(x)，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为xG(x)，在（a）(b)中均为真命题。

4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: x(F(x)H(x))(2)F(x): x是北京卖菜的人 H(x): x是外地人

命题符号化为: x(F(x)H(x))5.在一阶逻辑将下列命题符号化:(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解:(1)F(x): x是火车;G(x): x是轮船;H(x,y): x比y快 命题符号化为: xy((F(x)G(y))H(x,y))

(2)(1)F(x): x是火车;G(x): x是汽车;H(x,y): x比y快 命题符号化为: y(G(y)x(F(x)H(x,y)))9.给定解释I如下:(a)个体域D为实数集合R.6(b)D中特定元素错误！未找到引用源。=0.(c)特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,yD错误！未找到引用源。.(d)特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x

答:(1)对于任意两个实数x,y,如果x

（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)因为 p(qp)p(qp)1 为永真式；

所以 错误！未找到引用源。为永真式；

(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，前件假。此时为假命题。

此公式为非永真式的可满足式。13.给定下列各公式一个成真的解释，一个成假的解释。

(1)错误！未找到引用源。(F(x)错误！未找到引用源。

(2)错误！未找到引用源。x(F(x)错误！未找到引用源。G(x)错误！未找到引用源。H(x))解:(1)个体域:本班同学

F(x)：x会吃饭, G(x)：x会睡觉.成真解释

F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰山学院的学生

F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案

5.给定解释Ｉ如下:(a)个体域D={3,4};(b)f(x)错误！未找到引用源。为f(3)4,f(4)3错误！未找到引用源。(c)F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1错误！未找到引用源。.试求下列公式在Ｉ下的真值.(1)xyF(x,y)

(3)xy(F(x,y)F(f(x),f(y)))解:(1)xyF(x,y)x(F(x,3)F(x,4))

(F(3,3)F(3,4))(F(4,3)F(4,4))(01)(10)1

(2)xy(F(x,y)F(f(x),f(y)))

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))

x((F(x,3)F(f(x),4))(F(x,4)F(f(x),3)))((F(3,3)F(f(3),4))(F(3,4)F(f(3),3)))

((F(4,3)F(f(4),4))(F(4,4)F(f(4),3)))

((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3)))

(00)(11)(11)(00)1

12.求下列各式的前束范式。

(1)xF(x)yG(x,y)

(5)x1F(x1,x2)(H(x1)x2G(x1,x2))(本题课本上有错误)解:(1)xF(x)yG(x,y)xF(x)yG(t,y)xy(F(x)G(t,y))(5)x1F(x1,x2)(H(x1)x2G(x1,x2))

x1F(x1,x2)(H(x3)x2G(x3,x2))x1F(x1,x4)x2(H(x3)G(x3,x2))x1x2(F(x1,x4)(H(x3)G(x3,x2)))

15.在自然数推理系统F中,构造下面推理的证明:(1)前提: xF(x)y((F(y)G(y))R(y)),xF(x)

结论: xR(x)(2)前提: x(F(x)→(G(a)∧R(x))), 错误！未找到引用源。xF(x)结论:错误！未找到引用源。x(F(x)∧R(x))证明(1)①xF(x)前提引入

②F(c)①EI ③xF(x)y((F(y)G(y))R(y))前提引入

④y((F(y)G(y))R(y))①③假言推理

⑤(F(c)∨G(c))→R(c))④UI ⑥F(c)∨G(c)②附加

⑦R(c)⑤⑥假言推理

⑧xR(x)⑦EG

9(2)①xF(x)前提引入 ②F(c)①EI ③x(F(x)→(G(a)∧R(x)))前提引入 ④F(c)→(G(a)∧R(c))③UI ⑤G(a)∧R(c)②④假言推理 ⑥R(c)⑦F(c)∧R(c)⑧x(F(x)∧R(x))

⑤化简 ②⑥合取引入

第五篇：离散数学课后习题答案

第一章部分课后习题参考答案 设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1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外，只有6能被2整除，6才能被4整除。”

答：p: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除t: 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

0

0

0

0

0

0

0

0

所以公式类型为永真式

（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）

第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(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

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 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)m0m2m3

∑(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) M1

∏(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中用附加前提法证明下面各推理：

4(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 是矛盾式,所以推理正确.