离散数学教程-王元元-第0章 准备知识.pptVIP

离散数学 第0章 准备知识 第0章 准备知识 0.1.1 集合 例0.1（1）北京大学全体学生 （2）全体正整数 （3）本书中所有汉字 （4）获1921年诺贝尔物理学奖的科学家 （5）上海市市东中学所有班级 （6）好书的全体 （7）方程 x(x2-2x+1)=0 的所有根 （8）方程 x2 +x+1=0 的根 （9）满足方程 x2 + y2 =1 的平面直角坐标系中点的坐标 （10）满足方程x2 + y2 =1的平面直角坐标系中的点的坐标 0.1.1 集合 对象：称元素或成员 具体的或抽象的客体 单一的客体或客体的序列。 集合族：所有成员均为集合的集合 表示：集合——大写字母A，B，C 等 元素——小写字母a,b,c等 当对象a是集合A的成员时，称a属于A，记为a?A 当对象a不是集合A的成员时，称a不属于A，记为a?A 正规原理：集合理论约定，对任何对象、集合A , A?A。 0.1.2 命题与谓词 命题：对确定事物作出判断的陈述句。 真值：当判断正确或符合客观实际时，称该命题真（true）， 否则称该命题假（false）。 真值“真、假”常用数字“1、0”来表示。 排中律：命题或真、或假，但不能兼而有之。 0.1.2 命题与谓词 例0.2 （1）雪是白的。 （2）2+2=5 （3）陈胜、吴广起义的那天杭州下雨。 （4）第30届奥林匹克运动会开幕时伦敦天晴。 （5）大于2的偶数均可分解为两个质数的和（哥德巴赫猜想）。 （6）火星上有生物。 （7）好痛快啊！ （8）您身体好吗？ （9）我说的这句话（例0.2之（9））假。 （10）x≤0 0.1.2 命题与谓词 断言：？？ 谓词： 断言中关于对象基本性质或相互关系的语言成分。 表示： 带有空位的大写拉丁字母（或字母串）。 如：P( )表示“?小于等于零” QR( , ) 表示“?与?的平方和等于1” ADD( , , ) 表示“?与?的和等于?” 常用变元去填空位，如P(x)、 QR(x, y) 、ADD(x,y,z) n元谓词：含有n个空位（或变元）的谓词。 当谓词的空位或变元处填以确定的对象后，便可判别其真假， 即可得到一个命题。 0.1.2 命题与谓词 例0.3 R(x) ： x是实数 R(3)是真命题。 L(x,y) ： x小于y L(3,2)是假命题。 B(x,y) ： x生于y B(董青，青岛) 真假是确定的。 ADD(x,y,z) ： x + y = z ADD(3,5,8) 是真命题。 0.1.3 集合的表示 列举法：将集合A中元素一一列举在一个大括号中，或列出 足够多的元素以反映A中成员的特征，形如 A＝｛a1,a2,…,an｝或A=｛a1,a2,a3,…｝ 描述法：将集合A中元素的特征用一个谓词来描述，形如 A =｛x ? P(x)｝或 A =｛x ：P(x)｝ B =｛x1,x2,…,xn ? Q(x1,x2,…,xn)｝ 或 B =｛x1,x2,…,xn :Q(x1,x2,…,xn)｝ 概括原理：每一个谓词确定一个集合。 0.1.3 集合的表示 例0.4 常用集合及其表示： （1）{0,l}＝{x?TV(x) } （2）自然数集合N={0,1,2,3,…}={ x?NN(x) } 正整数集合I+={1,2,3,…}={ x?IN(x) } （3）整数集合I＝{…,-2,-l,0,l,2,…}=｛x?INTEG(x)｝ （4）前n个自然数的集合 Nn＝{ 0,1,2,…,n-1 }= { x?NN(x) 且 x?n } （5）前n个自然数集合的集合={ {0}, {0,1}, {0,1,2},… } ={