Misplaced Pages

#112887

88-611: The algebraic notation used to represent the XNOR operation is S = A ⊙ B {\displaystyle S=A\odot B} . The algebraic expressions ( A + B ¯ ) ⋅ ( A ¯ + B ) {\displaystyle (A+{\overline {B}})\cdot ({\overline {A}}+B)} and A ⋅ B + A ¯ ⋅ B ¯ {\displaystyle A\cdot B+{\overline {A}}\cdot {\overline {B}}} both represent

176-456: A Boolean circuit relates time complexity (of an algorithm ) to circuit complexity . Whereas expressions denote mainly numbers in elementary algebra, in Boolean algebra, they denote the truth values false and true . These values are represented with the bits , 0 and 1. They do not behave like the integers 0 and 1, for which 1 + 1 = 2 , but may be identified with the elements of

264-425: A SR latch . With E high ( enable true), the signals can pass through the input gates to the encapsulated latch; all signal combinations except for (0, 0) = hold then immediately reproduce on the (Q, Q ) output, i.e. the latch is transparent . With E low ( enable false) the latch is closed (opaque) and remains in the state it was left the last time E was high. A periodic enable input signal may be called

352-486: A group under function composition , isomorphic to the Klein four-group , acting on the set of Boolean polynomials. Walter Gottschalk remarked that consequently a more appropriate name for the phenomenon would be the principle (or square ) of quaternality . A Venn diagram can be used as a representation of a Boolean operation using shaded overlapping regions. There is one region for each variable, all circular in

440-426: A write strobe . When the enable input is a clock signal , the latch is said to be level-sensitive (to the level of the clock signal), as opposed to edge-sensitive like flip-flops below. This latch exploits the fact that, in the two active input combinations (01 and 10) of a gated SR latch, R is the complement of S. The input NAND stage converts the two D input states (0 and 1) to these two input combinations for

528-462: A 0-controlled NAND acts as a NOT gate. When the S and R inputs are both high, feedback maintains the Q outputs to the previous state. When either is zero, they fix their output bits to 0 while to other adapts to the complement. S=R=0 produces the invalid state. From a teaching point of view, SR latches drawn as a pair of cross-coupled components (transistors, gates, tubes, etc.) are often hard to understand for beginners. A didactically easier explanation

616-455: A Boolean law directly as any tautology , understood as an equation that holds for all values of its variables over 0 and 1. All these definitions of Boolean algebra can be shown to be equivalent. Principle: If {X, R} is a partially ordered set , then {X, R(inverse)} is also a partially ordered set. There is nothing special about the choice of symbols for the values of Boolean algebra. 0 and 1 could be renamed to α and β , and as long as it

704-478: A NAND gate and an OR-AND-Invert gate, as shown in the following picture. This is based on the identity a ⊻ b ¯ ⟺ ( a ∧ ¯ b ) ∧ ¯ ( a ∨ b ) {\displaystyle {\overline {a\veebar b}}\iff \left(a{\overline {\land }}b\right){\overline {\land }}\left(a\lor b\right)} An alternative, which

792-435: A NAND gate is an inverted-input OR gate. Another alternative arrangement is of five NOR gates in a topology that emphasizes the construction of the function from ( A + B ¯ ) ⋅ ( A ¯ + B ) {\displaystyle (A+{\overline {B}})\cdot ({\overline {A}}+B)} , noting from de Morgan's Law that a NOR gate is an inverted-input AND gate. For

880-890: A NOT gate. If we consider the expression ( A + B ¯ ) ⋅ ( A ¯ + B ) {\displaystyle (A+{\overline {B}})\cdot ({\overline {A}}+B)} , we can construct an XNOR gate circuit directly using AND, OR and NOT gates. However, this approach requires five gates of three different kinds. As alternative, if different gates are available we can apply Boolean algebra to transform ( A + B ¯ ) ⋅ ( A ¯ + B ) ≡ ( A ⋅ B ) + ( A ¯ ⋅ B ¯ ) {\displaystyle (A+{\overline {B}})\cdot ({\overline {A}}+B)\equiv (A\cdot B)+({\overline {A}}\cdot {\overline {B}})} as stated above, and apply de Morgan's Law to

