Midterm Flashcards
Study chapter 1 to 5
What is the primary difference between digital and analog systems?
Digital systems use discrete values, while analog systems can vary continuously over a specified range.
What are the two types of circuits discussed?
- Combinational circuits
- Sequential circuits
How do combinational circuits differ from sequential circuits?
Combinational circuits’ output depends only on present input values, while sequential circuits’ output depends on both past and present input values.
What is a basic building block of combinational circuits?
Logic gate
What is a basic building block of sequential circuits?
Flip-flop
What is the significance of binary numbers in digital systems?
Binary numbers are used because most switching devices only assume two different values.
What is positional notation in decimal numbers?
Each digit is multiplied by an appropriate power of 10 depending on its position.
What is positional notation in binary numbers?
Each digit is multiplied by an appropriate power of 2 depending on its position.
What does power series expansion in any number system involve?
Any positive integer R can be chosen as the radix or base, using R digits (0, 1, …, R−1).
How do you convert a decimal integer to base R using division?
Continue dividing until a0 is obtained; the remainder in each step is the desired digit.
Which letters represent numbers greater than 9 in hexadecimal?
- A = 10
- B = 11
- C = 12
- D = 13
- E = 14
- F = 15
How can conversion from binary to hexadecimal be done?
By inspection, as each hexadecimal digit corresponds to exactly four binary digits (bits).
Fill in the blank: A switching circuit has one or more _______ and one or more outputs which take on discrete values.
inputs
True or False: In sequential circuits, the output values only depend on the present values of inputs.
False
What are the basic operations that can be performed on positive binary numbers?
- Add
- Subtract
- Multiply
- Divide
What forms can negative binary numbers be represented in?
- Sign and magnitude
- 1’s complement
- 2’s complement
What code is used to represent decimal numbers in binary-coded decimal (BCD)?
Binary-coded-decimal (BCD)
What does it mean for switching devices to be two-state devices?
The output can only assume one of two discrete values.
What is required to represent digits in bases greater than 10?
More than 10 symbols are needed.
What does each octal digit correspond to in binary?
Three binary digits
Convert the binary number 100101101011010 to octal.
45532
In digital systems, arithmetic is performed in which number system?
Binary
What is the binary addition table used for?
To perform binary addition operations
What does the arrow indicate in binary subtraction?
Borrow which subtracts one from that column
In binary multiplication, what is the basic operation performed?
Multiplication of binary numbers
How does binary division compare to decimal division?
It is much easier because the only two possible quotient digits are 0 and 1
What are the two main groups of numbers in number representations?
- Unsigned numbers
- Signed numbers
What does the sign bit indicate in number representations?
0 indicates a positive number; 1 indicates a negative number
List the common methods of representing both positive and negative numbers.
- Sign and magnitude
- 1’s complement
- 2’s complement
How is a negative number represented using 2’s complement?
N* = 2^n - N
What is the definition of overflow in binary operations?
An operation result is outside the range of representation
When does overflow occur in binary addition?
When the sum of two positive numbers is less than 2^(n-1)
What is BCD in binary codes?
Binary Coded Decimal, where each decimal digit is replaced by its binary equivalent
What is the weight system for the 6-3-1-1 code?
- w3 = 6
- w2 = 3
- w1 = 1
- w0 = 1
What is the purpose of the Gray code?
The codes for successive decimal digits differ in exactly one bit
What are the basic operations in Boolean algebra?
- AND
- OR
- NOT
What are DeMorgan’s Laws used for in Boolean algebra?
To simplify complex Boolean expressions
What is the objective of using simplification theorems in Boolean algebra?
To simplify Boolean expressions
What is the significance of the complementing Boolean expressions?
To find the inverse of a Boolean expression
What are the basic operations of Boolean algebra?
AND, OR, complement (or inverse)
These operations are fundamental for manipulating Boolean expressions.
What do logic circuits represent in terms of switching variables?
Logic 0 represents low voltages, and Logic 1 represents high voltages.
In a switch circuit, 0 represents an open switch and 1 represents a closed switch.
How is the AND operation represented algebraically?
C = A·B = AB
This operation is also referred to as logical (or Boolean) multiplication.
How is the OR operation represented algebraically?
C = A + B
This operation is also referred to as logical (or Boolean) addition.
What does a truth table specify?
The values of a Boolean expression for every possible combination of values of the variables.
Truth tables are essential for understanding how a Boolean expression behaves.
What is the Commutative Law in Boolean algebra?
XY = YX and X + Y = Y + X
The order of variables does not affect the result of AND and OR operations.
What is the Associative Law in Boolean algebra?
(XY)Z = X(YZ) = XYZ and (X + Y) + Z = X + (Y + Z) = X + Y + Z
The result of AND and OR operations is independent of how the variables are grouped.
What is the Distributive Law in Boolean algebra?
X(Y + Z) = XY + XZ and X + YZ = (X + Y)(X + Z)
This law shows how multiplication and addition distribute over each other.
What does DeMorgan’s Law state?
(X + Y)’ = X’Y’ and (XY)’ = X’ + Y’
DeMorgan’s Law is crucial for simplifying Boolean expressions.
What is a Sum of Products (SOP) form?
An expression in SOP form consists of products of single variables.
This form is achieved when an expression is fully multiplied out.
What is a Product of Sums (POS) form?
An expression in POS form consists of sums of single variables.
This form is used in various Boolean simplifications.
Fill in the blank: The complement of a Boolean expression can be found using _______.
DeMorgan’s Laws
This method helps determine the inverse expressions of Boolean functions.
True or False: Two Boolean expressions are equal if they yield the same value for every combination of variable values.
True
This equality is fundamental in simplifying and verifying Boolean expressions.
How many rows will an n-variable expression have in its truth table?
2^n
This exponential growth represents all possible combinations of variable states.
What do NC and NO stand for in switch circuits?
Normally Closed (NC) and Normally Open (NO)
These terms describe the default state of the switch contacts.
What is the result of X’ when X = 0?
1
This represents the inversion of the Boolean variable.
What is the result of X’ when X = 1?
0
This is part of the fundamental properties of complementation in Boolean algebra.
What are the learning objectives of Boolean algebra?
Apply laws and theorems to simplify expressions, find complements, multiply out and factor expressions, prove theorems using truth tables or algebraic proofs, define exclusive-OR and equivalence operations, use consensus theorem, and prove the validity of equations.
What is the process to obtain the sum-of-products (SOP) expression from a product-of-sums (POS) form?
Multiply out (expand) using the two distributive laws.
What theorem is useful for factoring and multiplying out in Boolean algebra?
The theorem that aids in finding common factors.
When multiplying out an expression, which laws should be applied first?
(3-2) and (3-3) should generally be applied before (3-1).
What is the definition of the exclusive-OR (XOR) operation?
X Y = 1 if and only if X = 1 or Y = 1, but not both.
How can XOR be expressed in terms of AND and OR?
X Y = XY’ + X’Y.
What is the equivalence operation (XNOR) in Boolean algebra?
The output is 1 iff X and Y have the same value.
What does the consensus theorem do?
It cancels out redundant terms in an expression.
List three basic ways to simplify switching functions.
- Combining terms
- Eliminating terms
- Eliminating literals
What theorem is used to combine two terms in simplification?
XY + XY’ = X.
How can redundant terms be eliminated using a theorem?
Use the theorem X + XY = X.
What theorem can be used to eliminate redundant literals?
X + X’Y = X + Y.
What methods can be used to prove the validity of an equation?
- Construct a truth table
- Manipulate one side using theorems
- Reduce both sides to the same expression
How can you prove that an equation is NOT valid?
Show that the two sides have different values for only one combination of input values.
What is the cancellation law in Boolean algebra?
The cancellation law for ordinary algebra does not hold; if x+y=x+z, then y=z is NOT VALID.
Provide an example demonstrating the cancellation law’s invalidity in Boolean algebra.
Consider X=1, Y=0, Z=1; xy=xz then y=z is NOT VALID.
What is the law of multiplication in Boolean algebra?
The law of multiplication does not hold for Boolean algebra. If xy=xz, then y=z is NOT VALID.
Provide an example to illustrate the invalidity of the law of multiplication in Boolean algebra.
Consider X=0, Y=0, Z=1.
What are the Cancellation Laws in Boolean Algebra?
The converses of the cancellation laws hold true.
What are the main topics covered in the chapter on Applications of Boolean Algebra?
- Conversion of English Sentences to Boolean Equations
- Combinational Logic Design Using a Truth Table
- Minterm and Maxterm Expansions
- Incompletely Specified Functions
- Examples of Truth Table Construction
- Design of Binary Adders and Subtracters
What is a minterm in Boolean algebra?
A minterm is a product term that involves all variables in either true or complemented form, but not both.
How are minterms often denoted?
Minterms are often written in abbreviated form, such as A’B’C’ designated as m0, A’B’C as m1, etc.
What is a maxterm in Boolean algebra?
A maxterm is a sum term that involves all variables in either true or complemented form, but not both.
What is the relationship between minterms and maxterms?
A maxterm is the complement of the corresponding minterm.
What does it mean for a function to be incompletely specified?
Certain input combinations never occur, and for these combinations, we ‘don’t care’ about the output value.
What is a truth table used for in combinational logic design?
It is used to design a circuit based on the desired output for given input combinations.
Given a truth table, how can you express the function as a minterm expansion?
By writing the function as a sum of minterms, referred to as a minterm expansion or standard sum of products.
What is the output of a circuit if N >= 0112?
f = 1.
What is the output of a circuit if N < 0112?
f = 0.
Fill in the blank: A full adder is designed to perform ______.
addition of binary numbers with carry.
What is the general form of the minterm and maxterm expansion for a function of n variables?
The general form includes all combinations of the variables in both true and complemented forms.
What is the purpose of using ‘don’t-care’ terms in Boolean functions?
‘Don’t-care’ terms simplify the logic design by allowing flexibility in output values.
True or False: A function can be expressed in both minterm and maxterm forms.
True.
What is the first step in designing a logic circuit from English sentences?
Translate the sentences into Boolean equations.
What are the two forms of expansion for a Boolean function?
- Minterm expansion (standard SOP)
- Maxterm expansion (standard POS)
In a truth table, how is the minterm corresponding to row i designated?
It is designated as mi.
What is a full adder truth table used for?
To determine the output of a full adder for all possible input combinations.
What must be done to derive logic equations for a full adder?
Explain the operation and trace signals on the block diagram.
What is the truth table for a Full Adder?
A Full Adder has three inputs and two outputs:
- Inputs: A, B, Carry-in
- Outputs: Sum, Carry-out
The truth table represents all possible input combinations and their corresponding outputs.
What are the logic equations for a Full Adder?
The logic equations for a Full Adder are:
- Sum = A XOR B XOR Carry-in
- Carry-out = (A AND B) OR (Carry-in AND (A XOR B))
These equations define how to compute the sum and carry-out based on the inputs.
What is the design approach for a 4-bit Ripple Carry Adder?
A 4-bit Ripple Carry Adder connects four Full Adders in series. The carry output from each Full Adder serves as the carry input to the next.
This design allows for binary addition of two 4-bit numbers.
How is a Full Subtractor designed?
A Full Subtractor can be designed similarly to a Full Adder. It has three inputs and two outputs:
- Inputs: A, B, Borrow-in
- Outputs: Difference, Borrow-out
Subtraction can also be expressed as A - B = A + (-B).
What is the function of a Binary Subtracter?
A Binary Subtracter performs subtraction using Full Adders, where A - B is computed as A + (-B).
This method utilizes the principles of binary addition and complements.
What is a Carry Lookahead Adder?
A Carry Lookahead Adder improves speed over Ripple Carry Adders by using generate (Gi) and propagate (Pi) signals to calculate carry outputs more quickly.
This technique reduces the propagation delay of carry signals.
What are Don’t Care Conditions?
Don’t Care Conditions refer to input combinations that may never occur in practical systems. These conditions provide flexibility in circuit design.
Output values for these conditions can be chosen to simplify the circuit.
What is the definition of a Minimum Sum-of-Products Expression?
A Minimum Sum-of-Products Expression is a sum of product terms with the minimum number of terms and literals.
It corresponds to a minimum two-level gate circuit with the least number of gates and inputs.
How can you plot a function on a Karnaugh map?
To plot a function on a Karnaugh map, you need to represent the function in minterm, maxterm, or algebraic form and fill in the map according to the output values of the function.
This visual representation helps in simplifying Boolean functions.
What are Minterms and Maxterms?
Minterms are product terms involving all variables in true or complemented form, while Maxterms are sum terms involving all variables in true or complemented form.
Minterms are written in m-notation (m0, m1, etc.), and Maxterms in M-notation.
True or False: A Full Adder has two outputs.
True
The outputs are Sum and Carry-out.
What is the minimum form of switching functions?
A minimum product-of-sums expression is defined as a product of sum terms which has a minimum number of terms and a minimum number of literals among expressions with the same number of terms.
This concept is critical for simplifying logical expressions in digital logic design.
How can you find a minimum sum-of-products given a minterm expansion?
Combine terms using the uniting theorem XY + XY’ = X, repeatedly to eliminate as many literals as possible.
This theorem allows for the simplification of logical expressions by reducing redundancy.
What theorem can eliminate redundant terms in switching functions?
The consensus theorem or other theorems can be used to eliminate redundant terms.
Understanding different theorems is essential for optimizing logical expressions.
What is a Karnaugh map?
A systematic way of simplifying switching functions that leads to minimum cost two-level circuits composed of AND and OR gates.
Karnaugh maps are a visual tool for minimizing logical expressions.
How are values plotted on a two-variable Karnaugh map?
The value of F for A = B = 0 is plotted in the upper left square, with other entries plotted similarly. Each 1 corresponds to a minterm of F.
This mapping technique helps visualize and simplify logical functions.
What indicates that AB is a minterm on a Karnaugh map?
A 1 in square 01 indicates that AB is a minterm.
Minterms are crucial for defining the output of logical functions.
What determines if minterms can be combined on a Karnaugh map?
Minterms in adjacent squares differ in only one variable and can be combined using the uniting theorem XY + XY’ = X.
This property is fundamental for simplifying logical expressions.
What is the role of ‘don’t cares’ in Karnaugh maps?
‘Don’t cares’ are noted as X’s in Karnaugh maps and can be used to simplify expressions.
Utilizing ‘don’t cares’ can lead to more efficient logical designs.
What is a prime implicant?
A product term implicant that cannot be combined with another term to eliminate a variable.
Identifying prime implicants is essential for finding minimum expressions.
What is an essential prime implicant?
A prime implicant that covers a minterm which is covered by only one prime implicant and must be included in the minimum sum of products.
Essential prime implicants are critical for ensuring all necessary outputs are included in the final expression.
What is the procedure to obtain the minimum product of sums from a maxterm expansion?
A procedure similar to that used for minimum sum-of-products, using the uniting theorem (X + Y)(X + Y’) = X to combine terms.
This method is vital for expressing logical functions in a minimized form.
True or False: A sum-of-products expression containing a term which is not a prime implicant can still be minimum.
False.
Only prime implicants can ensure that the expression is minimized.
How is the minimum solution determined from a Karnaugh map?
By looping all of the essential prime implicants first.
This ensures all necessary terms are included for the minimum expression.
What happens to the minimum solution if not all prime implicants are included?
The minimum solution may not include all prime implicants.
This illustrates the need to carefully select implicants to achieve minimization.
What is the result of plotting functions on a Karnaugh map?
‘1’s are plotted for whichever values of the variables would result in the expression yielding ‘1’.
This plotting is essential for visualizing the logical function.
Fill in the blank: A minimum sum-of-products from a map should first loop all of the _______.
essential prime implicants.
This step is crucial for ensuring the minimum expression is accurate.
What is an essential prime implicant?
A term that covers a given minterm and all of the 1’s adjacent to it.
How can essential prime implicants sometimes be found?
By inspection or looking at all squares adjacent to a minterm.
What must be checked to determine if prime implicants are essential?
Whether all of the 1’s adjacent to a given minterm are covered by a single term.
What is the first step in obtaining a minimum SOP from a K-Map?
Choose a minterm (a 1) which has not yet been covered.
What should be done after choosing a minterm in the K-Map procedure?
Find all 1’s and X’s adjacent to that minterm.
What indicates that a term is an essential prime implicant in K-Maps?
If a single term covers the minterm and all of the adjacent 1’s and X’s.
What should be done after selecting an essential prime implicant?
Repeat the steps until all essential prime implicants have been chosen.
What is the final step in the K-Map procedure?
Find a minimum set of prime implicants which cover the remaining 1’s.
How should ‘don’t-care’ terms be treated in K-Map procedures?
Like 1’s in steps 2 and 3 but not in step 1.
How can a five-variable K-map be constructed?
By placing one four-variable map on top of a second one.
What numbering scheme is used for a five-variable K-map?
Terms in the bottom layer are numbered 0 through 15, and those in the top layer are numbered 16 through 31.
What is a Veitch Diagram?
A form of K-map labeling sides with A=1 for one half and A=0 for the other half.
True or False: Two functions can be proven equal by plotting them on Karnaugh maps.
True
What operations can be performed using Karnaugh maps?
ANDing or ORing the 1’s and 0’s in corresponding positions.
Fill in the blank: In a five-variable K-map, terms in the bottom layer contain ______.
A’
What should be done if there is more than one set of prime implicants covering the 1’s?
Choose a set with a minimum number of literals.
What diagram helps visually represent the K-map procedure?
A flowchart.
What is the significance of ‘don’t-care’ terms in K-maps?
They are treated as flexible 1’s to simplify the expressions.
