Boolean Algebra and logic Gates Flashcards
1
Q
Set
A
A set of elements is a collection of objects having common property.
2
Q
How can we define Boolean Algebra?
A
may be defined with a
set of elements, a set of operators, and a number of unproved axioms or postulates
3
Q
What is a binary operator defined on a set of elements?
A
It’s a rule that assigns every pair of element S, a unique element from S.
4
Q
Closure
A
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 .
5
Q
Associative Law:
A
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
6
Q
Commutative law:
A
A binary operator * on a set S is said to be commutative whenever
x * y = y * x for all x, y belong to S
7
Q
Identity element:
A
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
8
Q
Inverse:
A
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
9
Q
Distributive law:
A
If * and # are two binary operators on a set S, * is said to be distributive over # whenever
x * (y # z) = (x * y) # (x * z)
10
Q
Field
A
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
11
Q
x + (y # z) = (x + y) # (x + z)
# is .
talk about fields:
A
In the field of real numbers + is not distributive over ., but . is over +.
This is Boolean Algebra.
12
Q
Huntington postulates:
verify it for two-valued boolean algebra: b = {0,1}
A
- (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.# = ‘ . ‘
13
Q
Subtraction and division in Boolean Algebra.
and another difference in Real numbers field n boolean algebra?
A
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.
14
Q
duality principle:
A
states that every algebraic expression deducible from
the postulates of Boolean algebra remains valid if the operators and identity elements
are interchanged
15
Q
Basic Theorems and postulates:
A
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
16
Q
Proof by duality
A
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.
17
Q
Operator precedence
A
parenthesis then Not then And then OR
18
Q
Boolean Functions
A
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
19
Q
literal
A
We define a literal to
be a single variable within a term, in complemented or uncomplemented form.
20
Q
How to look at ( link between) boolean function in algebraic expression form and in its circuit form?
A
each term requires a gate
and each variable within the term designates an input to the gate.
21
Q
While simplifying the boolean function:
A
- 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.
22
Q
consensus theorem
A
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.
23
Q
The complement of a function:
A
- 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.
24
Q
Minterm or Standard product.
A
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.
25
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.
26
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.
27
Canonical Form
Boolean functions
| expressed as a sum of minterms or product of maxterms are said to be in canonical form.
28
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
29
With n variables how many minterms?
2 raise to n
30
With n variables how many total functions can be formed?
(2 ^ (2 ^n))
book printed : 2^(2n)
31
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.
32
Steps to express any function in Sum of minterms:
| 2 ways
1. first expanding the expression into a sum of AND terms
2. 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.
33
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
34
Product of Maxterms:
its the product of the max terms who give 0's value in truth table.
35
Steps to express any function in Product of maxterms:
1. 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).
2. Then any missing variable x in each OR term is ORed with xx'
36
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
37
A convenient way to express product of maxterms function is as follows:
F(x, y, z) = ∏(0, 2, 4, 5)
38
Conversion between Canonical form:
To convert from one canonical
form to another, interchange the symbols ∑ and ∏ and list those numbers missing from
the original form.
for n binary variables we have 2^n terms.
39
What are two standard forms, just name them:
| and how is it diff than canonical form:
1. Sum of products
2. Product of sums
In this configuration,
the terms that form the function may contain one, two, or any number of literals
This standard type of expression
results in a two‐level structure of gates
40
Sum Of products definition:
The sum of products is a Boolean expression containing AND terms, called product
terms, with one or more literals each. The sum denotes the ORing of these terms.
41
SOP logic diagram:
consists of a group of AND gates
followed by a single OR gate.
. Each
product term requires an AND gate, except for a term with a single literal. The logic sum
is formed with an OR gate whose inputs are the outputs of the AND gates and the
single literal. It is assumed that the input variables are directly available in their complements, so inverters are not included in the diagram. This circuit configuration is referred
to as a two‐level implementation.
42
Product Of Sums definition:
A product of sums is a Boolean expression containing OR terms, called sum terms.
Each term may have any number of literals. The product denotes the ANDing of these
terms
43
Gate structure of POS:
The gate structure of the product‐of‐sums
expression consists of a group of OR gates for the sum terms (except for a single literal),
followed by an AND gate,
44
Why prefer 2 level implementation?
| When is it not practical?
a two‐level
implementation is preferred because it produces the least amount of delay through the
gates when the signal propagates from the inputs to the output. However, the number
of inputs to a given gate might not be practical.
45
Boolean Expressions for the 16 Functions of Two Variables
OTHER LOGIC OPERATORS:
F0 = 0 ; Null; Binary constant 0
F1 = xy ; x.y AND; x and y
F2 = xy' ; x/y; Inhibition; x,but not y
F3 = x ; Transfer; x
F4 = x'y ; y/x; Inhibition; y, but not x
F5 = y; Transfer; y
F6 =xy'+x'y ; x⊕y; Exclusive‐OR; x or y, but not both
F7 = x + y; x + y; OR ; x or y
F8 = (x + y); x ↆy; NOR; Not‐OR
F9 = xy + x'y'; (x⊕y)'; Equivalence; x equals y
F10 = y' ; y' ; Complement; Not y
F11 = x + y' ; x ⊂ y; Implication; If y, then x
F12 = x'; x' ; Complement; Not x
F13 = x'+ y; x ⊃ y; Implication; If x, then y
F14 = (xy)' ; x↑y; NAND; Not‐AND
F15 = 1; Identity; Binary constant 1
46
Symbolism for and &; XOR:
The symbol ˆ is also used to indicate the exclusive or operator, e.g., xˆy. The symbol for the AND function is
sometimes omitted from the product of two variables, e.g., xy.
47
Transfer function:
A function that is equal to an
input variable has been given the name transfer, because the variable x or y is transferred
through the gate that forms the function without changing its value.
48
binary difference operator
XOR
49
Equivalence
Equivalence is a function that is 1 when the two binary variables are equal (i.e., when both
are 0 or both are 1). The exclusive‐OR and equivalence functions are the complements of each other.
equivalence function is called
exclusive‐NOR, abbreviated XNOR.
50
Factors to be
| weighed in considering the construction of other types of logic gates are
(1) the feasibility and economy of producing the gate with physical components,
(2) the possibility of
extending the gate to more than two inputs,
(3) the basic properties of the binary operator, such as commutativity and associativity.
(4) the ability of the gate to implement
Boolean functions alone or in conjunction with other gates.
51
Logic gates
| what represents the complement in a graphic symbol?
The small circle in the output of the graphic symbol of an inverter
(referred to as a bubble) designates the logic complement.
52
Buffer Circuit:
The triangle symbol by itself
designates a buffer circuit. A buffer produces the transfer function, but does not produce
a logic operation, since the binary value of the output is equal to the binary value of the
input.
53
power amplification of the signal Circuit:
This circuit is used for power amplification of the signal and is equivalent to two
inverters connected in cascade.
54
Why NAND &; NOR gates are used extensively as standard logic
gates?
This is because
NAND and NOR gates are easily constructed with transistor circuits and because digital
circuits can be easily implemented with them.
55
Recall the graphics, truth table for various operators. total 8
```
AND
OR
NOT
BUFFER
NAND
NOR
XOR
XNOR
```
56
Odd Function
gives one for odd number of 1s.
| Ex : XOR
57
Requirements for the extension to multiple inputs:
A gate can be extended to have multiple inputs if the binary
| operation it represents is commutative and associative.
58
How is it made possible?
| Nand & Nor extended to multiple inputs.?
definition of the operation is modified
slightly. (T = nor)
The difficulty is that the NAND and NOR operators are not associative
(i.e., (x T y) T z x T (y T z) ), as shown in Fig. 2.6 and the following equations:
(x T y) T z = [(x + y)' + z]' = (x + y)z' = xz' + yz'
x T (y T z) = [x + (y + z)']' = x'(y + z) = x'y + x'z
To overcome this difficulty, we define the multiple NOR (or NAND) gate as a
complemented OR (or AND) gate. Thus, by definition, we have
x T y T z = (x + y + z)'
x ↑ y ↑ z = (xyz)'
59
Exclusive OR extended to multiple inputs:
the definition of the function must
be modified when extended to more than two variables. Exclusive‐OR is an odd function
(i.e., it is equal to 1 if the input variables have an odd number of 1’s).
- This function is normally
implemented by cascading two‐input gates
-The truth table in clearly
indicates that the output F is equal to 1 if only one input is equal to 1 or if all three inputs
are equal to 1 (i.e., when the total number of 1’s in the input variables is odd).
60
Positive and negative logic:
Choosing the high‐level H to represent logic 1 defines
a positive logic system. Choosing the low‐level L to represent logic 1 defines a negative
logic system.
61
Polarity graphic symbol:
The small triangles in the inputs and output designate a polarity indicator, the presence of which along a terminal signifies that
negative logic is assumed for the signal
62
the same physical gate
1. under positive logic acts like what?
2. under negative logic acts as what?
the same physical gate can operate either
as a positive‐logic AND gate
or as a negative‐logic OR gate.
63
Conversion from positive to negative logic and vice versa?
It is essentially
an operation that changes 1’s to 0’s and 0’s to 1’s in both the inputs and the output
of a gate. Since this operation produces the dual of a function, the change of all terminals from one polarity to the other results in taking the dual of the function.
64
Integrated Circuit
An integrated circuit (IC) is fabricated on a die of a silicon semiconductor crystal, called
a chip, containing the electronic components for constructing digital gates
65
SSI
Small‐scale integration (SSI) devices contain several independent gates in a single
package. The inputs and outputs of the gates are connected directly to the pins in the
package. The number of gates is usually fewer than 10 and is limited by the number of
pins available in the IC.
66
MSI
Medium‐scale integration (MSI) devices have a complexity of approximately 10 to
1,000 gates in a single package. They usually perform specific elementary digital operations. MSI digital functions are introduced in Chapter 4 as decoders, adders, and multiplexers and in Chapter 6 as registers and counters.
67
LSI
Large‐scale integration (LSI) devices contain thousands of gates in a single package.
They include digital systems such as processors, memory chips, and programmable logic
devices.
68
VLSI
Very large‐scale integration (VLSI) devices now contain millions of gates within a
single package. Examples are large memory arrays and complex microcomputer chips.
69
What do you mean by Digital Logic Family:
Digital integrated circuits are also classified by the specific circuit technology to which they belong. The circuit technology
is referred to as a digital logic family.
Each logic family has its own basic electronic
circuit upon which more complex digital circuits and components are developed. The
basic circuit in each technology is a NAND, NOR, or inverter gate
70
Name popular Digital logic families:
TTL transistor–transistor logic;
ECL emitter‐coupled logic;
MOS metal‐oxide semiconductor;
CMOS complementary metal-oxide-semiconductor.
71
TTL:
TTL is a logic family that has been in use for 50 years and is considered to be standard
72
ECL
ECL has an advantage in systems requiring high‐speed operation.
73
MOS
MOS is suitable
| for circuits that need high component density.
74
CMOS
CMOS is preferable in systems
requiring low power consumption, such as digital cameras, personal media players, and
other handheld portable devices. Low power consumption is essential for VLSI design
75
Why has CMOS become dominant?
Low power consumption is essential for VLSI design.
76
Standard Load:
A standard load is usually defined as the
| amount of current needed by an input of another similar gate in the same family.
77
Fan Out:
Fan‐out specifies the number of standard loads that the output of a typical gate can
drive without impairing its normal operation
78
Power Dissipation
Power dissipation is the power consumed by the gate that must be available from the
power supply
79
Fan in:
Fan‐in is the number of inputs available in a gate.
80
Propagation delay:
Propagation delay is the average transition delay time for a signal to propagate from
input to output.
81
Operating speed and propagation delay relation:
The operating speed is inversely proportional to the propagation delay.
82
Noise Margin.
Noise margin is the maximum external noise voltage added to an input signal that
does not cause an undesirable change in the circuit output.
83
computer‐aided design (CAD)
To design VLSI which consists of millions of transistors and gates.
CAD consist of software programs that support computer‐based representations
of circuits and aid in the development of digital hardware by automating the design
process
84
How are Integrated Circuits manufactured?
Integrated circuits having submicron geometric features are manufactured by optically
projecting patterns of light onto silicon wafers. Prior to exposure, the wafers are coated
with a photoresistive material that either hardens or softens when exposed to light.
Removing extraneous photoresist leaves patterns of exposed silicon. The exposed
regions are then implanted with dopant atoms to create a semiconductor material having the electrical properties of transistors and the logical properties of gates.
85
What does the design process do?
The design process translates a functional specification or description of the circuit (i.e., what it must do) into a physical specification or description (how it must be implemented in silicon).
86
EDA
Electronic design automation (EDA) covers all phases of the design of integrated circuits
87
The designer can choose between?
An application‐specific integrated circuit
(ASIC),
a field‐programmable gate array (FPGA), a programmable logic device (PLD),
and a full‐custom IC.
88
A typical design flow for creating VLSI circuits consists of?
A typical design flow for creating VLSI circuits consists of a sequence of
steps beginning with design entry (e.g., entering a schematic) and culminating with the
generation of the database that contains the photomask used to fabricate the IC
89
schematic capture or schematic
| entry?
Some CAD systems include an editing program for creating and modifying schematic
diagrams on a computer screen. This process is called schematic capture or schematic
entry
90
Verification with CAD?
Verification is performed by applying inputs to the
| circuit and using a logic simulator to determine and display the outputs in text or waveform format.
91
HDL
Such a language resembles a computer programming
language, but is specifically oriented to describing digital hardware. It represents logic
diagrams and other digital information in textual form to describe the functionality
and structure of a circuit. Moreover, the HDL description of a circuit’s functionality
can be abstract, without reference to specific hardware, thereby freeing a designer to
devote attention to higher level functional detail (e.g., under certain conditions the
circuit must detect a particular pattern of 1’s and 0’s in a serial bit stream of data) rather
than transistor‐level detail.
92
Two HDLs have been approved as
| standards by the Institute of Electronics and Electrical Engineers (IEEE)?
—Verilog and VHDL—
93
two advances in technology?
| of making ICs..
HDL‐based models of a circuit or system are simulated to check and verify its functionality before it is submitted to fabrication, thereby reducing
the risk and waste of manufacturing a circuit that fails to operate correctly. In tandem
with the emergence of HDL‐based design languages, tools have been developed to
automatically and optimally synthesize the logic described by an HDL model of a
circuit. These two advances in technology have led to an almost total reliance by industry on HDL‐based synthesis tools and methodologies for the design of the circuits of
complex digital systems.
