程序代写代做代考 9/5/2018 Boolean Algebra | Alexandria

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 1/18

History

George Boole, born November 2, 1815, Lincoln, Lincolnshire, England,
died December 8, 1864, Ballintemple, County Cork, Ireland

He was an English mathematician who helped establish modern
symbolic logic and whose algebra of logic, now called Boolean algebra,
is basic to the design of digital computer circuits.

(Enciclopaedia Britannica)

Basic Concepts

In Boolean algebra, an expression can only have one of two possible
values: TRUE or FALSE. No other values exist. Therefore, in addition to
many other uses, Boolean Algebra is used to describe digital circuits
that also only have two states for each input or output.

The value TRUE is often represented by 1, while FALSE is represented
by 0.

Unknown date Unknown author

Boolean Algebra

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 2/18

The core operators for Boolean Algebra are just three: AND, OR, and
NOT.

Notation

Various di�erent notations are used to express AND, OR, and NOT. The
following variants are used in FIT1047 and are accepted for exam and
assignments:

A AND B can be written as

A ∧ B or AB

A OR B can be written as

A ∨ B or A+B

NOT A can be written as

A or ¬ A
Although looking quite similar, the 0 and 1 in Boolean Algebra should

not be confused with 0 and 1 in binary numbers. In particular as the
short notation for AND and OR looks like mathematical operations for
addition and multiplication, the behaviour in Boolean Algebra is
di�erent. To help distinguishing Boolean algebra terms from other
mathematical terms, we use capital letters (A.B,C,…).

Binary Boolean

0+0 0 0  (because it is FALSE OR FALSE)

1+1 10 (equals 2) 1  (because it is TRUE OR TRUE)

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 3/18

Boolean Operators

The following paragraphs provide explanations of the concepts of AND,
OR, and NOT. In principle, they are all very similar to the meaning of
the words in natural language. However, there are some subtle
di�erences that needs to be considered when using Boolean Algebra.

AND

A statement A AND B is only TRUE if both individual statements are
TRUE.

AND in Boolean algebra matches our intuitive understanding of the
word “and”.

Using 1 and 0, we can get a very compact representation as a truth
table:

When you look at this truth table, what would be the value of TRUE
AND FALSE?  Reveal
FALSE, of course. Nothing can be true and false at the same time.
Boolean logic is really very “black and white”.

OR

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 4/18

A OR B means that either A or B or both are TRUE

Note that OR in Boolean algebra is slightly di�erent from our usual
understanding of “or”. Very often, the word “or” in natural language
use means that either one or the other is true, but not both. For
example, the sentence “I would like a toast with jam or honey.”
probably does mean that either a toast with jam or a toast with honey is
okay, but not both. In Boolean algebra, the expression would mean that
both together are okay as well.

Truth table for OR:

NOT

By just adding negation, Boolean algebra becomes a quite powerful tool
that can be used to express complex logical statements, policies, or
large digital circuits.

If a statement A is TRUE, then, the negation NOT A is FALSE. If a
statement A is FALSE, then the negation NOT A is TRUE. Thus, negation
just �ips the value of a Boolean algebra statement from TRUE to FALSE
or from FALSE to TRUE.

The truth table of NOT looks like this:

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 5/18

Other operators and gates

In principle, AND, OR, and NOT are su�cient to express everything we
want. However, a few other operators are also frequently used:

XOR is the exclusive or that more resembles our intuitive
understanding of “or”. A XOR B is TRUE if either A is TRUE or B is
TRUE, but not both.

NAND is the negated AND. A NAND B is TRUE only if at least one of
A or B is FALSE.

NOR is the negated OR. A NOR B is TRUE only if both, A and B, are
FALSE.

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 6/18

Can you write the truth table for NOT(A) AND NOT(B)? Which of the
operators above has the same truth table?  Reveal
Indeed, it is exactly the same truth table as NOR, the negated OR. The
Boolean law for this is de Morgans law, which we will see a bit later.

From Boolean algebra to electrical (digital) circuits

In electrical circuits, AND, OR, NOT and additional operators (e.g. XOR,
NAND, NOR) are realised as so-called logic gates.

A gate performs one (or several) logical operations on some logical
input (i.e. bits) and produces a single logical output. We look at these
electrical circuits on an abstract level as “logical circuits”. These logical
circuits do not behave like electrical circuits. This can be a bit
confusing, as a 0 input can result in a 1 output (e.g. when using NOT).
This is the correct behaviour of a logical circuit, but it can contradict
the intuitive understanding that in an electric circuit there can be no
power at the output if there is no power coming in at the input side.
Indeed, a logical gate for NOT only has one input and the negated
output and a 0 input gets “magically” converted to a 1 output. The
reason for this is that in an actual implementation, the NOT gate will
have another input that provides power. Then, the NOT gate is actually

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 7/18

a switch that connects this additional power input to the output if the
actual input is 0. In the idealised notion of logical circuits, these
additional inputs are not shown, as they do not change state.