968-498: A NOT gate. With this it is now possible to derive the behavior of the SR latch as simple conditions (instead of, for example, assigning values to each line see how they propagate): Note: X means don't care , that is, either 0 or 1 is a valid value. The R = S = 1 combination is called a restricted combination or a forbidden state because, as both NOR gates then output zeros, it breaks the logical equation Q = not Q . The combination

SECTION 10

#1732766080113

1056-618: A cascade) to form the needed non-inverting amplifier. In this configuration, each amplifier may be considered as an active inverting feedback network for the other inverting amplifier. Thus the two stages are connected in a non-inverting loop although the circuit diagram is usually drawn as a symmetric cross-coupled pair (both the drawings are initially introduced in the Eccles–Jordan patent). Flip-flops and latches can be divided into common types: SR ("set-reset"), D ("data"), T ("toggle"), and JK (see History section above). The behavior of

1144-542: A circuit is described as sequential logic in electronics. When used in a finite-state machine , the output and next state depend not only on its current input, but also on its current state (and hence, previous inputs). It can also be used for counting of pulses, and for synchronizing variably-timed input signals to some reference timing signal. The term flip-flop has historically referred generically to both level-triggered (asynchronous, transparent, or opaque) and edge-triggered ( synchronous , or clocked ) circuits that store

1232-600: A logical "equivalence" function, unlike two-input XNOR gates. Boolean algebra In mathematics and mathematical logic , Boolean algebra is a branch of algebra . It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false , usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction ( and ) denoted as ∧ , disjunction ( or ) denoted as ∨ , and negation ( not ) denoted as ¬ . Elementary algebra, on

1320-537: A master–slave flip-flop. The truth table below shows that when the e nable/ c lock input is 0, the D input has no effect on the output. When E/C is high, the output equals D. The classic gated latch designs have some undesirable characteristics. They require dual-rail logic or an inverter. The input-to-output propagation may take up to three gate delays. The input-to-output propagation is not constant – some outputs take two gate delays while others take three. Designers looked for alternatives. A successful alternative

