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 physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)