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)$?
Best Answer
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?
A stronger hint is hidden below: