|
Zhegalkin Polynomial
Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, ''x''2 = ''x''. Hence a polynomial such as 3''x''2''y''5''z'' is congruent to, and can therefore be rewritten as, ''xyz''. __TOC__ Boolean equivalent Prior to 1927, Boolean algebra had been considered a calculus of logical values with logical operations of conjunction, disjunction, negation, and so on. Zhegalkin showed that all Boolean operations could be written as ordinary numeric polynomials, repres ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Algebraic Normal Form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing propositional logic formulas in one of three subforms: * The entire formula is purely true or false: ** 1 ** 0 * One or more variables are combined into a term by AND (\and), then one or more terms are combined by XOR (\oplus) together into ANF. Negations are not permitted: a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) * The previous subform with a purely true term: 1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM). Common uses ANF is a canonical form, which means that two logically equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem prov ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Boolean Functions
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form f:\^k \to \, where \ is known as the Boolean domain and k is a non-negative integer called the arity of the function. In the case where k=0, the function is a constant element of \. A Boolean function with multiple outputs, f:\^k \to \^m with m>1 is a vectorial or ''vector-valued'' Boolean function (an S-box in symmetric cryptography). There are 2^ different Boolean functions with k arguments; equal to the number of different truth tables with 2^k entries. Every k-ary Boolean function can be expressed as a propositional formula in k variables x_1,...,x_k, and two propositional formulas a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Disjunctive Normal Form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster concept''. As a normal form, it is useful in automated theorem proving. Definition A logical formula is considered to be in DNF if it is a disjunction of one or more conjunctions of one or more literals. A DNF formula is in full disjunctive normal form if each of its variables appears exactly once in every conjunction and each conjunction appears at most once (up to the order of variables). As in conjunctive normal form (CNF), the only propositional operators in DNF are and (\wedge), or (\vee), and not (\neg). The ''not'' operator can only be used as part of a literal, which means that it can only precede a propositional variable. The following is a context-free grammar for DNF: : ''DNF'' \, \to \, ''Conjunct'' \, \mid \, ''Conjunc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Canonical Disjunctive Normal Form
The adjective canonical is applied in many contexts to mean 'according to the canon' the standard, rule or primary source that is accepted as authoritative for the body of knowledge or literature in that context. In mathematics, ''canonical example'' is often used to mean 'archetype'. Science and technology * Canonical form, a natural unique representation of an object, or a preferred notation for some object Mathematics * * Canonical coordinates, sets of coordinates that can be used to describe a physical system at any given point in time * Canonical map, a morphism that is uniquely defined by its main property * Canonical polyhedron, a polyhedron whose edges are all tangent to a common sphere, whose center is the average of its vertices * Canonical ring, a graded ring associated to an algebraic variety * Canonical injection, in set theory * Canonical representative, in set theory a standard member of each element of a set partition Differential geometry * Canonical one-form, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
