The boolean algebra o Boolean algebra is the 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 the operations known in traditional algebra are notably affected.
Article index
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..
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 (.). Product synonym.
- OR operation or disjunction. Represented by a cross (+). Synonym of the sum.
- NOT operation or negation. Represented by the prefix NOT (NOT A). Also known as complement.
If in a set A 2 laws of internal composition are defined denoted as product and sum (. +), The triple (A. +) Is said to be 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 + to . (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 the set A must be binary, thus having values of universe or void.
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 order to optimize 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, to 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.
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..
The operator OR 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
The operator AND whose logical element is the intersection (∩) is defined for binary variables as follows:
0. 0 = 0
0. 1 = 0
1 . 0 = 0
1 . 1 = 1
The operator NOT 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 yield the conventional result of 2, because it does not belong to the elements of the binary set.
Any simple operation that involves an element with the binary variables, is defined:
0 + A = A
1 + A = 1
0. A = 0
1 . A = A
Operations between equal variables are defined as:
A + A = A
TO . A = A
Any operation between a variable and its complement is defined as:
A + NOT A = 1
TO . NOT A = 0
Any double negation will be considered as the natural variable.
NOT (NOT A) = A
A + B = B + A; Commutativity of the sum.
TO . B = B. TO ; Product commutativity.
A + (B + C) = (A + B) + C = A + B + C; Associativity of the sum.
TO . (B. C) = (A. B). C = A. B. C; Product associativity.
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.
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
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)
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 you take the postulate
1 . 0 = 0
And duality is applied
0 + 1 = 1
Another perfectly valid postulate is obtained.
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 potentiality with the need to simplify Boolean expressions, a key aspect in the fluidity of digital processes..
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 [A (B + 1) + B]. NOT (A + NOT B); Factoring A with a common factor.
NOT [A (1) + B]. 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). [ NOTE . NOT (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
NOTE . NOT B. NOTE . B; Algebraic grouping.
NOTE . NOTE . NOT B. B; Commutativity of product A. B = B. TO
NOTE . NOT B. B; By theorem A. A = A
NOTE . 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 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.
NOTE . NOT B. NOT C + NOT A. NOT B. C + NOT A. NOT C down to its minimum expression
NOTE . NOT B. (NOT C + C) + NOT A. NOT C; Factoring (NOT A. NOT B) with common factor
NOTE . 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
NOTE . NOT (B. C); By Morgan laws NOT (A. B) = NOT A + NOT B
NOT [A + (B. C)] By Morgan 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
(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
Yet No Comments