离散数学教程-王元元-第8章 可计算函数.pptVIP

离 散 数 学 第 8 章 可计算函数 第 8 章 可计算函数 8.1 函数概念的拓广 定义8.1 设f? X?Y, 称f为X到Y的一个偏函数，如果f满足下列条件： 对任意x?X， y1，y2?Y，若x,y1?f，x,y2?f，则y1=y2 。 偏函数的定义中取消了定义域等于前域的要求，保留了单值性 要求。对于x?X，若无y?Y，使x,y?f 时，称f在x处无定义，记为 f(x)=↑或 f(x)↑。 据定义8.1可知，一切函数均为偏函数，但反之不然。 当f为偏函数却非函数时，称f为真偏函数。 8.1 函数概念的拓广 （1） y = f(x) = ， y = g(x1,x2) = 规定的f，g都是实数集合上的真偏函数。 （2）当Y= ?，X ? ?时，X到Y的空关系为一真偏函数。 8.1 函数概念的拓广 （3）以下PASCAL程序定义了一个真偏函数 function f (x:integer) : integer; var y : integer ; begin y := 1 ; while(x 0) begin x := x – 2 ; y := y ? 2 end ; return y end 8.1 函数概念的拓广 例8.2 对例8.1 (1)中 y = f(x) = ，y = g(x1,x2) = 规定 f(x) = 0 当x 0 ; g(x1,0) = 0 后所得的f，g均为实数集上的函数。 反之，将f 限制于非负实数集合，将g限制于非零实数集 合，也都可以得到相应的函数。 8.2.1 初等函数集 本原函数 (1) 一元后继函数 (2) n元常值函数 （m为一确定的自然数，n为确定的正整数） (3) n元投影函数 （m≤n，m，n为正整数） 8.2.1 初等函数集 对函数的操作 (a) 函数的合成操作 设 为n元函数， , ┅ , , 是n个一元 函数，那么 称为 与 , ┅, , 的复合函数， 这一过程称为函数的合成操作。 8.2.1 初等函数集 对函数的操作 (b) 函数的迭加操作 设 为一元函数，定义 = = + + ? + 称 为迭加操作。( 就是大家熟悉的 ） 8.2.1 初等函数集 对函数的操作 (c) 函数的迭加操作 设 为一元函数，定义 = = ? ? ? ? 称 为迭乘操作。 8.2.1 初等函数集 定义8.2 归纳定义初等函数集： (1) 本原函数是初等函数。 (2) 二元差函数是初等函数： (3) 如果 与 , ? , 都是初等函数，那么它们 的合成 也是初等函数。 (4) 如果 是初等函数,那么 = ， = 也是初等函数。 (5) 只有有限次使用上述条款确定的函数是初等函数。 8.2.1 初等函数集 EF1. 二元乘函数 注意：i从0到x共取x+1个值。右边是常值函数的迭加与投影函数 合成于二元差函数。可用简单的数字验证上述定义： 8.2.1 初等函数集 EF2. 二元加函数 右边先是两个后继函数合