Functional Completeness - Informal Definition

Informal Definition

Modern texts on logic typically take as primitive some subset of the connectives: conjunction, or Kpq; disjunction, or Apq; negation, Np, or Fpq; or material conditional, or Cpq; and possibly the biconditional, or Epq. These connectives are functionally complete. However, they do not form a minimal functionally complete set, as the conditional and biconditional may be defined as:

\begin{align} A \to B &:= \neg A \lor B\\ A \leftrightarrow B &:= (A \to B) \land (B \to A).
\end{align}

So is also functionally complete. But then, can be defined as

can also be defined in terms of in a similar manner.

It is also the case that can be defined in terms of as follows:

No further simplifications are possible. Hence and one of are each minimal functionally complete subsets of .

Read more about this topic:  Functional Completeness

Famous quotes containing the words informal and/or definition:

    We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.
    Urie Bronfenbrenner (b. 1917)

    The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.
    William James (1842–1910)