# Propositional Calculus : Showing $\{ \lnot, \# \}$ is not complete

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.

• You can show that the $\#$ operator is a combination of the $\wedge$ and $\vee$ operators $\#pqr \equiv (p \wedge q) \vee (p \wedge r) \vee (q \wedge r)$...don't know if that helps (but it seems like it should). Sep 6 '14 at 2:43
• @Jared: Unfortunately it does not. That follows from the completeness of $\{ \lnot, \land, \lor \}$. A formula which uses these three connectives or others but is not representable by $\#$ and $\lnot$ is what I need. Sep 6 '14 at 2:49

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.
• Please could you verify this slightly altered approach. Let $\alpha_{T}$ denote the truth value of $\alpha$ when all its propositional variables are assigned $T$ and let $\alpha_F$ be similarly defined. Would it be correct if I let $S$ be the set of all formulas $\alpha$ such that $\alpha_T \neq \alpha_F$ and use induction to show that $S$ is the set of all formulas generated by $\#$ and $\lnot$ which I think uses a proof similar to yours word to word. Then no formula can model the constant functions $T$ and $F$?? Sep 6 '14 at 10:18
• @Ishfaaq: This sounds good to me. I think it's in fact the same argument, slightly reorganized: note that I in a first step pass from $A(p,q, \ldots ,r)$ to $A(p,p,\ldots , p)$ (I in fact didn't pay attention to this point in the first version, which was sloppy). The same effect is achieved by focusing on $A_T$, $A_F$.