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.

  • $\begingroup$ 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). $\endgroup$ – Jared Sep 6 '14 at 2:43
  • 1
    $\begingroup$ @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. $\endgroup$ – Ishfaaq 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.

  • $\begingroup$ 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$?? $\endgroup$ – Ishfaaq Sep 6 '14 at 10:18
  • $\begingroup$ @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$. $\endgroup$ – user138530 Sep 6 '14 at 21:11

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.