【离散数学】知识点典型例题整理
【半群】G非空，·为G上的二元代数运算，满足结合律。
【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。
【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1
【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。
【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。
【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。
n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）}
【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。
求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪…
【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立）
Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。
1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。
2设G为有限群,元数为n,对任意a∈G，有an=1。
3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。
4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。
5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。
【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。
设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。
【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。
【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。
N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。
设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。
【环】R非空，有加、乘两种运算
a+b=b+a2）a+（b+c）=（a+b）+c，
3）R中有一个元素0，适合a+0=a，
4）对于R中任意a,有-a,适合a+(-a)=0，
5）a（bc）=（ab）c，
6）a（b+c）=ab+ac,（a+b）c=ac+bc。
交换环：乘法适合交换律ab=ba 。
含壹环：R不只有一个元素且有一个元素1适合1a =a1=a。1不为零。
无零因子环：不含a，b∈R，a≠0，b≠0,但ab=0，a，b为零因子。又叫消去环。
消去环：消去律成立。不为0的元素在加法下的周期或为0或为质数。
整区：有壹无零因子的交换环。
体：如果去掉0，环R的其余元素作成一个乘法群。体有壹而且无零因子，其中任意非零元素有逆。域是交换体。单纯环：R除自己和{0}外没有别的理想。
【子环】环R的非空子集S在R的加法和乘法下仍是环。若a∈S，b∈S，则a-b∈S;若a∈S，b∈S，则ab∈S。对于乘法群，其壹恒与子群的壹一致；但对于环，其壹却未必与子环的壹一致。
【理想】环R的子集N (理想子环)
N非空；若a∈N，b∈N，则a-b∈N;若a∈N,х∈R,则aх∈N,хa∈N。
1理想一定是子环，但子环未必是理想。2任意体R只有平凡理想。
3设R是有壹的交换环,a∈R,则aR={ar|r∈R}是R的理想，且包含a。
【主理想（a）】R是有壹的交换环，a∈R,则aR称为由a生成的。(0)={0},(1)=R。环R的主理想（a）是R中包含a的理想中最小的理想。
【合同】设R是环，N是理想。a，b∈R，如果a-b=n∈N，或a=b+n，n∈N，则称a和b模N合同，记为a≡b（mod N）。
在环R中，对于模N，有：反身性：a≡a;对称性：若a≡b，则b≡a;传递性：若a≡b，b ≡c，则a≡c;加法同态性：若a≡b，c≡d，则a±c≡b±d。乘法同态性：若a≡b，c≡d，则ac≡bd。
【环同态】R是环，S有加乘两种运算，R到S中的一个映射σ（a+b）=σ（a）+σ（b），σ（ab）=σ（a）σ（b）。R到R′同态，记为R～R′。
【环同构】σ是环R到系统R′上的一个一对一的同态映射。R与R′同构,记为R?R′。
若σ是R到S中的一个同态映射,则R的映象R′=σ（R）也是一个环,σ（0）就是R′的零0′,σ(-a)=-σ（a）。若R有壹而R′不只有一个元素,则R′有壹而且σ（1）就是R′的壹1′;若a∈R有逆,则σ（a）在R′中有逆而且σ(a-1)就是σ(a)-1。
【理想】同态映射σ的核N是R的一个~.设a′是R′的任意元素,则a′的逆映象σ-1(a′)={a ∈R∣σ(a)=a′}是N的一个剩余类。
1按照剩余类的加法和乘法，R对于理想N的所有剩余类的集合R∕N是一个环，
2规定σ（a）= a+N，则σ是R到R∕N上的一个同态映射，其核为N。R∕N叫做R对于N 的剩余环
3设环R同态于R′：R～R′于是R与N之间的子环与R′的子环一一对应，大环对应大环，小环对应小环，理想对应理想。
【极大理想】N ? R，而R与N之间没有别的理想。极大理想不唯一
若N ? R，则N是R的极大理想必要而且只要R∕N是单纯环。
【域】任意有壹的交换的单纯环。任意域F是有壹的交换的单纯环。
设R是有壹的交换环，N是R的理想。于是，R∕N是一个域，必要而且只要N是一个极大理想。任意域F的特征P是零或一质数。
【最小域/素域】没有真子域的域，特征P的最小域为R (p为0或质数)。
设p为质数或等于0，特征为p的任意域F包含Rp为其最小子域。
域F上х的多项式作成的环F[х]是一个【整区】。
【多项式】1以х-α除?(х)所得的余式等于?（α）。 2 х-α∣?(х),当且仅当α是?(х)的根。3说α是非0多项式?（х）的k重根，如果（х-α）k∣?（х），（х-α）k+1不整除?（х）。4若α是非常数多项式?（х）的k重根，则它至少是?′（х）的k-1重根。5α是?（х）的重根，当且仅当它是?（х）和?′（х）的公共根。6复数域上任意非常数多项式必有根。
7实数域上，质式只能是一次式或二次式。二次式aх2+bx+c是质式，当且仅当判别式b2-4ac<0。
设?（х）= a0хn + a1хn-1 … + an 是整系数多项式，若对质数p，p不整除a0，p∣a1，…，p∣an，p2不整除an，则?（х）在有理域上【不可约】。
设?（х）= a0хn + a1хn-1 + … + an 是整系数多项式。若有理数b∕c是?（х）的根，其中b和c是互质的整数，则b∣an，c∣a0。
【求有理根】1.分别找a0和an的所有因子ci,bj;2.找互质对（ci,bj ）；3.判断ci/bj是否为根；
4.判断重根。
复数α称为一个代数数，如果α是某个有理系数非0多项式的根。若α不是任何有理系数非0多项式的根，则α称为一个超越数。
复数域中恰有n个n次单位根。它们在乘法下作成一个n元循环群
Φ1（х）=х-1 Φ2（х）=х+1
Φ3（х）=х2+ x + 1Φ4（х）= x2 + 1
х12-1=Φ12Φ6Φ4Φ3Φ2Φ1，
х6-1= Φ6Φ3Φ2Φ1
相除得х6+1 = Φ12Φ4
设n不是F的特征的倍数，并设Φn（х）在F中有根。于是，F中恰有n个n次单位根，它们在乘法下作成一个n元循环群，其?（n）个生成元素恰是Φn（х）的所有的根。
F中的q-1个非0元素恰是所有q-1次单位根，而F的所有q个元素是多项式хq-х的所有的根。
F的q-1个非0元素在乘法下作成一个q-1元循环群，其?（q-1）个生成元素恰是Φq-1（х）的所有的根。
【有限域】的元数必为pn的形式，其中p为其特征。如果同构的域看作是一样的，则对任意q=pn恰有一个q元有限域，
【格】部份序集(L，≤），对于任意a，b∈L，L的子集{a，b}在L中都有一个最大下界（记为inf{a，b}）和一个最小上界(记为sup{a，b})。
一个序集是一个格，但是，不是所有部份序集都是。
设（L，≤）是格,S是L的子集,即S?L，如果（S，≤）是格，则称（S，≤）是格（L，≤）的【子格】。
设L是一个集合,×,⊕是L上两个二元代数运算，如果这两种运算对于L中元素满足：（1）交换律：a×b=b×a，a ⊕ b=b ⊕ a。（2）结合律：a×（b×c）=（a×b）×c，a ⊕（b ⊕ c）=（a ⊕ b）⊕c。（3）吸收律：a×(a ⊕ b)=a,a ⊕(a×b)=a。则称此代数系统（L,×,⊕）为一个【格】。
集合L中的【部份序关系】R与其逆关系R-1,称为互相对偶的两个关系。
对任意x，y∈L，xR-1y?yRx。若R是部分序关系，则R-1也是。
【格同态】（L，×，⊕）和（S，∧，∨）是个格，L到S的映射g对任意a，b∈L，有g （a×b）= g（a）∧g（b）g（a⊕b）= g（a）∨g（b）
若g是L到S上的同态映射，且是一对一的，则称g是格【同构映射】。
【有界格】格（L，≤）有一个最大元素(记为1)和一个最小元素(记为0)，亦即，对任意a ∈L，都有0≤a≤1，0，1称为格（L，≤）的界。
在有界格(L,×,⊕,0,1)中，一个元素b∈L,称为元素a∈L的【余元素】,如果a×b = 0，a ⊕ b = 1。
在有界格（L,×,⊕,0,1）中，任意元素a可以有余元素，也可以没有余元素；如果有余元素，则可以有一个或一个以上的余元素。
有界格（L,×,⊕,0,1）说是一个【有余格】，如果对L中每一个元素，都至少有一个余元素。格（L，×，⊕）称为【分配格】，如果对任意a，b，c∈L，恒有a×（b⊕c）=（a×b）⊕（a ×c），a ⊕（b×c）=（a⊕b）×（a⊕c）
设格（L，×，⊕）是一个有余分配格，则对任意a∈L，a的余元素a′是唯一的。
设（L，≤）是一个格，对任意a，b，c∈L，如果a≤b，都有a⊕（b×c）= b×（a⊕c）则称（L，≤）为【模格】。任意一个分配格都是模格，但模格不一定是分配格。
对任意a，b，c∈L，如果a≤b，a×c=b×c，a⊕c=b⊕c,则必有a=b。
一个有余分配格是一个布尔代数。
【布尔代数】设B是一个至少含有两个不同元素的集合，·，+是定义在B上的两种代数运算，如果对任意a，b，c∈B，满足下面公理：
H1：a·b = b·a，a+b = b+a
H2：a·（b+c）=（a·b）+（a·c），
a+（b·c）=（a+b）·（a+c）。
H3：B中有元素0和元素1,使得对任意a∈B,有a·1 = a，a+0 = a。
H4：对任意a∈B，有∈B，使得a·=0，a+ =1。则（B，·，+，ˉ，0，1）是一个布尔代数。有限布尔代数的基底必是此代数的所有极小元素；反之，此代数的所有极小元素必然做成此代数的基底。
举例说明不要求可除条件而要求消去条件，即要求由aχ=ay可推出χ=y，由χ·a=y·a可推出χ=y，则G不见得是一个群，若G有限怎么样？
解：例如，全体自然数在普通乘法下，适合消去律，但不是群。若G={a1，a2，…an}，用a 右乘G中各元素得a1a，a2a，…，ana必不相同，否则若aia=aja (i≠j) ，由消去条件有ai=aj，矛盾。对任意b∈G，必有ai，使aia=b，因之方程xa=b有解。同理可知ay=b有解。故G是群。
设K和H都是群G的子群，试证明：若H·K是G的子群，则K·H = H·K。
证明：对任意的k·h∈K·H,
(k·h)-1=h-1·k-1∈H·K,由于H·K是G的子群,所以((k·h)-1)-1∈H·K，因此K·H?H·K。对于任意的h·k∈H·K，(h·k)-1∈H·K，即存在h1∈H，k1∈K使得(h·k)-1=h1·k1，所以h·k=(h1·k1)-1=k1-1 ·h1-1 ∈K·H，因此H·K? K·H。由集合论知识知K·H = H·K。
任意置换σ恰有一法写成不相杂的轮换乘积。
证明：先证σ可以写成不相杂的轮换的乘积，取任意a1∈M。
（1）若σ（a1）= a1,则a1自己就作成一个轮换。（2）设σ(a1)= a2,σ(a2)= a3，…。这样下去，由于M有限，故到某一个元素ar,
其σ（ar）必然不能再是新的元素，即这σ（ar）必在a1，…，ar之内。由于σ是一对一的,我们已有σ(ai)= ai+1，i=1，2，…，r-1，所以σ(ar)只能是a1。于是我们得到一个轮换
（a1…ar）。
若M已经没有另外的元素，则σ就等于这个轮换，否则设b1不在a1，…，ar之内，则同样作法又可得到一个轮换（b1…bs）。
因为a1，…，ar各自已有变到它的元素，所以b1，…，bs中不会有a1，…，ar出现，即这两个轮换不相杂。若M的元素已尽，则σ就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于M有限，最后必得
σ=( a1…ar)(b1…bs)…(c1…ct) （1）
即σ表成了不相杂的轮换的乘积。
证明f（x）= 3x5+7x2+5在有理域R0上不可约。
证明：本例不能使用Eisenstein定则。
因为，若f（x）在R0上可约，3不是2的倍数，则f（x）在R2上可约。
因此，只需证明f（x）在R2上不可约，则可知f（x）在R0上不可约。
而在R2上，f（x）= x5+x2+1。
（1）证明无一次因式。
由R2={0，1}，f（0）=f（1）=1知，
f （x）在R2上无根，即无一次因式。
（2）证明无二次因式。在R2上二次因式只有：x2，x2+1，x2+x，x2+x+1。
其中只有x2+x+1是质式。
但x5+x2+1 = x2（x+1）（x2+x+1）+1，
因此，f （x）在R2上无二次因式。
即，f（x）在R2上不可约。
所以，f（x）在R0上不可约。
5. 求证：?（x）F［x］的极大理想，当且仅当?（x）不可约。
证明：必要性：若?(x)可约，设?(x)＝λ(x)μ(x)，次λ（x）≥1，次μ（x）≥1。
对任意g(x)∈?(x)F［x］，
g(x)= ?(x)f(x)=λ(x)μ(x)f(x)，
故g(x)∈λ(x)F[x]。
显然，λ(x)∈λ(x)F[x]，但次λ(x)<次?(x),?(x)F[x]中非0元素次数≥次?(x)，
故λ(x)??(x)F[x]。综合以上得：λ(x)F[x]??(x)F[x],矛盾于?(x)F[x]的极大性。
充分性：若?(x)F［x］不是极大理想，
则另有理想λ(x)F［x］，非F［x］，
而使?(x)F［x］?λ(x)F［x］。
因为?（x）∈?(x)F［x］，
所以，?（x）∈λ(x)F［x］
所以，?（x）= λ(x)q(x) 且次q(x) ≥1。
（为什么？）
与?(x)不可约矛盾。
求证若G的元数是一个质数，则G必是循环群。
证明：设G的元数为质数P，任取G中非单位元a，则(a)是G的一个循环子群，设a的周期为r，则(a)的元数为r，因此r|P。但P是质数。显然r≠1,故r=P，所以G=(a)，即G是由a生
成的循环群。
定义A 所定义的格和定义B 所定义的格是等价的,亦即,一个部份序格必是一个代数格；反之亦然。
证明：i ）若（L ，≤）是一个格，
则对任意a,b ∈L,记inf{a ，b}为a ×b ；sup{a ，b}为a ⊕b 。由于对任意a,b,其inf{a,b},sup{a,b}是唯一的，所以，如上定义的×，⊕是集合L 上的两种二元代数运算。不难证明，对于×，⊕满足交换律,结合律,吸收律.我们只证明吸收律：
a ×（a ⊕
b ）=a
因为a ×（a ⊕b ）是a 与（a ⊕b ）的最大下界，所以
a ×（a ⊕
b ）≤a ；另一方面，由于a ≤a ，a ≤a ⊕b ，所以，a 是a 与a ⊕b 的下界，故a ≤a ×（a ⊕b ），
故a = a ×（a ⊕b ）。
因此，根据定义B ，（L ，×，⊕）是一个格。
ii ）若代数系统（L,×,⊕）是一个格,在集合L 上定义一个关系≤如下：
对任意a ，b ∈L ， a ≤b ?a ×b=a
往证：≤是一个部份序关系。
因为
a ×a=a ×（a ⊕（a ×a ））=a
所以有a ≤a 。
若有a ≤b,b ≤a,则应有a ×b=a ，b ×a=b ，
而a ×b = b ×a ，所以a=b 。
若 a ≤b ，b ≤c ，则有a ×b=a ，b ×c=b ，
故a ×c=（a ×b ）×c = a ×（b ×c ）= a ×b = a
亦即，有a ≤c 。
由此证明了关系≤具有反身性,反对称性,传递性。
故≤是部份序关系。
求证循环群的子群仍是循环群。 证明：若循环群G 由其中元a 生成。H 是G 的子群,但不是单位元群。则H 中必含有幂m>0的元am 。因为若m<0，am 的逆元a-m 也在H 内，而-m>0。假定am 是H 中的最小正幂，显然H 包含am 的任意乘幂。假如又有H 中任意元aS,由S=tm+r 。0≤r 中任意元aS 也是am 的乘幂,而知H 为am 生成的循环群。 构造元数为8的有限域，并写出该域的加法和乘法表。 解：由于8=23，所以，p=2,m=3。 （1）首先求Φpm-1（х），即Φ7（х）。 由x7-1=Φ7Φ1，x-1=Φ1，得Φ7（х）= 。 （2）求Φ7（х）在R2[х]中的3次质因式ψ（х）。 Φ7（х）=（x3+x2+1）（x3+x+1）， 我们不妨取ψ（х）=x3+x+1，则 R2[x]/(ψ（х）)= 111234567++++++=--x x x x x x x x } 1,,1,,1,,1,0{2222+++++x x x x x x x x （3）若取ξ= ，则ψ（ξ）= ， ，GF(8)={a0 +a1ξ+a2ξ2|a0，a1，a2∈R2}={0,1,ξ,ξ+1,ξ2,ξ2+1,ξ2+ξ,ξ2+ξ+1}. 离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为mn，A到B上可以定义m n 2种不同的关系； 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（） 《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ； 离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。 谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证 二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。 第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r); 数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作 不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律) 数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明: 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式 将一个普通公式转换为范式的基本步骤 1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={离散数学必备知识点总结
离散数学必备知识点总结
离散数学复习要点
《离散数学》考试题库及答案(三)
离散数学知识点整理
离散数学习题
离散数学第二章一阶逻辑知识点总结
离散数学第四章二元关系和函数知识点总结
离散数学例题整理
离散数学第一章命题逻辑知识点总结
离散数学题目大汇总
(完整word版)离散数学知识汇总,推荐文档
大学离散数学期末重点知识点总结(考试专用)