§4. Equivalent, TI and TL formulas of the algebra of logic. Basic equivalences. (Laws of logical operations). The law of duality.
Definition.
Two logic algebra formulas A and B are called EQUIVALENT if they take the same logical values on any set of elementary statements included in the formulas. We will denote the equivalence of formulas with the sign º, and the notation A ºB means that formulas A and B are equivalent.
Formula A is called IDENTICALLY TRUE (or TAUTOLOGY) if it takes the value 1 for all values of the variables included in it.
A formula is called IDENTICALLY FALSE (or CONTRADITION) if it takes the value 0 for all values of the variables included in it.
The following connection exists between the concepts of equivalence and equivalence: if the formulas A and B are equivalent, then the formula A"B is a tautology, and vice versa, if the formula A"B is a tautology, then the formulas A and B are equivalent.
The most important equivalences of the algebra of logic can be divided into three groups.
1. Basic equivalences.
Laws of idempotency.
Law of contradiction
Law of the excluded middle
Law of Double Negation Removal
absorption laws
2. Equivalences expressing some logical operations through others.
Here 3, 4, 5, 6 are Morgan's laws.
It is clear that equivalences 5 and 6 are obtained from equivalences 3 and 4, respectively, if we take negations from both parts of the latter and use the law of removing double negations.
Thus, the first four equivalences need proof. Let's prove one of them: the first one.
Since with the same logical values x and y the formulas https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21"> are true. Therefore, in this case both the parts of equivalence have the same true values.
Now let x and y have different logical values. Then the equivalence and one of the two implications or will be false. But the conjunction will also be false 
.
Thus, in this case, both sides of the equivalence have the same logical meanings.
Equivalences 2 and 4 are proved in a similar way.
From the equivalences of this group it follows that any formula in the algebra of logic can be replaced by an equivalent formula containing only two logical operations: conjunction and negation or disjunction and negation.
No further elimination of logical operations is possible. So, if we use only conjunction, then such a formula as negation cannot be expressed using the conjunction operation.
However, there are operations with which any of the five logical operations we use can be expressed. Such an operation is, for example, the operation “Schaeffer's stroke”. This operation is indicated by the symbol ½ left " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">
Laws of propositional algebra
Propositional algebra (algebra of logic) is a section of mathematical logic that studies logical operations on statements and rules for transforming complex statements.
When solving many logical problems It is often necessary to simplify formulas obtained by formalizing their conditions. Simplification of formulas in propositional algebra is carried out on the basis of equivalent transformations based on basic logical laws.
Laws of propositional algebra (algebra of logic) - these are tautologies.
Sometimes these laws are called theorems.
In propositional algebra, logical laws are expressed in the form of equality of equivalent formulas. Among the laws, those that contain one variable stand out.
The first four laws below are the basic laws of propositional algebra.
Law of identity:
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, the reasoning is correct that they say that language will take you to Kyiv, but I bought smoked tongue yesterday, which means that now I can safely go to Kyiv incorrectly, since the first and second words “language” mean different concepts.
In reasoning: Movement is eternal. Walking to school is movement. Consequently, going to school forever the word "movement" is used in two different senses (the first - in philosophical sense- as an attribute of matter, the second - in the ordinary sense - as the action of moving in space), which leads to a false conclusion.
Law of non-contradiction :
At the same moment in time, a statement can be either true or false, there is no third option. Either A is true or not A. Examples of fulfilling the law of excluded middle:
1. The number 12345 is either even or odd, there is no third option.
2. The company operates at a loss or break-even.
3. This liquid may or may not be an acid.
The law of 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 uncertainty occurs (for example, in reasoning about the future), the law of excluded middle often cannot be applied.
Consider the following statement: This sentence is false. It cannot be true because it states that it is false. But it cannot be false either, because then it would be true. This statement is neither true nor false, and therefore violates the law of excluded middle.
The paradox (Greek paradoxos - unexpected, strange) in this example arises due to the fact that the sentence refers to itself. Another well-known paradox is the hairdresser problem: In one city, a hairdresser cuts the hair of all residents, except those who cut their own hair. Who cuts the barber's hair? In logic, due to its formality, it is not possible to obtain the form of such a self-referring 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 remaining laws of propositional algebra can be obtained.
For example, let’s determine what A is equivalent (equivalent to) (double negation of A, i.e., the negation of the negation of A). To do this, we’ll build a truth table:
By definition of equivalence, we must find the column whose values coincide with the values of column A. This will be column A.
Thus, we can formulate the law of double negation:
If you negate a statement twice, the result is the original statement. For example, the statement A = Matroskin - cat is equivalent to statement A = It is not true that Matroskin is not a cat.
In a similar way, the following laws can be derived and verified:
Properties of constants:
Laws of idempotency:
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 repeating it, it’s warm outside, it’s warm outside,... it won’t get one degree warmer.
Laws of commutativity:
A v B = B v A
A & B = B & A
Operands A and B can be interchanged in the disjunction and conjunction operations.
Laws of associativity:
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 parentheses or arrange them arbitrarily.
Distributive laws:
A v (B & C) = (A v B) &(A v C)
(distributivity of disjunction
relative to conjunction)
A & (B v C) = (A & B) v (A & C)
(distributivity of the conjunction
regarding disjunction)
The distributive law of a conjunction relative to a disjunction is similar to the distributive law in algebra, but the distributive law of a disjunction relative to a conjunction has no analogue; it is valid only in logic. Therefore it is necessary to prove it. The proof is most conveniently carried out using a truth table:
Laws of absorption:
A v (A & B) = A
A & (A v B) = A
Prove the laws of absorption yourself.
De Morgan's laws:
Verbal formulations of De Morgan's laws:
Mnemonic rule: on the left side of the identity, the negation operation stands above the entire statement. On the right side, it seems to break and the negation stands over each of the simple statements, but at the same time the operation changes: disjunction to conjunction and vice versa.
Examples of 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 bad grade in it is identical to the statement Either I didn’t learn the lesson, or I didn’t get a bad grade in it.
Replacing the operations of implication and equivalence
The operations of implication and equivalence are sometimes not among the logical operations of a particular computer or translator from a programming language. However, to solve many problems these operations are necessary. There are rules for replacing these operations with sequences of negation, disjunction and conjunction operations.
Thus, the implication operation can be replaced 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 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 competition,
B = I will receive a prize.
Then
From here, E = I will win the competition, but I will not receive a prize.
Discrete Mathematics: Mathematical Logic
Lecture 8
Minimization of Boolean functions. Quine-McCluskey method
Boole's laws of algebra
IN mathematical logic a special algebra is defined, the Boole algebra, containing the operations of logical multiplication, logical addition and negation ( , +, - ), which allows for identical transformations of logical expressions. These laws includeLaw of idempotency (sameness)
Commutativity law
a b = b a
Law of associativity
a + (b + c) = (a + b) + c
a (b c) = (a b) c
Distributivity laws
Distributivity of conjunction relative to disjunction
A (b + c) = a b + a c
Distributivity of a disjunction relative to a conjunction
A + b c = (a + b) (a + c)
law of double negation
De Morgan's laws
Laws of absorption
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 validity of all the laws discussed above can be easily proven, for example, using truth tables.
Additional laws
Additional laws of Boole algebra are consequences of the basic laws and are very useful in simplifying the writing of logical functions.
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 law of distributivity:
Blake-Poretsky law
Applying the laws of action with logical constants, idempotency and gluing, this identity can be proven as follows:
Law of convolution of logical expression
This identity can be proven by consistently using the laws of working with logical constants, distributivity, idempotency and gluing:
Simplifying Logic Functions
For normal forms of function representation, the concept of function complexity is defined as the number of primary terms in such a representation. Normal form transformations to reduce the complexity of a function are called simplification . To simplify logical functions, all the laws of logical algebra are used.Tasks.
Simplify SDNF with the following functions:
1. (a b) c
2. (a b) c
Let's represent the function in perfect disjunctive form and simplify it using the laws of logical algebra:
3.
Let's represent the function in perfect disjunctive form and simplify it using the laws of logical algebra:
SDNF = 
No further simplification is possible.
4. 
Let's represent the function in perfect disjunctive form and simplify it using the laws of logical algebra:
SDNF =
5. 
Let's represent the function in perfect disjunctive form and simplify it using the laws of logical algebra:
Quine-McCluskey method
Minimization of logical functions can be carried out using the Quine-McCluskey method, which consists of four steps:
Let us represent the sets (constituents) on which the function is true in the form of binary equivalents.
Let's arrange the binary equivalents into tiers (according to the number of units of binary equivalents) and glue (apply the gluing rule to the corresponding constituents) sets in adjacent tiers, obtaining maximum intervals as long as possible; We mark each set involved in gluing. Only those sets or intervals are merged, the difference in which is 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 we put 1 at the intersection of the corresponding row and column, otherwise we put 0 or nothing.
We find the minimum covering of the Quine table, consisting of the minimum number of maximal intervals that include (cover) all tuples on which the function is true.
The binary equivalents of the true sets are:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Let's arrange binary sets into tiers and carry out gluing as long as 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 the 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 mandatory and form coating core, because must be included in any coating. In the table, the corresponding units are underlined; the intervals (0- -1,- -11) form not only the core coverage, but also cover the entire Quine table.
Thus, we obtained the minimal form of the function under study 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 was not involved in any merging - it itself is the maximum interval 0100. In the third column four more maximum intervals are added to it: (-0-1, -01-, --11, 1--1 ).
We build the 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 in this case, the coverage kernel covers the entire table as a whole.
The minimal disjunctive normal form f1 is:
2. Find MDNF functions f 2( x 1, x 2, x 3), which takes single values on 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 binary sets into tiers and perform 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 the Quine table, it is obvious that they form a minimum coverage, because removing any of these intervals will result in the loss of sets on which the function f2(x1, x2, x3 ) true. MDNF = x1 x2 +x3.
LITERATURE
Guseva A.I. Learning computer science: problems and methods for solving them. - M.: DIALOG-MEPhI, 2003.
Gorbatov V.A. Fundamentals of discrete mathematics. - M.: Science. Fizmatlit, 1999.-544s
Modern computers, based on “ancient” electronic computers, rely on certain postulates as basic principles of operation. They are called the laws of algebra of logic. For the first time such a discipline was described (of course, not in as much detail as in modern form) by the ancient Greek scientist Aristotle.
Representing a separate branch of mathematics, within which the calculus of propositions is studied, the algebra of logic has a number of clearly structured conclusions and conclusions.
In order to better understand the topic, we will analyze concepts that will help in the future to learn the laws of logical algebra.
Perhaps the main term in the discipline being studied is statement. This is a certain statement that cannot be both false and true. He always has only one of these characteristics. In this case, it is conventionally accepted to assign the value 1 to truth, 0 to falsity, and call the statement itself a certain A, B, C. In other words, the formula A = 1 means that statement A is true. You can deal with statements in the most in various ways. Let's briefly consider the actions that can be performed with them. We also note that the laws of logical algebra cannot be learned without knowing these rules.
1. Disjunction two statements - the result of the “or” operation. Can be either false or true. The symbol "v" is used.
2. Conjunction. The result of such an action performed on two statements will be new only in the case when both original statements are true. The “and” operator is used, the symbol “^”.
3. Implication. Operation “if A then B”. 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 in cases where both variables have the same scores. The symbol is used "<->».
There are also a number of operations close to implication, but they will not be considered in this article.
Now let’s consider in detail the basic laws of logical algebra:
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. Conjunctive or associative. According to this law, variables in the operations of conjunction or disjunction can be combined into groups.
3. Distributive or distributive. The essence of the law is that identical variables in equations can be taken out of brackets without changing the logic.
4. De Morgan's law (inversion or negation). The negation of the conjunction operation is equivalent to the disjunction of the negation of the original variables. The negation of a disjunction, in turn, is equal to the conjunction of the negation of the same variables.
5. Double negative. The negation of a certain statement twice results in the original statement, and 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 exclusion of the third. Among two contradictory statements, one is always true, the other is false, and 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. 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 together disappears. Example for logical addition:
(x^y) v (-x^y)=y.
We have considered only the most used laws of logical algebra, of which in fact there may be many more, since logical equations often take on a long and ornate form, which can be shortened by applying a number of similar laws.
As a rule, for ease of calculation and identification of results, special tables are used. All existing laws of logical algebra, the table for which has the general structure of a grid rectangle, are written out, distributing each variable into a separate cell. The larger the equation, the easier it is to deal with using tables.
There are five laws of logical algebra:
1. 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 constructing switches, because by applying a logical zero or one to one of the inputs of the “2I” element, you can either pass a signal to the output or form a zero potential at the output.
The second option for using these expressions is the possibility of selectively zeroing certain digits of a multi-digit number. When applying the “AND” operation bit by bit, you can either leave the previous value of the bit or reset it to zero by applying a unit or zero potential to the corresponding bits. For example, you need to reset digits 6, 3 and 1. Then:
In the given example of using the laws of logical algebra, it is clearly visible that to reset the necessary digits in the mask (lower number), zeros are written in place of the corresponding digits, and ones are written in the remaining digits. In the original number (top number) there are ones in place of the 6th and 1st digits. After performing the "AND" operation, zeros appear in these places. In place of the third digit in the original number there is a zero. The resulting number also contains a zero in this place. The remaining digits, as required by the conditions of the problem, are not changed.
In the same way, using the law of single elements, one of the basic laws of logical algebra, 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. When applying the “OR” operation bit by bit, you can either leave the previous value of the bit or reset it to zero by applying a zero or one potential to the corresponding bits. Suppose you want to write units into the 7th and 6th bits of a number. Then:
Here in the mask (lower number) we wrote ones in the seventh and sixth bits. The remaining bits contain zeros, and therefore cannot change the original state of the original number, which is what we see in the resulting number under the line.
The first and last expressions of the law of single gates allow use with a large number of inputs as logic gates with a smaller number of 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. Circuit "2I-NOT", implemented on a logical element "3I-NOT"
At the same time, the 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 next laws of the algebra of logic, which follow from the axioms of the algebra of logic, are the laws of negation.
2. Laws of negation
a. Law of Additional Elements
Expressions of this law of logical algebra are widely used to minimize logic circuits. If you can isolate such subexpressions from the general expression of a logical function, then you can 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 logical algebra is the law of double negation.
b. Twice no
The law of double negation is used both to simplify logical expressions (and as a consequence to simplify and reduce the cost of digital combinatorial circuits), and to eliminate signal inversion after such logical elements as “2AND-NOT” and “2OR-NOT”. In this case, the laws of logical algebra make it possible to implement given digital circuits using a limited set of logical elements.
c. Law of Negative Logic
The law of negative logic is valid for any number of variables. This law of logic algebra allows you to implement “OR” using logical elements and vice versa: to implement the “OR” logical function using “AND” logical elements. This is especially useful in TTL circuitry, since it is easy to implement “AND” logic gates, but “OR” logic gates are quite difficult to implement. Thanks to the law of negative logic, it is possible to implement “OR” elements on “AND” logical elements. Figure 3 shows the implementation of a logical element "2OR" on an 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 wiring "OR" circuit. 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 combination laws of logical algebra largely correspond to the combination laws of ordinary algebra, but there are also differences.
a. law of tautology (multiple repetition)
X + X + X + X = XX * X * X * X = X
This law of logic algebra allows logic gates with more inputs to be used as logic gates with fewer inputs. For example, you can implement a two-input “2I” circuit on a “3I” logic element, as shown in Figure 4:
Figure 4. “2I-NOT” circuit implemented on a “3I-NOT” logic element
or use the “2AND-NOT” circuit as a regular inverter, as shown in Figure 5:
Figure 5. "NOT" circuit implemented on a logical element "2I-NOT"
However, it should be warned that combining several inputs increases the input currents of the logic element and its capacitance, which increases the current consumption of the previous elements and negatively 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 logical algebra - the law of single elements, as shown above.
Let us continue our consideration of the laws of logical algebra:
b. law of mobility
A + B + C + D = A + C + B + Dc. law of combination
A + B + C + D = A + (B + C) + D = A + B + (C + D)d. law of distribution
X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /we will prove this by opening the parentheses/ == 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 (carries out only one variable)
Just like in ordinary mathematics, in the algebra of logic there is a precedence of operations. In this case, the first thing to do is:
- Action in parentheses
- Operation with one operand (single-place operation) - "NOT"
- Conjunction - "And"
- Disjunction - "OR"
- Modulo two sum.
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:
Read along with the article “Laws of Algebra of Logic”:
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://site/digital/SintSxem.php
Decoders (decoders) allow you to convert some types of binary codes into others. For example...
http://site/digital/DC.php
Quite often, digital equipment developers are faced with the opposite problem. You need to convert octal or decimal linear code to...
http://site/digital/Coder.php
Multiplexers are devices that allow you to connect multiple inputs to one output...
http://site/digital/MS.php
Demultiplexers are devices... A significant difference from a multiplexer is...
http://site/digital/DMS.php