离散数学06 函数

离散数学是一门研究离散结构和离散对象的数学学科，它在计算机科学等领域扮演着重要的角色。

布尔函数和布尔代数是离散数学中的重要概念之一，它们在逻辑电路设计、计算机编程等方面具有广泛的应用。

布尔函数是一种将布尔域上的值映射为布尔域上的值的函数。

布尔域上的值只有两个：真和假。

布尔函数的输入和输出都是布尔值。

布尔函数可以通过真值表、函数表达式或者逻辑电路图表示。

常见的布尔运算有与运算、或运算、非运算等。

布尔函数可以定义在不同的布尔变量上，而布尔变量可以取真或假两个值。

通过组合不同的布尔运算，可以构造出复杂的布尔函数。

布尔代数是研究布尔函数性质和运算规则的代数系统。

布尔代数的基本操作有与运算、或运算、非运算等。

与运算、或运算和非运算是布尔函数的基本运算，在布尔代数中具有特殊的性质。

例如，与运算满足交换律、结合律和分配律；或运算满足交换律、结合律和分配律；非运算满足德摩根定律。

布尔代数还有很多其他的运算规则，如吸收律、零元律、幂等律等。

这些运算规则可以用来简化布尔函数，使其更加简洁明了。

布尔函数和布尔代数在逻辑电路设计中起着重要的作用。

逻辑电路是一种基础的电子电路，用来完成逻辑运算。

布尔函数可以用来描述逻辑电路的功能，布尔代数可以用来简化逻辑电路。

通过布尔函数和布尔代数可以设计出各种复杂的逻辑电路，如逻辑门、多路选择器、时序电路等。

逻辑电路在计算机硬件中广泛应用，是计算机工作的基础。

因此，研究布尔函数和布尔代数不仅有助于理解离散数学的基本概念，也对计算机科学和工程领域有着重要的实际意义。

此外，布尔函数和布尔代数在计算机编程中也具有重要的应用。

计算机程序是一系列指令的集合，通过执行这些指令实现特定的功能。

布尔函数可以用来描述程序中的条件和逻辑关系，判断某个条件是否成立，从而确定程序的执行路径。

布尔代数可以用来简化程序的逻辑表达式，使程序更加高效和可读。

在编程语言中，布尔变量和布尔运算是基础数据类型和基本运算符之一，它们与布尔函数和布尔代数密切相关。

下面先规定几个标准集合的基数： 1) 空集的基数为0。 2) 设n为一自然数，Nn为从1到n的连贯的自然数集合， Nn={1,2,3,…,n}，Nn的基数为n，|Nn|=n 。 3) 设N为自然数的全体，N={1,2,3,…},N的基数为ℵ0(读成 阿列夫零， ℵ是希伯莱文的第一个字母)。 4) 设R为实数的全体，R的基数为ℵ ,|R|= ℵ 。 • • 以上四项规定，对于空集及Nn的基数，实际上就是集 合中元素的个数，关于ℵ0及ℵ，下面将予探讨。 有了标准基数之后，我们可以对各种集合测量其基数。 测量的手段是以双射函数为主体的等价关系一等势。 比如说，一个集合与N等势，那么这个集合的基数为 ℵ0 。
定理6 设A及B为两个可数集，那么A×B为一可数集。 定理 推论1 推论 设A1,A2,A3,…,An为n个可数集，那么 × A是可数集。
i=1 i n
定理7 (0,1)开区间上的实数不是可数集。 定理 定理8 设A为一集Y的函数，若f 是双射函数，则f 的逆关系 f –1是从Y到X的双射函数。 定理2 定理 设f 是从X到Y的函数，g 是从Y到Z的函数，则复合关 系f οg是从 X到Z的函数，将f ο g记为g ο f 。 定理3 定理 设f 是从X到Y的函数，g 是从Y到Z的函数。 1）若f 和g是满射函数，则g ο f 是满射函数； 2）若f 和g是单射函数，则g ο f 是单射函数； 3）若f 和g是双射函数，则g ο f 是双射函数。 定理4 定理 设f 是从X到Y的双射函数， f –1是f 的逆函数，则 1) (f –1) –1 = f 2) f –1 ο f = IX 3) f ο f –1 = IY
定义3 定义 设 |X|=n，P是从X到X的双射函数，称P为X上的置 换，称n为置换的阶。 • 在n个元素的集合中，不同的n阶置换的个数为n!。 • 通常用下面的方法表示置换。 x1 x2 x3 … xn P = p(x ) p(x ) p(x ) … p(x ) 1 2 3 n • 若∀xi∈X 有 p(xi) = xi ，则称P是恒等置换。 • P的逆函数P-1可表示为 p(x1) p(x2) p(x3) … p(xn) P-1 = x1 x2 x3 … xn • 置换的复合与关系的复合相同。 1 2 3 1 2 3 1 2 3 3 2 1 2 1 3 3 1 2