1408-506: A memory cell, a zero-order hold , or a delay line . Truth table: ( X denotes a don't care condition, meaning the signal is irrelevant) Most D-type flip-flops in ICs have the capability to be forced to the set or reset state (which ignores the D and clock inputs), much like an SR flip-flop. Usually, the illegal S = R = 1 condition is resolved in D-type flip-flops. Setting S = R = 0 makes

1496-400: A particular type can be described by the characteristic equation that derives the "next" output ( Q next ) in terms of the input signal(s) and/or the current output, Q {\displaystyle Q} . When using static gates as building blocks, the most fundamental latch is the asynchronous Set-Reset (SR) latch . Its two inputs S and R can set the internal state to 1 using

1584-578: A single bit of data using gates . Modern authors reserve the term flip-flop exclusively for edge-triggered storage elements and latches for level-triggered ones. The terms "edge-triggered", and "level-triggered" may be used to avoid ambiguity. When a level-triggered latch is enabled it becomes transparent, but an edge-triggered flip-flop's output only changes on a clock edge (either positive going or negative going). Different types of flip-flops and latches are available as integrated circuits , usually with multiple elements per chip. For example, 74HC75

1672-420: A transparent latch to make it non-transparent or opaque when another input (an "enable" input) is not asserted. When several transparent latches follow each other, if they are all transparent at the same time, signals will propagate through them all. However, following a transparent-high latch by a transparent-low latch (or vice-versa) causes the state and output to only change on clock edges, forming what

1760-494: Is a fundamental problem in the design of combinational logic circuits. Modern electronic design automation tools for very-large-scale integration (VLSI) circuits often rely on an efficient representation of Boolean functions known as (reduced ordered) binary decision diagrams (BDD) for logic synthesis and formal verification . Logic sentences that can be expressed in classical propositional calculus have an equivalent expression in Boolean algebra. Thus, Boolean logic

1848-558: Is a quadruple transparent latch in the 7400 series . The first electronic latch was invented in 1918 by the British physicists William Eccles and F. W. Jordan . It was initially called the Eccles–Jordan trigger circuit and consisted of two active elements ( vacuum tubes ). The design was used in the 1943 British Colossus codebreaking computer and such circuits and their transistorized versions were common in computers even after

SECTION 20

#1732766080113

1936-430: Is a self-dual operation of four arguments x , y , z , t . The principle of duality can be explained from a group theory perspective by the fact that there are exactly four functions that are one-to-one mappings ( automorphisms ) of the set of Boolean polynomials back to itself: the identity function, the complement function, the dual function and the contradual function (complemented dual). These four functions form

2024-426: Is also inappropriate in circuits where both inputs may go low simultaneously (i.e. a transition from restricted to hold ). The output could remain in a metastable state and may eventually lock at either 1 or 0 depending on the propagation time relations between the gates (a race condition ). To overcome the restricted combination, one can add gates to the inputs that would convert (S, R) = (1, 1) to one of

2112-425: Is also used in set theory and statistics . A precursor of Boolean algebra was Gottfried Wilhelm Leibniz 's algebra of concepts . The usage of binary in relation to the I Ching was central to Leibniz's characteristica universalis . It eventually created the foundations of algebra of concepts. Leibniz's algebra of concepts is deductively equivalent to the Boolean algebra of sets. Boole's algebra predated

2200-421: Is an identity such as x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z between two Boolean terms, where a Boolean term is defined as an expression built up from variables and the constants 0 and 1 using the operations ∧, ∨, and ¬. The concept can be extended to terms involving other Boolean operations such as ⊕, →, and ≡, but such extensions are unnecessary for the purposes to which the laws are put. Such purposes include

2288-425: Is called a master–slave flip-flop . A gated SR latch can be made by adding a second level of NAND gates to an inverted SR latch . The extra NAND gates further invert the inputs so a SR latch becomes a gated SR latch (a SR latch would transform into a gated SR latch with inverted enable). Alternatively, a gated SR latch (with non-inverting enable) can be made by adding a second level of AND gates to

2376-457: Is immaterial. When values and operations can be paired up in a way that leaves everything important unchanged when all pairs are switched simultaneously, the members of each pair are called dual to each other. Thus 0 and 1 are dual, and ∧ and ∨ are dual. The duality principle , also called De Morgan duality , asserts that Boolean algebra is unchanged when all dual pairs are interchanged. One change not needed to make as part of this interchange

2464-488: Is not strictly true with XOR and XNOR gates. However, extending the concept of the binary logical operation to three inputs, the SN74S135 with two shared "C" and four independent "A" and "B" inputs for its four outputs, was a device that followed the truth table: This is effectively Q = NOT ((A XOR B) XOR C). Another way to interpret this is that the output is true if an even number of inputs are true. It does not implement

2552-407: Is sometimes used to denote propositional calculus performed in this way. Boolean algebra is not sufficient to capture logic formulas using quantifiers , like those from first order logic . Although the development of mathematical logic did not follow Boole's program, the connection between his algebra and logic was later put on firm ground in the setting of algebraic logic , which also studies

2640-471: Is susceptible to logic hazard . Intentionally skewing the clock signal can avoid the hazard. The D flip-flop is widely used, and known as a "data" flip-flop. The D flip-flop captures the value of the D-input at a definite portion of the clock cycle (such as the rising edge of the clock). That captured value becomes the Q output. At other times, the output Q does not change. The D flip-flop can be viewed as

2728-456: Is the Earle latch. It requires only a single data input, and its output takes a constant two gate delays. In addition, the two gate levels of the Earle latch can, in some cases, be merged with the last two gate levels of the circuits driving the latch because many common computational circuits have an OR layer followed by an AND layer as their last two levels. Merging the latch function can implement

XNOR gate - Misplaced Pages Continue

2816-457: Is the basic storage element in sequential logic . Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems. Flip-flops and latches are used as data storage elements to store a single bit (binary digit) of data; one of its two states represents a "one" and the other represents a "zero". Such data storage can be used for storage of state , and such

2904-486: Is to draw the latch as a single feedback loop instead of the cross-coupling. The following is an SR latch built with an AND gate with one inverted input and an OR gate. Note that the inverter is not needed for the latch functionality, but rather to make both inputs High-active. Note that the SR AND-OR latch has the benefit that S = 1, R = 1 is well defined. In above version of the SR AND-OR latch it gives priority to

2992-493: Is useful when inverted inputs are also available (for example from a flip-flop ), uses a 2-2 AND-OR-Invert gate, shown on below on the right. CMOS implementations based on the OAI logic above can be realized with 10 transistors , as shown below. The implementation which uses both normal and inverted inputs uses 8 transistors, or 12 if inverters have to be used. Both the 4077 and 74x266 devices (SN74LS266, 74HC266, 74266, etc.) have

3080-463: The algebra of sets , by translating them into expressions in Boole's algebra, is explained in modern terms by saying that the algebra of sets is a Boolean algebra (note the indefinite article ). In fact, M. H. Stone proved in 1936 that every Boolean algebra is isomorphic to a field of sets . In the 1930s, while studying switching circuits , Claude Shannon observed that one could also apply

3168-450: The indicator function that takes the value 1 on F , and 0 outside F . The most general example is the set elements of a Boolean algebra , with all of the foregoing being instances thereof. As with elementary algebra, the purely equational part of the theory may be developed, without considering explicit values for the variables. While Elementary algebra has four operations (addition, subtraction, multiplication, and division),

3256-400: The models of these axioms as treated in § Boolean algebras . Writing down further laws of Boolean algebra cannot give rise to any new consequences of these axioms, nor can it rule out any model of them. In contrast, in a list of some but not all of the same laws, there could have been Boolean laws that did not follow from those on the list, and moreover there would have been models of

3344-462: The two-element field GF(2) , that is, integer arithmetic modulo 2 , for which 1 + 1 = 0 . Addition and multiplication then play the Boolean roles of XOR (exclusive-or) and AND (conjunction), respectively, with disjunction x ∨ y (inclusive-or) definable as x + y − xy and negation ¬ x as 1 − x . In GF(2) , − may be replaced by + , since they denote the same operation; however, this way of writing Boolean operations allows applying

3432-466: The Boolean algebra has only three basic operations: conjunction , disjunction , and negation , expressed with the corresponding binary operators AND ( ∧ {\displaystyle \land } ) and OR ( ∨ {\displaystyle \lor } ) and the unary operator NOT ( ¬ {\displaystyle \neg } ), collectively referred to as Boolean operators . Variables in Boolean algebra that store

3520-459: The JK latch is an SR latch that is made to toggle its output (oscillate between 0 and 1) when passed the input combination of 11. Unlike the JK flip-flop, the 11 input combination for the JK latch is not very useful because there is no clock that directs toggling. Latches are designed to be transparent. That is, input signal changes cause immediate changes in output. Additional logic can be added to

3608-505: The Laws of Thought (1854). According to Huntington , the term Boolean algebra was first suggested by Henry M. Sheffer in 1913, although Charles Sanders Peirce gave the title "A Boolian [ sic ] Algebra with One Constant" to the first chapter of his "The Simplest Mathematics" in 1880. Boolean algebra has been fundamental in the development of digital electronics , and is provided for in all modern programming languages . It

XNOR gate - Misplaced Pages Continue

3696-645: The NAND constructions, the lower arrangement offers the advantage of a shorter propagation delay (the time delay between an input changing and the output changing). For the NOR constructions, the upper arrangement requires fewer gates. From the opposite perspective, constructing other gates using only XNOR gates is possible though XNOR is not a fully universal logic gate . NOT and XOR gates can be constructed this way. Although other gates (OR, NOR, AND, NAND) are available from manufacturers with three or more inputs per gate, this

3784-405: The NAND inputs must normally be logic 1 to avoid affecting the latching action, the inputs are considered to be inverted in this circuit (or active low). The circuit uses the same feedback as SR NOR, just replacing NOR gates with NAND gates, to "remember" and retain its logical state even after the controlling input signals have changed. Again, recall that a 1-controlled NAND always outputs 0, while

3872-583: The NOR gate with the set control and "reset NOR" the NOR with the reset control; in the figures the set NOR is the bottom one and the reset NOR is the top one. The output of the reset NOR will be our stored bit Q, while we will see that the output of the set NOR stores its complement Q . To derive the behavior of the SR NOR latch, consider S and R as control inputs and remember that, from the equations above, set and reset NOR with control 1 will fix their outputs to 0, while set and reset NOR with control 0 will act as

3960-528: The R signal over the S signal. If priority of S over R is needed, this can be achieved by connecting output Q to the output of the OR gate instead of the output of the AND gate. The SR AND-OR latch is easier to understand, because both gates can be explained in isolation, again with the control view of AND and OR from above. When neither S or R is set, then both the OR gate and the AND gate are in "hold mode", i.e., they let

4048-424: The SR NOR latch using logic transformations: inverting the output of the OR gate and also the 2nd input of the AND gate and connecting the inverted Q output between these two added inverters; with the AND gate with both inputs inverted being equivalent to a NOR gate according to De Morgan's laws . The JK latch is much less frequently used than the JK flip-flop. The JK latch follows the following state table: Hence,

4136-531: The TTL 74LS implementation, the 74LS266, as well as the CMOS gates (CD4077, 74HC4077 and 74HC266 and so on) are available from most semiconductor manufacturers such as Texas Instruments or NXP , etc. They are usually available in both through-hole DIP and SOIC formats (SOIC-14, SOC-14 or TSSOP-14). Datasheets are readily available in most datasheet databases and suppliers. An XNOR gate can be implemented using

4224-694: The XNOR gate with inputs A and B . There are two symbols for XNOR gates : one with distinctive shape and one with rectangular shape and label. Both symbols for the XNOR gate are that of the XOR gate with an added inversion bubble. XNOR gates are represented in most TTL and CMOS IC families. The standard 4000 series CMOS IC is the 4077, and the TTL IC is the 74266 (although an open-collector implementation). Both include four independent, two-input, XNOR gates. The (now obsolete) 74S135 implemented four two-input XOR/XNOR gates or two three-input XNOR gates. Both

4312-475: The algebraic systems of many other logics. The problem of determining whether the variables of a given Boolean (propositional) formula can be assigned in such a way as to make the formula evaluate to true is called the Boolean satisfiability problem (SAT), and is of importance to theoretical computer science , being the first problem shown to be NP-complete . The closely related model of computation known as

4400-493: The axioms thus far have all been for monotonic Boolean logic. Nonmonotonicity enters via complement ¬ as follows. The complement operation is defined by the following two laws. All properties of negation including the laws below follow from the above two laws alone. In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, hence in both algebras it satisfies the double negation law (also called involution law) But whereas ordinary algebra satisfies

4488-437: The behavior of one gate appears to be intertwined with the other gate. The standard NOR or NAND latches could also be re-drawn with the feedback loop, but in their case the feedback loop does not show the same signal value throughout the whole feedback loop. However, the SR AND-OR latch has the drawback that it would need an extra inverter, if an inverted Q output is needed. Note that the SR AND-OR latch can be transformed into

SECTION 50

#1732766080113

4576-525: The circle. While we have not shown the Venn diagrams for the constants 0 and 1, they are trivial, being respectively a white box and a dark box, neither one containing a circle. However, we could put a circle for x in those boxes, in which case each would denote a function of one argument, x , which returns the same value independently of x , called a constant function. As far as their outputs are concerned, constants and constant functions are indistinguishable;

4664-436: The combination S=1 and R=0, and can reset the internal state to 0 using the combination S=0 and R=1. The SR latch can be constructed from a pair of cross-coupled NOR or NAND logic gates . The stored bit is present on the output marked Q. It is convenient to think of NAND, NOR, AND and OR as controlled operations, where one input is chosen as the control input set and the other bit as the input to be processed depending on

4752-416: The definition of a Boolean algebra as any model of the Boolean laws, and as a means for deriving new laws from old as in the derivation of x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) from y ∧ z = z ∧ y (as treated in § Axiomatizing Boolean algebra ). Boolean algebra satisfies many of the same laws as ordinary algebra when one matches up ∨ with addition and ∧ with multiplication. In particular

