Problems    33
AND and OR gates may have more than two inputs. An AND gate with three inputs 
and an OR gate with four inputs are shown in  Fig.   1.6   . The three‐input AND gate 
responds with logic 1 output if all three inputs are logic 1. The output produces logic 0 
if any input is logic 0. The four‐input OR gate responds with logic 1 if any input is logic 
1; its output becomes logic 0 only when all inputs are logic 0. 
PROBLEMS 
(Answers to problems marked with * appear at the end of the text.)  
 
1.1   List the octal and hexadecimal numbers from 16 to 32. Using A and B for the last two 
digits, list the numbers from 8 to 28 in base 12.   
 
1.2*   What is the exact number of bytes in a system that contains (a) 32K bytes, (b) 64M bytes, 
and (c) 6.4G bytes?   
 
1.3   Convert the following numbers with the indicated bases to decimal: 
(a)   *  (4310) 
5
(b)   *  (198) 
12
(c)   (435) 
8
(d)   (345) 
6
 
1.4   What is the largest binary number that can be expressed with 16 bits? What are the equiv-
alent decimal and hexadecimal numbers?   
 
1.5*   Determine the base of the numbers in each case for the following operations to be correct: 
(a) 14/2 = 5 
(b) 54/4 = 13 
(c) 24 + 17 = 40.   
 
1.6*   The solutions to the quadratic equation  x  
2
- 11x + 22 = 0 are  x  = 3 and  x  = 6. What is the 
base of the numbers?   
x
y
AND: ẋ y
OR: x+ y
NOT: x
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
0
FIGURE 1.5  
Input–output signals for gates       
A
B
C
F= ABC
G= A + B + C + D
A
B
C
D
(a) Three-input AND gate
(b) Four-input OR gate
FIGURE 1.6  
Gates with multiple inputs       
Change pdf to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
change pdf to powerpoint on; pdf picture to powerpoint
Change pdf to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf to powerpoint using; convert pdf to ppt online
34    Chapter 1  Digital Systems and Binary Numbers
 
1.7*   Convert the hexadecimal number 64CD to binary, and then convert it from binary to octal.   
 
1.8   Convert the decimal number 431 to binary in two ways: (a) convert directly to binary; 
(b) convert first to hexadecimal and then from hexadecimal to binary. Which method is faster?   
 
1.9   Express the following numbers in decimal: 
(a)   *  (10110.0101) 
2
(b)   *  (16.5) 
16
(c)  * (26.24) 
8
(d)   (DADA.B) 
16
(e)   (1010.1101) 
2
 
1.10   Convert the following binary numbers to hexadecimal and to decimal: (a) 1.10010, 
(b) 110.010. Explain why the decimal answer in (b) is 4 times that in (a).   
 
1.11   Perform the following division in binary: 111011 ÷ 101.   
 
1.12*   Add and multiply the following numbers without converting them to decimal. 
(a)   Binary numbers 1011 and 101.  
(b)   Hexadecimal numbers 2E and 34.     
 
1.13   Do the following conversion problems: 
(a)   Convert decimal 27.315 to binary.  
 
(b)   Calculate the binary equivalent of 2/3 out to eight places. Then convert from binary to 
decimal. How close is the result to 2/3?  
 
(c)   Convert the binary result in (b) into hexadecimal. Then convert the result to decimal. 
Is the answer the same?     
 
1.14   Obtain the 1’s and 2’s complements of the following binary numbers: 
(a) 00010000 
(b) 00000000
(c) 11011010 
(d) 10101010
(e) 10000101 
(f) 11111111.   
 
1.15   Find the 9’s and the 10’s complement of the following decimal numbers: 
(a) 25,478,036 
(b) 63, 325, 600 
(c)25,000,000 
(d) 00,000,000.   
 
