Boolean algebra identities - Discrete Math

Consider the Boolean expression $(A + B)(\overline{A} + C)(B + C)$ . Which of the following is the simplified form after applying Boolean algebra identities?
Answer: $AC + BC$ Expanding $(A + B)(\overline{A} + C)(B + C)$ : First expand $(A + B)(\overline{A} + C) = A\overline{A} + AC + B\overline{A} + BC = AC + B\overline{A} + BC$ (since $A\overline{A} = 0$ ). Then multiply by $(B + C)$ : $(AC + B\overline{A} + BC)(B + C) = ACB + ACC + B\overline{A}B + B\overline{A}C + BCB + BCC = ABC + AC + B\overline{A}C + BC$ (using idempotent laws). Since $ABC \subseteq AC$ and $B\overline{A}C \subseteq BC$ , we get $AC + BC$ .
Using the Boolean algebra identity $A \oplus B \oplus C = (ABC) + (\overline{A}\overline{B}C) + (\overline{A}B\overline{C}) + (A\overline{B}\overline{C})$ , which expression is equivalent to $\overline{x \oplus y \oplus z}$ ?
Answer: $\overline{x}\overline{y}\overline{z} + \overline{x}yz + x\overline{y}z + xy\overline{z}$ The three-way XOR x ⊕ y ⊕ z is true when an odd number of variables are true. From the given identity, x ⊕ y ⊕ z = xyz + x̄ȳz + x̄yz̄ + xȳz̄. The complement (x ⊕ y ⊕ z)¯ is true when an even number of variables are true (including zero). This gives us the minterms: x̄ȳz̄ (000), x̄yz (011), xȳz (101), and xyz̄ (110). Choice D correctly lists these minterms. Choice A has the wrong pattern of complements. Choice B includes xyz instead of xyz̄. Choice C matches the original XOR, not its complement.
A Boolean function $F(A,B,C) = AB + A\overline{C} + \overline{B}C$ is to be minimized. After applying the consensus theorem and other reduction identities, which term can be eliminated?
Answer: The term $\overline{B}C$ can be eliminated because it is the consensus of $AB$ and $A\overline{C}$ The consensus theorem states that $XY + \overline{X}Z + YZ = XY + \overline{X}Z$ (the $YZ$ term can be eliminated). Here, we can rewrite as $AB + A\overline{C} + \overline{B}C$ . We need terms of the form $XY + \overline{X}Z + YZ$ . Looking at $A\overline{C} + \overline{A}B + \overline{C}B$ - this doesn't directly fit. However, we can check if $\overline{B}C$ is the consensus of the other terms. For consensus, we need $AB + A\overline{C}$ to imply $\overline{B}C$ in some cases. Actually, $\overline{B}C$ is indeed the consensus term and can be eliminated, leaving $AB + A\overline{C}$ .
In Boolean algebra, which of the following expressions is equivalent to $\overline{\overline{A}B + A\overline{B}} \cdot (A + B)$ after applying De Morgan's laws and simplification?
Answer: $AB$ First, recognize that ĀB + AB̄ is the XOR operation (A ⊕ B). So we have (A ⊕ B)¯ · (A + B). The complement of XOR is the XNOR operation: (A ⊕ B)¯ = AB + ĀB̄. Therefore, the expression becomes (AB + ĀB̄)(A + B). Expanding: AB(A + B) + ĀB̄(A + B) = AB·A + AB·B + ĀB̄·A + ĀB̄·B = AB + AB + 0 + 0 = AB. Choice A gives the unsimplified product-of-sums form. Choice B represents XNOR but doesn't account for the (A + B) factor. Choice C represents XOR, which is the opposite of what we want.
Consider the Boolean identity $(A + B)(A + \overline{B}) = A$ . If we generalize this to $(X + Y)(X + \overline{Y}) = X$ , which of the following correctly explains why this identity holds?
Answer: By the distributive law: $XX + X\overline{Y} + YX + Y\overline{Y} = X + X\overline{Y} + YX + 0 = X(1 + \overline{Y} + Y) = X$ Applying the distributive law to $(X + Y)(X + \overline{Y})$ : we get $XX + X\overline{Y} + YX + Y\overline{Y}$ . Using the idempotent law $XX = X$ , the complement law $Y\overline{Y} = 0$ , and the identity law for addition with 0: $X + X\overline{Y} + YX + 0 = X + X\overline{Y} + YX = X(1 + \overline{Y} + Y)$ . Since $\overline{Y} + Y = 1$ and $1 + 1 = 1$ , we get $X(1) = X$ . Choice A incorrectly uses $X^2$ , Choice B omits the $Y\overline{Y} = 0$ step, and Choice D incorrectly factors the expression.
The Boolean identity $A + AB = A$ is known as the absorption law. Which of the following expressions demonstrates the dual form of this absorption law?
Answer: $A(A + B) = A$ showing that multiplication absorbs addition when terms share variables In Boolean algebra, every law has a dual obtained by swapping + with · and 0 with 1. The absorption law $A + AB = A$ has the dual $A(A + B) = A$ . We can verify this: $A(A + B) = AA + AB = A + AB = A$ (using idempotency and the original absorption law). Choice A correctly states this dual form. Choice B is just commutativity, Choice C is the same law with complements (not the dual), and Choice D incorrectly states that $A(A + B) = A + AB$ when it actually equals $A$ .
Which of the following Boolean expressions is NOT equivalent to the others?
Answer: $(A + B)(\overline{A} + \overline{B})$ When you encounter Boolean equivalence problems, your goal is to simplify each expression to its most basic form and compare the results. Boolean algebra follows specific rules like De Morgan's laws, distributive properties, and complement rules. Let's work through each expression systematically. For option A, $(A + B)(\overline{A} + \overline{B})$ , use the distributive property: $A\overline{A} + A\overline{B} + B\overline{A} + B\overline{B}$ . Since $A\overline{A} = 0$ and $B\overline{B} = 0$ , this simplifies to $A\overline{B} + B\overline{A}$ , which is the XOR operation $A \oplus B$ . Option B, $\overline{A}\overline{B} + AB$ , is already in simplified form and represents the XNOR operation $\overline{A \oplus B}$ (true when both inputs are the same). For option C, $\overline{A + B} + \overline{\overline{A} + \overline{B}}$ , apply De Morgan's law. The first term $\overline{A + B} = \overline{A}\overline{B}$ . The second term $\overline{\overline{A} + \overline{B}} = AB$ (by De Morgan's law again). So this becomes $\overline{A}\overline{B} + AB$ , which matches option B. Option D, $\overline{A \oplus B}$ , is literally the XNOR operation, equivalent to $\overline{A}\overline{B} + AB$ . Options B, C, and D all simplify to $\overline{A}\overline{B} + AB$ (XNOR), while option A simplifies to $A\overline{B} + B\overline{A}$ (XOR). These are complements of each other. Study tip: When checking Boolean equivalence, always simplify to sum-of-products form and watch for XOR versus XNOR patterns—they're frequently confused on exams.
Which Boolean algebra identity is demonstrated by the equivalence $A(B + C) + \overline{A}(B + C) = B + C$ ?
Answer: The distributive law in reverse, factoring out common terms from Boolean sum expressions The expression $A(B + C) + \overline{A}(B + C) = B + C$ demonstrates the distributive law applied in reverse (factoring). We can factor out the common term $(B + C)$ : $A(B + C) + \overline{A}(B + C) = (A + \overline{A})(B + C)$ . Since $A + \overline{A} = 1$ by the complement law, we get $1 \cdot (B + C) = B + C$ by the identity law. This is factoring (reverse distribution), not forward distribution. The complement law is involved but as a supporting step, not the main identity demonstrated.
Consider the Boolean function $F(a,b,c) = a\overline{b}c + \overline{a}bc + abc + \overline{a}\overline{b}\overline{c}$ . Using Boolean algebra identities, which expression represents the complement $\overline{F(a,b,c)}$ ?
Answer: $ab\overline{c} + \overline{a}b\overline{c} + a\overline{b}\overline{c} + \overline{a}\overline{b}c$ F(a,b,c) contains the minterms 101, 011, 111, and 000 (reading abc). For a 3-variable function, there are 8 possible minterms (000 through 111). The complement F̄ must contain the remaining minterms: 001, 010, 100, and 110. These correspond to āb̄c, ābc̄, ab̄c̄, and abc̄ respectively. Choice B lists these exact terms. Choice A incorrectly includes abc instead of abc̄. Choice C incorrectly includes abc. Choice D has the right terms but in a different order - checking carefully, it matches choice B.
The Boolean expression $\overline{\overline{A}B + A\overline{B}} \cdot (A + B)$ simplifies to which of the following?
Answer: $AB$ When simplifying Boolean expressions, your goal is to systematically apply Boolean algebra laws to reduce the expression to its simplest form. This problem tests your ability to work with complements, distribution, and absorption laws. Let's simplify $\overline{\overline{A}B + A\overline{B}} \cdot (A + B)$ step by step. First, apply De Morgan's law to the complement: $\overline{\overline{A}B + A\overline{B}} = \overline{\overline{A}B} \cdot \overline{A\overline{B}}$ . Using De Morgan's again: $= (A + \overline{B}) \cdot (\overline{A} + B)$ . Now our expression becomes: $(A + \overline{B}) \cdot (\overline{A} + B) \cdot (A + B)$ . Expanding the first two terms using distribution: $(A + \overline{B}) \cdot (\overline{A} + B) = A\overline{A} + AB + \overline{A}\overline{B} + \overline{B}B = 0 + AB + \overline{A}\overline{B} + 0 = AB + \overline{A}\overline{B}$ . So we have: $(AB + \overline{A}\overline{B}) \cdot (A + B)$ . Distributing: $AB(A + B) + \overline{A}\overline{B}(A + B) = AB + AB + \overline{A}\overline{B}A + \overline{A}\overline{B}B = AB + 0 + 0 = AB$ . Choice A gives the intermediate step but isn't fully simplified. Choice B shows $AB + \overline{A}\overline{B}$ , which is what we had before applying the final $(A + B)$ term. Choice C represents the original expression $\overline{A}B + A\overline{B}$ (exclusive OR) multiplied by $(A + B)$ , but doesn't account for the complement. Choice D correctly gives $AB$ , the final simplified result. Remember: when simplifying Boolean expressions, work systematically through complement laws, distribution, and always check if further reduction is possible using absorption or consensus laws.
Which of the following demonstrates a correct application of the consensus theorem in Boolean algebra? The consensus theorem states that $xy + \overline{x}z + yz = xy + \overline{x}z$ .
Answer: $(a + b)(\overline{a} + c)(b + c) = (a + b)(\overline{a} + c)$ The consensus theorem has a dual form for products: (x + y)(x̄ + z)(y + z) = (x + y)(x̄ + z). Choice C correctly applies this dual form where x = a, y = b, z = c, giving (a + b)(ā + c)(b + c) = (a + b)(ā + c). Choice A incorrectly applies the theorem because the 'd' term is independent. Choice B has the wrong structure - it should be xy + x̄z + yz form, but has xyz̄ + x̄yz + z which doesn't fit. Choice D uses the absorption law (A + AB = A), not consensus, since bc is absorbed by abc + ābc = bc(a + ā) = bc.
In Boolean algebra, the expression $(A + B)(\overline{A + B})$ simplifies to which of the following?
Answer: $0$ by the complement law since we have a term and its complement The expression $(A + B)(\overline{A + B})$ has the form $X \cdot \overline{X}$ where $X = A + B$ . By the complement law in Boolean algebra, $X \cdot \overline{X} = 0$ for any Boolean expression $X$ . Therefore, $(A + B)(\overline{A + B}) = 0$ . Choice A shows an incorrect expansion, Choice C stops at an intermediate step without completing the simplification, and Choice D gives the wrong result (that would be XOR of A and B).

Start this quiz