南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）数论基础

计算机问题求解一论题4-4 数论基础 2019年04月09日

计算机问题求解 – 论题4-4 - 数论基础 2019年04月09日

三大科学手段 ■理论 ·实验 ·计算 口概率论与数理统计

三大科学手段 ◼ 理论 ◼ 实验 ◼ 计算 ❑ 概率论与数理统计

问题1： 自然数有定义吗？

用集合定义自然数 设a为集合，称U{d为a的后继，记为或at,或s(a)。 ·设A是集合，若A满足下列条件，称A为归纳集： 口0∈A 口Va(a∈A→叶∈A) ■自然数集合N是所有归纳集的交集。 口因此：N={0,{0},{0,{0},{0,{0),{0,{0},…} 口N的每一个元素称为一个自然数。 口0记为0,0+记为1,1+记为2,2+记为3，余此类推

用集合定义自然数 ◼ 设a为集合, 称a{a}为a的后继, 记为或a + , 或s(a)。 ◼ 设A是集合，若A满足下列条件，称A为归纳集： ❑ ØA ❑ a(aA→a+A) ◼ 自然数集合N是所有归纳集的交集。 ❑ 因此：N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … } ❑ N的每一个元素称为一个自然数。 ❑ Ø记为0，0 +记为1，1 +记为2，2 +记为3，余此类推

再具体一点 ■记号0表示：0 ■记号1表示0+：0U0}={0} ■记号2表示1+：{0狄U{0}={0,{0} ■记号3表示2*：{0，{0}U{0,{0}={0,{0,{0,{0} ■3U2=? 3∩2=？ ■2∈3？ 1∈3？ ■1c2?2c5? 自然数上的小于关系如何表达？

再具体一点 ◼ 记号0表示：Ø ◼ 记号1表示0 +： Ø{Ø}={Ø} ◼ 记号2表示1 +： {Ø}{{Ø}}={Ø,{Ø}} ◼ 记号3表示2 + : {Ø,{Ø}}{{Ø,{Ø}}}={Ø,{Ø}, {Ø,{Ø}}} ◼ 3∪2=? 3∩2=? ◼ 23? 13? ◼ 12? 25? 自然数上的小于关系如何表达？

自然数上的运算 ■加法（递归定义） o m+0=m m+n*=(m+n)* ■乘法（递归定义) ▣m*0=0 m*n+=m+m*n 序关系 aa≤biff3ceN.a+c=b

自然数上的运算 ◼ 加法（递归定义） ❑ m+0=m ❑ m+n+=(m+n) + ◼ 乘法（递归定义） ❑ m*0=0 ❑ m*n+=m + m*n ◼ 序关系 ❑ ab iff cN. a+c=b

问题2： 关于自然数有“公理”吗？ 皮亚诺公理

皮亚诺公理

关于整数的公理 ■对于加法与乘法封闭： ■加法与乘法满足交换律： ■加法与乘法满足结合律； ■乘法对加法满足分配律； ■加法和乘法各自有单位元素 (0和1) ■方程十x=O有整数解（称为a的逆元素，并可由此定义“减法”） ■如果c≠0，ac=bc-→a=b（消去律) ▣（基于1,2,3…}定义“正整教”和“大于”、“小于”）对任意☑，Q>0 a=0,和a<0三者必有其一，也仅有其一； ■任一正整数的非空集合必含最小元素（良序性）

关于整数的公理 ◼ 对于加法与乘法封闭； ◼ 加法与乘法满足交换律； ◼ 加法与乘法满足结合律； ◼ 乘法对加法满足分配律； ◼ 加法和乘法各自有单位元素（0和1） ◼ 方程a+x=0有整数解（称为a的逆元素，并可由此定义“减法”） ◼ 如果c0，ac=bc → a=b（消去律） ◼ （基于{1,2,3,…}定义“正整数”和“大于”、“小于”）对任意a，a>0, a=0, 和a<0三者必有其一，也仅有其一； ◼ 任一正整数的非空集合必含最小元素（良序性）

良序性与数学归纳法原理 First Principle of Mathematical Induction.Let S(n)be a statement about integers for n E N and suppose S(no)is true for some integer no.If for all integers k with k no S(k)implies that S(k+1)is true,then S(n) is true for all integers n greater than no. Second Principle of Mathematical Induction.Let S(n)be a statement about integers for n EN and suppose S(no)is true for some integer no.If S(no),S(no+1),...,S(k)imply that S(+1)for k no,then the statement S(n)is true for all integers n greater than no. Principle of Well-Ordering.Every nonempty subset of the natural num- bers is well-ordered

良序性与数学归纳法原理

间题3： 你能说说为什么归纳法原 理与良序性质是等价的吗？