4840-443: The difference is that a constant takes no arguments, called a zeroary or nullary operation, while a constant function takes one argument, which it ignores, and is a unary operation. Venn diagrams are helpful in visualizing laws. The commutativity laws for ∧ and ∨ can be seen from the symmetry of the diagrams: a binary operation that was not commutative would not have a symmetric diagram because interchanging x and y would have

4928-415: The effect of reflecting the diagram horizontally and any failure of commutativity would then appear as a failure of symmetry. Idempotence of ∧ and ∨ can be visualized by sliding the two circles together and noting that the shaded area then becomes the whole circle, for both ∧ and ∨. To see the first absorption law, x ∧ ( x ∨ y ) = x , start with the diagram in the middle for x ∨ y and note that

5016-456: The examples here. The interior and exterior of region x corresponds respectively to the values 1 (true) and 0 (false) for variable x . The shading indicates the value of the operation for each combination of regions, with dark denoting 1 and light 0 (some authors use the opposite convention). The three Venn diagrams in the figure below represent respectively conjunction x ∧ y , disjunction x ∨ y , and complement ¬ x . For conjunction,

5104-487: The fact that, when the enable input is on, the signal propagates directly through the circuit, from the input D to the output Q. Gated D-latches are also level-sensitive with respect to the level of the clock or enable signal. Transparent latches are typically used as I/O ports or in asynchronous systems, or in synchronous two-phase systems ( synchronous systems that use a two-phase clock ), where two latches operating on different clock phases prevent data transparency as in

