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?

A stronger hint is hidden below:

Prove by induction that any formula built from $G$ and $\neg$ using only two propositional variables actually depends on only one of the variables.

  • $\begingroup$ 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 $\endgroup$ – CforLinux Apr 20 at 18:46
  • $\begingroup$ I'm not sure what you mean by "prove it" if using truth tables does not suffice. $\endgroup$ – Eric Wofsey Apr 20 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.