Logical operations. Disjunction, conjunction and negation

Logical addition (disjunction) is formed by combining two statements into one using the conjunction “or”.

In Russian, the conjunction “or” is used in a double sense.

For example, V proposal Usually at 8 pm I watch TV or drink tea the conjunction “or” is taken in a non-exclusive (unifying) sense, since you can only watch TV or only drink tea, but you can also drink tea and watch TV at the same time, because your mother is not strict. This operation is called non-strict disjunction.(If my mother were strict, she would only allow me to either watch TV or only drink tea, but not combine eating with watching TV.)

In a statement This verb has I or II conjugation conjunction "or"
used exclusively (dividing) sense. Such an operation
called strict disjunction.. ,. ,-> „,... > (, r>

Examples of strict and non-strict disjunctions:

Statement	Type of disjunction
Petya sits on the western or eastern stands of the stadium	Strict
A student rides a train or reads a book	Lax
Olya likes to write essays or solve logic problems	Lax
Seryozha is studying at school or graduated from it	Strict
Tomorrow it will rain or it won’t (there is no third option)	Strict
Let's fight for purity. Cleanliness is achieved in this way: either do not litter, or clean often	Lax
Zelia moves in a circular or elliptical orbit	Strict
Numbers can be added or multiplied	Lax
Children are either well-mannered or not ours	?

Notation for a weak disjunction:A OR IN; AORIN; A| IN; A V IN; A + B.(In this tutorial: A V IN.)

Let us give an example of a disjunction of two simple statements.

Let's say from your window you can see a parking lot, where there are usually two cars: a Mercedes and a Zhiguli, but there may be one of them or there may be none.

Let us denote the statements:

A = There is a Mercedes in the parking lot. IN= There are Zhiguli cars in the parking lot.

(A disjunction B) = It’s in the parking lot "Mercedes" or "Zhiguli".

Chapter 3. Logical operations ____________ [___________________________ SCH

Table., ^"-"n..;h; i■.■;- >i ,;,

From the truth table it follows that a disjunction of two statements is false if and only if both statements are false, and true when at least one statement is true. Sometimes this property is taken as the definition of the disjunction operation.

Mnemonic rule: disjunction is logical addition, and we have no doubt that you noticed that the equalities 0 + 0 = 0; 0+1 = 1;1+0=1, true for ordinary addition, are also true for the disjunction operation, but 1 V 1 = 1.

The word “conjunction” has one letter “and”, and the word “disjunction” has two letters “and”, as And in the word "or".

V L-The symbol V (disjunction) is formed from the first letter of the Latin word Vel (“or”).

“Dis” - “tick down” - V.

In set theory, disjunction corresponds to the operation associations sets.

To construct the Euler-Venn diagram corresponding to the union of sets, we select those rows of the truth table in which AvB=\. There are three of them. On the diagram we shade three areas in which the values AAndIN the same as in the selected lines. ^ _ h."" " * "o L su J I J

30 ___________________________ Part 1. Elements of mathematical logic

Graphic illustration: ».*■.

A IN A\jB- many students in the class who are excellent students or athletes.

j Consider the operation strict disjunctions (exclusive “or”). i Let us give an example of a strict disjunction.

,)■ Let the following statements be given:

"■ A= There is a Mercedes in the parking lot.

>; B = There are Zhiguli cars in the parking lot.

i (A strict disjunction B) = In the parking lot stands “Mvrsedve”*or

"Zhiguli". v ?;;

The use of the “exclusive “or” operation implies that there can be either only a Mercedes or only a Zhiguli in the parking lot, and prohibits the situation when a Mercedes and a Zhiguli are in the parking lot at the same time.

; . - "4",

Strict disjunction notation:A XOR IN; A v IN.

chapter 3. Logical operations ______________________________________ 31

From the truth table it follows that the operation of strict disjunction is true if and only if only one of the statements is true, and false when both statements are true or both are false. Sometimes this property is taken to be the definition of the strict disjunction operation.

An Euler-Venn diagram depicting a strict disjunction is constructed using a truth table in the same way as for other logical operations.

Graphic illustration:

<ЗЭ

A- many excellent students in the class; IN- many athletes in the class;

A at B- many students in the class who are either excellent students or athletes.

d "W.C. J

Logical consequence (implication) -wr™

Logical consequence (implication) is formed by connecting two!,

statements into one using the figure of speech “if..., That ... ». ■

Examples of implications: "

E = If an oath is given, then it must be fulfilled.{

P = If a number is divisible by 9, then it is divisible by 3. I

In logic it is permissible (accepted, agreed) to consider also non-.;:

statements that make sense from an everyday point of view. i

Let us give examples of judgments that are not only legitimately considered; rive in logic, but which also have the meaning “true”:

WITH= If cows fly, then 2 + 2 = 5. X = If- Napoleon, then a cat has four legs.

Implication designation:A -> B; A=e IN.(In this tutorial: A=» IN.) They say: if A, That IN; A implies IN; A entails IN; IN follows from A.

Part 1. Elements of mathematical logic

Chapter 3. Logical operations f; L._________________________ 33

This operation is not as obvious as the previous ones. It can be explained, for example, as follows.

Let the following statements be given: .>--.< а «<, .<-. *>,w ""ihw

L A = It's raining outside.>..;; j .„ , | G,., d

B = Asphalt is wet. ts

(A implication 2?) = £bш on It’s raining outside, then the asphalt is wet.

Then if it rains (A= 1) and the asphalt is wet (5=1), then this is the ratio
corresponds to reality, i.e. true. But if they tell you that
it's raining outside (A= 1), and the asphalt remains dry (B = 0), then you count
you hide it with lies. But when it's not raining outside (A= 0), then asphalt
can be both dry and wet (for example, you just drove through a
shafting machine). ъ. ?; t | rfl]

Table

Statement form: if A, That IN,

G SOW! ,chi , T "/1

"? , L ■ And " . "L\ and h > < "L

Lt S.Ch;":\0"1 "

Let us explain the construction of the diagram. We are interested in the truth of the implication, so we select those rows of the truth table in which A=> IN= 1. There are three such lines. On the diagram we shade three areas in which the values A And IN the same as in the selected lines:

From the truth table it follows that the implication of two statements is false if and only if a false statement follows from a true statement (when a true premise leads to a false conclusion). Sometimes this property is taken as the definition of the implication operation.

Let us examine one of the above examples of consequences that contradict common sense.

(A = 0)n(B = 0)

(A = 0)n (B = 1)

(L = 1)n(I = 1)

Logical equality (equivalence)

Logical equality (equivalence) is formed by combining two statements into one using the turn of phrase “... if and only if ...».

Part 1. Elements of mathematical logic^

Chapter 3. Logical Operations

Examples of equivalences: "

1) An angle is called right then and just when he equals 90°.

