离散数学重点笔记

第一章，0命题逻辑素数=质数，合数有因子和或假必真同为真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。(┐p∧q)→┐r公式(1)的成假赋值为011，其余7个赋值都是成真赋值第二章，命题逻辑等值演算（1）双重否定律AA（2）等幂律A∧AA；A∨AA（3）交换律A∧BB∧A；A∨BB∨A（4）结合律（A∧B）∧CA∧（B∧C）；（A∨B）∨CA∨（B∨C）（5）分配律（A∧B）∨C（A∨C）∧（B∨C）；（A∨B）∧C（A∧C）∨（B∧C）（6）德·摩根律（A∨B）A∧B；（A∧B）A∨B（7）吸收律A∨（A∧B）A；A∧（A∨B）A（8）零一律A∨11；A∧00（9）同一律A∨0A；A∧1A（10）排中律A∨A1（11）矛盾律A∧A0（12）蕴涵等值式A→BA∨B（13）假言易位A→BB→A（14）等价等值式AB（A→B）∧（B→A）（15）等价否定等值式ABABBA（16）归缪式（A→B）∧（A→B）AAi(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨As为析取范式(p∧┐q)∨(┐q∧┐r)∨pA=A1∧A2∧…∧As为合取范式(p∨q∨r)∧(┐p∨┐q)∧r一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式主范式【∧小真，∨大假】∧成真小写【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)(消去→)=(p∧┐q)∨┐p∨q(┐内移)(已为析取范式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)（*）=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3(幂等律、排序)(*)由┐p及q派生的极小项的过程如下：┐p=┐p∧(┐q∨q)=(┐p∧┐q)∨(┐p∧q)q=(┐p∨p)∧q=(┐p∧q)∨(p∧q)熟练之后，以上过程可不写在演算过程中。该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式，00，01，10，11全为成真赋值。【例】(p→q)∧┐p=(┐p∨q)∧┐p(消去→)=┐p∨(┐p∧q)(分配律、幂等律)已为析取范式=(┐p∧┐q)∨(┐p∧q)=m0∨m1【例】(p∧┐q)∨(┐p∧q)=(p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q)=(p∨q)∧┐(p∧q)重言蕴涵式【例】用附加前提证明法证明下面推理。前提：P→（Q→R），S∨P，Q结论：S→R证明：（1）S∨P前提引入规则（2）S附加前提引入规则（3）P（1）（2）析取三段论规则（4）P→（Q→R）前提引入规则（5）Q→R（3）（4）假言推理规则（6）Q前提引入规则（7）R（5）（6）假言推理规则【例】用归缪法证明。前提：P∨Q，P→R，Q→S结论：S∨R证明（1）（S∨R）附加前提引入规则（2）S∧R（1）置换规则（3）S（2）化简规则（4）R（2）化简规则（5）Q→S前提引入规则（6）Q∨S（5）置换规则（7）Q（3）（6）析取三段论（8）P∨Q前提引入规则（9）P（7）（8）析取三段论规则（10）P→R前提引入规则（11）P∨R（10）置换规则（12）R（9）（11）析取三段论规则（13）R∧R（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）﹁xA（x）x﹁A（x）（2）﹁xA（x）x﹁A（x）定理2设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）∨B）xA（x）∨B（2）x（A（x）∧B）xA（x）∧B（3）x（A（x）→B）xA（x）→B（4）x（B→A（x））B→xA（x）（5）x（A（x）∨B）xA（x）∨B（6）x（A（x）∧B）xA（x）∧B（7）x（A（x）→B）xA（x）→B（8）x（B→A（x））B→xA（x）定理3设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）x（A（x）∧B（x））xA（x）∧xB（x）（2）x（A（x）∨B（x））xA（x）∨xB（x）定理4下列蕴涵式成立（1）xA（x）∨xB（x）x（A（x）∨B（x））（2）x（A（x）∧B（x））xA（x）∧xB（x）（3）x（A（x）→B（x））xA（x）→xB（x）（4）x（A（x）→B（x））xA（x）→xB（x）（5）xA（x）→xB（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）幂等律：A∩A＝AA∪A＝A（2）同一律：A∩U＝A（3）零律：A∩＝A∪E＝E（4）结合律：(A∩B)∩C＝A∩(B∩C)(A∪B)∪C＝A∪(B∪C)（5）交换律：A∩B＝B∩AA∪B＝B∪A(6)分配律A∩（B∪C）＝（A∩B）∪（A∩C）A∪（B∩C）＝（A∪B）∩（A∪C）吸收律A∪（A∩B）＝AA∩（A∪B）＝A同一律A∪＝AA∩E＝AA-B称为集合B关于A的补集Ａ-B＝｛x|xＡ且xB｝补集记作~A~（A∪B）＝~A∩~B~（A∩B）＝~A∪~B（1）双重否定律：~（~A）＝A（2）摩根律：~＝U~U＝A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)=～B∩～C～(B∩C)=～B∪～C（4）矛盾律：A∩（~A）＝（5）排中律：A∪（~A）＝U集合A和B的对称差记作AB，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。AB＝(A∪B)-(A∩B)（1）AA＝（2）A＝A（3）AＵ＝~Ａ（4）AB＝BA（5）（AB）C＝A（BC）（6）AB＝(A-B)∪(B-A)第七章，二元关系A×B={x，yx∈A∧y∈B}A×B={a，b}×{c，d}={a，c，a，d，b，c，b，d}自反性和反自反性定义4.10设R是集合A上的二元关系，如果对于每个xA，都有x，xR，则称二元关系R是自反的。R在A上是自反的x（xAx，xR）定义4.11设R是集合A上的二元关系，如果对于每个xA，都有x，xR，则称二元关系R是反自反的。R在A上是反自反的x（xAx，xR）4.4.2对称性和反对称性定义4.12设R是集合A上的二元关系，如果对于每个x，yA，当x，yR，就有y，xR，则称二元关系R是对称的。R在A上是对称的xy（xA∧yA∧x，yRy，xR）定义4.13设R是集合A上的二元关系，如果对于每个x，yA，当x，yR和y，xR时，必有x=y，则称二元关系R是反对称的。4.4.3传递性定义4.14设R是集合A上的二元关系，如果对于任意x，y，zA，当x，yR，y，zR，就有x，zR，则称二元关系R在A上是传递的。R在A上是传递的xyz（xA∧yA∧zA∧x，yR∧y，zRx，zR）例4.13设A={a，b，c}，R，S，T是A上的二元关系，其中R={a，a，b，b，a，c}S={a，b，b，c，c，c}T={a，b}说明R，S，T是否为A上的传递关系。解根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为a，bR，b，cR，但a，cR。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作。设为偏序关系，如果x，y∈，则记作xy，读作“小于或等于”【例】【例】4、设R是二元关系，设S={a,b|存在某个c，使得a,c∈R且c,b∈R}。证明如果R是等价关系，则S也是等价关系。【例】第九章，代数系统可以用。、*、·、、等符号表示二元或一元运算,称为算符。对于二元运算。,如果x与y运算得到z,记做x。y=z；对于一元运算。，x的运算结果记作。x.【例】【例】