Thread: 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.

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

Thank you for your help. That makes complete sense.