3
$\begingroup$

I have the following truth table of a newly defined logical operator and have to prove its functional incompleteness via structural induction.

My idea is that that you cannot express the always true formula $\top$ in terms of this operator. I just don't know how to go about the proof.

Here is the truth table of the new 3-input Operator:

$$\begin{array}{|c|c|c|c|} X & Y & Z & <X,Y,Z> \\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 1\\ \hline 1 & 0 & 1& 0 \\ \hline 1 & 1 & 0 & 0\\ \hline 1 & 1 & 1 & 0\\ \hline \end{array}$$

$\endgroup$
4
  • 3
    $\begingroup$ How about: for any expression in $n$ variables that you can build with the operator, its evaluation at $(0, 0, \ldots, 0)$ is 0? $\endgroup$
    – Daniel Schepler
    Commented Mar 14, 2020 at 0:51
  • $\begingroup$ thank you for your reply , how does this prove its inadequacy though ? $\endgroup$
    – Johoey
    Commented Mar 14, 2020 at 1:40
  • 1
    $\begingroup$ You probably already know this, but just in case: <$X,Y,Z$> $\equiv (Y \land Z)\lor X$. I hope this helps. $\endgroup$
    – Dan Christensen
    Commented Mar 14, 2020 at 3:20
  • $\begingroup$ Johoey: The comment by @DanilSchepler means that you can't implement $\neg X$ using only this operator. $\endgroup$
    – JonathanZ
    Commented Mar 14, 2020 at 5:09

2 Answers 2

Reset to default
1
$\begingroup$

We can use structural induction to give a careful proof that any term we can build using only the function symbol $<-,-,->$ and the variable symbol $x$ represents either the identity function or the constant $0$ function.

Base case $x$: Upon substituting $1$ for $x$, we get $1$. Upon substituting $0$, we get $0$. Therefore $x$ represents the identity function.

Inductive case: Consider a term $f(x)$ form $<A(x),B(x),C(x)>$, where we know by inductive assumption that each of $A(x)$, $B(x)$ and $C(x)$ represents either the identity function or the constant 0 function.

We perform a case analysis, tabulating each of these eight possibilities:

A(x) | B(x) | C(x) | x | f(x)
-----|------|------|---|-----
 x   |  x   |  x   | 1 |  0
     |      |      | 0 |  0   (const. 0)
-----|------|------|---|-----
 x   |  x   |  0   | 1 |  0
     |      |      | 0 |  0   (const. 0)
-----|------|------|---|-----
 x   |  0   |  x   | 1 |  0
     |      |      | 0 |  0   (const. 0)
-----|------|------|---|-----
 x   |  0   |  0   | 1 |  1
     |      |      | 0 |  0   (identity)
-----|------|------|---|-----
 0   |  x   |  x   | 1 |  1
     |      |      | 0 |  0   (identity)
-----|------|------|---|-----
 0   |  x   |  0   | 1 |  0
     |      |      | 0 |  0   (const. 0)
-----|------|------|---|-----
 0   |  0   |  x   | 1 |  0
     |      |      | 0 |  0   (const. 0)
-----|------|------|---|-----
 0   |  0   |  0   | 1 |  0
     |      |      | 0 |  0   (const. 0)

We see that in each of these cases, $<A(x),B(x),C(x)>$ represents either the identity function or the constant $0$ function. By the principle of structural induction, any term built using only the function symbol $<-,-,->$ and the variable symbol $x$ represents either the identity function or the constant $0$ function.

Consequently, we cannot express negation or the constant $1$ function using only $<-,-,->$, and so the set $\{ <-,-,-> \}$ is not functionally complete.

$\endgroup$
0
$\begingroup$

$<X,Y,Z>$ or not-$<X,Y,Z>$
has a truth table of all 1's.

$\endgroup$

You must log in to answer this question.

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