1.16     (a)   Find the 16’s complement of C3DF.  
(b)   Convert C3DF to binary.  
(c)   Find the 2’s complement of the result in (b).  
(d)   Convert the answer in (c) to hexadecimal and compare with the answer in (a).     
 
1.17   Perform subtraction on the given unsigned numbers using the 10’s complement of the 
subtrahend. Where the result should be negative, find its 10’s complement and affix a minus 
sign. Verify your answers. 
(a) 4,637 - 2,579 
(b) 125 - 1,800
(c) 2,043 - 4,361 
(d) 1,631 - 745   
 
1.18   Perform subtraction on the given unsigned binary numbers using the 2’s complement of the 
subtrahend. Where the result should be negative, find its 2’s complement and affix a minus sign. 
(a) 10011 - 10010 
(b) 100010 - 100110
(c) 1001 - 110101 
(d) 101000 - 10101   
 
1.19*   The following decimal numbers are shown in sign‐magnitude form: +9,286 and +801. 
Convert them to signed-10’s‐complement form and perform the following operations 
(note that the sum is +10,627 and requires five digits and a sign). 
(a)   (+9,286) + (+801)     
(b)   (+9,286) + (-801)  
 
(c)   (-9,286) + (+801)     
(d)   (-9,286) + (-801)     
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Then just wait until the conversion from Powerpoint to PDF is complete and download the file.
how to convert pdf to powerpoint on; picture from pdf to powerpoint
RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Able to view and edit PowerPoint rapidly. Convert. Convert PowerPoint to PDF. Convert PowerPoint to HTML5. Convert PowerPoint to Tiff. Convert PowerPoint to Jpeg
pdf to powerpoint; add pdf to powerpoint presentation
Problems    35
 
1.20   Convert decimal +49 and +29 to binary, using the signed‐2’s‐complement representation 
and enough digits to accommodate the numbers. Then perform the binary equivalent of 
(+29) + (-49), (-29) + (+49), and (-29) + (-49). Convert the answers back to decimal and 
verify that they are correct.   
 
1.21   If the numbers (+9,742) 
10
and (+641) 
10
are in signed magnitude format, their sum is (+10,383) 
10
and requires five digits and a sign. Convert the numbers to signed-10’s‐complement form and 
find the following sums: 
(a)   (+9,742) + (+641)     
(b)   (+9,742) + (-641)  
 
(c)   (-9,742) + (+641)     
(d)   (-9,742) + (-641)     
 
1.22   Convert decimal 6,514 to both BCD and ASCII codes. For ASCII, an even parity bit is to 
be appended at the left.   
 
1.23   Represent the unsigned decimal numbers 791 and 658 in BCD, and then show the steps 
necessary to form their sum.   
 
1.24   Formulate a weighted binary code for the decimal digits, using the following weights: 
(a)   *  6, 3, 1, 1  
 
(b)   6, 4, 2, 1     
 
1.25   Represent the decimal number 6,248 in (a) BCD, (b) excess‐3 code, (c) 2421 code, and 
(d) a 6311 code.   
 
1.26   Find the 9’s complement of decimal 6,248 and express it in 2421 code. Show that the result 
is the 1’s complement of the answer to (c) in CR_PROBlem 1.25. This demonstrates that 
the 2421 code is self‐complementing.   
 
1.27   Assign a binary code in some orderly manner to the 52 playing cards. Use the minimum 
number of bits.   
 
1.28   Write the expression “G. Boole” in ASCII, using an eight‐bit code. Include the period and 
the space. Treat the leftmost bit of each character as a parity bit. Each eight‐bit code should 
have odd parity. (George Boole was a 19th‐century mathematician. Boolean algebra, 
introduced in the next chapter, bears his name.)   
 
1.29*   Decode the following ASCII code: 
1010011 1110100 1100101 1110110 1100101 0100000 1001010 1101111 1100010 1110011.   
 
