1

First, I will note that I don't need a formal prove. short explanation is enough.
The only way I know to show that an operator isn't universal, is by showing that you can't implement $NOT$ with it.
This worked for me so far, because I solved only questions with a small number of paramters in the operatores I got.
But now I have four- and that's too much cases to check.
I tried to look for an answer here, and I saw this post which has pretty similar question, but it was not really answered (or that I didn't understand how the post's functional completeness theorem can help here):
https://math.stackexchange.com/questions/1571448/how-to-prove-that-fw-x-y-z-%E2%88%914-5-13-isnt-universal

So, how can you show that this operator isn't universal?

Community
  • 1
Rodrigo
  • 25
  • 4

2 Answers2

1

The function has the property that if all the inputs are false, then the output is false too. Therefore there is no combination of $f$ and a single variable that can output true when the input variable is false -- so negation can't be implemented.

hmakholm left over Monica
  • 286,031
0

Post's functional completeness theorem is probably the way to do it. Look at the five conditions here:

https://en.wikipedia.org/wiki/Functional_completeness#Characterization_of_functional_completeness

Check your function. If it satisfies any of the conditions, it is not universal. Start with the ones that look easiest to check.

Edit: The first condition means that you can't strictly decrease the value of the function (change from True to False) by strictly increasing the input (changing values from False to True).

The second condition means that for each variable, no matter what the values of the other variables are, either changing it does nothing (the variable has no impact), or changing it always changes the output as well (the variable always has an impact). One of these two things must be true for each variable for the condition to hold.

Neither of these conditions hold for your function. For the first one, f(T,F,F,F)=T, but f(T,T,F,F)=F. I only increased values, but I decreased the answer, so the condition doesn't hold. You only need one counterexample to eliminate the condition. As for the second condition, f(w,F,F,z)=w, so in that case w changes the value, but f(w,T,y,z)=z, where w doesn't change the value. Only one of these can hold for any variable for the condition to hold, so we have a counterexample to this one as well.

Fricative Melon
  • 170
  • Wow, I didn't hear about this theorem untill now- it looks very usefull. However, I am not sure that I understand all the conditions. please correct me if I am wrong: codition 3 says that if $f=f^D$ ($f$ eqauls to it dual), then it is not universal. Condition 4 says that if we have a function $f$ with $n$ parameters, so that $f(1,1,..,1)=1$ ($n$ times $1$ in the function paramaters), then $f$ isn't universal. Condition 5 says the same as condition 4, just for $0$ value, representing $false$. – Rodrigo Jan 20 '16 at 08:30
  • Also, I didn't really understand the first and the second condition. Can you give an example for each of them? – Rodrigo Jan 20 '16 at 08:31