Boolean Algebra Practice Questions

To determine the glitch duration for output $Q$, we calculate the propagation delays of the two signal paths from input $A$ to the inputs of the final XOR gate.

1. Upper Path ($A \to \text{NOT} \to \text{AND}$): The total delay is $T_{upper} = t_{inv} + t_{AND} = 6 + 10 = 16 \text{ ns}$.
2. Lower Path ($A \to \text{OR}$): The total delay is $T_{lower} = t_{OR} = 11 \text{ ns}$.
3. The glitch occurs because the XOR gate receives changes at different times from these two paths. The duration of the glitch is the difference in propagation delays: $\Delta t = |T_{upper} - T_{lower}| = |16 - 11| = 5 \text{ ns}$.

Let's simplify the given Boolean expression $F(P,Q)$ using the properties of XOR operation.
Recall that $A \oplus 1 = \overline{A}$ and $A \oplus 0 = A$.

First, simplify the terms inside the expression:
$(1 \oplus P) = \overline{P}$
$(Q \oplus 0) = Q$

Substitute these back into $F(P,Q)$:
$F(P,Q) = (\overline{P} \oplus (P \oplus Q)) \oplus ((P \oplus Q) \oplus Q)$

Now, let $X = P \oplus Q$. The expression becomes:
$F(P,Q) = (\overline{P} \oplus X) \oplus (X \oplus Q)$

Using the property $A \oplus B = \overline{A}B + A\overline{B}$:
$\overline{P} \oplus X = \overline{P}\overline{X} + P X$
$X \oplus Q = X\overline{Q} + \overline{X}Q$

The expression is of the form $(A \oplus B) \oplus (C \oplus D)$.
A simpler approach is to use the associative and commutative properties of XOR:
$A \oplus B \oplus C = (A \oplus B) \oplus C = A \oplus (B \oplus C)$.
$F(P,Q) = \overline{P} \oplus (P \oplus Q) \oplus (P \oplus Q) \oplus Q$
Since $Y \oplus Y = 0$:
$F(P,Q) = \overline{P} \oplus 0 \oplus Q$
$F(P,Q) = \overline{P} \oplus Q$
We know that $A \oplus B = B \oplus A$ and $A \oplus B = \overline{A \oplus B}$ if $A=1$ or $B=1$.
And $\overline{P} \oplus Q = \overline{P}\overline{Q} + P Q = \overline{P \oplus Q}$.

The equivalent expression is $\overline{P \oplus Q}$.

A Boolean function $F$ is self-dual if $F(x_1, x_2, \dots, x_n) = F^D(x_1, x_2, \dots, x_n)$, where $F^D$ is the dual function. The dual function is obtained by swapping AND and OR operators, and 0 and 1 (if present). For a function to be self-dual, it must satisfy $F(x_1, \dots, x_n) = [F(\bar{x_1}, \dots, \bar{x_n})]'$.

For a function to be self-dual, it must have an equal number of minterms and maxterms. This implies that if a minterm is included, its corresponding maxterm (formed by complementing all variables) must be excluded, and vice versa. There are $2^n$ possible minterms (or maxterms) for $n$ variables.

These $2^n$ minterms can be paired up such that each pair consists of a minterm and its complement. For example, $(x_1x_2\dots x_n)$ and $(\bar{x_1}\bar{x_2}\dots \bar{x_n})$. There are $2^n / 2 = 2^{n-1}$ such pairs.

For each of these $2^{n-1}$ pairs, we have two choices for constructing a self-dual function: either include the minterm and exclude its complement, or exclude the minterm and include its complement. If we include a minterm, we must exclude its complementary maxterm to maintain the self-dual property.

Therefore, for each of the $2^{n-1}$ pairs, there are 2 independent choices. This leads to a total of $2^{2^{n-1}}$ self-dual functions.