1.30   The following is a string of ASCII characters whose bit patterns have been converted into 
hexadecimal for compactness: 73 F4 E5 76 E5 4A EF 62 73. Of the eight bits in each pair 
of digits, the leftmost is a parity bit. The remaining bits are the ASCII code. 
(a)   Convert the string to bit form and decode the ASCII.  
 
(b)   Determine the parity used: odd or even?     
 
1.31*   How many printing characters are there in ASCII? How many of them are special char-
acters (not letters or numerals)?   
 
1.32*   What bit must be complemented to change an ASCII letter from capital to lowercase and 
vice versa?   
 
1.33*   The state of a 12‐bit register is 100010010111. What is its content if it represents 
(a)   Three decimal digits in BCD?  
 
(b)   Three decimal digits in the excess‐3 code?  
 
(c)   Three decimal digits in the 84‐2‐1 code?  
 
(d)   A binary number?     
C# WinForms Viewer: Load, View, Convert, Annotate and Edit
to PDF; Convert PowerPoint to PDF; Convert Image to PDF; Convert Jpeg to PDF; Merge PDF Files; Split PDF Document; Remove Password from PDF; Change PDF Permission
change pdf to ppt; convert pdf file into ppt
How to C#: Overview of Using XDoc.PowerPoint
How to C#: Overview of Using XDoc.PowerPoint. Overview for How to Use XDoc.PowerPoint in C# .NET Programming Project. PowerPoint Conversion.
how to convert pdf to powerpoint; how to convert pdf to powerpoint slides
36    Chapter 1  Digital Systems and Binary Numbers
 
1.34   List the ASCII code for the 10 decimal digits with an even parity bit in the leftmost 
position.   
 
1.35   By means of a timing diagram similar to  Fig.   1.5   , show the signals of the outputs f and g in 
Fig.   P1.35    as functions of the three inputs a, b, and c. Use all eight possible combinations 
of a, b, and c. 
f
g
abc
FIGURE P1.35        
f
g
a
b
FIGURE P1.36        
 
1.36   By means of a timing diagram similar to  Fig.   1.5   , show the signals of the outputs f and g in 
Fig.   P1.36    as functions of the two inputs a and b. Use all four possible combinations of a 
and b. 
REFERENCES 
  
1. 
C avanagh,  J. J. 1984. Digital Computer Arithmetic. New York: McGraw‐Hill. 
  
2. 
M ano,  M. M. 1988. Computer Engineering: Hardware Design. Englewood Cliffs, NJ: 
Prentice‐Hall. 
 3. 
N elson,  V. P., H. T. N agle,  J. D. I rwin,  and B. D. C arroll . 1997. Digital Logic Circuit 
Analysis and Design. Upper Saddle River, NJ: Prentice Hall. 
 4. 
S chmid,  H. 1974. Decimal Computation. New York: John Wiley. 
 5. 
