离散数学 第5章 推理与证明技术.ppt

* 铺瓦问题 例5.4.4 一个直角三正方形，是一个由三个正方形组成的对象，如图1所示。如果我们从n×n(n为2的幂)正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图2。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。 * 直角三正方形 图1 图2 2k×2k 2k×2k 2k×2k 2k×2k 图3 * 证明 归纳基础验证 如k＝1，2×2缺方板本身就是一个直角三正方形。因此可由三正方形铺成； 归纳假设假定 设我们可以把2k×2k的缺方板用直角三正方形铺成； * 证明(续) 归纳结论证明部分 对于2k＋1×2k＋1的缺方板问题，我们可以将其分成四个2k×2k的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的2k×2k缺方板可由直角三正方形铺成，把一个直角三正方形T放在中间，则另外三个四分之一都是2k×2k的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是2k＋1×2k＋1的缺方板可由直角三正方形铺成。 由数学归纳法知，对任何的n，n×n正方形的铺瓦问题都是可以铺成的。 * 5.5 按定义证明方法 在离散数学中，我们大量的定义描述都是用蕴涵型“P→Q”的方式来描述的。 如集合中子集的包含关系的定义描述为： A ? B ? (?a)(a∈A→a∈B) * 5.5.1 按定义证明方法原理 加上题目中的已知G1, G2,…,Gn 证明问题H中的Q 规则触发 引用公理 引入证明问题H中的 P 设有一组前提(或叫做已知条件)为Г={G1,G2, …,Gn}，证明问题H = P→Q，则利用CP规则的证明方式，将证明问题H中的前提P作为附加前提，加入到前提集合当中，构成一组新前提Г’={G1,G2, …,Gn,P}，此时，证明这组新前提Г’ ?Q，即有 Г ? H Г’ ?Q * 5.5.2 按定义证明方法应用 例5.5.1 设A、B是两个任意集合，证明 A ? B ? P(A) ? P(B) 证明 （1）必要性“?”： 对任意x∈P(A)， 则x ? A， 由于A ? B， 所以x ? B，即 有x∈P(B)。 P(A) ?P(B)。 即 A ? B ? P(A) ? P(B) 由CP规则知： * 例5.5.1(续) （2）充分性“?”： 对任意x∈A，则{x}∈P(A)，由于P(A)?P(B)，所以{x}∈P(B)，即有x∈B。由CP规则知： A ?B。 即 P(A) ? P(B) ? A ? B。 原式得证。 * 例5.5.2 如果A ? B，则A∪B＝B且A∩B＝A 证明两个集合相等，即是证明两个集合相互包含，请学生自证。 * 1. (2),(4),(6) 2. (2),(4),(6) 3. (1),(3),(5) 5. (3),(4) 6. (6),(7) 7. (7),(8),(9) 8. 10. 12. 14. 习题 146－148页 注意 下次上课时： 交作业； 单元测验 www.T 95/wlxt/ncourse/lsxx/web/default.aspx * * 5.3.3 谓词逻辑推理的难点 在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。 如一个变量是用规则ES消去量词，对该变量在添加量词时，则只能使用规则EG，而不能使用规则UG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。 * 谓词逻辑推理的难点（续） 如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。 在用规则US和规则ES消去量词、用规则UG和规则EG添加量词时，此量词必须位于整个公式的最前端，并且它的辖域为其后的整个公式。 * 谓词逻辑推理的难点（续） 在添加量词(?x)、(?x)时，所选用的x不能在公式G(y)或G(c)中自由出现且G(y)或G(c)对x是自由的。 在使用规则EG引入存在量词(?x)时，此x不得仅为G(c)或G(y)中的函数变元。在使用规则UG引入全称量词(?x)时，此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。 在使用规则