离散数学精简讲义Word文档格式.docx

离散数学精简讲义Word文档格式.docx

《离散数学精简讲义Word文档格式.docx》由会员分享，可在线阅读，更多相关《离散数学精简讲义Word文档格式.docx（16页珍藏版）》请在冰点文库上搜索。

基本积的归纳定义是：

①文字是基本积；

②若A，B是基本积，则A∧B是基本积。

析取范式的归纳定义如下：

①基本积是析取范式；

②若A，B是析取范式，则（A∨B）是析取范式。

主析取范式的归纳定义是：

①极小项是主析取范式；

②若A，B是主析取范式，则（A∨B）是主析取范式。

▲1.5推理理论

推理规则：

⑴附加规则

⑵化简规则

⑶MP规则

⑷拒取式

⑸析取三段论

⑹假言三段论

⑺合取引入

⑻构造二性难

▲证明方法：

⑴前件假证明法

⑵后件真证明法

⑶直接证明法

⑷间接证明法

⑸分情况证明法

⑹附加前提证明法

⑺反证法

▲公理系统一般由下列几部分组成：

⑴初始符号：

它们是不经定义而直接使用的符号；

⑵形成规则：

确定定义在初始符号上的哪些符号串是合式公式；

⑶公理集：

它们是不经证明而被认为是恒真的命题；

⑷推理规则：

规定如何从公理和前面已经推导出的合式公式经过符号变形而推出其它公式。

命题逻辑的公理系统L的定义如下：

①P是合式公式；

②若A是合式公式，则（┑A）是合式公式；

③若A和B是合式公式，则（A→B）是合式公式；

④只有通过有限次使用①~③得到的符号串是合式公式。

（L）（A→（B→A））；

（L）（（A→（B→C））→（（A→B）→（A→C）））；

（L）（（（┑A）→（┑B））→（B→A））。

从A和（A→B）可推出B。

证明：

L中的证明是合式公式的一个有穷序列A，A，…A,其中A或者是公理，或者是序列中其前的某两个合式公式经MP规则得到。

并称该证明人是A是在L中的证明，称A是L的定理，记作。

演绎：

设是合式公式集，L中的从推出A的一个演绎是合式公式的一个有穷序列A，A，…A，其中A或者是公理，或者是中的一个合式公式，或者是序列中其前的某两个合式公式经MP规则得到。

中的合式公式称为假设。

L的演绎定理：

推论：

设A，B，C是L的任意合式公式，则{A→B，B→C}A→C。

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），（A∧B），（A∨B），（A→B），（A↔B），∀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范式

称下述形式的公式为前束范式：

QxQxQxQ…B,其中Q为∀或∃，B是不含任何量词的公式。

并称QxQxQxQ为前束词，称B为母式。

Skolem范式

设前束范式为QxQx…Qx…QxB。

若Qx为∃x（1≦t≦r）,那么⑴当Qx左边无全称量词时，用B中未出现的个体常元a支代替B中x的所有出现，并删支出Qx；

⑵当Qx左边的所有全称量词为QxQx,…,Qx（1≦）时，取B中未出现的s元函数符号f，用f（x,x,…x）代替B中x的所有出现，并删支Qx。

这种消去量词的变换称为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|x⊆A}为A的幂集，A的幂集即是由A的所有子集组成的集合。

3.3基本集合恒等式

3.4容斥原理

3.5集合的笛卡尔积

●称<

x,y>

={{x},{x,y}}为由x和y组成的有序二重组，也称为序偶。

●设n∈I,x,x,…,x是n个任意的元素。

⑴若n=1,则令<

x>

=x;

⑵若n=2,则令<

x,x>

={{x},{x,x}};

⑶若n>

2,则令<

x,x,…,x>

=<

<

x>

.称<

是由x,x,…,x组成的有序n重组，称x（1≤i≤n）是它的第i个分量。

●设n∈I,集合A,A,…,A的笛卡尔积AA…A定义为AA…A={<

a,a,…a>

|a∈A,i=1,2,3…n}.称n为该笛卡尔积的维数。

若A=A=…A,则记AAA…A为A。

笛卡尔积满足下列分配律：