The problem provides a set of minterms where the function $F$ is 1 and a set of 'do not care' terms. The minterms that must be covered are $m(0, 5, 10, 15)$ and the don't care terms are $d(2, 7, 8, 13)$. We use a 4-variable Karnaugh map to find the minimal sum-of-products expression.

1. We place '1's in the K-map for the minterms and 'X's for the don't cares. We then form the largest possible groups (prime implicants) to cover all the '1's.

2. The first group can be formed by the four corners of the K-map, which correspond to minterms $0, 2, 8, 10$. This group includes two '1's ($m_0, m_{10}$) and two don't cares ($d_2, d_8$). The common variables for this group are $\bar{Q}$ and $\bar{S}$, giving the term $\bar{Q}\bar{S}$.

3. The second group covers the remaining '1's ($m_5, m_{15}$) by including the don't cares $d_7$ and $d_{13}$. This group of four corresponds to minterms $5, 7, 13, 15$. The common variables for this group are $Q$ and $S$, giving the term $QS$.

4. Combining the terms from these two essential prime implicants gives the minimal sum-of-products form.

   $$F(P,Q,R,S) = \bar{Q}\bar{S} + QS$$

This expression is the logical equivalence (XNOR) of variables Q and S.

The top NAND gate outputs $\overline{CD}$.
The middle NAND gate takes $B$ and $\overline{CD}$, yielding $\overline{B \cdot \overline{CD}} = \bar{B} + CD$.
The bottom NAND gate takes $A$ and $B$, yielding $\overline{AB}$.
The final NAND gate computes $Q = \overline{(\bar{B} + CD) \cdot (\overline{AB})}$.
Applying De Morgan's law: $Q = \overline{(\bar{B} + CD)} + \overline{(\overline{AB})} = (B \cdot \overline{CD}) + AB$.
Simplifying, we get $Q = B(\bar{C} + \bar{D}) + AB = AB + B\bar{C} + B\bar{D}$.

To find the minimal sum-of-products form, we simplify the given Boolean expression.
The given expression is $F(P,Q,R,S)=PQ+\bar{P}QR+\bar{P}Q\bar{R}S$.
Factor out $PQ$ from the first two terms: $F = PQ(1+\bar{R}) + \bar{P}Q\bar{R}S$.
Since $1+X=1$, $1+\bar{R}=1$, so $F = PQ + \bar{P}Q\bar{R}S$.
Now factor out $Q$: $F = Q(P+\bar{P}\bar{R}S)$.
Using the absorption law $X+\bar{X}Y = X+Y$, we have $P+\bar{P}\bar{R}S = P+\bar{R}S$.
Substitute this back into the expression for F: $F = Q(P+\bar{R}S)$.
Distribute $Q$: $F = PQ + Q\bar{R}S$.

A tristate buffer functions based on an enable input, denoted as $E$. It provides three distinct output states: logic $0$, logic $1$, and a high-impedance (Hi-Z) state. When $E = 1$, the buffer passes the input signal to the output $Y$. However, when $E = 0$, the buffer's output circuitry enters a high-impedance state, effectively decoupling the output from the rest of the circuit. This condition behaves like an open switch, which corresponds to a disconnected state.

To verify Option C, apply the distributive law to the left side: $\bar{X} + XY = (\bar{X} + X) \cdot (\bar{X} + Y)$.
Since the complement law states that $\bar{X} + X = 1$, the expression simplifies: $1 \cdot (\bar{X} + Y) = \bar{X} + Y$.
Clearly, $\bar{X} + Y \neq Y$, proving the identity $\bar{X} + XY = Y$ is false.
Options A ($X \cdot X = X$), B ($(X+Y) \cdot X = X$), and D ($(X+Y) \cdot (X+Z) = X+YZ$) are standard, valid Boolean laws.
is not a valid Boolean algebra rule.

The exclusive NOR (XNOR) operation of two variables $x$ and $y$, denoted as $x \odot y$, is true when both $x$ and $y$ are the same (both true or both false). Its standard representation is $xy + x'y'$.

