$\{\implies, \vee\}$ and $\{\iff,\lnot\}$ cannot express all the truth functions Counterexample to see that $\{\implies, \vee\}$ and $\{\iff,\lnot\}$ are not alone adequate to express all the truth functions.
what could be the counterexample?
what expression could not be expressed with these pairs of operators?
I don't know how to do it.
 A: As was pointed out in a comment to the original post, both $\implies$ and $\lor$ are truth-preserving, which means (check this!) that all compositions of $\implies$ and $\lor$ will be truth-preserving. Since for example $\lnot$ isn't truth-preserving, $\{\implies,\lor\}$ cannot be functionally complete.
You can do something very similar for the other set. The connectives $\iff$ and $\lnot$ both happen to be affine (or linear), and it can be shown (but this is tricky) that all compositions of affine connectives are affine themselves. Since not all truth functions are affine (find a counterexample yourself!), $\{\iff,\lnot\}$ cannot be functionally complete.
A good place to start reading more about this is the section about characterization of functional completion on Wikipedia. Another excellent reference, that focuses specifically on $\{\iff,\lnot\}$, is the article On Proving Functional Incompleteness
in Symbolic Logic Classes from 1988 by Pelletier and Sharp.
A: As shown in this answer, there is an elementary method to show that the entire set $\{¬,⊕,⇔,⊤,⊥\}$ is not adequate.
