BOOLEAN ALGEBRA: HISTORY, THEOREMS AND POSTULATES, EXAMPLES - MATHS - 2024

The Boolean algebra or Boolean algebra is algebraic notation used for the treatment of binary variables. It covers the studies of any variable that only has 2 possible outcomes, complementary and mutually exclusive. For example, variables whose only possibility is true or false, correct or incorrect, on or off are the basis of the study of Boolean algebra.

Boolean algebra constitutes the basis of digital electronics, which makes it quite present today. It is governed by the concept of logic gates, where known operations in traditional algebra are notably affected.

Source: pexels.com

History

Boolean algebra was introduced in 1854 by the English mathematician George Boole (1815 - 1864), who was a self-taught scholar of the time. His concern arose from an existing dispute between Augustus De Morgan and William Hamilton, about the parameters that define this logical system.

George Boole argued that the definition of the numerical values ​​0 and 1 corresponds, in the field of logic, to the interpretation Nothing and Universe respectively.

George Boole's intention was to define, through the properties of algebra, the expressions of propositional logic necessary to deal with variables of binary type.

In 1854 the most significant sections of Boolean algebra were published in the book "An investigation of the laws of thought on which the mathematical theories of logic and probability are based."

This curious title would be summarized later as "The laws of thought" ("The laws of thought"). The title rose to fame due to the immediate attention it received from the mathematical community of the time.

In 1948 Claude Shannon applied it to the design of bistable electrical switching circuits. This served as an introduction to the application of Boolean algebra within the entire electronic-digital scheme.

Structure

The elementary values ​​in this type of algebra are 0 and 1, which correspond to FALSE and TRUE respectively. The fundamental operations in Boolean algebra are 3:

- AND operation or conjunction. Represented by a period (.). Synonym of the product.

- OR operation or disjunction. Represented by a cross (+). Synonym of the sum.

- NOT operation or negation. Represented by the prefix NOT (NOT A). It is also known as a complement.

If in a set A 2 laws of internal composition are defined denoted as product and sum (. +), It is said that the triple (A. +) Is a Boolean algebra if and only if said triple meets the condition of being a lattice distributive.

To define a distributive lattice, the distribution conditions must be met between the given operations:

. is distributive with respect to the sum + a. (b + c) = (a. b) + (a. c)

+ is distributive with respect to the product. a + (b. c) = (a + b). (a + c)

The elements that make up set A must be binary, thus having universe or void values.

Applications

Its main application scenario is the digital branch, where it serves to structure the circuits that make up the logical operations involved. The art of circuit simplicity in favor of optimizing processes is the result of the correct application and practice of Boolean algebra.

From the elaboration of electrical panels, passing through the transmission of data, until reaching the programming in different languages, we can frequently find Boolean algebra in all kinds of digital applications.

Boolean variables are very common in the structure of programming. Depending on the programming language used, there will be structural operations in the code that use these variables. The conditionals and arguments of each language admit Boolean variables to define the processes.

Postulates

There are theorems that govern the structural logical laws of Boolean algebra. In the same way, there are postulates to know the possible results in different combinations of binary variables, depending on the operation carried out.

Sum (+)

The OR operator whose logical element is the union (U) is defined for binary variables as follows:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Product (.)

The AND operator whose logical element is the intersection (∩) is defined for binary variables as follows:

0. 0 = 0

0. 1 = 0

one. 0 = 0

one. 1 = 1

Opposite (NOT)

The NOT operator whose logical element is the complement (X) 'is defined for binary variables as follows:

NOT 0 = 1

NOT 1 = 0

Many of the postulates differ from their counterparts in conventional algebra. This is due to the domain of the variables. For example, adding universe elements in Boolean algebra (1 + 1) cannot give the conventional result of 2, because it does not belong to the elements of the binary set.

Theorems

Rule of zero and unity

Any simple operation that involves an element with the binary variables, is defined:

0 + A = A

1 + A = 1

0. A = 0

one. A = A

Equal powers or idempotency

Operations between equal variables are defined as:

A + A = A

TO. A = A

Complementation

Any operation between a variable and its complement is defined as:

A + NOT A = 1

TO. NOT A = 0

Involution or double negation

Any double negation will be considered as the natural variable.

NOT (NOT A) = A

Commutative

A + B = B + A; Commutativity of the sum.

TO. B = B. TO; Commutativity of the product.

Associative

A + (B + C) = (A + B) + C = A + B + C; Associativity of the sum.

TO. (B. C) = (A. B). C = A. B. C; Product associativity.

Distributive

A + (B. C) = (A + B). (A + C); Distributivity of the sum with respect to the product.

TO. (B + C) = (A. B) + (A + C); Distributivity of the product with respect to the sum.

Laws of absorption

There are many absorption laws among multiple references, some of the best known are:

TO. (A + B) = A

TO. (NOT A + B) = A. B

NOT A (A + B) = NOT A. B

(A + B). (A + NOT B) = A

A + A. B = A

A + NOT A. B = A + B

NOT A + A. B = NOT A + B

TO. B + A. NOT B = A