Katz, R. H. and Borriello, G.  2004. Contemporary Logic Design 2nd ed. Upper Saddle 
River, NJ:  Prentice‐Hall.  
C# HTML5 Viewer: Load, View, Convert, Annotate and Edit PowerPoint
Such as load and view PowerPoint without Microsoft Office software installed, convert PowerPoint to PDF file, Tiff image and HTML file, as well as add
how to convert pdf to powerpoint in; converter pdf to powerpoint
VB.NET PowerPoint: Read, Edit and Process PPTX File
create image on desired PowerPoint slide, merge/split PowerPoint file, change the order of How to convert PowerPoint to PDF, render PowerPoint to SVG
add pdf to powerpoint; how to convert pdf to ppt using
Web Search Topics    37
WEB SEARCH TOPICS 
BCD code  
ASCII  
Storage register  
Binary logic  
BCD addition  
Binary codes  
Binary numbers  
Excess‐3 code      
VB.NET PDF Password Library: add, remove, edit PDF file password
Add password to PDF. Change PDF original password. Remove password from PDF. Set PDF security level. VB: Change and Update PDF Document Password.
convert pdf to editable ppt; how to convert pdf slides to powerpoint
C# powerpoint - Convert PowerPoint to PDF in C#.NET
C# PowerPoint - Convert PowerPoint to PDF in C#.NET. Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint to PDF Conversion Overview.
pdf to ppt converter; how to convert pdf into powerpoint
38
Chapter 2 
Boolean Algebra and Logic Gates 
2.1    INTRODUCTION 
Because binary logic is used in all of today’s digital computers and devices, the cost of 
the circuits that implement it is an important factor addressed by designers—be they 
computer engineers, electrical engineers, or computer scientists. Finding simpler and 
cheaper, but equivalent, realizations of a circuit can reap huge payoffs in reducing the 
overall cost of the design. Mathematical methods that simplify circuits rely primarily on 
Boolean algebra. Therefore, this chapter provides a basic vocabulary and a brief founda-
tion in Boolean algebra that will enable you to optimize simple circuits and to under-
stand the purpose of algorithms used by software tools to optimize complex circuits 
involving millions of logic gates.  
2.2    BASIC DEFINITIONS 
Boolean algebra, like any other deductive mathematical system, may be defined with a 
set of elements, a set of operators, and a number of unproved axioms or postulates. Aset 
of elements is any collection of objects, usually having a common property. If S is a set, 
and x and y are certain objects, then the notation    xHS    means that x is a member of the 
set S and    yxS    means that y is not an element of S. A set with a denumerable number 
of elements is specified by braces:    ={1, 2, 3, 4}    indicates that the elements of set A 
are the numbers 1, 2, 3, and 4. A binary operator defined on a set S of elements is a rule 
that assigns, to each pair of elements from S, a unique element from S. As an example, 
consider the relation    a*bc.    We say that    *    is a binary operator if it specifies a rule 
for finding c from the pair (a, b) and also if    a, bcHS.    However,    *    is not a binary  operator 
if    a, bHS,    and if    cxS    
Section 2.2  Basic Definitions    39
The postulates of a mathematical system form the basic assumptions from which it 
is possible to deduce the rules, theorems, and properties of the system. The most com-
mon postulates used to formulate various algebraic structures are as follows: 
 
1.   Closure. A set S is closed with respect to a binary operator if, for every pair of 
elements of S, the binary operator specifies a rule for obtaining a unique element 
of S. For example, the set of natural numbers    N= {1, 2, 3, 4, c}    is closed with 
respect to the binary operator    +    by the rules of arithmetic addition, since, for any 
abHN,    there is a unique    cHN    such that    a=c.    The set of natural numbers 
is not closed with respect to the binary operator    -    by the rules of arithmetic 
subtraction, because    2 2 - 3= = -1    and 2,    3HN,    but    (-1)xN.     
 
2.   Associative law. A binary operator    *    on a set S is said to be associative whenever 
(x*y)*zx*(y*z) for all x, yz,HS    
 
3.   Commutative law. A binary operator    *    on a set S is said to be commutative when-
ever 
x*y*x for all x, yH    
 
4.   Identity element. A set S is said to have an identity element with respect to a binary 
operation    *    on S if there exists an element    eHS    with the property that 
e*x*ex for every xH   
 Example: The element 0 is an identity element with respect to the binary operator 
+    on the set of integers    ={c, -3, -2, -1, 0, 1, 2, 3,c},    since 
+0 = 0 +x for any xH   
The set of natural numbers, N, has no identity element, since 0 is excluded from the set.  
 
5.   Inverse. A set S having the identity element e with respect to a binary operator    *    
is said to have an inverse whenever, for every    xHS,    there exists an element    yHS    
such that 
x*=e   
Example: In the set of integers, I, and the operator    +,    with    = 0,    the inverse of 
an element a is    (-a),    since    + (-a) = 0.     
 
