0
$\begingroup$

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!

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – MJD Nov 11 '18 at 18:00
  • $\begingroup$ I would first try looking only at triples $(a,a,a)$ where $a=T$ or $a=F$. $\endgroup$ – Somos Nov 11 '18 at 18:18
1
$\begingroup$

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))$$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – J. Clarke Nov 11 '18 at 20:20
  • $\begingroup$ @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$ $\endgroup$ – Bram28 Nov 11 '18 at 20:25
0
$\begingroup$

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)$.

$\endgroup$

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.