|
| Boolean
Algebra |
|
|
|
|
|
Boolean algebra |
Definition |
|
Basic
theorems |
|
Boolean
operations on sets |
|
Logic gates and circuits |
|
The
"AND" gate, the "OR" gate and the "NOT"
gate |
|
Binary number system |
|
Binary
to decimal conversion |
|
Decimal
to binary conversion |
|
Binary
addition |
|
The
half adder |
|
The
Binary
addition circuit - the full adder |
|
Binary
subtraction |
|
The
method of subtraction by adding the complement of the subtrahend
applied to decimals |
|
The
method of subtraction by adding the complement of the subtrahend
applied to binary numbers |
|
|
|
|
|
|
| Definition |
| Properties
of both set operations and logic operations are used in an
algebraic structure called a Boolean |
| algebra. |
| A
Boolean algebra is a set A
on which are defined; two binary operations, + (called OR),
·
(called AND), a unary operation, denoted '
(called NOT) and two distinct
elements 0 and 1, such that, for all elements a,
b
and c
of the set A,
the following axioms hold: |
|
| associative
law:
a + (b + c)
=
(a + b) + c
a ·
(b ·
c) = (a ·
b) ·
c |
| commutative
law:
a + b
= b + a
a ·
b = b
·
a |
| distributive
law:
a + (b ·
c) = (a + b) ·
(a + c)
a ·
(b + c) = (a ·
b) +
(a ·
c) |
| identity
law:
a + 0 = a
a ·
1
=
a |
| complement
law:
a + a' = 1
a ·
a' = 0 |
|
| From
these axioms derived are following identities: |
| idempotent
law:
a + a
=
a
a ·
a = a |
| boundedness
law:
a + 1
=
1
a ·
0 = 0 |
| absorption
law:
a + (a ·
b) = a
a ·
(a + b)
=
a |
| involution
law:
( a' )' = a |
| De
Morgan's
laws:
(a + b)'
= a' ·
b'
(a ·
b)' = a' + b' |
| 0
and 1 complements: 0'
=
1
1' = 0 |
|
| Boolean
Operations on Sets |
| Using
noticed coincidence between truth tables and Venn's diagrams we
can prove any of the axioms or |
| theorems of Boolean algebra.
Thus, below is shown the proof of the distributive law: |
|
A
· ( B
+ C
) =
A
· B
+ A
· C
|
| |
A |
B |
C |
B
+ C |
A
·
( B
+ C ) |
| 1 |
0 |
0 |
0 |
0 |
0 |
| 2 |
1 |
0 |
0 |
0 |
0 |
| 3 |
0 |
1 |
0 |
0 |
0 |
| 4 |
0 |
0 |
1 |
1 |
0 |
| 5 |
1 |
1 |
0 |
1 |
1 |
| 6 |
1 |
0 |
1 |
1 |
1 |
| 7 |
0 |
1 |
1 |
1 |
0 |
| 8 |
1 |
1 |
1 |
1 |
1 |
|
| A |
B |
C |
A
·
B |
A
·
C |
A
·
B
+ A
·
C |
| 0 |
0 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
0 |
0 |
0 |
| 0 |
1 |
0 |
0 |
0 |
0 |
| 0 |
0 |
1 |
0 |
0 |
0 |
| 1 |
1 |
0 |
1 |
0 |
1 |
| 1 |
0 |
1 |
0 |
1 |
1 |
| 0 |
1 |
1 |
0 |
0 |
0 |
| 1 |
1 |
1 |
1 |
1 |
1 |
|
|
| Notice
that required Boolean (binary) operations are performed
on the three sets so, in the above tables there are 23 =
8 combinations. In both tables, at the resultant
columns, obtained are ones (1) for the same combinations
of input values of the sets, A,
B
and C,
which correspond with the
three colored areas in the Venn's diagram. |
 |
|
| Using
rules of Boolean algebra each of the eight areas of the
Venn's diagram can be represented as a |
| product involving given
sets, A,
B
and C: |
| 1 |
A'
·
B'
·
C' |
3 |
A'
·
B
·
C' |
5 |
A ·
B
·
C' |
7 |
A'
·
B
·
C |
| 2 |
A
·
B'
·
C' |
4 |
A'
·
B'
·
C |
6 |
A ·
B'
·
C |
8 |
A ·
B
·
C |
|
| In
general, the following rules must always be followed when
evaluating a Boolean expression:
|
| 1.
First, perform all complementations of single terms.
|
|
2. Then perform all operations within parentheses.
|
|
3. Perform an AND operation before an OR operation unless
parentheses indicate otherwise.
|
|
|
Logic
Gates and Circuits |
| There
are exactly three basic electronic circuits called logic gates
each of which correspond to one of the |
| three Boolean (binary) operators, “and,” “or,” and
“not” having the same properties. |
| AND
gate |
| a |
b |
a
·
b |
| 0 |
0 |
0 |
| 1 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
1 |
1 |
|
OR
gate |
| a |
b |
a
+ b |
| 0 |
0 |
0 |
| 1 |
0 |
1 |
| 0 |
1 |
1 |
| 1 |
1 |
1 |
|
NOT gate (or
invertor) |
|
|
|
|
|
|
|
| Logic
circuits used in digital computers are built up from logic
gates. We want to know the output y
of a logic |
|
circuit for all possible combinations of input bits.
The value of the output is shown at the resultant column of |
| the
corresponding truth table. |
|
| Binary
Number System |
| The
binary number system uses digits, 0 and 1 to represent numbers.
A binary number can be therefore |
| represented by any sequence of
bits
(binary digits). |
| The tables
show binary representations of integers from 0 to 19 with corresponding place values of bits. |
| Decimal
number |
Binary
number |
| 24 |
23
|
22 |
21
|
20 |
| 0 |
0 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
0 |
0 |
1 |
| 2 |
0 |
0 |
0 |
1 |
0 |
| 3 |
0 |
0 |
0 |
1 |
1 |
| 4 |
0 |
0 |
1 |
0 |
0 |
| 5 |
0 |
0 |
1 |
0 |
1 |
| 6 |
0 |
0 |
1 |
1 |
0 |
| 7 |
0 |
0 |
1 |
1 |
1 |
| 8 |
0 |
1 |
0 |
0 |
0 |
| 9 |
0 |
1 |
0 |
0 |
1 |
|
|
| Decimal
number |
Binary
number |
| 24 |
23
|
22 |
21
|
20 |
| 10 |
0 |
1 |
0 |
1 |
0 |
| 11 |
0 |
1 |
0 |
1 |
1 |
| 12 |
0 |
1 |
1 |
0 |
0 |
| 13 |
0 |
1 |
1 |
0 |
1 |
| 14 |
0 |
1 |
1 |
1 |
0 |
| 15 |
0 |
1 |
1 |
1 |
1 |
| 16 |
1 |
0 |
0 |
0 |
0 |
| 17 |
1 |
0 |
0 |
0 |
1 |
| 18 |
1 |
0 |
0 |
1 |
0 |
| 19 |
1 |
0 |
0 |
1 |
1 |
|
|
|
| Binary
to decimal conversion: Any binary number can be converted to its
decimal equivalent by writing it |
| in
a place-value notation, i.e. as the sum of products of each
digit and that digit's place value. |
|
| Example: |
1 0 1 1 1 0 1 =
1 · 26 + 0
· 25
+ 1 · 24 + 1 · 23
+ 1 · 22 + 0 ·
21
+ 1 · 20 = |
|
|
= 64 + 0
+ 16 + 8
+ 4 +
0 + 1
= 93 |
|
| Decimal
to binary conversion: |
| To convert a decimal number to its
binary equivalent |
| divide given decimal and each successive
quotient by |
| 2 noting remainders from right to left, i.e., form
the |
| lowest place value to the higher.
The remainders can |
| only be 0 and 1 since divisions are by 2. The
division |
| ends by the quotient
zero |
|
| 113 |
÷ |
2 |
= |
1
1 1 1 0 0 0 1 |
| 56 |
|
|
|
<==== |
| 28 |
|
| 14 |
| 7 |
| 3 |
| 1 |
| 0 |
|
|
| Binary
addition |
| The
binary system works under the same principles as the decimal
system as show basic rules for binary |
| addition: |
| (1) |
|
|
|
0 |
+ |
0 |
= |
|
0 |
|
|
| (2) |
|
|
|
0 |
+ |
1 |
= |
|
1 |
| (3) |
|
|
|
1 |
+ |
0 |
= |
|
1 |
| (4) |
|
|
|
1 |
+ |
1 |
= |
1 |
0 |
(with a carry of
1) |
| (5) |
|
1 |
+ |
1 |
+ |
1 |
= |
1 |
1 |
(with a carry of
1) |
|
or |
| (1) |
(2)
and (3) |
(4) |
(5) |
|
|
|
1 |
|
0 |
1 |
1 |
1 |
| + 0 |
+
0 |
+
1 |
+
1 |
|
0 |
1 |
10 |
11 |
|
|
|
|
|
1 |
1 |
carry |
|
|
1 |
1 |
0 |
1 |
0 |
|
=> |
26 |
|
+ |
1 |
1 |
1 |
0 |
0 |
|
=> |
+ 28 |
|
1 |
1 |
0 |
1 |
1 |
0 |
sum |
54 |
|
When adding two multiple digits numbers a carry
has to be added to the
next higher place value digit.
Thus,
in order to design a logical circuit that
performs a binary addition we should form a truth table with two
columns for binary inputs, a
and b,
and columns
for the outputs, the sum (S) and carry (c). |
|
|
|
| The
half adder |
| |
a |
b |
a´ |
b´ |
a´· b |
a ·
b´ |
carry |
Sum |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
| 2 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
| 3 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
| 4 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
 |
|
|
The above circuit is named a
half adder because it only register a carry as the result of addition of the two binary 1's from the
input (marked with 4).
The circuit which is capable to perform
the addition of three bits (as the column marked with 6 in the right example), i.e., that includes a carry from a previous column, is called a
full adder and is shown below. |
|
|
| |
|
64 |
32 |
16 |
8 |
4 |
2 |
1 |
|
| |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
| |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
a
= 54 |
| |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
b
= 45 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
|
+ c
(carry) |
| |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
S = 99 |
|
|
|
| The
Binary
addition circuit - the full adder |
|
|
|
| Binary
subtraction |
| Computers
perform binary subtraction by adding the minuend (M) and the
complement of the subtrahend |
| (the
number to be subtracted). |
| The
sum of the complement and the given number equals the
corresponding place value (the particular |
| power of the base of a
counting system). |
| The
place values in the binary system are the powers of the base b
= 2, just as the place values in the |
| decimal system are the
powers of ten. |
| Thus,
for example the decimal complement of 79 is 21
since 79 + 21 = 100 = 102. |
| The
binary complement of 79 is 110001(49) since 1001111(79)
+ 110001(49) = 10000000(128) = 27. |
|
| The
method of subtraction by adding the complement of the subtrahend
applied to decimals: |
| Example: |
Calculate the
difference D = A − B,
where A = 423 minuend (M) and B = 79 subtrahend
(S). |
|
| Solution:
423 − 79 =
423 + (100 − 79 −
100) = 423 + 21− 100 = 344,
by using this method we can avoid |
|
subtraction of larger
from smaller digits thus, when calculating the complement of the
subtrahend (CS) we |
| write 100 − 79 =
99 + 1 − 79 = 21. |
|
| The
method of subtraction by adding the complement of the subtrahend
applied to binary numbers: |
|
|
Calculate the
difference D = A − B,
where A = 101000(40) and B = 10111(23). |
|
| The
calculation of the complement, 1000000 −
10111 = 111111 + 1 − 10111 =
101000 + 1 = 101001 (CS) |
| Solution:
101000 −
10111 = 101000
+ (1000000 −10111−1000000) =
101000 + 101001 −
1000000 = 10001 |
| Proof:
the binary complement of 10111(23) is 101001(41)
since 10111(23) + 101001(41) =
1000000(64) = 26. |
| Computers
form the complement in two steps, first invert all bits of the
number by changing all of the ones to |
| zeroes and all of the
zeroes to ones (which is called one's complement). Then, add 1
to the result, thus |
| forming, so called the two's complement of
the given number. |
| Since
computers use fixed-length fields, the complement from above
example is shown in 8 bits: |
|
| 0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
(23) |
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1's
complement |
|
+ |
1 |
|
|
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
2's
complement |
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
(23) |
| + |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
(133)
CS |
|
| 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
=
256 = 28
|
|
|
| Then
by adding the minuend and the complement of the subtrahend
obtained is the difference. |
| Notice that the
leading 1 (overflow), that occurs in the
highest-order bit of the result, equals the
corresponding place value 28
which
must be subtracted from the result as the above
algorithm shows. |
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
Minuend |
| + |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
CS |
|
| 1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Result |
|
|
| Binary
multiplication is the same as repeated binary addition, and
binary division is the repeated process of |
| subtraction, just as
in decimal division. |
|
|
|
|
|
|
|
|
|
|
|
| Beginning
Algebra Contents |
|
 |
|
| Copyright
© 2004 - 2012, Nabla Ltd. All rights reserved. |
