Boolean Algebra Questions and Answers

Answer: D

The formula in CNF is (p ∨ q) ∧ (¬r ∨ p).

A formula is in conjunctive normal form when it is a conjunction (AND) of clauses, each clause being a disjunction (OR) of literals, and a literal is a variable or a negated variable. (p ∨ q) and (¬r ∨ p) are both clauses of literals, joined by ∧, so the formula qualifies.

p → q uses the implication connective, which CNF does not allow until it is rewritten as ¬p ∨ q. p ∨ (q ∧ r) has an AND inside an OR, the shape of disjunctive form; its CNF is (p ∨ q) ∧ (p ∨ r). In ¬(p ∧ q) ∨ r the negation applies to a compound expression rather than to a single variable.

Answer: A

The minimal expression is A.

The second term contains both A and its complement, which makes it 0:

\[ \begin{aligned} A + A'BA &= A + (A'A)B \\ &= A + 0 \cdot B \\ &= A + 0 = A \end{aligned} \]

A + B would be the answer to the different expression A + A'B, which is the likely trap. AB and B do not follow, since the term A'BA contributes nothing for any input. A quick check: if A = 1 the expression is 1, and if A = 0 every term contains A or is A, so it is 0; the output always equals A.

Answer: B

De Morgan's law states (AB)' = A' + B'.

The complement of a product is the sum of the complements, and the complement of a sum is the product of the complements: (A + B)' = A'B'.

The other options complement only one variable or none: (A + B)' = A'B leaves B uncomplemented, (AB)' = A' + B misses B', and (AB)' = A + B complements nothing.

De Morgan's laws let any AND-OR expression be rewritten with NAND or NOR gates, which is why they matter in digital design.

Answer: B

The identity that is not valid is (x+y)⊕z = x⊕(y+z).

Take x = 1, y = 1, z = 0. The left side is (1 + 1)⊕0 = 1⊕0 = 1, while the right side is 1⊕(1 + 0) = 1⊕1 = 0. The two sides differ, so OR and XOR cannot be regrouped this way.

The others hold: XOR is associative; when xy = 0 the two inputs are never both 1, so XOR equals OR; and x⊕y is the complement of XNOR, (xy + x'y')'.

Answer: A

The number of Boolean functions is \(2^{2^{n}}\).

With n Boolean variables there are \(2^{n}\) rows in the truth table. A function assigns 0 or 1 to each row independently, so there are

\[ 2 \times 2 \times \cdots \times 2 = 2^{2^{n}} \]

functions. For n = 2 that is 16. \(n^{2^{n}}\) and \(2^{n!}\) count the wrong things, and since only one expression is right, 'More than one of these' is wrong.

Answer: C

The expression not equivalent to p ↔ q is (¬ p ∧ q) ∨ (p ∧ ¬ q).

That expression is true exactly when p and q differ, which is exclusive OR, the negation of p ↔ q.

The others are equivalent. (¬p ∨ q) is p → q and (p ∨ ¬q) is q → p, so their conjunction is p ↔ q, and option B writes the same thing with q → p. (¬p ∧ ¬q) ∨ (p ∧ q) is true exactly when p and q are equal, which is again p ↔ q.

Answer: A

A + 0 = A is the identity law.

The identity laws say that ORing a variable with 0, or ANDing it with 1, leaves it unchanged: A + 0 = A and A · 1 = A. 0 is the identity element for OR, as 1 is for AND.

The annulment (null) laws are A + 1 = 1 and A · 0 = 0. The complement laws are A + A' = 1 and A · A' = 0. The idempotent laws are A + A = A and A · A = A.

Answer: C

A(A+B) simplifies to A.

Multiply out and use the idempotent and absorption laws:

\[ \begin{aligned} A(A+B) &= AA + AB \\ &= A + AB \\ &= A(1 + B) = A \end{aligned} \]

This is the absorption law. A check with a truth table agrees: when A = 0 the expression is 0, and when A = 1 it is 1 whatever B is. A+B and B depend on B, so they are wrong, and AB is 0 when A = 1 and B = 0, where the expression is 1.