命题逻辑-复合命题真值判断先确定原子命题真值p 真、q 假、r 真蕴含式仅在 “前件真、后件假” 时为假。谓词逻辑 - 存在性否定命题符号化“有的 A 不是 B” 是存在否定命题用存在量词 合取连接集合论 - 幂集元素个数计算幂集元素个数公式密集P(A)的元素个数 2*集合A的元素个数一阶逻辑 - 整数域公式真值判定当 x 为 0 或绝对值大于 1 的整数时不存在整数 y 使(x*y1)如 x2 时 y0.5 不是整数全称命题不成立真值为 0二元关系 - 定义域与值域的交集运算定义域dom把关系里每一对前, 后的“前”第一个数字拿出来组成的集合。值域ran把关系里每一对前, 后的“后”第二个数字拿出来组成的集合domR{2,3}ranS{1,2}二者交集为 {2}二元关系 - 关系的幂运算关系的幂(R^2R * R)规则是若存在中间元素 y满足 x,y∈R 且 y,z∈R则 x,z∈(R^2)填命题逻辑 - 必要条件命题符号化“只有 p才 q” 是必要条件假言命题含义是 q 成立则 p 必须成立即 q 为前件、p 为后件命题逻辑 - 主析取范式通过真值表或等值演算可得公式在 p0,q0m0、p0,q1m1、p1,q1m3时为真对应极小项 0、1、3 的析取一阶逻辑 - 有限个体域消去全称量词全称量词表示 “所有个体都满足性质”有限个体域中等值于所有个体谓词的合取存在量词则对应所有个体谓词的析取。集合计数 - 容斥原理整除问题容斥原理公式|A∪B||A||B|-|A∩B|能被 4 整除的有 75 个能被 6 整除的有 50 个能同时被 4 和 6 整除即被最小公倍数 12 整除的有 25 个总数为 7550-25100二元关系 - 关系的右复合运算右复合规则若 x,y∈R 且 y,z∈S则 x,z∈(R * S)集合关系 - 等价关系计数等价关系需满足自反、对称、传递与集合划分一一对应。2 元集合有 2 种划分1 个划分块全关系、2 个划分块恒等关系对应 2 个等价关系集合关系 - 等价类计算模 2 相等即 x 与 y 除以 2 余数相同1 除以 2 余 1集合中所有除以 2 余 1 的元素构成等价类即 1、3、5。集合关系 - 商集计算商集是所有等价类构成的集合。模 2 相等共有两个等价类奇数类和偶数类因此商集由这两个集合组成。图论 - 无向树握手定理无向树满足 “边数 顶点数 - 1”结合握手定理 “总度数 2× 边数”。设树叶数为 x总度数(42×3x10x)顶点数(3x)列方程(10x2(3x-1))解得 x6。根树 - 完全 2 元正则树顶点计数高度为 h 的完全 2 元正则树满二叉树总顶点数公式为(2^h1 -1)。代入 h3 得(2^4-115)对应树叶数为(2^h8)。图论 - 欧拉图判定定理无向欧拉图充要条件图连通且所有顶点度数均为偶数无奇度顶点半欧拉图为连通且恰好有 2 个奇度顶点。图论 - 二部图判定定理二部图充要条件图中不存在奇数长度的回路奇环这是判断二部图的核心定理。