下学期辅修汇编、计组,需要补一下数电知识。。有输入就要有输出,谨以此文纪念我数电学习道路。

布尔代数和逻辑函数的化简

概念

怎么说呢,就是取值只有01两个值的逻辑变量组成表达式、函数。其运算就是布尔代数。

运算

最基本逻辑运算:

  1. 与逻辑,当且两个都为1时结果为1,记做$P=A\cdot B$
  2. 或逻辑,两个变量有一个为1即为1,记做$P=A+B$
  3. 非逻辑,当一个变量为1时结果为0,为0时结果为1,记做$P=\overline{A}$

扩展逻辑运算:

  1. 与非:$\overline{A\cdot B}$
  2. 或非:$\overline{A+B}$
  3. 与或非:$\overline{AB+CD}$
  4. 异或:$A\oplus B=\overline{A}B+A\overline{B}$

公式

下面这些公式只需要了解与、与或形式即可,因为或、或与形式可以由前面推出来,对偶变换会讲到。

证明的话可以用穷举法来证明,就是将变量所有取值一一带入验证,这里略过。

常量间运算

与、与或形式 或、或与形式
$0\cdot 0=0$ $0+1=1$
$0\cdot 1=0$ $0+1=1$
$1\cdot 1=1$ $1+1=1$
$\overline{0}=1$ $\overline{1}=0$

变量与常量的运算

与、与或形式 或、或与形式
$A\cdot 0=0$ $A+1=1$
$A\cdot 1=1$ $A+0=A$
$A\cdot \overline A=0$ $A+\overline A=1$

运算定律

定律 与、与或形式 或、或与形式
交换律 $A\cdot B=B\cdot A$ $A+B=B+A$
结合律 $(AB)C=A(BC)$ $(A+B)+C=A+(B+C)$
分配律 $A(B+C)=AB+AC$ $A+BC=(A+B)(A+C)$
同一律 $A\cdot A=A$ $A+A=A$
还原律 $\overline{\overline A}=A$ $\overline{\overline A}=A$
摩根定律 $\overline{A\cdot B}=\overline A+\overline B$ $\overline{A+B}=\overline A\cdot \overline B$

常用公式

  1. $A+AB=A$
  2. $A+\overline AB=A+B$ (证: $A+\overline AB=A+\overline AB+AB=A+B(A+\overline A)=A+B$)
  3. $AB+\overline AC+BC=AB+\overline AC$ (证:$AB+\overline AC+BC=AB+\overline AC+(A+\overline A)BC=AB+\overline AC$)

基本规则

带入规则

在布尔等式中,用函数去代替变量,等式仍成立。

对偶规则

在一个布尔等式(或函数式)中,等式两边实行:

  1. 加乘互换
  2. 01互换

等式仍然成立,则称上述变换为对偶变换。

例如在等式$A(B+C)=AB+AC$两边实行对偶变换,得到:$A+BC=(A+B)(A+C)$,所以前面提到只需要了解一半的公式,用对偶式可以推出另一半。再例如$P=A+B$的对偶式$P’=AB$,两次对偶得到自己:$P’’=P$

反演规则

设$P$为一布尔函数,如果实行:

  1. 加乘互换
  2. 01互换
  3. 原反变换(就是式子中原变量写成反变量,反变量写成原变量)

例如求$P=ABC$的反函数:$\overline P=\overline A+\overline B+\overline C$

不过需要注意的是:
\begin{aligned} P=A+\overline{B+\overline C+\overline {D+\overline E}} \\ \overline P= \overline A\cdot (B+\overline C+\overline {D+\overline E}) \end{aligned}
需要将$\overline{B+\overline C+\overline {D+\overline E}}$看成一个整体。

展开规则

$$ \begin{aligned} P(x_1, x_2, \cdots, x_n) &= x_1P(\color{red}{1}, x_2, \cdots, x_n) + \overline x_1 P(\color{red}{0}, x_2, \cdots, x_n)\\ & = [x_1+P(\color{red}{1}, x_2, \cdots, x_n)][\overline x_1 + P(\color{red}{0}, x_2, \cdots, x_n)] \end{aligned} $$

化简

对于同一逻辑关系有多种形式,最简单的就是与项最少,每一与项的变量也最少

  1. 先将任意布尔式化为与或型的布尔式。
  2. 利用公式化简。
  3. 可以考虑合项法(提公因式)和配项法(乘以$(A+\overline A)$)
  4. 卡诺图化简法

最大项和最小项

这里举个例子来说什么是最大项和最小项吧。

给出真值表求表达式:

A B C P
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

先看结果有多少个1,这里有4个1,则表达式有4项最小项(或最大项)。然后将结果为1的表达式中,0的部分用反变量表示,1的部分用原变量表示。

那么结果为:
$$P=\overline A\overline BC+\overline AB\overline C + A\overline B\overline C + ABC$$

最小项

n个变量的最小项就是n个变量的乘积项,每个变量自出现一次,每个变量可以是原变量或者反变量。所以最小项有$2^n$个,最小项也可以用$m_i$表示,下标就是最小项对应二进制码相应的十进制表示。

A B 最小项 $m_i$
0 0 $\overline A\overline B$ $m_0$
0 1 $\overline A B$ $m_1$
1 0 $A\overline B$ $m_2$
1 1 $AB$ $m_3$

最大项

n个变量的最大项就是n个变量的逻辑和,每个变量自出现一次,每个变量可以是原变量或者反变量。所以最大项有$2^n$个,最大项也可以用$M_j$表示,下标就是最小项对应二进制码相应的十进制表示。

A B 最大项 $M_i$
0 0 $A+B$ $M_0$
0 1 $A+\overline B$ $M_1$
1 0 $\overline A+B$ $M_2$
1 1 $\overline A\overline B$ $M_3$

性质

  1. 最大项和最小项互为反函数。$\overline M_i=m_i$
  2. 全部最小项之和等于1。$\sum_{i=0}^{2^n-1}m_i = 1$
  3. 全部最大项之积等于0。$\prod_{i=0}^{2^n-1}M_i = 0$
  4. 一部分最小项之和的反等于另一部分最小项之和。$\overline {m_1+m_2}=m_0+m_3$
  5. 两个不同的最小项之积等于0。$ABC\cdot \overline ABC=0$
  6. 两个不同的最大项之和等于1。$(A+B+C)+(A+B+\overline C)=1$

卡诺图

卡诺图类似于真值表,在图上有$2^n$个格子,每个格子对应于一个最小项,相邻行列首尾格子表示的最小项逻辑相邻(即最小项只有一个变量不同,相邻项可消去一个变量),在化简表达式的时候,先画出该表达式卡诺图,然后尽可能大的圈出大小为$2^n$的矩形,将所有为1的格子圈出来后,几个矩形就是几个与项。

卡诺图

化简