5192-417: The following laws are common to both kinds of algebra: The following laws hold in Boolean algebra, but not in ordinary algebra: Taking x = 2 in the third law above shows that it is not an ordinary algebra law, since 2 × 2 = 4 . The remaining five laws can be falsified in ordinary algebra by taking all variables to be 1. For example, in absorption law 1, the left hand side would be 1(1 + 1) = 2 , while

5280-548: The four NOR gates are replaced by NAND gates, this results in an XOR gate, which can be converted to an XNOR gate by inverting the output or one of the inputs (e.g. with a fifth NAND gate). An alternative arrangement is of five NAND gates in a topology that emphasizes the construction of the function from ( A ⋅ B ) + ( A ¯ ⋅ B ¯ ) {\displaystyle (A\cdot B)+({\overline {A}}\cdot {\overline {B}})} , noting from de Morgan's Law that

5368-449: The input through, their output is the input from the feedback loop. When input S = 1, then the OR gate outputs 1, regardless of the other input from the feedback loop ("set mode"). When input R = 1 then the AND gate outputs 0, regardless of the other input from the feedback loop ("reset mode"). And since the AND gate takes the output of the OR gate as input, R has priority over S. Latches drawn as cross-coupled gates may look less intuitive, as

SECTION 60

#1732766080113

