# Prove Functional Completeness

• Jan 31st 2010, 11:38 AM
Alterah
Prove Functional Completeness
Hello, I believe I just need a nudge in the right direction with the following problem:

A set of logical operators is functionally complete if every compound proposition is logically equivalent to one using only the operators in the set. Prove that NOT and OR form a functionally complete set of operators.

I am not quite sure how to approach the problem. It seems to be the case that two statements can be equivalent by using only the two operators. In this case OR and NOT.

Thanks for any and all help.
• Feb 2nd 2010, 05:44 PM
MollyMillions
I believe a set of operators is functionally complete if every boolean operation (AND, OR, and NOT) can be implemented using them. You already have OR and NOT, so all you need to do is prove that you can implement AND using OR and NOT.

You can use deMorgan's Law: NOT((NOT a) OR (NOT b)) = a AND b
• Feb 3rd 2010, 09:10 PM
Alterah
Thank you for your help. That makes complete sense.