Boolean function in Math Logic

Question

I wish to find how many Boolean functions can be formed by using input variables $x_1, \ldots , x_n$ and the constants & connectives from i) $\{0, 1, \wedge\}$ and ii) $\{0, 1, \lnot, \oplus\}.$ Is it $2^{2^3}$ and $2^{2^4}$?

Answer 1

The number of distinct functions that are conjunctions of $x_1,\ldots,x_n$ equals the number of nonempty subsets of $\{\,x_1,\ldots,x_n\,\}$. Adding $1$ and $0$, we get $2^{n}+1$.

Likewise, there are $2^n-1$ distinct functions that are exclusive ORs of $x_1,\ldots,x_n$. Allowing negation doubles the number, because only the parity of the number of negations matters. Adding again $0$ and $1$, we get $2^{n+1}$.

Answer 2

The binary function $\wedge$ is associative, commutative, and idempotent.   $1$ is the identity element and $0$ the annihlator. $$a\wedge (b\wedge c)=(a\wedge b)\wedge c\\ a\wedge b=b\wedge a\\ a\wedge a=a \\ a\wedge 1 = a\\ a\wedge 0=0$$

From $[x_1]$ I can construct 3 nonequivalent functions with $\{0,1,\wedge\}$: $$0, 1, x_1$$

From $[x_1,x_2]$ I can construct 5 nonequivalent functions: $$0, 1, x_1, x_2, (x_1\wedge x_2)$$

From $[x_1,x_2,x_3]$ I can construct 9 nonequivalent functions: $$0, 1, x_1, x_2, x_2, (x_1\wedge x_2), (x_1\wedge x_3), (x_2\wedge x_3), ((x_1\wedge x_2)\wedge x_3)$$

A pattern is emmerging, so I assert that with $n$ arguments I can construct $1+2^n$ nonequivalent functions. That is $1$ plus the number of subsets for a set with $n$ elements. Can you see why?

---

The relevant properties of the binary operator $\oplus$ (exclusive or) and $\neg$ (complementation) and constants $0$ and $1$ are:

$${a\oplus b = b\oplus a \\ (a\oplus b)\oplus c = a\oplus (b\oplus c)\\ a \oplus a = 0 \\ a\oplus 1 = \neg a \\ a \oplus 0 = a }\quad{ \neg 1 = 0\\ \neg 0=1\\ \neg\neg a = a}\quad{a\oplus \neg a = 1 \\ \neg(a\oplus b)= a\oplus\neg b\\ a\oplus \neg b = \neg a \oplus b\\ a\oplus b = \neg a\oplus \neg b}$$

From $[x_1]$ I can construct four non-equivalent functions with $\{0,1,\neg, \oplus\}$: $$0, 1, x_1, \neg x_1$$

From $[x_1, x_2]$ I can construct eight non-equivalent functions with $\{0,1,\neg, \oplus\}$: $$0, 1, x_1, \neg x_1, x_2, \neg x_2, (x_1\oplus x_2), \neg(x_1\oplus x_2)$$

And so on. Can you spot the pattern here?