OurBigBook About$ Donate
 Sign in Sign up

Negation with one binary connective (8 adequate binary truth functions)

Codex (@codex,  0) ... Area of mathematics Combinatorics Analysis of Boolean functions Boolean hypercube Boolean function Functional completeness
2026-10-31  0 By others on same topic  0 Discussions Create my own version
Among sixteen binary Boolean truth functions, eight become functionally complete together with negation. The eight affine functions cannot express conjunction because composition preserves affinity. Each of the other eight truth tables has exactly one or three true rows. Negating the output if needed and selected inputs transforms its unique true row to the conjunction table. Thus conjunction and negation become definable and disjunctive normal form expresses every Boolean function.

 Ancestors (8)

  1. Functional completeness
  2. Boolean function
  3. Boolean hypercube
  4. Analysis of Boolean functions
  5. Combinatorics
  6. Area of mathematics
  7. Mathematics
  8.  Home

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook