逻辑代数基础

简介: 逻辑代数基础

前言


逻辑代数系统由基本公式、常用公式、基本规则三部分构成。掌握了这些,设计出的电路可以尽可能地简单,减少故障几率和元件使用;编程时,如果掌握了逻辑函数化简,也能增加条件判断式的可读性,避免写出垃圾代码。

正文


逻辑代数中的三种基本运算


与、或、非


image.png

复合逻辑运算


最常见的有与非、或非、与或非、异或、同或等


8fa544031d1b4cbca72d28474985ae7d.png

异或:A⨁B=AB′+A′BA⨁B=AB′+A′B

同或:A⨀B=AB+A′B′A⨀B=AB+A′B′

异或与同或互为反运算

逻辑代数的基本公式和常用公式


image.png

基本公式


也叫布尔恒等式(证明方法包括真值表法和推演法)

正如加减乘除中存在各式运算律一样,逻辑运算也有运算规律。本章中,我们主要考虑与、或、非运算;异或、同或的运算律可以很方便地推导出来。我们从常量的运算开始。

image.png

以上相当于把真值表重新表达了一遍,比较直观。

接下来,我们开始把式子抽象化,把其中一个常量用变量 A 代替,看看常量与变量的运算(0律与1律)

image.png

这些也很好理解,只要把常量运算公式两两合并就可以得到。时刻要提示自己:变量的值只有0与1两种情况。

最后,是变量间的运算,即基本运算律

提示:在布尔运算中,运算优先级是 非 > 与 > 或

(1)交换律、结合律、分配律


这些公式基本和四则运算中的形式一样:

image.png

特别的分配律由于在布尔运算中,与运算和或运算常常处于可以互换的地位,因此,我们也有 A+BC=(A+B)(A+C) 。它和与对或的分配律非常接近,只是“与”和“或”调换了而已。可以证明一下公式的正确性:

image.png

分别用了:与逻辑分配律;重叠律(见(3));与逻辑分配律逆命题;1律

(2)还原律


image.png

很直观,变量两次取反后回到它本身。和语言中的“双重否定”是一个概念。

(3)重叠律


image.png

这两个式子比较难理解一点。但毕竟,布尔运算与四则运算中的“加法”“乘法”不是完全一致的——如果写成 A∪A=A, A∩A=A ,或者A || A == A, A && A == A ,表达的意思也是一样的。


在学习逻辑运算时,有许多迷惑性的符号——比如”0”与“1”,它们并不存在大小关系,而只是“真”与“假”的对应关系,与数字0和1无关

一道十分有趣的题目:能否通过 A + A = A 推导出 A = 0 ?

不能。由于布尔运算中没有“减法”运算,因此不可以把等式两端同时减去A。这告诉我们,虽然乍一看形式十分接近,但仍然不能被算术运算中的思维误导

(4)互补律


image.png

因为 A 与 A′ 中有且只有一个为1,因此可以回到1与0的运算上来理解。

(5)德·摩根定律


让我们一起迎接逻辑学中最著名、最经典、最实用的定律:

image.png

它如此优美,如此简洁地表明了与逻辑和或逻辑相互转化的关系。用非常“数学的话”说:

并集的补集是补集的交集,交集的补集是补集的并集

或者,用实际生活中的例子来理解——

一架飞机能成功降落的前提是前后起落架均已放下,缺一不可。所以,飞机不能降落,是因为“没有既放下前起落架又放下后起落架”,或者说是“没有放下前起落架或者没有放下后起落架”

此公式的用途之一是去括号。初学时,常常不自觉地写出

image.png

这样的式子。但实际上,去掉带取反的括号时,或要变与,与要变或。


还有一个用处是转换与逻辑和或逻辑。


如果在电路设计中只能使用“或”和“非”两种逻辑,我们也照样能表示出与逻辑—— AB=(A′+B′)′ 。


就比如,Minecraft游戏中便只有“或”和“非”,但能够创造出所有逻辑元件,原理就在于此

常用公式


以上公式都比较简单,使用时局限性也比较大。所以,我们还推导出了一系列常用公式。它们的使用频率要高得多(基础公式中的德·摩根定律除外)。

注意:在之前的描述中,尽量避免了出现“相加”“乘积”这样的字眼,以防造成误会;但为了叙述方便,接下来会经常出现这些词汇,它们不是一般意义上的“加法”“乘法”,请务必注意。

(1)吸收公式


image.png

两项相加,且其中一项( A )是另一项( AB )的因式时,另一项中的其他因式就被吸收了。

证明: A+AB=A(1+B)=A

先提取公因式;再运用1律

这里一系列公式的表达都非常简单抽象,而实际运用时,这两项不一定会长成A与AB的样子,但哪怕是 A(X+Y)M′+A(X+Y)(B+C′+D)M′E′F′G 这种庞大的式子,只要眼光毒辣,也能发现公因式,并化简成 A(X+Y)M′

(2)消因子公式


image.png

两项相加,且其中一项( A )取反后是另一项( A′B )的因式时,另一项中的这个相反因式就被消去了。(不要在意“吸收”“消去”这两个词到底有什么区别,只是为了区分这两个公式而已)

证明: A+A′B=(A+A′)(A+B)=1⋅(A+B)=A+B

其中提取公因式一步比较难想到,是证明过程的重点

要注意区分吸收公式和消因子公式:一个是相同的因式,一个是相反的因式;一个直接消去两项中较大的一项,一个仅仅去除部分因式

(3)并项公式


image.png

两项相加,部分因子相等( A ),剩下的互补( B 与 B′ ),那么可以合并成一项公有因子。

证明: AB+AB′=A(B+B′)=A⋅1=A

(4)消项公式


image.png

