The laws of absorption and gluing of exclusion. Laws of absorption algebra of logic
Modern computers based on "ancient" electronic computers are based on certain postulates as the basic principles of operation. They are called the laws of the algebra of logic. For the first time, such a discipline was described (of course, not in as much detail as in its modern form) by the ancient Greek scientist Aristotle.
Representing a separate branch of mathematics, within which the propositional calculus is studied, the algebra of logic has a number of well-defined conclusions and conclusions.
In order to better understand the topic, we will analyze the concepts that will help in the future to learn the laws of the algebra of logic.
Perhaps the main term in the discipline under study is a statement. This is a statement that cannot be both false and true at the same time. He always has only one of these characteristics. At the same time, it is conventionally accepted to give the value 1 to truth, 0 to falsity, and call the statement itself some kind of A, B, C. In other words, the formula A=1 means that the statement A is true. Expressions can be handled in a variety of ways. Let's briefly consider the actions that can be performed with them. Note also that the laws of the algebra of logic cannot be mastered without knowing these rules.
1. Disjunction two statements - the result of the operation "or". It can be either false or true. The character "v" is used.
2. Conjunction. The result of such an action, performed with two propositions, will be a new one only if both original propositions are true. The operation "and", the symbol "^" is used.
3. Implication."If A, then B" operation. The result is a statement that is false only if A is true and B is false. The "->" symbol is used.
4. Equivalence. Operation "A if and only if B when". This statement is true if both variables have the same value. The symbol "<->».
There are also a number of operations close to implication, but they will not be considered in this article.
Now let's take a closer look at the basic laws of the algebra of logic:
1. Commutative or commutative states that changing the places of logical terms in the operations of conjunction or disjunction does not affect the result.
2. Associative or associative. According to this law, variables in the operations of conjunction or disjunction can be combined into groups.
3. Distribution or distribution. The essence of the law is that the same variables in the equations can be taken out of brackets without changing the logic.
4. De Morgan's law (inversion or negation). The negation of the operation of conjunction is equivalent to the disjunction of the negation of the original variables. The negation of the disjunction, in turn, is equal to the conjunction of the negation of the same variables.
5. Double negation. The negation of a certain statement twice results in the original statement, three times - its negation.
6. The law of idempotency looks like this for logical addition: x v x v x v x = x; for multiplication: x^x^x^=x.
7. The law of non-contradiction says: two statements, if they are contradictory, cannot be true at the same time.
8. The law of the exclusion of the third. Among two contradictory statements, one is always true, the other is false, the third is not given.
9. The law of absorption can be written in this way for logical addition: x v (x ^ y) = x, for multiplication: x ^ (x v y) = x.
10. The law of gluing. Two adjacent conjunctions can stick together to form a conjunction of lower rank. In this case, the variable by which the original conjunctions were glued disappears. Example for logical addition:
(x^y) v (-x^y)=y.
We have considered only the most used laws of the algebra of logic, which in fact can be many more, since often logical equations take on a long and ornate form, which can be reduced by applying a number of similar laws.
As a rule, special tables are used for the convenience of counting and identifying results. All existing laws of the algebra of logic, the table for which has the general structure of a grid rectangle, are painted, distributing each variable into a separate cell. The larger the equation, the easier it is to deal with using tables.
Discrete Mathematics: Mathematical Logic
Lecture 8
Minimization of boolean functions. Quine-McCluskey Method
Boolean Algebra Laws
In mathematical logic, a special algebra, the Boolean algebra, is defined, containing the operations of logical multiplication, logical addition and negation ( ,+, - ), which allow identical transformations of logical expressions. These laws includeLaw of idempotency (sameness)
Law of commutativity
a b = b a
Associativity law
a + (b + c) = (a + b) + c
a (b c) = (a b) c
Distributivity laws
Distributivity of conjunction with respect to disjunction
A (b + c) = a b + a c
Distributivity of disjunction with respect to conjunction
A + b c = (a + b) (a + c)
Double Negative Law
De Morgan's laws
Absorption laws
a + a b = a
a (a + b) = a
Laws defining actions with logical constants 0 and 1
| a + 0 = a a 0 = 0 | a + 1 = 1 a 1 = a |
| 1 = 0 |
|
The legitimacy of all the laws discussed above can be easily proved, for example, using truth tables.
Additional laws
Additional laws of Boole algebra are corollaries of the basic laws and are very useful in simplifying the writing of logical functions.
The law of bonding
The proof of this identity is carried out using the first law of distributivity:
The proof of this identity is carried out using the second distributive law:
Blake-Poretsky law
Applying the laws of action with logical constants, idempotency and gluing, this identity can be proved as follows:
The law of convolution of a logical expression
This identity can be proved by successively using the laws of working with logical constants, distributivity, idempotency and gluing:
Simplifying Logic Functions
For normal forms of representation of functions, the concept of complexity of a function is defined as the number of primary terms in such a representation. Normal form transformations to reduce the complexity of a function is called simplification . To simplify the logical functions, all the laws of the algebra of logic are used.Tasks.
Simplify SDNF with the following functions:
1. (a b) c
2. (a b) c
We represent the function in a perfect disjunctive form and simplify it using the laws of the algebra of logic:
3.
We represent the function in a perfect disjunctive form and simplify it using the laws of the algebra of logic:
SDNF = 
No further simplification is possible.
4. 
We represent the function in a perfect disjunctive form and simplify it using the laws of the algebra of logic:
SDNF =
5. 
We represent the function in a perfect disjunctive form and simplify it using the laws of the algebra of logic:
Quine-McCluskey Method
Minimization of logical functions can be carried out using the Quine-McClussky method, which consists of four steps:
Let us represent the sets (constituents) on which the function is true in the form of binary equivalents.
We arrange the binary equivalents by tiers (according to the number of units of binary equivalents) and glue (apply the gluing rule to the corresponding constituents) sets in neighboring tiers, obtaining the maximum intervals as long as possible; we mark each set that participated in the gluing. Only those sets or intervals are glued together, the difference in which lies only in the value of one digit: 001 and 000, 001- and 101-, etc.
Let's build a Quine table, the columns of which correspond to the binary truth sets of the function, and the rows correspond to the maximum intervals. If the i-th set is covered by the j-th interval, then set 1 at the intersection of the corresponding row and column, otherwise set 0 or nothing.
We find the minimum cover of the Quine tableau, consisting of the minimum number of maximum intervals that include (cover) all sets on which the function is true.
The binary equivalents of true sets are as follows:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Let's arrange the binary sets by tiers and carry out gluing, as long as it is possible
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Then we build a Quine table:
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
In our table, the sets 0001 and 1011 are covered in the only possible way, therefore, the minimum intervals covering them are called obligatory and form coating core, because must be included in any coverage. In the table, the corresponding units are underlined, the intervals (0- -1, -11) form not only the core of the coverage, but also cover the entire Quine table.
Thus, we have obtained the minimal form of the investigated function in the form:
MDNF = (0 - - 1, - - 1 1) = 
Let's look at a few examples.
Tasks.
1. Find MDNF functionsf1 =
f1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
The perfect DNF of the function under study has the form:
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
The first column contains a set that did not participate in any gluing - it is the maximum interval 0100 itself. In the third column, four more maximum intervals are added to it: (-0-1, -01-, --11, 1--1 ).
We build a Quine table:
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Let's define the core of the coverage, which will include the mandatory intervals:
(0100, -0-1, -01-, --11). In this case, the coverage kernel covers the entire table as a whole.
The minimal disjunctive normal form f1 has the form:
2. Find MDNF functions f 2( x 1, x 2, x 3), which takes single values on the sets 0,2,3,6 and 7.
Let's build a truth table for f2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
SDNF =
Let's arrange the binary sets by tiers and carry out the gluing:
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
As a result of gluing, we got only two maximum intervals: (11-, --0). Without constructing a Quine table, it is obvious that they form a minimal coverage, since deleting any of these intervals will lead to the loss of sets on which the function f2(x1, x2, x3 ) true. MDNF = x1 x2 +x3.
LITERATURE
Guseva A.I. Learning computer science: tasks and methods for their solution. - M.: DIALOGUE-MEPhI, 2003.
Gorbatov V.A. Fundamentals of discrete mathematics. - M.: Science. Fizmatlit, 1999.-544s
There are five laws of the algebra of logic:
1. The law of single elements
1*X=X
0*X=0
1+X=1
0 + X = X
This law of the algebra of logic follows directly from the above expressions of the axioms of the algebra of logic.
The upper two expressions can be useful when building switches, because by applying a logical zero or one to one of the inputs of the “2I” element, you can either pass the signal to the output, or form a zero potential at the output.
The second variant of using these expressions is the possibility of selective zeroing of certain digits of a multi-digit number. With the bitwise application of the "AND" operation, you can either leave the previous value of the digit, or reset it by applying a unit or zero potential to the corresponding digits. For example, it is required to reset digits 6, 3 and 1. Then:
In the above example of using the laws of the algebra of logic, it is clearly seen that to zero the necessary digits in the mask (lower number), zeros are written in the place of the corresponding digits, and ones are written in the remaining digits. In the original number (upper number), there are units in place of 6 and 1 digits. After performing the "AND" operation, zeros appear in these places. In place of the third digit in the original number is zero. In the resulting number, zero is also present at this place. The remaining digits, as required by the condition of the problem, are not changed.
In the same way, with the help of the law of single elements, one of the basic laws of the algebra of logic, we can write units in the digits we need. In this case, it is necessary to use the lower two expressions of the law of single elements. With the bitwise application of the "OR" operation, you can either leave the previous value of the digit, or reset it by applying zero or unity potential to the corresponding digits. Let it be required to write units in 7 and 6 bits of a number. Then:
Here in the mask (lower number) we have written ones in the seventh and sixth bits. The remaining bits contain zeros, and, therefore, cannot change the initial state of the original number, which we see in the resulting number under the line.
The first and last expressions of the law of single elements allow using with more inputs as logic elements with fewer inputs. To do this, the unused inputs in the "AND" circuit must be connected to a power source, as shown in Figure 1:
Figure 1. Scheme "2I-NOT" implemented on the logic element "3I-NOT"
At the same time, unused inputs in the "OR" circuit, in accordance with the law of single elements, must be connected to the common wire of the circuit, as shown in Figure 2.
Figure 2. "NOT" circuit implemented on the "2I-NOT" element
The following laws of the algebra of logic, following from the axioms of the algebra of logic, are the laws of negation.
2. Laws of negation
a. Law of Complementary Elements
Expressions of this law of the algebra of logic are widely used to minimize logic circuits. If it is possible to isolate such subexpressions from the general expression of a logical function, then it is possible to reduce the required number of inputs of digital circuit elements, and sometimes even reduce the entire expression to a logical constant.
Another widely used law of the algebra of logic is the law of double negation.
b. Twice no
The law of double negation is used both to simplify logical expressions (and as a result of simplifying and reducing the cost of digital combinatorial circuits), and to eliminate the inversion of signals after such logical elements as "2I-NOT" and "2OR-NOT". In this case, the laws of the algebra of logic make it possible to implement given digital circuits using a limited set of logic elements.
c. Law of Negative Logic
The law of negative logic is valid for any number of variables. This law of the algebra of logic allows you to implement using the logical elements "OR" and vice versa: to implement the logical function "OR" using the logical elements "AND". This is especially useful in TTL circuitry, since it is easy to implement AND gates, but it is rather difficult to implement OR gates. Thanks to the law of negative logic, it is possible to implement the elements "OR" on the logical elements "AND". Figure 3 shows the implementation of the logic element "2OR" on the element " " and two inverters.
Figure 3. Logic element "2OR" implemented on the element "2I-NOT" and two inverters
The same can be said about the mounting "OR" scheme. If necessary, it can be turned into a mounting "AND" by using inverters at the input and output of this circuit.
3. Combination laws
The combinational laws of the algebra of logic largely correspond to the combinational laws of ordinary algebra, but there are also differences.
a. tautology law (multiple repetition)
X + X + X + X = XX * X * X * X = X
This law of the algebra of logic allows logic gates with more inputs to be used as gates with fewer inputs. For example, you can implement a two-input "2I" circuit on a logical element "3I", as shown in Figure 4:
Figure 4. Scheme "2I-NOT" implemented on the logic element "3I-NOT"
or use the "2NAND-NOT" circuit as a normal inverter, as shown in Figure 5:
Figure 5. "NOT" circuit implemented on the logical element "2I-NOT"
However, it should be warned that combining several inputs increases the input currents of the logic element and its capacity, which increases the current consumption of the previous elements and adversely affects the speed of the digital circuit as a whole.
To reduce the number of inputs in a logical element, it is better to use another law of the algebra of logic - the law of single elements, as shown above.
We continue our consideration of the laws of the algebra of logic:
b. law of movability
A + B + C + D = A + C + B + Dc. combination law
A + B + C + D = A + (B + C) + D = A + B + (C + D)d. distribution law
X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /let's prove it by expanding the brackets/ == X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3
4. Absorption rule (one variable absorbs others)
X1 + X1X2X3 =X1(1 + X2X3) = X15. Gluing rule (performed only by one variable)
Just like in ordinary mathematics, in the algebra of logic there is a precedence of operations. This is done first:
- Action in brackets
- Operation with one operand (single operation) - "NOT"
- Conjunction - "and"
- Disjunction - "OR"
- Sum modulo two.
Operations of the same rank are performed from left to right in the order in which the logical expression is written. The algebra of logic is linear and the principle of superposition is valid for it.
Literature:
Together with the article "Laws of the algebra of logic" they read:
Any logic circuit without memory is completely described by a truth table... To implement a truth table, it is enough to consider only those rows...
http://website/digital/SintSxem.php
Decoders (decoders) allow you to convert one type of binary code to another. For example...
http://website/digital/DC.php
Quite often, developers of digital equipment face the opposite problem. You want to convert an octal or decimal line code to...
http://website/digital/coder.php
Multiplexers are devices that allow you to connect several inputs to one output ...
http://website/digital/MS.php
Devices are called demultiplexers ... A significant difference from a multiplexer is ...
http://website/digital/DMS.php
To transform functions, simplify the formulas obtained by formalizing the conditions of logical problems, equivalent transformations are performed in the algebra of logic, based on the basic logical laws. Some of these laws are formulated and written in the same way as similar laws in arithmetic and algebra, others look unusual.
The laws of the algebra of logic are sometimes called theorems.
In propositional algebra, logical laws are expressed as equality of equivalent formulas.
The validity of all laws can be verified by constructing truth tables for the left and right parts of the written law. After simplifying the expression using the laws of algebra of logic, the truth tables are the same.
The validity of some laws can be proved using the tools of truth tables.
Picture 1.
Examples
Figure 3
Let's simplify the original expression using the basic laws of the algebra of logic:
Figure 4
(De Morgan's law, distributive law for AND, law of idempotence, operation of a variable with its inversion).
The table shows that for all sets of values of the variables $x$ and $y$, the formula in Fig. 2 takes the value $1$, that is, it is identically true.
Figure 6
It can be seen from the table that the Source expression takes the same values as the Simplified expression on the corresponding values of the variables $x$ and $y$.
Let's simplify the expression in Fig. 5 by applying the basic laws of the algebra of logic.
Figure 7
(De Morgan's law, absorption law, distributive law for I).
Figure 9
The table shows that for all sets of values of the variables $x$ and $y$, the formula in Fig. 8 takes the value $0$, that is, it is identically false.
Let's simplify the expression by applying the laws of the algebra of logic:
Figure 10.
Figure 12.
(De Mogrgan's law, distributive).
Let's make a truth table for the expression in Fig. 11:
Figure 13.
It can be seen from the table that the expression in Fig. 11 in some cases takes the value $1$, and in some - $0$, that is, it is feasible.
(de Morgan's rule, we take out the common factor, the rule of operations of a variable with its inversion).
(the second factor is repeated, which is possible using the law of idempotent; then the first two and last two factors are combined and the law of gluing is used).
(we introduce an auxiliary logical factor
Laws of Propositional Algebra
Algebra of propositions (algebra of logic) is a section of mathematical logic that studies logical operations on propositions and the rules for transforming complex propositions.
When solving many logical problems, it is often necessary to simplify the formulas obtained by formalizing their conditions. Simplification of formulas in the algebra of propositions is carried out on the basis of equivalent transformations based on the basic logical laws.
Laws of propositional algebra (algebra of logic) are tautologies.
Sometimes these laws are called theorems.
In propositional algebra, logical laws are expressed as equality of equivalent formulas. Among the laws, those that contain one variable are especially distinguished.
The first four of the following laws are the basic laws of propositional algebra.
Identity law:
A=A
Every concept and judgment is identical to itself.
The law of identity means that in the process of reasoning one cannot replace one thought with another, one concept with another. If this law is violated, logical errors are possible.
For example, reasoning Correctly says that language will bring you to Kyiv, but I bought a smoked language yesterday, which means that now I can safely go to Kyiv incorrectly, since the first and second words “language” denote different concepts.
In reasoning: Movement is eternal. Going to school is movement. Therefore, going to school forever the word "movement" is used in two different senses (the first - in the philosophical sense - as an attribute of matter, the second - in the ordinary sense - as an action to move in space), which leads to a false conclusion.
Law of non-contradiction :
At the same moment in time, the statement can be either true or false, there is no third. Either A is true or not A. Examples of the implementation of the law of the excluded middle:
1. The number 12345 is either even or odd, the third is not given.
2. The company operates at a loss or break even.
3. This liquid may or may not be an acid.
The law of the excluded middle is not a law recognized by all logicians as a universal law of logic. This law applies where cognition deals with a rigid situation: "either-or", "true-false". Where there is uncertainty (for example, in reasoning about the future), the law of the excluded middle often cannot be applied.
Consider the following statement: This sentence is false. It cannot be true because it claims to be false. But it cannot be false either, because then it would be true. This statement is neither true nor false, and therefore the law of the excluded middle is violated.
The paradox (Greek paradoxos - unexpected, strange) in this example arises from the fact that the sentence refers to itself. Another well-known paradox is the barber problem: In one city, the barber cuts the hair of all residents, except for those who cut their own hair. Who cuts the barber's hair? In logic, because of its formality, it is not possible to obtain the form of such a self-referential statement. This once again confirms the idea that with the help of the algebra of logic it is impossible to express all possible thoughts and arguments. Let us show how, based on the definition of propositional equivalence, the rest of the laws of the propositional algebra can be obtained.
For example, let's determine what is equivalent (equivalent) A (double negation A, i.e. negation of the negation A). To do this, we will build a truth table:
By definition of equivalence, we must find the column whose values match the values of column A. This will be column A.
Thus, we can formulate the law of double negation:
If we negate some statement twice, then the result is the original statement. For example, the statement A = Matroskin - cat is equivalent to A = It is not true that Matroskin is not a cat.
Similarly, the following laws can be derived and verified:
Constant properties:
Laws of idempotence:
No matter how many times we repeat: the TV is on or the TV is on or the TV is on... the meaning of the statement will not change. Similarly, from repetition it is warm outside, it is warm outside, ... it will not become one degree warmer.
The laws of commutativity:
A v B = B v A
A & B = B & A
Operands A and B in the operations of disjunction and conjunction can be interchanged.
Associativity laws:
A v(B v C) = (A v B) v C;
A & (B & C) = (A & B) & C.
If the expression uses only the disjunction operation or only the conjunction operation, then you can neglect the brackets or arrange them arbitrarily.
Distributivity laws:
A v (B & C) = (A v B) &(A v C)
(distributive disjunction
regarding conjunction)
A & (B v C) = (A & B) v (A & C)
(distributivity of the conjunction
regarding disjunction)
The distributive law of conjunction with respect to disjunction is similar to the distributive law in algebra, but the law of distributive disjunction with respect to conjunction has no analogue, it is valid only in logic. Therefore, it needs to be proven. The proof is best done using a truth table:
Absorption laws:
A v (A & B) = A
A & (A v B) = A
Carry out the proof of the absorption laws yourself.
De Morgan's laws:
Verbal formulations of de Morgan's laws:
Mnemonic rule: on the left side of the identity, the negation operation is above the entire statement. On the right side, it seems to be broken and negation stands above each of the simple statements, but at the same time the operation changes: disjunction to conjunction and vice versa.
Examples of the implementation of de Morgan's law:
1) The statement It is not true that I know Arabic or Chinese is identical to the statement I do not know Arabic and I do not know Chinese.
2) The statement It is not true that I learned the lesson and got a deuce for it is identical to the statement Either I did not learn the lesson, or I did not get a deuce for it.
Replacement of implication and equivalence operations
The operations of implication and equivalence are sometimes not among the logical operations of a particular computer or compiler from a programming language. However, these operations are necessary for solving many problems. There are rules for replacing these operations with sequences of negation, disjunction, and conjunction operations.
So, you can replace the implication operation in accordance with the following rule:
There are two rules for replacing the equivalence operation:
It is easy to verify the validity of these formulas by constructing truth tables for the right and left sides of both identities.
Knowledge of the rules for replacing the operations of implication and equivalence helps, for example, to correctly construct the negation of an implication.
Consider the following example.
Let the statement be given:
E = It is not true that if I win the competition, I will receive a prize.
Let A = I will win the contest,
B = I will receive a prize.
Then
From here, E = I will win the competition, but I will not receive a prize.