0
$\begingroup$

I have two 3-ary propositional functions given by the table

$$ \begin{array}{|c|c|c|c|c|} v(a) & v(b) & v(c) & v(f(a, b, c)) & v(g(a, b, c)) \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \hline \end{array} $$

And I need to decide which of these functions are complete. I made some googling but I didn't get the way how to solve such type of tasks. Books say that $L(\vee,\wedge,\neg)$, $L(\wedge,\neg)$, ... are complete and $L(\wedge)$, $L(\vee)$... are not. But how to apply this on the functions given by table?

I gues I need to make propositional formula from $f$ and $g$. Am I right? If so what's next?

$\endgroup$
  • 1
    $\begingroup$ $v(g(a,b,c))$ is the minority conncetive : $v(g(a,b,c))$ always disagrees with the majority of $v(a), v(b), v(c)$. See Enderton, Exercises 4, page 52 : is not complete. $\endgroup$ – Mauro ALLEGRANZA Nov 4 '14 at 12:35
1
$\begingroup$

We can try exploiting the fact that we know that : $\lnot, \land$ is complete.

The ternary connective $g(a,b,c)$ is the minority connective : $v(g(a,b,c))$ always disagrees with the majority of $v(a),v(b),v(c)$.

We can formally set :

$v(g(a,b,c))=1$ iff $v(a)+v(b)+v(c) \le 1$.

We can define $\lnot$, because $v(g(a,a,a))=1$ iff $v(a)=0$.

But we cannot define $a \land b$, because $v(a \land b)=1$ iff $v(a)+v(b) = 2$.

Thus, it is not complete.


It seems to me that $f(a,b,c)$ is complete.

We can formally set :

$v(f(a,b,c))=[1-v(a)v(c)][1-v(b)v(c)]$.

In this way, we can define $\lnot$, because $v(f(a,a,a))=1$ iff $v(a)=0$.

We can check also that $f(a,b,c)$ is equivalent to : $\lnot c \lor (\lnot a \land \lnot b)$.

Obviously : $\lnot a \land \lnot a \equiv \lnot a$; thus $f(a,a,c)$ is $\lnot a \lor \lnot c$ i.e. $\lnot (a \land c)$ that is NAND, or Sheffer stroke and we know that it is complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh that's not obvious at all. Thank you, you helped me a lot $\endgroup$ – Levitan Nov 4 '14 at 14:34

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.