离散数学

（二元）关系

• 性质：自反、对称、反对称、传递。
• 等价关系满足：自反、对称、传递。
• 关系可以表示为：有向图、矩阵、集合。
  • 矩阵乘可以表示关系的合成，在这里称为关系矩阵的布尔积。
• 闭包是包含原关系的具有某种性质的最小关系。
  • 传递闭包也就是连通性关系。

布尔代数

• 运算性质中 \(X+YZ=(X+Y)(X+Z)\) 需要特别记忆。
• 对偶：交换和与或、0和1。恒等式的两边取对偶，等式仍然成立。
• 反函数：在对偶的基础上把变量取反（德摩根定律的直接应用）。