5456-575: The introduction of integrated circuits , though latches and flip-flops made from logic gates are also common now. Early latches were known variously as trigger circuits or multivibrators . According to P. L. Lindley, an engineer at the US Jet Propulsion Laboratory , the flip-flop types detailed below (SR, D, T, JK) were first discussed in a 1954 UCLA course on computer design by Montgomery Phister, and then appeared in his book Logical Design of Digital Computers. Lindley

5544-464: The last term to get ( A ⋅ B ) + ( A + B ) ¯ {\displaystyle (A\cdot B)+{\overline {(A+B)}}} which can be implemented using only three gates as shown on the right. An XNOR gate circuit can be made from four NOR gates. In fact, both NAND and NOR gates are so-called "universal gates" and any logical function can be constructed from either NAND logic or NOR logic alone. If

5632-482: The latch with no additional gate delays. The merge is commonly exploited in the design of pipelined computers, and, in fact, was originally developed by John G. Earle to be used in the IBM System/360 Model 91 for that purpose. The Earle latch is hazard free. If the middle NAND gate is omitted, then one gets the polarity hold latch , which is commonly used because it demands less logic. However, it

5720-435: The listed laws that were not Boolean algebras. This axiomatization is by no means the only one, or even necessarily the most natural given that attention was not paid as to whether some of the axioms followed from others, but there was simply a choice to stop when enough laws had been noticed, treated further in § Axiomatizing Boolean algebra . Or the intermediate notion of axiom can be sidestepped altogether by defining

