离散数学知识点(70页).doc

《离散数学知识点(70页).doc》由会员分享，可在线阅读，更多相关《离散数学知识点(70页).doc（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-离散数学知识点-第 71 页绪论研究对象：离散量研究方法：解的存在性 解的能行性研究内容：数理逻辑 集合 代数系统 图论 离散概率 组合数学例题1、A、B、C、D四人参加四次长跑，问：“A在B前三次，B在C前三次，C在D前三次，D在A前三次”是否有解，若有求出，否则说明理由。方法一： A A B C D n个元素的环形排列可拆成n个元素的 B C D A 线性排列D B C D A B D A B CC方法二：集合Sa=X|A在B前 SaSbSc=A B C DSb=X|B在C前 SaSbSd=D A B CSc=X|C在D前 SaScSd=C D A BSd=X|D在A前 SbScSd=B

2、 C D A例题2：在边长为1的正方形中任取五个点，则至少有两个点的距离2/2。“中点分隔”将边长为1的正方形分成四个边长为1/2的小正方形，从中任取五个小点，必有两个小点来自一个小正方形。例题3：“布鲁英序列”-应用旋转鼓的设计，设旋转鼓有8个区域，旋转一圈可识别三位二进制数，如何确定磁粉位置。（阴影0，非阴影1） 0111 000 0010001 0111 010 011 1 0 100 101 1 110 111 1思考题：四位二进制 a1 a2 a3 a4例题4：有五位小姐排成一排，所有小姐姓不同，穿的衣服颜色不同，喝不同的饮料，养不同的宠物，吃不同的水果，已知：1.钱小姐穿红衣服3.

3、陈小姐喝茶 4.穿绿衣服的小姐在穿白色衣服小姐的左边，穿绿衣服的小姐在喝咖啡问每位小姐怎么站，她们分别养什么宠物，吃什么水果，喝什么饮料，穿什么颜色衣服，姓什么。12345姓赵陈钱江翁吃梨桔子西瓜香蕉苹果喝开水茶牛奶咖啡香槟颜色黄蓝红绿白宠物猫鱼鸟狗例题5：同态加密R+ f:ax(a1) R* f(x+y)=f(x)*f(y)X f(x)y f(y)x+y f(x+y)例题6:100被2、3、5任意个整除2 5 4 68 31 A=X|被2整除 |A|=100/2=50B=X|被3整除 |B|=100/3=337C=X|被5整除 |C|=100/5=20|AB|=16 |AC|=10|BC|=

4、6 |ABC|=31:|A|-|AB|-|AC|+|ABC|=278:|U|-|ABC|=|U|-(|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|)=26第一章 命题逻辑 求职数理逻辑（一阶） 演算 标准型 等价 谓词逻辑 证明 推理 应用 类型一、 命题：具有确定真假意义的陈述句（断言）永T命题：真值为T（1）永F命题：假值为F（0）1+1=10 X3 X的取值有关 二进制 十进制 （T） （F） 费晰逻辑原子命题：不可再拆开的命题复合命题：由原子命题和联结词构成的命题词：命题的符号表示，用大写字母表示二、 联结词1. 否定（not）A为命题，若A为T，A为FA:张明是上海