2) Two lines are parallel then and only when they do not intersect..,

3) Any material point maintains a state of rest or uniform rectilinear motion if and only if there is no external influence.(Newton's first law.)

4) The head thinks then and only then when the tongue is at rest.(Joke.)

All laws of mathematics, physics, all definitions are the equivalence of statements.

Equivalence notation: A = B; A<=>IN; A ~ B.(In this tutorial: A O IN.)

Let's give an example of equivalence. Let the following statements be given:

A= The number is divisible by 3 without a remainder (multiples of three). IN= The sum of the digits of a number is divisible by 3.

(A equivalent B) = A number is divisible by 3 if and only when
the sum of its digits is divisible by 3., ;

Explanation:

A	IN	A<^В

Truth table:

	Meaning
	statements
The meaning of statements	The number is a multiple of 3
A And IN for the specified< значений "*"	then and only when
*	the sum of its digits divided entirely by 3
The number is not	The sum of the numbers is not	True
multiple of three	multiple of three
The number is not	Sum of digits	Lie
multiple of three	multiple of three
The number is a multiple	The sum of the numbers is not	Lie
three	multiple of three
The number is a multiple	Sum of digits	True
three	multiple of three

From the truth table it follows that the equivalence of two statements is true if and only if both statements are true or both are false. Sometimes this property is taken as the definition of the equivalence operation.

In set theory this operation corresponds to the operation equivalence sets.

To construct the corresponding equivalence of sets in the Euler-Venn diagram, we select those rows of the truth table in which A<=> IN= 1. There are two of them. On the diagram we shade two areas in which the values AnV the same as in the selected lines.

Graphic illustration: c~J_ ........ 1l...Li

Ш BASIC CONCEPTS AND DEFINITIONS

Logical operation- a method of constructing a complex statement from given statements, in which the truth value of the complex statement is completely determined by the truth values of the original statements.

Inversion(logical negation) is formed from a statement by adding the particle “not” to the predicate or using the figure of speech “it is not true that...”.

Inversion symbol: NOT A;-. A; A; NOT A.>"i,t

Table
truth: ■■■ g -

A	A

The inversion of a statement is true when
showing is false, and false when the statement
true. ■--■

! t■ .■ " N ■

Part 1. Elements of mathematical logic

G Chapter 3. Logical operations

Conjunction(logical multiplication) is formed by combining two statements into one using the conjunction “and”.

Conjunction notation: A I B; A L IN; A& IN; A ■ B; A AND IN.

; (G">* „*

Equivalence(logical equality) is formed by combining two statements into one using the turn of phrase “... if and only if...”.

Equivalence notation: A = B; A<=> IN; A ~ B.

Truth table:

The equivalence of two statements is true if and only if both statements are true or both are false.

Disjunction(logical addition) is formed by connecting two statements into one using the conjunction “or”. ,

Disjunction notation: A OR IN; A\B; L V IN; A+ IN.

Truth table:

Implication(logical consequence) is formed by connection two statements into one using the figure of speech “if..., then...”. Implication designation: A->B;A=$B.

Basic summary “Properties of logical operations”

Truth table:

A	IN	A^B

An implication of two statements is false if and only if a false statement follows from a true statement.

Ch1ya" | ; - VI

. ..,.. . , .-. . if . ............... --,-

■*}■

<Ч. 1

Related information.

Logical operations. Disjunction, conjunction and negation

So how do simple logical statements connect with each other to form complex ones? In natural language we use various conjunctions and other parts of speech. For example, “and”, “or”, “either”, “not”, “if”, “then”, “then”. Example of complex statements: “he has knowledge And skills", "she will arrive on Tuesday, or on Wednesday", "I will play Then, when I do my homework", "5 Not equals 6". How do we decide what we've been told is true or not? Somehow logically, even somewhere unconsciously, based on previous life experience, we understand that the truth with the union “and” occurs in the case of the truthfulness of both simple statements. Once one becomes a lie, the entire complex statement will be false. But, with the connective “or”, only one simple statement must be true, and then the whole expression will become true.

Boolean algebra transferred this life experience to the apparatus of mathematics, formalized it, and introduced strict rules for obtaining an unambiguous result. Unions began to be called logical operators here.

The algebra of logic involves many logical operations. However, three of them deserve special attention, because... with their help you can describe all the others, and, therefore, use less variety of devices when designing circuits. Such operations are conjunction(AND), disjunction(OR) and negation(NOT). Often the conjunction is denoted & , disjunction - || , and the negation is a bar over the variable indicating the statement.

With a conjunction, the truth of a complex expression arises only if all the simple expressions that make up the complex are true. In all other cases, the complex expression will be false.

With disjunction, the truth of a complex expression occurs when at least one simple expression included in it is true, or two at once. It happens that a complex expression consists of more than two simple ones. In this case, it is enough for one simple to be true and then the whole statement will be true.