5808-476: The logical value of 0 and 1 are called the Boolean variables . They are used to store either true or false values. The basic operations on Boolean variables x and y are defined as follows: Alternatively, the values of x ∧ y , x ∨ y , and ¬ x can be expressed by tabulating their values with truth tables as follows: When used in expressions, the operators are applied according to

5896-425: The modern developments in abstract algebra and mathematical logic ; it is however seen as connected to the origins of both fields. In an abstract setting, Boolean algebra was perfected in the late 19th century by Jevons , Schröder , Huntington and others, until it reached the modern conception of an (abstract) mathematical structure . For example, the empirical observation that one can manipulate expressions in

5984-487: The next SR latch by inverting the data input signal. The low state of the enable signal produces the inactive "11" combination. Thus a gated D-latch may be considered as a one-input synchronous SR latch . This configuration prevents application of the restricted input combination. It is also known as transparent latch , data latch , or simply gated latch . It has a data input and an enable signal (sometimes named clock , or control ). The word transparent comes from

6072-534: The non-restricted combinations. That can be: This is done in nearly every programmable logic controller . Alternatively, the restricted combination can be made to toggle the output. The result is the JK latch . The characteristic equation for the SR latch is: where A + B means (A or B), AB means (A and B) Another expression is: The circuit shown below is a basic NAND latch. The inputs are also generally designated S and R for Set and Reset respectively. Because

6160-428: The notation has been changed, despite the fact that 0s and 1s are still being used. But if in addition to interchanging the names of the values, the names of the two binary operations are also interchanged, now there is no trace of what was done. The end product is completely indistinguishable from what was started with. The columns for x ∧ y and x ∨ y in the truth tables have changed places, but that switch

6248-447: The other NOR, as shown in the figure. We call feedback inputs , or simply feedbacks these output-to-input connections. The remaining inputs we will use as control inputs as explained above. Notice that at this point, because everything is symmetric, it does not matter to which inputs the outputs are connected. We now break the symmetry by choosing which of the remaining control inputs will be our set and reset and we can call "set NOR"

6336-420: The other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations. Boolean algebra was introduced by George Boole in his first book The Mathematical Analysis of Logic (1847), and set forth more fully in his An Investigation of

6424-411: The portion of the shaded area in common with the x circle is the whole of the x circle. For the second absorption law, x ∨ ( x ∧ y ) = x , start with the left diagram for x ∧ y and note that shading the whole of the x circle results in just the x circle being shaded, since the previous shading was inside the x circle. The double negation law can be seen by complementing the shading in

6512-416: The precedence rules. As with elementary algebra, expressions in parentheses are evaluated first, following the precedence rules. If the truth values 0 and 1 are interpreted as integers, these operations may be expressed with the ordinary operations of arithmetic (where x + y uses addition and xy uses multiplication), or by the minimum/maximum functions: One might consider that only negation and one of

6600-406: The region inside both circles is shaded to indicate that x ∧ y is 1 when both variables are 1. The other regions are left unshaded to indicate that x ∧ y is 0 for the other three combinations. The second diagram represents disjunction x ∨ y by shading those regions that lie inside either or both circles. The third diagram represents complement ¬ x by shading the region not inside

6688-434: The right hand side would be 1 (and so on). All of the laws treated thus far have been for conjunction and disjunction. These operations have the property that changing either argument either leaves the output unchanged, or the output changes in the same way as the input. Equivalently, changing any variable from 0 to 1 never results in the output changing from 1 to 0. Operations with this property are said to be monotone . Thus

6776-548: The rules of Boole's algebra in this setting, and he introduced switching algebra as a way to analyze and design circuits by algebraic means in terms of logic gates . Shannon already had at his disposal the abstract mathematical apparatus, thus he cast his switching algebra as the two-element Boolean algebra . In modern circuit engineering settings, there is little need to consider other Boolean algebras, thus "switching algebra" and "Boolean algebra" are often used interchangeably. Efficient implementation of Boolean functions

