Consider the following two Boolean Formulas f_1: x_1 and (Tilde x_1 or x_2) and

Question

Consider the following two Boolean Formulas f_1: x_1 and (Tilde x_1 or x_2) and (Tilde x_2 or x_3) and ... and (Tilde x_99 or x_100) f_2: x_1 and (Tilde x_1 or x_2) and (Tilde x_2 or x_3) and ... and (Tilde x_99 or x_100) and Tilde x_100 (a) If you were to write a truth table for f_1, (DO NOT ACTUALLY DO THIS!) how many rows would it have? Why? (b) If you were to write a truth table for f_1, how many rows evaluate to True? Why? (c) If you were to write a truth table for f_2, how many rows evaluate to True? Why? BEGIN YOUR ANSWER TO PROBLEM (5) BELOW THIS LINE

Explanation / Answer

5(a) There are 100 variables from x1 to x100.

Each variable can take either 0 or 1 which means each variable can take 2 values.

So, a total of 2^100 rows (Ans)

5(b) In F1, to have the result as True, each term of the POS must give True value.

When x1 is true, the ~x1 in the second term becomes false and so on. So, the overall result is True only when all the variables are True.

There is only one time when all the variables are True. So, Answer is exactly one row.

5(c) This is same as 5(b) but we have an extra multiplier with ~x100. If you take x100 as True, ~x100 will be false and hence, final result will be false. Similarly if we take x100 as false, ~x100 will be true and hence, final result will again be false.

So, the answer is exactly ZERO rows.

If you face difficulty in understanding any of this, you can ask me in the comment section.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---