Boolean Algebra and logic Gates Flashcards
Set
A set of elements is a collection of objects having common property.
How can we define Boolean Algebra?
may be defined with a
set of elements, a set of operators, and a number of unproved axioms or postulates
What is a binary operator defined on a set of elements?
It’s a rule that assigns every pair of element S, a unique element from S.
Closure
A set S is closed with respect to a binary operator if the operation on every pair of S results in a unique element of S .
Associative Law:
A binary operator * on a set S is said to be associative whenever
(x * y) * z = x * (y * z) for all x, y, z, belong to S
Commutative law:
A binary operator * on a set S is said to be commutative whenever
x * y = y * x for all x, y belong to S
Identity element:
A set S is said to have an identity element with respect to a binary
operation * on S if there exists an element e belongs to S with the property that
e * x = x * e = x for every x belongs to S
Inverse:
A set S having the identity element e with respect to a binary operator *
is said to have an inverse whenever for every x belong to S, there exists an element y belong to S
such that
x * y = e
Distributive law:
If * and # are two binary operators on a set S, * is said to be distributive over # whenever
x * (y # z) = (x * y) # (x * z)
Field
algebraic structure,
A field is a set of elements, together with
two binary operators, each having properties 1 through 5 and both operators combining
to give property 6
x + (y # z) = (x + y) # (x + z)
# is .
talk about fields:
In the field of real numbers + is not distributive over ., but . is over +.
This is Boolean Algebra.
Huntington postulates:
verify it for two-valued boolean algebra: b = {0,1}
- (a) The structure is closed with respect to the operator +.
(b) The structure is closed with respect to the operator # . - (a) The element 0 is an identity element with respect to +; that is, x + 0 =
0 + x = x.
(b) The element 1 is an identity element with respect to . ; that is, x . 1 = 1 . x = x - (a) The structure is commutative with respect to +; that is, x + y = y + x.
(b) The structure is commutative with respect to # ; that is, x . y = y . x - (a) The operator . is distributive over +; that is, x . (y + z) = (x . y) + (x . z)
(b) The operator + is distributive over . ; that is, x + (y .z) = (x + y) . (x + z) - For every element x H B, there exists an element x‘H B (called the complement of x)
such that (a) x + x’ = 1 and (b) x # x’ = 0. - There exist at least two elements x, y H B such that x =! y.
H = belongs to.# = ‘ . ‘
Subtraction and division in Boolean Algebra.
and another difference in Real numbers field n boolean algebra?
Boolean algebra does not have additive or multiplicative inverses; therefore, there
are no subtraction or division operations.
- Bool has complements, ordinary alg doesn’t.
- Ordinary algebra deals with the real numbers, which constitute an infinite set of
elements. Boolean algebra deals with the as yet undefined set of elements, B, but
in the two‐valued Boolean algebra defined next (and of interest in our subsequent use of that algebra), B is defined as a set with only two elements, 0 and 1.
duality principle:
states that every algebraic expression deducible from
the postulates of Boolean algebra remains valid if the operators and identity elements
are interchanged
Basic Theorems and postulates:
Postulate 2 (a) x + 0 = x (b) x # 1 = x
Postulate 5 (a) x + x’ = 1 (b) x # x’ = 0
Theorem 1 (a) x + x = x (b) x # x = x
Theorem 2 (a) x + 1 = 1 (b) x # 0 = 0
Theorem 3, involution (x’)’ = x
Postulate 3, commutative (a) x + y = y + x (b) xy = yx
Theorem 4, associative (a) x + (y + z) = (x + y) + z (b) x(yz) = (xy)z
Postulate 4, distributive (a) x(y + z) = xy + xz (b) x + yz = (x + y)(x + z)
Theorem 5, DeMorgan (a) (x + y)’ = x’ y’ (b) (xy)’ = x’ + y’
Theorem 6, absorption (a) x + xy = x (b) x(x + y) = x
Proof by duality
Note that Theorem 1(b) is the dual of theorem 1(a) and that each step of the proof
in part (b) is the dual of its counterpart in part (a). Any dual theorem can be similarly
derived from the proof of its corresponding theorem.
Operator precedence
parenthesis then Not then And then OR
Boolean Functions
A Boolean function described by an algebraic expression consists of binary variables, the
constants 0 and 1, and the logic operation symbols. For a given value of the binary variables,
the function can be equal to either 1 or 0.
F1 = x + yz
literal
We define a literal to
be a single variable within a term, in complemented or uncomplemented form.
How to look at ( link between) boolean function in algebraic expression form and in its circuit form?
each term requires a gate
and each variable within the term designates an input to the gate.
While simplifying the boolean function:
- manipulate to make use of absorption law, like 1 can be (x + ~x) or 0 = x(~x)
- sum of 4 terms. each term product of 2 literals : distributive? and if total 8 literals then form (x +y)(z +p)
- Scan through all the theorems and postulates.
consensus theorem
1. xy + x'z + yz = xy + x'z + yz(x + x') = xy + x'z + xyz + x'yz = xy(1 + z) + x'z(1 + y) = xy + x'z. what is 2. (x + y)(x' + z)(y + z)?
(x + y)(x’ + z)(y + z) = (x + y)(x’ + z), by duality from prev function.
The complement of a function:
- Use demorgans law:
The generalized form of DeMorgan’s theorems states that the complement of a function is obtained by interchanging AND and OR operators and complementing each
literal. - using duality principle:
A simpler procedure for deriving the complement of a function is to take the dual of
the function and complement each literal. This method follows from the generalized
forms of DeMorgan’s theorems. Remember that the dual of a function is obtained from
the interchange of AND and OR operators and 1’s and 0’s.
Minterm or Standard product.
A binary variable may appear either in its normal form (x) or in its complement form (x).
Now consider two binary variables x and y combined with an AND operation. Since each
variable may appear in either form, there are four possible combinations: xy, x’y, xy’,x’y’.
Each of these four AND terms is called a minterm, or a standard product.
maxterms, or standard sums:
In a similar fashion, n variables forming an OR term, with each variable being primed
or unprimed, provide 2^n possible combinations, called maxterms, or standard sums.
each minterm or maxterm must contain, by definition,
all the variables, either complemented or uncomplemented.
Minterm and maxterm relation:
each maxterm is the complement of its corresponding minterm and vice versa.
each maxterm is obtained from an OR term of the n variables, with
each variable being unprimed if the corresponding bit is a 0 and primed if a 1, for minterms its the opp version.
Canonical Form
Boolean functions
expressed as a sum of minterms or product of maxterms are said to be in canonical form.
A Boolean function can be expressed algebraically from a given truth table by:
and its complement too
1.forming a minterm for each combination of the variables that produces a 1 in the function
and then taking the OR of all those terms.
—————————————————————————
2. Form a maxterm for each combination of the variables that produces
a 0 in the function, and then form the AND of all those maxterms
—————————————————————————
the complement of a Boolean function: It may be read from the truth
table by forming a minterm for each combination that produces a 0 in the function and
then ORing those terms
With n variables how many minterms?
2 raise to n
With n variables how many total functions can be formed?
(2 ^ (2 ^n))
book printed : 2^(2n)
Sum of minterms:
The minterms whose
sum defines the Boolean function are those which give the 1’s of the function in a Truth table.
Steps to express any function in Sum of minterms:
2 ways
- first expanding the expression into a sum of AND terms
- Each term is then inspected to see if it contains all the
variables. If it misses one or more variables, it is ANDed with an expression such as
x + x’ , where x is one of the missing variables.
OR ————————————————————————–
An alternative procedure for deriving the minterms of a Boolean function is to obtain
the truth table of the function directly from the algebraic expression and then read the
minterms from the truth table.
Brief notation when a Boolean function is in its sum‐of‐minterms form
F(A, B, C) = ∑ (1, 4, 5, 6, 7)
when F = m1 + m4 + m5 + m6 + m7
Product of Maxterms:
its the product of the max terms who give 0’s value in truth table.
Steps to express any function in Product of maxterms:
- first bring the function into a form of OR terms. This may be done by using the distributive law,
x + yz = (x + y)(x + z). - Then any missing variable x in each OR term is ORed with xx’
Express the Boolean function F = xy + x’z as a product of maxterms
First, convert
the function into OR terms by using the distributive law:
F = xy + x’z = (xy + x’)(xy + z)
= (x + x’)(y + x’)(x + z)(y + z)
= (x’ + y)(x + z)(y + z)
The function has three variables: x, y, and z. Each OR term is missing one variable;
therefore,
x’+ y = x’+ y + zz’ = (x’+ y + z)(x’+ y + z’)
x + z = x + z + yy’ = (x + y + z)(x + y’+ z)
y + z = y + z + xx’ = (x + y + z)(x’+ y + z)
Combining all the terms and removing those which appear more than once, we finally
obtain
F = (x + y + z)(x + y + z)(x + y + z)(x + y + z)
= M0M2M4M5
A convenient way to express product of maxterms function is as follows:
F(x, y, z) = ∏(0, 2, 4, 5)
