There is a result in Robert Reckhow's thesis that characterizes the adequate sets of connectives. The result says that for a set of connectives to be complete one needs the following:
- F and T (or formulas with these values),
- an odd connective (a connective is called odd if some fixing of its input variables with T and F except two input variables has odd number of Ts in its truth table),
- a non-monotone connective (a connective that turning an F to a T will make its value change from T to F).
These are necessary and sufficient conditions for a set of connectives to be adequate. If a set of connectives is not adequate then it lacks one of these. If you have an odd connective, you can fix the inputs with T and F to get either $\vee$ or $\wedge$. If you have a non-monotone connective, you can fix the inputs with T and F to get $\lnot$. Any boolean function can then be constructed from these as a CNF.
Note that even connectives are closed under composition as well as monotone connectives. So to prove that a set of connectives is inadequate, you typically need to show that either
- all of the connectives are monotone, or
- all of the connectives are even.
For your examples, the first one is a set of monotone connectives, the second one is a set of even connective. So they cannot be adequate.
Consider just two propositional variables, say $p$ and $q$, and let's see what truth-functions of these we can express using $\neg$ and $G$. Using just $\neg$, we have $p,q,\neg p,\neg q$. Now let's apply $G$ to any triple of these, say $G(x,y,z)$. If two of $x,y,z$ are the same, the $G$ just produces that same one of $p,q,\neg p,\neg q$ as its output. So the only way to get anything new would be if $x,y,z$ are distinct elements of $\{p,q,\neg p,\neg q\}$. But then, since only one of $p,q,\neg p,\neg q$ is missing from $x,y,z$, this triple would contain either both $p$ and $\neg p$ or both $q$ and $\neg q$. But if some two of $x,y,z$ are each other's negations, then $G(x,y,z)$ agrees with the other one of $x,y,z$, so we still get nothing new. Conclusion: The only truth fnctions of $p$ and $q$ that can be expressed using $\neg$ and $G$ are $p,q,\neg p,\neg q$.
Best Answer
Here is the proof that for any $v$ and $\phi$ it is true that $v^C(\phi) \neq v(\phi)$ (i.e. that $v^C(\phi)$ and $v(\phi)$ always have the opposite truth-value).
We take any $v$, and now do structural induction on $\phi$:
Base: $\phi = P$ for some atomic proposition $P$. Given that by definition $v^C(P)$ is the opposite of $v(P)$, we have that $v^C(\phi)$ and $v(\phi)$ have the opposite truth-value as well.
Step: There are two cases to consider:
A. $\phi = \neg \psi$, where by inductive hypothesis we have that $v^C(\psi)$ and $v(\psi)$ have the opposite truth-value. By semantics of $\neg$, we have that $v(\psi)$ and $v(\neg \psi)$ have opposite truth-values, and we also have that $v^C(\psi)$ and $v^C(\neg \psi)$ have opposite truth-values. So, $v^C(\phi) = v^C(\neg \psi)$ has the opposite value of $v^C(\psi)$. But since by inductive hypothesis $v^C(\psi)$ has the opposite value of $v(\psi)$, that means that $v^C(\phi)$ has the same truth-value as $v(\psi)$ .... but that has the opposite truth-value as $v(\phi)$.
B. $\phi = G(\psi_1, \psi_2,\psi_3)$, where by inductive hypothesis we have that $v^C(\psi_i)$ and $v(\psi_i)$ have the opposite truth-value for $1 \leq i \leq 3$. Now, $v^C(\phi)$ evaluates to True iff the majority of $v^C(\psi_i)$ evaluates to True iff (Inductive Hypothesis) the majority of $v(\psi_i)$ evaluates to False iff $v(\phi)$ evaluates to False. (in that last step, we use the fact that $G$ takes an odd number of argument, so there is always either a majority of argument that evaluate to True, or a majority of argument that evaluate to False.). So, $v^C(\phi)$ and $v(\phi)$ will have opposite truth-values.