Biomedical Engineering Reference
In-Depth Information
Fig. 1.11
K-map for AND
Function
x
0
1
0
0
0
y
1
0
1
Definition I.4:
A
Karnaugh map
(K-map) is a graphical representation of the truth
table of a function. In a K-map, each square represents a vertex
v
of
B
n
, and the
contents of any vertex is the value. An example of a K-map is shown in Fig.
1.11
.
The K-map in this figure is that of the AND function with two input variables.
D
efinition I.5:
A
literal
or a
literal function
is a
b
inar
y v
ariable
x
or its negation
x
. For example,
x
1
,
x
2
,
...
are variables, while
x
1
,
x
1
,
x
2
,
x
2
,
...
are literals.
Definition I.6:
A
cube
or a
product
is a conjunction (AND) of literals.
Fo
r example,
the cube
xy
is a conjunction of two literal
s
x
and
y
. In the example
x
1
x
2
x
3
, this cube
is a conjunction of the literals
x
1
,
x
2
, and
x
3
.
Defin
iti
on I.7:
A
clause
is a disjunction (
lo
gical OR) containing literals. For
e
xa
m
-
ple, (
x
1
+
x
3
) is a clause with two liter
al
s
x
1
a
n
d
x
3
. Another example is (
x
+
y
+
z
)
which is a clause with three literals
x
,
y
, and
z
.
Definition I.8:
A
Sum of Products
(SOP) expression is a canonical representation
of a function
f
, which consists of a disjunction (OR) of minterms. For example, the
SOP of a 2-input AND gate is
f
AND
=
xy
.
Definition I.9:
A
Product of Sums
(POS) expression is a canonical representation
of a function
f
, which consists of a conjunction (AND) of maxterms. The POS
is the dual of
th
e
SO
P. For example, the POS of a 2-input AND gate is
f
AND
=
(
x
+
y
)
·
(
x
+
y
)
·
(
x
+
y
).
Definition I.10:
A
Conjunctive Normal Form (CNF)
expression
S
consists of a
conjunction (AND) of
m
clauses
c
1
...c
m
. Each clause
c
i
consists of disjunction
(OR) of
k
i
literals. POS is a form of CNF.
Definition I.11:
A
Boolean formula
is a formula that represents a function. The
formula is defined as catenations of:
parentheses (
)
literals (
x
,
y
,
x
,
y
)
Boolean operators (“
+
”) OR
, (“
·
”) AND
complementation (example:
x
+
y
)
Following are three examples of Boolean formulas.
f
=
x
1
·
x
2
+
x
1
+
x
2
g
=
(
x
1
+
x
2
)
·
(
x
1
+
x
2
)
h
=
a
·
(
b
+
c
)