6864-400: The same pinout diagram, as follows: Pinout diagram of the 74HC266N, 74LS266 and CD4077 quad XNOR plastic dual in-line package 14-pin package ( PDIP-14 ) ICs . If a specific type of gate is not available, a circuit that implements the same function can be constructed from other available gates. A circuit implementing an XNOR function can be trivially constructed from an XOR gate followed by

6952-431: The state of the control. Then, all of these gates have one control value that ignores the input (x) and outputs a constant value, while the other control value lets the input pass (maybe complemented): Essentially, they can all be used as switches that either set a specific value or let an input value pass. The SR NOR latch consists of two parallel NOR gates where the output of each NOR is also fanned out into one input of

7040-411: The third diagram for ¬ x , which shades the x circle. Flip-flop (electronics) In electronics , flip-flops and latches are circuits that have two stable states that can store state information – a bistable multivibrator . The circuit can be made to change state by signals applied to one or more control inputs and will output its state (often along with its logical complement too). It

7128-686: The time were all of the type that came to be known as J-K. In designing a logical system, Nelson assigned letters to flip-flop inputs as follows: #1: A & B, #2: C & D, #3: E & F, #4: G & H, #5: J & K. Nelson used the notations " j -input" and " k -input" in a patent application filed in 1953. Transparent or asynchronous latches can be built around a single pair of cross-coupled inverting elements: vacuum tubes , bipolar transistors , field-effect transistors , inverters , and inverting logic gates have all been used in practical circuits. Clocked flip-flops are specially designed for synchronous systems; such devices ignore their inputs except at

7216-420: The transition of a dedicated clock signal (known as clocking, pulsing, or strobing). Clocking causes the flip-flop either to change or to retain its output signal based upon the values of the input signals at the transition. Some flip-flops change output on the rising edge of the clock, others on the falling edge. Since the elementary amplifying stages are inverting, two stages can be connected in succession (as

7304-482: The two laws Boolean algebra satisfies De Morgan's laws : The laws listed above define Boolean algebra, in the sense that they entail the rest of the subject. The laws complementation 1 and 2, together with the monotone laws, suffice for this purpose and can therefore be taken as one possible complete set of laws or axiomatization of Boolean algebra. Every law of Boolean algebra follows logically from these axioms. Furthermore, Boolean algebras can then be defined as

7392-430: The two other operations are basic because of the following identities that allow one to define conjunction in terms of negation and the disjunction, and vice versa ( De Morgan's laws ): Operations composed from the basic operations include, among others, the following: These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs. A law of Boolean algebra

7480-402: The usual arithmetic operations of integers (this may be useful when using a programming language in which GF(2) is not implemented). Boolean algebra also deals with functions which have their values in the set {0,1} . A sequence of bits is a commonly used example of such a function. Another common example is the totality of subsets of a set E : to a subset F of E , one can define

7568-462: Was at the time working at Hughes Aircraft under Eldred Nelson, who had coined the term JK for a flip-flop which changed states when both inputs were on (a logical "one"). The other names were coined by Phister. They differ slightly from some of the definitions given below. Lindley explains that he heard the story of the JK flip-flop from Eldred Nelson, who is responsible for coining the term while working at Hughes Aircraft. Flip-flops in use at Hughes at

7656-439: Was done consistently throughout, it would still be Boolean algebra, albeit with some obvious cosmetic differences. But suppose 0 and 1 were renamed 1 and 0 respectively. Then it would still be Boolean algebra, and moreover operating on the same values. However, it would not be identical to our original Boolean algebra because now ∨ behaves the way ∧ used to do and vice versa. So there are still some cosmetic differences to show that

7744-505: Was to complement. Complement is a self-dual operation. The identity or do-nothing operation x (copy the input to the output) is also self-dual. A more complicated example of a self-dual operation is ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . There is no self-dual binary operation that depends on both its arguments. A composition of self-dual operations is a self-dual operation. For example, if f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , then f ( f ( x , y , z ), x , t )

#112887