1

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.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
  • 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). – Jared Sep 06 '14 at 02:43
  • 1
    @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. – Ishfaaq Sep 06 '14 at 02:49

1 Answers1

1

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$?? – Ishfaaq Sep 06 '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$. –  Sep 06 '14 at 21:11