6.   Distributive law. If    *    and    
#
are two binary operators on a set S   *    is said to be dis-
tributive over    
#
whenever 
x*(y
#
z) = (x*y)
#
(x*z)     
field is an example of an algebraic structure. A field is a set of elements, together with 
two binary operators, each having properties 1 through 5 and both operators combining 
to give property 6. The set of real numbers, together with the binary operators    +    and    
#
,    
40    Chapter 2  Boolean Algebra and Logic Gates
forms the field of real numbers. The field of real numbers is the basis for arithmetic and 
ordinary algebra. The operators and postulates have the following meanings: 
The binary operator    +    defines addition.  
The additive identity is 0.  
The additive inverse defines subtraction.  
The binary operator    
#
defines multiplication.  
The multiplicative identity is 1.  
For      0,    the multiplicative inverse of    =1>a    defines division (i.e.,    a
#
1>= 1   ).  
The only distributive law applicable is that of    
#
over    +:     
a
#
(c) =(a
#
b) + (a
#
c)       
2.3     AXIOMATIC DEFINITION 
OF BOOLEAN ALGEBRA 
In 1854, George Boole developed an algebraic system now called Boolean algebra. In 
1938, Claude E. Shannon introduced a two‐valued Boolean algebra called switching 
algebra that represented the properties of bistable electrical switching circuits. For the 
formal definition of Boolean algebra, we shall employ the postulates formulated by 
E. V. Huntington in 1904. 
Boolean algebra is an algebraic structure defined by a set of elements, B, together 
with two binary operators,    +   and    
#
,    provided that the following (Huntington) postulates 
are satisfied: 
 
1.     (a)   The structure is closed with respect to the operator    +.     
(b)   The structure is closed with respect to the operator    
#
.       
 
2.     (a)    The element 0 is an identity element with respect to    +;    that is,    +0 = 
0+ x.     
(b)   The element 1 is an identity element with respect to    
#
;    that is,    x
#
1 = 1
#
x.       
 
3.     (a)   The structure is commutative with respect to    +;    that is,    x.     
(b)   The structure is commutative with respect to    
#
;    that is,    x
#
=y
#
x.       
 
4.     (a)   The operator    
#
is distributive over    +;    that is,    x
#
(z) =(x
#
y) + (x
#
z).     
(b)   The operator    +    is distributive over    
#
;    that is,    x+ (y
#
z) =(xy)
#
(z).       
 
