How to build logical circuits in computer science. Algorithm for constructing logical circuits. I. Organizational moment

Why is it necessary to be able to build logical circuits?

The fact is that gates are used to make up more complex circuits that allow arithmetic operations and store information. Moreover, a circuit that performs certain functions can be constructed from different combinations and numbers of gates. Therefore, the importance of a formal representation of a logical diagram is extremely great. It is necessary so that the developer has the opportunity to choose the most suitable option for constructing a circuit from gates. The process of developing the general logical circuit of a device (including the computer as a whole) thus becomes hierarchical, and at each subsequent level the logical circuits created at the previous stage are used as “building blocks”.

The algebra of logic has been put into the hands of designers powerful tool development, analysis and improvement of logic circuits. In fact, it is much easier, faster and cheaper to study the properties and prove the correct operation of the circuit using a formula that expresses it than to create a real technical device. This is precisely the meaning of any mathematical modeling.

Logic circuits must be built from the minimum possible number of elements, which in turn ensures greater operating speed and increases the reliability of the device.

Algorithm for constructing logical circuits :

1) Determine the number of logical variables.

2) Determine the number of base logical operations and their order.

3) For each logical operation, draw the corresponding gate.

4) Connect the gates in order of performing logical operations.

Let's get to know them one by one.

Task:

Make a logical diagram for it.

Solution:

1. negation
2. multiplication
3. addition

We build the circuit in the specified order.

Task:

Construct a logical function using it.

Solution:

You can first label on the diagram the intermediate functions obtained at the output of each block, and then connect them with logical operations.

Task:

Determine the value of the function F at the output of the circuit.

Solution:

Answer:

Task:

Construct a truth table for it.

Solution:

Answer:

A convenient way to represent logical expressions is using logic diagrams. Here is how the three main logical operations are depicted in such diagrams:

Figure 6.1 - Schematic representation of logical operations

Example. To evaluate a Boolean expression: 1 or 0 And 1 draw a diagram reflecting the sequence of logical operations. Using the diagram, calculate the value of a logical expression.

This clearly shows that the operation is performed first And, then or. Now, in order from left to right, we will assign the results of the operations to the outgoing arrows:

The result was 1 , i.e. "TRUE".

Example. Given expression: Not (1 And (0 or 1) And 1).

Compute the value of an expression using a logic circuit.

Solution. The logical diagram with the calculation results looks like this:

Implication and equivalence

Implication(conditional statement). In Russian, this logical operation corresponds to conjunctions if..., then; when..., then; as soon as... then etc.

Expression starting after conjunctions if, when, as soon as is called the basis of a conditional statement.

Expression after words then, then, called a consequence. In logical formulas, the operation of implication is denoted by the sign “→”. Implication is a two-site operation; is written like this: A→B.

Equivalence. Language equivalent - conjunctions if and only if; then and only then when... Equivalence is indicated sign"≡" or "↔".

The order of all five logical operations in descending order of precedence is as follows: negation, conjunction, disjunction, implication, equivalence.

Converting Boolean Expressions

A formula has a normal form if it does not contain equivalence, implication, or double negation signs, while negation signs are found only for variables.

Basic formulas for converting logical expressions:

2. (A & B) ≡ A IN.

3. (A B) ≡ A & B.

4. (A → B) ≡A & B.

5. A→B ≡ A B.

6. A ↔ B ≡ (A & B) (A & B) ≡ (A B) & (A B).

7. A & (A B) ≡ A.

8. A A & B ≡ A.

9. A & (A B) ≡ A & B.

10.A A & B ≡ A IN.

11. Laws of commutativity:

A & B ≡ B & A;

A B ≡ B A.

12. Laws of associativity:

(A B) C ≡ A (IN WITH);

(A & B) & C ≡ A & (B & C).

13. Laws of idempotency:

A A ≡ A;

14. Laws of distributivity:

A & (B C) ≡ (A & B) (A&C);

A (B & C) ≡ (A B) & (A WITH).

15. A 1 ≡ 1;

16. A & 1 ≡ A;

17. A A ≡ 1;

18. A & 0 ≡ 0;

19. A & A ≡ 0.

6.3. Laboratory assignment

Assignments are distributed depending on what is given by the teacher mn-code. If m is an odd number, then your option is 1, if it is even, then option 2.

Task 1. Using logical operations, write down statements that are true if the following conditions are met:

Option 1.

1) at least one of the numbers X, Y, Z is positive;

2) only one of the numbers X, Y, Z is not positive.

3) only one of the numbers X, Y, Z is greater than 10

4) none of the numbers X, Y, Z is equal to 104

Option 2.

1) at least one of the numbers X, Y, Z is negative;

2) only one of the numbers X, Y, Z is negative.

3) only one of the numbers X, Y, Z is not more than 10

4) each of the numbers X, Y, Z is 0

Task 2. Determine the value of a Boolean expression Not (X>Z) otherwise (X=Y), if:

Option 1.

1) X=3, Y=5, Z=2;

2) X=5, Y=0, Z=–8.

