Distributive property

Last updated
Distributive property
Illustration of distributive property with rectangles.svg
Visualization of distributive law for positive numbers
Type Law, rule of replacement
Field
Symbolic statement
  1. Elementary algebra
  2. Propositional calculus:

In mathematics, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality

Contents

is always true in elementary algebra. For example, in elementary arithmetic, one has

Therefore, one would say that multiplication distributes over addition.

This basic property of numbers is part of the definition of most algebraic structures that have two operations called addition and multiplication, such as complex numbers, polynomials, matrices, rings, and fields. It is also encountered in Boolean algebra and mathematical logic, where each of the logical and (denoted ) and the logical or (denoted ) distributes over the other.

Definition

Given a set and two binary operators and on

When is commutative, the three conditions above are logically equivalent.

Meaning

The operators used for examples in this section are those of the usual addition and multiplication

If the operation denoted is not commutative, there is a distinction between left-distributivity and right-distributivity:

In either case, the distributive property can be described in words as:

To multiply a sum (or difference) by a factor, each summand (or minuend and subtrahend) is multiplied by this factor and the resulting products are added (or subtracted).

If the operation outside the parentheses (in this case, the multiplication) is commutative, then left-distributivity implies right-distributivity and vice versa, and one talks simply of distributivity.

One example of an operation that is "only" right-distributive is division, which is not commutative:

In this case, left-distributivity does not apply:

The distributive laws are among the axioms for rings (like the ring of integers) and fields (like the field of rational numbers). Here multiplication is distributive over addition, but addition is not distributive over multiplication. Examples of structures with two operations that are each distributive over the other are Boolean algebras such as the algebra of sets or the switching algebra.

Multiplying sums can be put into words as follows: When a sum is multiplied by a sum, multiply each summand of a sum with each summand of the other sum (keeping track of signs) then add up all of the resulting products.

Examples

Real numbers

In the following examples, the use of the distributive law on the set of real numbers is illustrated. When multiplication is mentioned in elementary mathematics, it usually refers to this kind of multiplication. From the point of view of algebra, the real numbers form a field, which ensures the validity of the distributive law.

First example (mental and written multiplication)
During mental arithmetic, distributivity is often used unconsciously:

Thus, to calculate in one's head, one first multiplies and and add the intermediate results. Written multiplication is also based on the distributive law.

Second example (with variables)
Third example (with two sums)

Here the distributive law was applied twice, and it does not matter which bracket is first multiplied out.

Fourth example
Here the distributive law is applied the other way around compared to the previous examples. Consider

Since the factor occurs in all summands, it can be factored out. That is, due to the distributive law one obtains

Matrices

The distributive law is valid for matrix multiplication. More precisely,

for all -matrices and -matrices as well as

for all -matrices and -matrices Because the commutative property does not hold for matrix multiplication, the second law does not follow from the first law. In this case, they are two different laws.

Other examples

Propositional logic

Rule of replacement

In standard truth-functional propositional logic, distribution [3] [4] in logical proofs uses two valid rules of replacement to expand individual occurrences of certain logical connectives, within some formula, into separate applications of those connectives across subformulas of the given formula. The rules are

where "", also written is a metalogical symbol representing "can be replaced in a proof with" or "is logically equivalent to".

Truth functional connectives

Distributivity is a property of some logical connectives of truth-functional propositional logic. The following logical equivalences demonstrate that distributivity is a property of particular connectives. The following are truth-functional tautologies.

Double distribution

Distributivity and rounding

In approximate arithmetic, such as floating-point arithmetic, the distributive property of multiplication (and division) over addition may fail because of the limitations of arithmetic precision. For example, the identity fails in decimal arithmetic, regardless of the number of significant digits. Methods such as banker's rounding may help in some cases, as may increasing the precision used, but ultimately some calculation errors are inevitable.

In rings and other structures

Distributivity is most commonly found in semirings, notably the particular cases of rings and distributive lattices.

A semiring has two binary operations, commonly denoted and and requires that must distribute over

A ring is a semiring with additive inverses.

A lattice is another kind of algebraic structure with two binary operations, If either of these operations distributes over the other (say distributes over ), then the reverse also holds ( distributes over ), and the lattice is called distributive. See also Distributivity (order theory) .

A Boolean algebra can be interpreted either as a special kind of ring (a Boolean ring) or a special kind of distributive lattice (a Boolean lattice). Each interpretation is responsible for different distributive laws in the Boolean algebra.

Similar structures without distributive laws are near-rings and near-fields instead of rings and division rings. The operations are usually defined to be distributive on the right but not on the left.

Generalizations

In several mathematical areas, generalized distributivity laws are considered. This may involve the weakening of the above conditions or the extension to infinitary operations. Especially in order theory one finds numerous important variants of distributivity, some of which include infinitary operations, such as the infinite distributive law; others being defined in the presence of only one binary operation, such as the according definitions and their relations are given in the article distributivity (order theory). This also includes the notion of a completely distributive lattice.

In the presence of an ordering relation, one can also weaken the above equalities by replacing by either or Naturally, this will lead to meaningful concepts only in some situations. An application of this principle is the notion of sub-distributivity as explained in the article on interval arithmetic.

