离散数学重点笔记分析

《离散数学重点笔记分析》由会员分享，可在线阅读，更多相关《离散数学重点笔记分析（15页珍藏版）》请在装配图网上搜索。

1、第一章，0 命题逻辑素数 =质数，合数有因子和或假必真同为真(p q) (q r)， (p q) r ， p (q r)等都是合式公式，而pq r ，（ p (rq) 等不是合式公式。若公式 A 是单个的命题变项，则称( p q) r ，( (p q) (rA 为 s)0 层合式 p) 分别为3 层和4 层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。(p q) r公式 (1) 的成假赋值为011，其余 7 个赋值都是成真赋值第二章，命题逻辑等值演算（ 1）双重否定律AA（ 2）等幂律A AA； AAA（ 3）交换律A BB A； ABB A（ 4）结合律（A B） CA（ B C）；

2、（AB） CA（ B C）（ 5）分配律（A B） C（AC）（ BC） ； （A B） C（ A C）（ B C）（ 6）德摩根律（AB）A B；（AB）AB（ 7）吸收律A（ A B）A；A（ AB）A（ 8）零一律A 11； A00（ 9）同一律A 0A； A1A（ 10）排中律AA1（ 11）矛盾律AA0（ 12）蕴涵等值式A BA B（ 13）假言易位A BBA（ 14）等价等值式AB（A B）（ B A）（ 15）等价否定等值式ABABBA（ 16）归缪式（A B）（ AB）AAi (i=1,2, ,s) A=A1A2 为简单合取式，则As 为合取范式(pA=A1 A2 As 为析

3、取范式q r) ( p q) r(p q) ( q r) p一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式主范式【小真，大假】成真小写【例】(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 ( qq)=(p q) ( p q)q = ( p p) q=(p q)

4、 (p q)熟练之后，以上过程可不写在演算过程中。该公式中含n=2 个命题变项，它的主析取范式中含了00，01， 10，11 全为成真赋值。22=4个极小项，故它为重言式，【例】 (p q) p= ( p q) p(消去 )= p ( p q)(分配律、幂等律)已为析取范式= ( p q) (p q)= m0 m1【例】 (p q) ( pq)= (p p) (p q)( q p) ( qq)= (p q) (p q)重言蕴涵式【例】用附加前提证明法证明下面推理。前提： P（ Q R），SP， Q结论： S R证明：（ 1）SP前提引入规则（ 2） S附加前提引入规则（ 3） P（ 1）（ 2

5、）析取三段论规则（ 4） P（ Q R）前提引入规则（ 5） QR（ 3）（4）假言推理规则（ 6） Q前提引入规则（ 7） R（ 5）（6）假言推理规则【例】用归缪法证明。前提： P Q，P R， QS证明（ 1）（ S R）（2）SR（3）S（4）R（ 5） QS（ 6）QS（7）Q（ 8） PQ（9）P（ 10） PR结论： S R附加前提引入规则（ 1）置换规则（ 2）化简规则（ 2）化简规则前提引入规则（ 5）置换规则（ 3）（ 6）析取三段论前提引入规则（ 7）（ 8）析取三段论规则前提引入规则（ 11）PR（ 10）置换规则（12）R（9）（ 11）析取三段论规则（ 13）RR（

6、 4）（ 12）合取引入规则全称量词 对 无分配律。 同样的，存在量词 对 无分配律(3) x yF(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）x A（ x）（ 2） x A （ x）x A（ x）定理 2设 A（x）是任意的含自由出现个体变项x 的公式， B 是不含 x 出现的公式，则有（ 1） x（ A（ x） B）x A （ x） B（ 2） x（ A（

7、x） B）x A （ x） B（ 3） x（ A（ x） B ）x A （ x） B（ 4） x（ B A（ x）Bx 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）B x 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

8、） 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）每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢

9、乘汽车，所以有的人不喜欢步行。 （个体域为人的集合） 。【例】符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。证明设： 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

10、（ 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）（ 10） S（ y） Q（ y）（ 11）（ S（ y） P（ y）（ S（ y） Q（ y）（ 12）（ S（ y） P（ y）（S（y） Q（ y）（ 13） S（y）（ P（ y） Q（ y）T（2）（5）IT（ 2）（ 8） IT（9）（10）IT （11） E T（ 12） E（ 14） S（ y）（ P（ y） Q（ y）T（ 13） E（ 15） x（ S（x）

11、 P（ x） R（ x）UG（14）第六章，集合代数自然数集合 N( 在离散数学中认为 0 也是自然数 ) ，整数集合 Z，有理数集合 Q，实数集合 R，复数集合 C 全集 U ，空集是一切集合的子集（ 1）幂等律： AA A A A A（ 2）同一律： AU A（ 3）零律： AA E E（ 4）结合律： (AB)C A(BC)(A B) C A (B C)（ 5）交换律： AB BAA B B A(6) 分配律 A（ B C）（ AB）（ AC）A （ BC）（ A B ）（A C）吸收律A （ AB） AA（ A B） A同一律AAAE AA-B 称为集合B 关于 A 的补集 -B x|

12、x且 xB 补集记作 A（ A B） A B（ AB） A B（1）双重否定律：（ A ） A（ 2）摩根律： UU A (BC)(A B) (AC)A (BC) (A B) (A C) (B C)= B C (BC)= B C（ 4）矛盾律： A （ A ）（ 5）排中律： A （ A ） U集合 A 和 B 的对称差记作AB，它是一个集合，其元素或属于A ，或属于B ，但不能既属于A 又属于 B。A B(A B)- (A B)（ 1）A A（2）AA（ 3）A （ 4）A BB A（5）（AB）CA（BC）（ 6）A B(A - B)(B- A)第七章，二元关系AB=x A y BA B=

13、a ， b c ， d= ， ， 自反性和反自反性定义 4.10设 R自反的。是集合A 上的二元关系，如果对于每个xA ，都有R，则称二元关系R 是定义 4.11设 R是集合R 在 A 上是自反的x（xA 上的二元关系，如果对于每个AR）xA ，都有 R，则称二元关系R 是反自反的。R 在 A 上是反自反的x（xA R）4.4.2对称性和反对称性定义 4.12设 R 是集合 A 上的二元关系，如果对于每个x，yA ，当 R，就有 R，则称二元关系 R 是对称的。R 在 A 上是对称的xy（ x A y A R R）定义 4.13设 R 是集合 A 上的二元关系，如果对于每个x，yA ，当 R

14、和 R 时，必有 x=y ，则称二元关系R 是反对称的。4.4.3传递性定义 4.14设 R 是集合 A 上的二元关系，如果对于任意x， y， zA ，当 R，R，就有 R，则称二元关系R 在 A 上是传递的。R 在 A 上是传递的xy z（ x A y A zA R RR）例 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.【例】【例】