Morgan's theorem

They are transformation laws, which handle pairs of variables that interact between the defined operations of Boolean algebra (+.).

NOT (A. B) = NOT A + NOT B

NOT (A + B) = NOT A. NOT B

A + B = NOT (NOT A + NOT B)

TO. B = NOT (NOT A. NOT B)

Duality

All postulates and theorems possess the faculty of duality. This implies that by exchanging the variables and operations the resulting proposition is verified. That is, when exchanging 0 for 1 and AND for OR or vice versa; an expression is created that will also be completely valid.

For example if the postulate is taken

one. 0 = 0

And duality is applied

0 + 1 = 1

Another perfectly valid postulate is obtained.

Karnaugh Map

The Karnaugh map is a diagram used in Boolean algebra to simplify logical functions. It consists of a two-dimensional arrangement similar to the truth tables of propositional logic. The data from the truth tables can be directly captured on the Karnaugh map.

The Karnaugh map can accommodate processes of up to 6 variables. For functions with a higher number of variables, the use of software is recommended to simplify the process.

Proposed in 1953 by Maurice Karnaugh, it was established as a fixed tool in the field of Boolean algebra, because its implementation synchronizes human potential with the need to simplify Boolean expressions, a key aspect in the fluidity of digital processes.

Examples

Boolean algebra is used to reduce logic gates in a circuit, where the priority is to bring the complexity or level of the circuit to its lowest possible expression. This is due to the computational delay that each gate supposes.

In the following example we will observe the simplification of a logical expression to its minimum expression, using the theorems and postulates of Boolean algebra.

NOT (AB + A + B). NOT (A + NOT B)

NOT. NOT (A + NOT B); Factoring A with a common factor.

NOT. NOT (A + NOT B); By theorem A + 1 = 1.

NOT (A + B). NOT (A + NOT B); by theorem A. 1 = A

(NOT A. NOT B).;

By Morgan's theorem NOT (A + B) = NOT A. NOT B

(NOT A. NOT B). (NOT A. B); By double negation theorem NOT (NOT A) = A

NOT A. NOT B. NOT A. B; Algebraic grouping.

NOT A. NOT A. NOT B. B; Commutativity of product A. B = B. TO

NOT A. NOT B. B; By theorem A. A = A

NOT A. 0; By theorem A. NOT A = 0

0; By theorem A. 0 = 0

TO. B. C + NOT A + A. NOT B. C

TO. C. (B + NOT B) + NOT A; Factoring (A. C) with a common factor.

TO. C. (1) + NOT A; By theorem A + NOT A = 1

TO. C + NOT A; By rule of zero theorem and unity 1. A = A

NOT A + C; By law of Morgan A + NOT A. B = A + B

For this solution, Morgan's law must be extended to define:

NOT (NOT A). C + NOT A = NOT A + C

Because NOT (NOT A) = A by involution.

Simplify the logic function

NOT A. NOT B. NOT C + NOT A. NOT B. C + NOT A. NOT C down to its minimum expression

NOT A. NOT B. (NOT C + C) + NOT A. NOT C; Factoring (NOT A. NOT B) with common factor

NOT A. NOT B. (1) + NOT A. NOT C; By theorem A + NOT A = 1

(NOT A. NOT B) + (NOT A. NOT C); By rule of zero theorem and unity 1. A = A

NOT A (NOT B + NOT C); Factoring NOT A with a common factor

NOT A. NOT (B. C); By Morgan laws NOT (A. B) = NOT A + NOT B

NOT By Morgan's laws NOT (A. B) = NOT A + NOT B

Any of the 4 options in bold represents a possible solution to reduce the level of the circuit

Simplify the logical function to its simplest form

(A. NOT B. C + A. NOT B. B. D + NOT A. NOT B). C

(A. NOT B. C + A. 0. D + NOT A. NOT B). C; By theorem A. NOT A = 0

(A. NOT B. C + 0 + NOT A. NOT B). C; By theorem A. 0 = 0

(A. NOT B. C + NOT A. NOT B). C; By theorem A + 0 = A

TO. NOT B. C. C + NOT A. NOT B. C; By distributivity of the product with respect to the sum

TO. NOT B. C + NOT A. NOT B. C; By theorem A. A = A

NOT B. C (A + NOT A) ; Factoring (NOT B. C) with common factor

NOT B. C (1); By theorem A + NOT A = 1

NOT B. C; By rule of zero theorem and unity 1. A = A

References

1. Boolean algebra and its applications J. Eldon Whitesitt. Continental Publishing Company, 1980.
2. Mathematics and Engineering in Computer Science. Christopher J. Van Wyk. Institute for Computer Sciences and Technology. National Bureau of Standards. Washington, DC 20234
3. Mathematics for Computer Science. Eric Lehman. Google Inc.

   F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies.

4. Elements of Abstract Analysis. Mícheál O'Searcoid PhD. Department of mathematics. University college Dublin, Beldfield, Dublind.
5. Introduction to Logic and to the Methodology of the Deductive Sciences. Alfred Tarski, New York Oxford. Oxford University press.