Functional Completeness - Characterization of Functional Completeness

Characterization of Functional Completeness

Further information: Post's lattice

Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

  • The monotonic connectives; changing the truth value of any connected variables from F to T without changing any from T to F never makes these connectives change their return value from T to F, e.g., .
  • The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g., .
  • The self-dual connectives, which are equal to their own de Morgan dual; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g., MAJ(p,q,r).
  • The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables, e.g., .
  • The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g., .

In fact, Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called Post's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal clones.

Read more about this topic:  Functional Completeness

Famous quotes containing the words functional and/or completeness:

    “Indigenous to Minnesota, and almost completely ignored by its people, are the stark, unornamented, functional clusters of concrete—Minnesota’s grain elevators. These may be said to express unconsciously all the principles of modernism, being built for use only, with little regard for the tenets of esthetic design.”
    —Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)

    “Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
    —Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)