3
$\begingroup$

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$.

For example:
$G(T,T,F)=T$ since there are more $T$'s than $F$'s
and $G(F,F,T)=F$ since there are more $F$'s than $T$'s

It seems that we cannot express tautologies and contradictions with this set of connectives but when I tried to prove it (using structural induction) I got stucked.

Thanks for any hint or help.

$\endgroup$
5
  • $\begingroup$ How exactly are you defining functional completeness? $\endgroup$
    – Git Gud
    Apr 25, 2015 at 18:01
  • $\begingroup$ @Git Gud: it's a standard notion. See en.wikipedia.org/wiki/Functional_completeness. $\endgroup$
    – Rob Arthan
    Apr 25, 2015 at 18:12
  • $\begingroup$ @RobArthan I know two ways of defining functional completeness. One doesn't require reduction to standard connectives, the other does. The wikipedia link doesn't help in this respect. $\endgroup$
    – Git Gud
    Apr 25, 2015 at 18:13
  • $\begingroup$ @Git Hud: please elucidate. The wikipaedia link gives the standard definition of a functionally complete set of connectives as one that can define any truth-theoretic function. $\endgroup$
    – Rob Arthan
    Apr 25, 2015 at 19:57
  • $\begingroup$ I've seen similar in some boolean logic forms, with the $\text{Maj}(\vec{p_n})$ function being defined as ${\left \lfloor \frac{1}{2} + \frac{\left(\displaystyle\sum_{i=1}^n p_i\right) - 1/2}{n} \right \rfloor}$; yours seems to be a special case where $n=3$. I'm not sure if this helps, but it's my two cents ;) $\endgroup$
    – Conor O'Brien
    Apr 26, 2015 at 17:27

1 Answer 1

Reset to default
2
$\begingroup$

Consider just two propositional variables, say $p$ and $q$, and let's see what truth-functions of these we can express using $\neg$ and $G$. Using just $\neg$, we have $p,q,\neg p,\neg q$. Now let's apply $G$ to any triple of these, say $G(x,y,z)$. If two of $x,y,z$ are the same, the $G$ just produces that same one of $p,q,\neg p,\neg q$ as its output. So the only way to get anything new would be if $x,y,z$ are distinct elements of $\{p,q,\neg p,\neg q\}$. But then, since only one of $p,q,\neg p,\neg q$ is missing from $x,y,z$, this triple would contain either both $p$ and $\neg p$ or both $q$ and $\neg q$. But if some two of $x,y,z$ are each other's negations, then $G(x,y,z)$ agrees with the other one of $x,y,z$, so we still get nothing new. Conclusion: The only truth fnctions of $p$ and $q$ that can be expressed using $\neg$ and $G$ are $p,q,\neg p,\neg q$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .