Which of the following is not a valid expression of Boolean algebra?
2022
Which of the following is not a valid expression of Boolean algebra?
Answer: B. x * ~y + ~x * y + ~x * ~y = 1 — Concept — an equation in Boolean algebra is a valid identity only when its two sides take the same value for every possible 0/1 combination of its variables.…
- A.
~x + (y * ~z) + x + ~y = 1
- B.
x * ~y + ~x * y + ~x * ~y = 1
- C.
~(x + y + z) = ~x * ~y * ~z
- D.
x * ~y + ~x * y + x * y = x + y
Attempted by 473 students.
Show answer & explanation
Correct answer: B
Concept — an equation in Boolean algebra is a valid identity only when its two sides take the same value for every possible 0/1 combination of its variables. A single combination in which the two sides differ is therefore enough to reject the equation, while accepting it needs equality in general: either reduce one side to the other using the standard laws, or check every row of the truth table.
The laws used below, each stated in the abstract:
Complement Law: A + Ā = 1 and A·Ā = 0
Domination (Null) Law: 1 + A = 1 and 0·A = 0
Identity Law: A·1 = A and A + 0 = A
Distributive Law: A·B + A·C = A·(B + C)
Absorption (Redundancy) Law: A + Ā·B = A + B
De Morgan's Law: ¬(A + B) = Ā·B̄ and ¬(A·B) = Ā + B̄
Application — reduce the left side of each given equation with those laws and compare it with the right side.
~x + (y·~z) + x + ~y = 1
Two of the four terms are complementary literals: ~x + x = 1 by the Complement Law.
The left side becomes 1 + (y·~z) + ~y, and 1 + A = 1 by the Domination Law, so it is 1 whatever x, y and z are.
Left side and right side agree for every input.
x·~y + ~x·y + ~x·~y = 1
Factor ~x out of the last two terms: ~x·y + ~x·~y = ~x·(y + ~y) by the Distributive Law.
y + ~y = 1 by the Complement Law and ~x·1 = ~x by the Identity Law, so the left side reduces to x·~y + ~x.
x·~y + ~x is not the constant 1: at x = 1, y = 1 it is (1·0) + 0 = 0, while the right side is 1.
Left side and right side disagree at x = 1, y = 1.
~(x + y + z) = ~x·~y·~z
De Morgan's Law states that the complement of an OR is the AND of the complements, so ~(x + y + z) = ~x·~y·~z.
Left side and right side agree for every input — this equation is the law itself.
x·~y + ~x·y + x·y = x + y
Group the two terms containing y: ~x·y + x·y = y·(~x + x) = y·1 = y, using the Distributive, Complement and Identity Laws.
The left side becomes x·~y + y, which is y + ~y·x = y + x by the Absorption Law.
Left side and right side agree for every input.
Truth table — exactly one of those four reductions failed to settle to a constant, so write that one out row by row. It involves x and y only, so four rows cover every case:
x | y | x·~y | ~x·y | ~x·~y | Left side | Right side |
|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 0 | 1 |
Three rows give 1, but the row x = 1, y = 1 gives 0 while the right side stays 1. One disagreeing row is enough: the equation is not an identity.
Cross-check — run the same four rows through x·~y + ~x·y + x·y: it gives 0, 1, 1, 1, and x + y gives 0, 1, 1, 1 as well, so those two sides agree in every row. The equation ~x + (y·~z) + x + ~y = 1 collapses to the constant 1 because it contains both x and ~x, and ~(x + y + z) = ~x·~y·~z is De Morgan's Law itself, valid by definition. Exactly one of the four given equations breaks down.
Result — the expression that is not a valid Boolean identity is x·~y + ~x·y + ~x·~y = 1, because it fails at x = 1, y = 1. Each of the other three holds for every input: ~x + (y·~z) + x + ~y = 1 by the Complement and Domination Laws, ~(x + y + z) = ~x·~y·~z by De Morgan's Law, and x·~y + ~x·y + x·y = x + y by the Absorption Law.