Negation is a unary operation, because it is performed in relation to one simple expression or in relation to the result of a complex one. As a result of negation, a new statement is obtained that is opposite to the original one.

Truth tables

It is convenient to describe logical operations by the so-called truth tables, which reflect the results of calculations of complex statements for different values of the original simple statements. Simple statements are denoted by variables (for example, A and B).

Logical Fundamentals of Computer

Computers use various devices, the operation of which is perfectly described by the algebra of logic. Such devices include groups of switches, triggers, adders.

In addition, the connection between Boolean algebra and computers lies in the number system used in the computer. As you know, it is binary. Therefore, computer devices can store and transform both numbers and the values of logical variables.

Switching circuits

Computers use electrical circuits consisting of many switches. The switch can only be in two states: closed and open. In the first case, the current passes, in the second - not. It is very convenient to describe the operation of such circuits using the algebra of logic. Depending on the position of the switches, you may or may not receive signals at the outputs.

Gates, flip-flops and adders

A gate is a logical element that accepts some binary values and produces others depending on its implementation. For example, there are gates that implement logical multiplication (conjunction), addition (disjunction) and negation.

Triggers and adders are relatively complex devices consisting of simpler elements - gates.

The trigger is capable of storing one binary digit, due to the fact that it can be in two stable states. Triggers are mainly used in processor registers.

Adders are widely used in processor arithmetic logic units (ALUs) and perform summation of binary bits.

The construction of computers, or rather hardware, is based on the so-called valves. They are fairly simple elements that can be combined with each other, thereby creating various schemes. Some schemes are suitable for implementation arithmetic operations, and on the basis of others they build different memory COMPUTER.

A ventel is a device that produces the result of a Boolean operation from the data (signals) entered into it.

The simplest valve is a transistor inverter that converts low voltage to high voltage or vice versa (high to low). This can be thought of as converting a logical zero to a logical one or vice versa. Those. we get a valve NOT.

By connecting a pair of transistors in different ways, gates are obtained OR NO And AND-NOT. These gates no longer accept one, but two or more input signals. The output signal is always the same and depends (produces high or low voltage) on the input signals. In the case of a NOR gate, a high voltage (logical one) can only be achieved if all inputs are low. In the case of an NAND gate, the opposite is true: a logical one is obtained if all input signals are zero. As you can see, this is the opposite of such familiar logical operations as AND and OR. However, NAND and NOR gates are commonly used because their implementation is simpler: AND-NOT and NOR-NOT are implemented by two transistors, while logical AND and OR are implemented by three.

The gate output can be expressed as a function of the inputs.

It takes very little time for a transistor to switch from one state to another (switching time is measured in nanoseconds). And this is one of the significant advantages of schemes built on their basis.

For logical values, three operations are commonly used:

Conjunction– logical multiplication (AND) – and, &, ∧.
Disjunction– logical addition (OR) – or, |, v.
Logical negation (NOT) – not,.

Logical expressions can be converted according to laws of algebra of logic:

Laws of reflexivity
a ∨ a = a
a ∧ a = a
Commutativity laws
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Laws of associativity
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Distributivity laws
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Law of Negation of Negation
(a) = a
De Morgan's laws
(a ∧ b) = a ∨ b
(a ∨ b) = a ∧ b
Laws of absorption
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

Every logical formula defines some Boolean function. On the other hand, for any Boolean function one can write infinitely many formulas representing it. One of the main tasks of logical algebra is finding canonically x forms (i.e. formulas constructed according to a certain rule, canon), as well as the simplest formulas representing Boolean functions.

If a logical function is expressed through disjunction, conjunction and negation of variables, then this form of representation is called normal. Among normal forms, there are those in which functions are written in a unique way. They are called perfect.

A special role in the algebra of logic is played by the classes of disjunctive and conjunctive perfect normal forms. They are based on the concepts of elementary disjunction and elementary conjunction.

The formula is called elementary conjunction, if it is the conjunction of one or more variables, taken with or without negation. One variable or its negation is considered one-term elementary conjunction.

The formula is called elementary disjunction, if it is a disjunction (perhaps monomial) of variables and negations of variables.

DNF AND SDNF

The formula is called disjunctive normal form(DNF), if it is a disjunction of non-repeating elementary conjunctions. DNFs are written as: А1 v А2 v ... v Аn, where each An- elementary conjunction.

Formula A from k variables are called perfect disjunctive normal form(SDNF), if:
1.A is a DNF in which every elementary conjunction is a conjunction k variables x1, x2, …, xk, and in the i-th place of this conjunction there is either a variable xi or its denial;
2. All elementary conjunctions in such a DNF are pairwise distinct.

For example: A = x1 & NOT x2 v x1 & x2

A perfect disjunctive normal form is a formula constructed according to strictly defined rules up to the order of the elementary conjunctions (disjunctive terms) in it.

It is an example of a unique representation of a Boolean function in the form of a formulaic (algebraic) notation.

SDNF theorem

Let f(x1 x2, …, xn)– Boolean function of n variables that is not identically zero. Then there is a perfect disjunctive normal form expressing the function f.

Algorithm for constructing SDNF using a truth table:

1. In the truth table, we mark the sets of variables for which the value of the function f = 1.
2.For each marked set, we write the conjunction of all variables as follows: if the value of some variable in this set is equal to 1, then we include the variable itself in the conjunction, otherwise, its negation.
3. We connect all the resulting conjunctions with disjunction operations.

KNF AND SKNF

The formula is called conjunctive normal form(CNF), if it is a conjunction of non-repeating elementary disjunctions. CNFs are written in the form: A1 & A2 & ... & An, where each An– elementary disjunction.

