离散数学教案设计(编辑修改稿)

离散数学教案设计(编辑修改稿)内容摘要：

: 1 2 ...f A A A n B   ，称 f 为1, 2,...,A A An 到 B的 n元运算。 A到 B的 n 元运算，或 A 上的 n元运算： A上的 n元封闭运算 （代数运算） ： ， 1, 2,... ,x x xn A有 ( 1, 2 , ..., )f x x x n y A 例：判定取绝对值运算 ||、加法运算 +、取大运算 max是否是自然数集合 N(Z)上的代数运算。 解： xN x x N   ,x y N x y N     1 , 2 , . . . m a x ( 1 , 2 , . . . )x x x n N x x x n N    例：判定减法运算 ,取小运算 min是否是 自然数 集合 N 上的代数运 算。 解： 例：判断数的加法运算是否是集合 A={2n |n∈ N}上的代数运算。 解： 122 2 6 2n   例 ： 将 十进制数 273 转换成八进制 解： 273=34 8 1 , 34 4 8 2   , 22 7 3 3 4 8 1 ( ( 4 8 ) 2 ) 8 14 8 2 8 1             BAAAf n   ...:AAAAf n   ...: 15 8273 (421) ② 模运算 定义： : , ( ) ( m o d )f Z N f x x m， (mod )xm是使 ,0x qm r r m   成立的整数 r,即 x除以 m 的余数。 例 ： 16(mod 3)、 8(mod 5)、 9(mod 2) 模 m 加法，模 m乘法 ( ) ( m o d )( ) ( m o d )mmx y x y mx y x y m     例： m=5, 553 ( 5 ) 3 , 3 ( 5 ) 0      ③最大公约数，最小公倍数 ,mn Z若 d|m 且 d|n,则 d 是 m,n 的公约数，用 gcd(m,n)表示 m,n 的最大公约数 ,mn Z若 m|d且 n|d，则 d是 m,n 的公倍数，用 lcm(m,n)表示 m,n 的最小公倍数。 注： Gcd 与 lcm分别记为 [,]和（，） gcd(m , n)= gcd(|m| ,| n|)且 lcm(m, n)=lcm(|m|, |n|) 素因数分解 ：（对于大于 1 的正整数 n 都可以分解成一些素数乘积） Euclid 算法 例 119 若 gcd(m,n)=1,称 m和 n 互素。 欧拉函数 ()n ： 表示小于等于 n 且与 n 互素的正整数的个数 ④运算表 给定集合 A，则集合 A 上的 1 元或 2 元运算可以用运算表来表示 例： A={a,b,c},* * a b c a b c a b a b c c b c a 思考： A 上的封闭的 1 元， 2 元， 3 元运算的个数是多少。 1 2 1 21 , 1 2 , 21 , 1 2 , 2111 2 1 2m in ( ) m in ( ) m in ( , )12m a x ( ) m a x ( ) m a x ( , )12,( , )g c d ( , )( , )kkkkkkrsr r s sk k kr s r s rskr s r s rskm p p p Z n p p p Zp r sm n p p plc m m n p p p     为 素 数 ， 为 非 负 整 数21 1 1 2 1 2 2 1 1 1, 0 , , 0 , . . . , 1g c d ( , ) k k k k k k kkm q n r r n n q r r r r n r q r r r q rr m n m x n y                 16 33 39 327 (2)运算的性质 ①对合性 （ 5 分钟） 定义 ： 设 *是 A 上的一元代数运算， 例： : ( )x R x x     11( ) , ( )TTA A A A  xx。 ②幂等性 （ 5 分钟） 幂等元： *,x x x x A 定义 ： A 中的每个元素对于 *都是幂等元 例 ： * 1 2 3 1 1 2 3 2 2 3 2 3 3 1 3 例： ,?R ③交换性 （ 5 分钟） 定义 ： 对于 A 上的二元运算 *, ,x y A,均有 例 ： R 上的 +具有交换性 R 上的 ，映射的复合运算 fg? ④结合性 （ 5 分钟） 定义 ： 例 :映射的复合运算 ( ) ( )f g h f g h 具有 结合 性 R 上的 +具有 结合 性 R 上的。 ⑤单位元素 （幺元素） （ 5 分钟） 定义 ： 对于 A 上的二元运算 *， e ，使得对于 x 例： R 关于加法运算 +的单位元素是 0 R 关于乘法运算  的单位元素是 1 R 关于减法运算 的单位元素是。 定理 13：若 A 关于 * 有单位元素，则单位元素是唯一的 证明：设 e1,e2 是 A 关于 *的单位元素，则 e1=e1*e2=e2 ⑥零元素 （ 5 分钟） 定义 ： 对于 A 上的二元运算 *，  ，使得对于 x 例 :R 关于乘法运算  的零元素是 0 .,)( Axxx ,xyyx ).()(:, zyxzyxAzyx .xxe .xex . x .x 17 R 关于减法运算 的零元素是。 R 关于加法运算  的零元素是。 定理 14：若 A 关于 * 有零元素，则零元素是唯一的 证明：设 e1,e2 是 A 关于 *的 零 元素，则 e1=e1*e2=e2 ⑦逆元素 （ 5 分钟） 前提： A 关于 二元 运算 *有单位元素 e 定义 ： ,x A y A   ，使得： 例 ： R 上的加法运算 +： x+(x)=0=(x)+x R 上的乘法运算  ： 110 , 1x x xxx     注： 逆元不一定存在，存在不一定唯一，参见表 15 定理 15： 若 A 关于 *运算有单位元素为 e 且 *运算满足结合律，若对于 A中的 x 有左逆元 y 与右逆元 z，则 y=z,此逆元唯一 证明： y*x=e,x*z=e y=y*e=y*(x*z)=(y*x)*z=e*z=z ⑧消去性 （分钟） 定义 ： 若 A 关于 *有零元，则记为  ， 对于 ,x y z A， 若 x  例 131 Z上的加法运算 +和乘法运算 均满足消去律 . ⑨分配性 （ 5 分钟） 定义 ： *, 是 A上的两个二元运算， 对于 ,x y z A 则称 *关于 是可分配的 ⑩吸收性 （ 2 分钟） 定义 ： *, 是 A 上的两个二元运算， 对于 ,x y z A 则称 *关于 是可吸收的 ○⒒ 德摩根律 （ 3 分钟） 定义 ：  是 A上的一元运算， *, 是 A 上的两个二元运算，对于 ,x y z A 4. 教学小结 （ 3 分钟） 本讲首先介绍了运算的定义并介绍了几种常用的运算，接着介绍了 运算的 性质： 对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律， 并结合之前 所学 知识讲解运算的性质。 .eyx  .exy .zyzxyx .zyxzxy ).()()( zxyxzyx   ).()()( xzxyxzy  .)( xyxx   .)( xxxy ).()()( yxyx   ).()()( yxyx   18 四、 作业与实验 （ 2 分钟） 1. 书面作业： 习题 ： 8 2. 上机作业：无 19 第 四 讲： 集合、 映射和运算 （ 四 ） 一、教学目标 的各种 运算 各种 集合运算 所满足 的 性质 ，集合的基数，可数集合等概念 二、重点与难点分析 ： 集合 的运算 —— 并、交、补、差、对称差 集合运算 性质 ： 集合运算等值式的证明， 集合的对等 、 基数 三、 教学内容与教学过程 （ 5 分钟） 运算的定义 运算的性质 ：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律 、开始第 四 讲 本讲知识点概括 (1)集合的运算 ① 并运算 （ 15分钟） 定义 ： 定理 116： AB 是包含 A和 B的最小集合 ,C A C B C A B      定理 117：并 运算满足的性质： A B B A   （交换 律 ） ( ) ( )A B C A B C    （结合 律 ） A A A（ 幂等 律 ） A A A    （  是 ∪运算的 单位元素 ） A U U A U   （ U 是 ∪运算的 零元素 ） 例 138:设 f : A  B, X, Y  A, 则 证明： ( ) ( ) ( )f X Y f X f Y   }.|{ BxAxxBA  或 20 证明： ( ) ( )( ) ( )( ) ( ) ( )X X Y f X f X YY X Y f Y f X Yf X f Y f X Y            ( ) ( ) : ( )( ) ( )( ) ( )( ) ( )( ) ( ) ( )b f X Y a X Y b f aa X b f a f Xa Y b f a f Yb f X f Yf X Y f X f Y                  ② 交运算 （ 15分钟） 定义 ： { | B }A B x x A x   且 定理 118： AB 是包含在 A 和 B的最大集合 C A , C B C A B       定理 119：交运算满足的性质： A A A（ 幂等 律） A B B A   （交换律） ( ) ( )A B C A B C    （结合律） AA     （  是  运算的零元素） A U U A A    （ U是  运算的单位元素） 例 ： 定理 120：并运算与交运算之间满足的性质： 例 141： A B A B A A B B       证： AB  A B B ,B A Bx A B x A B      由 于 A B x A B B   A B B      A A B=B A B ( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )A A B AA A B AA B C A B A CA B C A B A C                      对 可 吸 收对 可 吸 收对 可 分 配对 可 分 配 21 ③ 补运算 （ 10分钟） 定义 ： 例 142：（ A的补集依赖于全集 U的选取） A={a,b,c} U={a,b,c,d} {}Ad { , , , , { , } , { , } , { { } } } { , { , } , { , } , { { } } }U a b c d a b b c c A d a b b c c   定理 121： A A UAA  定理 122：德。