Functionally Complete

Question

Suppose a function F(A,B) = A' + B then to prove it functionally complete.Can we do it like:-

F(A,A') = A'   ---->  Complementation derived

F(A',B) = A + B     -----> OR Operation Derived

So we could conclude that its functionally Complete.

Is it the right way if not Please tell the right eay to prove the Function to be Functionally Complete.

Thank You in advance

Answer 1

Functionally complete if you are able to derive functionally complete set <AND,OR,NOT>

F(A,B)=A'+B

F(A,A)=A'+A=1

F(B,B)=B'+B=1

---------------------------------------------------------------

USING 1 as input:-

F(1,B)=1'+B=0+B=B

F(A,1)=A'+1=1

Not able to derive not , hence not functionally complete

--------------------------------------------------------------------------------

http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf

Theorem. A system of boolean functions is functionally complete if and only if this system does
not entirely belong to any of T0, T1, L, M, S.
The mentioned theorem is called Post's completeness criterion and is due to Emil Post. What this
criterion says is that in order for a system of boolean functions to be functionally complete, this
system should have
• at least one function that does not preserve zero (i.e. it is not in T0), and
• at least one function that does not preserve one (i.e. it is not in T1), and
• at least one function that is not linear (i.e. it is not in L), and
• at least one function that is not monotone (i.e. it is not in M), and
• at least one function that is not self-dual (i.e. it is not in S).
Of course, one function may combine some of these roles, e.g., a function may not preserve one and,
at the same time, not be monotone.

--------------------------------------------------------

using above theorem:-

1. Does not preserve zero as well as one:-

F(0,0)=0'+0=1+0=1

F(1,1)=1'+1=0+1=1 =>> preserve one so not functionally complete

Comments

Only one thing to ask sir what you mean here by clause "Not entirely" , cant we say if the System doesnt belongs to......,Please explain this line

---

Sir it is partially function completeness. Am i right?

Answer 2

if you are able to derive  set <AND,OR,NOT> .then it is colled Functionally complete. 

 in this question we cant able to derive complement . so it is not Functionally complete. but with the help of 0 we can derive set< OR,NOT> so it is partially functionally complete.

Answer 3

F(A,A') = A'   ---->  Complementation derived

 

This is not allowed. If u can provide A' in input, it means we already have inverter (NOT gate) which is not the case.