Boolean Algebra

Show your work for each problem.

1.
Which law says $A \land \neg A = 0$ ?
1. a)Complement law
2. b)Idempotent law
3. c)Absorption law
4. d)Identity law
Answer: Complement law
The complement law: a variable AND its own negation is always 0, because $A$ and $\neg A$ are never both true. Its OR form is $A \lor \neg A = 1$ .
2.
What is $A \lor 1$ , whatever the value of $A$ ? Enter 1 for true or 0 for false.
Answer: 1
Null (domination) law: $A \lor 1 = 1$ . If $A = 0$ , then $0 \lor 1 = 1$ ; if $A = 1$ , then $1 \lor 1 = 1$ .
3.
Simplify $(A \lor 0) \land (B \lor 1)$ and check two rows.
Answer: 0
1. By the null law, $B \lor 1$ is a constant. Which one? Enter 0 or 1. 1
2. So the expression is $A \land 1 = A$ . Check: what is the original expression for $A = 1$ , $B = 0$ ? 1
3. And for $A = 0$ , $B = 0$ ? 0
4.
$A \lor A$ simplifies to:
1. a) $2A$
2. b) $A$
3. c) $\neg A$
4. d) $A^2$
Answer: $A$
Idempotent law: $A \lor A = A$ , because $0 \lor 0 = 0$ and $1 \lor 1 = 1$ . $2A$ and $A^2$ come from ordinary algebra and do not apply here.
5.
Simplify $\neg\neg A \land 0$ . The result is a constant: enter 0 or 1.
Answer: 0
Double negation gives $\neg\neg A = A$ , and the null law gives $A \land 0 = 0$ . The value of $A$ does not matter.
6.
Check De Morgan's law $\neg(A \land B) = \neg A \lor \neg B$ for $A = 1$ and $B = 0$ .
Answer: 1
1. What is $A \land B$ ? 0
2. So what is $\neg(A \land B)$ ? 1
3. What is $\neg A$ ? 0
4. What is $\neg A \lor \neg B$ ? 1
7.
Which expression is equivalent to $\neg(A \lor B)$ ?
1. a) $\neg A \land \neg B$
2. b) $A \land B$
3. c) $\neg A \lor \neg B$
4. d) $\neg A \lor B$
Answer: $\neg A \land \neg B$
De Morgan's law: $\neg(A \lor B) = \neg A \land \neg B$ . NOT (A OR B) is true only when neither is true. $\neg A \lor \neg B$ is the negation of $A \land B$ instead.
8.
Which expression equals $A \lor (B \land C)$ ?
1. a) $A \land (B \lor C)$
2. b) $(A \lor B) \land C$
3. c) $(A \lor B) \land (A \lor C)$
4. d) $(A \land B) \lor (A \land C)$
Answer: $(A \lor B) \land (A \lor C)$
Distributive law (OR over AND): $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ . Check $A = 1$ : both sides are 1. Check $A = 0$ : both sides are $B \land C$ .
9.
What is the value of $\neg(A \land \neg B)$ for $A = 1$ and $B = 0$ ? Enter 0 or 1.
Answer: 0
$\neg B = 1$ , so $A \land \neg B = 1 \land 1 = 1$ and $\neg 1 = 0$ . With De Morgan: $\neg A \lor B = 0 \lor 0 = 0$ , the same value.
10.
$(A \land B) \lor (A \land \neg B)$ simplifies to $A$ . Counting one gate for each $\land$ , $\lor$ and $\neg$ , how many gates does the simplification save?
Answer: 4
Original: two AND, one NOT and one OR, so 4 gates. $A$ needs 0 gates. Saved: $4 - 0 = 4$ .
11.
Check the absorption law $A \land (A \lor B) = A$ row by row.
Answer: 2
1. For $A = 0$ , what is $A \land (A \lor B)$ , whatever $B$ is? 0
2. For $A = 1$ and $B = 0$ , what is $A \land (A \lor B)$ ? 1
3. For $A = 1$ and $B = 1$ ? 1
4. In how many of the 4 rows is $A \land (A \lor B)$ true? 2
12.
Simplify $(A \lor B) \land (A \lor \neg B)$ and check it.
Answer: 2
1. The distributive law gives $A \lor (B \land \neg B)$ . What constant is $B \land \neg B$ ? Enter 0 or 1. 0
2. So the expression is $A \lor 0 = A$ . Check the row $A = 0$ , $B = 1$ : what is the original expression? 0
3. Check the row $A = 1$ , $B = 0$ : 1
4. In how many of the 4 rows is the original expression true? 2
13.
Simplify $\neg(A \lor \neg B)$ with De Morgan's law.
Answer: 1
1. De Morgan's law gives $\neg A \land \neg\neg B$ . How many $\neg$ signs does this form have? 3
2. After double negation the expression is $\neg A \land B$ . How many $\neg$ signs are left? 1
3. $\neg A \land B$ is true in only one row. What is $A$ in that row? Enter 0 or 1. 0
4. And what is $B$ in that row? 1
14.
Which expression is NOT equivalent to $A$ ?
1. a) $(A \lor B) \land (A \lor \neg B)$
2. b) $A \lor (A \land B)$
3. c) $A \land (A \lor B)$
4. d) $A \lor (\neg A \land B)$
Answer: $A \lor (\neg A \land B)$
The first two are the absorption laws, and $(A \lor B) \land (A \lor \neg B) = A \lor (B \land \neg B) = A$ . But $A \lor (\neg A \land B) = (A \lor \neg A) \land (A \lor B) = A \lor B$ , which is 1 for $A = 0$ , $B = 1$ .
15.
In how many of the 4 rows is $(A \lor B) \land (A \lor \neg B) \land (\neg A \lor B)$ true?
Answer: 1
$(A \lor B) \land (A \lor \neg B) = A$ . Then $A \land (\neg A \lor B) = (A \land \neg A) \lor (A \land B) = 0 \lor (A \land B) = A \land B$ , which is true only in the row $A = 1$ , $B = 1$ .
16.
Simplify $\neg(A \land B) \land (A \lor \neg B)$ and count the gates saved.
Answer: 4
1. De Morgan gives $(\neg A \lor \neg B) \land (A \lor \neg B)$ , and the distributive law gives $\neg B \lor (\neg A \land A)$ . What constant is $\neg A \land A$ ? 0
2. So the expression is $\neg B \lor 0 = \neg B$ . Check $A = 1$ , $B = 1$ : what is the original expression? 0
3. Check $A = 0$ , $B = 0$ : 1
4. Counting one gate for each $\land$ , $\lor$ and $\neg$ , how many gates does the original expression use? 5
5. How many gates are saved by using $\neg B$ instead? 4
17.
Simplify $A \lor (\neg A \land B)$ .
Answer: 3
1. The distributive law gives $(A \lor \neg A) \land (A \lor B)$ . What constant is $A \lor \neg A$ ? 1
2. So the expression is $1 \land (A \lor B) = A \lor B$ . Check $A = 0$ , $B = 1$ : what is the original expression? 1
3. In how many of the 4 rows is $A \lor B$ true? 3
18.
Simplify $(A \land B) \lor (A \land \neg B \land C)$ and count its true rows.
Answer: 3
1. Factoring out $A$ gives $A \land (B \lor (\neg B \land C))$ , and the distributive law turns the bracket into $(B \lor \neg B) \land (B \lor C)$ . What constant is $B \lor \neg B$ ? 1
2. So the expression is $A \land (B \lor C)$ . Counting one gate for each $\land$ , $\lor$ and $\neg$ , how many gates does it use? 2
3. A table for $A$ , $B$ and $C$ has 8 rows. In how many of them is $A = 1$ ? 4
4. Among those rows, $B \lor C$ is false only when $B = 0$ and $C = 0$ . In how many rows is the expression true? 3