Formula A from k variables are called perfect conjunctive normal form(SKNF), if:
1. A is a CNF in which every elementary disjunction is a disjunction k variables x1, x2, …, xk, and in the i-th place of this disjunction there is either the variable xi or its negation;
2. All elementary disjunctions in such a CNF are pairwise distinct.

For example: A = (x1 v NOT x2) & (x1 v x2)

SCNF theorem

Let f(x1 x2, …, xn)– Boolean function of n variables that is not identically zero. Then there is a perfect conjunctive normal form expressing the function f.

Algorithm for constructing SCNF using a truth table:

1. In the truth table, we mark the sets of variables for which the value of the function f = 0.
2. For each marked set, we write the disjunction of all variables as follows: if the value of some variable in this set is equal to 0, then we include the variable itself in the disjunction; otherwise, its negation.
3. We connect all the resulting disjunctions with conjunction operations.

From the algorithms for constructing SDNF and SCNF, it follows that if for most of the sets of variable values the function is equal to 0, then to obtain its formula it is easier to construct SDNF, otherwise - SCNF.

Minimizing Logical Functions Using Karnaugh Maps

The Karnaugh map is a graphical way of minimizing switching (Boolean) functions, providing relative ease of working with large expressions and eliminating potential races. Represents the operations of pairwise incomplete gluing and elementary absorption. Karnaugh maps are considered as the truth table of a function rearranged accordingly. Carnaugh maps can be thought of as a specific flat development of an n-dimensional Boolean cube.

Carnot maps were invented in 1952 by Edward W. Veitch and improved in 1953 by Maurice Carnot, a physicist at Bell Labs, and were intended to help simplify digital electronic circuits.

In a Carnaugh map, Boolean variables are transferred from the truth table and ordered using Gray code, in which each next number differs from the previous one by only one digit.

The main method for minimizing logical functions presented in the form of SDNF or SCNF is the operation of pairwise incomplete gluing and elementary absorption. The operation of pairwise gluing is carried out between two terms (members) containing identical variables, the occurrences of which (direct and inverse) coincide for all variables except one. In this case, all variables except one can be taken out of brackets, and the direct and inverse occurrences of one variable remaining in brackets can be glued together. For example:

The possibility of absorption follows from the obvious equalities

Thus, the main task in minimizing SDNF and SCNF is to find terms suitable for gluing with subsequent absorption, which can be quite a difficult task for large shapes. Carnaugh maps provide a visual way to find such terms.

The figure shows a simple truth table for a function of two variables, a 2-dimensional cube (square) corresponding to this table, as well as a 2-dimensional cube with the designation of SDNF terms and an equivalent table for grouping terms:

Veitch diagram method.

"The method allows you to quickly obtain minimal DNFs of a Boolean function f of a small number of variables. The method is based on specifying Boolean functions by diagrams of some special type, called Veitch diagrams. For a Boolean function of two variables, the Veitch diagram has the form (Table 4.4.1).

Each cell in the diagram corresponds to a set of Boolean function variables in its truth table. In (Table 4.4.1) this correspondence is shown. In the cell of the Veitch diagram, a unit is placed if the Boolean function takes the unit value on the corresponding set. Zero values of the Boolean function are not set in the Veitch diagram. For a Boolean function of three variables, the Veitch diagram has the following form (Table 4.4.2).

Adding the same table to it gives a diagram for a function of 4 variables (Table 4.4.3).

In the same way, that is, by adding another diagram of 3 variables to the one just considered, you can get a diagram for a function of 5 variables, etc., but diagrams for functions with more than 4 variables are rarely used. The following diagrams are typical:

The synthesis of combinational circuits can be illustrated by solving a simple problem.

Problem 1

The admissions committee, consisting of three commission members and one chairman, decides the applicant’s fate by a majority vote. In the event of an equal distribution of votes, the majority is determined by the group in which the chairman of the selection committee finds himself. Build an automaton that ensures the determination of the majority of votes.

Solution

Taking into account the above assumptions, the problem condition can be unambiguously represented in the form of a truth table.

We fill out the table taking into account the fact that the function f is completely defined, i.e. it is defined on all possible sets of variables x1 - x4. For n input variables, there are N = 2n sets of variables. In our example, N = 24 = 16 sets.

These sets can be written in any order, but it is better in ascending binary code order.

Decimal number system

The base of this number system p is equal to ten. This number system uses ten digits. Currently, the symbols used to denote these numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. A number in the decimal number system is written as the sum of units, tens, hundreds, thousands, and so on. That is, the weights of adjacent digits differ by a factor of ten. Numbers smaller than one are written in the same way. In this case, the digits of the number will be called tenths, hundredths or thousandths of a unit.

Let's look at an example of writing a decimal number. In order to show that the example uses the decimal number system, we use the index 10. If, in addition to the decimal form of writing numbers, no other form of recording is intended to be used, then the index is usually not used:

A 10 =247.56 10 =2*10 2 +4*10 1 +7*10 0 +5*10 -1 +6*10 -2 = 200 10 +40 10 +7 10 +0.5 10 +0 .06 10

Here the most significant digit of the number will be called hundreds. In the above example, hundreds correspond to the number 2. The next digit will be called tens. In the above example, the number 4 corresponds to tens. The next digit will be called ones. In the example above, units correspond to the number 7. Tenths correspond to the number 5, and hundredths – 6.

Binary number system

The base of this number system p is equal to two. This number system uses two digits. In order not to invent new symbols to denote numbers, the symbols of the decimal digits 0 and 1 were used in the binary number system. In order not to confuse the number system in writing a number, the index 2 is used. If, in addition to the binary form of writing numbers, no other form is intended to be used, then this index can be omitted.

A number in this number system is written as the sum of ones, twos, fours, eights, and so on. That is, the weights of adjacent digits differ by a factor of two. Numbers smaller than one are written in the same way. In this case, the digits of the number will be called halves, quarters or eighths of a unit.