第四章二元关系

●设n∈I，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|x∈A∧<

∈R}为R的定义域，称ran（R）={y|y∈A∧<

∈R}为R的值域。

若<

a,b>

∈R,则说a与b有关系R，常用中缀法记为aRb;

若<

∈R,则说a与b没有关系R，常用中缀法记为aRb。

由于任意集合均有两个平凡子集，即空集和集合自身，因此称AA…A上的关系为空关系，称AA…A为全域关系。

A上的关系{<

x,x>

|x∈A}称为A上的恒等关系，记为I。

●设R⊆A,R⊆A.若⑴n=m;

⑵;

⑶集合R和R相等，则称关系R与R相等，记为R=R。

▲关系的表示

⑴集合表示法；

⑵关系矩阵表示法；

⑶关系图表示法。

4.2关系的性质

●设A是集合，R⊆AA。

⑴若∀x（x∈A→xRx）,则称R是自反的；

⑵若∀x（x∈A→xRx）,则称R是反自反的；

⑶若∀x∀y（x∈A∧y∈A∧xRy→yRx）,则称R是对称的；

⑷若∀x∀y（x∈A∧y∈A∧xRy∧yRx→x=y）,则称R是反对称的；

⑸若∀x∀y∀z（x∈A∧y∈A∧z∈A∧xRy∧yRz→xRz）,则称R是传递的。

4.3关系的运算

●设A，B是集合，R⊆AB，且S⊆AB，则交R∩S，并R∪S，差R-S和补R均是A和B上的二元关系，且x（R∩S）y⇔xRy∧xSy,x（R∪S）⇔xRy∨xSy,x（R-S）⇔xRy∧xSy,xRy⇔xRy.

●设A和B是集合，R⊆AB，令R⊆BA且R={<

y,x>

|xRy}，则称R是R的逆关系。

▲设A和B是集合，R⊆AB（i=1,2），则⑴R=R；

⑵R∩R=R∩R；

⑶R∪R=R∪R；

⑷R-R=R-R；

⑸R=R；

⑹若R⊆R，则R⊆R。

●关系的合成：

设A，B和C是集合，R⊆AB，R⊆BC，R与R的合成关系是RR⊆AC，且RR={<

x,z>

|x∈A∧z∈C∧∃y（y∈B∧xRy∧yRz）}.

合成运算不满足交换律，但是它满足结合律。

●关系的幂：

设A是集合，R⊆AA，n∈N，则R的n次幂定义为R=I，R=RR。

若R⊆AA，且满足：

⑴R是自反的（对称的、传递的）；

⑵R⊆R；

⑶若R⊆AA且满足：

①R是自反的（对称的、传递的），②R⊆R,则⊆R；

那么称R是R的自反（对称、传递）闭包，记为r（R）（s（R）,t（R））。

▲设A是集合，R⊆AA，则⑴R是自反的当且仅当r（R）=R；

⑵R是对称的当且仅当s（R）=R；

⑶R是传递的当且仅当t（R）=R。

▲设A是集合，R⊆AA，则⑴r（R）=R∪I；

⑵s（R）=R∪R;

⑶t（R）=∪R.

▲设A是集合，R⊆AA（i=1,2），若R⊆R，则⑴r（R）⊆r（R）;

⑵s（R）⊆s（R）;

⑶t（R）⊆t（R）;

▲设A是集合，R⊆AA，⑴若R是自反的，则s（R）和t（R）j自反的；

⑵若R是对称的，则r（R）和t（R）是对称的；

⑶若R是传递的，则r（R）传递的。

▲设A是集合，R⊆AA，则⑴rs（R）=sr（R）;

⑵rt（R）=tr（R）;

⑶st（R）⊆ts（R）.

4.4等价关系和划分

●设A是集合，R⊆AA。

若R是自反的、对称的和传递的，则称R是A上的等价关系，并且若aRb,则说a与b等价。

●设R是集合A上的等价关系。

对任何a∈A,称[a]={x|x∈A∧xRa}为a关于R的等价类（有时简记为[a]），并且称a为[a]的代表元；

若等价类个数有限，则称R的不同类的个数为R的秩，否则称R的秩是无限的，称{[a]|a∈A}为A关于R的商集，记为A/R。

