There are 2^(2^n) different truth tables that can be constructed using the Boole

Question

There are 2^(2^n) different truth tables that can be constructed using the Boolean variables x1, . . . , xn, the operations , , ¬, and parentheses. What happens to this 2^(2^n) if we do not allow the use of the NOT operation “¬”? For n = 1 we only have one possible table, corresponding to the formula 1 = x1. For n = 2 we have four possibilities: 1 = x1, 2 = x2, 3 = x1 x2, or 4 = x1 x2. How many possibilities are there for n = 3? Give the number, list the corresponding formulæ, and explain how you derived this answer.

Explanation / Answer

For n = 3, There are 9 possibilities

List of formulae:

1 = x1, 2 =x2 , 3 =x3 ,

4 =x1^x2 , 5 =x2^x3 , 6 =x1^x3 ,

7 =x1Vx2 , 8 =x2Vx3 , 9 =x1Vx3

Explanation:

n = 3 means, there are 3 variables : x1, x2 and x3

1 = x1, 2 = x2 , 3 = x3 makes three possibilities

Similarly there are three possibilities for the AND ^ Operation

and three more possibilities for the OR V operation

Hence 3 + 3 + 3 = 9

one truth table for 2 variable and one operation V

3 truth tables for 3 variables and one operation

x1 x2 xn-1 xn ^ V Not () Remove NOT Operation

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.