离散数学(第十四章)

第一章部分课后习题参考答案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) ⇔ 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中用附加前提法证明下面各推理：(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,均有错误！未找到引用源。

第七章部分课后习题参考答案7.列出集合A={2,3,4}上的恒等关系I A ,全域关系E A ,小于或等于关系L A ,整除关系D A .解：I A ={<2，2>,<3,3>,<4,4>}E A ={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,4>}13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>}求A ⋃B,A ⋂B, domA, domB, dom(A ⋃B), ranA, ranB, ran(A ⋂B ), fld(A-B). 解：A ⋃B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A ⋂B={<2,4>}domA={1,2,3} domB={1,2,4} dom(A ∨B)={1,2,3,4}ranA={2,3,4} ranB={2,3,4} ran(A ⋂B)={4}A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R R, R -1, R ↑{0,1,}, R[{1,2}] 解：R R={<0,2>,<0,3>,<1,3>}R -1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R ↑{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}16．设A={a,b,c,d}，1R ，2R 为A 上的关系，其中1R ={},,,,,a a a b b d{2,,,,,,,R a d b c b d c b=求23122112,,,R R R R R R 。

数学14章知识树全文共四篇示例，供读者参考第一篇示例：数学作为一门重要的学科，被广泛地运用于各个领域。

而在数学的学习过程中，很多时候我们往往会感觉有些知识点相互关联，但却无法构建出一个系统性的框架，难以将其融会贯通。

为了帮助大家更好地理解数学的知识体系，我们可以通过绘制“知识树”的形式，将各个知识点串联起来，形成一个有机的整体。

在本文中，我将为大家介绍一份关于数学的14章知识树，希望可以帮助大家更好地理解数学知识的结构和内在联系。

第一章：基本概念在这一章中，我们将学习到数学的起源和基本概念，包括数的分类、数的性质、集合的概念等。

这是数学学习的基础，建立在这些基本概念之上，我们才能更深入地探索数学的世界。

第二章：初等代数在这一章中，我们将学习关于代数的基本概念和技巧，包括多项式的运算、方程的解法、因式分解等。

初等代数是数学学习的重要阶段，它为我们打下了解决各种数学问题的基础。

第三章：几何学几何学是研究空间和形状的科学，它包括点、线、面、体等基本概念，以及几何图形的性质和相互关系。

通过学习几何学，我们可以更好地理解空间结构，解决与形状和大小相关的问题。

第四章：三角学三角学是研究三角形和三角函数的学科，它包括三角函数的定义、图像、性质和应用等内容。

三角学是数学中一个重要的分支，它在解决各种实际问题中扮演着至关重要的角色。

第五章：微积分微积分是研究变化的数学，它包括导数、微分、积分等概念和技巧。

微积分被广泛地应用于科学、工程、经济等领域，它为我们提供了解决变化和尺度问题的数学工具。

第六章：概率论概率论是研究随机事件的概率和规律的学科，它包括概率的定义、性质、分布等内容。

概率论在各种实际问题中都有着广泛的应用，它帮助我们了解随机现象的规律性和规律。

第七章：数论数论是研究整数的性质和规律的学科，它包括素数、同余、数论函数等内容。

数论在密码学、编码理论等领域有着重要的应用，它帮助我们理解整数之间的关系和规律。