Let's look at an example of writing a binary number:

A 2 =101110.101 2 = 1*2 5 +0*2 4 +1*2 3 +1*2 2 +1*2 1 +0*2 0 +1*2 -1 +0*2 -2 + 1*2 -3 = 32 10 +8 10 +4 10 +2 10 +0.5 10 +0.125 10 =46.625 10

When writing in the second line an example of decimal equivalents of binary digits, we did not write powers of two that are multiplied by zero, since this would only lead to cluttering the formula and, as a result, making it difficult to understand the material.

A disadvantage of the binary number system can be considered the large number of digits required to write numbers. An advantage of this number system is the ease of performing arithmetic operations, which will be discussed later.

Octal number system

The base of this number system p is equal to eight. The octal number system can be thought of as a shorter way to write binary numbers, since the number eight is a power of two. This number system uses eight digits. In order not to invent new symbols to denote numbers, the decimal number symbols 0, 1, 2, 3, 4, 5, 6 and 7 were used in the octal number system. In order not to confuse the number system, the index 8 is used in writing the number. In addition to the octal form of writing numbers, no other form of notation is expected to be used, then this index can be omitted.

A number in this number system is written as the sum of ones, eights, sixty fours, and so on. That is, the weights of adjacent digits differ by a factor of eight. Numbers smaller than one are written in the same way. In this case, the digits of the number will be called eighths, sixty-fours, and so on, fractions of one.

Let's look at an example of writing an octal number:

A 8 =125.46 8 =1*8 2 +2*8 1 +5*8 0 +4*8 -1 +6*8 -2 = 64 10 +16 10 +5 10 +4 10 /8 10 + 6 10 /64 10 = 85.59375 10

The second line of the example above actually converts a number written in octal form into the decimal representation of the same number. That is, we actually looked at one of the ways to convert numbers from one form of representation to another.

Since the formula uses simple fractions, it is possible that exact translation from one form of representation to another becomes impossible. In this case, they are limited to a specified number of fractional digits.

Types of digital comparators

Comparator for comparing different polarity signals

Comparator for comparing unipolar signals

Comparator for comparing unipolar voltages with a hysteresis characteristic. In the considered comparators, characteristics with hysteresis properties can be obtained. The introduction of hysteresis into the operation of the comparator somewhat reduces the accuracy of the comparison, but makes it immune to noise and interference. Hysteresis is achieved by turning on a higher reference voltage when the voltage changes from a low to a high level, compared to the value used when the voltage changes from a high to low level. In this case, a high reference voltage value is called the upper response threshold, and a low value is called the lower response threshold. This is achieved by introducing positive feedback.

Multi-bit comparators

Let us consider as an example a four-bit digital comparator of the K555SP1 series, the eight inputs of which are used to connect two four-bit words: A0. A3, B0. B3 to be compared. Control inputs I(A>B), (A = B) and I(A< В) могут быть использованы для наращивания разрядности компаратора. Предусмотрены три выхода результата сравнения: А>B, A = B and A<В.

The truth table of such a comparator (Table 1) is divided row by row into three sections.

The first section (the top eight rows of the table) defines the case when the comparator operates when the four-bit words to be compared are not equal to each other. In this case, the signals at the inputs of increasing the bit depth as a reaction to the signals of the lower bits of the words being compared do not have any effect on the result of the comparison.

Rice. 1. Conventional graphical representation of a comparator type SP1

The three rows of the second section of this table characterize the operation of the comparator with a sequential method of increasing the bit depth, i.e. when the outputs of the low-order comparator are connected to the control inputs of the high-order comparator.

Single-bit comparators

A single-bit comparator has two inputs that simultaneously receive single-bit binary numbers x1 and x2, and three outputs (=, >,<). Из таблицы истинности логические уравнения компаратора при сравнении x1 с x2 получаются в виде

The implementation of such a comparator in the NAND basis leads to the following figure (Fig. 2):

Figure 2. Single-bit binary number comparator.

Table 1. Truth table of a four-bit comparator type SP1

Comparator(analog signals) (eng. comparator - comparing device) - an electronic circuit that receives two analog signals at its inputs and produces a logical “1” if the signal at the direct input (“+”) is greater than at the inverse input (“−” ), and logical “0” if the signal at the direct input is less than at the inverse input.

One comparison voltage of the binary comparator divides the entire input voltage range into two subranges. The binary logic signal (bit) at the output of the binary comparator indicates which of the two subranges the input voltage is in.

The simplest comparator is a differential amplifier. The comparator differs from a linear operational amplifier (op-amp) in the design of both the input and output stages:

The comparator input stage must withstand a wide range of input voltages between the inverting and non-inverting inputs, up to the swing of the supply voltages, and quickly recover when the sign of this voltage changes.
The output stage of the comparator is compatible in terms of logical levels and currents with a specific type of logic circuit inputs (TTL, ESL technologies, etc.). Output stages based on a single transistor with an open collector are possible (compatible with TTL and CMOS logic).
To form a hysteretic transfer characteristic, comparators are often covered with positive feedback. This measure avoids rapid unwanted switching of the output state due to noise in the input signal when the input signal is slowly changing.

When the reference comparison voltage is applied to the inverting input, the input signal is applied to the non-inverting input, and the comparator is non-inverting (follower, buffer).

By applying the reference comparison voltage to the non-inverting input, the input signal is applied to the inverting input and the comparator is inverting (inverting).

Comparators based on logical elements covered by feedback are somewhat less commonly used (see, for example, a Schmitt trigger - not a comparator by nature, but a device with a very similar scope of application).

When mathematically modeling a comparator, the problem of the output voltage of the comparator arises when the voltages at both inputs of the comparator are the same. At this point the comparator is in a state of unstable equilibrium. The problem can be solved in many different ways, described in the “software comparator” subsection.

