离散数学重点笔记.doc

离散数学重点笔记212020年4月19日文档仅供参考，不当之处，请联系改正。第一章， 0命题逻辑素数 = 质数，合数有因子 和 或 假必真 同为真(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式(pq)r，(pq)(rs)p)分别为3层和4层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。 (pq)r公式(1)的成假赋值为011，其余7个赋值都是成真赋值第二章， 命题逻辑等值演算（1）双重否定律 AA（2）等幂律 AAA ； AAA（3）交换律 ABBA ； ABBA（4）结合律 （AB）CA（BC） ； （AB）CA（BC）（5）分配律 （AB）C（AC）（BC） ； （AB）C（AC）（BC）（6）德摩根律 （AB）AB ； （AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蕴涵等值式 ABAB（13）假言易位 ABBA（14）等价等值式 AB（AB）（BA）（15）等价否定等值式 ABABBA（16）归缪式 （AB）（AB）AAi(i=1,2,s)为简单合取式，则A=A1A2As为析取范式 (pq)(qr)p A=A1A2As为合取范式 (pqr)(pq)r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式 【小真，大假】 成真 小写【例】 (pq)(qp) = (pq)(qp) (消去) = (pq)pq (内移) (已为析取范式) = (pq)(pq)(pq)(pq)(pq) （*） = m2m0m1m1m3 = m0m1m2m3 (幂等律、排序) (*)由p及q派生的极小项的过程如下： p = p(qq) = (pq)(pq) q = (pp)q = (pq)(pq) 熟练之后，以上过程可不写在演算过程中。 该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式，00，01，10，11全为成真赋值。【例】(pq)p = (pq)p (消去) = p(pq) (分配律、幂等律) 已为析取范式 = (pq)(pq) = m0m1【例】(pq)(pq) = (pp)(pq)(qp)(qq) = (pq)(pq)重言蕴涵式 【例】用附加前提证明法证明下面推理。前提：P（QR），SP，Q 结论：SR证明：（1）SP 前提引入规则 （2）S 附加前提引入规则 （3）P （1）（2）析取三段论规则 （4）P（QR） 前提引入规则 （5）QR （3）（4）假言推理规则 （6）Q 前提引入规则 （7）R （5）（6）假言推理规则【例】用归缪法证明。前提：PQ，PR，QS 结论：SR证明（1）（SR） 附加前提引入规则 （2）SR （1）置换规则 （3）S （2）化简规则 （4）R （2）化简规则 （5）QS 前提引入规则 （6）QS （5）置换规则 （7）Q （3）（6）析取三段论 （8）PQ 前提引入规则 （9）P （7）（8）析取三段论规则 （10）PR 前提引入规则 （11）PR （10）置换规则 （12）R （9）（11）析取三段论规则 （13）RR （4）（12）合取引入规则全称量词对无分配律。同样的，存在量词对无分配律 (3) xyF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) 谓词逻辑的等价公式 定理1 设A（x）是谓词公式，有关量词否定的两个等价公式：（1）x A（x）xA（x）（2）x A（x）xA（x）定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A（x） 定理3 设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B（x） 定理4 下列蕴涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x）【例】【例】【例】【例】【例】在一阶逻辑自然推理系统F中构造下面推理的证明 （1）所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。（个体域为人的集合）。 （2）每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车，因此有的人不喜欢步行。（个体域为人的集合）。【例】符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，因此任何虚数既不是有理数也不是无理数”，并推证其结论。证明 设：P（x）：x是有理数。 Q（x）：x是无理数。 R（x）：x是实数。 S（x）：x是虚数。本题符号化为：x（P（x） R（x），x（Q（x） R（x），x（S（x）R（x）x（S（x）P（x）R（x）解（1）x（S（x）R（x） P（2）S（y）R（y） US（1）（3）x（P（x） R（x） P（4）P（y） R（y） US（3）（5）R（y）P（y） T（4）E（6）x（Q（x） R（x） P（7）Q（y） R（y） US（6）（8）R（y）Q（y） T（7）E （9）S（y）P（y） T（2）（5）I（10）S（y）Q（y） T（2）（8）I（11）（S（y）P（y）（S（y）Q（y） T（9）（10）I（12）（S（y）P（y）（S（y）Q（y） T（11）E（13）S（y）（P（y）Q（y） T（12）E（14）S（y）（P（y）Q（y） T（13）E（15）x（S（x）P（x）R（x） UG（14）第六章，集合代数自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C 全集U，空集是一切集合的子集（1）幂等律：AAA AAA （2）同一律：AUA（3）零律：A AEE（4）结合律：(AB)CA(BC) (AB)CA(BC) （5）交换律：ABBA ABBA (6) 分配律 A（BC）（AB）（AC） A（BC）（AB）（AC） 吸收律 A（AB）A A（AB）A 同一律 AA AEA A-B称为集合B关于A的补集 -Bx|x且xB补集记作A（AB）AB（AB）AB （1）双重否定律：（A）A（2） 摩根律：U U A(BC)(AB)(AC)A(BC)(AB)(AC)(BC)=BC(BC)=BC（4）矛盾律：A（A）（5） 排中律：A（A）U集合A和B的对称差记作AB，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。AB(AB)-(AB)（1）AA（1）（2）AA（3）A（4）ABBA（5）（AB）CA（BC）（6）AB(A-B)(B-A)第七章 ，二元关系AB=xAyBAB=a，bc，d=，自反性和反自反性 定义4.10 设R是集合A上的二元关系，如果对于每个xA，都有R，则称二元关系R是自反的。R在A上是自反的x（xAR） 定义4.11 设R是集合A上的二元关系，如果对于每个xA，都有R，则称二元关系R是反自反的。R在A上是反自反的x（xAR） 4.4.2 对称性和反对称性 定义4.12 设R是集合A上的二元关系，如果对于每个x，yA，当R，就有R，则称二元关系R是对称的。R在A上是对称的xy（xAyARR） 定义4.13 设R是集合A上的二元关系，如果对于每个x，yA，当R和R时，必有x=y，则称二元关系R是反对称的。 4.4.3 传递性 定义4.14 设R是集合A上的二元关系，如果对于任意x，y，zA，当R，R，就有R，则称二元关系R在A上是传递的。R在A上是传递的xyz（xAyAzARRR） 例4.13 设A=a，b，c，R，S，T是A上的二元关系，其中R=，S=，T=说明R，S，T是否为A上的传递关系。解 根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为R，R，但R。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作。设为偏序关系，如果，则记作xy，读作“小于或等于” 【例】【例】4、设R是二元关系，设S=|存在某个c，使得R且R。证明如果R是等价关系，则S也是等价关系。【例】第九章 ，代数系统能够用。、*、 等符号表示二元或一元运算,称为算符。对于二元运算。,如果x与y运算得到z,记做x。y=z；对于一元运算。，x的运算结果记作。x. 【例】【例】