Let's evaluate each option:
A. $xy + x'y'$: This is the standard definition of XNOR, so it represents $x \odot y$.
B. $x \oplus y'$: The exclusive OR (XOR) is $x \oplus y = xy' + x'y$. So, $x \oplus y' = x(y')' + x'y' = xy + x'y'$. This also represents $x \odot y$.
C. $x' \oplus y$: Similarly, $x' \oplus y = x'y' + (x')'y = x'y' + xy$. This also represents $x \odot y$.
D. $x' \oplus y'$: Using the XOR definition, $x' \oplus y' = x'(y')' + (x')'y' = x'y + xy'$. This expression represents $x \oplus y$, which is the complement of XNOR. Therefore, it does NOT represent exclusive NOR.

The given Boolean function is $f(A, B, C, D) = \sum(7, 8, 9, 10, 11, 12, 13, 14, 15)$.
Using a $4$-variable K-map, the minterms $8, 9, 10, 11, 12, 13, 14, 15$ fill the entire bottom half of the map where $A=1$, simplifying to the term $A$.
The remaining minterm $7$ ($0111_2$) is adjacent to minterm $15$ ($1111_2$) vertically, allowing them to form a $2$-cell group.
This vertical group identifies the common variables $B=1, C=1, D=1$, which simplifies to $BCD$.
Combining these prime implicants yields the simplified expression $f = A + BCD$.

A set of Boolean operators is functionally complete if it can express every possible Boolean function, which requires the ability to generate the NOT operation ($\neg$). The operators $\{AND, OR\}$ are monotonic; any Boolean expression $f(x_1, \dots, x_n)$ formed using only these operators satisfies the property that $f(1, \dots, 1) = 1$. Since the NOT operation requires mapping an input of $1$ to $0$, the set $\{AND, OR\}$ cannot generate $\neg$, rendering it incomplete. By contrast, $\{NOR\}$ is a universal gate, and both $\{NOT, OR\}$ and $\{AND, NOT\}$ can implement all Boolean functions via De Morgan's laws (e.g., $A \lor B = \neg(\neg A \land \neg B)$). Therefore, $\{AND, OR\}$ fails to be functionally complete.

The Karnaugh map shows a 4-variable function with 'don't care' terms (X). To find the minimal form, we group adjacent 1s and X's in powers of two.

1. Identify a group of eight adjacent cells: The first column (00) has a 1 at 00, an X at 01, a 1 at 10, and an X at 11. This group covers $\bar{b}\bar{d}$.
2. Identify a group of four adjacent cells: The first row (00) has a 1 at 00, an X at 01, an X at 11, and a 1 at 10. The 1 at 00 in the first row is already covered by $\bar{b}\bar{d}$. We need to cover the remaining 1s.
3. Consider the 1s in the third column (11). There is a 1 at 01 (cb=01, ab=11). We can form a group with this 1 and the X at 00 (cb=00, ab=11) and the X at 10 (cb=10, ab=11) and the 1 at 11 (cb=11, ab=11). This forms a column $\bar{b}\bar{c}$.
4. A different grouping: The first column (ab=00) has a 1 at cd=00 and a 1 at cd=10. This gives $\bar{a}\bar{b}$. The X's in this column can be used to extend groups.
5. Consider the first row (cd=00): There is a 1 at ab=00 and a 1 at ab=10. We can form a group with these two 1s and the two X's at ab=01 and ab=11. This forms a group covering $\bar{d}\bar{b}$.
6. The remaining uncovered 1 is at (ab=01, cd=10). This is $a\bar{b}\bar{c}d$. We can cover this with a group involving the X's. A group of two at (ab=01, cd=10) and (ab=01, cd=11) would be $\bar{b}c\bar{d}$.

However, the provided solution uses a different minimal grouping:

• A group of 8 containing (00,00), (00,01), (00,10), (00,11), (10,00), (10,01), (10,10), (10,11) represents $\bar{d}\bar{b}$. This covers the first and fourth columns (ab=00 and ab=10).
• A group of 4 containing (01,10), (01,11), (11,10), (11,11) represents $\bar{c}\bar{b}$. This covers the cells where cd=10 and cd=11, effectively $\bar{c}$.

Let's re-evaluate the K-map carefully:
The terms are:
(ab=00, cd=00) = 1
(ab=00, cd=01) = X
(ab=00, cd=10) = 1
(ab=00, cd=11) = X
(ab=01, cd=00) = X
(ab=01, cd=10) = 1
(ab=10, cd=00) = 1
(ab=10, cd=01) = X
(ab=10, cd=10) = 1
(ab=10, cd=11) = X
(ab=11, cd=00) = X
(ab=11, cd=01) = X
(ab=11, cd=10) = X
(ab=11, cd=11) = 1

Group 1 (Vertical group of 4): The cells (ab=00, cd=00), (ab=00, cd=10), (ab=10, cd=00), (ab=10, cd=10) along with the X's can form a group. A group of 4 across (ab=00,01,11,10) and (cd=00) and (cd=10) is not possible.
Let's look at the columns:
Column (ab=00): cells (0,0), (0,1), (1,0), (1,1) -> 1, X, 1, X. This whole column is $\bar{a}\bar{b}$. It contains 1s at (00,00) and (00,10).
Column (ab=10): cells (0,0), (0,1), (1,0), (1,1) -> 1, X, 1, X. This whole column is $a\bar{b}$. It contains 1s at (10,00) and (10,10).
We can form a group of 8 by combining these two columns. These are all cells where $\bar{b}$ is true. This group is $\bar{b}$. However, this is wrong from the image. The image has columns for $ab$ as $00, 01, 11, 10$. So, $\bar{b}$ would be columns $00$ and $01$.
Let's use the provided K-map format:
ab
00 01 11 10
cd
00 | 1 | X | X | 1 |
01 | X | | X | X |
11 | X | | 1 | X |
10 | 1 | 1 | X | 1 |

Group 1: A group of 4 formed by (ab=00, cd=00), (ab=00, cd=10), (ab=10, cd=00), (ab=10, cd=10).
This group is $c\bar{d}$ (from cd=10) and $\bar{b}$ (from ab=00, ab=10).
This group covers: (00,00) (00,10) (10,00) (10,10). The cells are: $(a\bar{b}\bar{c}\bar{d})$, $(\bar{a}\bar{b}c\bar{d})$, $(a\bar{b}\bar{c}\bar{d})$, $(a\bar{b}c\bar{d})$.
The common term for (ab=00, ab=10) is $\bar{b}$. The common term for (cd=00, cd=10) is $\bar{d}$.
So, this group is $\bar{b}\bar{d}$. This covers the 1s at (00,00), (00,10), (10,00), (10,10).

Remaining 1s to cover: (ab=01, cd=10) and (ab=11, cd=11).
(ab=01, cd=10) is $\bar{a}b c\bar{d}$.
(ab=11, cd=11) is $ab c d$.

Group 2: To cover (ab=01, cd=10). We can use the X at (ab=11, cd=10) and the X at (ab=01, cd=11).
A group of 4: (ab=01, cd=10), (ab=01, cd=11), (ab=11, cd=10), (ab=11, cd=11).
The common terms for (ab=01, ab=11) are $b$. The common terms for (cd=10, cd=11) are $c$.
So, this group is $bc$. This covers the 1 at (01,10) and the 1 at (11,11).

Therefore, the minimal expression is $\bar{b}\bar{d} + bc$.

Let's check the solution in the document:
The solution highlights two groups:

1. A group of 8 across columns (00, 01, 11, 10) in rows (00, 10). This implies $\bar{d}\bar{b}$ (from columns $00,01$ as $\bar{a}\bar{b}, \bar{a}b$ which is $\bar{a}$, and $11,10$ as $ab, a\bar{b}$ which is $a$. So all columns are $ab, \bar{a}b, \bar{a}\bar{b}, a\bar{b}$). No, this is wrong grouping.
   The first group is made up of (ab=00,cd=00), (ab=00,cd=10), (ab=10,cd=00), (ab=10,cd=10) and using the X's. This forms $\bar{b}\bar{d}$. This is the rectangle on the leftmost and rightmost columns for cd=00 and cd=10. This group is correct.
2. The second group is shown as (ab=01, cd=10) (the 1) and (ab=01, cd=11) (X) and (ab=11, cd=10) (X) and (ab=11, cd=11) (the 1). This forms a group of 4: $bc$. This is also correct.

So the minimal form is $\bar{b}\bar{d} + bc$.

The image of the solution shows a grouping that covers:

1. Cells (00,00), (00,01) (X), (00,10), (00,11) (X), (10,00), (10,01) (X), (10,10), (10,11) (X). This covers all cells in columns $ab=00$ and $ab=10$. This is equivalent to $\bar{b}$.
2. Cells (00,00), (01,00)(X), (11,00)(X), (10,00) (1). This is $\bar{c}\bar{d}$.
3. Cells (00,10), (01,10)(1), (11,10)(X), (10,10)(1). This is $c\bar{d}$.

The solution's visual grouping:

