离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案.doc

离散数学答案 屈婉玲版第二版 高等教育出版社课后答案第一章部分课后习题参考答案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∧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→0117．判断下面一段论述是否为真：“是无理数并且，如果3是无理数，则也是无理数另外6能被2整除，6才能被4整除答：p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:　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 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 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∨r1 所以公式类型为永真式(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)→(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) ∑(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中用附加前提法证明下面各推理：(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).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合. (b)个体域为实数集合.解：F(x): 2=(x+)(x). G(x): x+5=9.(1)在两个个体域中都解释为，在（a）中为假命题，在(b)中为真命题。

2)在两个个体域中都解释为，在（a）(b)中均为真命题4. 在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数命题符号化为: (2)F(x): x是北京卖菜的人 H(x): x是外地人命题符号化为: 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解:(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快命题符号化为: (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快命题符号化为: 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=xy,x,y. (d) 特定谓词(x,y):x=y,(x,y):x

此时为假命题此公式为非永真式的可满足式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)为(c). 试求下列公式在Ｉ下的真值.(1) (3)解:(1) (2) 12.求下列各式。