tag:blogger.com,1999:blog-76004031939100836272024-03-12T21:02:37.070-07:00Digital logic DesignAnonymoushttp://www.blogger.com/profile/14325535332830106182noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-7600403193910083627.post-85286477209606759232012-07-10T08:49:00.001-07:002012-07-10T08:49:21.265-07:00Postulates (continued)<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
– Inverse. For a set with an identity element with respect to a<br />
binary operation, the set is said to have an inverse if for every<br />
element of the set the following property holds:<br />
» x * y = e<br />
• The additive inverse of element a is –a and it defines<br />
subtraction, since a + (–a) = 0. Multiplicative inverse of<br />
a is 1/a and defines division, since a.1/a = 1<br />
– Distributive Law. * is said to be distributive over . when<br />
» x * ( y · z) = (x * y) · (x * z)<br />
– Note: * + and . are binary operators. Binary operator + defines<br />
addition and binary operator . defines multiplication<br />
• Two-value Boolean algebra is defined by the:<br />
– The set of two elements B={0, 1}<br />
– The operators of AND (·) and OR (+)<br />
– Huntington Postulates are satisfied<br />
<b><u>Huntington Postulates:</u></b><br />
<br />
Boolean algebra is an algebraic structure defined by a set<br />
of elements, B , together with two binary operators, + and .<br />
, provided that the following (Huntington) postulates are<br />
satisfied:<br />
1. Closure.<br />
a) with respect to the binary operation OR (+); c=x+y<br />
b)with respect to the binary operation AND (·); c=x.y<br />
2. Identity.<br />
a) with respect to OR (+) is 0:<br />
x + 0 = 0 + x = x, for x = 1 or x = 0<br />
b)with respect to AND (·) is 1:<br />
x · 1 = 1 · x = x, for x = 1 or x =0<br />
3. Commutative Law.<br />
a) With respect to OR (+):<br />
x + y = y + x<br />
b)With respect to AND (·):<br />
x · y = y · x<br />
<br />
4C.Doistnribtuitinveu Leawd.…<br />
a) with respect to the binary operation OR (+):<br />
x + (y · z) = (x + y) · (x + z) + is distributive over .<br />
b)with respect to the binary operation AND (·):<br />
x · (y + z) = (x · y) + (x · z) . is distributive over +<br />
5.Complement. For every element x, that belongs to B, there also<br />
exists an element x’ (complement of x) such that:<br />
a) x + x’ = 1, for x = 1 or x = 0<br />
b)x · x’ = 0 , for x = 1 or x = 0<br />
6. Membership.<br />
There exists at least two elements, x and y, of the set such that<br />
x ≠ y.<br />
0 ≠ 1<br />
<b><u>Notes on Huntington Postulate </u></b><br />
<br />
Comparing Boolean algebra with arithmetic and ordinary<br />
algebra, we note the following differences:<br />
• The associative law is not listed but it can be derived from<br />
the existing postulates for both + and . operations.<br />
• The distributive law of + over . i.e.,<br />
x+(y . z) = (x + y) . (x + z)<br />
is valid for Boolean algebra but not for ordinary algebra.<br />
• Boolean algebra doesn’t have inverses (additive or<br />
multiplicative) therefore there are no operations related to<br />
subtraction or division.<br />
• Postulate 5 defines an operator called complement that is<br />
not available in ordinary algebra.<br />
• Boolean algebra deals with only two elements, 0 and 1<br />
<br />
<br />
<br />
</div>Anonymoushttp://www.blogger.com/profile/14325535332830106182noreply@blogger.com0tag:blogger.com,1999:blog-7600403193910083627.post-30702428677268962852012-07-10T08:45:00.002-07:002012-07-10T08:45:43.382-07:00Boolean Algebra<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<b><u><span style="background-color: white;">Boolean</span> Algebra:</u></b><br />
• Boolean algebra is the basic mathematics needed<br />
for the study of logic design of digital systems.<br />
• In 1854, George Boole an English mathematician<br />
gave the concept of “Logical algebra” known<br />
today as Boolean algebra.<br />
• Boolean algebra is a convenient and systematic<br />
way of expressing and analyzing the operation of<br />
logic circuits.<br />
• Claude Shannon was the first to apply Boole’s<br />
work to the analysis of relays and switching<br />
circuits in 1938.was Other Logic Operations<br />
• In 1904, Huntington gave a set of postulates that<br />
form the basis of formal definition of Boolean<br />
algebra.<br />
<b><u>Set Notations:</u></b><br />
<br />
Mathematical systems can be defined with:<br />
– A set of elements; A set of elements is any collection of<br />
objects having a common property.<br />
– A set of operators; A binary operator defined on a set S of<br />
elements is a rule that assigns to each pair of elements from<br />
S a unique element from S.<br />
– A number of unproved axioms or postulates that form the<br />
basic assumptions from which it is possible to deduce the<br />
rules, theorems and properties of the system.<br />
• The following notations are being used in this class:<br />
– <span style="background-color: white;"> </span><span style="background-color: white;">x∈S </span><span style="background-color: white;">indicates that x is an element of the set S.</span><br />
– <span style="background-color: white;">y ∉ S</span><span style="background-color: white;"> indicates that y is not an element of the set S.</span><br />
<br />
<br />
– <span style="background-color: white;">A</span><span style="background-color: white;"> = {1, 2, 3, 4} indicates that set A exists with a finite number</span><br />
of elements (1, 2, 3, 4).<br />
<b><u>Basic Postulates:</u></b><br />
<br />
The basic postulates of a mathematical system are:<br />
– Closure. A set S is closed w.r.t a binary operator if this operation<br />
only produces results that are within the set of elements defined by<br />
the system.<br />
– Associative Law. A binary operator is said to be associative when:<br />
» (x * y) * z = x * (y * z)<br />
– Commutative Law. A binary operator is said to be commutative<br />
when:<br />
» x * y = y * x<br />
– Identity Element. A set is said to have an identity element with<br />
respect to a binary operation if there exists an element, e, that is a<br />
member of the set with the property:<br />
» e * x = x * e = x for every element of the set<br />
• Additive identity is 0 and multiplicative identity is 1<br />
– Note: * + and . are binary operators<br />
<br />
<br />
</div>Anonymoushttp://www.blogger.com/profile/14325535332830106182noreply@blogger.com0tag:blogger.com,1999:blog-7600403193910083627.post-53623849498886494732012-07-10T08:39:00.002-07:002012-07-10T08:39:38.860-07:00Complements<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Complements are used to simplify subtraction<br />
operations. We do subtraction by adding.<br />
A – B = A+ (-B)<br />
• There are two types:<br />
– The radix complement, called the r’s complement.<br />
– The diminished radix complement, called the (r-1)’s complement.<br />
<b><u>Diminished Radix Complement:</u></b><br />
<br />
Given a number N in base r having n digits, the (r-1)’s<br />
complement of N is defined as:<br />
(rn – 1) – N<br />
• Decimal numbers are in base-10.<br />
(r-1) = (10-1) = 9.<br />
• The 9’s complement would be defined as:<br />
(10n – 1) – N<br />
• So, to determine the 9’s complement of 52:<br />
(102 – 1) – 52 = 47<br />
• Another example is to determine the 9’s complement<br />
of 3124:<br />
(104 – 1) – 3124 = 6875<br />
<u><b>Finding Diminished Radix complement:</b></u><br />
<br />
The DRC or (r-1)’s complement of decimal number is<br />
obtained by subtracting each digit from 9<br />
• The (r-1)’s complement of octal or hexadecimal<br />
number is obtained by subtracting each digit from 7 or<br />
F, respectively<br />
• The DRC (1’s complement) of a binary number is<br />
obtained by subtracting each digit from 1. It can also<br />
be formed by changing 1’s to 0’s and 0’s to 1’s<br />
<b><u>DRC for Binary Numbers:</u></b><br />
<br />
For binary numbers r = 2 and (r-1) = 1. So, the 1’s<br />
complement would be defined as:<br />
(2n – 1) – N<br />
• To determine the 1’s complement of 1000101:<br />
(27 – 1) – 1000101 = 0111010<br />
• To determine the 1’s complement of 11110111101:<br />
(211 – 1) - 11110111101 = 00001000010<br />
• Note that 1’s complement can be done by switching<br />
all 0’s to 1’s and 1’s to 0’s.<br />
<b><u>r's Complement</u></b><br />
<br />
• The r’s complement of an n-digit number N in base-r is<br />
defined as:<br />
rn – N - for N ≠ 0<br />
0 -for N = 0<br />
• We may obtain r’s complement by adding 1 to (r-1)’s<br />
complement. Since rn – N = [(rn – 1) – N]+1<br />
• 10’s complement of 3229 is:<br />
104 – 3229 = 6771<br />
• 2’s complement of 101101 is:<br />
26 – 101101 = 010011<br />
• Note that to determine 2’s complement, leave the least<br />
significant 0’s and the first 1 unchanged and then<br />
switch the remaining 1’s to 0’ and 0’s to 1’s.<br />
<br />
<br />
<br />
<br />
</div>Anonymoushttp://www.blogger.com/profile/14325535332830106182noreply@blogger.com0tag:blogger.com,1999:blog-7600403193910083627.post-54171763100515208622012-07-10T08:32:00.002-07:002012-07-10T08:32:26.516-07:00Different Base systems<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<u>Binary Numbers:</u><br />
The binary system contains only two values in the<br />
allowed coefficients (0 and 1).<br />
• The binary system uses powers of 2 as the<br />
multipliers for the coefficients.<br />
• For example, we can represent the binary number<br />
10111.01 as:<br />
– 1 X 24 + 0 X 23 + 1 X 22 + 1 X 21 + 1 X 20 + 0 X 2-1 + 1 X 2-2 = 23.25<br />
<u>Octal Numbers:</u><br />
<br />
The octal number system is a base-8 system that<br />
contains the coefficient values of 0 to 7.<br />
• The octal system uses powers of 8 as the multipliers<br />
for the coefficients.<br />
• For example, we can represent the octal number<br />
72032 as:<br />
7 X 84 + 2 X 83 + 0 X 82 + 3 X 81 + 2 X 80 = (29722)10<br />
<u>Hexadecimal Numbers:</u><br />
<br />
The hexadecimal number system is a base-16 system<br />
that contains the coefficient values of 0 to 9 and A to<br />
F. The letters A through F represent the coefficient<br />
values of 10, 11, 12, 13, 14, and 15, respectively.<br />
• The hexadecimal system uses powers of 16 as the<br />
multipliers for the coefficients.<br />
• For example, we can represent the hexadecimal<br />
number C34D as:<br />
– 12 X 163 + 3 X 162 + 4 X 161 + 13 X 160 = (49997)10<br />
<u>Conversion From any base to Decimal:</u><br />
<br />
Conversion of a number in base r to decimal is done<br />
by expanding the number in a power series and<br />
adding all the terms.<br />
• For example, (C34D)16 is converted to decimal:<br />
12 X 163 + 3 X 162 + 4 X 161 + 13 X 160 = (49997)10<br />
• (11010.11)2 is converted to decimal:<br />
1 X 24 + 1 X 23 + 0 X 22 + 1 X 21 + 0 X 20 + 1 X 2-1 + 1 X 2-2 = 26.75<br />
<br />
<br />
<br />
<br />
<br />
</div>Anonymoushttp://www.blogger.com/profile/14325535332830106182noreply@blogger.com2