Option 2.

1) X=9, Y=–9, Z=9;

2) X=0, Y=1, Z=19.

Task 3. Let a, b, c be logical quantities that have the following meanings: a = true, b= lie, c = true. Draw logic diagrams for the following Boolean expressions and evaluate their values:

Option 1.

1) a And b;

2) Not A or b;

3) a or b And With;

4) (a or b) And(c or b).

Option 2.

1) a or b;

2) a And b or With;

3) Not A or b And With;

4) Not(A And b And With).

Task 4. Construct logical circuits using a logical expression:

Option 1. x 1 And (Not x 2 or x 3).

Option 2. x 1 And x 2 or not x 1 And x 3 .

Task 5. Perform logic calculations. Write down the corresponding logical expressions:

Option 1. Option 2.

Task 6. A logical diagram is given. Construct a logical expression corresponding to this circuit.

Calculate the value of the expression for:

Option 1.

1) x 1 =0, x 2 =1;

2) x 1 =1, x 2 =1.

Option 2.

1) x 1 =1, x 2 =0;

2) x 1 =0, x 2 =0.

Task 7. A logical diagram is given. Construct a truth table for this circuit.

Task 8. Determine the truth of the formula:

Option 1. ((a) .

Option 2. .

Task 9. Simplify the expression:

Option 1. .

Option 2. .

6.4. Requirements for the content of the report

1. Purpose of laboratory work.

2. Laboratory assignment. Mn – code.

3. Results of solving problems of your version.

4. Conclusions based on the results obtained.

6.5. Security questions

1. What is a logical statement, constant, variable, formula?

2. What types of logical operations are considered in the laboratory work?

3. Truth tables for implication and equivalence?

4. List the laws of algebra of logic?

Laboratory work №7
"NUMBER SYSTEMS"

7.1. Purpose of the work

Study of number systems. Acquiring skills in transferring from one number system to another

7.2. Guidelines

Expanded form writing a number is called writing in the form:

A q =±(a n-1 q n-1 + a n-2 q n-2 +…+ a 0 q 0 + a –1 q -1 + a -2 q -2 + …+ a -m q - m).

Here A q is the number itself, q is the base of the number system, and i are the digits of this number system, n is the number of digits of the integer part of the number, m is the number of digits of the fractional part of the number.

Example. Get expanded form of decimal numbers 32478; 26,387.

32478 10 = 3*10000 + 2*1000 + 4*100 + 7*10 + 8 = 3*10 4 + 2*10 3 + 4*10 2 + 7*10 1 + 8*10 0 .

26,387 10 = 2*10 1 + 6*10 0 + 3*10 -1 + 8*10 -2 + 7*10 -3 .

Example. Get the expanded form of the numbers 112 3, 101101 2, 15FC 16, 101.11 2

112 3 =1*10 2 + 1*10 1 + 2*10 0 .

1011012 = 1*10 101 + 0*10 100 + 1*10 11 + 1*10 10 + 0*10 1 + 1*10 0 .

15FC 16 = 1*10 3 + 5 *10 2 + F*10 1 + C.

101,11 2 = 1*10 10 + 0*10 1 + 1*10 0 + 1*10 -1 + 1*10 -10 .

If all the terms in the expanded form of a non-decimal number are represented in the decimal system and the resulting expression is calculated according to the rules of decimal arithmetic, then a number in the decimal system equal to the given one will be obtained. This principle is used to convert from the non-decimal system to the decimal system.

Example. Convert all numbers from the previous example to the decimal system.

112 3 =1*3 2 + 1*3 1 + 2*3 0 = 9+3+2 = 14 10 .

101101 2 = 1*2 5 + 0*2 4 + 1*2 3 + 1*2 2 + 0*2 1 + 1*2 0 =32+8+4+1 = 45 10 ,

15FC 16 = 1*16 3 + 5*16 2 + 15*16 1 + 12 = 4096 + 1280 + 240 + 12 = 5628 10.

101,11 2 = 1*2 2 + 0*2 1 + 1*2 0 + 1*2 –1 + 12 -2 = 4 + 1 + 1/2 + 1/4 = 5 + 0,5 + 0,25 = 5,75 10 .

In digital circuitry, a digital signal is a signal that can take on two values, considered as a logical "1" and a logical "0".

Logic circuits can contain up to 100 million inputs, and such gigantic circuits exist. Imagine that the Boolean function (equation) of such a circuit was lost. How to restore it with the least loss of time and without errors? The most productive way is to break the diagram into tiers. With this method it is written output function each element in the previous tier and is substituted for the corresponding input in the next tier. Today we will consider this method of analyzing logical circuits with all its nuances.

Logic circuits are implemented using logical elements: “NOT”, “AND”, “OR”, “NAND”, “NOR”, “XOR” and “Equivalence”. The first three logical elements allow you to implement any, no matter how complex, logical function in a Boolean basis. We will solve problems on logical circuits implemented precisely in a Boolean basis.

Several standards are used to designate logic elements. The most common are American (ANSI), European (DIN), international (IEC) and Russian (GOST). The figure below shows the designations of logical elements in these standards (to enlarge, you can click on the figure with the left mouse button).

In this lesson we will solve problems on logical circuits, in which logical elements are designated in the GOST standard.

Logic circuit problems are of two types: the problem of logical circuit synthesis and the problem of logical circuit analysis. We will start with the second type of task, since in this order we can quickly learn to read logic circuits.

Most often, in connection with the construction of logical circuits, the functions of logic algebra are considered:

• three variables (will be considered in analysis problems and in one synthesis problem);
• four variables (in synthesis problems, that is, in the last two paragraphs).

Let's consider the construction (synthesis) of logical circuits

• in the Boolean basis "AND", "OR", "NOT" (in the penultimate paragraph);
• in the also common bases “AND-NOT” and “OR-NOT” (in the last paragraph).

Logic circuit analysis problem

The task of analysis is to determine the function f, implemented by a given logic circuit. When solving such a problem, it is convenient to adhere to the following sequence of actions.

1. The logical diagram is divided into tiers. Tiers are assigned sequential numbers.
2. The outputs of each logical element are designated by the name of the desired function, equipped with a digital index, where the first digit is the tier number, and the remaining digits are the serial number of the element in the tier.
3. For each element, an analytical expression is written that connects its output function with the input variables. The expression is determined by the logical function implemented by the given logical element.
4. Substitution of some output functions through others is carried out until a Boolean function is obtained, expressed in terms of input variables.

Example 1.

Solution. We divide the logical circuit into tiers, which is already shown in the figure. Let's write down all the functions, starting from the 1st tier:

x, y, z :

Example 2. Find the Boolean function of a logic circuit and construct a truth table for the logic circuit.

Example 3. Find the Boolean function of a logic circuit and construct a truth table for the logic circuit.

We continue to search for the Boolean function of the logic circuit together

Example 4. Find the Boolean function of a logic circuit and construct a truth table for the logic circuit.

Solution. We divide the logical diagram into tiers. Let's write down all the functions starting from the 1st tier:

Now let's write down all the functions, substituting the input variables x, y, z :

As a result, we get the function that the logic circuit implements at the output:

.

Truth table for this logic circuit:

Example 5. Find the Boolean function of a logic circuit and construct a truth table for the logic circuit.

Solution. We divide the logical diagram into tiers. The structure of this logical circuit, unlike previous examples, has 5 tiers, not 4. But one input variable - the lowest one - runs through all the tiers and directly enters the logical element in the first tier. Let's write down all the functions starting from the 1st tier:

Now let's write down all the functions, substituting the input variables x, y, z :

As a result, we get the function that the logic circuit implements at the output:

.

Truth table for this logic circuit:

The problem of synthesizing logic circuits in a Boolean basis

The development of a logical circuit according to its analytical description is called the problem of logical circuit synthesis.

Each disjunction (logical sum) corresponds to an “OR” element, the number of inputs of which is determined by the number of variables in the disjunction. Each conjunction (logical product) corresponds to an “AND” element, the number of inputs of which is determined by the number of variables in the conjunction. Each negation (inversion) corresponds to a “NOT” element.

Logic design often begins with defining the logical function that the logic circuit must implement. In this case, only the truth table of the logic circuit is given. We will analyze just such an example, that is, we will solve a problem that is completely opposite to the problem of analyzing logical circuits discussed above.

Example 6. Construct a logical circuit that implements a function with a given truth table.

Laboratory work No.4 .

Circuit implementation of logical elements. Construction of logical circuits.

Theoretical part.

Computer processing of information is based on the algebra of logic developed by J. Boole. It has been proven that all electronic computer circuits can be implemented using logical 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. no current will pass through it, and the output will be a signal high level(1). If a high-level signal (1) is applied to the input of the circuit, the transistor will “open” and begin to pass electric current. At the output, due to the voltage drop, the voltage will be established low level. 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, the circuit will begin to pass current, and a high level signal (logical “1”) will also be established at the load resistance.

Element I

If low-level signals (logical “0”) are applied to inputs In1 and In2, then both transistors are closed, no current passes through them, and the output voltage at Rn is close to zero. Let a high voltage (“1”) be applied to one of the inputs. Then the corresponding transistor will open, but the other one will remain closed, and no current will pass through the transistors and resistance. Consequently, 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 supplied 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 logical elements, using a truth table or CNF and DNF representation of a logical function, one can 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, you can understand how a logical device works, i.e. answer the question: what function does it perform? An equally important form of describing logical devices is a structural formula. Let us show with an example how a formula is written out according to a given functional diagram (1 diagram). It is clear that the “AND” element performs logical multiplication of the values ​​and B. A negation operation is performed on the result in the “NOT” element, 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

Example: the logical diagram is given:

It is built on the basis of a Boolean expression - Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E

Practical part.

Task 1. For each of the functional diagrams, write down the corresponding structural formula.

2) For CNF and DNF from laboratory work 5, construct functional diagrams.