Pulse counter– an electronic device designed to count the number of pulses applied to the input. The number of received pulses is expressed in the binary number system.

Pulse counters are a type of registers (counting registers) and are built on flip-flops and logic elements, respectively.

The main indicators of counters are the counting coefficient K 2n - the number of pulses that can be counted by the counter. For example, a counter consisting of four flip-flops may have a maximum counting factor of 24=16. For a four-trigger counter, the minimum output code is 0000, the maximum is -1111, and with a counting coefficient Kc = 10, the output count stops at code 1001 = 9.

Figure 1, a shows the circuit of a four-bit counter using T-flip-flops connected in series. Counting pulses are supplied to the counting input of the first flip-flop. The counting inputs of subsequent flip-flops are connected to the outputs of previous flip-flops.

The operation of the circuit is illustrated by the timing diagrams shown in Figure 1, b. When the first counting pulse arrives, upon its decline, the first trigger goes into state Q1 = 1, i.e. The digital code 0001 is written in the counter. At the end of the second counting pulse, the first trigger switches to the “0” state, and the second switches to the “1” state. The counter records the number 2 with code 0010.

Figure 1 – Binary four-bit counter: a) circuit, b) graphical designation, c) timing diagrams of operation

From the diagram (Fig. 1, b) it is clear that, for example, according to the decline of the 5th pulse, code 0101 is written in the counter, according to the 9th - 1001, etc. At the end of the 15th pulse, all bits of the counter are set to the “1” state, and at the fall of the 16th pulse, all triggers are reset, i.e., the counter goes to its original state. To force the counter to zero, there is a “reset” input.

The counting coefficient of a binary counter is found from the relation Ксч = 2n, where n is the number of bits (triggers) of the counter.

Counting the number of pulses is the most common operation in digital information processing devices.

During operation of the binary counter, the pulse repetition rate at the output of each subsequent trigger is halved compared to the frequency of its input pulses (Fig. 1, b). Therefore, counters are also used as frequency dividers.

Encryptor(also called an encoder) converts the signal into a digital code, most often decimal numbers into the binary number system.

The encoder has m inputs, numbered sequentially with decimal numbers (0, 1,2,..., m - 1), and n outputs. The number of inputs and outputs is determined by the dependence 2n = m (Fig. 2, a). The symbol "CD" is formed from the letters in the English word Coder.

Applying a signal to one of the inputs results in the appearance at the outputs of an n-bit binary number corresponding to the input number. For example, when a pulse is applied to the 4th input, a digital code 100 appears at the outputs (Fig. 2, a).

Decoders (also called decoders) are used to convert binary numbers back into small decimal numbers. The decoder inputs (Fig. 2, b) are intended to supply binary numbers, the outputs are sequentially numbered with decimal numbers. When a binary number is applied to the inputs, a signal appears at a specific output, the number of which corresponds to the input number. For example, when applying code 110, the signal will appear at the 6th output.

Figure 2 – a) UGO encoder, b) UGO decoder

Multiplexer- a device in which the output is connected to one of the inputs, in accordance with the address code. That. A multiplexer is an electronic switch or commutator.

Figure 3 – Multiplexer: a) graphical designation, b) state table

An address code is supplied to inputs A1, A2, which determines which of the signal inputs will be transmitted to the output of the device (Fig. 3).

To convert information from digital to analog form, they use digital-to-analog converters (DACs), and for the inverse transformation - analog-to-digital converters (ADCs).

The input signal of the DAC is a binary multi-bit number, and the output signal is the voltage Uout, generated based on the reference voltage.

The analog-to-digital conversion procedure (Fig. 4) consists of two stages: time sampling (sampling) and level quantization. The sampling process consists of measuring the values of a continuous signal only at discrete points in time.

Figure 4 – Analog-to-digital conversion process

For quantization, the range of change in the input signal is divided into equal intervals - quantization levels. In our example there are eight, but usually there are many more. The quantization operation comes down to determining the interval in which the sampled value falls and assigning a digital code to the output value.

A register is a functional unit that combines several triggers of the same type.

1) Latch registers– built on latched triggers (K155TM5; K155TM7), recording into which is carried out by the level of the strobe signal.

In the K155TM8 trigger, recording is carried out by the positive edge of the strobe signal.

2) Shift registers– perform the function of only sequential code reception.

3) Universal registers– can receive information in parallel and serial code.

4) Special registers– K589IR12 have additional options for use.

Shift register

This is a register, the contents of which, when a control signal is applied, can be shifted towards the higher or lower digits. For example, the left shift is shown in Table 9.

Table 9 Code shift left

Universal registers

They have external outputs and inputs for all bits, as well as a serial DS input.

There are two types of universal registers:

1) a register that performs a shift in only one direction and receives code in parallel (for example, K155IR1; K176IR3).

2) with four operating modes: shift right/left; parallel reception; storage (for example, 8-bit register K155IR13; 4-bit register K500IR141).

The main elementary operation performed on number codes in digital devices is arithmetic addition.

Logical adder operating node that performs arithmetic adding the codes of two numbers. During arithmetic addition, other additional operations are performed: taking into account the signs of numbers, aligning the orders of terms, and the like. These operations are performed in arithmetic logic units (ALUs) or processing elements, the core of which are adders.

Adders are classified according to various criteria.

Depending on the number system distinguish:

binary;
binary decimal (in general, binary coded);
decimal;
others (for example, amplitude).

By the number of simultaneously processed digits of the added numbers:

single digit,
multi-bit.

By the number of inputs and outputs of single-bit binary adders:

