Computer Science
De Morgan's Laws
De Morgan's Laws are a pair of fundamental principles in Boolean algebra that describe the relationship between logical conjunction (AND) and disjunction (OR) operations. The laws state that the negation of a conjunction is equivalent to the disjunction of the negations of the individual terms, and the negation of a disjunction is equivalent to the conjunction of the negations of the individual terms. These laws are widely used in computer science for simplifying and optimizing logical expressions.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "De Morgan's Laws"
eBook - PDFElectricity and Electronics for Renewable Energy Technology
An Introduction
- Ahmad Hemami(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
A + 1 = 1 A × 1 = A Example 0 1 1 0 1 0 1 1 1 1 1 1 + = × = + = × = The following two laws are called De Morgan laws: Ninth Law (De Morgan First Law) The inverse of the result of OR’ing two entities A and B is the same as if the inverse of those entities are AND’ed. A B A B + = ⋅ Example Because there are four different cases for two inputs all are shown in a truth table. TRUTH TABLE FOR THE FIRST DE MORGAN LAW A B A + B A B + A B A B ⋅ 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 Note that A B + is the output of a NOR gate. 688 Electricity and Electronics for Renewable Energy Technology Tenth Law (De Morgan Second Law) The inverse of the result of AND’ing two entities A and B is the same as if the inverse of those entities are OR’ed. A B A B × = + Example The following truth table illustrates the four possibilities. TRUTH TABLE FOR THE SECOND DE MORGAN LAW A B A × B A B × A B A B + 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 The term A B × represents the output of a NAND circuit. The implementation of De Morgan laws is converting AND and OR gates and vice versa when they are combined with a NOT gate. Consider the equivalence between the two expressions A B + and A B ⋅ and between A B × and A B + based on De Morgan’s laws. The associated gates combinations are shown in Figure 23.14a. Note that an alternative way when a NOT gate is involved to invert an input signal is shown in Figure 23.14b. 23.4.2 Application of Boolean Algebra Laws Boolean algebra is employed to simplify logic circuits. Simplification often leads to having fewer components. Moreover, many cases can be found where two logic circuits lead to the same results. The two circuits in this case are equivalent to each other. Boolean algebra can help to verify and identify these circuits. This helps to reduce the number of gates in a circuit or synthe-size a logic gate by some other gates, when necessary.
eBook - ePub- J. Gibson(Author)
- 2013(Publication Date)
- Routledge(Publisher)
must be identical. This demonstrates that de Morgan’s theorem is true in this particular case.The relationships of Boolean algebra may be used to manipulate Boolean expressions (that is mathematical descriptions of logic circuits) into alternative forms. The usual reason for performing such manipulations is to change one Boolean expression for a circuit into another which is more easily or more economically constructed from the available components.Example 2.3 Suppose the output, R, of some circuit is given as Can this be manipulated into a more simple form?SolutionChange the expression using the Distributive laws toSince B + = 1 from the Complement relations, then it can be written aswhich can be further treated in the same way giving This final form is much simpler than the original, but some steps in the reduction were not obvious unless the answer was already known.One fault of Boolean algebra is that the steps in the manipulation are not always obvious. Chapter 3 introduces some methods which may be used to reduce complicated Boolean expressions in a reliable and consistent manner.2.5 De Morgan’s theorem De Morgan’s theorem (or law) is very important; it is probably one of the most frequently used relationships in Boolean algebra. The two forms are and both forms are valid with any number of variables.The principle use of de Morgan’s theorem is to convert an OR type of expression (i.e. either OR or NOR) into an AND form (i.e. either AND or NAND) and vice versa when a particular type of logic gate is to be used for circuit construction. For example, suppose that X = A + B + C and that a circuit is required to produce X using only NAND gates. Because double inversion is the same as no inversion, then X = ; applying de Morgan’s theorem to
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Library Press(Publisher)
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 the third diagram for ¬ x , which shades the x circle. To visualize the first De Morgan's law, (¬ x ) ∧ (¬ y ) = ¬( x ∨ y ), start with the middle diagram for x ∨ y and complement its shading so that only the region outside both circles is shaded, which is what the right hand side of the law describes. The result is the same as if we shaded that region which is both outside the x circle and outside the y circle, i.e. the conjunction of their exteriors, which is what the left hand side of the law describes. The second De Morgan's law, (¬ x ) ∨ (¬ y ) = ¬( x ∧ y ), works the same way with the two diagrams interchanged. The first complement law, x ∧ ¬ x = 0, says that the interior and exterior of the x circle have no overlap. The second complement law, x ∨ ¬ x = 1, says that everything is either inside or outside the x circle. Digital logic gates Digital logic is the application of the Boolean algebra of 0 and 1 to electronic hardware consisting of logic gates connected to form a circuit diagram. Each gate implements a Boolean operation, and is depicted schematically by a shape indicating the operation. The shapes associated with the gates for conjunction (AND-gates), disjunction (OR-gates), and complement (inverters) are as follows. The lines on the left of each gate represent input wires or ports . The value of the input is represented by a voltage on the lead. For so-called active-high logic 0 is represented by a voltage close to zero or ground while 1 is represented by a voltage close to the supply voltage; active-low reverses this. The line on the right of each gate represents the output port, which normally follows the same voltage conventions as the input ports.
eBook - ePubDigital Electronic Circuits
Principles and Practices
- Shuqin Lou, Chunling Yang(Authors)
- 2019(Publication Date)
- De Gruyter(Publisher)
In Boolean algebra, there are certain well-developed laws, rules, and theorems that must be followed in order to properly apply Boolean algebra. This section only introduces the most important Boolean algebra laws, rules, and theorems for analyzing and designing digital circuits.The objectives of this section are to- – Apply commutative laws, associative laws, and distributive laws
- – Apply basic rules of Boolean algebra
- – Apply DeMorgan’s theorems
3.3.1 Boolean addition and Boolean multiplication
1. Boolean addition
Boolean addition is equivalent to the OR operation and the basic rules are illustrated with their relation to the OR gate as shown in Figure 3.3.1 .Figure 3.3.1: Illustration of the relation between Boolean addition and OR gate.In Boolean algebra, a sum term is a sum of literals. In logic circuit, a sum term could be produced by an OR operation without AND operation involved. For example, A +C ,andA +B ˉare sum terms.A ˉ+B ˉ+C ˉ2. Boolean multiplication
Boolean multiplication is equivalent to AND operation and the basic rules are illustrated with their relation to AND gate as shown in Figure 3.3.2 .Figure 3.3.2: Illustration of the relation between Boolean multiplication and AND gate.In Boolean algebra, a product term is a product of literals. In logic circuit, a product term could be produced by an AND operation without OR operation involved. For example, AC ,,AB ˉ, andA ˉB ˉC ˉare product terms.A ˉB ˉC D3.3.2 Laws of Boolean algebra
Similar to ordinary algebra, Boolean algebra has three basic laws including commutative laws, associative laws, and distributive laws. Each of the laws is illustrated with two or three variables, but the number of variables can be extended.1. Commutative laws
The commutative laws for the multiplication and the addition of two variables are expressed as below:A B = B AA + B = B + A2. Associative laws
The associative laws for the multiplication and the addition of three variables are written as follows:A BC = AB CA + B+ C = A +B + C3. Distributive laws
No longer available |Learn more- (Author)
- 2014(Publication Date)
- White Word Publications(Publisher)
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 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 se en by complementing the shading in the third diagram for ¬ x , which shades the x circle. To visualize the first De Morgan's law, (¬ x ) ∧ (¬ y ) = ¬( x ∨ y ), start with the middle diagram for x ∨ y and complement its shading so that only the region outside both circles is shaded, which is what the right hand side of the law describes. The result is the same as if we shaded that region which is both outside the x circle and outside the y circle, i.e. the conjunction of their exteriors, which is what the left hand side of the law describes. The second De Morgan's law, (¬ x ) ∨ (¬ y ) = ¬( x ∧ y ), works the same way with the two diagrams interchanged. The first complement law, x ∧ ¬ x = 0, says that the interior and exterior of the x circle have no overlap. The second complement law, x ∨ ¬ x = 1, says that everything is either inside or outside the x circle. Digital logic gates Digital logic is the application of the Boolean algebra of 0 and 1 to electronic hardware consisting of logic gates connected to form a circuit diagram. Each gate implements a Boolean operation, and is depicted schem atically by a shape indicating the operation. The shapes associated with the gates for conjunction (AND -gates), disjunction (OR -gates), and complement (inverters) are as follows.
eBook - PDF- S Sasti D Sasti(Author)
- 2019(Publication Date)
- Macmillan(Publisher)
1 Module 1 Topic 1: Principles of digital electronics for computing Boolean algebra and logic gates Module 1 Overview At the end of this module, you will be able to: • Unit 1.1: Demonstrate algebraic laws using Boolean algebra. • Unit 1.2: Translate Boolean expressions into logic diagrams and vice versa. • Unit 1.3: Use truth tables to represent Boolean expressions. • Unit 1.4: Use decision tables to simplify Boolean expressions. • Unit 1.5: Demonstrate knowledge of logic gates. • Unit 1.6: Demonstrate knowledge of the principles of logic devices. • Unit 1.7: Identify integrated circuits (ICs) that implement gates for computer systems. • Unit 1.8: Explain memory chips in terms of their use, functions and operational characteristics. Unit 1.1: Boolean algebra 1.1.1 Introduction You learned in Level 2 that computers are electronic devices made up of digital logic circuits that work on a sequence of ON or OFF switches. As programmers, we commonly refer to these switches as binary values represented by 1 or 0. Boolean algebra is a branch of mathematics based on logic . It has its own set of rules and laws which are used to analyse and simplify digital logic circuits. George Boole invented this logical way of analysing Boolean expressions to produce either a TRUE or FALSE result which can be represented by 1 or 0. 1.1.2 Boolean algebra Definition: Boolean algebra Boolean algebra is the algebra of logic. Boolean algebra operates using the logical operators on Boolean values. We will look at some of the Boolean algebraic laws and operations in this module. Logical operators Refer to Table 1.1 for a brief explanation of logical operators. Did you know? In 1847, George Boole introduced the idea of Boolean algebra and Boolean logic in his first book, The Mathematical Analysis of Logic . His intention was to demonstrate how we can use mathematics to represent complex human reasoning in a logical way. This idea led to the design and logical working of computers.
eBook - PDFDigital Electronic Circuits
Principles and Practices
- Shuqin Lou, Chunling Yang(Authors)
- 2019(Publication Date)
- De Gruyter(Publisher)
3.3 Laws, rules, and theorems of Boolean algebra In Boolean algebra, there are certain well-developed laws, rules, and theorems that must be followed in order to properly apply Boolean algebra. This section only introduces the most important Boolean algebra laws, rules, and theorems for analyz-ing and designing digital circuits. A B 0 1 1 0 0 0 1 1 0 1 0 1 Inputs (c) F A B A B = 1 F (a) (b) Output F = A B Figure 3.2.10: Standard logic symbol and truth table of an exclusive-OR gate: (a) distinctive shape; (b) rectangular outline with the XOR qualifying symbol; (c) truth table. A B 1 0 0 1 0 0 1 1 0 1 0 1 Inputs (c) F A B A B = 1 F (a) (b) Output F = A B Figure 3.2.11: Standard logic symbol and truth table of an exclusive-NOR gate: (a) distinctive shape; (b) rectangular outline with the XNOR qualifying symbol (=1); (c) truth table. 44 3 Boolean algebra and logic simplification The objectives of this section are to – Apply commutative laws, associative laws, and distributive laws – Apply basic rules of Boolean algebra – Apply DeMorgan ’ s theorems 3.3.1 Boolean addition and Boolean multiplication 1. Boolean addition Boolean addition is equivalent to the OR operation and the basic rules are illustrated with their relation to the OR gate as shown in Figure 3.3.1. In Boolean algebra, a sum term is a sum of literals. In logic circuit, a sum term could be produced by an OR operation without AND operation involved. For exam-ple, A + C , A + B and A + B + C are sum terms. 2. Boolean multiplication Boolean multiplication is equivalent to AND operation and the basic rules are illu-strated with their relation to AND gate as shown in Figure 3.3.2. In Boolean algebra, a product term is a product of literals. In logic circuit, a product term could be produced by an AND operation without OR operation involved. For example, AC , A B , A B C , and A BCD are product terms.
- Charles Roth, Jr., Larry Kinney, Eugene John, , Charles Roth, Jr., Larry Kinney, Eugene John(Authors)
- 2020(Publication Date)
- Cengage Learning EMEA(Publisher)
Boolean Algebra 43 while a switch in parallel with a short circuit is equivalent to a short circuit. If a switch is labeled Auni2032 , then it is open when A is closed and conversely. Hence, A in parallel with Auni2032 can be replaced with a closed circuit because one or the other of the two switches is always closed. Similarly, switch A in series with Auni2032 can be replaced with an open circuit (why?). 2.5 Commutative, Associative, Distributive, and DeMorgan’s Laws Many of the laws of ordinary algebra, such as the commutative and associative laws, also apply to Boolean algebra. The commutative laws for AND and OR, which fol- low directly from the definitions of the AND and OR operations, are A (A + 1 = 1) = A Auni2032 (A + Auni2032 = 1) = (A • Auni2032 = 0) = A Auni2032 XY = YX (2-9) X + Y = Y + X (2-9D) This means that the order in which the variables are written will not affect the result of applying the AND and OR operations. The associative laws also apply to AND and OR: (XY)Z = X(YZ) = XYZ (2-10) (X + Y) + Z = X + (Y + Z) = X + Y + Z (2-10D) When forming the AND (or OR) of three variables, the result is independent of which pair of variables we associate together first, so parentheses can be omitted as indicated in Equations (2-10) and (2-10D). Copyright 2021 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 44 Unit 2 When the preceding laws are interpreted as switch circuits, they simply indicate that the order in which switch contacts are connected does not change the logic operation of the circuit.
eBook - PDFDiscrete Mathematics
Proofs, Structures and Applications, Third Edition
- Rowan Garnier, John Taylor(Authors)
- 2009(Publication Date)
- CRC Press(Publisher)
Chapter 10 Boolean Algebra 10.1 Introduction In chapter 3 we noted the strong similarity between the algebra of sets and that of propositions. In particular, each of the laws listed in §3.5 has a counterpart in §1.5 to which it bears more than a passing resemblance. For example, De Morgan’s laws for the propositions p and q are given by p ∨ q ≡ ¯ p ∧ ¯ q and p ∧ q ≡ ¯ p ∨ ¯ q . For the sets A and B these laws take the form ( A ∪ B ) = ¯ A ∩ ¯ B and ( A ∩ B ) = ¯ A ∪ ¯ B . In this chapter we shall see that the laws common to these two systems are attributable to their relationship to an algebraic structure known as a ‘Boolean algebra’ and that the properties which they share are those which are common to all Boolean algebras. The idea of a Boolean algebra was first developed by George Boole † in the middle of the nineteenth century. Boole was chiefly concerned with the algebra of propositions but, in recent years, the subject has been extended and is now a significant component of abstract algebra. An important application of Boolean algebra is in the analysis of electronic circuits and hence in the design of a range of digital devices such as computers, telephone systems and electronic control systems. † Boole’s book The Laws of Thought published in 1854 was an attempt to formalize the process of logical thinking. 492 Introduction 493 Definition 10.1 A Boolean algebra consists of a set B together with three operations defined on that set. These are: (a) a binary operation denoted by ⊕ referred to as the sum (or join ); (b) a binary operation denoted by * referred to as the product (or meet ); (c) an operation which acts on a single element of B , denoted by ¯ , where, for any element b ∈ B , the element ¯ b ∈ B is called the complement of b . (An operation which acts on a single member of a set S and which results in a member of S is called a unary operation .) The following axioms apply to the set B together with the operations ⊕ , * and ¯ .
eBook - PDF- John Bird(Author)
- 2017(Publication Date)
- Routledge(Publisher)
Chapter 65 Boolean algebra and logic circuits Why it is important to understand: Boolean algebra and logic circuits Logic circuits are the basis for modern digital computer systems; to appreciate how computer systems operate an understanding of digital logic and Boolean algebra is needed. Boolean algebra (named after its developer, George Boole), is the algebra of digital logic circuits all computers use. Boolean algebra is the algebra of binary systems. A logic gate is a physical device implementing a Boolean function, performing a logical operation on one or more logic inputs, and produces a single logic output. Logic gates are implemented using diodes or transistors acting as electronic switches, but can also be constructed using electromagnetic relays, fluidic relays, pneumatic relays, optics, molecules or even mechanical elements. Learning Boolean algebra for logic analysis, learning about gates that process logic signals and learning how to design some smaller logic circuits is clearly of importance to computer engineers.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
