离散数学(09).ppt

1，第2章集合2.3归纳法和自然数，2.3.3归纳法证明归纳法定义不仅提供了一种定义无穷集合的方法，而且还形成了一些证明定理的有效技巧的基础。对于XP (x)命题，如果它的讨论域是一组归纳定义，归纳通常是一种有效的2-证明方法。归纳证明通常由两部分组成：基本步骤和归纳步骤，它们分别对应于S定义中的基本术语和归纳术语。(1)基本步骤。这一步证明了每个元素xS，P(x)中规定的基本子句中定义的S是真的。(2)归纳步骤。这一步证明了如果x，y，z，具有性质p，那么通过归纳子句中指定的方法组合它们而获得的新元素也具有性质p。归纳定义的极简主义子句保证只有应用基本和归纳子句才能形成S的所有元素，从而证明上述两个步骤足以启动XP (X)。现在举一个例子来说明这个方法。回顾定理1.2-1(P12):“设A和A*是对偶的。P2 P1，Pn都是出现在a和A*中的命题论点，所以： A (P1，P2，(pn)*(P1， P2， Pn) (1)因为公式A只包含连接词，根据对偶性的定义，公式A可以概括为：5，(1)Pi(1in)是一个公式；t是公式；f是公式。(2)如果a和b是公式，那么A，(AB)，(AB)是公式。(3)只有当子句(1)和(2)被应用有限的次数时，才会生成公式。定理1.2-1是基于一组由归纳定义的公式，所以它可以由上面的一般归纳证明。(1)(基本步骤)A (P1，P2)Pi；TF，(这时，a和A*只是一个单一命题的自变量或常数a=a *)a(P1，P2.)pi；t 48(2)(归纳步骤)假设a1 (P1，p2，pn)，a2 (P1，p2，pn)适用于公式(1)，即：7，94a1 (P1，p2，pn) a1 * (P1，94p2，pn) a2 (P1，p2，pn) a2 * (P1，94p2，pn)现在证明： (a1 a2) (a1 a2) 情况1: (A1A2)注(a1 a2)是a。a的对偶A*是(a1 *a2 *)，8， a (P1，p2，pn)(a1(P1，p2，pn)a2(P1，p2，a1(P1，p2，pn)a2(P1，p2，pn)a1 *(p1，p2，pn)a2 *(p1，p2，pn)案例2:(A1A2)类似于案例1，留给读者去证明自己。9，案例3:A1记录A1是一个 a (P1，p2，pn) a1 (P1，p2， a1 * ( P1，94p2， pn) a * ( P1，94p2，94p2，因此公式(1)适用于n个命题变量的所有运算。上述归纳法是为了证明对偶公式中可能的命题运算，10，而这种归纳法又称为完全归纳法(exhaustive method)。然而，一般归纳证明涉及自然数，其具有以下归纳特征：(1)(基本)0N(2)(归纳)如果nN，则N 1N(3)(极小)如果Sn和S具有以下性质：11，(I)0S；(ii)对于每一个nN，如果nS，那么(N 1)S。所以，s=n。这里，最小子句是在自然数的定义中通常使用的一种形式，这被称为数学归纳法的第一原理。如果我们适当地改变这个子句的形式，就可以得到以自然数为讨论域的XP (x)形式断言的归纳证明过程。我们通常使用的数学归纳法如下：证明p (n) (n=1，2，3，)成立。(1)首先证明当n=1时P(1)成立(2)假设当n=k (3)时P(k)成立，然后证明当n=k 1 (1)成立时P(k 1)成立(2)(3)表明后一项成立，只要前一项成立。结合已被证明的第一项，得到任何n，P(n)都是有效的。13，让S=n|P(n)是n的子集，因此极简主义子句可以改为“如果(1) p (0)为真，(2) n (P(n) p (n 1)为真，(P(n)作为假设前提为真)，那么，对于所有n，P(n)为真。”根据该条款，立即获得归纳证明的过程如下：(1)(基本)首先，证明P(0)为真。可以使用任何证明技术。(2)(归纳法)再次证明n (p (n) p (n 1)是真的。由于这个原因，14，通常假设“P(n)对任何nN都是真的”，这被称为归纳假设(或归纳前提)，然后P(n 1)也是真的。一旦证明了P(n)P(n 1)对任何n都是真的，则规则n (p (n) p (n 1)被完全推广。根据数学归纳法的第一原理，得到了极限表达式。对于所有的nN，这里的定理是NP (n)形式。P(n)是一个断言证明：(1)(基本)证明P(1)因为是1=1，它显然是真的(2)(归纳)证明N (P (n) P (n 1)。假设对于所有的nN，P(n)为真，即16，我们要证明P(n 1)，即因为(根据归纳假设)，17，N是任意的，我们得到n (p (n) p (n 1)，XP (x)是通过应用第一个归纳原理得到的，即所有的自然数N，并且建立了数学归纳的第一个原理，这实际上是自然数域中的一个推理规则。对于第1.5节中的符号，规则如下：18。规则可以有各种变化。例如，我们通常想证明对于整数k(第一项是k项)，谓词P适用于所有x k的情况。此时，基本步骤必须由证明P(k)代替。因此，推理规则是：很容易证明这两种形式的推理规则是等价的。当n 4时，2n N2 (1)(基本)n=5，25 52显然是真的。(2)(归纳)如果n被设置，2n N2成立，如果n 1被证明，命题成立，其中n5。因为2 n1=22n 2 N2N2 N2N2 nnN2 5n N2 2 n1=(n1)2，对于所有n 4，2n n2。经过验证。如果n=m 5，上述问题将变成“证明所有自然数m，2m 5 (m 5)2”，这样，问题将成为从m=0开始的基本形式。示例10按照本节示例6中的定义设置。试着证明：Mn (aman=am n)证书：设置m为任意，求和n，证明断言n (aman=am n)，21，(1)(基础)如果n=0，那么aman=ama0=am1=am=am0=amn (2)(求和)设置aman=am n为真，那么aman 1=am(ana)an=(aman)a乘法关联法则=(am n)归纳假设=a(m n)1 an的定义，21因为m是任意的，所以在Mnam上有另一种形式的归纳证明。通过普遍推广规则得到的自然数场，称为数学归纳法的第二个原理。作为推理规则的第二个原则的形式如下：23。应用该推理规则的归纳性证明假设是3336k k NP (k)，即所有k n，P (k)都是真的。从这个假设出发，我们必须证明P(n)。在归纳假设的前提下，一旦P(n)被证明，就可以得到XP (x)。第二个原则的应用只需要我们证明一个单一的前提，但它通常需要逐案证明。首先，我们证明n=0的情况。当n=0时，k 0对所有kN总是假的，因此P(n) k k 0 p (k) 的先行词总是真的(诚信推理)。因此，证明k k 0 p (k) 这样，用第二原理证明和用第一原理证明之间的唯一区别是：用“所有k n，P(k)为真”的归纳假设代替“p (n-1)为真”的归纳假设。归纳的第一个原则是证明如果n=k，n=k1成立；归纳的第二个原则是：证明当n 2。叉积也称为集合的笛卡儿积。34，从定义中可以看出，Ai是n重组集 | AiAiAi1In 另外，Ai可以缩写为a，表示所有的I，AI=a，例1集合a=a，b，b=1，2，3，c=p，q，d=0，e=.(a) ab=，35，(b) abc=，a，2，p，如图2.5-1所示。36，(c)CD=， .(d) d (c2)=d ，=，注意，etc。这里不能写成etc。(e) ae=。我们同意：a=a=当a和b是实数集时，AB可以代表笛卡尔平面的点集。例如：一个平面可以是一个集合(x，y)xryr 或(r，)0r | 1x20y (B)ba= | 1x20y ，38，(a) (b)，这个例子说明：的叉积运算不满足交换性ABC (AB) CA (BC)，39，定理2.5-1如果A，37 A(BC)=(AB)AC(B)A(BC)=(AB)AC(C)(C)(AB)C=(AC)BC(D)(AB)C=(AC)BC(BC)证书3:设置为A(BC)然后A(BC)xay(BC)，40，xaC 有些读者自己证明了这一点。上述定理表明集合上叉积运算的分布规律是有效的。41，定理2.5-2如果所有的人工智能(I=1，2，n)是有限集合，| A1A2.安|=| A1 | | A2 | | A3.|安|证明：n=1，|A1|=|A1|显然成立。当n=2被归纳证明为n2时，设| a1 |=p，| A2 |=q，a1中的每个元素和A2中的q个不同元素可以形成q个不同的序列对，所以总共可以形成pq个不同的序列对，所以|A1A2|=pq=|A1|A2|，42，让我们假设定理为任何n2成立，现在让我们证明n 1也成立。| a1a2.anan1 |=| a1a2.an | | an1 |=| a1 | | a2 |.| an | | an1 |