ens 1990
2010-03-26, 15:47
Lessons In Electric Circuits -- Volume IV
Chapter 7
BOOLEAN ALGEBRA
Introduction (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65650)
Boolean arithmetic (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65651)
Boolean algebraic identities (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65652)
Boolean algebraic properties (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65653)
Boolean rules for simplification (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65654)
Circuit simplification examples (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65655)
The Exclusive-OR function (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65656)
DeMorgan's Theorems (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65657)
Converting truth tables into Boolean expressions (http://openbookproject.net//electricCircuits/Digital/DIGI_7.html#xtocid65658)
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Rules of addition for Boolean quantities
"Gee Toto, I don't think we're in Kansas anymore!"
Dorothy, in The Wizard of Oz
Introduction
Mathematical rules are based on the defining limits we place on the particular numerical quantities dealt with. When we say that 1 + 1 = 2 or 3 + 4 = 7, we are implying the use of integer quantities: the same types of numbers we all learned to count in elementary education. What most people assume to be self-evident rules of arithmetic -- valid at all times and for all purposes -- actually depend on what we define a number to be.
For instance, when calculating quantities in AC circuits, we find that the "real" number quantities which served us so well in DC circuit analysis are inadequate for the task of representing AC quantities. We know that voltages add when connected in series, but we also know that it is possible to connect a 3-volt AC source in series with a 4-volt AC source and end up with 5 volts total voltage (3 + 4 = 5)! Does this mean the inviolable and self-evident rules of arithmetic have been violated? No, it just means that the rules of "real" numbers do not apply to the kinds of quantities encountered in AC circuits, where every variable has both a magnitude and a phase. Consequently, we must use a different kind of numerical quantity, or object, for AC circuits (complex numbers, rather than real numbers), and along with this different system of numbers comes a different set of rules telling us how they relate to one another.
An expression such as "3 + 4 = 5" is nonsense within the scope and definition of real numbers, but it fits nicely within the scope and definition of complex numbers (think of a right triangle with opposite and adjacent sides of 3 and 4, with a hypotenuse of 5). Because complex numbers are two-dimensional, they are able to "add" with one another trigonometrically as single-dimension "real" numbers cannot.
Logic is much like mathematics in this respect: the so-called "Laws" of logic depend on how we define what a proposition is. The Greek philosopher Aristotle founded a system of logic based on only two types of propositions: true and false. His bivalent (two-mode) definition of truth led to the four foundational laws of logic: the Law of Identity (A is A); the Law of Non-contradiction (A is not non-A); the Law of the Excluded Middle (either A or non-A); and the Law of Rational Inference. These so-called Laws function within the scope of logic where a proposition is limited to one of two possible values, but may not apply in cases where propositions can hold values other than "true" or "false." In fact, much work has been done and continues to be done on "multivalued," or fuzzy logic, where propositions may be true or false to a limited degree. In such a system of logic, "Laws" such as the Law of the Excluded Middle simply do not apply, because they are founded on the assumption of bivalence. Likewise, many premises which would violate the Law of Non-contradiction in Aristotelian logic have validity in "fuzzy" logic. Again, the defining limits of propositional values determine the Laws describing their functions and relations.
The English mathematician George Boole (1815-1864) sought to give symbolic form to Aristotle's system of logic. Boole wrote a treatise on the subject in 1854, titled An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, which codified several rules of relationship between mathematical quantities limited to one of two possible values: true or false, 1 or 0. His mathematical system became known as Boolean algebra.
All arithmetic operations performed with Boolean quantities have but one of two possible outcomes: either 1 or 0. There is no such thing as "2" or "-1" or "1/2" in the Boolean world. It is a world in which all other possibilities are invalid by fiat. As one might guess, this is not the kind of math you want to use when balancing a checkbook or calculating current through a resistor. However, Claude Shannon of MIT fame recognized how Boolean algebra could be applied to on-and-off circuits, where all signals are characterized as either "high" (1) or "low" (0). His 1938 thesis, titled A Symbolic Analysis of Relay and Switching Circuits, put Boole's theoretical work to use in a way Boole never could have imagined, giving us a powerful mathematical tool for designing and analyzing digital circuits.
In this chapter, you will find a lot of similarities between Boolean algebra and "normal" algebra, the kind of algebra involving so-called real numbers. Just bear in mind that the system of numbers defining Boolean algebra is severely limited in terms of scope, and that there can only be one of two possible values for any Boolean variable: 1 or 0. Consequently, the "Laws" of Boolean algebra often differ from the "Laws" of real-number algebra, making possible such statements as 1 + 1 = 1, which would normally be considered absurd. Once you comprehend the premise of all quantities in Boolean algebra being limited to the two possibilities of 1 and 0, and the general philosophical principle of Laws depending on quantitative definitions, the "nonsense" of Boolean algebra disappears.
It should be clearly understood that Boolean numbers are not the same as binary numbers. Whereas Boolean numbers represent an entirely different system of mathematics from real numbers, binary is nothing more than an alternative notation for real numbers. The two are often confused because both Boolean math and binary notation use the same two ciphers: 1 and 0. The difference is that Boolean quantities are restricted to a single bit (either 1 or 0), whereas binary numbers may be composed of many bits adding up in place-weighted form to a value of any finite size. The binary number 100112 ("nineteen") has no more place in the Boolean world than the decimal number 210 ("two") or the octal number 328 ("twenty-six").
Boolean arithmetic
Let us begin our exploration of Boolean algebra by adding numbers together:
http://openbookproject.net//electricCircuits/Digital/14006.png
The first three sums make perfect sense to anyone familiar with elementary addition. The last sum, though, is quite possibly responsible for more confusion than any other single statement in digital electronics, because it seems to run contrary to the basic principles of mathematics. Well, it does contradict principles of addition for real numbers, but not for Boolean numbers. Remember that in the world of Boolean algebra, there are only two possible values for any quantity and for any arithmetic operation: 1 or 0. There is no such thing as "2" within the scope of Boolean values. Since the sum "1 + 1" certainly isn't 0, it must be 1 by process of elimination.
It does not matter how many or few terms we add together, either. Consider the following sums:
http://openbookproject.net//electricCircuits/Digital/14007.png
Take a close look at the two-term sums in the first set of equations. Does that pattern look familiar to you? It should! It is the same pattern of 1's and 0's as seen in the truth table for an OR gate. In other words, Boolean addition corresponds to the logical function of an "OR" gate, as well as to parallel switch contacts:
http://openbookproject.net//electricCircuits/Digital/14009.png
http://openbookproject.net//electricCircuits/Digital/14010.png
http://openbookproject.net//electricCircuits/Digital/14011.png
http://openbookproject.net//electricCircuits/Digital/14012.png
There is no such thing as subtraction in the realm of Boolean mathematics. Subtraction implies the existence of negative numbers: 5 - 3 is the same thing as 5 + (-3), and in Boolean algebra negative quantities are forbidden. There is no such thing as division in Boolean mathematics, either, since division is really nothing more than compounded subtraction, in the same way that multiplication is compounded addition.
Multiplication is valid in Boolean algebra, and thankfully it is the same as in real-number algebra: anything multiplied by 0 is 0, and anything multiplied by 1 remains unchanged:
http://openbookproject.net//electricCircuits/Digital/14008.png
This set of equations should also look familiar to you: it is the same pattern found in the truth table for an AND gate. In other words, Boolean multiplication corresponds to the logical function of an "AND" gate, as well as to series switch contacts:
http://openbookproject.net//electricCircuits/Digital/14013.png
http://openbookproject.net//electricCircuits/Digital/14014.png
http://openbookproject.net//electricCircuits/Digital/14015.png
http://openbookproject.net//electricCircuits/Digital/14016.png
Like "normal" algebra, Boolean algebra uses alphabetical letters to denote variables. Unlike "normal" algebra, though, Boolean variables are always CAPITAL letters, never lower-case. Because they are allowed to possess only one of two possible values, either 1 or 0, each and every variable has a complement: the opposite of its value. For example, if variable "A" has a value of 0, then the complement of A has a value of 1. Boolean notation uses a bar above the variable character to denote complementation, like this:
http://openbookproject.net//electricCircuits/Digital/14005.png
In written form, the complement of "A" denoted as "A-not" or "A-bar". Sometimes a "prime" symbol is used to represent complementation. For example, A' would be the complement of A, much the same as using a prime symbol to denote differentiation in calculus rather than the fractional notation d/dt. Usually, though, the "bar" symbol finds more widespread use than the "prime" symbol, for reasons that will become more apparent later in this chapter.
Boolean complementation finds *****alency in the form of the NOT gate, or a normally-closed switch or relay contact:
http://openbookproject.net//electricCircuits/Digital/14017.png
http://openbookproject.net//electricCircuits/Digital/14018.png
The basic definition of Boolean quantities has led to the simple rules of addition and multiplication, and has excluded both subtraction and division as valid arithmetic operations. We have a symbology for denoting Boolean variables, and their complements. In the next section we will proceed to develop Boolean identities.
REVIEW:
Boolean addition is *****alent to the OR logic function, as well as parallel switch contacts.
Boolean multiplication is *****alent to the AND logic function, as well as series switch contacts.
Boolean complementation is *****alent to the NOT logic function, as well as normally-closed relay contacts.
Boolean algebraic identities
In mathematics, an identity is a statement true for all possible values of its variable or variables. The algebraic identity of x + 0 = x tells us that anything (x) added to zero equals the original "anything," no matter what value that "anything" (x) may be. Like ordinary algebra, Boolean algebra has its own unique identities based on the bivalent states of Boolean variables.
The first Boolean identity is that the sum of anything and zero is the same as the original "anything." This identity is no different from its real-number algebraic *****alent:
http://openbookproject.net//electricCircuits/Digital/14019.png
No matter what the value of A, the output will always be the same: when A=1, the output will also be 1; when A=0, the output will also be 0.
The next identity is most definitely different from any seen in normal algebra. Here we discover that the sum of anything and one is one:
http://openbookproject.net//electricCircuits/Digital/14020.png
No matter what the value of A, the sum of A and 1 will always be 1. In a sense, the "1" signal overrides the effect of A on the logic circuit, leaving the output fixed at a logic level of 1.
Next, we examine the effect of adding A and A together, which is the same as connecting both inputs of an OR gate to each other and activating them with the same signal:
http://openbookproject.net//electricCircuits/Digital/14021.png
In real-number algebra, the sum of two identical variables is twice the original variable's value (x + x = 2x), but remember that there is no concept of "2" in the world of Boolean math, only 1 and 0, so we cannot say that A + A = 2A. Thus, when we add a Boolean quantity to itself, the sum is equal to the original quantity: 0 + 0 = 0, and 1 + 1 = 1.
Introducing the uniquely Boolean concept of complementation into an additive identity, we find an interesting effect. Since there must be one "1" value between any variable and its complement, and since the sum of any Boolean quantity and 1 is 1, the sum of a variable and its complement must be 1:
http://openbookproject.net//electricCircuits/Digital/14022.png
Just as there are four Boolean additive identities (A+0, A+1, A+A, and A+A'), so there are also four multiplicative identities: Ax0, Ax1, AxA, and AxA'. Of these, the first two are no different from their *****alent expressions in regular algebra:
http://openbookproject.net//electricCircuits/Digital/14023.png
http://openbookproject.net//electricCircuits/Digital/14024.png
The third multiplicative identity expresses the result of a Boolean quantity multiplied by itself. In normal algebra, the product of a variable and itself is the square of that variable (3 x 3 = 32 = 9). However, the concept of "square" implies a quantity of 2, which has no meaning in Boolean algebra, so we cannot say that A x A = A2. Instead, we find that the product of a Boolean quantity and itself is the original quantity, since 0 x 0 = 0 and 1 x 1 = 1:
http://openbookproject.net//electricCircuits/Digital/14025.png
The fourth multiplicative identity has no *****alent in regular algebra because it uses the complement of a variable, a concept unique to Boolean mathematics. Since there must be one "0" value between any variable and its complement, and since the product of any Boolean quantity and 0 is 0, the product of a variable and its complement must be 0:
http://openbookproject.net//electricCircuits/Digital/14026.png
To summarize, then, we have four basic Boolean identities for addition and four for multiplication:
http://openbookproject.net//electricCircuits/Digital/14027.png
Another identity having to do with complementation is that of the double complement: a variable inverted twice. Complementing a variable twice (or any even number of times) results in the original Boolean value. This is analogous to negating (multiplying by -1) in real-number algebra: an even number of negations cancel to leave the original value:
http://openbookproject.net//electricCircuits/Digital/14033.png
Boolean algebraic properties
Another type of mathematical identity, called a "property" or a "law," describes how differing variables relate to each other in a system of numbers. One of these properties is known as the commutative property, and it applies equally to addition and multiplication. In essence, the commutative property tells us we can reverse the order of variables that are either added together or multiplied together without changing the truth of the expression:
http://openbookproject.net//electricCircuits/Digital/14028.png
http://openbookproject.net//electricCircuits/Digital/14029.png
Along with the commutative properties of addition and multiplication, we have the associative property, again applying equally well to addition and multiplication. This property tells us we can associate groups of added or multiplied variables together with parentheses without altering the truth of the equations.
http://openbookproject.net//electricCircuits/Digital/14030.png
http://openbookproject.net//electricCircuits/Digital/14031.png
Lastly, we have the distributive property, illustrating how to expand a Boolean expression formed by the product of a sum, and in reverse shows us how terms may be factored out of Boolean sums-of-products:
http://openbookproject.net//electricCircuits/Digital/14032.png
To summarize, here are the three basic properties: commutative, associative, and distributive.
http://openbookproject.net//electricCircuits/Digital/14034.png
Boolean rules for simplification
Boolean algebra finds its most practical use in the simplification of logic circuits. If we translate a logic circuit's function into symbolic (Boolean) form, and apply certain algebraic rules to the resulting equation to reduce the number of terms and/or arithmetic operations, the simplified equation may be translated back into circuit form for a logic circuit performing the same function with fewer components. If *****alent function may be achieved with fewer components, the result will be increased reliability and decreased cost of manufacture.
To this end, there are several rules of Boolean algebra presented in this section for use in reducing expressions to their simplest forms. The identities and properties already reviewed in this chapter are very useful in Boolean simplification, and for the most part bear similarity to many identities and properties of "normal" algebra. However, the rules shown in this section are all unique to Boolean mathematics.
http://openbookproject.net//electricCircuits/Digital/14035.png
This rule may be proven symbolically by factoring an "A" out of the two terms, then applying the rules of A + 1 = 1 and 1A = A to achieve the final result:
http://openbookproject.net//electricCircuits/Digital/14036.png
Please note how the rule A + 1 = 1 was used to reduce the (B + 1) term to 1. When a rule like "A + 1 = 1" is expressed using the letter "A", it doesn't mean it only applies to expressions containing "A". What the "A" stands for in a rule like A + 1 = 1 is any Boolean variable or collection of variables. This is perhaps the most difficult concept for new students to master in Boolean simplification: applying standardized identities, properties, and rules to expressions not in standard form.
For instance, the Boolean expression ABC + 1 also reduces to 1 by means of the "A + 1 = 1" identity. In this case, we recognize that the "A" term in the identity's standard form can represent the entire "ABC" term in the original expression.
The next rule looks similar to the first one shown in this section, but is actually quite different and requires a more clever proof:
http://openbookproject.net//electricCircuits/Digital/14037.png
http://openbookproject.net//electricCircuits/Digital/14038.png
Note how the last rule (A + AB = A) is used to "un-simplify" the first "A" term in the expression, changing the "A" into an "A + AB". While this may seem like a backward step, it certainly helped to reduce the expression to something simpler! Sometimes in mathematics we must take "backward" steps to achieve the most elegant solution. Knowing when to take such a step and when not to is part of the art-form of algebra, just as a victory in a game of chess almost always requires calculated sacrifices.
Another rule involves the simplification of a product-of-sums expression:
http://openbookproject.net//electricCircuits/Digital/14039.png
And, the corresponding proof:
http://openbookproject.net//electricCircuits/Digital/14040.png
To summarize, here are the three new rules of Boolean simplification expounded in this section:
http://openbookproject.net//electricCircuits/Digital/14041.png
Circuit simplification examples
Let's begin with a semiconductor gate circuit in need of simplification. The "A," "B," and "C" input signals are assumed to be provided from switches, sensors, or perhaps other gate circuits. Where these signals originate is of no concern in the task of gate reduction.
http://openbookproject.net//electricCircuits/Digital/04287.png
Our first step in simplification must be to write a Boolean expression for this circuit. This task is easily performed step by step if we start by writing sub-expressions at the output of each gate, corresponding to the respective input signals for each gate. Remember that OR gates are *****alent to Boolean addition, while AND gates are *****alent to Boolean multiplication. For example, I'll write sub-expressions at the outputs of the first three gates:
http://openbookproject.net//electricCircuits/Digital/04288.png
. . . then another sub-expression for the next gate:
http://openbookproject.net//electricCircuits/Digital/04289.png
Finally, the output ("Q") is seen to be equal to the expression AB + BC(B + C):
http://openbookproject.net//electricCircuits/Digital/04290.png
Now that we have a Boolean expression to work with, we need to apply the rules of Boolean algebra to reduce the expression to its simplest form (simplest defined as requiring the fewest gates to implement):
http://openbookproject.net//electricCircuits/Digital/14042.png
The final expression, B(A + C), is much simpler than the original, yet performs the same function. If you would like to verify this, you may generate a truth table for both expressions and determine Q's status (the circuits' output) for all eight logic-state combinations of A, B, and C, for both circuits. The two truth tables should be identical.
Now, we must generate a schematic diagram from this Boolean expression. To do this, evaluate the expression, following proper mathematical order of operations (multiplication before addition, operations inside parentheses before anything else), and draw gates for each step. Remember again that OR gates are *****alent to Boolean addition, while AND gates are *****alent to Boolean multiplication. In this case, we would begin with the sub-expression "A + C", which is an OR gate:
http://openbookproject.net//electricCircuits/Digital/04291.png
The next step in evaluating the expression "B(A + C)" is to multiply (AND gate) the signal B by the output of the previous gate (A + C):
http://openbookproject.net//electricCircuits/Digital/04292.png
Obviously, this circuit is much simpler than the original, having only two logic gates instead of five. Such component reduction results in higher operating speed (less delay time from input signal transition to output signal transition), less power consumption, less cost, and greater reliability.
Electromechanical relay circuits, typically being slower, consuming more electrical power to operate, costing more, and having a shorter average life than their semiconductor counterparts, benefit dramatically from Boolean simplification. Let's consider an example circuit:
http://openbookproject.net//electricCircuits/Digital/04293.png
As before, our first step in reducing this circuit to its simplest form must be to develop a Boolean expression from the schematic. The easiest way I've found to do this is to follow the same steps I'd normally follow to reduce a series-parallel resistor network to a single, total resistance. For example, examine the following resistor network with its resistors arranged in the same connection pattern as the relay contacts in the former circuit, and corresponding total resistance formula:
http://openbookproject.net//electricCircuits/Digital/04294.png
Remember that parallel contacts are *****alent to Boolean addition, while series contacts are *****alent to Boolean multiplication. Write a Boolean expression for this relay contact circuit, following the same order of precedence that you would follow in reducing a series-parallel resistor network to a total resistance. It may be helpful to write a Boolean sub-expression to the left of each ladder "rung," to help organize your expression-writing:
http://openbookproject.net//electricCircuits/Digital/04295.png
Now that we have a Boolean expression to work with, we need to apply the rules of Boolean algebra to reduce the expression to its simplest form (simplest defined as requiring the fewest relay contacts to implement):
http://openbookproject.net//electricCircuits/Digital/14043.png
The more mathematically inclined should be able to see that the two steps employing the rule "A + AB = A" may be combined into a single step, the rule being expandable to: "A + AB + AC + AD + . . . = A"
http://openbookproject.net//electricCircuits/Digital/14044.png
As you can see, the reduced circuit is much simpler than the original, yet performs the same logical function:
http://openbookproject.net//electricCircuits/Digital/04296.png
REVIEW:
To convert a gate circuit to a Boolean expression, label each gate output with a Boolean sub-expression corresponding to the gates' input signals, until a final expression is reached at the last gate.
To convert a Boolean expression to a gate circuit, evaluate the expression using standard order of operations: multiplication before addition, and operations within parentheses before anything else.
To convert a ladder logic circuit to a Boolean expression, label each rung with a Boolean sub-expression corresponding to the contacts' input signals, until a final expression is reached at the last coil or light. To determine proper order of evaluation, treat the contacts as though they were resistors, and as if you were determining total resistance of the series-parallel network formed by them. In other words, look for contacts that are either directly in series or directly in parallel with each other first, then "collapse" them into *****alent Boolean sub-expressions before proceeding to other contacts.
To convert a Boolean expression to a ladder logic circuit, evaluate the expression using standard order of operations: multiplication before addition, and operations within parentheses before anything else.
The Exclusive-OR function
One element conspicuously missing from the set of Boolean operations is that of Exclusive-OR. Whereas the OR function is *****alent to Boolean addition, the AND function to Boolean multiplication, and the NOT function (inverter) to Boolean complementation, there is no direct Boolean *****alent for Exclusive-OR. This hasn't stopped people from developing a symbol to represent it, though:
http://openbookproject.net//electricCircuits/Digital/04297.png
This symbol is seldom used in Boolean expressions because the identities, laws, and rules of simplification involving addition, multiplication, and complementation do not apply to it. However, there is a way to represent the Exclusive-OR function in terms of OR and AND, as has been shown in previous chapters: AB' + A'B
http://openbookproject.net//electricCircuits/Digital/04298.png
As a Boolean *****alency, this rule may be helpful in simplifying some Boolean expressions. Any expression following the AB' + A'B form (two AND gates and an OR gate) may be replaced by a single Exclusive-OR gate.
DeMorgan's Theorems
A mathematician named DeMorgan developed a pair of important rules regarding group complementation in Boolean algebra. By group complementation, I'm referring to the complement of a group of terms, represented by a long bar over more than one variable.
You should recall from the chapter on logic gates that inverting all inputs to a gate reverses that gate's essential function from AND to OR, or vice versa, and also inverts the output. So, an OR gate with all inputs inverted (a Negative-OR gate) behaves the same as a NAND gate, and an AND gate with all inputs inverted (a Negative-AND gate) behaves the same as a NOR gate. DeMorgan's theorems state the same *****alence in "backward" form: that inverting the output of any gate results in the same function as the opposite type of gate (AND vs. OR) with inverted inputs:
http://openbookproject.net//electricCircuits/Digital/04299.png
A long bar extending over the term AB acts as a grouping symbol, and as such is entirely different from the product of A and B independently inverted. In other words, (AB)' is not equal to A'B'. Because the "prime" symbol (') cannot be stretched over two variables like a bar can, we are forced to use parentheses to make it apply to the whole term AB in the previous sentence. A bar, however, acts as its own grouping symbol when stretched over more than one variable. This has profound impact on how Boolean expressions are evaluated and reduced, as we shall see.
DeMorgan's theorem may be thought of in terms of breaking a long bar symbol. When a long bar is broken, the operation directly underneath the break changes from addition to multiplication, or vice versa, and the broken bar pieces remain over the individual variables. To illustrate:
http://openbookproject.net//electricCircuits/Digital/14045.png
When multiple "layers" of bars exist in an expression, you may only break one bar at a time, and it is generally easier to begin simplification by breaking the longest (uppermost) bar first. To illustrate, let's take the expression (A + (BC)')' and reduce it using DeMorgan's Theorems:
http://openbookproject.net//electricCircuits/Digital/04300.png
Following the advice of breaking the longest (uppermost) bar first, I'll begin by breaking the bar covering the entire expression as a first step:
http://openbookproject.net//electricCircuits/Digital/14046.png
As a result, the original circuit is reduced to a three-input AND gate with the A input inverted:
http://openbookproject.net//electricCircuits/Digital/04301.png
You should never break more than one bar in a single step, as illustrated here:
http://openbookproject.net//electricCircuits/Digital/14050.png
As tempting as it may be to conserve steps and break more than one bar at a time, it often leads to an incorrect result, so don't do it!
It is possible to properly reduce this expression by breaking the short bar first, rather than the long bar first:
http://openbookproject.net//electricCircuits/Digital/14047.png
The end result is the same, but more steps are required compared to using the first method, where the longest bar was broken first. Note how in the third step we broke the long bar in two places. This is a legitimate mathematical operation, and not the same as breaking two bars in one step! The prohibition against breaking more than one bar in one step is not a prohibition against breaking a bar in more than one place. Breaking in more than one place in a single step is okay; breaking more than one bar in a single step is not.
You might be wondering why parentheses were placed around the sub-expression B' + C', considering the fact that I just removed them in the next step. I did this to emphasize an important but easily neglected aspect of DeMorgan's theorem. Since a long bar functions as a grouping symbol, the variables formerly grouped by a broken bar must remain grouped lest proper precedence (order of operation) be lost. In this example, it really wouldn't matter if I forgot to put parentheses in after breaking the short bar, but in other cases it might. Consider this example, starting with a different expression:
http://openbookproject.net//electricCircuits/Digital/14048.png
http://openbookproject.net//electricCircuits/Digital/14049.png
As you can see, maintaining the grouping implied by the complementation bars for this expression is crucial to obtaining the correct answer.
Let's apply the principles of DeMorgan's theorems to the simplification of a gate circuit:
http://openbookproject.net//electricCircuits/Digital/04302.png
As always, our first step in simplifying this circuit must be to generate an *****alent Boolean expression. We can do this by placing a sub-expression label at the output of each gate, as the inputs become known. Here's the first step in this process:
http://openbookproject.net//electricCircuits/Digital/04303.png
Next, we can label the outputs of the first NOR gate and the NAND gate. When dealing with inverted-output gates, I find it easier to write an expression for the gate's output without the final inversion, with an arrow pointing to just before the inversion bubble. Then, at the wire leading out of the gate (after the bubble), I write the full, complemented expression. This helps ensure I don't forget a complementing bar in the sub-expression, by forcing myself to split the expression-writing task into two steps:
http://openbookproject.net//electricCircuits/Digital/04304.png
Finally, we write an expression (or pair of expressions) for the last NOR gate:
http://openbookproject.net//electricCircuits/Digital/04305.png
Now, we reduce this expression using the identities, properties, rules, and theorems (DeMorgan's) of Boolean algebra:
http://openbookproject.net//electricCircuits/Digital/14051.png
The *****alent gate circuit for this much-simplified expression is as follows:
http://openbookproject.net//electricCircuits/Digital/04306.png
REVIEW
DeMorgan's Theorems describe the *****alence between gates with inverted inputs and gates with inverted outputs. Simply put, a NAND gate is *****alent to a Negative-OR gate, and a NOR gate is *****alent to a Negative-AND gate.
When "breaking" a complementation bar in a Boolean expression, the operation directly underneath the break (addition or multiplication) reverses, and the broken bar pieces remain over the respective terms.
It is often easier to approach a problem by breaking the longest (uppermost) bar before breaking any bars under it. You must never attempt to break two bars in one step!
Complementation bars function as grouping symbols. Therefore, when a bar is broken, the terms underneath it must remain grouped. Parentheses may be placed around these grouped terms as a help to avoid changing precedence.
Converting truth tables into Boolean expressions
In designing digital circuits, the designer often begins with a truth table describing what the circuit should do. The design task is largely to determine what type of circuit will perform the function described in the truth table. While some people seem to have a natural ability to look at a truth table and immediately envision the necessary logic gate or relay logic circuitry for the task, there are procedural techniques available for the rest of us. Here, Boolean algebra proves its utility in a most dramatic way.
To illustrate this procedural method, we should begin with a realistic design problem. Suppose we were given the task of designing a flame detection circuit for a toxic waste incinerator. The intense heat of the fire is intended to neutralize the toxicity of the waste introduced into the incinerator. Such combustion-based techniques are commonly used to neutralize medical waste, which may be infected with deadly viruses or bacteria:
http://openbookproject.net//electricCircuits/Digital/04360.png
So long as a flame is maintained in the incinerator, it is safe to inject waste into it to be neutralized. If the flame were to be extinguished, however, it would be unsafe to continue to inject waste into the combustion chamber, as it would exit the exhaust un-neutralized, and pose a health threat to anyone in close proximity to the exhaust. What we need in this system is a sure way of detecting the presence of a flame, and permitting waste to be injected only if a flame is "proven" by the flame detection system.
Several different flame-detection technologies exist: optical (detection of light), thermal (detection of high temperature), and electrical conduction (detection of ionized particles in the flame path), each one with its unique advantages and disadvantages. Suppose that due to the high degree of hazard involved with potentially passing un-neutralized waste out the exhaust of this incinerator, it is decided that the flame detection system be made redundant (multiple sensors), so that failure of a single sensor does not lead to an emission of toxins out the exhaust. Each sensor comes equipped with a normally-open contact (open if no flame, closed if flame detected) which we will use to activate the inputs of a logic system:
http://openbookproject.net//electricCircuits/Digital/04361.png
Our task, now, is to design the circuitry of the logic system to open the waste valve if and only if there is good flame proven by the sensors. First, though, we must decide what the logical behavior of this control system should be. Do we want the valve to be opened if only one out of the three sensors detects flame? Probably not, because this would defeat the purpose of having multiple sensors. If any one of the sensors were to fail in such a way as to falsely indicate the presence of flame when there was none, a logic system based on the principle of "any one out of three sensors showing flame" would give the same output that a single-sensor system would with the same failure. A far better solution would be to design the system so that the valve is commanded to open if and only if all three sensors detect a good flame. This way, any single, failed sensor falsely showing flame could not keep the valve in the open position; rather, it would require all three sensors to be failed in the same manner -- a highly improbable scenario -- for this dangerous condition to occur.
Thus, our truth table would look like this:
http://openbookproject.net//electricCircuits/Digital/14061.png
It does not require much insight to realize that this functionality could be generated with a three-input AND gate: the output of the circuit will be "high" if and only if input A AND input B AND input C are all "high:"
http://openbookproject.net//electricCircuits/Digital/04362.png
If using relay circuitry, we could create this AND function by wiring three relay contacts in series, or simply by wiring the three sensor contacts in series, so that the only way electrical power could be sent to open the waste valve is if all three sensors indicate flame:
http://openbookproject.net//electricCircuits/Digital/04363.png
While this design strategy maximizes safety, it makes the system very susceptible to sensor failures of the opposite kind. Suppose that one of the three sensors were to fail in such a way that it indicated no flame when there really was a good flame in the incinerator's combustion chamber. That single failure would shut off the waste valve unnecessarily, resulting in lost production time and wasted fuel (feeding a fire that wasn't being used to incinerate waste).
It would be nice to have a logic system that allowed for this kind of failure without shutting the system down unnecessarily, yet still provide sensor redundancy so as to maintain safety in the event that any single sensor failed "high" (showing flame at all times, whether or not there was one to detect). A strategy that would meet both needs would be a "two out of three" sensor logic, whereby the waste valve is opened if at least two out of the three sensors show good flame. The truth table for such a system would look like this:
http://openbookproject.net//electricCircuits/Digital/14062.png
Here, it is not necessarily obvious what kind of logic circuit would satisfy the truth table. However, a simple method for designing such a circuit is found in a standard form of Boolean expression called the Sum-Of-Products, or SOP, form. As you might suspect, a Sum-Of-Products Boolean expression is literally a set of Boolean terms added (summed) together, each term being a multiplicative (product) combination of Boolean variables. An example of an SOP expression would be something like this: ABC + BC + DF, the sum of products "ABC," "BC," and "DF."
Sum-Of-Products expressions are easy to generate from truth tables. All we have to do is examine the truth table for any rows where the output is "high" (1), and write a Boolean product term that would equal a value of 1 given those input conditions. For instance, in the fourth row down in the truth table for our two-out-of-three logic system, where A=0, B=1, and C=1, the product term would be A'BC, since that term would have a value of 1 if and only if A=0, B=1, and C=1:
http://openbookproject.net//electricCircuits/Digital/14063.png
Three other rows of the truth table have an output value of 1, so those rows also need Boolean product expressions to represent them:
http://openbookproject.net//electricCircuits/Digital/14064.png
Finally, we join these four Boolean product expressions together by addition, to create a single Boolean expression describing the truth table as a whole:
http://openbookproject.net//electricCircuits/Digital/14065.png
Now that we have a Boolean Sum-Of-Products expression for the truth table's function, we can easily design a logic gate or relay logic circuit based on that expression:
http://openbookproject.net//electricCircuits/Digital/04364.png
http://openbookproject.net//electricCircuits/Digital/04365.png
Unfortunately, both of these circuits are quite complex, and could benefit from simplification. Using Boolean algebra techniques, the expression may be significantly simplified:
http://openbookproject.net//electricCircuits/Digital/14066.png
As a result of the simplification, we can now build much simpler logic circuits performing the same function, in either gate or relay form:
http://openbookproject.net//electricCircuits/Digital/04366.png
http://openbookproject.net//electricCircuits/Digital/04367.png
Either one of these circuits will adequately perform the task of operating the incinerator waste valve based on a flame verification from two out of the three flame sensors. At minimum, this is what we need to have a safe incinerator system. We can, however, extend the functionality of the system by adding to it logic circuitry designed to detect if any one of the sensors does not agree with the other two.
If all three sensors are operating properly, they should detect flame with equal accuracy. Thus, they should either all register "low" (000: no flame) or all register "high" (111: good flame). Any other output combination (001, 010, 011, 100, 101, or 110) constitutes a disagreement between sensors, and may therefore serve as an indicator of a potential sensor failure. If we added circuitry to detect any one of the six "sensor disagreement" conditions, we could use the output of that circuitry to activate an alarm. Whoever is monitoring the incinerator would then exercise judgment in either continuing to operate with a possible failed sensor (inputs: 011, 101, or 110), or shut the incinerator down to be absolutely safe. Also, if the incinerator is shut down (no flame), and one or more of the sensors still indicates flame (001, 010, 011, 100, 101, or 110) while the other(s) indicate(s) no flame, it will be known that a definite sensor problem exists.
The first step in designing this "sensor disagreement" detection circuit is to write a truth table describing its behavior. Since we already have a truth table describing the output of the "good flame" logic circuit, we can simply add another output column to the table to represent the second circuit, and make a table representing the entire logic system:
http://openbookproject.net//electricCircuits/Digital/14067.png
While it is possible to generate a Sum-Of-Products expression for this new truth table column, it would require six terms, of three variables each! Such a Boolean expression would require many steps to simplify, with a large potential for making algebraic errors:
http://openbookproject.net//electricCircuits/Digital/14068.png
An alternative to generating a Sum-Of-Products expression to account for all the "high" (1) output conditions in the truth table is to generate a Product-Of-Sums, or POS, expression, to account for all the "low" (0) output conditions instead. Being that there are much fewer instances of a "low" output in the last truth table column, the resulting Product-Of-Sums expression should contain fewer terms. As its name suggests, a Product-Of-Sums expression is a set of added terms (sums), which are multiplied (product) together. An example of a POS expression would be (A + B)(C + D), the product of the sums "A + B" and "C + D".
To begin, we identify which rows in the last truth table column have "low" (0) outputs, and write a Boolean sum term that would equal 0 for that row's input conditions. For instance, in the first row of the truth table, where A=0, B=0, and C=0, the sum term would be (A + B + C), since that term would have a value of 0 if and only if A=0, B=0, and C=0:
http://openbookproject.net//electricCircuits/Digital/14069.png
Only one other row in the last truth table column has a "low" (0) output, so all we need is one more sum term to complete our Product-Of-Sums expression. This last sum term represents a 0 output for an input condition of A=1, B=1 and C=1. Therefore, the term must be written as (A' + B'+ C'), because only the sum of the complemented input variables would equal 0 for that condition only:
http://openbookproject.net//electricCircuits/Digital/14070.png
The completed Product-Of-Sums expression, of course, is the multiplicative combination of these two sum terms:
http://openbookproject.net//electricCircuits/Digital/14071.png
Whereas a Sum-Of-Products expression could be implemented in the form of a set of AND gates with their outputs connecting to a single OR gate, a Product-Of-Sums expression can be implemented as a set of OR gates feeding into a single AND gate:
http://openbookproject.net//electricCircuits/Digital/04368.png
Correspondingly, whereas a Sum-Of-Products expression could be implemented as a parallel collection of series-connected relay contacts, a Product-Of-Sums expression can be implemented as a series collection of parallel-connected relay contacts:
http://openbookproject.net//electricCircuits/Digital/04369.png
The previous two circuits represent different versions of the "sensor disagreement" logic circuit only, not the "good flame" detection circuit(s). The entire logic system would be the combination of both "good flame" and "sensor disagreement" circuits, shown on the same diagram.
Implemented in a Programmable Logic Controller (PLC), the entire logic system might resemble something like this:
http://openbookproject.net//electricCircuits/Digital/04370.png
As you can see, both the Sum-Of-Products and Products-Of-Sums standard Boolean forms are powerful tools when applied to truth tables. They allow us to derive a Boolean expression -- and ultimately, an actual logic circuit -- from nothing but a truth table, which is a written specification for what we want a logic circuit to do. To be able to go from a written specification to an actual circuit using simple, deterministic procedures means that it is possible to automate the design process for a digital circuit. In other words, a computer could be programmed to design a custom logic circuit from a truth table specification! The steps to take from a truth table to the final circuit are so unambiguous and direct that it requires little, if any, creativity or other original thought to execute them.
REVIEW:
Sum-Of-Products, or SOP, Boolean expressions may be generated from truth tables quite easily, by determining which rows of the table have an output of 1, writing one product term for each row, and finally summing all the product terms. This creates a Boolean expression representing the truth table as a whole.
Sum-Of-Products expressions lend themselves well to implementation as a set of AND gates (products) feeding into a single OR gate (sum).
Product-Of-Sums, or POS, Boolean expressions may also be generated from truth tables quite easily, by determining which rows of the table have an output of 0, writing one sum term for each row, and finally multiplying all the sum terms. This creates a Boolean expression representing the truth table as a whole.
Product-Of-Sums expressions lend themselves well to implementation as a set of OR gates (sums) feeding into a single AND gate (product).
ens 1990
2010-03-31, 19:29
Leçons dans les circuits électriques - Volume IV
Chapitre 7
Algèbre de Boole
* Introduction
* Arithmétique booléenne
* Booléenne identités algébriques
* Booléenne propriétés algébriques
* Des règles booléennes de simplification
* Des exemples de simplification du circuit
* La fonction OU exclusif
* DeMorgan théorèmes
* Conversion en tables de vérité des expressions booléennes
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Règles de l'addition pour les quantités booléenne
"Gee Toto, je ne pense pas que nous sommes plus au Kansas!
Dorothy dans Le Magicien d'Oz
Introduction
règles mathématiques sont basés sur les limites que nous accordons à la définition des quantités notamment numériques traitées. Quand on dit que 1 + 1 = 2 ou 3 + 4 = 7, nous sommes ce qui implique l'utilisation de quantités entier: les mêmes types de numéros nous avons tous appris à compter dans l'enseignement primaire. Ce que la plupart des gens supposent à des règles évidentes de l'arithmétique - valide en tout temps et à toutes fins - en fait dépendre de ce que nous définissons un certain nombre d'être.
Par exemple, lors du calcul des quantités de circuits AC, nous constatons que la «vraie quantités de numéro" qui nous a si bien servi dans l'analyse de circuits à courant continu sont insuffisantes pour la tâche de représenter les quantités AC. Nous savons que les tensions ajouter lorsqu'il est connecté en série, mais nous savons aussi qu'il est possible de connecter une source AC 3-V en série avec une source AC 4-V et finissent avec une tension totale de 5 volts (3 + 4 = 5) ! Est-ce que cela signifie des règles inviolables et de soi de l'arithmétique ont été violés? Non, cela signifie juste que les règles de «vrais» chiffres ne s'appliquent pas aux types de quantités rencontrées dans les circuits AC, où chaque variable est à la fois une ampleur et d'une phase. Par conséquent, nous devons utiliser un autre type de valeur numérique, ou un objet, pour les circuits AC (nombres complexes, plutôt que des nombres réels), et avec ce système différent de numéros est un ensemble de règles différentes pour nous dire comment ils se rapportent à un autre .
Une expression telle que "3 + 4 = 5» est un non-sens dans le champ et la définition des nombres réels, mais il s'intègre bien dans le champ et la définition des nombres complexes (pensez à un triangle rectangle dont les côtés opposés et adjacents de 3 et 4, avec une hypoténuse de 5). Parce que les nombres complexes sont en deux dimensions, ils sont capables de "ajouter" un avec l'autre trigonométriquement que seule dimension "réelle" nombres ne peuvent pas.
La logique est un peu comme les mathématiques, à cet égard: la soi-disant «lois» de la logique dépendent de la façon dont nous définissons ce qu'est une proposition est. Le philosophe grec Aristote a fondé un système de logique basée sur seulement deux types de propositions: vraies et fausses. Son bivalent (bi-mode) définition de la vérité conduit à la quatre lois fondamentales de la logique: le principe d'identité (A est A), la loi de non-contradiction (A n'est pas non-A); le droit de la Exclusion du Milieu (A ou non A), et le droit de Rational inférence. Ces soi-disant lois de fonction dans le cadre de la logique où une proposition se limite à l'une des deux valeurs possibles, mais peuvent ne pas s'appliquer dans les cas où les propositions peuvent contenir des valeurs autres que les «vrais» ou «faux». En fait, beaucoup de travail a été fait et continue d'être fait sur "plusieurs valeurs», ou la logique floue, où les propositions peuvent être vraies ou fausses dans une mesure limitée. Dans un tel système de la logique, «Lois» telles que le droit de la Exclusion du Milieu n'ont tout simplement pas applicable, parce qu'elles sont fondées sur l'hypothèse de bivalence. De même, de nombreux locaux qui violerait la loi de non-contradiction dans la logique aristotélicienne ont une validité dans le "flou" logique. Encore une fois, les limites de la définition des valeurs propositionnel déterminer les lois décrivant leurs fonctions et relations.
Le mathématicien anglais George Boole (1815-1864) a cherché à donner une forme symbolique au système d'Aristote de la logique. Boole a écrit un traité sur le sujet en 1854, intitulé Une enquête des lois de la pensée, sur lesquels sont fondées les théories mathématiques de la logique et probabilités, qui codifie plusieurs règles de la relation entre les quantités mathématiques limitée à l'une des deux valeurs possibles: vrai ou faux, 1 ou 0. Son système mathématique est devenu connu comme l'algèbre de Boole.
Toutes les opérations arithmétiques effectuées avec des quantités booléennes ont, mais un des deux résultats possibles: 0 ou 1. Il n'y a pas une telle chose comme "2" ou "-1" ou "1 / 2" dans le monde booléenne. C'est un monde dans lequel toutes les autres possibilités sont invalides par Fiat. Comme on peut le deviner, ce n'est pas le genre de mathématiques que vous souhaitez utiliser lors de l'équilibrage d'un chéquier ou de calcul de courant à travers une résistance. Toutefois, Claude Shannon de la renommée du MIT reconnu l'algèbre de Boole pourrait être appliquée à des circuits à l'intérieur et à pied, où tous les signaux sont caractérisés comme étant «élevé» (1) ou «faible» (0). Sa thèse de 1938, intitulé Une analyse symbolique des circuits de commutation de relais et, mis travaux théoriques de Boole à utiliser d'une manière Boole n'aurais jamais pu imaginer, nous donnant ainsi un puissant outil mathématique pour la conception et l'analyse des circuits numériques.
Dans ce chapitre, vous trouverez beaucoup de similitudes entre l'algèbre de Boole et «normal» l'algèbre, la nature de l'algèbre impliquant que l'on appelle des nombres réels. Juste garder à l'esprit que le système de numéros de définir l'algèbre de Boole est très limitée en termes de portée, et qu'il ne peut être l'une des deux valeurs possibles pour une variable booléenne: 1 ou 0. Par conséquent, les «lois» de l'algèbre de Boole diffèrent souvent de les "Lois" de l'algèbre réelle nombre, rendant possible des énoncés tels que 1 + 1 = 1, ce qui serait normalement considéré comme absurde. Une fois que vous comprenez le principe de toutes les quantités dans l'algèbre de Boole étant limité à deux possibilités de 1 et 0, et le principe philosophique général des lois en fonction de définitions quantitatives, les «non-sens» de l'algèbre booléenne disparaît.
Il doit être clairement entendu que le nombre de booléens ne sont pas les mêmes que les nombres binaires. Considérant que les numéros booléens représentent un système complètement différent des mathématiques à partir des nombres réels, binaire n'est rien de plus une notation alternative pour les nombres réels. Les deux sont souvent confondues en raison à la fois la notation mathématiques booléens et binaires, utilisez les deux mêmes chiffres: 1 et 0. La différence est que les quantités booléennes sont limités à un seul bit (0 ou 1), tandis que les nombres binaires peuvent être composés de plusieurs bits en ajoutant en place sous forme pondérée d'une valeur de n'importe quelle taille finie. Le nombre binaire 100112 («dix-neuf") n'a pas plus de place dans le monde booléenne que le nombre décimal 210 ("deux") ou le nombre octal 328 («vingt-six").
arithmétique booléenne
Commençons notre exploration de l'algèbre de Boole en ajoutant des numéros ainsi que:
Les trois premières sommes parfaitement logique pour quiconque connaît plus élémentaires. La dernière somme, cependant, est très probablement responsable de plus de confusion que de toute autre déclaration unique dans l'électronique numérique, car il semble aller à l'encontre des principes de base des mathématiques. Eh bien, il ne contredit les principes de l'addition des nombres réels, mais pas pour les numéros de booléens. N'oubliez pas que dans le monde de l'algèbre de Boole, il n'y a que deux valeurs possibles pour toutes les quantités et pour toute opération arithmétique: 1 ou 0. Il n'y a pas une telle chose comme "2" dans le cadre de valeurs booléennes. Puisque la somme "1 + 1» n'est certainement pas 0, il faut 1 par processus d'élimination.
Il n'a pas d'importance combien de quelques termes ou on additionne, que ce soit. Considérons les sommes suivantes:
Portez une attention particulière à la somme de deux mandats dans la première série d'équations. Est-ce ce modèle aspect familier pour vous? Il convient! C'est le même schéma de 1 et 0 comme on le voit dans la table de vérité d'une porte OU. En d'autres termes, plus booléenne correspond à la fonction logique d'un «OU» porte, ainsi que de contacts de l'interrupteur en parallèle:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Il n'y a pas une telle chose comme la soustraction dans le domaine des mathématiques booléenne. Soustraction implique l'existence de nombres négatifs: 5 - 3 est la même chose que 5 + (-3), et l'algèbre de Boole des quantités négatives sont interdites. Il n'ya rien de tel que la division en mathématiques booléenne, que ce soit, puisque la division est vraiment rien de plus aggravé la soustraction, de la même manière que la multiplication est composé d'addition.
La multiplication est valable dans l'algèbre de Boole, et, heureusement, il est le même que dans l'algèbre nombre réel: tout multiplié par 0 est égal à 0, et tout ce qui, multiplié par 1 reste inchangée:
Cet ensemble d'équations doivent aussi aller vous connaissez: c'est le même schéma dans la table de vérité d'une porte ET. En d'autres termes, la multiplication booléenne correspond à la fonction logique d'un "AND", ainsi que de contacts de commutation série:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Comme "normal" algèbre, l'algèbre de Boole utilise des lettres alphabétiques pour désigner des variables. Contrairement à "normal" algèbre, cependant, les variables booléennes sont toujours des majuscules, minuscules jamais. Parce qu'elles sont autorisées à posséder une seule des deux valeurs possibles, 0 ou 1, chaque variable a un complément: le contraire de sa valeur. Par exemple, si la variable «A» a une valeur de 0, alors le complément de A a une valeur de 1. Boolean notation utilise une barre au-dessus du caractère variable pour désigner complémentation, comme ceci:
Sous forme écrite, le complément de "A" notée "A-pas" ou "Un bar-". Parfois, une "prime" symbole est utilisé pour représenter la complémentation. Par exemple, A 'sera le complément de A, sensiblement le même que l'utilisation d'un symbole pour désigner le Premier différenciation dans le calcul plutôt que la notation des fractions d / dt. Habituellement, cependant, le "bar" symbole constate une utilisation plus répandue que la "prime" symbole, pour des raisons qui apparaîtront plus clairement plus loin dans ce chapitre.
complémentation booléenne trouve ***** alency sous la forme de la porte NON, ou un interrupteur normalement fermé ou un contact de relais:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
La définition de base des quantités booléenne a conduit à des règles simples d'addition et de multiplication, et a exclu la fois la soustraction et la division des opérations arithmétiques comme valide. Nous avons une symbologie pour indiquer les variables booléennes, et leurs compléments. Dans la section suivante, nous allons procéder à créer des identités booléennes.
* EXAMEN:
* Outre booléenne est ***** ALENT à la fonction logique OU, ainsi que les contacts d'interrupteurs en parallèle.
* Multiplication booléenne est ***** ALENT à la fonction logique ET, ainsi que les contacts d'interrupteurs en série.
* Complémentation booléenne est ***** ALENT à la fonction logique NON, ainsi que des contacts de relais normalement fermé.
identités algébriques booléennes
En mathématiques, une identité est un énoncé vrai pour toutes les valeurs possibles de ses variables ou variables. L'identité algébrique de x + x = 0 nous dit que tout (x) est égal à zéro a ajouté l'original "rien", quelle que soit la valeur que "quelque chose" (x) peut être. Comme l'algèbre ordinaire, l'algèbre de Boole a sa propre identité unique basé sur les États bivalent de variables booléennes.
La première identité booléenne est que la somme de rien et zéro est la même que l'original "rien." Cette identité n'est pas différent de ses algébrique réelle numéro ***** ALENT:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Quelle que soit la valeur de A, la sortie sera toujours le même: quand A = 1, la sortie sera également 1; lorsque A = 0, la sortie sera aussi 0.
L'identité suivante est très certainement différent de tout voir en algèbre normale. Ici, nous découvrons que la somme de tout ce qui est l'un et l'autre:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Quelle que soit la valeur de A, la somme de A et 1 sera toujours 1. Dans un sens, le signal «1» l'emporte sur l'effet de A sur le circuit logique, laissant la sortie fixée à un niveau logique 1.
Ensuite, nous examinons l'effet de l'ajout de A et A ensemble, qui est la même que la connexion de deux entrées d'une porte OU à l'autre et de les activer avec le même signal:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
En algèbre réel le nombre, la somme de deux variables identiques est deux fois la valeur de la variable d'origine (x + x = 2x), mais rappelez-vous qu'il n'y a pas de concept de "2" dans le monde des mathématiques booléenne, que 1 et 0, de sorte nous ne pouvons pas dire que A + A = 2A. Ainsi, lorsque nous ajoutons une quantité booléens pour lui-même, la somme est égale à la quantité initiale: 0 + 0 = 0, et 1 + 1 = 1.
L'introduction du concept unique booléenne de complémentation dans un additif d'identité, nous trouvons un effet intéressant. Depuis il doit y avoir un "1" de valeur entre une variable et son complément, et puisque la somme d'une quantité booléenne et 1 est 1, la somme d'une variable et son complément doit être de 1:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Tout comme il ya quatre booléenne identités additif (A +0, A +1, A + et A + A '), donc il ya aussi quatre identités multiplicatif: Ax0, Ax1, AXA et AXA. Parmi ceux-ci, les deux premiers ne sont pas différents de leurs expressions ***** ALENT en algèbre ordinaire:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
L'identité multiplicative troisième exprime le résultat d'une quantité booléenne multiplié par lui-même. En algèbre normale, le produit d'une variable et lui-même est le carré de cette variable (3 x 3 = 32 = 9). Cependant, le concept de «carré» implique une quantité de 2, ce qui n'a pas de sens dans l'algèbre de Boole, nous ne pouvons pas dire que A x A = A2. Au lieu de cela, nous trouvons que le produit d'une quantité booléens et lui-même est la quantité initiale, puisque 0 x 0 = 0 et 1 x 1 = 1:
L'identité quatrième multiplicatif n'a pas ALENT ***** à l'algèbre ordinaire, car elle utilise le complément d'une variable, un concept unique aux mathématiques booléenne. Depuis il doit y avoir un "0" de valeur entre une variable et son complément, et puisque le produit d'une quantité booléenne et 0 est 0, le produit d'une variable et son complément doit être 0:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Pour résumer, donc, nous avons quatre identités de base Boolean pour l'ajout et quatre pour la multiplication:
Une autre identité d'avoir à faire avec la complémentation est celui de la double complément: une variable inversé deux fois. En complément des résultats d'une variable à deux reprises (ou tout nombre pair de fois) dans la valeur d'origine booléenne. Ceci est analogue à la négation (en multipliant par -1) dans l'algèbre nombre réel: un nombre pair de négations Annuler pour quitter la valeur d'origine:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
propriétés algébriques booléennes
Un autre type d'identité mathématique, appelé un «bien» ou une «loi», décrit comment les variables divergentes se rapportent les uns aux autres dans un système de numéros. L'une de ces propriétés est connue comme étant la propriété commutative, et elle s'applique également à l'addition et de multiplication. En substance, la propriété commutative nous dit qu'on peut inverser l'ordre des variables qui sont additionnées ou multipliées ensemble sans changer la vérité de l'expression:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Avec les propriétés commutativité de l'addition et la multiplication, nous avons la propriété associative, encore une fois l'application aussi bien à l'addition et de multiplication. Cette propriété nous dit qu'on peut associer des groupes ajoutés ou multiplié variables avec des parenthèses sans altérer la vérité des équations.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Enfin, nous avons la propriété distributive, illustrant la manière de développer une expression booléenne constituée par le produit d'une somme, et en marche arrière nous montre comment les termes peuvent ne pas être pris de Boolean sommes-des-produits:
Pour résumer, voici les trois propriétés fondamentales: commutative, associative et distributive.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
règles booléennes de simplification
algèbre de Boole trouve son utilisation la plus pratique dans la simplification des circuits logiques. Si nous traduisons la fonction d'un circuit logique de dans symboliques (Boolean) la forme, et d'appliquer certaines règles algébriques de l'équation résultant de réduire le nombre de termes et / ou des opérations arithmétiques, l'équation simplifiée peut être retraduite en forme de circuit pour un circuit logique de la scène la même fonction avec moins de composants. Si ***** fonction ALENT peut être atteint avec moins de composants, le résultat sera une fiabilité accrue et une diminution des coûts de fabrication.
À cette fin, il ya plusieurs règles de l'algèbre booléenne présentés dans cette section pour une utilisation dans la réduction des expressions de leurs formes les plus simples. L'identité et les propriétés déjà passé en revue dans ce chapitre sont très utiles dans la simplification booléenne, et pour la plupart similitude supporter une partie de nombreuses identités et les propriétés de "normal" algèbre. Toutefois, les règles présentées dans cette section sont tous uniques aux mathématiques booléenne.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Cette règle ne peut être prouvée par l'affacturage symboliquement un «A» sur les deux termes, puis en appliquant les règles d'un + 1 = 1 et 1A = A pour atteindre le résultat final:
S'il vous plaît noter comment la règle A + 1 = 1 a été utilisé pour réduire le (B + 1) terme à 1. Quand une règle comme "A + 1 = 1" est exprimé en utilisant la lettre "A", cela ne signifie pas qu'elle ne s'applique qu'aux expressions contenant "A". Ce que le «A» représente en règle générale comme A + 1 = 1 est une variable booléenne ou une collection de variables. C'est peut-être le concept le plus difficile pour les nouveaux étudiants à la maîtrise en matière de simplification booléenne: l'application des identités standardisées, les propriétés et les règles d'expressions et non sous forme standard.
Par exemple, l'expression booléenne ABC + 1 permet également de réduire à 1 par le biais de "A + 1 = 1 identité». Dans ce cas, nous reconnaissons que le "A" terme sous forme standard de l'identité peut représenter l'ensemble du "ABC" terme dans l'expression originale.
La règle suivante est similaire à la première présentés dans cette section, mais est en fait très différente et requiert une preuve plus intelligent:
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
ÅÖÛØ åäÇ áÑÄíÉ ÇáÕæÑÉ ÈÍÌãåÇ ÇáØÈíÚí.
Notez comment la dernière règle (A + AB = A) est utilisé pour "non-simplifier" le premier "A" terme dans l'expression, en changeant le "A" dans un "A + AB". Même si cela peut sembler comme un pas en arrière, il a certainement contribué à réduire l'expression de quelque chose de plus simple! Parfois, en mathématiques, nous devons prendre "en arrière" des mesures pour atteindre la solution la plus élégante. Savoir quand prendre une telle mesure et quand ne pas fait partie de l'art-forme de l'algèbre, comme une victoire dans une partie d'échecs nécessite presque toujours calculée sacrifices.
Une autre règle implique la simplification d'un produit-de-sommes l'expression:
Et, la preuve correspondante:
Pour résumer, voici les trois nouvelles règles de simplification booléenne exposées dans cette section:
exemples de simplification du circuit
Commençons par un circuit semi-conducteur porte dans le besoin de simplification. La Une »,« B »et« C signaux d'entrée "sont censés être fournis par des commutateurs, capteurs, circuits ou peut-être d'autres portes. Lorsque ces signaux proviennent n'intéresse pas dans la tâche de la réduction de la porte.
Notre première étape dans la simplification doit être d'écrire une expression booléenne pour ce circuit. Cette tâche est facile à réaliser, étape par étape si l'on commence par écrire des sous-expressions à la sortie de chaque porte, correspondant à des signaux d'entrée respectifs pour chaque porte. Rappelez-vous que les portes OU sont ***** ALENT à l'addition booléenne, tandis que les portes ET sont ***** ALENT à la multiplication booléenne. Par exemple, je vais écrire sous-expressions à la sortie des trois premières portes:
. . . puis un autre sous-expression de la grille suivante:
Enfin, la sortie ("Q") est considérée comme étant égale à la Colombie-Britannique expression AB + (B + C):
Maintenant que nous avons une expression booléenne à travailler, nous devons appliquer les règles de l'algèbre booléenne pour réduire l'expression à sa forme la plus simple (plus simple définie comme exigeant le moins de barrières à mettre en œuvre):
L'expression finale, B (A + C), est beaucoup plus simple que l'original, effectue encore la même fonction. Si vous souhaitez vérifier cela, vous pouvez générer une table de vérité pour les deux expressions et de déterminer le statut de Q (sortie des circuits ») pour toutes les combinaisons logiques étatiques huit A, B et C, pour les deux circuits. Les deux tables de vérité doivent être identiques.
Maintenant, nous devons générer un schéma à partir de cette expression booléenne. Pour ce faire, d'évaluer l'expression, à la suite bon ordre mathématique des opérations (multiplication avant l'addition, les opérations entre parenthèses avant toute autre chose), et d'en tirer les portes pour chaque étape. Rappelez-vous encore que les portes OU sont ***** ALENT à l'addition booléenne, tandis que les portes ET sont ***** ALENT à la multiplication booléenne. Dans ce cas, nous commencerons avec la sous-expression "A + C", qui est une porte OU:
La prochaine étape dans l'évaluation de l'expression «B (A + C)" est de multiplier (porte ET) le signal B par la sortie de la porte précédente (A, C +):
De toute évidence, ce circuit est beaucoup plus simple que l'original, ne contenant que deux portes logiques au lieu de cinq. Cette réduction résulte composante de la vitesse de fonctionnement plus élevée (moins de temps retard de la transition du signal d'entrée à la sortie du signal de transition), moins de consommation de puissance, moins de coûts et une plus grande fiabilité.
circuits de relais électromécaniques, étant généralement plus lente, plus le pouvoir de consommation électrique pour faire fonctionner, coûte plus cher, et avoir une vie moyenne plus courte que leurs homologues des semi-conducteurs, bénéficient considérablement d'une simplification booléenne. Prenons un exemple de circuit:
Comme précédemment, notre première étape dans la réduction de ce circuit à sa forme la plus simple doit être de développer une expression booléenne du schéma. La meilleure façon que j'ai trouvé pour ce faire est de suivre les mêmes étapes que j'avais normalement suivre afin de réduire un réseau de résistances en série-parallèle à une seule résistance totale. Par exemple, examinez le réseau de résistances suivantes à ses résistances disposés dans la structure même connexion que les contacts de relais dans le circuit de l'ancien, et correspondant formule résistance totale:
Rappelez-vous que les contacts parallèles sont ***** ALENT à l'addition booléenne, tandis que des contacts séries sont ***** ALENT à la multiplication booléenne. Donnez une expression booléenne pour ce circuit contact de relais, à la suite du même ordre de priorité que vous pouvez suivre pour réduire un réseau de résistances en série-parallèle à une résistance totale. Il peut être utile d'écrire une valeur booléenne sous-expression à gauche de chaque échelle «sonné», pour aider à organiser votre expression écrite:
Maintenant que nous avons une expression booléenne à travailler, nous devons appliquer les règles de l'algèbre booléenne pour réduire l'expression à sa forme la plus simple (plus simple définie comme exigeant le moins de contacts de relais pour mettre en œuvre):
Les plus enclins mathématiquement devrait être en mesure de voir que les deux étapes utilisant la règle "A + AB = A" peuvent être combinés en une seule étape, la règle étant extensible à: "A + AB + AC + AD +... = A "
Comme vous pouvez le voir, le circuit de réduction est beaucoup plus simple que l'original, effectue encore la même fonction logique:
* EXAMEN:
* Pour convertir un circuit de porte d'une expression booléenne, l'étiquette de chaque sortie de grille avec une sous-expression booléenne correspondant à des signaux d'entrée des portes, jusqu'à ce qu'une expression finale est atteint à la dernière porte.
* Pour convertir une expression booléenne à un circuit de porte, d'évaluer l'expression à l'aide de commande standard d'opérations: la multiplication avant l'addition, et les opérations entre parenthèses avant toute autre chose.
* Pour convertir un circuit logique à relais pour une expression booléenne, l'étiquette chaque échelon d'une sous-expression booléenne correspondant à des signaux d'entrée les contacts », jusqu'à ce que l'expression finale soit prise à la dernière bobine ou de la lumière. Pour déterminer le bon ordre de l'évaluation, de traiter les contacts comme s'ils étaient les résistances, et comme si vous étiez détermination de la résistance totale du réseau série-parallèle formé par eux. En d'autres termes, chercher des contacts qui sont, soit directement, en série ou directement en parallèle les uns avec les autres d'abord, puis "effondrement" dans les ***** ALENT booléenne sous-expressions avant de procéder à d'autres contacts.
* Pour convertir une expression booléenne à un circuit logique d'échelle, d'évaluer l'expression à l'aide de commande standard d'opérations: la multiplication avant l'addition, et les opérations entre parenthèses avant toute autre chose.
La fonction OU exclusif
Un élément manifestement absent de l'ensemble des opérations booléennes est celui de OU exclusif. Considérant que la fonction ou s'il est ***** ALENT à l'addition booléenne, la fonction et à la multiplication booléenne, et la fonction NON (inverseur) pour la complémentation booléenne, il n'y a pas Boolean direct ***** ALENT Exclusive-OR. Cela n'a pas empêché les gens de l'élaboration d'un symbole pour le représenter, si:
Ce symbole est rarement utilisé dans des expressions booléennes parce que les identités, les lois et règles de simplification portant sur l'addition, multiplication, et la complémentation ne s'appliquent pas à elle. Toutefois, il existe un moyen de représenter la fonction OU exclusif en termes de OR et AND, comme cela a été démontré dans les chapitres précédents: AB + A'B
En alency booléenne *****, cette règle peut être utile dans la simplification des expressions booléennes. Toute expression suivante de la AB + A'B forme (deux portes ET et une porte OU) peuvent être remplacées par une seule porte OU exclusif.
DeMorgan théorèmes
Un mathématicien nommé DeMorgan développé une paire de règles importantes concernant la complémentation de groupe dans l'algèbre de Boole. Par complémentation groupe, je fais référence à compléter les d'un groupe de termes, représentée par une longue barre à plus d'un variable.
Vous devez rappeler dans le chapitre sur les portes logiques que renversant toutes les entrées d'une porte qui renverse's Gate fonction essentielle de et vers OR, ou vice versa, et inverse aussi la sortie. Ainsi, une porte OU avec toutes les entrées inversées (une porte-négatif OU) se comporte comme une porte NAND, et une porte ET avec toutes les entrées inversée (négatif-porte ET) se comporte comme une porte NOR. théorèmes DeMorgan l'état de la même lence ***** à "en arrière" forme: que inversant la sortie de tous les résultats dans la porte de la même fonction que le type en face de la porte (et vs OR) avec des entrées inversées:
Une longue barre qui s'étend sur les actes AB terme comme un symbole de groupement, et en tant que tel est tout à fait différent du produit de A et B indépendamment inversé. En d'autres termes, (AB) n'est pas égale à A'B '. Parce que le "Premier" symbole (') ne peut pas être étalée sur deux variables comme une barre peut, nous sommes obligés d'utiliser des parenthèses pour faire appliquer à l'ensemble AB terme dans la phrase précédente. Un bar, cependant, agit en tant que symbole de groupement propre étirée sur plus d'une variable. Cela a un impact profond sur la façon dont expressions booléennes sont évaluées et réduites, comme nous le verrons.
DeMorgan théorème peut être pensée en termes de rupture d'un symbole longue barre. Quand une longue barre est rompu, l'opération directement sous les modifications pause de plus de multiplication, ou vice versa, et les morceaux brisés bar restent sur les variables individuelles. Pour illustrer:
Lorsque plusieurs «couches» de bars existent dans une expression, vous ne pouvez briser une barre à un moment, et il est généralement plus facile de commencer par briser la simplification la plus longue (supérieure) première barre. Pour illustrer, prenons l'expression (A + (BC) ») et de réduire en utilisant les théorèmes de DeMorgan:
Sur les conseils de la rupture la plus longue (supérieure) première barre, je vais commencer par briser la barre couvrant toute l'expression comme une première étape:
En conséquence, le circuit d'origine est réduit à un à trois entrées ET porte avec l'entrée A inversé:
Il ne faut jamais briser plus d'un bar en une seule étape, comme illustré ici:
Aussi tentant que cela puisse être de conserver des mesures et de briser plus d'un bar à un moment, il conduit souvent à un résultat incorrect, il ne faut pas le faire!
Il est possible de bien réduire cette expression en cassant la barre premier court métrage, plutôt que la barre de long en premier:
Le résultat final est le même, mais plusieurs étapes sont nécessaires par rapport à la première méthode, où le plus long bar a été brisée en premier. Notez comment dans la troisième étape nous avons cassé la barre de temps à deux endroits. C'est une opération légitime mathématiques, et pas la même que la rupture de deux bars en une seule étape! L'interdiction de la rupture de plus d'un bar en une seule étape ne constitue pas une interdiction de briser une barre en plus d'un endroit. Briser dans plus d'un lieu en une seule étape est correct; briser plus d'un bar en une seule étape l'est pas.
Vous pourriez vous demander pourquoi parenthèses ont été placés autour de la sous-expression B '+ C ", compte tenu du fait que je viens de les enlever à l'étape suivante. Je l'ai fait pour souligner un aspect important mais facilement oublié: du théorème de DeMorgan. Comme une longue barre fonctions en tant que symbole de regroupement, les variables autrefois regroupés par une barre cassée doit rester groupés peur priorité adéquate (ordre de l'opération) seront perdues. Dans cet exemple, il serait vraiment pas si j'ai oublié de mettre entre parenthèses après la rupture de la barre de courte durée, mais dans d'autres cas il pourrait. Considérons cet exemple, en commençant par une expression différente:
Comme vous pouvez le voir, le maintien du groupement sous-entendus par les barres de complémentation de cette expression est cruciale pour obtenir la bonne réponse.
Let's appliquer les principes de théorèmes DeMorgan à la simplification d'un circuit de porte:
Comme toujours, notre première étape dans la simplification de ce circuit doit être de générer une expression ***** ALENT booléenne. Nous pouvons le faire en plaçant une étiquette sous-expression à la sortie de chaque porte, que les entrées sont connus. Voici la première étape dans ce processus:
Ensuite, on peut étiqueter les produits de la première porte NOR et la porte NAND. Lorsque vous traitez avec des portes de sortie inversé, il m'est plus facile d'écrire une expression pour la sortie de la porte sans l'inversion finale, avec une flèche pointant à juste avant la bulle inversion. Puis, au fil de leader hors de la porte (après la bulle), j'écris le plein, l'expression complétée. Cela permet de garantir que je n'oublie pas un bar complètent dans la sous-expression, en me forçant à diviser la tâche expression écrite en deux étapes:
Enfin, nous écrire une expression (ou une paire d'expressions) pour la dernière porte NOR:
Maintenant, nous réduisons cette expression en utilisant les identités, les propriétés, les règles, et les théorèmes (DeMorgan's) de l'algèbre booléenne:
Le circuit porte ***** ALENT pour l'expression de cette très simplifiée est la suivante:
* EXAMEN
Théorèmes * DeMorgan décrivent les lence ***** entre les portes d'entrées inversées et les portes avec les sorties inversées. Bref, une porte NAND est ***** ALENT à une porte OU-négative, et une porte NOR est ***** ALENT à un négatif, et la porte.
* Lorsque "casser" un bar de complémentation dans une expression booléenne, l'opération directement sous la pause (addition ou multiplication) des revers, et les morceaux brisés bar reste sur la durée respective.
* Il est souvent plus facile d'aborder un problème en brisant la plus longue (supérieure) bar avant de rompre toutes les barres en dessous. Il ne faut jamais tenter de briser deux barres en une seule étape!
* Bars complémentation fonction de groupement des symboles.