命题逻辑-复合命题真值判断

先确定原子命题真值：p 真、q 假、r 真，蕴含式仅在 “前件真、后件假” 时为假。

谓词逻辑 - 存在性否定命题符号化

“有的 A 不是 B” 是存在否定命题，用存在量词 + 合取连接

集合论 - 幂集元素个数计算

幂集元素个数公式：密集P(A)的元素个数 = 2*集合A的元素个数

一阶逻辑 - 整数域公式真值判定

当 x 为 0 或绝对值大于 1 的整数时，不存在整数 y 使(x*y=1)（如 x=2 时 y=0.5 不是整数），全称命题不成立，真值为 0；

二元关系 - 定义域与值域的交集运算

• 定义域（dom）：把关系里每一对 <前, 后> 的“前”（第一个数字）拿出来组成的集合。

• 值域（ran）：把关系里每一对 <前, 后> 的“后”（第二个数字）拿出来组成的集合

domR={2,3}，ranS={1,2}，二者交集为 {2}

二元关系 - 关系的幂运算

关系的幂(R^2=R * R)，规则是：若存在中间元素 y，满足 <x,y>∈R 且 < y,z>∈R，则 < x,z>∈(R^2)

填

命题逻辑 - 必要条件命题符号化

“只有 p，才 q” 是必要条件假言命题，含义是 q 成立则 p 必须成立，即 q 为前件、p 为后件

命题逻辑 - 主析取范式

通过真值表或等值演算可得，公式在 p=0,q=0（m0）、p=0,q=1（m1）、p=1,q=1（m3）时为真，对应极小项 0、1、3 的析取

一阶逻辑 - 有限个体域消去全称量词

全称量词表示 “所有个体都满足性质”，有限个体域中等值于所有个体谓词的合取；存在量词则对应所有个体谓词的析取。

集合计数 - 容斥原理（整除问题）

容斥原理公式：|A∪B|=|A|+|B|-|A∩B|

能被 4 整除的有 75 个，能被 6 整除的有 50 个，能同时被 4 和 6 整除（即被最小公倍数 12 整除）的有 25 个，总数为 75+50-25=100

二元关系 - 关系的右复合运算

右复合规则：若 <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，总度数(4+2×3+x=10+x)，顶点数(3+x)，列方程(10+x=2(3+x-1))，解得 x=6。

根树 - 完全 2 元正则树顶点计数

高度为 h 的完全 2 元正则树（满二叉树）总顶点数公式为(2^（h+1）   -1)。代入 h=3 得(2^4-1=15)，对应树叶数为(2^h=8)。

图论 - 欧拉图判定定理

无向欧拉图充要条件：图连通，且所有顶点度数均为偶数（无奇度顶点）；半欧拉图为连通且恰好有 2 个奇度顶点。

图论 - 二部图判定定理

二部图充要条件：图中不存在奇数长度的回路（奇环），这是判断二部图的核心定理。