In category theory, if and are monads on a category a distributive law is a natural transformation such that is a lax map of monads and is a colax map of monads This is exactly the data needed to define a monad structure on : the multiplication map is and the unit map is See: distributive law between monads.

A generalized distributive law has also been proposed in the area of information theory.

Antidistributivity

The ubiquitous identity that relates inverses to the binary operation in any group, namely which is taken as an axiom in the more general context of a semigroup with involution, has sometimes been called an antidistributive property (of inversion as a unary operation). [5]

In the context of a near-ring, which removes the commutativity of the additively written group and assumes only one-sided distributivity, one can speak of (two-sided) distributive elements but also of antidistributive elements. The latter reverse the order of (the non-commutative) addition; assuming a left-nearring (i.e. one which all elements distribute when multiplied on the left), then an antidistributive element reverses the order of addition when multiplied to the right: [6]

In the study of propositional logic and Boolean algebra, the term antidistributive law is sometimes used to denote the interchange between conjunction and disjunction when implication factors over them: [7]

These two tautologies are a direct consequence of the duality in De Morgan's laws.

Notes

    1. Distributivity of Binary Operations from Mathonline
    2. Kim Steward (2011) Multiplying Polynomials from Virtual Math Lab at West Texas A&M University
    3. Elliott Mendelson (1964) Introduction to Mathematical Logic, page 21, D. Van Nostrand Company
    4. Alfred Tarski (1941) Introduction to Logic, page 52, Oxford University Press
    5. Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Relational Methods in Computer Science . Springer. p.  4. ISBN   978-3-211-82971-4.
    6. Celestina Cotti Ferrero; Giovanni Ferrero (2002). Nearrings: Some Developments Linked to Semigroups and Groups. Kluwer Academic Publishers. pp. 62 and 67. ISBN   978-1-4613-0267-4.
    7. Eric C.R. Hehner (1993). A Practical Theory of Programming. Springer Science & Business Media. p. 230. ISBN   978-1-4419-8596-5.

    Related Research Articles

    <span class="mw-page-title-main">Associative property</span> Property of a mathematical operation

    In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs.

    In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4.

    <span class="mw-page-title-main">Least common multiple</span> Smallest positive number divisible by two integers

    In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(ab), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a, 0) as 0 for all a, since 0 is the only common multiple of a and 0.

    <span class="mw-page-title-main">Logical connective</span> Symbol connecting sentential formulas in logic

    In logic, a logical connective is a logical constant. Connectives can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .

    Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

    In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. Informally, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

    <span class="mw-page-title-main">De Morgan's laws</span> Pair of logical equivalences

    In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.

    In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canonical normal form, it is useful in automated theorem proving and circuit theory.

    In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

    <span class="mw-page-title-main">Exclusive or</span> True when either but not both inputs are true

    Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ. With multiple inputs, XOR is true if and only if the number of true inputs is odd.

    In mathematics, an algebraic structure consists of a nonempty set A, a collection of operations on A, and a finite set of identities, known as axioms, that these operations must satisfy.

    <span class="mw-page-title-main">Matrix multiplication</span> Mathematical operation in linear algebra

    In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.

    Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not assume the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

    In mathematics, an algebra over a field is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition and scalar multiplication by elements of a field and satisfying the axioms implied by "vector space" and "bilinear".

    <span class="mw-page-title-main">Commutative property</span> Property of some mathematical operations

    In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a property of arithmetic, e.g. "3 + 4 = 4 + 3" or "2 × 5 = 5 × 2", the property can also be used in more advanced settings. The name is needed because there are operations, such as division and subtraction, that do not have it ; such operations are not commutative, and so are referred to as noncommutative operations. The idea that simple operations, such as the multiplication and addition of numbers, are commutative was for many years implicitly assumed. Thus, this property was not named until the 19th century, when mathematics started to become formalized. A similar property exists for binary relations; a binary relation is said to be symmetric if the relation applies regardless of the order of its operands; for example, equality is symmetric as two equal mathematical objects are equal regardless of their order.

    In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

    In mathematics, specifically abstract algebra, the opposite of a ring is another ring with the same elements and addition operation, but with the multiplication performed in the reverse order. More explicitly, the opposite of a ring (R, +, ) is the ring (R, +, ∗) whose multiplication ∗ is defined by ab = ba for all a, b in R. The opposite ring can be used to define multimodules, a generalization of bimodules. They also help clarify the relationship between left and right modules (see § Properties).

    In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.

    In mathematical logic, Skolem arithmetic is the first-order theory of the natural numbers with multiplication, named in honor of Thoralf Skolem. The signature of Skolem arithmetic contains only the multiplication operation and equality, omitting the addition operation entirely.

    The Tseytin transformation, alternatively written Tseitin transformation, takes as input an arbitrary combinatorial logic circuit and produces an equisatisfiable boolean formula in conjunctive normal form (CNF). The length of the formula is linear in the size of the circuit. Input vectors that make the circuit output "true" are in 1-to-1 correspondence with assignments that satisfy the formula. This reduces the problem of circuit satisfiability on any circuit to the satisfiability problem on 3-CNF formulas. It was discovered by the Russian scientist Grigori Tseitin.