Boolean Expressions

Show your work for each problem.

1.
In $A \lor B \land \neg C$ (no parentheses), which operation is done first?
1. a)AND ( $\land$ )
2. b)OR ( $\lor$ )
3. c)NOT ( $\neg$ )
4. d)Left to right, so OR
Answer: NOT ( $\neg$ )
NOT is done first: $\neg C$ . Then AND: $B \land \neg C$ . OR comes last.
2.
Evaluate $A \land B$ for $A = 1$ and $B = 0$ . Answer 1 for true or 0 for false.
Answer: 0
$1 \land 0 = 0$ , because $B$ is 0.
3.
Evaluate $A \lor \neg B$ for $A = 0$ and $B = 0$ . Answer 1 for true or 0 for false.
Answer: 1
$\neg 0 = 1$ , so $0 \lor 1 = 1$ .
4.
How many rows does the truth table of an expression with the variables $A$ , $B$ and $C$ have?
1. a)3
2. b)6
3. c)9
4. d)8
Answer: 8
3 variables give $2^3 = 2 \times 2 \times 2 = 8$ rows, not $2 \times 3 = 6$ .
5.
Evaluate $A \land \neg B$ for $A = 1$ and $B = 1$ . Answer 1 for true or 0 for false.
Answer: 0
1. NOT first: what is $\neg B$ for $B = 1$ ? 0
2. Now AND: what is $1 \land 0$ ? 0
6.
Evaluate $\neg A \lor B$ for $A = 0$ and $B = 0$ . Answer 1 for true or 0 for false.
Answer: 1
1. What is $\neg A$ for $A = 0$ ? 1
2. What is $1 \lor 0$ ? 1
7.
Which expression means the same as $A \lor B \land C$ ?
1. a) $(A \land B) \lor C$
2. b) $(A \lor B) \land C$
3. c) $A \land (B \lor C)$
4. d) $A \lor (B \land C)$
Answer: $A \lor (B \land C)$
AND is done before OR, so the parentheses go around $B \land C$ : $A \lor (B \land C)$ .
8.
Evaluate $A \lor B \land C$ for $A = 1$ , $B = 1$ , $C = 0$ . Answer 1 for true or 0 for false.
Answer: 1
$B \land C = 1 \land 0 = 0$ , then $1 \lor 0 = 1$ . Working left to right would wrongly give $(1 \lor 1) \land 0 = 0$ .
9.
Evaluate $\neg(A \land B) \lor C$ for $A = 1$ , $B = 1$ , $C = 0$ . Answer 1 for true or 0 for false.
Answer: 0
1. Parentheses first: what is $A \land B$ ? 1
2. What is $\neg(A \land B)$ ? 0
3. What is $0 \lor C$ for $C = 0$ ? 0
10.
Evaluate $\neg A \land B \lor A \land \neg B$ for $A = 1$ and $B = 0$ . Answer 1 for true or 0 for false.
Answer: 1
1. What is $\neg A$ ? 0
2. What is $\neg B$ ? 1
3. What is $\neg A \land B$ ? 0
4. What is $A \land \neg B$ ? 1
5. OR last: what is the value of the whole expression? 1
11.
In how many rows of its truth table is $\neg A \land B$ equal to 1?
Answer: 1
$\neg A \land B = 1$ only when $A = 0$ and $B = 1$ : that is 1 row out of 4.
12.
What is the final column of $A \lor \neg B$ for the rows $AB$ = 00, 01, 10, 11?
1. a)0, 1, 1, 1
2. b)1, 0, 1, 1
3. c)1, 1, 0, 1
4. d)0, 1, 0, 0
Answer: 1, 0, 1, 1
$A$ : 0, 0, 1, 1 OR $\neg B$ : 1, 0, 1, 0 gives 1, 0, 1, 1. The expression is 0 only when $A = 0$ and $B = 1$ .
13.
Build the truth table of $\neg(A \lor B)$ . In how many rows is it equal to 1?
Answer: 1
1. How many rows does the table have? 4
2. In how many rows is $A \lor B$ equal to 1? 3
3. NOT flips every row. In how many rows is $\neg(A \lor B)$ equal to 1? 1
14.
In how many rows of its truth table is $A \land B \lor C$ equal to 1?
Answer: 5
$C = 1$ in 4 of the 8 rows. Among the rows with $C = 0$ , only $A = B = 1$ (row 110) gives $A \land B = 1$ . Total: $4 + 1 = 5$ rows.
15.
Build the truth table of $A \land (B \lor C)$ . In how many rows is it equal to 1?
Answer: 3
1. How many rows does the table have? 8
2. In how many rows is $B \lor C$ equal to 1? 6
3. Now AND with $A$ : in how many rows are both $A$ and $B \lor C$ equal to 1? 3
16.
Build the truth table of $A \land B \lor A \land \neg B$ . Which expression is equivalent to it?
1. a) $A \land B$
2. b) $A$
3. c) $A \lor B$
4. d) $B$
Answer: $A$
For $AB$ = 00, 01, 10, 11: $A \land B$ is 0, 0, 0, 1 and $A \land \neg B$ is 0, 0, 1, 0. OR gives 0, 0, 1, 1, which is exactly the column of $A$ .
17.
Compare the truth tables of $A \lor B \land C$ and $(A \lor B) \land C$ . In how many rows do they differ?
Answer: 2
1. How many rows does each table have? 8
2. In how many rows is $A \lor (B \land C)$ equal to 1? 5
3. In how many rows is $(A \lor B) \land C$ equal to 1? 3
4. In how many rows do the two final columns differ? 2
18.
Evaluate $\neg(A \land B \lor \neg C)$ for $A = 1$ , $B = 0$ , $C = 1$ . Answer 1 for true or 0 for false.
Answer: 1
1. Inside the parentheses, NOT first: what is $\neg C$ ? 0
2. Then AND: what is $A \land B$ ? 0
3. Then OR: what is the value inside the parentheses? 0
4. Finally the outer NOT: what is the value of the whole expression? 1