离散数学重点资料库文本笔记.doc

《离散数学重点资料库文本笔记.doc》由会员分享，可在线阅读，更多相关《离散数学重点资料库文本笔记.doc（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、/ 第一章，第一章，0 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）

2、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为

3、合取范式 (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 个命题变项，它的主析取

4、范式中含了 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）假言

5、推理规则【例】用归缪法证明。 前提：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,

6、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 1 设 A（x）是谓词公式，有关量词否定的两个等价公式： （1）x A（x）xA（x） （2）x A（x）xA（x） 定理定理 2 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

7、）x A（x）B （7）x（A（x） B）x A（x） B （8）x（BA（x） ）Bx A（x） 定理定理 3 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 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）

8、x（A（x） B（x） ）/【例】【例】/【例】/【例】/【例】在一阶逻辑自然推理系统 F 中构造下面推理的证明（1）所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。 （个体域为 人的集合） 。 （2）每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘 汽车，所以有的人不喜欢步行。 （个体域为人的集合） 。/【例】符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所 以任何虚数既不是有理数也不是无理数”，并推证其结论。 证明 设：P（x）：x 是有理数。Q（x）：x 是无理数。R（x）：x 是

9、实数。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

10、（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 N(在离散数学中认为 0 也是自然数)，整数集合 Z Z，有理数集合 Q Q，实数集合 R R，复数集合 C C 全集 U，空集是一切集合的子集 （1）幂等律：AAA AAA （2）同一律：AUA（3）零律：A AEE（4）结合律：(AB)CA(BC) (AB)CA(BC) （5）交换律：ABB

11、A 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 UA(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/（2）AA（3）A （4）ABBA （

12、5） （AB）CA（BC） （6）AB(A-B)(B-A)第第 7 章章，二元关系，二元关系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 是对

13、称的。 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 也是等价关系。/【例】第第 9 9 章章，代数系统，代数系统可以用。 、*、 等符号表示二元或一元运算,称为算符。对于二元运算。,如果 x 与 y 运算 得到 z,记做 x。y=z；对于一元运算。 ，x 的运算结果记作。x. 【例】【例】/