5、人 A：张明不是上海人2. 合取（and）A、 B是命题，AB为T, iff(当且仅当）A、B均为TA B AB AB AB A BF F F F T TF T F T T FT F F T F FT T T T T T3. 析取（or） 可兼A、 B是命题，AB为F, iff A、B均为F 或 不可兼 量的估计4. 蕴含命题（if-then）A、 B是命题，AB为F，iff A为T，B为F前提 结论AB：原命题 AB:反命题（否命题）BA：逆命题 BA:逆反（逆否）命题5. 等值词（iff） A B为T，iff A、B的值相同P：生命息 Q：战斗止（PQ）(QP) P Q三、 命题公式（合成

6、公式）wff1. 命题变元，常元常元：T、F（仅有两个）变元：在T、F中取值，用小写字母表示2. wff的定义一个wff定义递归（归纳）如下：基础i) 命题变元，常元是wff归纳ii) 若A、B是wff,则（A）,(AB),(AB),(AB),(A B)也是wff极小化iii) 有限次使用i）和ii)得到的符号命题是wff 反进P Q (P) (Q)约定：最外层括号可省略优先级： 高 低 结合方向：左结合 如(PQ)R若优先级，结合方向可确定计算顺序时，括号可省略括号是用来改变运算顺序的扩展：（1）n个变元的增值表有2n行（指派），可构成22n wff（2）结合律：等值有结合侓A B C (A

7、 B) C A (B C)0 0 0 1 0 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 1 0 0 0 11 0 0 0 1 1 11 0 1 0 0 0 01 1 0 1 0 0 01 1 1 1 1 1 1重言式（永T式）一、基本概念1.指派（解释）对wffG中全部变元的一组赋值，成为一个指派N个变元的全部指派有2n个，可构成2的2n个wff2.永T式（重言式）在任何指派下为T PP3.永F式（矛盾式）在任何指派下为F PP4.偶然式非永T，亦非永F PQ5.可满足式至少在一组指派下取值为T PQ,P Q 二、逻辑恒等式1.定义：设A，B是wff,若A B为永T，则

8、称A与B是逻辑恒等式，记为A B例题：A:PQ B:PQ 求证 A B即求证A B为永T? P Q PQ PQ0 0 1 1 10 1 1 1 11 0 0 1 01 1 1 1 1 所以PQ PQ2.常用恒等式 P9（1）.A A,A A为永T 自反性（2）.若A B,则BA 对称性（3）.若AB,且BC,则AC 传递性（1）.代入规则代换实例：设wffG,P1，P2Pn是G中全部命题的变元，A是wff，以A代Pi的全部出现，得到公式G为G的一个代换实例。如 wffG:(PQ)(QR) wffA:SRA代Q的全部出现：G(P(SR)(SR)R)代入规则：（1）.永T式的任何可代入实例是永T式

9、 （2）.永F式的任何可代入实例是永F式 （3）.可满足式是任何可代入实例是不确定的例题： wffG: PQ G G PRR RRQ 可满足式 永T式 RRSS 永F式（2）.重换规则设wffG，A是G的子公式，B是wff且AB,以B代A的某些出现，得到公式G,则GG例题：wffG:（PQ）(QR)(PQ)化简，取A:PQ B:PQG1：(PQ)（QR）(PQ) GG1取:A:QR B:QR GG2G2：(PQ)（QR）(PQ) G1G2（PQ）(QR)(PQ) (PQ)（ QR）(PQ)（PQPRQQQR）(PQ)PRQPQQRQR（PPT）QRQR（3）.对偶规则设wffG中仅含、且不包含

10、和作用于变元在G中，将与互换，T与F互换，得新公式G*,则称G*为对偶式例题：求wffG:P(PQ)的对偶式解：P（PQ）P(PQ) G*:P(PQ)求（PQ）R的G*（PQ）R(PQ)R(PQ)RPQRG*:（PQ）R步骤：i)消、 ii)利用D-M定侓 iii)写G*，必要时加括号（2）.对偶规则设A、B是wff，A*、B*分别为A、B对偶式，若AB,则A*B*如： PQQP PQQP三大规则规则对象范围要求结论代入变元Pi全部出现永F式永T式重换子公式A某些出现ABGG对偶、T、F全部不含、AB则A*B*四、 永真蕴含式1.设A、B是wff，若AB永T，则称A永真蕴含B，记为ABAB i

11、ff AB永为T iff A为T，B必为T（肯定前件）Iff B为F，A必为F（否定后件）A BPPQ AB永为TPPQPPQTQT（1）AA AA永为T？ AAAAT（2）AB,BA则AB（3）AB,BC则AC4.A与A*关系例： A（P,Q）:PQPQ A*（P,Q）:PQ A*（P,Q）:PQ A（P,Q）:PQA（P1，P2Pn）A* （P1，P2Pn）A（P1，P2Pn）A*（P1，P2Pn）A（P1，P2Pn） A* （P1，P2Pn）A （P1，P2Pn） A*（P1，P2Pn）th1 :AB,A*B* th2:AB,B*A*范式一、基本积（和）1.基本积：变元、变元的否定、合取