5.   For every element    xHB,    there exists an element    x′HB    (called the  complementofx
such that (a)    x′= 1   and (b)    x
#
x′= 0.     
 
6.   There exist at least two elements    xyHB    such that     y.      
Comparing Boolean algebra with arithmetic and ordinary algebra (the field of real 
numbers), we note the following differences: 
 
1.   Huntington postulates do not include the associative law. However, this law holds for 
Boolean algebra and can be derived (for both operators) from the other postulates.  
 
2.   The distributive law    of f + over 
#
(i.e.,    + (y
#
z) = (y)
#
(xz)   ) is valid for 
Boolean algebra, but not for ordinary algebra.  
Section 2.3  Axiomatic Definition of Boolean Algebra     41
 
3.   Boolean algebra does not have additive or multiplicative inverses; therefore, there 
are no subtraction or division operations.  
 
4.   Postulate 5 defines an operator called the complement that is not available in 
ordinary algebra.  
 
5.   Ordinary algebra deals with the real numbers, which constitute an infinite set of 
elements. Boolean algebra deals with the as yet undefined set of elements, B, but 
in the two‐valued Boolean algebra defined next (and of interest in our subse-
quent use of that algebra), B is defined as a set with only two elements, 0 and 1.   
Boolean algebra resembles ordinary algebra in some respects. The choice of the 
symbols + and
#
is intentional, to facilitate Boolean algebraic manipulations by persons 
already familiar with ordinary algebra. Although one can use some knowledge from 
ordinary algebra to deal with Boolean algebra, the beginner must be careful not to 
substitute the rules of ordinary algebra where they are not applicable. 
It is important to distinguish between the elements of the set of an algebraic structure 
and the variables of an algebraic system. For example, the elements of the field of real 
numbers are numbers, whereas variables such as a, b, c, etc., used in ordinary algebra, 
are symbols that stand for real numbers. Similarly, in Boolean algebra, one defines the 
elements of the set B, and variables such as xy, and z are merely symbols that represent 
the elements. At this point, it is important to realize that, in order to have a Boolean 
algebra, one must show that 
 
1.   the elements of the set B 
 
2.   the rules of operation for the two binary operators, and  
 
3.   the set of elements, B, together with the two operators, satisfy the six Huntington 
postulates.   
One can formulate many Boolean algebras, depending on the choice of elements of 
B and the rules of operation. In our subsequent work,  we deal only with a two‐valued 
Boolean   algebra  (i.e., a Boolean algebra with only two elements). Two‐valued Boolean 
algebra has applications in set theory (the algebra of classes) and in propositional logic. 
Our interest here is in the application of Boolean algebra to gate‐type circuits commonly 
used in digital devices and computers. 
Two‐Valued Boolean Algebra 
A two‐valued Boolean algebra is defined on a set of two elements,    ={0, 1},    with rules 
for the two binary    operators s + and
#
as shown in the following operator tables (the rule 
for the complement operator is for verification of postulate 5): 
x
x
#
y
 y 
xy
    
x
 0 
 1 
 0 
 1 
42    Chapter 2  Boolean Algebra and Logic Gates
These rules are exactly the same as the AND, OR, and NOT operations, respectively, 
defined in Table 1.8. We must now show that the Huntington postulates are valid for the 
set    B= {0, 1}    and the two binary    operators s + and
#
.    
 
1.   That the structure is closed with respect to the two operators is obvious from the 
tables, since the result of each operation is either 1 or 0 and    1, 0HB.     
 
2.   From the tables, we see that 
(a)      0+ + 0 = 0
0+ 1 = 1+ 0 = 1;     
(b)      1
#
1 = 1
1
#
0 =0
#
1 =0.      
This establishes the two identity elements, 0 for    +    and 1 for    
#
,    as defined by 
postulate 2.  
 
3.   The commutative laws are obvious from the symmetry of the binary operator tables.  
 
4.     (a)   The distributive law    x
#
(yz) = (x
#
y) +(x
#
z)    can be shown to hold from 
the operator tables by forming a truth table of all possible values of xy, and z. For 
each combination, we derive    x
#
(yz)    and show that the value is the same as the 
value of    (x
#
y) + (x
#
z):    
 z
x
#
(yz)
x
#
y
x
#
z
(x
#
y)(x
#
z)
(b)   The distributive law    of f + over
#
can    be shown to hold by means of a truth table 
similar to the one in part (a).    
 
5.   From the complement table, it is easily shown that 
(a)      x′= 1,    since    0+ + 0′= 0+ 1 = 1    and    1+ + 1′= 1 +0 = 1.     
(b)      x
#
x′= 0,    since    0
#
0′= 0
#
1= 0    and    1
#
1′= 1
#
0= 0.      
Thus, postulate 1 is verified.  
 
6.   Postulate 6 is satisfied because the two‐valued Boolean algebra has two elements, 
1 and 0, with    1 1  0.      
We have just established a two‐valued Boolean algebra having a set of two elements, 
1 and 0, two binary operators with rules equivalent to the AND and OR operations, and 
a complement operator equivalent to the NOT operator. Thus, Boolean algebra has been 
defined in a formal mathematical manner and has been shown to be equivalent to the 
binary logic presented heuristically in Section 1.9. The heuristic presentation is helpful 
in understanding the application of Boolean algebra to gate‐type circuits. The formal 
Documents you may be interested
Documents you may be interested