quarter adders (elements “sum modulo 2”; elements “exclusive OR”), characterized by the presence of two inputs, to which two single-digit numbers are supplied, and one output, at which their arithmetic sum is realized;
half-adders, characterized by the presence of two inputs, to which the same digits of two numbers are supplied, and two outputs: one implements the arithmetic sum in a given digit, and the other carries a transfer to the next (higher digit);
complete single-bit binary adders, characterized by the presence of three inputs, to which the same digits of two numbers being added and a transfer from the previous (lower) digit are supplied, and two outputs: on one, the arithmetic sum in this digit is realized, and on the other, the transfer to the next (higher) discharge).

By the way of representing and processing added numbers multi-bit adders are divided into:

sequential, in which numbers are processed one by one, digit by digit on the same equipment;
parallel, in which the terms are added simultaneously across all digits, and each digit has its own equipment.

In the simplest case, a parallel adder consists of n one-bit adders, sequentially (from least significant to most significant) connected by carry circuits. However, such an adder circuit is characterized by a relatively low performance, since the generation of sum and carry signals in each i-th bit occurs only after the transfer signal arrives from the (i-1) th bit. Thus, the speed of the adder is determined by the signal propagation time along the transfer chain. Reducing this time is the main task when constructing parallel adders.

To reduce the propagation time of the transfer signal, use: Constructive decisions

PROPERTIES OF LOGICAL OPERATIONS

1. Designations

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 indicate a lie (false statement).

1.2. Two Boolean expressions containing variables are called equivalent (equivalent) if the values of these expressions coincide for any values of the variables. Thus, 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 = 1, B = 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 intended to be complete, but is hopefully representative enough.

2.1. General properties

For a set of n there are exactly logical variables 2 n different meanings. Truth table for logical 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 values of the variables, then the entire disjunction is true for this set of values.
If all expressions from a certain list are true on a certain set of variable values, then the disjunction of these expressions is also true.
If all expressions from a certain list are false on a certain set of variable values, then the disjunction of these expressions is also false.
The meaning of a disjunction does not depend on the writing 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 this set of values.
If all expressions from a certain list are true on a certain set of variable values, then the conjunction of these expressions is also true.
If all expressions from a certain list are false on a certain set of variable values, then the conjunction of these expressions is also false.
The meaning of a conjunction does not depend on the writing order of the subexpressions to which it is applied.

2.4. Simple disjunctions and conjunctions

Let us 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 equivalent to disjunction (¬ A) \/ B. This disjunction can also be written as follows: ¬ 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.

Conjunction: corresponds to the conjunction: “and”, denoted by the sign^, denotes logical multiplication.

A conjunction of two logical ~ is true if and only if both statements are true. Can be generalized for any number of variables A^B^C = 1 if A=1, B=1, C=1.

Truth table for the operation “Conjunction”:

Table No. 2

Disjunction

The logical operation corresponds to the union OR, denoted by the sign v, otherwise called LOGICAL ADDITION.

A disjunction of two logical variables is false if and a pebble is false if both statements are false.

This definition can be generalized to any number of logical variables combined by a disjunction.

A v B v C = 0 only if A = O, B = O, C - 0.

Truth table for the operation “Disjunction”:

Table No. 3

Inversion

The logical operation corresponds to the particle not, is denoted by ¬ or ¯ and is a logical negation.

The inverse of a boolean variable is true if the variable is false and vice versa: the inverse is false if the variable is true.

Truth table for operation "Inversion":

Table No. 5

The equivalence “And then B and only then” is denoted by A ~ B

Table No. 6

When calculating the value of a logical expression (formula), logical operations are calculated in a certain order, according to their priority:

inversion;

conjunction;

disjunction;

implication and equivalence;

Operations of the same priority are performed from left to right. Parentheses are used to change the order of actions.

Formalization of statements

Natural languages are used to create descriptive information models. Numerous descriptive information models are known in the history of science; for example, the heliocentric model of the world that Copernicus proposed was formulated as follows:

The Earth rotates on its axis and around the Sun;

all planets orbit around the Sun;

With the help of formal languages, formal information models (mathematical, logical, etc.) are built. One of the most widely used formal languages is mathematics. Models built using mathematical concepts and formulas are called mathematical models. The language of mathematics is a collection of formal languages.

The language of algebra allows one to formalize functional dependencies between quantities. Thus, Newton formalized the heliocentric system of the world, discovering the laws of mechanics and the law of universal gravitation and writing them down in the form of algebraic functional dependencies. For example, in a school physics course, many different functional dependencies are considered, expressed in the language of algebra, which are mathematical models of the phenomena or processes being studied.

The language of logic algebra (propositional algebra) allows you to build formal logical models. Using propositional algebra, you can formalize (write in the form of logical expressions) simple and complex statements expressed in natural language. Building logical models allows you to solve logical problems, build logical models of computer devices (adder, trigger), and so on.

The process of building information models using formal languages is called formalization.

In the process of understanding the world around us, humanity constantly uses modeling and formalization. When studying a new object, first, its descriptive information model is usually built in natural language, then it is formalized, that is, expressed using formal languages (mathematics, logic, etc.).

Algebra of logic and logical foundations of the computer

Algebra of logic (Boolean algebra) is a branch of mathematics that arose in the 19th century thanks to the efforts of an English mathematician J. Boulya. At first, Boolean algebra had no practical significance. However, already in the 20th century, its provisions found application in describing the functioning and development of various electronic circuits. The laws and apparatus of logical algebra began to be used in the design of various parts of computers (memory, processor). Although this is not the only area of application of this science.

What is it? algebra of logic? First, it studies methods for establishing the truth or falsity of complex logical statements using algebraic methods. Secondly, Boolean algebra does this in such a way that a complex logical statement is described by a function, the result of which can be either true or false (1 or 0). In this case, function arguments (simple statements) can also have only two values: 0 or 1.

