Jump to content

Zhegalkin algebra

From Wikipedia, the free encyclopedia
(Redirected from Draft:Zhegalkin algebra)

In mathematics, Zhegalkin algebra is a set of Boolean functions defined by the nullary operation taking the value , use of the binary operation of conjunction , and use of the binary sum operation for modulo 2 . The constant is introduced as .[1] The negation operation is introduced by the relation . The disjunction operation follows from the identity .[2]

Using Zhegalkin Algebra, any perfect disjunctive normal form can be uniquely converted into a Zhegalkin polynomial (via the Zhegalkin Theorem).

Basic identities

[edit]
  • ,
  • ,

Thus, the basis of Boolean functions is functionally complete.

Its inverse logical basis is also functionally complete, where is the inverse of the XOR operation (via equivalence). For the inverse basis, the identities are inverse as well:  is the output of a constant,  is the output of the negation operation, and is the conjunction operation.

The functional completeness of the these two bases follows from completeness of the basis .

See also

[edit]

References

[edit]
  • Zhegalkin, Ivan Ivanovich (1927). "On the technique of calculating propositions in symbolic logic" (PDF). Matematicheskii Sbornik. 34 (1): 9–28. Retrieved 12 January 2024.

Notes

[edit]
  1. ^ Zhegalkin, Ivan Ivanovich (1928). "The arithmetization of symbolic logic" (PDF). Matematicheskii Sbornik. 35 (3–4): 320. Retrieved 12 January 2024., additional text.
  2. ^ Yu. V. Kapitonova, S.L. Krivoj, A. A. Letichevsky. Lectures on Discrete Mathematics. — SPB., BHV-Petersburg, 2004. — ISBN 5-94157-546-7, p. 110-111.

Further reading

[edit]