The laws of absorption and gluing of exclusion. Fundamentals of the algebra of logic. Verbal formulations of de Morgan's laws
Basic laws of the algebra of logic and rules for the transformation of logical expressions
In the algebra of logic, there are laws that are written in the form of relationships. Logical laws allow to produce equivalent (equivalent) transformations of logical expressions. Transformations are called equivalent if the true values of the original and the logical functions obtained after the transformation coincide for any values of the logical variables included in them.
For ease of notation, we present the basic laws of the algebra of logic for two logical variables A And IN. These laws apply to other logical variables as well.
1. The law of contradiction:
2. Law of the excluded middle:
3. Law of double negation:
4. Laws of de Morgan:
5. Laws of repetition: A&A=A; A v A = A; B & B = B; B v B = B.
6. Laws of absorption: A? (A&B)=A; A & (A ? B) = A.
7. Laws of exclusion of constants: A? 1 = 1; A? 0=A; A&1=A; A&0=0; b? 1 = 1; b? 0=B; B&1=B; B & 0 = 0.
8. Laws of gluing:
9. Law of counterposition: (A ? B) = (B ? A).
For logical variables, general mathematical laws are also valid. For ease of notation, we present general mathematical laws for three logical variables A, B and C:
1. Commutative law: A&B=B&A; A? B=B? A.
2. Association law: A & (B & C) = (A & B) & C; A? (B ? C) = (A ? B) ? C.
3. Distributive law: A & (B ? C) = (A & B) ? (A&C).
As already noted, with the help of the laws of the algebra of logic, it is possible to produce equivalent transformations of logical expressions in order to simplify them. In the algebra of logic, based on the accepted convention, the following rules (priorities) are established for performing logical operations: operations in brackets are performed first, then in the following order: inversion (negation), conjunction (&), disjunction (v), implication (?), equivalence (?)
Let's transform, for example, a logical function
by applying the appropriate laws of the algebra of logic.
Lesson Laws of algebra of logic
- learn to apply the laws of algebra of logic to simplify expressions;
- develop logical thinking;
- instill mindfulness
- X X The law of identity.
- Law of contradiction
- Law of the excluded middle
- The law of double negation
- Laws of idempotence: X X X, X X C
- The laws of commutativity (displacement): X Y Y X, X Y Y X
- Laws of associativity (combinability): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
- Distributivity (distribution) laws: X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
- De Morgan's laws,
- X 1 X, X 0 X
- X 0 0, X 1 1
Questioning the laws of the algebra of logic (on the board).
We list the most important of them:
1st law formulated by the ancient Greek philosopher Aristotle. The law of identity states that the thought contained in a statement remains unchanged throughout the entire reasoning in which this statement appears.
Law of contradiction says that no sentence can be true at the same time as its negation. “This apple is ripe” and “This apple is not ripe”.
Law of the excluded middle says that for each statement there are only two possibilities: this statement is either true or false. There is no third. “Today I get 5 or I don’t get it.” Either a proposition is true or its negation is true.
The law of double negation. To deny the negation of some statement is the same as to affirm this statement.
“It is not true that 2*24”
Laws of idempotence. There are no exponents and coefficients in the algebra of logic. The conjunction of identical "factors" is equivalent to one of them.
Laws of commutativity and associativity. Conjunction and disjunction are similar to the signs of the same name for multiplication and addition of numbers.
Unlike addition and multiplication of numbers, logical addition and multiplication are equal with respect to distributivity: not only is conjunction distributive with respect to disjunction, but disjunction is distributive with respect to conjunction.
Meaning of De Morgan's Laws(August de Morgan (1806-1871) - Scottish mathematician and logician) can be expressed in brief verbal formulations:
- the negation of a logical product is equivalent to the logical sum of the negations of factors.
— the negation of a logical sum is equivalent to the logical product of the negations of the terms.
1. Determine whether the statements are equivalent.
3. Using truth tables, prove the laws of absorption and gluing.
I. Submission of new material.
- Absorption laws: X (X Y) X, X (X Y) X
- Bonding laws: (X Y) (Y) Y, (X Y) (Y) Y
- using truth tables;
- through equivalences.
- (X Y) (Y) (X+Y) *(+Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y(+1 ) Y bonding
- X (X Y) X*X+X*Y X+X*Y X(1+Y) X absorption
- Expand the brackets (A + B) * (A + C) A * A + A * C + B * A + B * C
- By the law of idempotency A*A A , therefore, A*A + A*C + B*A + B*C A + A*C + B*A + B*C
- In statements A and A*C, we bracket A and using property A+1 1, we get A+A*C+ B*A + B*C A*(1 + C) + B*A + B*СA + B* A+B*C
- Similarly to point 3. we will take out the statement of A.
A + B*A + B*C A (1 + B) + B C A + B*C - We use the de Morgan formula, we get:
- For the expression, we apply the de Morgan formula again, we get:
- signs of logical addition;
- signs of logical multiplication,
- will be used:
- negation and logical multiplication signs
- signs of negation and logical addition.
You can prove the laws of logic:
Let us prove the laws of gluing and absorption with the help of equivalences:
P. Practical part
1. Simplification of formulas.
Example 1 Simplify the formula (A + B) * (A + C)
2. Transformations “absorption” and “gluing”
Example 2 Simplify expression A+ A*B
Solution. A+A*B A (1 + B) A - absorption
Example 3 Simplify expression A*B+A*
Solution . A*B + A* A (B + ) A - bonding
3. Any formula can be transformed in such a way that there will be no negations of complex statements in it - all negations will apply only to simple statements.
Example 4 Transform the formula so that there are no negations of complex statements.
4. Any formula can be identically transformed so that it does not use:
Example 5 Transform the formula so that it does not use logical addition signs.
Solution. Let's use the law of double negation, and then the de Morgan formula.
Conclusion: In the algebra of logic, any logical function can be expressed in terms of other logical functions, but there must be at least 2 of them, and one of them must be negation.
All operations can be expressed through conjunction and negation, disjunction and negation, implication and negation. Other operations cannot be expressed through equivalent and negation.
Exercise 1. Determine the truth of the statement.
Task 2 Determine whether the statement is a tautology?
Task 3. Determine if statements are equivalent.
1. Convert the formulas of these statements into equivalent ones, excluding logical addition:
2. Convert the formulas of these statements into equivalent ones, exclude logical multiplication.
lunina.21205s09.edusite.ru
WORLD OF LOGIC
Laws of the algebra of logic and rules for the transformation of logical expressions
Equivalent transformations of logical formulas have the same purpose as the transformations of formulas in ordinary algebra. They serve to simplify formulas or bring them to a certain form by using the basic laws of the algebra of logic.
Under the simplification of the formula, not containing the operations of implication and equivalence, they understand an equivalent transformation that leads to a formula that either contains a smaller number of conjunction and disjunction operations compared to the original one and does not contain negations of non-elementary formulas, or contains a smaller number of occurrences of variables.
Some transformations of logical formulas are similar to transformations of formulas in ordinary algebra (bracketing the common factor, using commutative and associative laws, etc.), while other transformations are based on properties that ordinary algebra operations do not have (using the distributive law for conjunction , the laws of absorption, gluing, de Morgan, etc.).
Law
Wording
1. The law of identity
Every statement is identical to itself.
2. Law of the excluded middle
A statement can be either true or false, there is no middle ground. Consequently, the result of the logical addition of the statement and its negation always takes the value "true".
3. Law of non-contradiction
A statement cannot be both true and false at the same time. If X is true, then its negation NOT X must be false. Therefore, the logical product of a proposition and its negation must be false.
4. Law of double negation
If we negate some statement twice, then we get the original statement as a result.
5. Commutative (commutative) law
6. Associative (associative) law
With the same signs, brackets can be placed arbitrarily or even omitted.
5. Distributive (distributive) law
(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)
(X/\Y)\/Z = (X\/Z)/\(Y\/Z)
Defines the rule for bracketing a general statement.
7. Law of General Inversion De Morgan's Law
The law of general inversion.
8. The law of equivalence (idempotency)
from the Latin words idem - the same and potens - strong
Laws of absorption algebra of logic
Topic 3. Fundamentals of mathematical logic 1. Logical expressions and logical operations.
2. Construction of truth tables and logical functions.
3. Laws of logic and transformation of logical expressions.
Laboratory work No. 3. Fundamentals of mathematical logic.
3. Laws of logic and rules for transforming logical expressions
The law of double negation (double negation excludes negation):
A = = Ú
Law of idempotence (from the Latin words idem - the same and potens - strong; literally - equivalent):
for logical addition: A U A = A ;
for logical multiplication: A&A=A .
Law means no exponents.
for logical multiplication: A&1 = A, A&0 = 0 .
A&=0 .
It is impossible for contradictory statements to be true at the same time.
A U = 1 .
Of the two contradictory statements about the same subject, one is always true, and the second is false, the third is not given.
for logical multiplication: A & (A Ú B) = A .
Knowledge of the laws of logic allows you to check the correctness of reasoning and evidence. Based on the laws, you can simplify complex logical expressions. This process of replacing a complex logic function with a simpler but equivalent function is called function minimization.
Some transformations of logical formulas are similar to transformations of formulas in ordinary algebra (bracketing the common factor, using commutative and associative laws, etc.), others are based on properties that ordinary algebra operations do not have (using the distribution law for conjunction, laws absorption, bonding, de Morgan, etc.).
Violations of the laws of logic lead to logical errors and the resulting contradictions.
Example 1 Simplify formula (A Ú B) & (A Ú C) .
A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C .
Thus, we have proved the law of distributivity.
Any formula can be transformed in such a way that there will be no negations of complex statements in it - all negations will apply only to simple statements.
Example 2 Simplify the expressions so that the resulting formulas do not contain the negation of complex statements.
Solution:
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 tasks 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 Kiev, but I bought a smoked language yesterday, which means that now I can safely go to Kiev 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 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 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.
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 use of 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
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.
Let's order 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, which consists 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
Logics- a science that studies the laws and forms of thinking; the doctrine of methods of reasoning and evidence.
The laws of the world, the essence of objects, the common in them, we learn through abstract thinking. The main forms of abstract thinking are concepts, judgments and inferences.
concept- a form of thinking that reflects the essential features of an individual object or class of homogeneous objects. Concepts in language are expressed in words.
The scope of the concept- a set of objects, each of which has attributes that make up the content of the concept. The concepts of general and singular are distinguished.
The following relations of concepts are distinguished by volume:
- identity or coincidence of volumes, meaning that the volume of one concept is equal to the volume of another concept;
- subordination or inclusion of volumes: the volume of one of the concepts is fully included in the volume of the other;
- exception volumes - a case in which there is not a single feature that would be in two volumes;
- intersection or partial coincidence of volumes;
- subordination volumes - the case when the volumes of two concepts, excluding each other, are included in the volume of the third.
Judgment- this is a form of thinking in which something is affirmed or denied about objects, signs or their relations.
inference- a form of thinking, through which from one or more judgments, called premises, we, according to certain rules of inference, obtain a judgment-conclusion.
Algebra in the broad sense of the word, the science of general operations similar to addition and multiplication, which can be performed not only on numbers, but also on other mathematical objects.
Examples of algebras: algebra of natural numbers, algebra of rational numbers, algebra of polynomials, algebra of vectors, algebra of matrices, algebra of sets, etc. The objects of the algebra of logic or Boolean algebra are propositions.
statement- is any sentence of any language (statement), the content of which can be determined as true or false.
Every proposition is either true or false; it cannot be both at the same time.
In natural language, utterances are expressed in declarative sentences. Exclamatory and interrogative sentences are not statements.
Statements can be expressed using mathematical, physical, chemical and other signs. From two numerical expressions, statements can be made by connecting them with equal or inequality signs.
The statement is called simple(elementary) if no part of it is itself a statement.
A statement made up of simple statements is called composite(difficult).
Simple statements in the algebra of logic are denoted by capital Latin letters:
A= (Aristotle is the founder of logic),
IN= (Bananas grow on apple trees).
Justification of the truth or falsity of simple statements is decided outside the algebra of logic. For example, the truth or falsity of the statement: "The sum of the angles of a triangle is 180 degrees" is established by geometry, and - in Euclid's geometry this statement is true, and in Lobachevsky's geometry it is false.
A true statement is assigned 1, a false one - 0. Thus, A = 1, IN = 0.
The algebra of logic is abstracted from the semantic content of statements. She is interested in only one fact - the given statement is true or false, which makes it possible to determine the truth or falsity of compound statements by algebraic methods.
Basic operations of propositional algebra.
Logical operation CONJUNCTION(lat. conjunctio - I bind):
- in natural language corresponds to the union And;
- designation: & ;
- in programming languages the notation is: and;
- other name: logical multiplication.
A conjunction is a logical operation that associates each two simple statements with a compound statement that is true if and only if both original statements are true.
Conjunction truth table:
| A | IN | A&IN |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operation DISJUNCTION(lat. disjunctio - I distinguish):
Disjunction is a logical operation that associates each two simple statements with a compound statement that is false if and only if both original statements are false and true when at least one of the two statements that form it is true.
Disjunction truth table:
| A | IN | AIN |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Logical operation INVERSE(lat. inversio - turn over):
Negation is a logical operation that associates each simple statement with a compound statement, which consists in the fact that the original statement is negated.
Negative Truth Table:
| A | not A |
| 0 | 1 |
| 1 | 0 |
The logical addition function OR (LogValue1;LogValue2;…) evaluates to TRUE (True) only when at least one boolean argument is TRUE (1).
The logical negation function NOT(LogValue) evaluates to TRUE (True) when the logical argument is FALSE (0) and, conversely, the value FALSE (False) when the logical argument is TRUE (1).
Logical operation IMPLICATION(lat. implicatio - I closely associate):
An implication is a logical operation that associates every two simple statements with a compound statement that is false if and only if the condition (the first statement) is true and the consequence (the second statement) is false.
Implication truth table:
| A | IN | AIN |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operation EQUIVALENCE(lat. aequivalens - equivalent):
- in natural language corresponds to turns of speech then and only then And if and only if;
- designation: ~ ;
- other name: equivalence.
An equivalence is a logical operation that assigns to each two simple statements a compound statement that is true if and only if both original statements are both true or both false.
Equivalence truth table:
| A | IN | A~IN |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operations have the following precedence: actions in brackets, inversion, &, , ~.
A table showing what values a compound statement takes for all combinations (sets) of values of its simple statements is called truth table compound utterance.
Compound statements in the algebra of logic are written using logical expressions. For any logical expression, it is enough to simply build a truth table.
The algorithm for constructing a truth table:
- count the number of variables n in a logical expression;
- determine the number of rows in a table m = 2 n ;
- count the number of logical operations in the formula;
- establish the sequence of execution of logical operations, taking into account brackets and priorities;
- determine the number of columns in the table: the number of variables plus the number of operations;
- write out sets of input variables, taking into account the fact that they are a natural series of n-bit binary numbers from 0 to 2 n -1;
- fill in the truth table by columns, performing logical operations in accordance with the sequence established in clause 4.
Sets of input variables, in order to avoid errors, are recommended to be listed as follows:
a) determine the number of sets of input variables;
b) divide the column of values of the first variable in half and fill the upper part of the column with 0, and the lower part -1;
c) divide the column of values of the second variable into four parts and fill each quarter with alternating groups of 0 or 1, starting with group 0;
d) continue dividing the columns of values of subsequent variables by 8, 16, etc. parts and filling them with groups of 0 or 1 until groups 0 and 1 will not consist of one character.
Example. For the formula A&(B C), construct a truth table algebraically and using spreadsheets.
The number of boolean variables is 3, therefore, the number of rows in the truth table should be 2 3 = 8.
The number of logical operations in the formula is 5, therefore, the number of columns in the truth table should be 3 + 5 = 8.
| A | IN | C | INC | A & (INC) |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Boolean function call the function F(X 1, X 2, ..., X n), whose arguments X 1, X 2, ..., X n(independent variables) and the function itself (dependent variable) take the values 0 or 1.
A table showing what values a logical function takes on for all combinations of the values of its arguments is called the truth table of a logical function. Logic function truth table n arguments contains 2 n lines, n argument value columns and 1 function value column.
Logic functions can be specified in a tabular way or analytically - in the form of appropriate formulas.
If a logical function is represented using disjunctions, conjunctions and inversions, then this form of representation is called normal.
There are 16 different logical functions from two variables.
Boolean expressions called equivalent, if their truth values coincide for any values of the logical variables included in them.
In the algebra of logic, there are a number of laws that allow equivalent transformations of logical expressions. Let us present the relations reflecting these laws.
- The law of double negation:
not (not A) = A.
Double negation excludes negation. - Commutative (commutative) law:
- for logical addition:
A B = B A;
A&B=B&A.The result of the operation on statements does not depend on the order in which these statements are taken.
- Associative (associative) law:
- for logical addition:
(A B) C = A (B C);For logical multiplication:
(A & B) & C = A & (B & C).With the same signs, brackets can be placed arbitrarily or even omitted.
- Distributive (distributive) law:
- for logical addition:
(A B) & C = (A & C) (B & C);For logical multiplication:
(A & B) C = (A C) & (B C).Defines the rule for bracketing a general statement.
- Law of general inversion (de Morgan's laws):
- for logical addition:
;For logical multiplication:
. - The law of idempotency (from the Latin words idem - the same and potens - strong; literally - equivalent):
- for logical addition:
A A = A;For logical multiplication:
A&A=A.Law means no exponents.
- Constant exclusion laws:
- for logical addition:
A 1 = 1, A 0 = A;For logical multiplication:
A&1 = A, A&0 = 0. - The law of contradiction:
A & (not A) = 0.It is impossible for contradictory statements to be true at the same time.
- Law of exclusion of the third:
A (not A) = 1.Of the two contradictory statements about the same subject, one is always true, and the second is false, the third is not given.
- Absorption law:
- for logical addition:
A(A&B)=A;For logical multiplication:
A & (A B) = A. - The law of exclusion (gluing):
- for logical addition:
(A & B) (& B) = B;For logical multiplication:
(A B) & (B) = B. - Law of contraposition (reversal rule):
(AB) = (BA).The validity of the above laws can be proved in a tabular way: write out all sets of values A and B, calculate the values of the left and right parts of the expression being proved on them, and make sure that the resulting columns match.
Example. Simplify the boolean expression:
- Efimova O., Morozov V., Ugrinovich N. Course of computer technology with the basics of informatics. Tutorial for senior classes. - M.: LLC "AST Publishing House"; ABF, 2000
- Taskbook-workshop on informatics. In 2 volumes / Ed. I.Semakina, E.Khenner. - M.: Basic Knowledge Laboratory, 2001
- Ugrinovich N. Informatics and information technologies. Grade 10-11 - M .: Basic Knowledge Laboratory, JSC "Moscow textbooks", 2001
Tasks and tests on the topic "Fundamentals of formal logic"
- Access DBMS Logic - Logical and mathematical models Grade 10
Lessons: 5 Assignments: 9 Quizzes: 1
- Solving logical problems by means of mathematical logic
Lessons: 4 Assignments: 6 Tests: 1
Dear student!
Work 1 presents three topics that form the basis of the course "Information Technology". We hope that you already have minimal experience with a computer and got acquainted with its device in middle school.
The topic "Computer communications. Internet" is of great interest lately, many young people spend almost all their free time in the global network. I would like to remind you that mastery of the Internet implies not only the ability to “surf” the network and visit interesting “chats” from time to time, but also understand the principles of organizing information in the global network, understand its structure, protocols, be able to configure the browser and e-mail programs, to know and observe the ethics of working on the Internet, and of course to use the network for its most important purpose - to expand one's horizons.
We did not cover the technology of creating Web sites in this course, believing that the minimum knowledge for creating a web home page can be gleaned from additional literature. Creating sites at a professional level requires some training, which is based on the skills of working with text and graphics, as well as the ability to program.
The topic "Logic" usually causes some confusion among students, not everyone understands the importance of studying this topic. I would like to note that knowledge of logic is important not only as a basis for further study of programming languages and principles of working with databases, but also as a "simulator" for the development of a special type of thinking. A person who excels in the study of logic has tremendous advantages in communication. It is very flattering to hear in your address: "It is logical", "there is logic in your reasoning."