Construction of logical circuits by logical expression. Determination of the signal at the output of the logic circuit according to the given values of the signals at all inputs of this circuit
4) Answer: l v 0 & l = 1.
Example 2
Build a logical circuit corresponding to a logical expression
F = X & Y v (Y v X).
Calculate the values of the expression for X = 1, Y = 0.
1) There are two variables: X and Y;
2) There are three logical operations: conjunction and two disjunctions: 14 3 2 X & Y v (Y v X).
3) We build the circuit from left to right in accordance with the order of logical operations:
 |
3) Calculate the value of the expression: F = l & 0 v (0 v 1) = 0
Do the exercise
Build a logical circuit corresponding to the logical expression and find the value of the logical expression:
A) F = A v B & C if A = 1, B=1, C=1.
B) F = (A v B & C) if A=0, B=1, C=1.
B) F = A v B & C if A=1, B=0, C=1.
D) F = (A v B) & (C v B), if A=0, B=1, C=0.
E) F = (A & B & C) if A=0, B=0, C=1.
E) F = (A & B & C) v (B & C vA) if A=1, B=1, C=0.
G) F = B & A v B & A if A=0, B=0.
Laws of logic
If a logical expression contains a large number of operations, then it is quite difficult to compile a truth table for it, since you have to sort through a large number of options. In such cases, it is convenient to reduce the formulas to normal form.
A formula has a normal form if it does not contain equivalence signs, implication, double negation, while negation signs are found only with logical variables.
To bring the formula to normal form, the laws of logic and the rules of logical transformations are used.
| A=A | Law of Identity | |
| A&A=0 | Law of contradiction | |
| Av A = l | Law of the exclusive middle | |
| A = A | The law of double negation | |
| A&0 = 0 A v 0 = A | Constant Exclusion Laws | |
| A&1=A A v 1 = 1 | Constant Exclusion Laws | |
| A&A=A A v A=A | Idempotency Rule | |
| AvA=l | ||
| (A→B)=A&B | ||
| A→B = A v B | ||
| A& (Av B)= A | law of absorption | |
| A v (A & B) = A | law of absorption | |
| A& (Av B) = A & B | ||
| AvA&B = A v B | ||
| (AvB) vC =Av(BvC) (A&B)&C = A&(B&C) | Associativity rule | |
| (A&B) v(A&C) = A&(BvC) (AvB)&(AvC) = Av(B&C) | Distributivity rule | |
| AvB = BvA A&B = B&A | Commutativity rule | |
| AóB = A&Bv(A&B) | ||
| (AvB)= A & B | Morgan's laws | |
| (A&B)=AvB | Morgan's laws | |
Example
Simplify Boolean Expression F= ((A v B) → (B v FROM)). This logical expression must be converted to normal form, because it contains the implication and negation of the logical operation.
1. Get rid of the implication and negation. Let's use (8). It turns out: ((AvB)→(BvC))= (AvB)&(BvC).
2. Apply the law of double negation (4). We get: (AvB)&(BvC)= (AvB)&(BvC)
3. Apply the distributivity rule (15). We get:
(AvB)&(BvC)= (AvB)&Bv(AvB)&C.
4. Let us apply the law of commutativity (17) and distributivity (15). We get: (AvB)&Bv(AvB)&C = A&BvB&BvA&CvB&C.
5. Apply (16) and get: A&BvB&BvA&CvB&C=A&BvBvA&CvВ&С
6. Let's apply (15), i.e. we take B out of brackets. We get:
A&BvBv A&Cv B&C=B&(Av1)v A&Cv B&C
7. Let's apply (6). We get: B &(Avl)v A&Cv B &C = Bv A&Cv B &C.
8. Rearrange the terms, group and take B out of brackets. We get:
BvA&CvB&C = B&(1vC)vA&C.
9. Apply (6) and get the answer:
Answer: F = ((A v B) → (B v C)) = B v A & C.
Simplify the expression:
1) F = (A & B)v(B v C).
2) F = (A→B) v (B→A).
3) F = A & C vA & C.
4) F = A v B v C v A v B v C.
5) F = (X & Y v(X & Y)).
6) F= X &(Y v X).
7) F = (X v Z) & (X v Z) & (Y v Z).
10) F= B&C& (AvA).
11) F=A&B&CvAvB
12) F= (AvB)&(BvA)& (CvB)
Simplify the expression:
1.F= A&C vA&C.
2. F= A ↔ B v A&C
3.F=A&(B↔C)
4. F = (X v Y) & (Y ↔ X).
5.F= A v B v C v A v B v C.
6. F=(AvB) → (AvC)
7. F= A ↔ (B v C)
8. F = A & B → C & D.
9.F=(X & Y v(X & Y)).
10. F = (X v Y) & (Y v X).
11.F= A ↔ B&C
12. F = (A v B) & (B v A → B).
13.F= X &(Y v X).
14. F= A → B v A&C
15. F = X & Y v X.
16. F = ((X v Y) & (Z → X)) & (Z v Y).
17.F=(X v Z) & (X v Z) & (Y v Z).
18. F= A → (B v C)
19. F= A ↔ B v C
20. F = ((X v Y) & (Z v X)) & (Z → Y).
21. F= (B&(A→C))
22. F= A → B v A&C
23. F= A ↔ (B v C)
24. F = ((X v Y) & (Z v X)) & (Z v Y).
25.F=(A→B) v (B→A).
26.F=A&B&C&D.
27. F \u003d A ↔ (B v C)
28. F=A& (B→C).
29.F= A&(AvB)
30. F= A ↔ (B v C)
31. F= A → B v A &C
32. F = (A v B) & (B v A v B).
33.F= B&C& (AvA).
34. F= A&B v A&C
35. F = X & Y ↔ X.
36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).
37.F= A&B&CvAvB
38. F = (X → Y) & (Y v X).
39.F= A → B&C
40. F = (A ↔ B) & (B v A & B).
41.F=(AvB)&(BvA)& (CvB) .
42. F= A&B v A&C
43. F=A& (BvC)
44. F = (X → Y) & (Y ↔ X).
45.F= Av(A&B)
46. F = A & B ↔ C & D.
47. F \u003d A ↔ (B v C)
48. F=(X & Y) v (Y & X).
Sections: Informatics
Goals:
1. Educational
- Main logical operations.
- Construction of truth tables for complex statements.
- Logic circuits and logical expressions.
2. Educational
- Development of research and cognitive activities.
- Concisely, fully and meaningfully answer and draw generalizing conclusions.
3. Educational
- Formation of accuracy when working with a computer.
- Understanding the connections between other students, the culture of behavior.
Lesson type: combined
Methods of organizing educational activities:
- frontal
- individual
- student-computer
Software and didactic support: PC, presentation, practice assignment, handout, Electronics Workbench (EWB512), PowerPoint.
DURING THE CLASSES
I. Organizational moment.
II. Updating previously studied material and checking homework.
Assignments to be done in notebooks and at the blackboard.
No. 1. Create truth tables for the following logical expressions:
Number 3. Draw on the board the logical elements AND, OR, NOT, AND-NOT, OR-NOT.
III. New material.
Scientists and engineers have been thinking about the possibilities of using logic in technology for a long time. For example, the Dutch physicist Paul Ehrenfest (1880 - 1933), back in 1910, wrote: "... Let there be a draft wire diagram for an automatic telephone exchange. It is necessary to determine:
1) whether it will function correctly in any combination that may occur during the operation of the plant;
2) whether it contains unnecessary complications.
Each such combination is a premise, each small commutator is a logical "either-or" embodied in ebonite and brass; all together - a system of purely qualitative ... "premises" that leaves nothing to be desired in terms of complexity and intricacies ... is it true that, despite the existence of an algebra of logic, a kind of "algebra of distributive schemes" should be considered a utopia?
Created later by M.A. Gavrilov (1903 - 1979), the theory of relay-contact circuits showed that this is not a utopia at all.
Let's look at the microchip. At first glance, we do not see anything that would surprise us!
But when viewed at high magnification, it will amaze us with its slender architecture. To understand how it works, let's remember that the computer runs on electricity, that is, any information is presented in the computer in the form of electrical impulses.
Why is it necessary to be able to build logical circuits?
The fact is that gates make up more complex circuits that allow you to perform arithmetic operations and store information. Moreover, a circuit that performs certain functions can be built from valves that are different in combination and number. Therefore, the value of the formal representation of the logical circuit is extremely high. It is necessary for the developer to be able to choose the most suitable option for constructing a circuit from gates. The process of developing a general logical scheme of a device (including a computer as a whole) becomes hierarchical, and at each next level, logical schemes created at the previous stage are used as "bricks".
The algebra of logic gave designers a powerful tool for developing, analyzing and improving logic circuits. Indeed, it is much easier, faster and cheaper to study the properties and prove the correct operation of the circuit using a formula expressing it than to create a real technical device. This is the essence of any mathematical modeling.
Logic circuits must be built from the minimum possible number of elements, which in turn ensures greater speed and increases the reliability of the device.
The rule for constructing logic circuits:
1) Determine the number of boolean variables.
2) Determine the number of basic logical operations and their order.
3) For each logical operation, draw the corresponding gate and connect the gates in the order in which the logical operations are performed.
Consideration of two examples of transition from expression to schema. (Presentation)
Consideration of two examples of the transition from schema to expression. (Presentation)
More often in life, a situation arises when the result is known and for its implementation it is necessary to build a device.
Consider the following problem: (Presentation)
Task 1. In a two-story house, the staircase is illuminated by one lamp X. On the first floor there is one switch A, on the second floor - switch B. If A is turned on, the lamp lights up. When raised to the second floor and turned on, the lamp goes out. If someone goes out and presses B, then the lamp turns on, when going down to the first floor and pressing A, the lamp should go out.
Solution algorithm:
- Make a truth table.
- Define a boolean function.
- Build a logic diagram.
| A | B | X |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
To create a logical function on the truth table, you need to write down the values of the output variable.
Between the rows of the table there will be a logical addition sign, and between the columns - a logical multiplication sign 
.
IV. Consolidation of the studied material.
Work at the blackboard and in notebooks on cards.
No. 1. According to the logical expression, construct a logical circuit:
No. 2. According to the logical scheme, make a logical expression:
V. Computer workshop.
Practical work using the Electronics Workbench (EWB512).
Option 1
1. Simplify the boolean expression
2. Check your work using the Electronics Workbench program:
Write the original expression to Logic Converter;
- Make a truth table 
- Simplify the expression using 
- Build a simplified logic circuit 
.
3. Check the correctness of the simplifications made.
VI. Homework:
a) simplify the logical expression, build a logical circuit and a truth table 
b) according to the truth table (00001011), make an expression, simplify it, draw a diagram.
Lab No.4 .
Circuit implementation of logic elements. Construction of logical circuits.
Theoretical part.
The computer processing of information is based on the algebra of logic developed by J. Boole. It was proved that all electronic circuits of a computer can be implemented using logic elements AND, OR, NOT.
Element NOT
When a low level signal (0) is applied to the input of the circuit, the transistor will be locked, i.e. current will not pass through it, and the output will be a signal high level(one). If a high-level signal (1) is applied to the input of the circuit, then the transistor will “open” and begin to pass electric current. At the output, due to the voltage drop, a low level voltage will be established. Thus, the circuit converts signals from one level to another, performing a logical function.
OR element
The “OR” function is a logical addition (disjunction), its result is 1 if at least 1 of the arguments is 1. Here, the transistors are connected in parallel to each other. If both are closed, then their total resistance is high and the output will be a low level signal (logical “0”). It is enough to apply a high level signal (“1”) to one of the transistors, as the circuit begins to pass current, and a high level signal (logical “1”) is also set on the load resistance.
Element AND
If low-level signals (logical “0”) are applied to the inputs Vx1 and Vx2, then both transistors are closed, the current does not pass through them, the output voltage at R n is close to zero. Let one of the inputs be fed high voltage("one"). Then the corresponding transistor will open, but the other one will remain closed, and no current will flow through the transistors and resistance. Therefore, when a high level voltage is applied to only one of the transistors, the circuit does not switch and a low level voltage remains at the output. And only when high-level signals (“1”) are simultaneously applied to the inputs, we will also receive a high-level signal at the output.
Thus, each basic logical function - "AND", "OR", "NOT" - corresponds to a specially designed circuit called a logical element. By combining signals denoting logical variables and outputs corresponding to logical functions using logic elements, using a truth table or CNF and DNF representation of a logical function, it is possible to compose a structural or functional diagram(see examples below), which is the basis for the hardware implementation of the circuit.
By analyzing the functional diagram, one can understand how the logical device works, i.e. answer the question: what function does it perform. An equally important form of describing logical devices is the structural formula. We will show by example how a formula is written out according to a given functional diagram (1 diagram). It is clear that the “AND” element performs the logical multiplication of values and B. The result in the “NOT” element is negated, i.e. the value of the expression is calculated: The formula is the structural formula of the logical device.
So, the main logical functions are denoted
|
Inversion |
|
|
Conjunction |
|
|
Disjunction |
|
Example: given the logic diagram:
|
|
|
It is built on the basis of a Boolean expression - Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E
Practical part.
Exercise 1. For each of the functional schemes, write out the corresponding structural formula.
2) For CNF and DNF from laboratory work 5, construct functional diagrams.
Service assignment. The online calculator is designed for constructing a truth table for a logical expression.Truth table - a table containing all possible combinations of input variables and their corresponding output values.
The truth table contains 2n rows, where n is the number of input variables, and n+m are columns, where m are the output variables.
Instruction. When entering from the keyboard, use the following conventions: For example, the logical expression abc+ab~c+a~bc should be entered like this: a*b*c+a*b=c+a=b*c
To enter data in the form of a logical diagram, use this service.
Logic function input rules
- Use the + sign instead of v (disjunction, OR).
- Before the logical function, you do not need to specify the function designation. For example, instead of F(x,y)=(x|y)=(x^y) you would simply type (x|y)=(x^y) .
- The maximum number of variables is 10 .
The design and analysis of computer logic circuits is carried out with the help of a special section of mathematics - the algebra of logic. In the algebra of logic, three main logical functions can be distinguished: "NOT" (negation), "AND" (conjunction), "OR" (disjunction).
To create any logical device, it is necessary to determine the dependence of each of the output variables on the current input variables, such a dependence is called a switching function or a function of the logic algebra.
A logic algebra function is called fully defined if all 2 n of its values are given, where n is the number of output variables.
If not all values are defined, the function is called partially defined.
A device is called logical if its state is described using a function of the algebra of logic.
The following methods are used to represent the logic algebra function:
- a verbal description is a form that is used at the initial design stage and has a conditional representation.
- description of the function of the algebra of logic in the form of a truth table.
- description of the function of the algebra of logic in the form of an algebraic expression: two algebraic forms of FAL are used:
a) DNF - disjunctive normal form is the logical sum of elementary logical products. DNF is obtained from the truth table according to the following algorithm or rule:
1) those rows of variables for which the output function =1 are selected in the table.
2) for each row of variables, a logical product is written; and the variables =0 are written with inversion.
3) the resulting product is logically summarized.
Fdnf = X 1 * X 2 * X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
A DNF is said to be perfect if all variables have the same rank or order, i.e. each work must necessarily include all variables in direct or inverse form.
b) CNF - conjunctive normal form is the logical product of elementary logical sums.
CNF can be obtained from the truth table using the following algorithm:
1) select sets of variables for which the output function = 0
2) for each set of variables we write down an elementary logical sum, and the variables =1 are written with inversion.
3) the resulting amounts are logically multiplied.
Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
CNF is called perfect if all variables have the same rank.
Figure 1 - Diagram of a logical device
All operations of the algebra of logic are defined truth tables values. The truth table determines the result of performing an operation for all possible x logical values of the original statements. The number of options that reflect the result of applying the operations will depend on the number of statements in the logical expression. If the number of statements in the logical expression is N, then the truth table will contain 2 N rows, since there are 2 N different combinations of possible argument values.
Operation NOT - logical negation (inversion)
The logical operation is NOT applied to a single argument, which can be either a simple or a complex logical expression. The result of the operation is NOT the following:- if the original expression is true, then the result of its negation will be false;
- if the original expression is false, then the result of its negation will be true.
not A, Ā, not A, ¬A, !A
The result of the negation operation is NOT determined following table truth:
| A | not A |
| 0 | 1 |
| 1 | 0 |
The result of the negation operation is true when the original statement is false, and vice versa.
Operation OR - logical addition (disjunction, union)
The logical OR operation performs the function of combining two statements, which can be either a simple or a complex logical expression. Statements that are initial for a logical operation are called arguments. The result of the OR operation is an expression that will be true if and only if at least one of the original expressions is true.Designations used: A or B, A V B, A or B, A||B.
The result of the OR operation is determined by the following truth table:
The result of the OR operation is true when A is true, or B is true, or both A and B are true, and false when both A and B are false.
Operation AND - logical multiplication (conjunction)
The logical operation AND performs the function of the intersection of two statements (arguments), which can be either a simple or a complex logical expression. The result of the AND operation is an expression that is true if and only if both of the original expressions are true.Symbols used: A and B, A Λ B, A & B, A and B.
The result of the AND operation is determined by the following truth table:
| A | B | A and B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The result of operation AND is true if and only if statements A and B are both true, and false in all other cases.
Operation "IF-THEN" - logical consequence (implication)
This operation connects two simple logical expressions, of which the first is a condition, and the second is a consequence of this condition.Applied designations:
if A, then B; A attracts B; if A then B; A → B.
Truth table:
| A | B | A→B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The result of the operation of consequence (implication) is false only when premise A is true and conclusion B (consequence) is false.
Operation "A if and only if B" (equivalence, equivalence)
Applicable designation: A ↔ B, A ~ B.Truth table:
| A | B | A↔B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Modulo 2 addition operation (XOR, exclusive or, strict disjunction)
Notation used: A XOR B, A ⊕ B.Truth table:
| A | B | A⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The result of an equivalence operation is true only if both A and B are both true or both false.
Precedence of logical operations
- Actions in brackets
- Inversion
- Conjunction (&)
- Disjunction (V), Exclusive OR (XOR), modulo 2 sum
- Implication (→)
- Equivalence (↔)
Perfect disjunctive normal form
Perfect disjunctive normal form of a formula(SDNF) is a formula equivalent to it, which is a disjunction of elementary conjunctions, which has the following properties:- Each logical term of the formula contains all the variables included in the function F(x 1 ,x 2 ,...x n).
- All logical terms of the formula are different.
- No logical term contains a variable and its negation.
- No logical term in a formula contains the same variable twice.
For each function, SDNF and SKNF are uniquely defined up to a permutation.
Perfect conjunctive normal form
Perfect conjunctive normal form of a formula (SKNF) is a formula equivalent to it, which is a conjunction of elementary disjunctions that satisfies the following properties:- All elementary disjunctions contain all variables included in the function F(x 1 ,x 2 ,...x n).
- All elementary disjunctions are different.
- Each elementary disjunction contains a variable once.
- No elementary disjunction contains a variable and its negation.
Let's get to know them one by one.
Construction of a logical circuit according to a given logical function.
A task:
Given a logical function:Make a logic diagram for it.
Solution:
Let's arrange the order of execution of logical operations, guided by the rules:- negation
- multiplication
- addition
We get:
We build the scheme in the specified order.
Recording a logical function according to a given logic circuit.
A task:
Given a logic diagram:
Write a logic function based on it.
Solution:
We consider the circuit from the end and write the corresponding logical operations, given that the function being written has three operands A, B, CYou can first sign on the circuit intermediate functions obtained at the output of each block, and then chain them with logical operations.
Determination of the signal at the output of the logic circuit according to the given values of the signals at all inputs of this circuit.
A task:
The logic diagram and signal values at all inputs are given:
Determine the value of the function F at the output of the circuit.
Solution:
Using the truth tables for the corresponding logical elements of the circuit, we arrange the values of the signals at the outputs and, accordingly, at the inputs of each logical element, until we get to the end of the circuit. We get:
Answer:
The value of the function F at the output of the circuit = 1.Building a truth table for a given logic circuit.
A task:
Given a logic diagram:
Build a truth table for it.
Solution:
Check the number of inputs on the diagram. The number of combinations of signals at 2 inputs is 4, for 3 inputs it is 8, for 4 inputs it is 16, etc. circuit element, and lines - reflect different combinations of signals at the inputs. The number of lines is the same as the number of signal combinations. Using the truth tables for the corresponding logical elements of the circuit, we place the values of the signals at the outputs of each logical element, that is, for each column until we get to the end of the circuit. We get:Answer:
