Set functions [CNOT, NOT] is functionally complete? Set functions [CNOT, NOT] is functionally complete?
CNOT function:
$CNOT(0, 0) = 0$
$CNOT(0, 1) = 1$
$CNOT(1, 0) = 1$
$CNOT(1, 1) = 0$
NOT function:
$NOT(0) = 1$
$NOT(1) = 0$
If not then what should be added minimal to it?
 A: The complete set must have functions not belonging to


*

*Preserving 0 (check)

*Preserving 1 (check)

*Monotone (check)

*Self-dual (check)

*Linear (uncheck)


Both functions are linear, therefore the set is not complete (linearity is conserved across composition).
A: With this set you can not produce truth tables with an odd number of 1's with two inputs. You need to add a function that has an odd number of ones in the range.
A: Claim: Any binary function $\phi$ defined over two or more variables and using $NOT$ and $CNOT$ only will have an even number of $1$'s and (therefore) an even number of $0$'s in the truth-table.
Proof: Take any such truth-function $\phi$. Since it involves two or more variables, the number of rows in the truth-table is a multiple of 4. By Induction over the syntactic structure of $\phi$ we'll show that any subformula of $\phi$ will have an even number of $1$'s and $0$'s in the truth-table of $\phi$
Base: Take variable $P$.  In the truth-table of $\phi$, exactly half of the times $P$ will be $1$, and the other half it is $0$ (remember: we're looking at what is under the $P$ column in the truth-table for $\phi$). So given that the number of rows in the truth-table is a multiple of 4, there are an even number of $1$'s and an even number of $0$'s for $P$
Step: Let $\psi$ be a subformula of $\phi$. We need to consider two cases:
Case 1: $\psi = NOT(\psi_1)$
By inductive hypothesis, $\psi_1$ has an even number of $1$'s and $0$'s in the truth-table for $\phi$. Since all $T$'s become $F$'s and vice versa when negating, that means that $\psi$ also has an even number of $1$'s and $0$'s in the truth-table for $\phi$.
Case 2: $\psi = CNOT(\psi_1 , \psi_2)$
By inductive hypothesis, $\psi_1$ and $\psi_2$ both have an even number of $1$'s and $0$'s in the truth-table for $\phi$.
Now consider what happens when we evaluate $\psi = \psi_1 \leftrightarrow \psi_2$ in the truth-table for $\phi$. Let us first consider the $m$ rows where $\psi_1$ is $1$. Of those rows, assume that $\psi_2$ is $1$ in $m_1$ of those and hence $0$ in $m_2 = m-m_1$ of those. This gives us $m_1$ $0$'s and $m_2$ $1$'s for $\psi$. Now consider the $n$ rows where $\psi_1$ is $0$. Of those rows, assume that $\psi_2$ is $1$ in $n_1$ of those and hence $0$ in $n_2 = n-n_1$ of those. This gives us $n_1$ $1$'s and $n_2$ $0$'s for $\psi$. So, in total we get $m_1 + n_2$ $1$'s and $m_2 + n_1$ $0$'s for $\psi$.
But, since by inductive hypothesis $\psi_1$ has an even number of $1$'s and $0$'s, we know $m = m_1 + m_2$ and $n = n_1 + n_2$ are both even and thus $m_1$ and $m_2$ have the same parity, and same for $n_1$ and $n_2$. Also, since by inductive hypothesis  $\psi_2$ has an even number of $T$'s and $F$'s in the truth-table, we have that $m_1 + n_1$ and $m_2 + n_2$ are both even, meaning that $m_1$ and $n_1$ have the same parity, and same for $m_2$ and $n_2$. Combining this, that means that $m_1$ and $n_2$ have the same parity, and same for $m_2$ and $n_1$. Hence, $m_1 + n_2$ and $m_2 + n_1$ are both even, meaning that $\psi$ has an even number of $1$'s and $0$'s in the truth-table.
Now that we have proven the claim, we know that you cannot capture functions over two or more variables that have an odd number of $1$'s and an odd number of $0$'s in the truth-table. Hence, $\{ NOT, CNOT \}$ is not expressively complete.
A: NOT has an odd number of 1s. I think what Mosquite means is that you can't get functions which have different numbers of 0s and 1s 
