I am having some trouble with one of my courses. For example, one thing I just do not understand is completeness.
I am just looking for maybe alternative explanations by the community.
I am confused about what it means for a set to be n complete. I am also confused how to know which functions exist.
For example, my teacher said for the set containing the negation symbol and the disjunction symbol it is 1 complete and 2 complete. Then he said,
for 1 completeness there are four 1 ary Boolean functions, two constants, 0 and 1, the identity and negation. How did he know these were the four?
Can anyone help to explain these things to me?
I am also generally confused on what a Boolean function is, and what it means for different arity. The definition we are using for completeness is that a set $\phi$ of Boolean functions is n complete if any Boolean function $f:\{0,1\}^{n} \to \{0,1\}$ can be expressed by $\phi$
Thanks
Let's start with the easy question: how many Boolean operations of a given arity are there?
Well, by definition, each of the inputs to a Boolean operation is either True or False. So there are $2^n$ possible inputs you can give to an $n$-ary Boolean operation. For instance, the $2^2$ possible inputs for a $2$-ary Boolean operation are
True, True
True, False
False, True
False, False
Now, what sort of output can a Boolean operation give? Again, either True or False.
So we can think of an $n$-ary operation is just a map from a $2^n$-element set to a $2$-element set. In general, the number of maps from an $A$-element set to a $B$-element set is $B^A$ (why?), so this says that the number of $n$-ary Boolean operations is $2^{(2^n)}$. (Note that this is not the same as $(2^2)^n$.) For instance, there are $2^{(2^1)}=2^2=4$ unary Boolean operations, just like your teacher says.
Now, what does completeness mean?
Well, we can combine Boolean operations (via composition) to get new Boolean operations. For instance, let "$\vee$" be the Boolean operation of disjunction ("or"), and "$\neg$" be negation ("not"). Then we can define "$\implies$" (implication) as $a\implies b:=(\neg a)\vee b$, or $$\vee(\neg(a), b)$$ (the former is how we usually write it, the latter makes the composition structure clear - first apply $\neg$ to $a$, then feed the result of that, and $b$, to $\vee$).
A collection $S$ of Boolean operations is complete if any Boolean operation can be built out of operations from $S$. It might be surprising to you that there even are finite complete collections of Boolean operations! But this is in fact true: e.g. from $\neg$ and $\vee$, it turns out we can build any Boolean operation you want!
I don't know what "$n$-complete" means, however; for that you'll have to consult your notes. If you edit your question to include a definition of $n$-completeness, however, I can help explain what it means. (One guess I have is that $n$-complete means that you can build all the $n$-ary operations; however, that seems a bit silly, since $n$-complete and complete are then the same for $n>1$.)
A slight omission: when I talk about "Boolean operations," I am assuming we are looking at non-nullary operations - that is, all the operations we consider take in at least one input. See https://en.wikipedia.org/wiki/Functional_completeness#Formal_definition for a brief discussion of why.