Wiring diagram, designed to perform any logical operation with the input data, is called a logical element. The input data is represented here in the form of voltages of various levels, and the result of a logical operation at the output is also obtained in the form of a voltage of a certain level.
Operands in this case are fed - signals are received at the input of the logic element in the form of a high or low level voltage, which essentially serve as input data. So, a high-level voltage - a logical one - indicates the true value of the operand, and a low-level voltage of 0 - a false value. 1 - TRUE, 0 - FALSE.
Logic element- an element that implements certain logical relationships between input and output signals. Logic gates are commonly used to build logic circuits computers, discrete circuits of automatic control and management. For all types of logical elements, regardless of their physical nature, discrete values of input and output signals are characteristic.
Logic elements have one or more inputs and one or two (usually inverse to each other) outputs. The values of "zeros" and "ones" of the output signals of logic elements are determined by the logic function that the element performs, and the values of "zeros" and "ones" of the input signals, which play the role of independent variables. There are elementary logic functions, from which you can compose any complex logical function.
Depending on the design of the element circuit, on its electrical parameters, the logical levels (high and low voltage levels) of the input and output have the same values for high and low (true and false) states.
Traditionally, logic elements are produced in the form of special radio components - integrated circuits. Boolean operations, such as conjunction, disjunction, negation and modulo addition (AND, OR, NOT, exclusive OR) are the main operations performed on logical elements of basic types. Let's take a closer look at each of these types of logical elements.
Logical element "AND" - conjunction, logical multiplication, AND
"AND" - a logical element that performs a conjunction or logical multiplication operation on the input data. This element can have from 2 to 8 (the most common in production are “AND” elements with 2, 3, 4 and 8 inputs) inputs and one output.
Symbols of logical elements "AND" with a different number of inputs are shown in the figure. In the text, the logical element "AND" with one or another number of inputs is designated as "2I", "4I", etc. - the element "AND" with two inputs, with four inputs, etc.
The truth table for the 2I element shows that the output of the element will be a logical unit only if the logical units are simultaneously at the first input AND at the second input. In the other three possible cases, the output will be zero.
In Western schemes, the icon of the "And" element has a straight line at the entrance and a rounding at the exit. On domestic schemes - a rectangle with the symbol "&".
Logical element "OR" - disjunction, logical addition, OR
"OR" - a logical element that performs a disjunction or logical addition operation on the input data. It, like the “AND” element, is available with two, three, four, etc. inputs and one output. Symbols of logical elements "OR" with a different number of inputs are shown in the figure. These elements are designated as follows: 2OR, 3OR, 4OR, etc.
The truth table for the element "2OR" shows that for the appearance of a logical unit at the output, it is enough that the logical unit is at the first input OR at the second input. If logical ones are at once on two inputs, the output will also be one.
In Western schemes, the icon for the "OR" element has a rounded entry and a rounded, pointed exit. On domestic schemes - a rectangle with the symbol "1".
Logic element "NOT" - negation, inverter, NOT
"NOT" - a logical element that performs a logical negation operation on the input data. This element, which has one output and only one input, is also called an inverter, since it actually inverts (inverts) the input signal. The figure shows the symbol of the logical element "NOT".
The truth table for the inverter shows that a high input potential gives a low output potential and vice versa.
In Western schemes, the icon of the "NOT" element has the shape of a triangle with a circle at the exit. On domestic schemes - a rectangle with the symbol "1", with a circle at the exit.
Logical element "AND-NOT" - conjunction (logical multiplication) with negation, NAND
"AND-NOT" - a logical element that performs a logical addition operation on the input data, and then a logical negation operation, the result is output. In other words, it is basically an "AND" element, complemented by a "NOT" element. The figure shows the symbol of the logical element "2I-NOT".
The truth table for the "NAND" element is the opposite of the table for the "AND" element. Instead of three zeros and one - three ones and zero. The "NAND" element is also called the "Schaeffer element" in honor of the mathematician Henry Maurice Schaeffer, who first noted the significance of this in 1913. Designated as "I", only with a circle at the exit.
Logical element "OR-NOT" - disjunction (logical addition) with negation, NOR
"OR-NOT" - a logical element that performs a logical addition operation on the input data, and then a logical negation operation, the result is output. In other words, this is an "OR" element, supplemented by a "NOT" element - an inverter. The figure shows the symbol of the logic element "2OR-NOT".
The truth table for the element "OR-NOT" is opposite to the table for the element "OR". A high potential at the output is obtained only in one case - both inputs are fed simultaneously with low potentials. Referred to as "OR", only with a circle at the output indicating inversion.
Logical element "exclusive OR" - addition modulo 2, XOR
"XOR" - a logical element that performs the operation of logical addition modulo 2 on the input data, has two inputs and one output. Often these elements are used in control schemes. The figure shows the symbol of this element.
The image in Western schemes is like that of "OR" with an additional curved strip on the input side, in the domestic one - like "OR", only instead of "1" it will be written "=1".
This logical element is also called "inequivalence". A high voltage level will be at the output only when the signals at the input are not equal (on one unit, on the other zero or on one zero, and on the other one) even if there are two units at the input at the same time, the output will be zero - this is the difference from "OR". These logic elements are widely used in adders.
Sections: Computer science
Currently, there are many tasks on the topic “algebra of logic” in the entrance exams in computer science. The purpose of this lesson is to consolidate the skills of solving USE tasks in computer science using elements of the algebra of logic.
Lesson Objectives:
- Formation of the ability to apply the acquired knowledge in practice;
- Development of the ability to build truth tables according to given formulas;
- Development of the ability to solve text problems using the laws of logic.
Lesson objectives:
- Educational - development of cognitive interest, logical thinking.
- educational- repetition of the basics of mathematical logic, the implementation of practical tasks.
- Educational - development of logical thinking, mindfulness.
During the classes
- Repetition of logical operations and laws.
- Application of logical operations and laws in practice.
- Explanation of homework.
Today we are completing the topic “Fundamentals of Logic” and we will apply the basic logical operations, transformation laws to solve USE tasks in computer science.
The lesson goes along with the presentation.<Приложение1>
1. Repetition of logical operations and laws.
Algebra of logic is a branch of mathematical logic that studies the structure of complex logical statements and ways to establish their truth using algebraic methods.
1. Founder of formal logic?
Aristotle.
2. Founder of the algebra of logic?
George Bull.
3. List the logical operations:
¬ negation (inversion)
&, /\conjunction (“AND”)
V disjunction (“OR”)
logical consequence (implication)
equivalence (equivalence)
4. What is the meaning of the law of double negation?
Double negation excludes negation.
5. Laws of de Morgan (laws of general inversion).
The negation of a disjunction is a conjunction of negations:
¬(A V B) = ¬A /\ ¬B
The negation of a conjunction is a disjunction of negations:
¬(A /\B) = ¬A V ¬B
6. The law of idempotence (sameness).
7. What is the meaning of the law of the exclusion of the third?
Of two contradictory statements about the same thing, one is always true, the second is false, the third is not given:
8. What is the law of contradiction about?
A statement and its negation cannot be true at the same time:
9. The law of exclusion of constants.
For logical addition:
A V 1 = 1 A V 0 = A
For logical multiplication:
A /\ 1 = A A /\ 0 = 0
10. How to express an implication through a disjunction?
A B = ¬A V B
2. Application of logical operations and laws in practice.
Example 1. ( Task A11 demo version 2004)
For which name is the statement true:
¬ (The first letter of the name is a vowel -> The fourth letter of the name is a consonant)?
Decision. A compound sentence is made up of two simple sentences:
A - the first letter of the name is a vowel,
B is the fourth letter of the consonant name.
¬ (A B) = ¬ (¬A V B) = (¬ (¬A) /\ ¬B) = A /\ ¬B
Applicable formulas:
1. Implication through disjunction A? V = ¬A V V
2. De Morgan's law ¬(A V B) = ¬A /\ ¬B
3. Law of double negation.
(The first letter of the name is a vowel /\ The fourth letter of the name is a vowel)
Example 2. ( Task A12 demo 2004)
What logical expression is equivalent to the expression ¬ (A \/ ¬B)?
Decision. ¬ (A \/ ¬B)= ¬ A \/ ¬ (¬B)= ¬ A \/ B
Create a truth table for the formula
¬ (B /\C) V (A/\C B)
The order of execution of logical operations:
¬ (B /\C) V (A/\C B)
Make a truth table.
How many rows will your table have? 3 variables: A, B, C; 2 3 =8
How many columns? 5 operations + 3 variables = 8
| A | B | C | (B/\C) | ¬(B/\C) | A/\C | (A/\C ? B) | ¬ (B/\C) V (A/\Cb) |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
What are the answers in the last column?
identically true, if it takes the values 1 on all collections of simple propositions included in it. The identically true formulas are called tautologies.
Let's solve this example analytically:
simplifying the expression
¬ (B /\ C) V (A/\C B)= (use the implication formula)
¬ (B /\ C) V ¬ (A / \ C) V B = (we apply 1 and 2 de Morgan's laws)
(¬B V ¬C) V (¬A V ¬C) V B = (remove brackets)
¬B V ¬C V ¬A V ¬C V B= (we apply the displacement law)
¬B V B V ¬C V ¬C V ¬A = (law of elimination of the middle, law of idempotence)
1 V ¬C V ¬A = 1 V ¬A = 1 (constant exclusion law)
Answer: 1 , means that the formula is identically true or a tautology.
The boolean expression is called identically false, if it takes the values 0 on all collections of simple propositions included in it.
(task 3 homework)
The table shows queries to the search server. Arrange the query designations in ascending order of the number of pages that the search engine will find for each query.
The symbol I is used to indicate the logical operation “OR” in the query, and the symbol & is used for the logical operation “AND”.
The first way is based on reasoning. Logically, we see that most of the pages will be found for the query D, since when it is executed, pages with the word “laws”, and pages with the word “physics”, and pages with the word “biology” will be found. The fewest pages will be found for query B, since it contains all four words on the searched page. It remains to compare queries A and B. By query B, all pages corresponding to query A will be found (since the latter must contain the word “laws”), as well as pages containing the words “physics” and “biology” at the same time. Therefore, query B will find more pages than query A. So, ordering the queries in ascending order of pages, we get VABG.
Answer: WABG.
The second method involves the use of a graphical representation of operations on sets. (See presentation)
Example 5. ( Task A16 demo 2006)
Below in tabular form is a fragment of the database on the results of testing students (a hundred-point scale is used)
| Surname | Floor | Mathematics | Russian language | Chemistry | Computer science | Biology |
| Aganyan | and | 82 | 56 | 46 | 32 | 70 |
| Voronin | m | 43 | 62 | 45 | 74 | 23 |
| Grigorchuk | m | 54 | 74 | 68 | 75 | 83 |
| Rodnina | and | 71 | 63 | 56 | 82 | 79 |
| Sergeenko | and | 33 | 25 | 74 | 38 | 46 |
| Cherepanov | and | 18 | 92 | 83 | 28 | 61 |
How many records in this fragment satisfy the condition
“Gender=’m’ OR Chemistry>Biology”?
We select records: Boys (two) and Chemistry> Biology (three, but one boy, has already taken 1 time). As a result, 4 records satisfy the condition.
Task 6. ( Task B4 demo version 2007)
In the school table tennis championship, the top four included girls: Natasha, Masha, Luda and Rita. The most ardent fans expressed their guesses about the distribution of places in future competitions.
One believes that Natasha will be the first, and Masha will be the second.
Another fan will put Luda in second place, and Rita, in his opinion, will take fourth place.
The third tennis fan did not agree with them. He believes that Rita will take third place, and Natasha will be second.
What place did Natasha, Masha, Luda, Rita take in the championship?
(In your answer, list in a row without spaces the numbers corresponding to the places of the girls in the given order of names.)
Let's denote the statements:
Н1 = “Natasha will be the first”;
M2 = “the second will be Masha”;
L2 = “the second will be Luda”;
P4 = “the fourth will be Rita”;
P3 = “the third will be Rita”;
Н2 = “the second will be Natasha”.
According to the condition:
it follows from the statements of 1 fan that H1VM2 is true;
it follows from the fan's statements2 that R2VP4 is true;
it follows from the statements of fan 3 that P3VH2 is true.
Therefore, the conjunction is also true
(H1VM2) /\ (L2VP4) /\ (P3VH2) = 1.
Opening the brackets we get:
(N1VM2) /\ (L2VP4) /\ (P3VN2) = (N1/\L2V H1/\P4 V M2/\L2 V M2/\P4) /\ (P3VN2)=
H1/\ L2/\P3 V H1/\P4/\P3 V M2/\L2/\P3 V M2/\P4/\P3 V H1/\L2/\H2 V H1/\P4/\H2 V M2/ \L2/\H2 V M2/\P4/\H2 =H1/\ L2/\P3 V 0 V 0 V 0 V 0 V 0 V 0 V= H1/\ L2/\P3
Natasha-1, Luda-2, Rita-3, and Masha-4.
Answer: 1423
3. Explanation of homework.
Exercise 1. ( Task B8 demo version 2007)
The table shows queries to the search server. Arrange the query designations in ascending order of the number of pages that the search engine will find for each query.
To denote the logical operation "OR" in the query, the symbol | is used, and for the logical operation "AND" - &.
Task 2 ( Task B4 demo version 2008)
Before the start of the Tournament of Four, fans made the following assumptions about their idols:
A) Max wins, Bill second;
B) Bill is the third. Nick is the first;
C) Max is the last and the first is John.
When the competition ended, it turned out that each of the fans was right in only one of their predictions.
What place did John, Nick, Bill, Max take in the tournament?
(In your answer, list in a row without spaces the places of the participants in the specified order of names.)
Conjunction or logical multiplication (in set theory, this is an intersection)
A conjunction is a complex logical expression that is true if and only if both simple expressions are true. Such a situation is possible only in a single case, in all other cases the conjunction is false.
Designation: &, $\wedge$, $\cdot$.
Truth table for conjunction
Picture 1.
Conjunction properties:
- If at least one of the subexpressions of the conjunction is false on some set of variable values, then the entire conjunction will be false for this set of values.
- If all conjunction expressions are true on some set of variable values, then the entire conjunction will also be true.
- The value of the entire conjunction of a complex expression does not depend on the order of the subexpressions to which it is applied (as in mathematics, multiplication).
Disjunction or logical addition (in set theory, this is a union)
A disjunction is a complex logical expression that is almost always true, except when all expressions are false.
Designation: +, $\vee$.
Truth table for disjunction
Figure 2.
Disjunction properties:
- If at least one of the disjunction subexpressions is true on some set of variable values, then the entire disjunction takes a true value for this set subexpressions.
- If all expressions from some disjunction list are false on some set of variable values, then the entire disjunction of these expressions is also false.
- The value of the entire disjunction does not depend on the order of subexpressions (as in mathematics - addition).
Negation, logical negation, or inversion (in set theory, this is negation)
Negation - means that the particle NOT or the word INCORRECT is added to the original logical expression, WHICH and as a result we get that if the original expression is true, then the negation of the original one will be false and vice versa, if the original expression is false, then its negation will be true.
Notation: not $A$, $\bar(A)$, $¬A$.
Truth table for inversion
Figure 3
Negative properties:
The "double negation" of $¬¬A$ is a consequence of the proposition $A$, that is, it is a tautology in formal logic and is equal to the value itself in Boolean logic.
Implication or logical consequence
An implication is a complex logical expression that is true in all cases except when true implies false. That is, this logical operation connects two simple logical expressions, of which the first is the condition ($A$), and the second ($A$) is the consequence of the condition ($A$).
Notation: $\to$, $\Rightarrow$.
Truth table for implication
Figure 4
Implication properties:
- $A \to B = ¬A \vee B$.
- The implication $A \to B$ is false if $A=1$ and $B=0$.
- If $A=0$, then the implication $A \to B$ is true for any value of $B$, (true can follow from false).
Equivalence or logical equivalence
Equivalence is a complex logical expression that is true on equal values of variables $A$ and $B$.
Designations: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.
Truth table for equivalence
Figure 5
Equivalence properties:
- The equivalence is true on equal sets of values of the variables $A$ and $B$.
- CNF $A \equiv B = (\bar(A) \vee B) \cdot (A \cdot \bar(B))$
- DNF $A \equiv B = \bar(A) \cdot \bar(B) \vee A \cdot B$
Strict disjunction or addition modulo 2 (in set theory, this is the union of two sets without their intersection)
A strict disjunction is true if the values of the arguments are not equal.
For electronics, this means that the implementation of circuits is possible using one typical element (although this is an expensive element).
Order of execution of logical operations in a complex logical expression
- Inversion(negation);
- Conjunction (logical multiplication);
- Disjunction and strict disjunction (logical addition);
- Implication (consequence);
- Equivalence (identity).
In order to change the specified order of execution of logical operations, you must use parentheses.
General properties
For a set of $n$ booleans, there are exactly $2^n$ distinct values. The truth table for a boolean expression in $n$ variables contains $n+1$ columns and $2^n$ rows.
PROPERTIES OF LOGICAL OPERATIONS
1. Notation
1.1. Notation for logical connectives (operations):
a) negation(inversion, logical NOT) is denoted by ¬ (for example, ¬A);
b) conjunction(logical multiplication, logical AND) is denoted by /\
(for example, A /\ B) or & (for example, A & B);
c) disjunction(logical addition, logical OR) is denoted by \/
(for example, A \/ B);
d) following(implication) is denoted by → (for example, A → B);
e) identity denoted by ≡ (for example, A ≡ B). The expression A ≡ B is true if and only if the values of A and B are the same (either they are both true or they are both false);
f) symbol 1 is used to denote truth (true statement); symbol 0 - to denote a lie (false statement).
1.2. Two boolean expressions containing variables are called equivalent (equivalent) if the values of these expressions are the same for any values of the variables. So, the expressions A → B and (¬A) \/ B are equivalent, but A /\ B and A \/ B are not (the meanings of the expressions are different, for example, when A \u003d 1, B \u003d 0).
1.3. Priorities of logical operations: inversion (negation), conjunction (logical multiplication), disjunction (logical addition), implication (following), identity. Thus, ¬A \/ B \/ C \/ D means the same as
((¬A) \/ B)\/ (C \/ D).
It is possible to write A \/ B \/ C instead of (A \/ B) \/ C. The same applies to the conjunction: it is possible to write A / \ B / \ C instead of (A / \ B) / \ C.
2. Properties
The list below is NOT meant to be exhaustive, but is hopefully representative.
2.1. General properties
- For a set of n boolean variables exist exactly 2 n different values. Truth table for boolean expression from n variables contains n+1 column and 2 n lines.
2.2 Disjunction
- If at least one of the subexpressions to which the disjunction is applied is true on some set of variable values, then the entire disjunction is true for this set of values.
- If all expressions from some list are true on some set of variable values, then the disjunction of these expressions is also true.
- If all expressions from some list are false on some set of variable values, then the disjunction of these expressions is also false.
- The value of a disjunction does not depend on the order of the subexpressions to which it is applied.
2.3. Conjunction
- If at least one of the subexpressions to which the conjunction is applied is false on some set of variable values, then the entire conjunction is false for that set of values.
- If all expressions from some list are true on some set of variable values, then the conjunction of these expressions is also true.
- If all expressions from some list are false on some set of variable values, then the conjunction of these expressions is also false.
- The meaning of a conjunction does not depend on the order of subexpressions to which it is applied.
2.4. Simple disjunctions and conjunctions
We call (for convenience) the conjunction simple if the subexpressions to which the conjunction is applied are distinct variables or their negations. Similarly, the disjunction is called simple if the subexpressions to which the disjunction is applied are distinct variables or their negations.
- A simple conjunction evaluates to 1 (true) on exactly one set of variable values.
- A simple disjunction evaluates to 0 (false) on exactly one set of variable values.
2.5. implication
- implication A →B is tantamount to disjunction (¬ A) \/ B. This disjunction can also be written as: A\/B.
- implication A →B takes the value 0 (false) only if A=1 and B=0. If A=0, then the implication A →B true for any value b.
For quick search information on the Internet use search queries. The search query is a set keywords, connected by signs of logical operations AND, OR, NOT.
The priority of operations, if there are no specially placed brackets, is as follows: first NOT, then AND, then OR.
You need to understand that the AND operation (simultaneous fulfillment of conditions) reduces the volume of the result, and the OR operation (fulfillment of at least one of the conditions), on the contrary, increases the volume.
If the query contains a phrase in quotation marks, the system will search for exactly that phrase in its entirety.
1. Arrangement of queries in ascending (descending) order
The AND operation (&) denotes the simultaneous presence of keywords in the searched documents, and therefore reduces the amount of information found. The more keywords are connected with the AND operation, the less information is found. Conversely, the "OR" (|) operation indicates the presence of at least one keyword in the searched documents, and therefore increases the amount of information found.
Example 1
The table shows queries to the search server. Arrange the query designations in ascending order of the number of pages that the search engine will find for each query.
A) abstract | mathematics | Gauss
B) abstract | mathematics | Gauss | method
B) abstract | mathematics
D) abstract & math & Gauss
Decision:
The smallest number of pages will be selected for the query with the most AND operations (query D), the largest number of pages will be selected for the query with the largest number of OR operations (query B). Query A will select more pages than query B, because query A contains more keywords linked by an "OR" operation.
Answer: GVAB
2. Counting pages found by query
This type of problem is usually solved by a system of equations. I will offer a more visual and simple way.
The principle of selecting information on search queries the Euler-Venn diagram (Euler circles) illustrates well. On the diagram, sets are represented by intersecting circles. The AND operation (&) is the intersection of the circles, and the OR operation (|) is the union of the circles.
For example, we denote by circles the sets of Apples, Pears, Bananas. The query Apples & Pears & Bananas will select the intersection (common part) of all three circles:
On request Apples | The pear will be selected by combining two circles:
Example 2
The table shows the queries and the number of pages that the search server found for these queries in a certain segment of the Internet:
How many pages (in thousands) will be found for chess?
Decision:
Let's draw an Euler-Venn diagram. The solution to the problem consists in counting the number of pages corresponding to each area bounded by lines:
The query chess & tennis matches the middle region (1000k pages), while the query tennis matches the entire right circle (5500k pages).
Then the right "cropped circle" is 5500-1000=4500:
Request chess | tennis matches both circles (7770), then the left "clipped circle" is 7770-5500=2270