12、基本和：变元、变元的否定、析取如： p q 基本积：pq pq pp pqp 基本和: pq pq pp pqp基本积（和）永F（T） Iff变元及其否定同时出现在基本积（和）中（1）析取范式若wffA，AA1A2Ak（*） Ai是基本积，称（*）为A的析取范式若wffA，AA1A2Ac（*） Ai是基本积，称（*）为A的合取范式PS：把其中运算符最少的称为最简析取范式例：设wffA:P（QR）求析（合）取范式解：P（QR）P(QR) (PQR) 析取范式 合取范式 基本积：P,Q，R 基本和：PQR二、主析取范式（1）Df：若基本积满足i).每个变元必须出现且进出现一次 ii).变元及其否定

13、不能同时出现则称该基本积为极小项。 编码 1 1 1 0 0 1 0 0p q pq pq pq pq0 0 0 0 0 10 1 0 0 1 01 0 0 1 0 01 1 1 0 0 0（2）性质1.每个变元的极小项有2n个2.每个极小项仅在变元的一组指派下取值为T，其余(2n)-1组指派下取值为F4.全部极小项的析取为永T式 原变元1 反变元0M0:P1 P2Pn M1:P1Pn-1PnM(2n)-1:P1P2Pn设wffA，若AA1A2Ak（*） Ai为极小项，则称（*）为A的主析取范式例：求P(QP)的主析式范式方法一：等值演算（E1 E24）P(QP) P(QP) P QP(PP)

14、 QTQT方法二：真值表P Q P(QP) PQPQPQPQ0 0 1 1 M0M1M2M30 1 1 01 0 1 11 1 1 1求（PQ）P （PQ）P PQP P(QT) PT P最简范式PQPT PQP(Q Q) PQPQPQM2M3(2，3)三、主合取范式 编码 0 0 0 1 1 0 1 1p q pq pq pq pq0 0 0 1 1 10 1 1 0 1 11 0 1 1 0 11 1 1 1 1 0原变元0 反变元1极小项：1 1pq 极大项：1 1pq M3M3性质4：MiMi注：永T式不存在主合取范式，仍记为T四主合取/主析取范式的计数问题n个变元的极小项有2n个结论

