Let the ternary connective $ \# $ stand for the majority connective. Accordingly, the truth value of $ (\# p q r) $ is $T$ if a majority of $p, q, r$ are true. $(\#pqr)$ is false if a majority of $p, q, r$ is false. I am having trouble to prove:
Show that the set $\{ \lnot , \#\}$ is not complete.
By completeness we mean the ability to come up with a propositional formula using only these connectives that represents any Boolean function. The set $ \{ \lnot , \lor, \land \} $ is complete since every propositional formula is logically equivalent to one that uses only these connectives.
I believe any formula using only those two connectives does not realise the constant truth and falsity functions. But I am unable to prove it. Just a hint would be great. Thanks in advance.
Your idea works, as follows: We can show by induction on the complexity that there is no formula $A$ that takes the truth value $t$ under all valuations. First of all, if there was such a formula, then we could also find one with just one propositional variable $p$ (just substitute $p$ for all variables).
Now it's clear that $A=p$ is not constant (= basis). Similarly, $B=\lnot A$ is not constant if $A$ has this property.
Finally, consider $A=\#(BCD)$: if $A(p=t)=t$, then at least two of $B,C,D$ (let's say $B$ and $C$) also satisfy $B(t)=C(t)=t$. By the IH, $B(f)=C(f)=f$, so $A(f)=f$, and $A$ is not constant.