当前位置:网站首页>Fundamentals of digital circuits (II) logic algebra
Fundamentals of digital circuits (II) logic algebra
2022-07-06 14:41:00 【ブリンク】
Fundamentals of digital circuits ( Two ) Logic Algebra
One 、 Logical variables and logical functions
Students who are familiar with computer programming language should know , There is a boolean variable in many programming , It has and only has two values true and false (True and False, Sometimes you use 1 and 0). Boolean variable itself can actually be regarded as a logical variable , Conform to the characteristics of logical variables . Given a definite input , Usually the output can be uniquely determined .
We assume that there are two inputs A A A and B B B, There's an output F F F, Between them Logical expression Satisfy F = f ( A , B ) F=f(A,B) F=f(A,B), among A , B , F A,B,F A,B,F go by the name of Logical variable , Variable A A A and B B B be called Logical arguments , F F F go by the name of Logical dependent variable ( Also known as Logical functions ). Logical variables usually only take 0 or 1 Two values , It can be expressed in the circuit , High and low levels , The disconnection and connection of the switch .
In logic circuits , The definition of high and low level is not only determined by the unique value , They all have a certain constant pressure range . for example : stay TTL In circuit , The high level is usually 2-5V, The low level is usually 0-0.8V
Two 、 Basic logic operations and basic logic gates
There are three basic logical operations in logic circuits : Logic and , Logic or , Logic is not . The circuits used to realize these three logical operations are and gates , Or gate , Not gate . Here are the three logic operations and gate circuits .
1. Logic and
Logic and refers to when all the conditions that determine an event are true , This event will happen . The circuit shown in the figure below shows how the circuit controlled by a switch realizes and operates :
Only when S1 and S2 When both switches are closed at the same time , Light bulb: L It will light up ; If any one of the switches is off , Then the bulb L It won't light up .
take A A A, B B B, F F F All States of are listed in a table , This table is called Truth table , As shown in the following table :
From the truth table, we can see that it is similar to multiplication in operation and arithmetic , So logic and is also called Logical multiplication
F = A ⋅ B = A B F=A \cdot B=AB F=A⋅B=AB
Logic and have the following operations :
0 ⋅ 0 = 0 , 0 ⋅ 1 = 0 , 1 ⋅ 0 = 0 , 1 ⋅ 1 = 1 0\cdot 0=0,0\cdot 1=0,1\cdot0=0,1\cdot1=1 0⋅0=0,0⋅1=0,1⋅0=0,1⋅1=1
The symbol of logical and is shown in the figure below
2. Logic or
Logical and refers to all the conditions that determine an event , As long as any one of the conditions is satisfied , Events will happen . The circuit shown in the figure below shows how the circuit controlled by a switch realizes or operates :
When S1 and S2 When any one of the switches is closed , The lamp L Will light up ; If both switches are disconnected , Then the lamp L It won't light up .
The truth table of or door is shown in the figure below :
From the truth table, we can see that the or operation is similar to the addition in arithmetic , So logical or is also called Logical addition
F = A + B F=A + B F=A+B
Logic and have the following operations :
0 + 0 = 0 , 0 + 1 = 1 , 1 + 0 = 1 , 1 + 1 = 1 0 + 0=0,0 + 1=1,1+0=1,1+1=1 0+0=0,0+1=1,1+0=1,1+1=1
The symbol of logical and is shown in the figure below :
3. Logic is not
Logical non means when the condition is satisfied , It doesn't happen ; If the conditions are not met , events . The circuit shown below shows how to realize non operation with switch control circuit :
When the switch S When disconnected , Power Supply 、 resistance R And light bulb L Formation pathway , The bulb is on ; When the switch S When closed , Light bulb: L Switched S A short circuit , The light bulb doesn't work .
The truth table of non gate is shown in the figure below :
The expression is :
F = A ‾ F=\overline{A} F=A
The non operation rule is :
0 ‾ = 1 , 1 ‾ = 0 \overline{0}=1,\overline{1}=0 0=1,1=0
4. Compound logic operation
(1) And non operation
The logical expression is : F = A B ‾ F=\overline{AB} F=AB, It is done by logical variables first and , And then do the non operation , The logical symbols are shown in the figure below :
(2) Or not
The logical expression is : F = A + B ‾ F=\overline{A+B} F=A+B, It is done by logical variables first or operation , And then do the non operation , The logical symbols are shown in the figure below :
(3) And or not operation
The logical expression is : F = A B + C D ‾ F=\overline{AB+CD} F=AB+CD, It is done by logical variables first and , Do or calculate again , Finally, do non operation to get , The logical symbols are shown in the figure below :
(4) Exclusive or operation
The logical expression is : F = A B ‾ + A ‾ B = A ⊕ B F=A\overline{B}+\overline{A}B=A\oplus B F=AB+AB=A⊕B. The rule of exclusive or operation is : When the two input logical variables are the same , The output of 0; When the two input logical variables are different , The output of 1. The logical symbols are shown in the figure below :
(5) The same or operation
The logical expression is : F = A B + A B ‾ = A ⊙ B F=AB+\overline{AB}=A\odot B F=AB+AB=A⊙B. The same or operation rule is : When the two input logical variables are the same , The output of 1; When the two input logical variables are different , The output of 0. The logical symbols are shown in the figure below :
3、 ... and 、 Basic formulas and common formulas of logical algebra
1. The basic formula
(1)0-1 Law A ⋅ 0 = 0 A\cdot 0=0 A⋅0=0 A + 1 = 1 A+1=1 A+1=1
(2) The law of self equivalence A ⋅ 1 = A A\cdot 1=A A⋅1=A A + 0 = A A+0=A A+0=A
(3) Overlapping law A ⋅ A = A A\cdot A=A A⋅A=A A + A = A A+A=A A+A=A
(4) Law of complementarity A ⋅ A ‾ = 0 A\cdot \overline{A}=0 A⋅A=0 A + A ‾ = 1 A+ \overline{A}=1 A+A=1
(5) Commutative law A ⋅ B = B ⋅ A A\cdot B=B\cdot A A⋅B=B⋅A A + B = B + A A+B=B+A A+B=B+A
(6) Associative law A ⋅ ( B ⋅ C ) = ( A ⋅ B ) ⋅ C A\cdot(B\cdot C)=(A\cdot B)\cdot C A⋅(B⋅C)=(A⋅B)⋅C
A + ( B + C ) = ( A + B ) + C A+(B+C)=(A+B)+C A+(B+C)=(A+B)+C
(7) Distribution rate A ⋅ ( B + C ) = A B + A C A\cdot(B+C)=AB+AC A⋅(B+C)=AB+AC
A + ( B + C ) = ( A + B ) ( A + C ) A+(B+C)=(A+B)(A+C) A+(B+C)=(A+B)(A+C)
(8) absorptivity A ⋅ ( A + B ) = A A\cdot(A+B)=A A⋅(A+B)=A A + A B = A A+AB=A A+AB=A
(9) Inversion law A B ‾ = A ‾ + B ‾ \overline{AB}=\overline{A}+\overline{B} AB=A+B A + B ‾ = A ‾ ⋅ B ‾ \overline{A+B}=\overline{A}\cdot \overline{B} A+B=A⋅B
(10) Double negative rate A ‾ ‾ = A \overline{\overline{A}} = A A=A
Inversion law is one of the most widely used , It plays an important role in simplifying logical expressions
2. The basic rule
(1) Substitution rule
In any logical equation , If all the variables on both sides of the equation are replaced by a logical function , Then this equation still holds .
for example : A ⋅ B ‾ = A ‾ + B ‾ \overline{A\cdot B}=\overline{A}+\overline{B} A⋅B=A+B Medium A A A Use F = A C F=AC F=AC replace , Then the original formula becomes : A C ⋅ B ‾ = A C ‾ + B ‾ = A ‾ + B ‾ + C ‾ \overline{AC\cdot B}=\overline{AC}+\overline{B}=\overline{A}+\overline{B}+\overline{C} AC⋅B=AC+B=A+B+C. Still established .
(2) Inversion rules
When we need to solve a logical function F F F The inverse function of F ‾ \overline{F} F when , Inversion rules can be used .
Only need to F F F Medium
⋅ change by + , + change by ⋅ , 1 change by 0 , 0 change by 1 , change The amount take back \cdot Turn into +, + Turn into \cdot ,1 Turn into 0 ,0 Turn into 1, The variable is inverted ⋅ change by +,+ change by ⋅,1 change by 0,0 change by 1, change The amount take back
that will do .
It should be noted that : When changing the inverse variable , If there are more than two variables, the common negative sign remains unchanged
for example : seek F = A + B + C ‾ + D + E ‾ ‾ ‾ + ( G ⋅ H ) F=A+\overline{B+ \overline{C} +\overline{D+\overline{ E}}}+(G\cdot H) F=A+B+C+D+E+(G⋅H) The inverse function of
F ‾ = A ‾ ⋅ B ‾ ⋅ C ⋅ D ‾ ⋅ E ‾ ‾ ⋅ ( G ‾ + H ‾ ) \overline{F}=\overline{A}\cdot \overline{\overline{B}\cdot C \cdot \overline{\overline{D}\cdot E}}\cdot (\overline{G}+\overline{H}) F=A⋅B⋅C⋅D⋅E⋅(G+H)
(3) The duality rule
When we need to solve a logical function F F F Dual form of F ′ F' F′ when ,
Only need to F F F Medium
⋅ change by + , + change by ⋅ , 1 change by 0 , 0 change by 1 \cdot Turn into +, + Turn into \cdot ,1 Turn into 0 ,0 Turn into 1 ⋅ change by +,+ change by ⋅,1 change by 0,0 change by 1
that will do .
Two logical functions are equal ⇔ \Leftrightarrow ⇔ The duality of two logical functions is equal ( Sufficient and necessary conditions )
for example : seek F = A ⋅ B + A ‾ ⋅ C + B ⋅ C F=A\cdot B+\overline{A}\cdot C+B\cdot C F=A⋅B+A⋅C+B⋅C Dual form of
F ′ = ( A + B ) ⋅ ( A ‾ + C ) ⋅ ( B + C ) F'=(A+B)\cdot (\overline{A}+C) \cdot (B+C) F′=(A+B)⋅(A+C)⋅(B+C)
3. Common formula
The formula 1 A B + A B ‾ = A AB+A\overline{B}=A AB+AB=A
prove : A B + A B ‾ = A ( B + B ‾ ) = A AB+A\overline{B}=A(B+\overline{B})=A AB+AB=A(B+B)=A
The formula 2 A + A B ‾ = A + B A+A\overline{B}=A+B A+AB=A+B
prove : A + A ‾ B = ( A + A ‾ ) ⋅ ( A + B ) = A + B A+\overline{A}B=(A+\overline{A})\cdot (A+B)=A+B A+AB=(A+A)⋅(A+B)=A+B
The formula 3 A B + A ‾ C + B C = A B + A ‾ C AB+\overline{A}C+BC=AB+\overline{A}C AB+AC+BC=AB+AC
prove : A B + A ‾ C + B C = A B + A ‾ C + B C ( A + A ‾ ) = A B + A ‾ C + A B C + A ‾ B C = A B + A ‾ C AB+\overline{A}C+BC=AB+\overline{A}C+BC(A+\overline{A})=AB+\overline{A}C+ABC+\overline{A}BC=AB+\overline{A}C AB+AC+BC=AB+AC+BC(A+A)=AB+AC+ABC+ABC=AB+AC
The formula 4 A B + A ‾ C ‾ = A B ‾ + A ‾ C ‾ \overline{AB+\overline{A}C}=A\overline{B}+\overline{A}\overline{C} AB+AC=AB+AC
prove : A little
The formula 5 A ⊕ B ‾ = A ⊙ B \overline{A\oplus B}=A\odot B A⊕B=A⊙B
prove : A little
Four 、 Briefly introduce several ideas of using formula method to simplify
The names of the methods here are all given by the author himself , Perhaps it is more in line with the meaning of the formula
(1) Go heteromorphic
A + A B A+AB A+AB type , here A , B A,B A,B It can be a logical expression rather than a separate logical variable . In direct discharge “ Alien species ”: B B B, The rest as a result is A + A B = A A+AB=A A+AB=A
(2) Go non type
A + A ‾ B A+\overline{A}B A+AB type , here A , B A,B A,B It can be a logical expression rather than a separate logical variable . In direct discharge “ Non item ”: A ‾ \overline{A} A, The rest as a result is A + A ‾ B = A + B A+\overline{A}B=A+B A+AB=A+B
(3) De inversion
A B + A ‾ B AB+\overline{A}B AB+AB type , here A , B A,B A,B It can be a logical expression rather than a separate logical variable . In direct discharge “ The opposite ”: A ‾ \overline{A} A and A A A, The rest as a result is A B + A ‾ B = B AB+\overline{A}B=B AB+AB=B
(4) Three deficiencies and one type
It is generally used to have three variables , But in the and or formula with only two logical variables for each term in the logical expression , You can operate after the lack of a logical variable ( X + X ‾ ) (X+\overline{X}) (X+X), X X X Indicates the missing logical variable .
A simple example : F = A B ‾ + B C ‾ F=A\overline{B}+B\overline{C} F=AB+BC Only need A B ‾ A\overline{B} AB After and operation a ( C + C ‾ ) (C+\overline{C}) (C+C), B C ‾ B\overline{C} BC After and operation a ( A + A ‾ ) (A+\overline{A}) (A+A) that will do .
5、 ... and 、 Use Karnaugh map to simplify logical expressions
1. Minimum term
Want to use Karnaugh map for simplification , First of all, we need to understand the concept of minimum term .
In the Carnot , Each square represents a minimum term . There is n n n In the logical function of logical variables , The product term of all variables is called the minimum term . Why is it called the minimum term , Because every variable only appears once , And they all appear in the form of itself or anti variable . Analogous to making permutations , List all possible variables that can occur only once , Is all its smallest terms .
for example : Two variables A , B A,B A,B The minimum term of is 2 2 = 4 2^2=4 22=4 individual ( A B , A B ‾ , A ‾ B , A B ‾ AB,A\overline{B},\overline{A}B,\overline{AB} AB,AB,AB,AB)
For convenience , Use m i m_i mi Record the smallest item in the form of . Its notation is : When a logical variable appears as an original variable in the minimum term , Write it down as 1; When it appears as an inverse variable , Write it down as 0. Then convert it into decimal numbers , What is this decimal number , that m i m_i mi The subscript i i i Just for how much .
for example : A ‾ B C \overline{A}BC ABC Recorded as binary number 011, and 011 The corresponding decimal number is 3, so A ‾ B C \overline{A}BC ABC Write it down as m 3 m_3 m3
When we are familiar with the concept of minimum term , We can convert any logic function into the form of the minimum term , And use m i m_i mi Formal representation of .
for example : A B C + A B C ‾ + A ‾ B C + A B ‾ C = m 7 + m 6 + m 3 + m 1 ABC+AB\overline{C}+\overline{A}BC+\overline{AB}C=m_7+m_6+m_3+m_1 ABC+ABC+ABC+ABC=m7+m6+m3+m1
2. Karnaugh map
(1) Two variable Karnaugh map
The following figure is a two variable Karnaugh map :
The picture shows , A A A and B B B There are two values 0 and 1, They can form four combinations , Each combination is a minimum term . If the minimum term is used to represent the Karnaugh map, it is shown in the following figure :
You can see that its binary value corresponds to the minimum term m i m_i mi Medium i i i
(2) Three variable Karnaugh map
Here is a three variable Karnaugh map :
The picture shows , A A A, B B B and C C C There are two values 0 and 1, They can form eight combinations , Each combination is a minimum term . If the minimum term is used to represent the Karnaugh map, it is shown in the following figure :
You can also see that its binary value corresponds to the minimum term m i m_i mi Medium i i i
(4) Four variable Karnaugh map
The minimum term form of four variable Karnaugh map is given :
Its determination method is consistent with the determination method of the minimum term of two variables and three variables .
Three variable and four variable Karnaugh map 00,01,11,10 The arrangement of ensures that there is only one different number between two , The adjacent conditions are met
3. Karnaugh map represents logic function
When we know the logic function , You can first simplify the logical function into a minimum term expression , Then fill the value in the Karnaugh map corresponding to the minimum term as 1, Fill in the rest as 0 that will do , You can also fill in the Karnaugh map directly according to the expression ; If what we know directly is minimal term expression , You can directly fill in the corresponding position in the Karnaugh map 1, Fill in the rest 0.
for example :
F = A B C + A B C ‾ + A ‾ B C + A B ‾ C = m 7 + m 6 + m 3 + m 1 F=ABC+AB\overline{C}+\overline{A}BC+\overline{AB}C=m_7+m_6+m_3+m_1 F=ABC+ABC+ABC+ABC=m7+m6+m3+m1
We know its minimal term expression , You can directly fill in numbers in the blank Karnaugh map , As shown in the figure below :
4. Reduction method
(1) Merge minimums
We can put the adjacent 8 individual 、4 individual 、2 individual 、1 The smallest collar of , A merger . As shown in the figure below :
The red circle in the figure indicates that these two items are merged , It is easy to see that they are adjacent . I have to pay attention to , The boundary of Karnaugh map is not the boundary in the practical sense .
for example :
These two and other similar situations belong to the adjacent situation when two variables are merged
For the case of four variables , The following two series are obviously adjacent :
besides , The following cases also belong to four adjacent variables
There are several combinations of eight variables ( Including similar situations ):
give an example : Simplify with Karnaugh map F = A B C D ‾ + A B C ‾ D + A ‾ B C ‾ + A B D ‾ + A ‾ B C + B C D F=\overline{ABCD}+A\overline{BC}D+\overline{A}B\overline{C}+AB\overline{D}+\overline{A}BC+BCD F=ABCD+ABCD+ABC+ABD+ABC+BCD
Draw the logical expression in the Karnaugh diagram , And merge in the way we just explained :
here , We just need to write the circled part of the Karnaugh map in the form of a logical expression , Then take or operate them
F = A B C ‾ D + A C D ‾ + A ‾ B + B C + B D ‾ F=A\overline{BC}D+\overline{ACD}+\overline{A}B+BC+B\overline{D} F=ABCD+ACD+AB+BC+BD
(2) Simplification of Karnaugh map with irrelevant terms
In some logic functions , The minimum item corresponding to some combinations of variable values will not appear or is not allowed , These minimum terms are called constraint terms . It is generally used in Karnaugh map " × \times ×" Express . When simplifying in this case , You can merge the smallest items with the help of irrelevant items .
give an example :
F ( A , B , C , D ) = ∑ ( m 15 , m 13 , m 10 , m 6 , m 4 ) + ∑ d ( m 8 , m 7 , m 5 , m 2 , m 1 , m 0 ) F(A,B,C,D)=\sum(m_{15},m_{13},m_{10},m_6,m_4)+\sum_d(m_8,m_7,m_5,m_2,m_1,m_0) F(A,B,C,D)=∑(m15,m13,m10,m6,m4)+∑d(m8,m7,m5,m2,m1,m0)
You can treat irrelevant items as 1 To process and merge .
Then write the circled ones as logical expressions .
F = A ‾ B + B D + B D ‾ F=\overline{A}B+BD+\overline{BD} F=AB+BD+BD
first draft 2022/5/5
边栏推荐
- 【指针】使用插入排序法将n个数从小到大进行排列
- 浙大版《C语言程序设计实验与习题指导(第3版)》题目集
- 指针--剔除字符串中的所有数字
- [paper reproduction] cyclegan (based on pytorch framework) {unfinished}
- Statistics 8th Edition Jia Junping Chapter 12 summary of knowledge points of multiple linear regression and answers to exercises after class
- Captcha killer verification code identification plug-in
- AQS details
- Intranet information collection of Intranet penetration (3)
- 【指针】删除字符串s中的所有空格
- JDBC看这篇就够了
猜你喜欢
《統計學》第八版賈俊平第七章知識點總結及課後習題答案
Attack and defense world misc practice area (GIF lift table ext3)
1.支付系统
Résumé des points de connaissance et des réponses aux exercices après la classe du chapitre 7 de Jia junping dans la huitième édition des statistiques
High concurrency programming series: 6 steps of JVM performance tuning and detailed explanation of key tuning parameters
An unhandled exception occurred when C connected to SQL Server: system Argumentexception: "keyword not supported:" integrated
Mysql的事务是什么?什么是脏读,什么是幻读?不可重复读?
Intranet information collection of Intranet penetration (5)
Statistics 8th Edition Jia Junping Chapter 5 probability and probability distribution
Transplant hummingbird e203 core to Da Vinci pro35t [Jichuang xinlai risc-v Cup] (I)
随机推荐
数字电路基础(四) 数据分配器、数据选择器和数值比较器
【指针】八进制转换为十进制
The most popular colloquial system explains the base of numbers
数字电路基础(三)编码器和译码器
captcha-killer验证码识别插件
内网渗透之内网信息收集(二)
Record an edu, SQL injection practice
Internet Management (Information Collection)
《统计学》第八版贾俊平第四章总结及课后习题答案
函数:计算字符串中大写字母的个数
JDBC transactions, batch processing, and connection pooling (super detailed)
This article explains in detail how mockmvc is used in practical work
我的第一篇博客
On the idea of vulnerability discovery
Function: find 1-1/2+1/3-1/4+1/5-1/6+1/7-... +1/n
MySQL中什么是索引?常用的索引有哪些种类?索引在什么情况下会失效?
c语言学习总结(上)(更新中)
Statistics, 8th Edition, Jia Junping, Chapter VIII, summary of knowledge points of hypothesis test and answers to exercises after class
数字电路基础(一)数制与码制
Constants, variables, and operators of SystemVerilog usage