02324 离散数学 密训资料VIP专享VIP免费

目录第1章命题与命题公式.........................................................................................................................2第2章命题逻辑的推理理论.................................................................................................................4第3章谓词逻辑.....................................................................................................................................5第4章集合.............................................................................................................................................7第5章关系与函数.................................................................................................................................9第6章代数系统的一般概念...............................................................................................................12第7章格与布尔代数...........................................................................................................................14第8章图...............................................................................................................................................14第9章图的应用...................................................................................................................................1611.1命题与命题联结词★★第1章命题与命题公式真值陈述句成立时，真值为真，记为T或1；陈述句不成立，真值为假，记为F或0。判断命题的条件①语句本身是个陈述句（疑问句、感叹句、祈使句等都不能是命题）；②有唯一的真值。原子命题不能再分解的命题。复合命题由原子命题通过联结词联结而成的命题。如“今天天气炎热，有雷阵雨”。联结词（设P，Q为两个命题）①否定：P的否定记为¬P。若P为T，¬P则为F；反之亦然。②合取：P和Q的合取记为P∧Q。当且仅当P、Q同时为T时，P∧Q的真值为T，其余情况为P∧Q的真值F。③析取：P和Q的析取记为P∨Q。当且仅当P、Q同时为F时，P∧Q的真值为F，其余情况为P∧Q的真值T。④条件：P和Q组成的条件命题记为P→Q。当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，其余情况P→Q的真值为T。⑤双条件：P和Q组成的双条件命题记为P↔Q。当P、Q的真值相同时，P↔Q的真值为T，否则P↔Q的真值为F。1.2命题公式的等值演算★★★PQRPQ(PQ)→RP→RQ→R(P→R)(Q→R)00001111001011110101010001111111100100101011111111010000111111112真值表①找出公式中所含的全体命题变元，从F…F开始写依次写出每个赋值，直到T…T为止；②按从简到繁的顺序写出公式的各个子公式；③对于各个赋值计算出各子公式的真值，直到最后计算出公式的真值。等价命题公式A和B，设P1，…，Pn为A和B的原子变元，若给P1，…，Pn任一组真值指派，A和B真值都相同，称A和B是等值的或等价的，记为AB。若至少存在一组真值指派，使其真值不同，称A和B不等值或不等价，记为AB。例：用列真值表的方法说明下列等价式成立：(PQ)→R(P→R)(Q→R)解：根据题给等式列出如下真值表，其中T和F用1和0表示。由真值表可知，对于PQR的任意指派，(PQ)→R和(P→R)(Q→R)真值都相同，所以(PQ)→R(P→R)(Q→R)永真式命题公式A，若在它的各指派情况下，取值均为真，称A为重言式或永真式。永假式命题公式A，若在它的各指派情况下，取值均为假，称A为矛盾式或永假式。可满足式命题公式A，若在它的各指派情况下，至少存在一组成真指派，称A是可满足式。若可满足式A至少存在一个成假赋值，则称A为非重言式的可满足式。结论①合式公式P是可满足式，等价于P至少存在一个成真赋值；②重言式一定是可满足式，但可满足式不一定是重言式；③若两个命题公式P和Q等价，则PQ是重言式。命题定律双重否定律A¬¬A幂等律AAA,AAA结合律(AB)CA(BC)；(AB)CA(BC)交换律AB...