190
Digital Electronics
4. More specifically, Boolean algebra captures the essential properties of both logic operations such
as AND, OR and NOT and set operations such as intersection, union and complement. As an
illustration, the logical assertion that both a statement and its negation cannot be true has a
counterpart in set theory, which says that the intersection of a subset and its complement is a null
(or empty) set.
5. Boolean algebra may also be defined to be a set A supplied with two binary operations of logical
AND (, logical OR (V), a unary operation of logical NOT (¬ and two elements, namely
logical FALSE (0) and logical TRUE (1). This set is such that, for all elements of this set,
the postulates or axioms relating to the associative, commutative, distributive, absorption and
complementation properties of these elements hold good. These postulates are described in the
following pages.
6.1.1 Variables, Literals and Terms in Boolean Expressions
Variables are the different symbols in a Boolean expression. They may take on the value ‘0’ or ‘1’.
For instance, in expression (6.1), A, B and C are the three variables. In expression (6.2), P, Q, R and
S are the variables:
A + AAB + AAC + AABBC
(6.1)
P + QQQQR + SSSSP + Q + RR
(6.2)
The complement of a variable is not considered as a separate variable. Each occurrence of a variable
or its complement is called a literal. In expressions (6.1) and (6.2) there are eight and seven literals
respectively. A term is the expression formed by literals and operations at one level. Expression (6.1)
has five terms including four AND terms and the OR term that combines the first-level AND terms.
6.1.2 Equivalent and Complement of Boolean Expressions
Two given Boolean expressions are said to be equivalent if one of them equals ‘1’ only when the
other equals ‘1’ and also one equals ‘0’ only when the other equals ‘0’. They are said to be the
complement of each other if one expression equals ‘1’ only when the other equals ‘0’, and vice versa.
The complement of a given Boolean expression is obtained by complementing each literal, changing
all ‘.’ to ‘+’ and all ‘+’ to ‘.’, all 0s to 1s and all 1s to 0s. The examples below give some Boolean
expressions and their complements:
Given Boolean expression
AAB + AAB
(6.3)
Corresponding complement
A + BBBBA + BB
(6.4)
Given Boolean expression
A + BBBBA + BB
(6.5)
Digital Electronics
4. More specifically, Boolean algebra captures the essential properties of both logic operations such
as AND, OR and NOT and set operations such as intersection, union and complement. As an
illustration, the logical assertion that both a statement and its negation cannot be true has a
counterpart in set theory, which says that the intersection of a subset and its complement is a null
(or empty) set.
5. Boolean algebra may also be defined to be a set A supplied with two binary operations of logical
AND (, logical OR (V), a unary operation of logical NOT (¬ and two elements, namely
logical FALSE (0) and logical TRUE (1). This set is such that, for all elements of this set,
the postulates or axioms relating to the associative, commutative, distributive, absorption and
complementation properties of these elements hold good. These postulates are described in the
following pages.
6.1.1 Variables, Literals and Terms in Boolean Expressions
Variables are the different symbols in a Boolean expression. They may take on the value ‘0’ or ‘1’.
For instance, in expression (6.1), A, B and C are the three variables. In expression (6.2), P, Q, R and
S are the variables:
A + AAB + AAC + AABBC
(6.1)
P + QQQQR + SSSSP + Q + RR
(6.2)
The complement of a variable is not considered as a separate variable. Each occurrence of a variable
or its complement is called a literal. In expressions (6.1) and (6.2) there are eight and seven literals
respectively. A term is the expression formed by literals and operations at one level. Expression (6.1)
has five terms including four AND terms and the OR term that combines the first-level AND terms.
6.1.2 Equivalent and Complement of Boolean Expressions
Two given Boolean expressions are said to be equivalent if one of them equals ‘1’ only when the
other equals ‘1’ and also one equals ‘0’ only when the other equals ‘0’. They are said to be the
complement of each other if one expression equals ‘1’ only when the other equals ‘0’, and vice versa.
The complement of a given Boolean expression is obtained by complementing each literal, changing
all ‘.’ to ‘+’ and all ‘+’ to ‘.’, all 0s to 1s and all 1s to 0s. The examples below give some Boolean
expressions and their complements:
Given Boolean expression
AAB + AAB
(6.3)
Corresponding complement
A + BBBBA + BB
(6.4)
Given Boolean expression
A + BBBBA + BB
(6.5)