How do I apply Post's crieterion to check if given function is functionally complete

47 Views Asked by At

I was reading about Post's crieterion to prove whether given function is functionally complete or not.

I came cross function $f(a,b)=a'+b$. I tried determining whether this function is functionally complete or not as follows:

$f(0,0)=1→$ Not zero preserving
$f(1,1)=0→$ Not one preserving enter image description here
As can be seen from above truth table, odd number of 1s can cause both $f=0$ and $f=1$. Hence $f$ is not linear.
$f'(a',b')=(a+b')'=a'b≠f→$ Not self-dual.
Also from below Hassee diagram, it can be seen that the function is not monotone (as $f(0,0)=1$, but $f(1,0)=0$.): enter image description here
According to Post, a system of boolean functions is functionally complete if and only if this system does not entirely belong to any of above properties. $f$ is the only function in given system and it does not posses any of those properties. Hence $f$ is functionally complete.

However, I was referring text which says following:

$f(a,0)=a'$
So to obtain complement of variable $a$, we need to set other variable $b=0$. So, we need to take help of 0. $f$ cannot emulate negation without the help of boolean constant 0. Hence its not functionally complete, but partially functionally complete.

Now I am confused. Does Post's criteria fail to address partial functional completeness. Or text is incorrect and no such concept of partial functional completeness exist?