# how to prove an operators' set isn't functionally complete

let $$G(\alpha, \beta, \gamma)$$ be a logical operator that get the truth value of the majority of the propositions $$\alpha, \beta, \gamma$$, e.g if $$\alpha = T, \beta = F, \gamma= T \Longrightarrow G(\alpha, \beta, \gamma)=T$$ and $$\alpha = F, \beta = F, \gamma= T \Longrightarrow G(\alpha, \beta, \gamma)=F$$. I need to prove that the set $$\{\neg, G\}$$ isn't a functionally complete set of operators.

I tried assuming that the set is functionally complete and reach a contradiction. If the set is indeed functionally complete then any propositional logic formula is equivalent to a formula using only the two operators $$\neg$$ and $$G$$ and if I can show that there is a formula that don't have an equivalent then the set isn't functionally complete. $$\{\neg, \vee \}$$ is a minimal functionally complete set so if I can find a formula that uses only $$\neg$$ and $$\vee$$ that doesn't have an equivalent using $$\neg$$ and $$G$$, I'll reach a contradiction and prove that $$\{\neg, G\}$$ isn't functionally complete, but how can I prove that there is no such formula (using $$\neg$$ and $$G$$)? there are infinite valid formulas with only $$\neg$$ and $$G$$ how can I prove that none of those is equivalent to, for example, $$(\varphi\vee\psi)$$?

Hint: Consider formulas you can build from $$G$$ and $$\neg$$ using only two propositional variables. What can you say about $$G(\alpha,\beta,\gamma)$$ when $$\alpha,\beta,$$ and $$\gamma$$ are each either one of the two propositional variables or their negation?
Prove by induction that any formula built from $$G$$ and $$\neg$$ using only two propositional variables actually depends on only one of the variables.
• I think I get what you're trying to hint to: if $\varphi$ and $\psi$ propositions then any $G$ with these two or their negation will be equivalent to one of $\varphi$/$\neg\varphi$/$\psi$/$\neg\psi$ and I can show it in truth tables, but I don't understand how I can prove it – CforLinux Apr 20 at 18:46