How many connectives do we actually need?
In classical logic there are several logical connectives, that is the building blocks of terms that connect simpler terms together. The most prominent examples are $\land$, and, and $\lor$, or, which behave in the obvious way. Then a few more are named, negation, $\neg$, which is true whenever it operates on a falsehood. Implication $\rightarrow$, which is probably the first logical operation that is not obvious. In classical logic it abbreviates $A\rightarrow B \equiv \neg A \lor B$ which is somewhat more expansive than we would expect, after all that I am writing this while it is not raining does not obviously imply that it is not raining because I'm writing. However it implies that we can conclude $B$ whenever we observe $A$. Then we can of course introduce additional symbols like equivalence $\leftrightarrow$. Now the question is, how many of these do we actually need and just looking at truth tables, there are $2^4 = 16$ possible 2-ary functions in bivalent logic and inspecting a truth table, two operations should be enough to generate them. For example one rotation and toggling a specific place should suffice, since we can rotate a toggled bit to it's desired place. For the logical connectives doing the same kind of analysis we will need negation, and one of the others to have all sixteen possibilities.
We can express
$$ A\lor B \equiv \neg\left(\neg A \land \neg B\right) $$
that is $A$ or $B$ is the same as not $A$ and $B$ being false. Conversely we have
$$ A\land B \equiv \neg \left( \neg A \lor \neg B\right) $$
that is, $\land$ is true if neither $A$ nor $B$ are false. This implies that we can do without one of these. The third one, $\rightarrow$, is given above already as
$$ A\rightarrow B \equiv \neg A \lor B $$
and is true whenever observing A is sufficient to conclude B. Implication has an obvious bidirectional cousin, equivalence
$$ A\leftrightarrow B \equiv \left(A\rightarrow B \right) \land \left(B\leftarrow A\right)\\ \equiv \left( \neg A \land \neg B\right) \lor \left(A \land B \right) $$ which implies that either both are true or neither. Here we see they can also be reduced to either $\land$ or $\lor$ and negation. It is however not possible to express negation in terms of the other,
$$ \neg A \equiv ? $$
We could introduce another symbol $\bot$ that always evaluates as false. Then we have
$$\neg A \equiv A\rightarrow \bot \\\equiv \neg A \lor \bot \\\equiv \neg A, $$
but that just introduces another irreducible symbol.
To see that implication can not be expressed in terms of the other, consider the case where $A$ is true, then $A\land A$, $A\lor A$ and $A \rightarrow A$ are true and to build more complex ones we have to connect simpler terms with connectives, but these simpler terms are already true and we will never get one that evaluates to falsehood.
Post page