第一篇：屈婉玲版离散数学课后习题答案【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∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 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∨r1
所以公式类型为永真式
(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)→(qp)屈婉玲版离散数学课后习题答案
(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3
∑(0,2,3)主合取范式：
(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1
∏(1)(2)主合取范式为：
(p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：
(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)屈婉玲版离散数学课后习题答案
第三章部分课后习题参考答案
14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq
证明：（2）
①(qr)前提引入 ②qr ①置换
③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p ⑤⑥拒取式
证明（4）：
①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入
⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取
15在自然推理系统P中用附加前提法证明下面各推理：
屈婉玲版离散数学课后习题答案
(1)前提：p(qr),sp,q 结论：sr 证明
①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理
16在自然推理系统P中用归谬法证明下面各推理：
(1)前提：pq,rq,rs 结论：p 证明：
①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢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快 屈婉玲版离散数学课后习题答案 命题符号化为: xy((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)xy(G(x,y)(2)F(x,y)) xy(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(qp)p(qp)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)xyF(x,y) F(f(x),f(y)))(3)xy(F(x,y)解:(1)xyF(x,y)x(F(x,3)F(x,4))屈婉玲版离散数学课后习题答案 (F(3,3)F(3,4))(F(4,3)F(4,4)) (01)(10)1 (2)xy(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)))((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3)))(00)(11)(11)(00)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)xy(F(x)G(t,y)) (5)x1F(x1,x2)(H(x1)x2G(x1,x2)) x1F(x1,x2)(H(x3)x2G(x3,x2))x1F(x1,x4)x2(H(x3)G(x3,x2))x1x2(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 ②④假言推理⑤化简 ②⑥合取引入 屈婉玲版离散数学课后习题答案 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2）非零整数集合错误！未找到引用源。普通的除法运算。不封闭 （3）全体nn实矩阵集合错误！未找到引用源。（R）和矩阵加法及乘法运算，其中n错误！未找到引用源。2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误！未找到引用源。2。不封闭 （5）正实数集合错误！未找到引用源。和错误！未找到引用源。运算，其中错误！未找到引用源。运算定义为： 错误！未找到引用源。 不封闭 因为 1111111R （6）n错误！未找到引用源。关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（n1），零元是 0；n1单位元是1 （7）A = {a1,a2,,an} 错误！未找到引用源。n错误！未找到引用源。运算定义如下： 错误！未找到引用源。 封闭 不满足交换律，满足结合律，（8）S = 错误！未找到引用源。关于普通的加法和乘法运算。封闭 均满足交换律，结合律，乘法对加法满足分配律（9）S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = 错误！未找到引用源。,S关于普通的加法和乘法运算。屈婉玲版离散数学课后习题答案 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 7． 设 * 为Z错误！未找到引用源。上的二元运算x,yZ，X * Y = min(x，y),即x和y之中较小的数.(1)求4 * 6，7 * 3。 4，(2)* 在Z上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律 (3)求*运算的单位元，零元及Z中所有可逆元素的逆元。单位元无，零元1, 所有元素无逆元 8．SQQ Q为有理数集，*为S上的二元运算，错误！未找到引用源。 < a，b >* （1）*运算在S上是否可交换，可结合？是否为幂等的？ 不可交换： （2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。设 屈婉玲版离散数学课后习题答案 设 错误！未找到引用源。 10．令S={a，b}，S上有四个运算：*，错误！未找到引用源。分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a)交换律，结合律，幂等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 a1a,b1b (c)满足交换律,不满足幂等律,不满足结合律 a(bb)a(bb)aab,(ab)b(ab)baba 没有单位元, 没有零元 (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 4S解：(1)x,y∈S, x,是S上的代数运算。 (2)x,y,z∈S,设xy=4k+r 0(xy)z =((xy)mod 4) r3 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)111,31x)=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, 所以，x1y4xZ,o是Z上的代数运算。 所以〈Z，o〉构成群 屈婉玲版离散数学课后习题答案 11.设1G=00,1100,1100,11001，证明G关于矩阵乘法构成一个群． 解：(1)x,y∈G, 易知xy∈G,乘法是Z上的代数运算。 (2)矩阵乘法满足结合律(3)设1001是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群． 14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。证明:x,y∈G，设x xyaaaklkla,lkkyaaall，则 yxak 所以，G是交换群 17.设G为群，证明e为G中唯一的幂等元。证明:设e0 18.设G为群，a,b,c∈G,证明 ∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc设(abc)kG也是幂等元，则e02e0，即e02e0e，由消去律知e0e)ke(bca)ke e,则(abc)(abc)(abc)(abc)e，a(bc)(abc)(abc)a(bc)aa1即 e 左边同乘a1，右边同乘a得 (bca)(bca)(bca)(bca)(bac)kkka1eae 反过来，设(bac)e,则(abc)e.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 屈婉玲版离散数学课后习题答案 19.证明：偶数阶群G必含2阶元。 证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是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阶元，则a2a,bG,a1e1，a1a，a,b1b,(ab)1ab,所以aba1b(ba)1ba与G为Abel群矛盾； 所以，G含至少含一个3阶元，设为a，则a令ba2a2，且a2aaa2。的证。 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,ex,yN(a),N(a) ,所以xy1则axxa,ayya a(xy)(ax)y(xa)yx(ay)x(ya)(xy)aN(a) 由axxa，得x1axx1x1xax1,x1aeeax，即x1aax1，所以x1N(a) 所以N（a）构成G的子群 31.设1是群G1到G2的同态，2是G2到G3的同态，证明12 是G1到G3的同态。 屈婉玲版离散数学课后习题答案 证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。 a,bG1,(12)(ab)(2(1(a)))(2(1(b)))2(1(ab))2(1(a)1(b))(12)(a)(12)(b) 所以:1·2是G1到G3的同态。 33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G是循环群,令G=,x,yG,令xxyaaaklkla,yakl,那么 alkaalkyx,G是阿贝尔群 克莱因四元群,G{e,a,b,c} eabceeabcaaecbbbceaccbae 是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设,是5元置换，且 2121344551，332435415 2(1)计算(2)将,,11,1,1； ,,1表示成不交的轮换之积。 (3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1)411253533434251 4112324313142435552 1142531425 312215 41511 (2)(3) 1(1425)(14253)(143)(25) (14)(12)(15)奇置换，(14)(12)(15)(13)偶置换 (14)(13)(25)奇置换 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∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 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∨r1 所以公式类型为永真式 (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)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3 ∑(0,2,3)主合取范式： (p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1 ∏(1)(2)主合取范式为： (p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为： (p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案 14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq 证明：（2） ①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p ⑤⑥拒取式 证明（4）： ①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理： 4(1)前提：p(qr),sp,q 结论：sr 证明 ①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：pq,rq,rs 结论：p 证明： ①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢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快 命题符号化为: xy((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,yD错误！未找到引用源。.(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(qp)p(qp)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)xyF(x,y) (3)xy(F(x,y)F(f(x),f(y)))解:(1)xyF(x,y)x(F(x,3)F(x,4)) (F(3,3)F(3,4))(F(4,3)F(4,4))(01)(10)1 (2)xy(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))) ((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3))) (00)(11)(11)(00)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)xy(F(x)G(t,y))(5)x1F(x1,x2)(H(x1)x2G(x1,x2)) x1F(x1,x2)(H(x3)x2G(x3,x2))x1F(x1,x4)x2(H(x3)G(x3,x2))x1x2(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∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 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∨r1 所以公式类型为永真式 (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)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3 ∑(0,2,3)主合取范式： (p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1 ∏(1)(2)主合取范式为： (p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为： (p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案 14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq 证明：（2） ①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p（3）⑤⑥拒取式 证明（4）： ①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理： 4(1)前提：p(qr),sp,q 结论：sr 证明 ①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：pq,rq,rs 结论：p 证明： ①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正确.第三篇：屈婉玲版离散数学课后习题答案【4】
第四篇：离散数学(屈婉玲)答案_1-5章
第五篇：离散数学课后习题答案
点击咨询 