离散数学知识点

绪论研究对象：离散量研究方法：解的存在性解的能行性研究内容：数理逻辑集合代数系统图论离散概率组合数学例题1、A、B、C、D四人参加四次长跑，问：“A在B前三次，B在C前三次，C在D前三次，D在A前三次”是否有解，若有求出，否则说明理由。方法一：AABCDn个元素的环形排列可拆成n个元素的BCDA线性排列DBCDABDABCC方法二：集合Sa={X|A在B前}Sa∩Sb∩Sc={ABCD}Sb={X|B在C前}Sa∩Sb∩Sd={DABC}Sc={X|C在D前}Sa∩Sc∩Sd={CDAB}Sd={X|D在A前}Sb∩Sc∩Sd={BCDA}例题2：在边长为1的正方形中任取五个点，则至少有两个点的距离≤√2/2。“中点分隔”将边长为1的正方形分成四个边长为1/2的小正方形，从中任取五个小点，必有两个小点来自一个小正方形。例题3：“布鲁英序列”----应用旋转鼓的设计，设旋转鼓有8个区域，旋转一圈可识别三位二进制数，如何确定磁粉位置。（阴影0，非阴影1）0—1—1—100000100010—1—1—10100111010010111101111思考题：四位二进制a1a2a3a4例题4：有五位小姐排成一排，所有小姐姓不同，穿的衣服颜色不同，喝不同的饮料，养不同的宠物，吃不同的水果，已知：1.钱小姐穿红衣服2.翁小姐养了一只狗3.陈小姐喝茶4.穿绿衣服的小姐在穿白色衣服小姐的左边，穿绿衣服的小姐在喝咖啡5.吃西瓜的小姐养鸟6.穿黄衣服的小姐吃梨7.站中间的小姐喝牛奶8.赵小姐站最左边9.吃桔子的小姐站在养猫的小姐旁边10.养鱼的小姐旁边小姐吃梨11.吃苹果的小姐喝香槟12.江小姐吃香蕉13.赵小姐站在穿蓝色衣服小姐旁边14.喝开水的小姐站在吃桔子的小姐旁边问每位小姐怎么站，她们分别养什么宠物，吃什么水果，喝什么饮料，穿什么颜色衣服，姓什么。12345姓赵陈钱江翁吃梨桔子西瓜香蕉苹果喝开水茶牛奶咖啡香槟颜色黄蓝红绿白宠物猫鱼鸟狗例题5：同态加密R+f:a^x(a1)R*f(x+y)=f(x)*f(y)Xf(x)yf(y)x+yf(x+y)例题6:100被2、3、5任意个整除A={X|被2整除}|A|=[100/2]=50B={X|被3整除}|B|=[100/3]=33C={X|被5整除}|C|=[100/5]=20|A∩B|=16|A∩C|=10|B∩C|=6|A∩B∩C|=31:|A|-|A∩B|-|A∩C|+|A∩B∩C|=278:|U|-|A∪B∪C|=|U|-(|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|)=26第一章命题逻辑求职25468317数理逻辑（一阶）演算标准型等价谓词逻辑证明推理应用类型一、命题：具有确定真假意义的陈述句（断言）永T命题：真值为T（1）永F命题：假值为F（0）1+1=10X3X的取值有关二进制十进制（T）（F）费晰逻辑原子命题：不可再拆开的命题复合命题：由原子命题和联结词构成的命题词：命题的符号表示，用大写字母表示二、联结词1.否定（not）¬A为命题，若A为T，¬A为FA:张明是上海人¬A：张明不是上海人2.合取（and）∧A、B是命题，A∧B为T,iff(当且仅当）A、B均为TABA∧BA∨BA→BABFFFFTTFTFTTFTFFTFFTTTTTT3.析取（or）∨可兼A、B是命题，A∨B为F,iffA、B均为F或不可兼量的估计4.蕴含命题（if-then）→A、B是命题，A→B为F，iffA为T，B为F前提结论A→B：原命题¬A→¬B:反命题（否命题）B→A：逆命题¬B→¬A:逆反（逆否）命题5.等值词（iff）AB为T，iffA、B的值相同P：生命息Q：战斗止（¬P→¬Q）∧(¬Q→¬P)¬P¬Q三、命题公式（合成公式）wff1.命题变元，常元常元：T、F（仅有两个）变元：在{T、F}中取值，用小写字母表示2.wff的定义一个wff定义递归（归纳）如下：基础i)命题变元，常元是wff归纳ii)若A、B是wff,则（¬A）,(A∧B),(A∨B),(A→B),(AB)也是wff极小化iii)有限次使用i）和ii)得到的符号命题是wff反进¬P¬Q((¬P)(¬Q))约定：①最外层括号可省略②优先级：¬∧∨→↔高低结合方向：左结合如(P→Q)→R若优先级，结合方向可确定计算顺序时，括号可省略括号是用来改变运算顺序的扩展：（1）n个变元的增值表有2^n行（指派），可构成2^2nwff（2）结合律：等值有结合侓ABC(AB)CA(BC)00010010011110010011001100011000111101000011010001111111重言式（永T式）一、基本概念1.指派（解释）——对wffG中全部变元的一组赋值，成为一个指派N个变元的全部指派有2^n个，可构成2的2^n个wff2.永T式（重言式）——在任何指派下为TP∨¬P3.永F式（矛盾式）——在任何指派下为FP∧¬P4.偶然式——非永T，亦非永FP→Q5.可满足式——至少在一组指派下取值为TP→Q,PQ二、逻辑恒等式1.定义：设A，B是wff,若AB为永T，则称A与B是逻辑恒等式，记为AB例题：A:P→QB:¬P∨Q求证A⇔B即求证AB为永T?PQP→Q¬P∨Q00111011111001011111所以P→Q⇔¬P∨Q2.常用恒等式P93.性质（1）.A⇔A,A↔A为永T自反性（2）.若A⇔B,则B⇔A对称性（3）.若A⇔B,且B⇔C,则A⇔C传递性4.三大规则（1）.代入规则代换实例：设wffG,P1，P2……Pn是G中全部命题的变元，A是wff，以A代Pi的全部出现，得到公式G’为G的一个代换实例。如wffG:(P→Q)∧(Q∨R)wffA:S∧RA代Q的全部出现：G’(P→(S∧R))∧((S∧R)∨R)代入规则：（1）.永T式的任何可代入实例是永T式（2）.永F式的任何可代入实例是永F式（3）.可满足式是任何可代入实例是不确定的例题：wffG:P→QG’G’P→R∨¬RR∨¬R→Q可满足式永T式R∨¬R→S∧¬S永F式（2）.重换规则设wffG，A是G的子公式，B是wff且A⇔B,以B代A的某些出现，得到公式G’,则G⇔G’例题：wffG:（P→Q）∧(Q→R)∧(P∨Q)化简，取A:P→QB:¬P∨QG1：(¬P∨Q)∧（Q→R）∧(P∨Q)G⇔G1取:A:Q→RB:¬Q∨RG⇔G2G2：(¬P∨Q)∧（¬Q∨R）∧(P∨Q)G1⇔G2（P→Q）∧(Q→R)∧(P∨Q)⇔(¬P∨Q)∧（¬Q∨R）∧(P∨Q)⇔（¬P∧¬Q∨¬P∧R∨Q∧¬Q∨Q∧R）∧(P∨Q)⇔¬P∧R∨Q∧P∨Q∧Q∧R∨Q∧R⇔（¬P∨P∨T）∧Q∧R⇔Q∧R（3）.对偶规则1.对偶式设wffG中仅含¬、∧、∨且不包含↔和→作用于变元在G中，将∧与∨互换，T与F互换，得新公式G*,则称G*为对偶式例题：求wffG:P∧(P→Q)的对偶式解：P∧（P→Q）⇔P∧(¬P∨Q)G*:P∨(¬P∧Q)求（P→Q）→R的G*（P→Q）→R⇔¬(P→Q)∨R⇔¬(¬P∨Q)∨R⇔P∧¬Q∨RG*:（P∨Q）∧R步骤：i)消→、↔ii)利用D-M定侓iii)写G*，必要时加括号（2）.对偶规则设A、B是wff，A*、B*分别为A、B对偶式，若A⇔B,则A*⇔B*如：P∨Q⇔Q∨PP∧Q⇔Q∧P三大规则规则对象范围要求结论代入变元Pi全部出现永F式……永T式重换子公式A某些出现A⇔BG⇔G’对偶∨、∧、T、F全部不含→、↔A⇔B则A*⇔B*四、永真蕴含式1.设A、B是wff，若A→B永T，则称A永真蕴含B，记为A⇒BA⇒BiffA→B永为TiffA为T，B必为T（肯定前件）IffB为F，A必为F（否定后件）2.常用永真蕴含式P10ABP⇒P∨QA→B永为TP→P∨Q⇔¬P∨P∨Q⇔T∨Q⇔T3.性质（1）A⇒AA→A永为T？A→A⇔¬A∨A⇔T（2）A⇒B,B⇒A则A⇔B（3）A⇒B,B⇒C则A⇒C4.A与A*关系例：A（P,Q）:P→Q⇔¬P∨QA*（P,Q）:¬P∧Q¬A*（P,Q）:P∨¬QA（¬P,¬Q）:P∨¬QA（¬P1，¬P2……¬Pn）⇔¬A*（P1，P2……Pn）A（P1，P2……Pn）⇔¬A*（¬P1，¬P2……¬Pn）¬A（¬P1，¬P2……¬Pn）⇔A*（P1，P2……Pn）¬A（P1，P2……Pn）⇔A*（¬P1，¬P2……¬Pn）th1:A⇔B,A*⇔B*th2:A⇒B,B*⇒A*范式一、基本积（和）1.基本积：变元、变元的否定、合取基本和：变元、变元的否定、析取如：pq基本积：p∧qp∧¬qp∧pp∧q∧¬p……基本和:p∨qp∨¬qp∨pp∨q∨¬p……2.性质基本积（和）永F（T）Iff变元及其否定同时出现在基本积（和）中3.范式（1）析取范式若wffA，A⇔A1∨A2∨……∨Ak（*）Ai是基本积，称（*）为A的析取范式若wffA，A⇔A1∧A2∧……∧Ac（**）Ai是基本积，称（**）为A的合取范式PS：把其中运算符最少的称为最简析取范式例：设wffA:P→（Q→R）求析（合）取范式解：P→（Q→R）⇔¬P∨(Q→R)⇔(¬P∨¬Q∨R)析取范式合取范式基本积：¬P,¬Q，R基本和：¬P∨¬Q∨R二、主析取范式1.极小项及其性质（1）Df：若基本积满足i).每个变元必须出现且进出现一次ii).变元及其否定不能同时出现则称该基本积为极小项。编码11100100pqp∧qp∧¬q¬p∧q¬p∧¬q000001010010100100111000（2）性质1.每个变元的极小项有2^n个2.每个极小项仅在变元的一组指派下取值为T，其余(2^n)-1组指派下取值为F3.任两个极小项的合取为永F式4.全部极小项的析取为永T式2.编码原变元——1反变元——0M0:¬P1∧¬P2……∧¬PnM1:¬P1∧……∧¬Pn-1∧Pn……M(2^n)-1:P1∧P2∧……∧Pn3.主析取范式设wffA，若A⇔A1∨A2∨……∨Ak（*）Ai为极小项，则称（*）为A的主析取范式例：求P→(Q→P)的主析式范式方法一：等值演算（E1~E24）P→(Q→P)⇔¬P∨(¬Q∨P)⇔¬P∨¬Q∨P⇔(¬P∨P)∨¬Q⇔T∨¬Q⇔T方法二：真值表PQP→(Q→P)⇔¬P∧¬Q∨¬P∧Q∨P∧¬Q∨P∧Q0011⇔M0∨M1∨M2∨M3011010111111求（P→Q）→P⇔¬（¬P∨Q）∨P⇔P∧¬Q∨P⇔P∧(¬Q∨T)⇔P∧T⇔P——最简范式⇔P∧¬Q∨P∧T⇔P∧¬Q∨P∧(Q∨¬Q)⇔P∧¬Q∨P∧Q∨P∧¬Q⇔M2∨M3⇔∑(2，3)三、主合取范式编码00011011pqp∨qp∨¬q¬p∨q¬p∨¬q0001110110111011011111102.编码原变元——0反变元——1极小项：11——p∧q极大项：11——¬p∨¬q¬M3⇔M3性质4：¬Mi⇔Mi注：永T式不存在主合取范式，仍记为T四．主合取/主析取范式的计数问题n个变元的极小项有2^n个结论：（1）永F式的主析取范式不存在，仍记为F（2）永T式的主析取范式全部由极小项构成（3）可满足式由部分极小项构成有2^（2^n）-1个联结词的扩充与归约已学过的联结词：{￢，∧，∨，→，↔}联结词的扩充一元：Pf1f2f3f40001110永假1恒等0否定1永真f1:Ff2:Pf3:¬pf4:T∴一元无需扩充二元：PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000100101101111扩充：↑与非：P↑Q⇔￢(P∧Q）↓或非：P↓Q⇔￢（P∨Q）⊕异或：P⊕Q⇔(P→Q)全功能集：设A是运算符集，若在任一wff中可用A中运算符表示，则称A为全功能集。若A中符号最少，则称A为最小全功能集。归约—找全功能集：{￢，∧}{￢，∧}{￢，∧，∨}{↓}{↑}是全功能集，但{￢}不是全功能集。例证明：