1. 数的表示与布尔代数

# 数的编码与二进制表示

# 概述

• MSB（Most Significant Bit）： 最高有效位
• LSB（Least Significant Bit）： 最低有效位
• 左移与右移： 常见的位运算

# 常用编码

• BCD 码： 二进制编码的十进制数
• 格雷码： 一种循环码，任意两个相邻的代码只有一位不同

# 有符号数的表示与运算

• 补码与反码：
  • 反码（1 补码）： 正数与原码相同，负数是其绝对值的原码按位取反。
  • 补码（2 补码）： 正数与原码相同，负数是其绝对值的原码按位取反后加1。
• 加减法运算：
  • 加法： 补码运算可以直接将符号位和数值位一起相加。
  • 减法： 减去一个数等于加上这个数的补码。
• 溢出判断：
  • 当符号位的进位输入与进位输出不同时（异或结果为1），表示发生溢出。
• 溢出处理：
  • 增加位数来处理溢出。正数前面补0，负数前面补1。

---

# 布尔代数

# 布尔代数基本定律

• 交换律： $X+Y=Y+X$；$XY=YX$
• 结合律： $X+(Y+Z)=(X+Y)+Z$；$X(YZ)=(XY)Z$
• 分配律： $X(Y+Z)=XY+XZ$；$X+YZ=(X+Y)(X+Z)$
• 幂等律： $X+X=X$；$XX=X$
• 吸收律： $X+XY=X$；$X(X+Y)=X$
• 互补律： $X+X'=1$；$XX'=0$
• 一致性定理： $(X+Y)(X'+Z)(Y+Z)=(X+Y)(X'+Z)$；$XY+X'Z+YZ=XY+X'Z$

# 逻辑函数与运算

• 函数反演（德摩根律）：
  • 将 AND 运算转换为 OR 运算，0 变为 1，变量 $X$ 变为 $X'$。
• 异或（XOR）运算：
  • 异或： $X \oplus Y = X'Y + XY'$
  • 同或： $(X \oplus Y)' = XY + X'Y'$
  • 异或的性质： 满足交换律和结合律。
• 算术布尔函数：
  • 乘法： 对应布尔代数中的 与（AND） 运算。
  • 加法： 对应布尔代数中的 异或（XOR） 运算。
  • 加法进位： 对应布尔代数中的 与（AND） 运算。
• 真值表：
  • 包含 0、1 和 无关项（Don't Care），用于表示函数的输出。

---

# 布尔表达式的化简

# 逻辑函数的标准形式

• 最小项（Min-term）： 积之和（SOP, Sum of Products） 形式，用 $m$ 表示。
• 最大项（Max-term）： 和之积（POS, Product of Sums） 形式，用 $M$ 表示。
• 最小项与最大项的关系：
  • $m_i = M_i'$
  • $\sum m(i \in D) = \prod M(i \in D')$，其中 $D$ 是使函数输出为1的最小项索引集合。

# 化简方法

• 卡诺图（Karnaugh Map）：
  • 蕴含项（Implicant）： 卡诺图上圈出的1（或0）的矩形区域。
  • 本原蕴含项（Prime Implicant）： 无法被更大的矩形区域所覆盖的蕴含项。
  • 本质本原蕴含项（Essential Prime Implicant）： 至少覆盖一个无法被其他本原蕴含项覆盖的1（或0）的本原蕴含项。
• QM 算法（Quine-McCluskey Algorithm）：
  • 是一种更系统化的化简方法，通常用于变量较多的情况，本笔记不做深入要求。