一个十分重要的例子。
2020/3/14
计算机科学与技术学院
12
三、函数的合成运算
定义 考虑g：A→B，f：B→C是两个函数，则合成 关系f•g是从A到C的函数，记为 f•g：A→C，
称为函数g与f的合成函数。
显然，对任意x∈A，有 f•g(x)＝f(g(x))。
2020/3/14
计算机科学与技术学院
2020/3/14
计算机科学与技术学院
16
例
例1 设f：R→R,满足： 1）f＝{<x,x2>|x∈R}； 2）f＝{<x,x+1>|x∈R}。求f-1。
解 1）对任意x∈R，有f(x)＝x2与之对应，所以 f不是单射函数，即f非双射函数，因此f的逆函 数不存在。 2）因f是双射函数，所以f-1存在，且有： f-1＝{<x,x-1>|x∈R}。
计算机科学与技术学院
5
例2
设A＝{a,b}，B＝{1,2}，A×B＝{<a,1>,<a,2>,<b,1>,<b,2>}，
此时从A到B的不同的关系有24＝16个。分别如下：
R0＝Φ R1＝{<a,1>} R2＝{<a,2>} R3＝{<b,1>}；
R4＝{<b,2>}；R5＝{<a,1>,<b,1>} R6＝{<a,1>,<b,2>}
2020/3/14
计算机科学与技术学院
10
例2
设An＝{a1,a2,a3,…,an}是n个元素的有限集， Bn＝{b1b2b3…bn|bi∈{0,1}}，对An的每一个子 集S(即对任意S(An)),令

基本等值式1.双重否定律 A Û┐┐A2.幂等律 A Û A∨A, A Û A∧A3.交换律A∨B Û B∨A，A∧B Û B∧A4.结合律(A∨B)∨C Û A∨(B∨C) (A∧B)∧C Û A∧(B∧C)5.分配律A∨(B∧C) Û (A∨B)∧(A∨C) （∨对∧的分配律）A∧(B∨C) Û (A∧B)∨(A∧C) （∧对∨的分配律）6.德·摩根律┐(A∨B) Û┐A∧┐B ┐(A∧B) Û┐A∨┐B7.吸收律A∨(A∧B) Û A，A∧(A∨B) Û A8.零律A∨1 Û 1,A∧0 Û 09.同一律A∨0 Û A，A∧1 Û A10.排中律A∨┐A Û 111.矛盾律A∧┐A Û 012.蕴涵等值式A→B Û┐A∨B13.等价等值式A«B Û (A→B)∧(B→A)14.假言易位A→B Û┐B→┐A15.等价否定等值式A«B Û┐A«┐B16.归谬论(A→B)∧(A→┐B) Û┐A求给定公式范式的步骤(1)消去联结词→、«(若存在)。

(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。

(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。

推理定律--重言蕴含式(1) A Þ (A∨B) 附加律(2) (A∧B) Þ A化简律(3) (A→B)∧A Þ B假言推理(4) (A→B)∧┐B Þ┐A 拒取式(5) (A∨B)∧┐B Þ A析取三段论(6) (A→B) ∧ (B→C) Þ (A→C) 假言三段论(7) (A«B) ∧ (B«C) Þ (A « C) 等价三段论(8) (A→B)∧(C→D)∧(A∨C) Þ(B∨D) 构造性二难(A→B)∧(┐A→B)∧(A∨┐A) Þ B 构造性二难(特殊形式)(9)(A→B)∧(C→D)∧(┐B∨┐D) Þ(┐A∨┐C) 破坏性二难设个体域为有限集D={a1,a2,…,an},则有（1）"xA(x) Û A(a1)∧A(a2)∧…∧A(an)（2）$xA(x) Û A(a1)∨A(a2)∨…∨A(an)设A(x)是任意的含自由出现个体变项x的公式，则（1）┐"xA(x) Û $x┐A(x)（2）┐$xA(x) Û "x┐A(x)设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1） "x(A(x)∨B) Û "xA(x)∨B"x(A(x)∧B) Û "xA(x)∧B"x(A(x)→B) Û $xA(x)→B"x(B→A(x)) Û B→"xA(x)（2） $x(A(x)∨B) Û $xA(x)∨B$x(A(x)∧B) Û $xA(x)∧B$x(A(x)→B) Û "xA(x)→B$x(B→A(x)) Û B→$xA(x)设A(x)，B(x)是任意的含自由出现个体变项x的公式，则（1）"x(A(x)∧B(x)) Û "xA(x)∧"xB(x)（2）$x(A(x)∨B(x)) Û $xA(x)∨ $xB(x)全称量词“"”对“∨”无分配律。