15、：（1）永F式的主析取范式不存在，仍记为F （2）永T式的主析取范式全部由极小项构成 （3）可满足式由部分极小项构成 有2（2n）-1个联结词的扩充与归约已学过的联结词：，联结词的扩充一元：Pf1f2f3f40001110永假1恒等0否定1永真f1:F f2:P f3:p f4:T一元无需扩充二元：PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000100101101111扩充： 与非 ：P Q (PQ） 或非 ：P Q （PQ） 异或 ：PQ

16、(PQ)全功能集： 设A是运算符集，若在任一wff中可用A中运算符表示，则称A为全功能集。 若A中符号最少，则称A为最小全功能集。归约 找全功能集： ，是全功能集，但不是全功能集。例证明：是全功能集P(PP)PPTPP(PP)(PP)P(PP)FPP(P(P)P(P)(P(PP)(P(PP)PQ(PQ)(PQ)(PQ)(PQ)PQ(PQ)(PQ)(P)(Q)(PP)(QQ)PQPQ(PQ)PQP(QQ)PQ(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)(PQ)推理规则和证明方法如：H1：PH2：PQC：Q求Q是否为H1H2的有效结论。P(PQ)Q (P(PQ)Q P(PQ)QTQ是P

17、（PQ）的有效结论推理规则1、 前提引入 P 可在任何时刻引入2、 结论引入 T 若证明过程中，一个或多个wff永真蕴含S，则S可加入证明中3、 逻辑恒等式4、 永真蕴含式如： P Q PQ PQ PQ PQ P Q证明方法 H1H2.HnC 步骤 断言（真） 结论若H1H2.HnCH1H2.Hn C形如H1H2.HnC的证明即证：H1H2.HnC是永真的H1H2.HnC （H1H2.Hn）C （H1C）（H2C）.（HnC） (H1C)(H2C).(HnC)i使得HiC永真形如H1H2.HnC的证明（H1H2.Hn）C (H1H2.Hn)C H1H2.HnC (H1C)(H2C).(HnC)

18、 (H1C)(H2C).(HnC)即证：i有HnC永真 i有HnC形如H1H2.HnAB的证明H1H2.Hn（AB）（H1H2.Hn）A）B （H1H2.HnA）B H1H2.HnAB4. 归谬法相容性（一致性）： 设命题集合A1，A2，.,Ak，若A1A2.Ak为真，则称A1Ak 是相容的（或一致的），否则称为不相容的。 H1H2.HnC （H1H2.Hn）C (H1H2.HnC) 即证：H1H2.HnC为F H1，H2，.,Hn,C不相容计数问题： 一组前提可得多少个有效结论步骤：i）求H1H2.Hn的主合取范式 ii）确定有效结论设其主合取范式有n个极大项，则：CC2n1.P(PQ)P(

19、PQ) (PF)(PQ) (PQQ)(PQ) (PQ)(PQ)(PQ)PQ,PQ,PQ(PQ)(PQ):P(PQ(PQ):Q(PQ)(PQ):PQ(PQ)(PQ)(PQ):P(PQ)主范式的应用： 主合取推理的结论计数 主析取方案的设计谓词和量词个体域讨论问题的范围，记为DD中的元素称为个体个体常元：特指时，a,b,c.个体变元：泛指时，u,v,.,x,y,z谓词刻画个体的性质或几个个体间关系的模式叫谓词。特指时：谓词常元泛指时：谓词变元量词全能量词：xA(x)：对所有x，A(x)为T存在量词；特性量词：刻画个体属性1. 对，特性谓词作为前件加入2. 对，特性谓词作为合取式加入量化断言和命题的

20、关系1. 论域D是有限D=a1,a2,.,anxA(x)A(a1)A(a2).A(an)xA(x)A(a1)A(a2).A(a1)xA(x)A(0)A(1)A(2).xA(x)A(0)A(1)A(2).谓词公式原子公式：无联结词约束变元，自由变元辖域：紧接于量词之后最小的子公式叫量词的辖域约束，自由变元改名规则：操作对象：约束变元操作范围：全部替换选用符号：不在公式中出现的符号谓词演算的永真公式一、 基本概念A与B等价，设A、B是任意的谓词公式，E是指定的论域，若：（1） 对A B中的谓词指定E中的中心谓词（2） 对A B中个体常元、变元指定E中的个体有A与B的取值相同，则称A与B在E上是等价

21、的，记为A=B若E是任意的，当A与B的取值相同时，称A与B等价 2、类型：永真 永假 可满足二、谓词公式的永真式1、关于量词 xAA XAA A中无XxA(x)=A(Y) A(Y)=xA(x)所以xA(x)= xA(x)2、量词的否定xA(x) xA(x) xA(x) xA(x)3、量词的辖域 缩小x(A(x)P) xA(x)P 增大例：PQPQ P: xA(x) Q: xB(x)xA(x) xB(x) xA(x)xB(x) xA(x)xB(x)x(A(x)B(x) x(A(x) B(x)4、量词的分配形式x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x)x(

22、A(x) B(x)= xA(x)xB(x)x(A(x)B(x)= xA(x)xB(x)5、 量词与和的关系 x(A(x)B(x) xA(x) xB(x)6、 关于多个量词xyP（x,y）yx P（x,y）xyP(x,y) yx P(x,y)三、谓词运算的三个规则 1、代入规则 操作对象：自由变元 操作范围：全部替换 最多代入：若公式中含有n个谓词变元，最多可带入n个自由变元 2、置换规则 A是G的子公式，AB,以B代A的某些出现，得G，则GG 3、对偶规则 谓词公式A仅含 ， 与 ，T与F ，与，互换得A* AB A*B* AB A*-B*谓词的推理规则一、A(x)关于y是自由的-x不在y的辖

23、域中出现 推理规则：P规则，T规则，E1-E24，I1-I9，Q1-Q191、 全称特指 US2、 存在特指 ES3、 全称推广 UG4、 存在推广 EG集合 集合的行性质：唯一，无序，确定，抽象 集合与元素的子集： 集合与集合的关系： =描述集合的方法：列举法 命题法 归纳法 例：N=(0，1，2、)（1） ON（2） xN,X+1N（3） 若SN满足(1)(2),则S=N 幂集1. 定义：P(A)=X|XA2. 性质（1）P(A) (A) (2) P(A) (3)|A|=N |P(A)|=2 =2A集合的运算 1定义AB=XAXBAB= XAXBA=XUXA (A的补集) 绝对补A-B=X

24、| XAXB 相对补AB= XABXAB= 对称差AB=AB化为并、交、补、环和、环积 2性质 （1）关于 AA=A AA=A AB (2)关于补 (3)关于 (4)关于幂集 3、有限集合的计数问题ABmin (A=B）AB=ABABAB=ABAB归纳法和自然数 一、用归纳法描述集合E= 二、自然数 设A是任一集合，则A的后继A”意义如下 A”=A 性质: （1） (2) (3)0不是任一元素的后继 (4) (5) 若SN满足 则S=N三数学归纳法 1.第一数学归纳法（完全数学归纳法） P (n0） 2.第二数学归纳法（不完全数学归纳法） P (n0 ) 笛卡尔乘积一 序偶 Df，设x,y是任

25、意两个元素，称为次序偶 X:第一分量；Y：第二分量 1.Df.设A，B是任意集合 |xAyB称为A与B的笛卡尔乘积，记为AB 若A1,A2,，An,则 A1A2xAn=|xn Ai 称为n个集合的笛卡尔乘积例：A=1，2，B=C，D=4，5（AB）D=,D =,4,5,4,5=, A(BD)=1,1,2,2(AB)DA(BD)不满足交换律和结合律2. 性质B=,iffA=vB=证：“=” 假设A且B aA,bB 使ABAB,矛盾 假设AB AB,有xA,yBA且B矛盾Th2.设A，B，C，D是任意非空集合，则：ACBD，iffABCD，反之亦然Th3.假设A，B，C是任意集合，则：1） A（B

26、C）=ABAC2） （BC）A=BACA3） A（BC）=ABAC4） （BC）A=BACATh4.若|A|=n,|B|=m,则|AB|=nm第三章 二元关系 Df:1)AB的子集称为A到B的二元关系 2)A1A2An的子集称为A1，A2An间的n元关系（n2)3)若A1=A2=An=A 则n XA 的子集称为A上的n元关系一 Df RAB,称为A到B的二元关系A为前域，B为陪域RAA，称R为A上的二元关系d (R）=x|Rr (R)=y|R二 二元关系的表示 例：A=1,2,3,4,5 R=|x+y4 =,3. 归纳法 例：设RNN定义如下. R ,i f f xyxRy iff xy基础1

27、）R归纳2）R,有R,R极小3）仅由1）和2）得到的序偶R4. 关系矩阵 RAB,|A|=n,|B|=m MR=(Vij)nm,如下0 R Vij =1 否则称为R的关系矩阵1 0 10 1 00 0 0MR=y GR：R xx=y，环三 性质AxA若满足xA,有R,则称R是A上的自反关系例：A=1，2，3R=,1) 集上的关系是自反的 x(x), 永T2） 全关系是自反的 IA=|xA,称为A上的恒等关系 R自反，iff x(xAR)3) 非集合上的关系不是自反的 x(xA),永F2） 特征 R自反iff xA,有R Iff,IAR (集合特征）Iff，MR主对角线全“1”GR中每个点有自圈2. 反自反性3. 对称性AA,x,yA,R有R,则称R是A上的对称关系 2）特征 MR:（1）允许有“1” (2) 关