这个较为复杂:三项相加,两项中部分因子互补( AB 中的 A 与 A′C 中的 A′ ),剩下的都是第三项( BC )的因式(这两项的乘积不一定要和第三项相同,只需都是第三项的部分因式),那么第三项可以消去。

证明如下:

image.png

这个公式使用频率不算很高,但它的证明用到了一种很有用的思想——引入冗余项,以进行进一步简化。可以看到,证明开头,逆运用并项公式,创造了一个新的项,随后和另外两项分别合并。除了这种用法,还可以利用重叠律 A=A+A ,重复写入一项,再和其他项化简。这种方法很有用,但需要训练才能掌握(妙啊)。

基本规则


何谓基本规则?其实很难说清楚。但大概来讲,它描述了对等式进行恒等变形的一些方法。

(1)代入规则


将逻辑函数式中任一变量(或函数)用另一变量(或函数)替换,等式仍成立。这类似方程化简中的“换元法”思想。


如果有方程: F(M(X,Y,Z),B,C,...)=G(M(X,Y,Z),B,C,...) ,其中 F,G,M 均表示函数,则可以设 A=M(X,Y,Z) ,从而得到 F(A,B,C,...)=G(A,B,C,...) 。

举个例子,之前提到,常用公式不仅仅局限于两到三个变量的运算,还可以拓展到更多变量,这可以用代入规则解释。以消因子公式为例:如果有 (M+N)′+(M+N)XY ,则可以设 A=(M+N)′, B=XY ,把式子变形成 A+A′B ,然后运用公式。

(2)反演规则


回顾一下德·摩根定律: (AB)′=A′+B′, (A+B)′=A′B′ ,它可以同样通过应用代入规则,拓展到多个变量: (ABC...)′=A′+B′+C′+..., (A+B+C+...)′=A′B′C′...

注意看,等式的左边是一系列项的积或和,并进行了取反,而等式的右边则是这个反函数的展开。由此,我们可以推导出化简一个函数的反函数——或者叫反演——的规则。

得到函数的反演式有两步:

  • 加变乘,乘变加——对应德·摩根定律中与和或的转换,并保证运算顺序不变;
  • 对每个量取反(包括变量变为反变量和0变1,1变0),但保留非单变量的非号。

比如, ((A+B)C+0)D′⋅1 ,先变换符号: ((AB)+C⋅0)+D′+1 ,再对变量逐个取反: ((A′B′)+C′⋅1)+D+0 ,最后检查运算顺序,并通过添加去除括号调整: (A′B′+C′)⋅1+D+0 。就这样,得到了原函数的反演函数。

(3)对偶规则


这个规则便是之前提到的“与逻辑和或逻辑常常可以互换”的一个严谨定义。对偶式的得到也有两步:

  • 加变乘,乘变加,保证运算顺序不变;
  • 0变1,1变0。

对偶式的性质是:若两个逻辑式 F1=F2 成立,则它们的对偶式 F1D=F2D 也成立。比如由于 A(B+C)=AB+AC ,通过对偶变换就可以得到 A+BC=(A+B)(A+C)

对偶规则也是由德·摩根定律推导而来的,具体证明过程比较复杂,不再赘述。

其实,对偶式和反演式的本质区别就是没有了“对所有量取反”这一步。但为什么要保留“对常数取反”呢?如果没有这一步——比如, 0+A=A 的对偶等式是 1⋅A=A ;如果不对常数取反,就有 0⋅A=A ,显然不成立

总结


当今时代,数字电路已广泛应用于各个领域。数字电路比模拟电路的发展更迅猛,应用更广泛。所以对于当代的工科学生来说学好数字电路势在必行。其中,正确理解数字电路中的“数字”二字以及逻辑电路中的“逻辑”二字的含义是学好数字逻辑电路的基础。本文梳理了逻辑代数的基础内容,为今后数字逻辑电路的分析和设计打下良好的基础。


目录
相关文章
|
6月前
|
存储 Shell Python
零基础学会Python编程——不同的运算:算术、关系与逻辑(1)
零基础学会Python编程——不同的运算:算术、关系与逻辑(1)
102 0
|
存储 C++
深度复杂空间结构运算的逻辑
深度复杂空间结构运算的逻辑
|
5月前
|
SQL 数据可视化 算法
掌握计算机逻辑:离散数学中的逻辑和布尔代数
掌握计算机逻辑:离散数学中的逻辑和布尔代数
|
6月前
|
vr&ar
分解为BCNF范式的方法(详细讲解)
分解为BCNF范式的方法(详细讲解)
166 1
|
机器学习/深度学习 算法 Python
代数与逻辑:作业一 线性模型
代数与逻辑作业一,了解学习有关线性模型相关知识。
253 0
代数与逻辑:作业一 线性模型
|
数据可视化 数据挖掘 Python
代数与逻辑:作业二 主成分分析法
代数与逻辑作业二,了解学习有关主成分分析法的相关知识并通过Python进行实现。
95 0
代数与逻辑:作业二 主成分分析法
|
资源调度 Serverless vr&ar
【计算理论】计算理论总结 ( 上下文无关文法 ) ★★
【计算理论】计算理论总结 ( 上下文无关文法 ) ★★
201 0
【计算理论】计算理论总结 ( 上下文无关文法 ) ★★
|
算法
【计算理论】计算复杂性 ( 多项式等价引入 | 多项式时间规约 )
【计算理论】计算复杂性 ( 多项式等价引入 | 多项式时间规约 )
255 0
【计算理论】计算复杂性 ( 多项式等价引入 | 多项式时间规约 )
|
vr&ar
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★
323 0
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★
|
vr&ar
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 2 ) ★★
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 2 ) ★★
238 0
【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 2 ) ★★