离散数学精简讲义.doc

第一编 数理逻辑命题逻辑1.1命题符号化否定词，合取词，析取词，蕴含词，等值词若一个命题是一个简单陈述句，则称之为简单命题；由简单命题通过、这些联结词组成的命题称为复合命题；PQ是条件命题；PQ是双条件命题。1.2合式公式命题常元T，F命题变元P，P，.P 联结词辅助词（）这个字母表可记为（P，P，）,如不引起混淆，也可简记为。（P，P，）表示字母表（P，P，）上的所有字符串，包括空串；用表示上的所有非空符号串的集合。 合式公式：（1）命题常元或命题变元是合式公式；（2）若A，B是合式公式，则（A），（A），（AB），（AB），（AB）是合式公式；（3）只有通过有限次使用（1），（2）所得到的符号串才是合式公式。代入和替换：替换只要求对该子公式的某一出现或某几个出现进行替换，而不是对每一处出现都进行替换。1.3永真公式解释：设是含有 这n个命题变元的合式公式，对的一组真值赋值，称为对A的一个解释，记作I= ，其中取0或1，I( )= 。合式公式可分为：永真式，永假式，可满足式。逻辑恒等式： 永真蕴含式：1.4范式文字：命题变元或命题变元的否定称为文字，并称命题变元为正文字，命题变元的否定为负文字。基本和的归纳定义是：文字是基本和；若A，B是基本和，则AB是基本和。合取范式的归纳定义如下：基本和是合取范式；若A，B是合取范式，则（AB）是合取范式。主合取范式的归纳定义是：极大项是主合取范式；若A，B是主合取范式，则（AB）是主合取范式。 基本积的归纳定义是：文字是基本积；若A，B是基本积，则AB是基本积。析取范式的归纳定义如下：基本积是析取范式；若A，B是析取范式，则（AB）是析取范式。主析取范式的归纳定义是：极小项是主析取范式；若A，B是主析取范式，则（AB）是主析取范式。 1.5推理理论推理规则：附加规则化简规则MP规则拒取式析取三段论假言三段论合取引入构造二性难 证明方法：前件假证明法后件真证明法直接证明法间接证明法分情况证明法附加前提证明法反证法 公理系统一般由下列几部分组成：初始符号：它们是不经定义而直接使用的符号；形成规则：确定定义在初始符号上的哪些符号串是合式公式；公理集：它们是不经证明而被认为是恒真的命题；推理规则：规定如何从公理和前面已经推导出的合式公式经过符号变形而推出其它公式。命题逻辑的公理系统L的定义如下：初始符号：形成规则：P是合式公式；若A是合式公式，则（A）是合式公式；若A和B是合式公式，则（AB）是合式公式；只有通过有限次使用得到的符号串是合式公式。公理集：（L ）（A（BA）；（L ）（A（BC）（AB）（AC）；（L ）（A）（B）（BA）。推理规则：从A和（AB）可推出B。证明：L中的证明是合式公式的一个有穷序列A ，A ， A ,其中A 或者是公理，或者是序列中其前的某两个合式公式经MP规则得到。并称该证明人是A 是在L 中的证明，称A 是L的定理，记作。演绎：设是合式公式集，L中的从推出A 的一个演绎是合式公式的一个有穷序列A ，A ，A ，其中A 或者是公理，或者是中的一个合式公式，或者是序列中其前的某两个合式公式经MP规则得到。中的合式公式称为假设。L的演绎定理：推论：设A，B，C是L的任意合式公式，则AB，BC AC。1.6联结词的全功能集设C 是联结词的集合，若任何公式均可由仅含C中联结词的公式等价的表示，则称C是联结词的全功能集；若从C中任意去掉一个联结词，则C不是全功能集，则称C是联结词的极小全功能集。2. 一阶逻辑2.1命题符号化在一阶逻辑中，我们把所讨论的对象称为个体，用来表示个体的符号称为个体词。若一个个体词表示一个特定个体，则称之为个体常元；若一个个体词泛指任何一个个体，则称之为个体变元；个体变元的取值范围称为个体域或论域。在简单命题中，表示个体的性质或个体之间联系的词称为谓词，表示数量的词称为量词，量词一般有两种：全称量词和存在量词2.2合式公式一阶谓词逻辑的字母表为个体常元a,b,c,个体变元x,y,z,函数符号f,g,h,(n元函数f可记为f )谓词符号P，Q，R，联结词量词 辅助符号（）项的归纳定义如下：个体常元和个体变元是项；若t ,t ,t ,是项，则f (t ,t ,t,)是项；只有通过有限次使用（1）和（2）所得到的符号串是项。设t ,t ,t ,t 是项，则称P (t ,t ,t ,t )为原子公式。合式公式的归纳定义如下：原子公式是合式公式；若A，B是合式公式，则（A），（AB），（AB），（AB），（AB），xA, xA是合式公式；只有通过有限次使用（1），（2）所得到的符号串才是合式公式。在合式公式QxA中，称A为Q的辖域，其中Q为或。变元x在Qx及Q的辖域中的出现称为x 的约束出现，并称x为约束变元；x的非约束出现称为x的自由出现，并称x 为自由变元。换名规则：若要将约束变元x改为y，则将Qx中的x 及在Q的辖域中自由出现的x均改为y;y不在限制x的量词的辖域中出现。2.2永真公式合式公式G 的一个I是由一个非空集合D （称为I的论域）和如下一组规则组成：对G中的每一个个体常元和自由个体变元指定D 中的一个元素；对G中的每一个n元函数，指定D 上的一个n元函数；对G中的每一个n元谓词符号，指定D 上的一个n元谓词。永真式：2.4范式称下述形式的公式为前束范式：Q x Q x Q x Q B,其中Q 为或，B是不含任何量词的公式。并称Q x Q x Q x Q 为前束词，称B为母式。Skolem范式设前束范式为Q x Q x Q x Q x B。若Q x 为x (1tr),那么当Q x 左边无全称量词时，用B中未出现的个体常元a支代替B中x 的所有出现，并删支出Q x ；当Q x 左边的所有全称量词为Q x Q x ,Q x (1 )时，取B中未出现的s元函数符号f ，用f （x ,x ,x ）代替B中x 的所有出现，并删支Q x 。这种消去量词的变换称为Skolem变换。2.5推理理论全称指定规则（US规则）：存在推广规则（EG规则）：存在指定规则（ES规则）：全称推广规则（UG规则）：第二编 集合论第三章 集合3.1集合的基本概念及其表示法集合，N，I，Q，R，C设A是任意集合，|A|表示A所含有的元素的个数。若|A|=0，则称A是空集，记作 。若|A|是自然数，则称A是有限集。若|A|无穷大，则称A是无限集。集合的表示法:列举法按某一次序列出集合的全部或部分元素,并用一对花括号括起；描述法用谓词描述出集合元素的公共特征，其形式为S=x|P(x)；归纳定义法通常包括以下三步：基本步 S 非空且S 中的任意元素均是A的元素；归纳步给出一组规则，从A的元素出发，依据这些规则所得到的仍是A的元素；极小化若S的任意元素均是A的元素，并且S满足和，则S与A有相同的元素。元素可以多次出现的集合为多重集，无特别说明，集合均指一般集合，不是多重集。3.2集合的运算并： 交：差： 补：完全以集合为元素的集合称为集类，常用字母 表示。广义交： 广义并：环和： 环积：幂：设A是集合，则称x|xA为A的幂集，A的幂集即是由A的所有子集组成的集合。3.3 基本集合恒等式3.4容斥原理3.5集合的笛卡尔积 称=x,x,y为由x和y组成的有序二重组，也称为序偶。 设nI ,x ,x ,x 是n个任意的元素。若n=1,则令=x ;若n=2,则令=x ,x ,x ;若n2,则令=,x .称是由x ,x ,x 组成的有序n重组，称x (1in)是它的第i个分量。 设nI ,集合A ,A ,A 的笛卡尔积 A A A 定义为A A A =|aA ,i=1,2,3n.称n为该笛卡尔积的维数。若 A =A =A ,则记A A A A 为A 。笛卡尔积满足下列分配律：第四章 二元关系 设nI ，A ，A ，A 是n个集合，R A ，称R是集合A ，A ，,A 上的n元关系。若A =A =A =A,则称R是A上的n 元关系。当n=2时，称R是A 到A 的二元关系，A 称为R的前域，A 称为R的陪域，称dom(R)=x|xA R为R的定义域，称ran(R)=y|yA R为R的值域。若R,则说a与b有关系R，常用中缀法记为aRb; 若R,则说a与b没有关系R，常用中缀法记为aRb。由于任意集合均有两个平凡子集，即空集和集合自身，因此称A A A 上的关系为空关系，称A A A 为全域关系。A上的关系|xA称为A上的恒等关系，记为I 。 设R A ,R A .若n=m; ;集合R 和R 相等，则称关系R 与R 相等，记为R =R 。关系的表示集合表示法；关系矩阵表示法；关系图表示法。4.2关系的性质 设A是集合，RA A。若x(xAxRx),则称R是自反的；若x(xAxRx),则称R是反自反的；若xy(xAyAxRyyRx),则称R是对称的；若xy(xAyAxRyyRxx=y),则称R是反对称的；若xyz(xAyAzAxRyyRzxRz),则称R是传递的。4.3关系的运算 设A，B是集合，RA B，且SA B，则交RS，并RS，差R-S和补R均是A和B上的二元关系，且x(RS)yxRyxSy,x(RS)xRyxSy,x(R-S)xRyxSy,xRyxRy. 设A和B是集合，RA B，令RB A且R=|xRy，则称R是R的逆关系。 设A和B是集合，R A B（i=1,2），则R =R ；RR=RR；RR=RR；R-R=R-R；R=R；若RR，则RR。 关系的合成：设A，B和C是集合，RA B ，RB C ，R 与R 的合成关系是R RA C，且R R =|xAzCy(yBxR yyR z).合成运算不满足交换律，但是它满足结合律。 关系的幂：设A是集合，RA A，nN，则R的n次幂定义为R =I ，R =R R。 设A是集合，RA A。若RA A，且满足：R是自反的（对称的、传递的）；RR；若RA A且满足：R是自反的（对称的、传递的），RR,则R；那么称R是R的自反（对称、传递）闭包，记为r(R)(s(R),t(R)。 设A是集合，RA A，则R是自反的当且仅当r(R)=R；R是对称的当且仅当s(R)=R；R是传递的当且仅当t(R)=R。 设A是集合，R A A，则r(R)=RI ；s(R)=RR;t(R)= R. 设A是集合，R A A(i=1,2)，若R R ，则r(R) r(R);s(R) s(R);t(R) t(R); 设A是集合，R A A，若R是自反的，则s(R)和t(R)j自反的；若R是对称的，则r(R)和t(R)是对称的；若R是传递的，则r(R)传递的。 设A是集合，R A A，则rs(R)=sr(R);rt(R)=tr(R);st(R) ts(R).4.4等价关系和划分 设A是集合，R A A。若R是自反的、对称的和传递的，则称R是A上的等价关系，并且若aRb,则说a与b等价。 设R是集合A上的等价关系。对任何aA,称a =x|xAxRa为a关于R的等价类（有时简记为a），并且称a 为a 的代表元；若等价类个数有限，则称R的不同类的个数为R的秩，否则称R的秩是无限的，称a |aA为A关于R的商集，记为A/R。 设R是A上的等价关系，A= ，a,bA,则a= ;aRb当且仅当a=b;a=b或者a b= . 设集合A= ， （A）。若满足： ； 中任意两个不同元素不相交； =A；则称是A的一个划分，且称中的元素为划分块；若有限，则称 的不同划分块的个数为的秩，否则称 的秩是无限的。 设集合A= ，R是A上的等价关系，则A/R是A的一个划分。 设集合A= ，R 和R 是A上的等价关系，则R =R 当且仅当A/R =A/R 。等价关系可以诱导一个划分，一个等价关系所诱导的划分是惟一的。 设是非空集合A的划分，定义A上的二元关系R为： aRb当且仅当a和b同属于A的一个划分块。则R是A上的等价关系。 设集合A= ，是A的一个划分，R是A上的一个等价关系，则诱导R当且仅当R诱导。一个等价关系可以惟一诱导出一个划分，一个划分也可惟一确定一个等价关系。 设集合A= ，和 是A的划分，且它们诱导的等价关系分别为R和R，那么细分 当且仅当R R。 设集合A= ，和是A划分。若是A的划分，且 细分 和 ；若 细分 和，则 细分 ，则称 是 与的积。记为 .若是A的划分，且 和 细分 ；若 和 细分，则 细分 ，则称 是 与的和。记为 。 设集合A= ，和是A的划分，且它们诱导的等价关系分别为R 和R ，那么RR 诱导的划分是；t(RR)诱导的划分是。4.5序关系序关系是一类重要的二元关系，它提供了比较集合中元素的一种方法。 偏序关系：设A是集合，R A A。若R是自反的、反对称的和传递的，则称R是A上的偏序关系，并称是偏序集。偏序关系有时也称作半序或部分序关系，常用表示偏序关系。 覆盖：设R是集合A上的偏序关系，aA.若bA满足aRb且b=a;若xA使得aRx且xRb,则必有x=a或x=b.那么称b是a关于R的覆盖。 拟序关系：设A是集合，RA A。若R是反自反的和传递的，则称R是A上的拟序关系，并称是拟序集。 拟序关系是反对称的。 设A是集合。RA A。若R是偏序关系，则R-I 是拟序关系；若R是拟序关系，则RI 是偏序关系。 全序关系：设是偏序集，若xy(xAyAx yy x),则称是A上的全序关系到，并称为全序集。全序关系也称作线序关系，全序集也称作线序集或链。 良序关系：设是偏序集，若对任意的S， =SA,则S有最小元，那么称是A上的良序关系，并称为良序集。4.6相容关系 设A是集合，RA A。若R是自反的和对称的，则称R是A上的相容关系；若aRb,则称x与y相容，否则称x与y不相容。 设R是集合A上的相容关系。若 =CA，且a,bC,有aRb,则称C是R的一个相容类。若C是R的相容类，bC,则必有aC使得aRb,那么称C是R的一个极大相容类。 求极大相容类的方法：关系图法；关系矩阵法。5. 函数5.1函数的基本概念和性质 设X和Y是任意集合，fX Y.若x(xX!y(yYf),则称f是从X到Y的函数，记为f:XY.设f: XY,X= .定义RX X为x ,x X,x Rx 当且仅当f(x)=f(x),则易证F是X上的等价关系（称之为由f诱导的等价关系），并且由关系R确定的划分为f (y)|yYf (y)= .令g:XX/R,g(x)=x ,称g是由f诱导的规范映射。可见对给定的一个函数均可得到一个规范映射。 设X和Y是任意集合，则从X到Y的所有函数构成的集合记为Y ，即Y =f|f:XY.当一个函数是递归定义时，常需要验证函数是良定的(well-defined). 设f:XY.若f(X)=Y,则称f是满射的。若xx(xXf(x)=f(x)x =x ),则称f是单射的。若f既是单射的，又是满射的，则称f是双射的。 集合的的特征函数：设U是全集，AU。定义A的特征函数为 ：U0，1，（x）=5.2函数的合成 设f:XY,g:YZ,则f与g的合成关系f g是从X到Z的函数，并且对一切xX,f g(x)=g(f(x). 设f:XY,g:YZ,则若f和g是满射，则g f是满射；若f和g是单射，则g f是单射；若f和g是双射，则g f是双射。 设f:XY,g:YZ,则若g f是满射，则g是满射；若g f是单射，则f是满射；若g f是双射，则g是满射且f是单射。5.3逆函数 设f:XY是双射，则f的逆关系f是从Y到X的函数。 设f是从X到Y的双射，g是从Y到X的函数，则f =g当且仅当g f=1 且f g=1 . 设f:XY。若有g:YX使得g f=1 和f g=1 成立，则称g是f的逆函数，并称f是可逆的。 若有g:XY,使得g f=1 成立，则称g是f的左可逆函数，并称f是左可逆的。若有g:XY,使得f g=1 成立，则称g是f的右可逆函数，并称f是右可逆的。 设f:XY,X= ,则f是左可逆的当且仅当f是单射；f是右可逆的当且仅当f是满射；f是可逆的当且仅当f是双射，或当且仅当f既是左可逆的，又是右可逆的。5. 集合的基数6.1可数集和无限集 设S是任一集合，称S =SS的后继集。 自然数N的归纳定义是： N；若nN,则n N；若SN,且满足 S；若nS，则n S；则S=N。 若m,mN,nN使mn,则称m 小于m，记为mn. 设A和B是任意集合，若存在从A到B的双射，则称A与B是等势的，记为AB；若A与B不等势，则记为AB。 若有nN,使得N A，则称A是有限集，且称其基数为n,记为|A|=n; 若A不是有限集，则称A是无限集。 任何有限子集都不能与它的真子集等势 设A是任意集合。若NA，则称A是可数无限集，并称A的基数为（读作阿列夫零），记为|A|= 。有限集与可数无限集称为可数集或可列集；非可数集合称为不可数集。 可数集的任何子集都是可数集。可数个可数集的并集是可数集。若A和B是可数集，则A B是可数集。 实数集合的子集0，1不是可数无限集合。 设A是任意集合。若0，1A，则称A的基数为（读作阿列夫），并称A是具有连续统势的集合，记为|A|= 。 设A，B，C和D是任意集合，AB，CD，AC=BD= ，则ACBD.6.2集合基数的比较 设A和B是任意集合。若存在从A到B的双射函数，则称A和B具有相同的基数。 设A和B是任意集合，则|A|=|B|，|A|B|恰有一个成立。 设A和B是任意集合。若|A|B|,且|B|A|,则|A|=|B|。要证明A与B有相同的基数，只需找一个从A到B的双射即可。而此定理告诉我们，只要找一个从A到B的单射和一个从B到A的单射就能证明A与B有相同的基数。 下列三个条件是等价的：A是无限集；A有可数无限子集；A有与其自身等势的真子集。 若A是有限集，则|A| .若A是无限集合，则 |A|. 设A是任意集合，则|A| (A)|.5. 代数系统 设A为非空集合，nI ，函数f:A A称为A上的一个n元运算，n称为该运算的阶。特别地，A中的每一个元素称为A上的一个0元运算。 设。是集合A上的n元运算，S是A的非空子集，若a ,a ,a S,有。(a ,a ,a ) S，则称S关于运算。是封闭的。 设。是A上的n元运算，是 （A）的非空集合，若S ，S关于。封闭，则 关于。也封闭，即广义交保持封闭性。 设*是集合A上的二元运算。若a,bA，有a*