In logical circuits, the following symbols are used for the di�erent
types of gates.

AND Gate

License: Public Domain

OR Gate

License: Public Domain

NOT Gate

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 8/18

License: Public Domain

A slightly less idealised version of the NOT gate would also show the
additional connections that provide power to the gate:

License: Public Domain

These gates can be combined to create logical circuits for Boolean
functions. The following video explains how to get from a truth table
for a Boolean function to a logical circuit using the three basic gates for
AND, OR, and NOT.

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 9/18

Boolean algebra rules

The term Boolean algebra implies that we might be able to do
arithmetic on symbols. Indeed, there are a number of rules we can use
to manipulate Boolean expressions in symbolic form, quite analogous
to those rules of arithmetic. Some of these laws for Boolean algebra
exist in versions for AND and OR.

Identity Law

Null Law (or Dominance Law)

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 10/18

Idempotent Law

Complement Law

Commutative Law

Associative Law

Distributive Law

Absorption Law

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 11/18

DeMorgans Law

Double Complement Law

Optimization of Boolean functions / K-maps

When realizing a function as circuit, one would like to minimize the
number of gates used for the circuit. Obviously, the di�erent Boolean
laws can be used to derive smaller representations for Boolean
functions. However, determining the correct order of applying the laws
is sometimes di�cult and trying di�erent laws is not very e�cient.  In
addition to having a smaller number of gates, one would also like to
minimize the use of di�erent types of gates. Therefore, normalized
forms for Boolean functions can be useful.

One generic approach for minimizing (smaller) Boolean functions are
Karnaugh maps or K-maps. The idea behind K-maps is to use a
graphical representation to �nd cases where di�erent terms in a
Boolean formular can be combined to one simpler term. The
simpli�cation used in K-maps is based on the following observation. In

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 12/18

both cases, the function is independent from the value of B. Thus, B can
be omitted.

K-maps are best understood by looking at a few examples.

A K-map with 2 variables

As described above, the following function is obviously independent
from B. The example illustrates how this can be derived by using the
graphical method of a K-map. The example uses the short notation
( for   and  for ).

In principle, a K-map is another type of truth table. The values of the
two variables are noted on the top and the side of a table, while the
function’s value for a particular combination of inputs is noted within
the table.

License: Public Domain

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 13/18

Now, the goal is to �nd groups of 1s in the map. Each group of ones that
is not diagonal represents a group of terms that can be combined into
one term. In the small example, there is only one group:

License: Public Domain

This group means that for the value of the function is 1 whatever
the value of B is. Thus, the function can be minimized as follows.

A K-map with 3 variables

While the example with just 2 variables is quite obvious, it gets a bit
less obvious with three variables. Now, the values of two of the
variables are noted at one side and the other variable at the second side.
Note that the order and choice of variables does not matter. The only
important rule is that between two columns (and also two rows) there
can only be one variable that is di�erent. Thus, the order for two
variables needs to be 00, 01, 11, 10. This is di�erent to the order usually
used in truth tables.

This example illustrates the use of K-maps for 3 variables.

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 14/18

We have 5 terms in this function. Thus, we have to place 5 1s into the K-
map:

License: Public Domain

There is one large group with four 1s that is covering the complete
space for A=1.

The remaining 1 seems to stand alone. Nevertheless, we can �nd a
group by wrapping round to the other side of the table. This group
covers two 1s for the area that is valid for C=1 and B=0. Thus, this group
is independent from A.

License: Public Domain

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 15/18

The minimized function now has only two terms representing the two
groups in the K-map.

Rules for K-maps

Rule 1: No group can contain a zero.

License: Public Domain

Rule 2: Groups may be horizontal/vertical/square, but never diagonal.

License: Public Domain

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 16/18

Rule 3: Groups must contain 1,2,4,8,16,32,… (powers of 2).

License: Public Domain

Rule 4: Each group must be as large as possible.

Rule 5: Groups can overlap.

Rule 6: Each 1 must be part of at least one group.

License: Public Domain

Rule 7: Groups may wrap around the map.

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 17/18

License: Public Domain

Universal gates

NAND has special properties:

NAND can be physically implemented very e�ciently.
All other gates can be build only using NAND gates.

Thus, all logical circuits can be implemented using hardware with just a
single type of gates. The same holds for NOR. Therefore, NAND and
NOR are also called universal gates.

The symbol for a NAND gate is this:

License: Public Domain

If NAND is negated, obviously the result is just AND. Thus, if we can
realize NOT and OR with NAND, all three basic gates can be
implemented just using NAND gates. The following circuits show how
NOT and OR can be implemented just using NAND gates. Coorectness of
these circuits is easily checked using truth tables.

9/5/2018 Boolean Algebra | Alexandria

https://www.alexandriarepository.org/module/boolean-algebra-3/ 18/18

Imlpementation of a NOT gate using NAND

License: Public Domain

Implementation of an OR gate using NAND

Viewed using Just Read

https://justread.link/