离散数学(屈婉玲)答案_15章_离散数学答案屈婉玲

离散数学(屈婉玲)答案_15章由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学答案屈婉玲”。

第一章部分课后习题参考答案设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

00

0

0

00

0

0

0 0

0

0 1

0

0

0

0 1

01

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.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(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(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))

⑤化简 ②⑥合取引入