# Proving that a set of connectives { # , T } is functionally complete / adequate

I am a little bit stuck trying to prove if a set of logical connectives {#, T} is functionally complete. For the ternary connective # we have;

#(a,b,c) = T if there are 2 T's,

#(a,b,c) = F otherwise.

We also have T being the connective 'veritum', where every valuation sends it to true.

Now I have proved completeness or incompleteness of sets including ternary connectives before, but this is one case where I cannot see a way to begin. I think it may be the inclusion of the nullary connective that is throwing me off. Any help would be very much appreciated on this!

• One thing you can try, if you can't think of anything else, is to start writing down simple formulas of $\#$ and $T$, calculate their truth tables, and see if you get anything you recognize. Even if you don't , getting familiar with the two new operations can't hurt. – MJD Nov 11 '18 at 18:00
• I would first try looking only at triples $(a,a,a)$ where $a=T$ or $a=F$. – Somos Nov 11 '18 at 18:18

## 2 Answers

Here's one way to show completeness:

We know that $$\{ \neg, \land \}$$ is a complete set, so let's see if we can capture both $$\neg$$ and $$\land$$ with the $$\#$$ and $$\top$$

Well:

$$\#(a,\top,\top)$$ has already two $$T$$'s, so would be $$T$$ if $$a$$ is F, and $$F$$ if $$a$$ is $$T$$. So, this captures the $$\neg$$, i.e. $$\neg a = \#(a,\top,\top)$$

How about $$\land$$? OK, let's try ... what does $$\#(a,b,c)$$ do? We want it to be true iff $$A$$ and $$b$$ are both T ... so we want $$c$$ to always be $$F$$. OK, so we want that $$c$$ is the opposite of $$\top$$, i.e. $$c$$ should be the negation of $$\top$$. OK, we just saw how to do negation, so make $$c=\#(\top,\top,\top)$$. And so that gives us that: $$a \land b = \#(a,b,\#(\top,\top,\top))$$

• Thank you! I was completely looking over the fact that ⊤ could just be substituted in for a,b,c. Rookie mistake! Out of curiosity, how would you go about proving that # itself is incomplete? I would normally look for a counter-example, but here I'm not too sure how to prove it. – J. Clarke Nov 11 '18 at 20:20
• @J.Clarke You're welcome! :) To show that $\#$ by itself is incomplete, note that it is incapable to capture any function $f$ for which $f(F,F,F)=T$ – Bram28 Nov 11 '18 at 20:25

Hints: It's enough to express negation and conjunction.
We have $$\#(\top, \top, x) =\lnot x$$, in particular, $$\bot=\#(\top, \top, \top)$$.

Try $$\#(\bot, x, y)$$.