▲设R是A上的等价关系，A=，a,b∈A,则⑴[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，那么⑴R∩R诱导的划分是；

⑵t（R∪R）诱导的划分是。

4.5序关系

序关系是一类重要的二元关系，它提供了比较集合中元素的一种方法。

●偏序关系：

设A是集合，R⊆AA。

若R是自反的、反对称的和传递的，则称R是A上的偏序关系，并称<

A,R>

是偏序集。

偏序关系有时也称作半序或部分序关系，常用表示偏序关系。

●覆盖：

设R是集合A上的偏序关系，a∈A.若b∈A满足⑴aRb且b=a;

⑵若x∈A使得aRx且xRb,则必有x=a或x=b.那么称b是a关于R的覆盖。

●

●拟序关系：

设A是集合，R⊆AA。

若R是反自反的和传递的，则称R是A上的拟序关系，并称<

是拟序集。

▲拟序关系是反对称的。

▲设A是集合。

R⊆AA。

⑴若R是偏序关系，则R-I是拟序关系；

⑵若R是拟序关系，则R∪I是偏序关系。

●全序关系：

设<

A,>

是偏序集，若∀x∀y（x∈A∧y∈A→xy∨yx）,则称是A上的全序关系到，并称<

为全序集。

全序关系也称作线序关系，全序集<

也称作线序集或链。

●良序关系：

是偏序集，若对任意的S，=S⊆A,则S有最小元，那么称是A上的良序关系，并称<

为良序集。

4.6相容关系

若R是自反的和对称的，则称R是A上的相容关系；

若aRb,则称x与y相容，否则称x与y不相容。

●设R是集合A上的相容关系。

⑴若=C⊆A，且∀a,b∈C,有aRb,则称C是R的一个相容类。

⑵若C是R的相容类，∀b∈C,则必有a∈C使得aRb,那么称C是R的一个极大相容类。

▲求极大相容类的方法：

⑴关系图法；

⑵关系矩阵法。

5.函数

5.1函数的基本概念和性质

●设X和Y是任意集合，f⊆XY.若∀x（x∈X→∃!

y（y∈Y∧<

∈f））,则称f是从X到Y的函数，记为f:

X→Y.

设f:

X→Y,X=.定义R⊆XX为∀x,x∈X,xRx当且仅当f（x）=f（x）,则易证F是X上的等价关系（称之为由f诱导的等价关系），并且由关系R确定的划分为{f（{y}）|y∈Y∧f（{y}）=}.令g:

X→X/R,g（x）=[x],称g是由f诱导的规范映射。

可见对给定的一个函数均可得到一个规范映射。

●设X和Y是任意集合，则从X到Y的所有函数构成的集合记为Y，即Y={f|f:

X→Y}.

当一个函数是递归定义时，常需要验证函数是良定的（well-defined）.

●设f:

X→Y.⑴若f（X）=Y,则称f是满射的。

⑵若∀x∀x（x∈X∧f（x）=f（x）→x=x）,则称f是单射的。

⑶若f既是单射的，又是满射的，则称f是双射的。

●集合的的特征函数：

设U是全集，A⊆U。

定义A的特征函数为：

U→{0，1}，（x）=

5.2函数的合成

▲设f:

X→Y,g:

Y→Z,则f与g的合成关系fg是从X到Z的函数，并且对一切x∈X,fg（x）=g（f（x））.

Y→Z,则⑴若f和g是满射，则gf是满射；

⑵若f和g是单射，则gf是单射；

⑶若f和g是双射，则gf是双射。

Y→Z,则⑴若gf是满射，则g是满射；

⑵若gf是单射，则f是满射；

⑶若gf是双射，则g是满射且f是单射。

5.3逆函数

X→Y是双射，则f的逆关系f是从Y到X的函数。

▲设f是从X到Y的双射，g是从Y到X的函数，则f=g当且仅当gf=1且fg=1.

X→Y。

若有g:

Y→X使得gf=1和fg=1成立，则称g是f的逆函数，并称f是可逆的。

●⑴若有g:

X→Y,使得gf=1成立，则称g是f的左可逆函数，并称f是左可逆的。

⑵若有g:

X→Y,使得fg=1成立，则称g是f的右可逆函数，并称f是右可逆的。

X→Y,X=,则⑴f是左可逆的当且仅当f是单射；

⑵f是右可逆的当且仅当f是满射；

⑶f是可逆的当且仅当f是双射，或当且仅当f既是左可逆的，又是右可逆的。

5.集合的基数

6.1可数集和无限集

●设S是任一集合，称S=S∪{S}的后继集。

●自然数N的归纳定义是：

⑴∈N；

⑵若n∈N,则n∈N；

⑶若S∈N,且满足①∈S；

②若n∈S，则n∈S；

则S=N。

●若m,m∈N,n∈N使m∈n,则称m小于m，记为m<

n.

●设A和B是任意集合，若存在从A到B的双射，则称A与B是等势的，记为A~B；

若A与B不等势，则记为A~B。

●若有n∈N,使得N~A，则称A是有限集，且称其基数为n,记为|A|=n;

若A不是有限集，则称A是无限集。

▲任何有限子集都不能与它的真子集等势

●设A是任意集合。

若N~A，则称A是可数无限集，并称A的基数为（读作阿列夫零），记为|A|=。

有限集与可数无限集称为可数集或可列集；

非可数集合称为不可数集。

▲可数集的任何子集都是可数集。

可数个可数集的并集是可数集。

若A和B是可数集，则AB是可数集。

▲实数集合的子集[0，1]不是可数无限集合。

若[0，1]~A，则称A的基数为（读作阿列夫），并称A是具有连续统势的集合，记为|A|=。

▲设A，B，C和D是任意集合，A~B，C~D，A∩C=B∩D=，则A∪C~B∪D.

6.2集合基数的比较

●设A和B是任意集合。

若存在从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为非空集合，n∈I，函数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,b∈A，有a*b=b*a,则称*是可交换的，或称*满足交换律。

若∀a,b,c∈A，有（a*b）*c=a*（b*c）,则称*是可结合的，或称*满足结合律。

∙设*和。

是A上的二元运算。

⑴若∀a,b,c∈A,有a*（bº

c）=（a*b）º

（a*c）,则称*关于º

是左可分配的。

⑵若∀a,b,c∈A,有（bº

c）*a=（b*a）º

（c*a）,则称*关于º

⑶若*关于º

既是左可分配的，又是右可分配的，则称*关于º

是满足分配律。

∙设*是A上可结合的二元运算，则∀n∈I,∀a,a,…,a∈A,表达式a*a*…*a经任意加括号而计算出的结果不变。

∙若*是A上可结合的二元运算，则∀a∈A及∀m,n∈I,有a*a=a,（a）=a.

∙设*是A集合上的二元运算。

⑴若∃e∈A,使得∀a∈A,有e*a=a,则称e为关于的左单位元，也称左幺元。

⑵若∃e∈A,使得∀a∈A,有a*e=a,则称e为关于的右单位元，也称右幺元。

⑶若∃e∈A,使得∀a∈A,有e*a=a*e=a,则称e为关于的单位元，也称幺元。

∙设*是A上的二元运算,e和e分别是关于的左、右单位元，则e=e,且它是关于*的惟一单位元。

⑴若∃0∈A，使得∀a∈A,有0*a=0,则称0为关于*的左零元。

⑵若∃0∈A，使得∀a∈A,有a*0=0,则称0为关于*的右零元。

⑶若∃0∈A，使得∀a∈A,有0*a=a*0=0,,则称0为关于*的零元。

∙设*是集合A上的二元运算，0和0分别是关于*的左、右零元，则0=0,且它是关于8的惟一零元。

∙设*是集合A上的二元运算，e是关于*的单位元，a∈A.⑴若∃a∈A,使得a*a=e,则称a关于*是左可逆的，并称a是a的关于*的左逆元。

⑵若∃a∈A,使得a*a=e,则称a关于*是右可逆的，并称a是a的关于*的右逆元。

⑶若∃a∈A,使得a*a=a*a=e,则称a关于*是可逆的，找称a为a的关于*的逆元。