At this point, with all the discussions surrounding POS and SOP, we are convinced that any Boolean function can be expressed using only negation, conjunction and disjunction. However, are there other ways to “span” all Boolean functions?
In other words, are there other sets of boolean operators that we can use to express any Boolean functions?
As it turns out, there are other sets of boolean operators that are functionally complete. For example, the set of {¬,→} is functionally equivalent to {¬,∨,∧}, and hence it is also functionally complete.
→ is the “imply” operator, its truth table is expressed in table 2.
How can we prove that {¬,→} is equivalent to {¬,∨,∧}? If we can express A ∧ B and A ∨ B using operators only in {¬,→}, then both sets of operators are complete.
One can show that A ∨ B = (¬A) → B, and A ∧ B = ¬(A →¬B).