What is simple logical statement? These are phrases like “two is more than one”, “5.8 is an integer”. In the first case we have truth, and in the second we have false. The algebra of logic does not concern the essence of these statements. If someone decides that the statement “The Earth is square” is true, then the algebra of logic will accept this as a fact. The fact is that Boolean algebra deals with calculating the result of complex logical statements based on previously known values of simple statements.

Logical operations. Disjunction, conjunction and negation

How do we decide what we've been told is true or not? Somehow logically, even somewhere unconsciously, based on previous life experience, we understand that the truth with the union “and” occurs in the case of the truthfulness of both simple statements. Once one becomes a lie, the entire complex statement will be false. But, with the connective “or”, only one simple statement must be true, and then the whole expression will become true.

The algebra of logic involves many logical operations. However, three of them deserve special attention, because... with their help you can describe all the others, and, therefore, use less variety of devices when designing circuits. Such operations are conjunction (AND), disjunction (OR) and negation (NOT). Often the conjunction is denoted by &, the disjunction by ||, and the negation by a bar over the variable denoting the statement.

At conjunction@/a> true with a false expression arises only if all the simple expressions that make up the complex are true. In all other cases, the complex expression will be false.

At disjunctions truth of a complex expression occurs when at least one simple expression included in it is true, or two at once. It happens that a complex expression consists of more than two simple ones. In this case, it is enough for one simple to be true and then the whole statement will be true.

Negation- this is a unary operation, because it is performed in relation to one simple expression or in relation to the result of a complex one. As a result of negation, a new statement is obtained that is opposite to the original one.

For logical values, three operations are commonly used:

Conjunction - logical multiplication (AND) - and, &, ∧.

Disjunction - logical addition (OR) - or, |, v.

Logical negation (NOT) - not,.

It is convenient to describe logical operations with so-called truth tables, which reflect the results of calculations of complex statements for various values of the original simple statements. Simple statements are denoted by variables (for example, A and B).

Logical Fundamentals of Computer

Computers use various devices, the operation of which is perfectly described by the algebra of logic. Such devices include groups of switches, triggers, adders.

Switching circuits

Gates, flip-flops and adders

Triggers And adders- these are relatively complex devices consisting of simpler elements - valves.

The trigger is capable of storing one binary digit, due to the fact that it can be in two stable states. Triggers are mainly used in processor registers.

Adders are widely used in processor arithmetic logic units (ALUs) and perform summation of binary bits.

Information and information processes. Types of information, its binary coding. Amount of information, approaches to defining the concept of “amount of information,” units of measurement of information. Binary coding of numeric, text, graphic, audio information

Information(from Latin informatio - “explanation, presentation, awareness”) - information about something, regardless of the form of its presentation.

Currently, there is no single definition of information as a scientific term. From the point of view of various fields of knowledge, this concept is described by its specific set of characteristics. The concept of “information” is basic in a computer science course, where it is impossible to define it through other, more “simple” concepts.

Information properties:

Objectivity (information is objective if it does not depend on anyone’s opinion or judgment);

Reliability (information is reliable if it reflects the true state of affairs);

Completeness (information is complete if it is sufficient for understanding and making a decision);

Relevance (information is relevant, timely, if it is important, significant for the present time);

Usefulness (evaluated by the tasks that we can solve with its help);

Understandability (information is understandable if it is expressed in a language accessible to the recipient);

Availability (information is available if we can get it).

Information process- a set of sequential actions (operations) performed on information (in the form of data, information, facts, ideas, hypotheses, theories, etc.) to obtain any result (achieve a goal).

Information is manifested precisely in information processes. Information processes always take place in some kind of system (social, sociotechnical, biological, etc.).

The most generalized information processes are the collection, transformation, and use of information.

The main information processes studied in a computer science course include: search, selection, storage, transmission, coding, processing, and protection of information.

Information processes carried out using certain information technologies form the basis of human information activity.

A computer is a universal device for automated execution of information processes.

People deal with many types of information. The communication of people with each other at home and at school, at work and on the street is the transfer of information. A teacher's story or a friend's story, a television program, a telegram, a letter, an oral message, etc. - all these are examples of information transfer.

And we already talked about that that the same information can be transmitted and received in different ways. So, to find the way to a museum in an unfamiliar city, you can ask a passerby, get help from the information desk, try to figure it out yourself using a city map, or consult a guidebook. When we listen to a teacher's explanation, read books or newspapers, watch TV news, visit museums and exhibitions - at this time we receive information.

A person stores the information received in his head. The human brain is a huge repository of information. A notepad or notebook, your diary, school notebooks, a library, a museum, a cassette with recordings of your favorite tunes, videotapes - all these are examples of storing information.

Information can be processed: translating text from English into Russian and vice versa, calculating the sum of given terms, solving a problem, coloring pictures or contour maps - all these are examples of information processing. You all loved coloring in coloring books at one time or another. It turns out that at this time you were engaged in an important process - information processing, turning a black and white drawing into a color one.

Information can even be lost. Let's say Dima Ivanov forgot his diary at home and therefore wrote down his homework on a piece of paper. But, while playing at recess, he made an airplane out of it and launched it. Arriving home, Dima could not do his homework, he lost information. Now he needs to either try to remember what he was asked, or call a classmate to get the necessary information, or go to school with unfinished homework.

Binary coding - one of the common ways of presenting information. In computers, robots and numerically controlled machines, as a rule, all the information that the device deals with is encoded in the form of words of the binary alphabet.

The binary alphabet consists of two digits 0 and 1.

Digital computers (personal computers belong to the digital class) use binary coding of any information. This is mainly explained by the fact that it was technically easier to build a technical device that accurately distinguishes between 2 different signal states than one that would accurately distinguish between 5 or 10 different states.

The disadvantages of binary coding include very long binary code records, which makes them difficult to work with.