Two equal opponents play chess. Equivalent transformations. Simplification of formulas. Perfect normal forms
Definition. Two equations f 1 (x) = g 1 (x) and f 2 (x) = g 2 (x) are called equivalent if the sets of their roots coincide.
For example, the equations x 2 - 9 = 0 and (2 X + 6)(X- 3) = 0 are equivalent, since both have the numbers 3 and -3 as their roots. Equations (3 X + 1)-2 = x 2- + 1 and x 2+ 1 = 0, since both have no roots, i.e. the sets of their roots coincide.
Definition. Replacing an equation with an equivalent equation is called an equivalent transformation.
Let us now find out what transformations allow us to obtain equivalent equations.
Theorem 1. Let the equation f(x) and g(x) defined on the set and h(x) is an expression defined on the same set. Then the equations f(x) = g(x)(1)and f(x) + h(x) =g(x) + h(x) (2) are equivalent.
Proof. Let us denote by T 1 - set of solutions to equation (1), and through T 2 - set of solutions to equation (2). Then equations (1) and (2) will be equivalent if T 1 = T 2. To verify this, it is necessary to show that any root of T 1 is the root of equation (2) and, conversely, any root of T 2 is the root of equation (1).
Let the number A- root of equation (1). Then a? T 1, and when substituted into equation (1) turns it into a true numerical equality f(a) = g(a), and the expression h(x) converts to a numeric expression h(a), which makes sense on the set X. Let's add to both sides of the true equality f(a) = g(a) numeric expression h(a). We obtain, according to the properties of true numerical equalities, a true numerical equality f(a) + h(a) =g(a) + h(a), which indicates that the number A is the root of equation (2).
So, it has been proven that every root of equation (1) is also a root of equation (2), i.e. T 1 With T 2.
Let it now A - root of equation (2). Then A? T 2 and when substituted into equation (2) turns it into a true numerical equality f(a) + h(a) =g(a) + h(a). Let's add to both sides of this equality the numerical expression - h(a), We obtain a true numerical equality f(x) = g(x), which indicates that the number A - root of equation (1).
So, it has been proven that every root of equation (2) is also a root of equation (1), i.e. T 2 With T 1.
Because T 1 With T 2 And T 2 With T 1, then by definition of equal sets T 1= T 2, which means that equations (1) and (2) are equivalent.
This theorem can be formulated differently: if both sides of the equation with the domain of definition X add the same expression with a variable defined on the same set, then we obtain a new equation equivalent to the given one.
From this theorem follow corollaries that are used when solving equations:
1. If we add the same number to both sides of the equation, we get an equation equivalent to the given one.
2. If any term (numerical expression or expression with a variable) is transferred from one part of the equation to another, changing the sign of the term to the opposite, then we obtain an equation equivalent to the given one.
Theorem 2. Let the equation f(x) = g(x) defined on the set X And h(x) - an expression that is defined on the same set and does not vanish for any value X from many X. Then the equations f(x) = g(x) And f(x) h(x) =g(x) h(x) are equivalent.
The proof of this theorem is similar to the proof of Theorem 1.
Theorem 2 can be formulated differently: if both sides of the equation have domain X multiplied by the same expression, which is defined on the same set and does not vanish on it, then we obtain a new equation equivalent to the given one.
A corollary follows from this theorem: If both sides of the equation are multiplied (or divided) by the same number other than zero, we obtain an equation equivalent to the given one.
Solving equations in one variable
Let's solve equation 1- x/3 = x/6, x ? R and we will justify all the transformations that we will perform in the solution process.
| Transformations | Rationale for transformation |
| 1. Let’s bring the expressions on the left and right sides of the equation to a common denominator: (6-2 X)/ 6 = X/6 | We performed an identical transformation of the expression on the left side of the equation. |
| 2. Let's discard the common denominator: 6-2 X = X | We multiplied both sides of the equation by 6 (Theorem 2) and obtained an equation equivalent to this one. |
| 3. We transfer the expression -2x to the right side of the equation with the opposite sign: 6 = X+2X. | We used the corollary of Theorem 1 and obtained an equation equivalent to the previous one and, therefore, to the given one. |
| 4. We present similar terms on the right side of the equation: 6 = 3 X. | Performed an identity transformation of the expression. |
| 5. Divide both sides of the equation by 3: X = 2. | We used the corollary from Theorem 2 and obtained an equation equivalent to the previous one, and therefore to this one |
Since all the transformations that we performed when solving this equation were equivalent, we can say that 2 is the root of this equation.
If, in the process of solving the equation, the conditions of Theorems 1 and 2 are not met, then loss of roots may occur or extraneous roots may appear. Therefore, it is important, when transforming an equation in order to obtain a simpler one, to ensure that they lead to an equation equivalent to the given one.
Consider, for example, the equation x(x - 1) = 2x, x? R. Let's divide both parts by X, we get the equation X - 1 = 2, whence X= 3, i.e. this equation has a single root - the number 3. But is this true? It is easy to see that if in this equation instead of a variable X substitute 0, it turns into the true numerical equality 0·(0 - 1) = 2·0. This means that 0 is the root of this equation, which we lost when performing transformations. Let's analyze them. The first thing we did was divide both sides of the equation by X, those. multiplied by expression1/ x, but at X= Oh it doesn't make sense. Consequently, we did not fulfill the condition of Theorem 2, which led to the loss of the root.
To make sure that the set of roots of this equation consists of two numbers 0 and 3, we present another solution. Let's move expression 2 X from right to left: x(x- 1) - 2x = 0. Let’s take it out of brackets on the left side of the equation X and give similar terms: x(x - 3) = 0. The product of two factors is equal to zero if and only if at least one of them is equal to zero, therefore x= 0 or X- 3 = 0. From here we see that the roots of this equation are 0 and 3.
In the beginning course of mathematics theoretical basis solving equations is the relationship between the components and results of actions. For example, solving the equation ( X·9):24 = 3 is justified as follows. Since the unknown is in the dividend, to find the dividend, you need to multiply the divisor by the quotient: X·9 = 24·3, or X·9 = 72.
To find the unknown factor, you need to divide the product by the known factor: x = 72:9, or x = 8, therefore, the root of this equation is the number 8.
Exercises
1 . Determine which of the following entries are equations in one variable:
A) ( X-3) 5 = 12 X; d) 3 + (12-7) 5 = 16;
b) ( X-3) 5 = 12; d) ( X-3)· y =12X;
V) ( X-3) 17 + 12; e) x 2 - 2x + 5 = 0.
2. Equation 2 X 4 + 4X 2 -6 = 0 defined on the set natural numbers. Explain why the number 1 is the root of this equation, but 2 and -1 are not its roots.
3. In equation ( X+ ...)(2X + 5) - (X - 3)(2X+ 1) = 20 one number is erased and replaced with dots. Find the erased number if you know that the root of this equation is the number 2.
4. Formulate the conditions under which:
a) the number 5 is the root of the equation f(x) = g(x);
b) the number 7 is not the root of the equation f(x) = g(x).
5. Determine which of the following pairs of equations are equivalent on the set of real numbers:
a) 3 + 7 X= -4 and 2(3 + 7l X) = -8;
6)3 + 7X= -4 and 6 + 7 X = -1;
c)3 + 7 X= -4 and l X + 2 = 0.
6. Formulate the properties of the equation equivalence relation. Which of them are used in the process of solving the equation?
7. Solve the equations (all of them are given on the set of real numbers) and justify all the transformations performed in the process of simplifying them:
a)(7 x+4)/2 – x = (3x-5)/2;
b) x –(3x-2)/5 = 3 – (2x-5)/3;
at 2- X)2-X (X + 1,5) = 4.
8. Student solved equation 5 X + 15 = 3 X+ 9 as follows: I took the number 5 out of brackets on the left side and the number 3 on the right, and I got the equation 5(x+ 3) = 3(X+ 3) and then divided both sides into the expression X+ 3. I received the equality 5 = 3 and concluded that this equation has no roots. Is the student correct?
9. Solve the equation 2/(2- x) – ½ = 4/((2- x)x); X? R. Is the number 2 the root of this equation?
10. Solve the equations using the relationship between the components and the results of the actions:
A) ( X+ 70) 4 = 328; c) (85 X + 765): 170 = 98;
b) 560: ( X+ 9) - 56; G) ( X - 13581):709 = 306.
11. Solve problems using arithmetic and algebraic methods:
a) There are 16 more books on the first shelf than on the second. If you remove 3 books from each shelf, then there will be one and a half times more books on the first shelf than on the second. How many books are on each shelf?
b) The cyclist traveled the entire distance from the camp site to the station, equal to 26 km, in 1 hour 10 minutes. For the first 40 minutes of this time he drove at one speed, and the rest of the time at a speed 3 km/h less. Find the speed of the cyclist on the first section of the journey.
Section 2. Logical equivalence of formulas. Normal forms for propositional algebra formulas
Equivalence relation
Using truth tables, you can establish for which sets of truth values of the input variables a formula will take a true or false value (as well as a statement having the corresponding logical structure), which formulas will be tautologies or contradictions, and also determine whether two given formulas equivalent.
In logic, two sentences are said to be equivalent if they are both true or false. The word “simultaneously” in this phrase is ambiguous. Thus, for the sentences “Tomorrow will be Tuesday” and “Yesterday was Sunday,” this word has a literal meaning: on Monday they are both true, and on the rest of the days of the week they are both false. For the equations " x = 2" And " 2x = 4""simultaneously" means "at the same values of the variable." The predictions “It will rain tomorrow” and “It is not true that it will not rain tomorrow” will be simultaneously confirmed (turn out to be true) or not confirmed (turn out to be false). In essence, this is the same forecast expressed in two different forms, which can be represented by the formulas X And . These formulas are both true and false. To check, it is enough to create a truth table:
| X | ||
| 1 | 0 | 1 |
| 0 | 1 | 0 |
We see that the truth values in the first and last columns coincide. It is natural to consider such formulas, as well as the corresponding sentences, to be equivalent.
Formulas F 1 and F 2 are said to be equivalent if their equivalent is a tautology.
The equivalence of two formulas is written as follows: (read: formula F 1 is equivalent to the formula F 2).
There are three ways to check whether formulas are equivalent: 1) create their equivalent and use the truth table to check whether it is a tautology; 2) for each formula, create a truth table and compare the final results; if in the resulting columns with the same sets of variable values the truth values of both formulas are equal, then the formulas are equivalent; 3) using equivalent transformations.
Example 2.1: Find out whether the formulas are equivalent: 1) , ; 2) , .
1) Let us use the first method to determine equivalence, that is, we will find out whether the equivalence of formulas is also a tautology.
Let's create an equivalent formula: . The resulting formula contains two different variables ( A And IN) and 6 operations: 1) ; 2) ; 3) ; 4) ; 5) ; 6) . This means that the corresponding truth table will have 5 rows and 8 columns:
| A | IN | ||||||
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
From the final column of the truth table it is clear that the constructed equivalence is a tautology and, therefore, .
2) In order to find out whether the formulas are equivalent, we use the second method, that is, we compile a truth table for each of the formulas and compare the resulting columns. ( Comment. In order to effectively use the second method, it is necessary that all compiled truth tables begin the same, that is the sets of variable values were the same in the corresponding rows .)
The formula contains two different variables and 2 operations, which means that the corresponding truth table has 5 rows and 4 columns:
| A | IN | ||
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
The formula contains two different variables and 3 operations, which means that the corresponding truth table has 5 rows and 5 columns:
| A | IN | |||
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
Comparing the resulting columns of the compiled truth tables (since the tables begin the same, we can not pay attention to the sets of variable values), we see that they do not match and, therefore, the formulas are not equivalent ().
The expression is not a formula (since the symbol " " does not refer to any logical operation). It expresses attitude between formulas (as well as equality between numbers, parallelism between lines, etc.).
The theorem about the properties of the equivalence relation is valid:
Theorem 2.1. Equivalence relation between propositional algebra formulas:
1) reflexively: ;
2) symmetrically: if , then ;
3) transitive: if and , then .
Laws of logic
Equivalences of propositional logic formulas are often called laws of logic. We list the most important of them:
1. – law of identity.
2. – law of excluded middle
3. – law of contradiction
4. – disjunction with zero
5. – conjunction with zero
6. – disjunction with unity
7. – conjunction with one
8. – law of double negation
9. – commutativity of the conjunction
10. – commutativity of disjunction
11. – associativity of conjunction
12. – associativity of disjunction
13. – distributivity of the conjunction
14. – distributivity of disjunction
15. – laws of idempotency
16. 
; 
– absorption laws
17. 
; 
- De Morgan's laws
18. 
– a law expressing implication through disjunction
19. 
– law of contraposition
20. – laws expressing equivalence through other logical operations
The laws of logic are used to simplify complex formulas and to prove the identical truth or falsity of formulas.
Equivalent transformations. Simplifying Formulas
If the same formula is substituted everywhere instead of some variable into equivalent formulas, then the newly obtained formulas will also turn out to be equivalent in accordance with the substitution rule. In this way, from each equivalence one can obtain as many new equivalences as desired.
Example 1: If in De Morgan's law instead X substitute, and instead Y substitute , we get a new equivalence. The validity of the resulting equivalence can be easily verified using a truth table.
If any formula that is part of the formula F, replace with a formula equivalent to the formula , then the resulting formula will be equivalent to the formula F.
Then for the formula from Example 2 the following substitutions can be made:
– the law of double negation;
- De Morgan's law;
– the law of double negation;
– law of associativity;
– the law of idempotency.
By the transitivity property of the equivalence relation, we can state that 
.
Replacing one formula with another that is equivalent to it is called equivalent transformation formulas.
Under simplification formulas that do not contain implication and equivalence signs are understood as an equivalent transformation leading to a formula that does not contain negations of non-elementary formulas (in particular, double negatives) or contains in total a smaller number of conjunction and disjunction signs than the original one.
Example 2.2: Let's simplify the formula 
.
In the first step, we applied the law that transforms the implication into a disjunction. At the second step we applied the commutative law. At the third step, we applied the law of idempotency. The fourth is De Morgan's law. And fifth is the law of double negation.
Note 1. If a certain formula is a tautology, then any formula equivalent to it is also a tautology.
Thus, equivalent transformations can also be used to prove the identical truth of certain formulas. For this this formula it is necessary to lead by equivalent transformations to one of the formulas, which are tautologies.
Note 2. Some tautologies and equivalences are combined into pairs (the law of contradiction and the law of alternative, commutative, associative laws, etc.). These correspondences reveal the so-called principle of duality .
Two formulas that do not contain implication and equivalence signs are called dual , if each of them can be obtained from the other by replacing the signs respectively with .
The principle of duality states the following:
Theorem 2.2: If two formulas that do not contain implication and equivalence signs are equivalent, then their dual formulas are also equivalent.
Normal forms
Normal form is a syntactically unambiguous way of writing a formula that implements a given function.
Using the known laws of logic, any formula can be transformed into an equivalent formula of the form 
, where and each is either a variable, or the negation of a variable, or a conjunction of variables or their negations. In other words, any formula can be reduced to an equivalent formula of simple standard form, which will be a disjunction of elements, each of which is a conjunction of individual different logical variables either with or without a negation sign.
Example 2.3: In large formulas or during multiple transformations, it is customary to omit the conjunction sign (by analogy with the multiplication sign): . We see that after the transformations carried out, the formula is a disjunction of three conjunctions.
This form is called disjunctive normal form (DNF). An individual DNF element is called elementary conjunction or constituent of a unit.
Similarly, any formula can be reduced to an equivalent formula, which will be a conjunction of elements, each of which will be a disjunction of logical variables with or without a negation sign. That is, each formula can be reduced to an equivalent formula of the form 
, where and each is either a variable, or the negation of a variable, or a disjunction of variables or their negations. This form is called conjunctive normal form
(KNF).
Example 2.4:
A separate element of CNF is called elementary disjunction or a constituent of zero.
Obviously, every formula has infinitely many DNFs and CNFs.
Example 2.5: Let's find several DNFs for the formula 
.
Perfect normal forms
SDNF (perfect DNF) is a DNF in which each elementary conjunction contains all elementary statements or their negations once; elementary conjunctions are not repeated.
SKNF (perfect CNF) is a CNF in which each elementary disjunction contains all elementary statements or their negations once; elementary disjunctions are not repeated.
Example 2.6: 1) – SDNF
2) 1 - SKNF
Let's formulate characteristic features SDNF (SKNF).
1) All members of the disjunction (conjunction) are different;
2) All members of each conjunction (disjunction) are different;
3) No conjunction (disjunction) contains both a variable and its negation;
4) Each conjunction (disjunction) contains all the variables included in the original formula.
As we see, characteristic features (but not forms!) satisfy the definition of duality, so it is enough to understand one form in order to learn how to obtain both.
From DNF (CNF) using equivalent transformations one can easily obtain SDNF (SKNF). Since the rules for obtaining perfect normal forms are also dual, we will analyze in detail the rule for obtaining SDNF, and formulate the rule for obtaining SCNF yourself, using the definition of duality.
General rule bringing the formula to SDNF using equivalent transformations:
In order to give the formula F, which is not identically false, to SDNF, it is enough:
1) lead her to some kind of DNF;
2) remove the terms of the disjunction containing the variable along with its negation (if any);
3) remove all but one of the identical terms of the disjunction (if any);
4) remove all but one of the identical members of each conjunction (if any);
5) if any conjunction does not contain a variable from among the variables included in the original formula, add a term to this conjunction and apply the corresponding distributive law;
6) if the resulting disjunction contains identical terms, use prescription 3.
The resulting formula is the SDNF of this formula.
Example 2.7: Let's find SDNF and SCNF for the formula 
.
Since the DNF for this formula has already been found (see Example 2.5), we will start by obtaining the SDNF:
2) in the resulting disjunction there are no variables along with their negations;
3) there are no identical members in the disjunction;
4) there are no identical variables in any conjunction;
5) the first elementary conjunction contains all the variables included in the original formula, and the second elementary conjunction is missing a variable z, so let’s add a member to it and apply the distributive law: ;
6) it is easy to notice that identical terms appeared in the disjunction, so we remove one (prescription 3);
3) remove one of the identical disjunctions: 
;
4) the remaining disjunctions do not have identical terms;
5) none of the elementary disjunctions contain all the variables included in the original formula, so let’s supplement each of them with the conjunction: ;
6) in the resulting conjunction there are no identical disjunctions, therefore the found conjunctive form is perfect.
Since in the aggregate the SKNF and SDNF formulas F 8 members, then most likely they were found correctly.
Each feasible (falsifiable) formula has one unique SDNF and one unique SCNF. A tautology does not have an SKNF, but a contradiction does not have a SKNF.
Definition. Two logic algebra formulas A and B are called equivalent, if they take the same logical values on any set of values included in the formulas of elementary statements.
We will denote the equivalence of formulas by the sign, and the notation A IN means that the formulas A and B are equivalent.
For example, the formulas 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.
For example, the formulas are also true , .
Formula A called identically false, if it takes the value 0 for all values of the variables included in it.
For example, the formula is identically false.
It is clear that the equivalence relation is reflexive, symmetrical and transitive.
There is the following connection between the concepts of equivalence and equivalence: if the formulas A And IN are equivalent, then the formula A IN- tautology, and vice versa, if the formula A IN- tautology, then formulas A And IN are equivalent.
The most important equivalences of the algebra of logic can be divided into three groups.
1. Basic equivalences:
Let us prove one of the laws of absorption. Consider the formula . If in this formula A= 1 then, obviously, and then as a conjunction of two true statements. Let now in the formula A x = 0. But then, by the definition of the conjunction operation, the conjunction will also be false . So, in all cases the values of the formula A match the values A, and therefore A x.
2. Equivalences expressing some logical operations through others:
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 two of them: the first and the third.
Since with the same logical values X And at if the formulas , , , are true, then the conjunction will also be true 
.
Therefore, in this case, both sides of the equivalence have the same true values.
Let it now X And at have different logical values. Then the equivalence and one of the two implications or will be false. At the same time
the conjunction will be false . Thus, in this case, both sides of the equivalence have the same logical meaning.
Consider equivalence 3. If X And at take on true values at the same time, then the conjunction will be true x&y and the false negation of a conjunction. At the same time, and and will be false, and therefore the disjunction will also be false .
Let now at least one of the variables X or at evaluates to false. Then the conjunction will be false x&y and its true negation. At the same time, the negation of at least one of the variables will be true, and therefore the disjunction will also be true .
Therefore, in all cases, both sides of equivalence 3 take the same logical values.
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 X cannot be expressed using the conjunction operator.
However, there are operations with which any of the five logical operations we use can be expressed. Such an operation is, for example, the “Scheffer’s stroke” operation. This operation is indicated by the symbol x|y and is determined by the following truth table:
| x | y | x|y |
Obviously, there are equivalences:
2) x&y (x|y)|(x|y).
From these two equivalences it follows that any formula in the algebra of logic can be replaced by an equivalent formula containing only the “Schaeffer stroke” operation.
Note that .
The operation can be entered similarly 
.
3. Equivalences expressing the basic laws of algebra of logic:
1. x&y y&x - commutativity of the conjunction.
2. x at y X- commutativity of the disjunction.
3. x&(y&y) (x&y)&z- associativity of the conjunction.
4. X(y z ) (X y) z is the associativity of the disjunction.
5. x&(y z) (x&y) (x&z)- distributivity of conjunction relative to disjunction.
6. X (y&z) (X y)& (x z ) - distributivity of the disjunction relative to the conjunction.
Let us prove the last of the listed laws. If X= 1, then the formulas will be true X (y& z), X y, x z . But then the conjunction will also be true (X y)& (x z ). Thus, when X= 1, both sides of the equivalence 6 take the same logical values (true).
Let it now x = 0. Then X (y&z) y&z,x at at And x z z , and therefore the conjunction X (y&z) y&z. Therefore, here both sides of equivalence 6 are equivalent to the same formula y&z, and therefore take the same logical values.
§ 5. Equivalent transformations of formulas
Using the equivalences of groups I, II and III, you can replace part of the formula or a formula with an equivalent formula. Such transformations of formulas are called equivalent.
Equivalent transformations are used to prove equivalences, to bring formulas to a given form, to simplify formulas.
Formula A is considered simpler than its equivalent formula IN, if it contains fewer letters, fewer logical operations. In this case, the operations of equivalence and implication are usually replaced by the operations of disjunction and conjunction, and negation is classified as elementary statements. Let's look at a number of examples.
1. Prove equivalence 
.
Using equivalences of groups I, II and III
2.
Simplify the formula 
.
Let's write a chain of equivalent formulas:
3. Prove the identical truth of the formula
Let's write a chain of equivalent formulas:
Boolean algebra
The equivalences of group III indicate that the algebra of logic has commutative and associative laws regarding the operations of conjunction and disjunction and a distributive law of conjunction regarding disjunction; the same laws also apply in the algebra of numbers. Therefore, the same transformations can be performed on the formulas of the algebra of logic that are carried out in the algebra of numbers (opening brackets, putting them in brackets, putting a common factor out of brackets).
But in the algebra of logic other transformations are possible, based on the use of equivalences:
This feature allows us to come to far-reaching generalizations.
Consider the non-empty set M elements of any nature ( x,y,z,...} , in which the relation “=” (equal) and three operations are defined: “+” (addition), “ ” (multiplication) and “-” (negation), subject to the following axioms:
Commutative laws:
1a. x + y = y + x, 1b. X y = y X.
Association laws:
2a. x + (y + z)= (x + y) + z, 2b. X (y z) = (x y) z.
Distributive laws:
3a. (x + y) z = (x z ) + (y G) 3b. (x y) + z = (x+z) (y + z).
Laws of idempotency:
4a. x + x = x, 4b. X x = x.
Law of double negation:
De Morgan's laws:
6a. , 6b . .
Laws of absorption:
7a. x + (y X)= X, 7b. X (y + x) = x.
So many M called Boolean algebra.
If under the main elements x, y, z, ... If we mean statements by the operations “+”, “ ”, “-” disjunction, conjunction, negation, respectively, and the equal sign is considered as an equivalence sign, then, as follows from the equivalences of groups I, II and III, all the axioms of Boolean algebra are satisfied.
In those cases when, for a certain system of axioms, it is possible to select specific objects and specific relationships between them so that all axioms are satisfied, they say that it has been found interpretation(or model) of this system of axioms.
This means that the algebra of logic is an interpretation of Boolean algebra. Boole algebra has other interpretations. For example, if under the main elements x, y, z, ... sets M we mean sets, by the operations “+”, “ ”, “-” union, intersection, addition, respectively, and by the equal sign - the equal sign of sets, then we come to the algebra of sets. It is not difficult to verify that in set algebra all the axioms of Boole algebra are satisfied.
Among the various interpretations of Boolean algebra, there are interpretations of a technical nature. One of them will be discussed below. As will be shown, it plays an important role in modern automation.
Logic algebra functions
As already noted, the meaning of a logical algebra formula completely depends on the meanings of the statements included in this formula. Therefore, the formula of the algebra of logic is a function of the elementary statements included in it.
For example, the formula is a function
three variables f(x,y,z). The peculiarity of this function is the fact that its arguments take one of two values: zero or one, and at the same time the function also takes one of two values: zero or one.
Definition. Logic algebra function hectares of variables (or Boolean function) is called a function of ha variables, where each variable takes two values: 0 and 1, and the function can only take one of two values: 0 or 1.
It is clear that identically true and identically false formulas of the algebra of logic represent constant functions, and two equivalent formulas express the same function.
Let's find out what is the number of functions of n variables. Obviously, each function of the algebra of logic (as well as the formula of the algebra of logic) can be specified using a truth table, which will contain 2 n rows. Therefore, each function of n variables takes 2 n values consisting of zeros and ones. Thus, a function of n variables is completely determined by a set of values of zeros and ones of length 2 n. (The total number of sets of zeros and ones of length 2 n is equal to . This means that the number of different functions of the algebra of logic P variables are equal to .
In particular, there are four different functions of one variable, and sixteen different functions of two variables. Let us write down all the functions of the algebra of logic in one And two variables.
Consider a truth table for various functions of one variable. It obviously looks like:
| x | f 1 (x) | f2(x) | f 3 (x) | f 3 (x) |
| 1 | ||||
From this table it follows that two functions of one variable will be constant: f 1 (x)= 1, f 4 (x) = 0, a f2(x) X, And f 3 (x) .
The truth table for all possible functions of two variables has the form:
f i = f i (x,y)
| x | y | f 1 | f 2 | f 3 | f 4 | f 5 | f 6 | f 7 | f 8 | f 9 | f 10 | f 11 | f 12 | f 13 | f 14 | f 15 | f 16 |
It is clear that the analytical expressions of these functions can be written as follows.
Allowing you to move from the equation being solved to the so-called equivalent equations And corollary equations, from whose solutions it is possible to determine the solution to the original equation. In this article we will analyze in detail which equations are called equivalent and which are called corollary equations, give the corresponding definitions, give explanatory examples and explain how to find the roots of an equation using the known roots of an equivalent equation and a corollary equation.
Equivalent equations, definition, examples
Let us define equivalent equations.
Definition
Equivalent equations- these are equations that have the same roots or do not have roots.
Definitions that are the same in meaning, but slightly different in wording, are given in various mathematics textbooks, for example,
Definition
The two equations f(x)=g(x) and r(x)=s(x) are called equivalent, if they have the same roots (or, in particular, if both equations have no roots).
Definition
Equations that have the same roots are called equivalent equations. Equations that do not have roots are also considered equivalent.
By the same roots is meant the following: if some number is the root of one of the equivalent equations, then it is also the root of any other of these equations, and not one of the equivalent equations can have a root that is not the root of any other of them. these equations.
Let us give examples of equivalent equations. For example, three equations 4 x = 8, 2 x = 4 and x = 2 are equivalent. Indeed, each of them has a single root 2, so they are equivalent by definition. Another example: two equations x·0=0 and 2+x=x+2 are equivalent, the sets of their solutions coincide: the root of both the first and second of them is any number. The two equations x=x+5 and x 4 =−1 are also examples of equivalent equations; they both have no real solutions.
To complete the picture, it is worth giving examples of unequal equations. For example, the equations x=2 and x 2 =4 are not equivalent, since the second equation has a root −2, which is not the root of the first equation. Equations and are also not equivalent, since the roots of the second equation are any numbers, and the number zero is not the root of the first equation.
The stated definition of equivalent equations applies to both equations with one variable and equations with a large number of variables. However, for equations with two, three, etc. variables, the word “roots” in the definition must be replaced with the word “solutions”. So,
Definition
Equivalent equations- these are equations that have the same solutions or do not have them.
Let's show an example of equivalent equations with several variables. x 2 +y 2 +z 2 =0 and 5 x 2 +x 2 y 4 z 8 =0 - here is an example of equivalent equations with three variables x, y and z, they both have a unique solution (0, 0, 0) . But equations with two variables x+y=5 and x·y=1 are not equivalent, since, for example, a pair of values x=2, y=3 is a solution to the first equation (when substituting these values into the first equation we get the correct equality 2+3=5), but is not a solution to the second (when substituting these values into the second equation we get the incorrect equality 2·3=1).
Consequence equations
Here are the definitions of corollary equations from school textbooks:
Definition
If each root of the equation f(x)=g(x) is at the same time a root of the equation p(x)=h(x), then the equation p(x)=h(x) is called consequence equations f(x)=g(x) .
Definition
If all the roots of the first equation are roots of the second equation, then the second equation is called consequence first equation.
Let's give a couple of examples of corollary equations. The equation x 2 =3 2 is a consequence of the equation x−3=0. Indeed, the second equation has a single root x=3, this root is also the root of the equation x 2 =3 2, therefore, by definition, the equation x 2 =3 2 is a consequence of the equation x−3=0. Another example: the equation (x−2)·(x−3)·(x−4)=0 is a consequence of the equation 
, since all the roots of the second equation (there are two of them, these are 2 and 3) are obviously the roots of the first equation.
From the definition of a corollary equation it follows that absolutely any equation is a consequence of any equation that has no roots.
It is worth citing several rather obvious consequences from the definition of equivalent equations and the definition of a corollary equation:
- If two equations are equivalent, then each of them is a consequence of the other.
- If each of two equations is a consequence of the other, then these equations are equivalent.
- Two equations are equivalent if and only if each of them is a consequence of the other.
1. Two equal players play a game in which there are no draws. What is the probability for the first player to win: a) one game out of two? b) two out of four? c) three out of six?
Answer: A) ; b) ; V)
3. Segment AB separated by a dot WITH in a ratio of 2:1. Four points are thrown at random on this segment. Find the probability that two of them will be to the left of point C, and two - to the right.
Answer:
4. Find the probability that event A will occur exactly 70 times in 243 trials if the probability of this event occurring in each trial is 0.25.
Answer: .
5. The probability of having a boy is 0.515. Find the probability that among 100 newborns there will be an equal number of boys and girls.
Answer: 0,0782
6. The store received 500 bottles in glass containers. The probability that any bottle will be broken during transportation is 0.003. Find the probability that the store will receive broken bottles: a) exactly two; b) less than two; c) at least two; d) at least one.
Answer: a) 0.22; b) 0.20; c) 0.80; d) 0.95
7. An automobile plant produces 80% of cars without significant defects. What is the probability that among the 600 cars delivered from the factory to the automobile exchange, there will be at least 500 cars without significant defects?
Answer: 0,02.
8. How many times must a coin be tossed so that with a probability of 0.95 one can expect that the relative frequency of appearance of the coat of arms will deviate from the probability R=0.5 appearance of the coat of arms with one coin toss by no more than 0.02?
Answer: n ≥ 2401.
9. The probability of an event occurring in each of 100 independent events is constant and equal to p=0.8. Find the probability that the event will appear: a) at least 75 times and not more than 90 times; b) at least 75 times; c) no more than 74 times.
Answer: a B C) .
10. The probability of an event occurring in each of the independent trials is 0.2. Find what deviation of the relative frequency of occurrence of an event from its probability can be expected with a probability of 0.9128 with 5000 trials.
Answer:
11. How many times must a coin be tossed so that with probability 0.6 one can expect that the deviation of the relative frequency of appearance of the coat of arms from the probability p=0.5 will be no more than 0.01 in absolute value.
Answer: n = 1764.
12. The probability of an event occurring in each of 10,000 independent trials is 0.75. Find the probability that the relative frequency of occurrence of an event will deviate from its probability in absolute value by no more than 0.01.
Answer: .
13. The probability of an event occurring in each of the independent trials is 0.5. Find the number of trials n, at which with a probability of 0.7698 we can expect that the relative frequency of the occurrence of an event will deviate from its probability in absolute value by no more than 0.02.
Loading...