• A group of 4 (including X's) covering the cells (ab=00, cd=00), (ab=00, cd=10), (ab=10, cd=00), (ab=10, cd=10). This is $\bar{b}\bar{d}$. This covers 1s at (00,00), (00,10), (10,00), (10,10).
• A group of 4 (including X's) covering the cells (ab=01, cd=10), (ab=01, cd=11)(implied 1 or X for grouping), (ab=11, cd=10)(X), (ab=11, cd=11)(1). This is $bc$. This covers 1s at (01,10) and (11,11).

The minimal form derived from these groupings is $\bar{b}\bar{d} + bc$.

To determine the Boolean function represented by the truth table, we can analyze the output for different input combinations of X and Y.

The truth table is:
| X | Y | f(X,Y) |
|---|---|--------|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

From the table, we observe that the output $f(X,Y)$ is 1 only when X is 1, regardless of the value of Y. When X is 0, the output is always 0. This behavior directly matches the input X.
Therefore, the Boolean function is $f(X,Y) = X$.
We can also derive this using Sum of Products (SOP) form:
$f(X,Y) = (X \land \neg Y) \lor (X \land Y)$
Factoring out X:
$f(X,Y) = X \land (\neg Y \lor Y)$
Since $(\neg Y \lor Y)$ is always true (1):
$f(X,Y) = X \land 1 = X$

The circuit consists of three main stages:

1. The top AND gate receives inputs $X$ and $Y$, producing the output $X \cdot Y$.
2. The bottom section processes $X$ and $Y$ through NOT gates to produce $\bar{X}$ and $\bar{Y}$, which are then fed into another AND gate to yield $\bar{X} \cdot \bar{Y}$.
3. An OR gate combines the outputs of both AND gates to generate the final result.
4. Therefore, the final output expression is $X \cdot Y + \bar{X} \cdot \bar{Y}$.

To simplify the given Boolean expression, we can use the distributive law and the property $X \cdot \bar{X} = 0$ and $X + \bar{X} = 1$.

The expression is $(P+\bar{Q}+\bar{R})\cdot (P+\bar{Q}+R)\cdot (P+Q+\bar{R})$.
First, consider the first two terms:
$(P+\bar{Q}+\bar{R})\cdot (P+\bar{Q}+R) = (P+\bar{Q}) + (\bar{R}\cdot R)$ (using $(X+Y)(X+Z) = X+YZ$)
$= (P+\bar{Q}) + 0$
$= P+\bar{Q}$

Now, multiply this result with the third term:
$(P+\bar{Q})\cdot (P+Q+\bar{R})$
Again, applying the distributive law $(X+Y)(X+Z) = X+YZ$:
Let $X = P$, $Y = \bar{Q}$, and $Z = Q+\bar{R}$.
So, the expression becomes $P + (\bar{Q})(Q+\bar{R})$.
$= P + (\bar{Q}Q + \bar{Q}\bar{R})$ (distributive law)
$= P + (0 + \bar{Q}\bar{R})$ (since $\bar{Q}Q = 0$)
$= P + \bar{Q}\bar{R}$

The simplified Sum of Product (SOP) form is $P+\bar{Q}\bar{R}$.

To expand the expression $(X+Y)(X+Z)$, apply the distributive law:
$(X+Y)(X+Z) = X \cdot X + X \cdot Z + Y \cdot X + Y \cdot Z$
Apply the idempotent law ($X \cdot X = X$) and the commutative property ($Y \cdot X = X \cdot Y$):
$= X + XZ + XY + YZ$
Factor $X$ out of the first three terms:
$= X(1 + Z + Y) + YZ$
Using the null law ($1 + \text{anything} = 1$), the expression simplifies to:
$= X(1) + YZ = X + YZ$

An XNOR gate, also known as an equivalence gate, produces a HIGH output when both inputs are the same (both HIGH or both LOW). Its Boolean expression is $A \odot B = AB + \overline{A}\overline{B}$.

Let's analyze the provided circuits:

• Circuit (A): This circuit is a standard XNOR gate implementation using an OR gate with two AND gates for $AB$ and $\overline{A}\overline{B}$.
• Circuit (B): This circuit is equivalent to an XNOR gate. It consists of an XOR gate followed by a NOT gate, which is a common way to realize an XNOR gate (XNOR = NOT XOR).
• Circuit (C): This circuit is an XNOR gate. It uses two NOT gates, two AND gates, and an OR gate. It explicitly computes $AB + \overline{A}\overline{B}$.
• Circuit (D): This circuit is an XOR (exclusive OR) gate, not an XNOR gate. It outputs HIGH when the inputs are different and LOW when they are the same, which is the opposite behavior of an XNOR gate.

Therefore, circuit (D) is not equivalent to a 2-input XNOR gate.

The XOR operation, denoted by $\oplus$, is associative and commutative.
Given the expression $(X \oplus Y) \oplus Y$, we can apply the associative property to rewrite it as $X \oplus (Y \oplus Y)$.
We know that the XOR of any value with itself results in $0$, meaning $Y \oplus Y = 0$.
Substituting this result, the expression simplifies to $X \oplus 0$.
Since XORing any value with $0$ returns the original value, the final result is $X$.

To find the minterm expansion, we need to express the function $f(P,Q,R)=PQ+QR'+PR'$ as a sum of its fundamental products (minterms). A minterm is a product term that includes every variable in either its true or complemented form. We can expand each term in the function to include all variables.

1. Term PQ: Missing the variable R. We expand it as $PQ = PQ(R+R') = PQR + PQR'$.

   • $PQR$ corresponds to minterm $m_7$ (binary 111).
   • $PQR'$ corresponds to minterm $m_6$ (binary 110).

2. Term QR': Missing the variable P. We expand it as $QR' = QR'(P+P') = PQR' + P'QR'$.

   • $PQR'$ corresponds to minterm $m_6$ (binary 110).
   • $P'QR'$ corresponds to minterm $m_2$ (binary 010).

3. Term PR': Missing the variable Q. We expand it as $PR' = PR'(Q+Q') = PQR' + PQ'R'$.

   • $PQR'$ corresponds to minterm $m_6$ (binary 110).
   • $PQ'R'$ corresponds to minterm $m_4$ (binary 100).

The function is the logical OR (sum) of these terms. By collecting all the unique minterms, we get:

$f(P,Q,R) = m_7 + m_6 + m_2 + m_4$

Rearranging them in numerical order, the expansion is $m_2 + m_4 + m_6 + m_7$.