Truth table of 5 variables. I. Organizational moment

And, which will be enough for you to solve complex logical expressions. We will also look at the order in which these logical operations are performed in complex logical expressions and present truth tables for each logical operation. We advise you to use our programs for solving problems in mathematics, and. In addition to a large number of programs for solving problems, the site runs , where you can always ask a question and where you can always be helped with solving problems. Use our services for your health!

Glossary, definitions of logic

Statement is a declarative sentence about which one can definitely say whether it is true or false (true (logical 1), false (logical 0)).

Logical operations- mental actions, the result of which is a change in the content or scope of concepts, as well as the formation of new concepts.

Boolean expression- an oral statement or recording, which, along with constant quantities, necessarily includes variable quantities (objects). Depending on the values ​​of these variables (objects), a logical expression can take one of two possible values: true (logical 1) or false (logical 0).

Complex logical expression- a logical expression consisting of one or more simple logical expressions (or complex logical expressions) connected using logical operations.

Logical operations and truth tables

1) Logical multiplication or conjunction:

A conjunction is a complex logical expression that is considered true if and only if both simple expressions are true; in all other cases, the complex expression is false.
Designation: F = A & B.

Truth table for conjunction

3) Logical negation or inversion:

Inversion is a complex logical expression, if the original logical expression is true, then the result of negation will be false, and vice versa, if the original logical expression is false, then the result of negation will be true. In other simple words, this operation means that the particle NOT or the words NOT TRUE WHAT is added to the original logical expression.

Truth table for inversion

5) Logical equivalence or equivalence:

Equivalence is a complex logical expression that is true if and only if both simple logical expressions have the same truth.

Truth table for equivalence

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Order of logical operations in a complex logical expression

1. Inversion;
2. Conjunction;
3. Disjunction;
4. Implication;
5. Equivalence.

Parentheses are used to change the specified order of logical operations.

Algebra of logic

Algebra of logic

Algebra of logic(English) algebra of logic) is one of the main branches of mathematical logic, in which algebraic methods are used in logical transformations.

The founder of the algebra of logic is the English mathematician and logician J. Boole (1815-1864), who based his logical teaching on the analogy between algebra and logic. He wrote down any statement using the symbols of the language he developed and received “equations”, the truth or falsity of which could be proven based on certain logical laws, such as the laws of commutativity, distributivity, associativity, etc.

Modern algebra of logic is a branch of mathematical logic and studies logical operations on statements from the point of view of their truth value (true, false). Statements can be true, false, or contain truth and falsehood in different proportions.

Logical statement is any declarative sentence whose content can be unequivocally stated to be true or false.

For example, “3 times 3 equals 9”, “Arkhangelsk is north of Vologda” are true statements, but “Five is less than three”, “Mars is a star” are false.

Obviously, not every sentence can be a logical statement, since it does not always make sense to talk about its falsity or truth. For example, the statement “Computer science is an interesting subject” is vague and requires additional information, and the statement “For a student of grade 10-A Ivanov A.A., computer science is an interesting subject,” depending on the interests of Ivanov A.A., can take on the meaning “true” or "lie".

Except two-valued propositional algebra, in which only two values ​​are accepted - “true” and “false”, there is multivalued propositional algebra. In such algebra, in addition to the values ​​“true” and “false”, such truth values ​​as “probable”, “possible”, “impossible”, etc. are used.

In algebra, logic differs simple(elementary) statements, designated by Latin letters (A, B, C, D, ...), and complex(composite), made up of several simple ones using logical connectives, for example, such as “not”, “and”, “or”, “if and only then”, “if... then”. The truth or falsity of complex statements obtained in this way is determined by the meaning of simple statements.

Let's denote it as A the statement “The algebra of logic is successfully applied in the theory of electrical circuits,” and through IN— “Logic algebra is used in the synthesis of relay circuits.”

Then the compound statement “The algebra of logic is successfully applied in the theory of electrical circuits and in the synthesis of relay circuits” can be briefly written as A and B; here “and” is a logical connective. It is obvious that since elementary statements A and B are true, then the compound statement is true A and B.

Each logical connective is considered as an operation on logical statements and has its own name and designation.

There are only two logical values: true (TRUE) And false (FALSE). This corresponds to the digital representation − 1 And 0 . The results of each logical operation can be written in the form of a table. Such tables are called truth tables.

Basic operations of logical algebra

1. Logical negation, inversion(lat. inversion- inversion) is a logical operation, as a result of which a new statement is obtained from a given statement (for example, A) not A), which is called negation of the original statement, is symbolically indicated by an overbar ($A↖(-)$) or by such conventions as ¬, "not", and reads: “not A”, “A is false”, “it is not true that A”, “negation of A”. For example, “Mars is a planet of the solar system” (statement A); “Mars is not a planet in the solar system” ($A↖(-)$); the statement “10 is a prime number” (statement B) is false; The statement “10 is not a prime number” (statement B) is true.

An operation used on a single quantity is called unary. The table of values ​​for this operation looks like

The statement $A↖(-)$ is false when A is true, and true when A is false.

Geometrically, negation can be represented as follows: if A is a certain set of points, then $A↖(-)$ is the complement of the set A, i.e., all points that do not belong to the set A.

2.Conjunction(lat. conjunctio- connection) - logical multiplication, an operation that requires at least two logical quantities (operands) and connects two or more statements using a connective "And"(For example, "A and B"), which is symbolically denoted by the sign ∧ (A ∧ B) and reads: “A and B.” The following signs are also used to indicate conjunction: A ∙ B; A & B, A and B, and sometimes there is no sign between statements: AB. Example of logical multiplication: “This triangle is isosceles and right-angled.” A given statement can be true only if both conditions are met, otherwise the statement is false.

A	B	A∧B
1	0	0
0	1	0
0	0	0
1	1	1

Statement A ∧ IN true only if both statements are A And IN are true.

Geometrically, the conjunction can be represented as follows: if A, B A ∧ IN there is an intersection of sets A And IN.

3. Disjunction(lat. disjunction- division) - logical addition, an operation that connects two or more statements using a connective "or"(For example, "A or B"), which is symbolically denoted by the sign ∨ (A∨ IN) and reads: "A or B". The following signs are also used to indicate disjunction: A + B; A or B; A | B. An example of logical addition: “The number x is divisible by 3 or 5.” This statement will be true if both conditions or at least one of the conditions are met.

The truth table of the operation has the form

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Statement A∨ IN is false only when both statements are A And IN false.

Geometrically, logical addition can be represented as follows: if A, B are some sets of points, then A ∨ IN is a union of sets A And IN, i.e., a figure that combines both a square and a circle.

4. Strictly separative disjunction, addition modulo two- a logical operation that connects two statements using a connective "or", used in an exclusive sense, which is symbolically denoted by the signs ∨ ∨ or ⊕ ( A ∨ ∨ B, A ⊕ IN) and reads: "either A or B". An example of addition modulo two is the statement “This triangle is obtuse or acute.” The statement is true if any one of the conditions is met.

The truth table of the operation has the form

A	IN	A⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

The statement A ⊕ B is true only if the statements A and B have different meanings.

5. Implication(lat. implisito- closely connect) - a logical operation connecting two statements using a connective "if... then" into a complex statement, which is symbolically indicated by the sign → ( A → IN) and reads: “if A, then B”, “A implies B”, “from A follows B”, “A implies B”. The sign ⊃ (A ⊃ B) is also used to denote implication. An example of an implication: “If the resulting quadrilateral is a square, then a circle can be described around it.” This operation connects two simple logical expressions, of which the first is a condition, and the second is a consequence. The result of an operation is false only when the premise is true and the consequence is false. For example, “If 3 * 3 = 9 (A), then the Sun is a planet (B),” the result of the implication A → B is false.

The truth table of the operation has the form

A	IN	A→IN
1	0	0
0	1	1
0	0	1
1	1	1

For the operation of implication, the statement is true that anything can follow from a lie, but only truth can follow from truth.

6. Equivalence, double implication, equivalence(lat. aequalis- equal and valentis- having force) - a logical operation that allows from two statements A And IN get a new expression A ≡ B which reads: "A is equivalent to B". The following signs are also used to indicate equivalence: ⇔, ∼. This operation can be expressed by connectives “then and only then”, “necessary and sufficient”, “equivalent”. An example of equivalence is the statement: “A triangle is right-angled if and only if one of the angles is 90 degrees.”

The truth table of the equivalence operation has the form

A	IN	A∼ IN
1	0	0
0	1	0
0	0	1
1	1	1

The equivalence operation is the opposite of addition modulo two and evaluates to true if and only if the values ​​of the variables are the same.

Knowing the meanings of simple statements, it is possible to determine the meanings of complex statements based on truth tables. It is important to know that to represent any function in the algebra of logic, three operations are sufficient: conjunction, disjunction and negation.

The priority of logical operations is as follows: negation ( "Not") has the highest priority, then the conjunction ( "And"), after the conjunction - disjunction ( "or").

With the help of logical variables and logical operations, any logical statement can be formalized, that is, replaced by a logical formula. In this case, the elementary statements that form a compound statement may be absolutely unrelated in meaning, but this does not interfere with determining the truth or falsity of the compound statement. For example, the statement “If five is greater than two ( A), then Tuesday always comes after Monday ( IN)" - implication A→ IN, and the result of the operation in this case is “true”. In logical operations, the meaning of statements is not taken into account, only their truth or falsity is considered.

Consider, for example, the construction of a compound statement from statements A And IN, which would be false if and only if both statements are true. In the truth table for the operation of addition modulo two we find: 1 ⊕ 1 = 0. And the statement could be, for example, like this: “This ball is completely red or completely blue.” Therefore, if the statement A"This ball is completely red" is a truth and a statement IN“This ball is completely blue” is true, then the compound statement is false, because the ball cannot be both red and blue at the same time.

Examples of problem solving

Example 1. For the specified values ​​of X, determine the value of the logical statement ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Solution. The sequence of operations is as follows: first the comparison operations in parentheses are performed, then the disjunction, and lastly the implication operation is performed. The disjunction operation ∨ is false if and only if both operands are false. The truth table for the implication looks like

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

From here we get:

1) for X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) for X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) for X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Example 2. Indicate the set of integer values ​​of X for which the expression ¬((X > 2) → (X > 5)) is true.

Solution. The negation operation is applied to the entire expression ((X > 2) → (X > 5)), therefore, when the expression ¬((X > 2) → (X > 5)) is true, the expression ((X > 2) →(X > 5)) is false. Therefore, it is necessary to determine for which values ​​of X the expression ((X > 2) → (X > 5)) is false. The operation of implication takes on the value “false” only in one case: when a lie follows from truth. And this is only true for X = 3; X = 4; X = 5.

Example 3. For which of the following words is the statement ¬(the first letter is a vowel ∧ the third letter a vowel) ⇔ a string of 4 characters false? 1) assa; 2) kuku; 3) corn; 4) error; 5) strongman.

Solution. Let's consider all the proposed words sequentially:

1) for the word assa we get: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 - the statement is true;

2) for the word kuku we get: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - the statement is true;

3) for the word corn we get: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - the statement is false;

4) for the word error we get: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - the statement is true;

5) for the word strongman we get: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - the statement is false.

Logical expressions and their transformation

Under logical expression should be understood as a record that can take the logical value “true” or “false”. With this definition, among logical expressions it is necessary to distinguish:

• expressions that use comparison operations (“greater than,” “less than,” “equal to,” “not equal to,” etc.) and take logical values ​​(for example, the expression a > b, where a = 5 and b = 7, equals the value "false");
• direct logical expressions associated with logical quantities and logical operations (for example, A ∨ B ∧ C, where A = true, B = false and C = true).

Boolean expressions can include functions, algebraic operations, comparison operations, and logical operations. In this case, the priority of actions is as follows:

1. calculation of existing functional dependencies;
2. performing algebraic operations (first multiplication and division, then subtraction and addition);
3. performing comparison operations (in random order);
4. performing logical operations (first the negation operations, then the operations of logical multiplication, logical addition, and lastly the operations of implication and equivalence are performed).

A Boolean expression can use parentheses, which change the order in which the operations are performed.

Example. Find the meaning of the expression:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ for a = 2, b = 3, A = true, B = false.

Solution. The order of counting values:

1) b a + a b > a + b, after substitution we get: 3 2 + 2 3 > 2 + 3, i.e. 17 > 2 + 3 = true;

2) A ∧ B = true ∧ false = false.

Therefore, the expression in parentheses is (b a + a b > a + b ∨ A ∧ B) = true ∨ false = true;

3) 1≤ a = 1 ≤ 2 = true;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

After these calculations we finally get: true ∨ A ∧ true ∧ ¬B ∧ ¬ true.

Now the operations of negation, then logical multiplication and addition must be performed:

5) ¬B = ¬false = true; ¬true = false;

6) A ∧ true ∧ true ∧ false = true ∧ true ∧ true ∧ false = false;

7) true ∨ false = true.

Thus, the result of a logical expression for given values ​​is “true”.

Note. Considering that the original expression is, ultimately, the sum of two terms, and the value of one of them is 1 ≤ a = 1 ≤ 2 = true, without further calculations we can say that the result for the entire expression is also “true”.

Identical transformations of logical expressions

In the algebra of logic, basic laws are followed that allow identical transformations of logical expressions.

Law	For ∨	For ∧
Traveling	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Conjunctive	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Distribution	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
De Morgan's rules	$(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$	$(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
Idempotency	A ∨ A = A	A ∧ A = A
Takeovers	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Bonding	(A ∧ B) ∨ (A↖(-) ∧ B) = B	(A ∨ B) ∧ (A↖(-) ∨ B) = B
Operation of a variable with its inversion	$A ∨ A↖(-)$ = 1	$A ∧ A↖(-)$ = 0
Operation with constants	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Double negative	$A↖(=)$ = A

Proofs of these statements are made based on the construction of truth tables for the corresponding records.

Equivalent transformations of logical formulas have the same purpose as transformations of formulas in ordinary algebra. They serve to simplify formulas or reduce them to a certain form by using the basic laws of logical algebra. Under simplifying the formula, which does not contain the operations of implication and equivalence, is understood as an equivalent transformation leading to a formula that contains either a smaller number of operations or a smaller number of variables compared to the original one.

Some transformations of logical formulas are similar to transformations of formulas in ordinary algebra (taking the common factor out of brackets, using commutative and combinational laws, etc.), while other transformations are based on properties that the operations of ordinary algebra do not have (using the distributive law for conjunction , laws of absorption, gluing, de Morgan, etc.).

Let's look at some examples of techniques and methods used to simplify logical formulas:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

To transform here, you can apply the law of idempotence, the distributive law; operation of a variable with inversion and operation with a constant.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

Here, for simplicity, the absorption law is applied.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

When transforming, the de Morgan rule, the operation of a variable with its inversion, and the operation with a constant are applied

Examples of problem solving

Example 1. Find a logical expression equivalent to the expression A ∧ ¬(¬B ∨ C) .

Solution. We apply de Morgan's rule for B and C: ¬(¬B ∨ C) = B ∧ ¬C.

We obtain an expression equivalent to the original one: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Answer: A ∧ B ∧ ¬C.

Example 2. Indicate the value of the logical variables A, B, C, for which the value of the logical expression (A ∨ B) → (B ∨ ¬C ∨ B) is false.

Solution. The operation of implication is false only if a false statement follows from a true premise. Therefore, for a given expression, the premise A ∨ B must be true, and the consequence, i.e., the expression B ∨ ¬C ∨ B, must be false.

1) A ∨ B — the result of the disjunction is “true” if at least one of the operands is “true”;

2) B ∨ ¬C ∨ B - the expression is false if all terms have the value “false”, i.e. B is “false”; ¬C is “false”, and therefore the variable C has the value “true”;

3) if we consider the premise and take into account that B is “false”, we obtain that the value of A is “true”.

Answer: A is true, B is false, C is true.

Example 3. What is the largest integer X for which the statement (35

Solution. Let's write down the truth table for the implication operation:

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Expression X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Answer: X = 5.

Using Boolean Expressions to Describe Geometric Regions

Logical expressions can be used to describe geometric regions. In this case, the task is formulated as follows: write down for a given geometric region a logical expression that takes the value “true” for the values ​​x, y if and only if any point with coordinates (x; y) belongs to the geometric region.

Let's consider the description of a geometric region using a logical expression using examples.

Example 1. An image of a geometric region is specified. Write a logical expression describing the set of points belonging to it.

1) .

Solution. A given geometric region can be represented as a set of the following regions: the first region - D1 - half-plane $(x)/(-1) +(y)/(1) ≤ 1$, the second - D2 - a circle with center at the origin $x ^2 + y^2 ≤ 1$. Their intersection D1 $∩$ D2 represents the desired region.

Result: logical expression $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

This area can be written as follows: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

Note. When constructing a logical expression, loose inequalities are used, which means that the boundaries of the figures also belong to the shaded area. If you use strict inequalities, then boundaries will not be taken into account. Boundaries that do not belong to the area are usually shown as dotted lines.

You can solve the inverse problem, namely: draw a region for a given logical expression.

Example 2. Draw and shade the area for which the logical condition y ≥ x ∧ y + x ≥ 0 ∧ y is satisfied< 2 .

Solution. The sought area is the intersection of three half-planes. We construct straight lines on the plane (x, y) y = x; y = -x; y = 2. These are the boundaries of the region, and the last boundary y = 2 does not belong to the region, so we draw it with a dotted line. To satisfy the inequality y ≥ x, the points must be to the left of the line y = x, and the inequality y = -x is satisfied for points that are to the right of the line y = -x. Condition y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Using Logic Functions to Describe Electrical Circuits

Logic functions are very useful for describing the operation of electrical circuits. So, for the circuit shown in Fig., where the value of the variable X is the state of the switch (if it is on, the value of X is “true”, and if it is off, the value is “false”), this value of Y is the state of the light bulb (if it is on - the value is “true”, and if not - “false”), the logical function will be written like this: Y = X. The function Y is called conductivity function.

For the circuit shown in Fig., the logical function Y has the form: Y = X1 ∪ X2, since one switch on is enough for the light bulb to light. In the circuit in Fig., in order for the light bulb to light, both switches must be turned on, therefore, the conductivity function has the form: Y = X1 ∧ X2.

For a more complex circuit, the conductivity function will have the form: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

The circuit may also contain short-circuit contacts. In this case, the open contact acts as a switch to ensure that the light bulb lights up when the button is released and not pressed. For such circuits, the disconnect switch is described by negation.

The two schemes are called equivalent, if a current passes through one of them then it also passes through the other. Of two equivalent circuits, the simpler circuit is the one whose conductivity function contains a smaller number of elements. The task of finding the simplest circuits among equivalent ones is very important.

Using the apparatus of logic algebra in the design of logic circuits

The mathematics of logical algebra is very useful for describing how computer hardware functions. When processed on a computer, any information is presented in binary form, that is, it is encoded by a certain sequence of 0s and 1s. The processing of binary signals corresponding to 0s and 1s is performed in the computer by logical elements. Logic gates that perform basic logical operations AND, OR, NOT, are presented in Fig.

Symbols for logical elements are standard and are used when drawing up logic circuits of a computer. Using these circuits, you can implement any logical function that describes the operation of a computer.

Technically, a computer logic element is implemented in the form of an electrical circuit, which is a connection of various parts: diodes, transistors, resistors, capacitors. The input of a logic element, which is also called a gate, receives electrical signals of high and low voltage levels, and one output signal is also issued at either a high or low level. These levels correspond to one of the states of the binary system: 1 - 0; TRUTH IS FALSE. Each logical element has its own symbol, which expresses its logical function, but does not indicate what kind of electronic circuit is implemented in it. This makes it easier to write and understand complex logic circuits. The operation of logic circuits is described using truth tables. The symbol in the OR diagram is the sign “1” - from the outdated designation of disjunction as “>=1” (the value of the disjunction is 1 if the sum of the two operands is greater than or equal to 1). The “&” sign in the AND diagram is an abbreviation for the English word and.

Electronic logic circuits are made from logical elements that perform more complex logical operations. A set of logical elements consisting of NOT, OR, AND elements, with the help of which you can build a logical structure of any complexity, is called functionally complete.

Construction of truth tables of logical expressions

For a logical formula you can always write truth table, i.e., present a given logical function in tabular form. In this case, the table should contain all possible combinations of function arguments (formulas) and the corresponding function values ​​(the results of the formula on a given set of values).

A convenient form of recording when finding the values ​​of a function is a table containing, in addition to the values ​​of variables and function values, also the values ​​of intermediate calculations. Let's consider an example of constructing a truth table for the formula $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

X1	X2	$(X1)↖(-)$	$(X1)↖(-)$ \ X2	X1 ∧ X2	$(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

If a function takes the value 1 for all sets of variable values, it is identically true; if for all sets of input values ​​the function takes the value 0, it is identically false; if the set of output values ​​contains both 0 and 1, the function is called feasible. The above example is an example of an identically true function.

Knowing the analytical form of a logical function, you can always go to the tabular form of logical functions. Using a given truth table, you can solve the inverse problem, namely: for a given table, construct an analytical formula for a logical function. There are two forms of constructing the analytical dependence of a logical function based on a table-specified function.

1. Disjunctive normal form (DNF)- the sum of products formed from variables and their negations for false values.

The algorithm for constructing a DNF is as follows:

1. in the truth table, functions select sets of arguments for which the logical forms are equal to 1 (“true”);
2. all selected logical sets are written down as logical products of arguments, sequentially connecting them to each other using the operation of logical sum (disjunction);
3. for arguments that are false, a negation operation is inserted in the constructed record.

Example. Construct a function that determines that the first number is equal to the second using the DNF method. The truth table of the function looks like

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Solution. We select sets of argument values ​​in which the function is equal to 1. These are the first and fourth rows of the table (we do not take into account the header row when numbering).

We write down the logical products of the arguments of these sets, combining them with a logical sum: X1 ∧ X2 ∨ X1 ∧ X2.

We write down the negation of the arguments of the selected sets that have a false value (the fourth row of the table; the second set in the formula; the first and second elements): X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Answer: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Conjunctive normal form (CNF)- the product of sums formed from variables and their negations for true values.

The algorithm for constructing CNF is as follows:

1. in the truth table, sets of arguments are selected for which the logical forms are equal to 0 (“false”);
2. all selected logical sets as logical sums of arguments are written sequentially, connecting them together using the operation of a logical product (conjunction);
3. for arguments that are true, a negation operation is entered in the constructed record.

Examples of problem solving

Example 1. Let's consider the previous example, i.e., construct a function that determines that the first number is equal to the second, using the CNF method. For a given function, its truth table has the form

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Solution. We select sets of argument values ​​in which the function is equal to 0. These are the second and third lines (we do not take into account the header line when numbering).

We write down the logical sums of the arguments of these sets, combining them with a logical product: X1 ∨ X2 ∧ X1 ∨ X2.

We write down the negation of the arguments of the selected sets that have a true value (the second row of the table, the first set of the formula, the second element; for the third line, and this is the second set of the formula, the first element): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Thus, a record of the logical function in CNF has been obtained.

Answer: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

The function values ​​obtained by the two methods are equivalent. To prove this statement, we use the rules of logic: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖(-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2)↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Example 2. Construct a logical function for a given truth table:

The required formula: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

It can be simplified: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

Example 3. For the given truth table, construct a logical function using the DNF method.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1		X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1		$(X1)↖(-)$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $(X3)↖(-)$
1	0	0	1		X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
0	1	0	0
0	0	0	0

The required formula: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-)$ ∧ $ (X3)↖(-)$.

The formula is quite cumbersome and should be simplified:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ $(X3) ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Truth tables for solving logical problems

Compiling truth tables is one of the ways to solve logical problems. When using this method of solution, the conditions that the problem contains are recorded using specially compiled tables.

Examples of problem solving

Example 1. Construct a truth table for a security device that uses three sensors and is triggered when only two of them are shorted.

Solution. Obviously, the result of the solution will be a table in which the desired function Y(X1, X2, X3) will have the value “true” if any two variables have the value “true”.

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Example 2. Make a lesson schedule for the day, taking into account that a computer science lesson can only be the first or second, a mathematics lesson - the first or third, and a physics lesson - the second or third. Is it possible to create a schedule that meets all the requirements? How many scheduling options are there?

Solution. The problem can be easily solved if you create the appropriate table:

	1st lesson	Lesson 2	Lesson 3
Computer science	1	1	0
Mathematics	1	0	1
Physics	0	1	1

The table shows that there are two options for the desired schedule:

1. mathematics, computer science, physics;
2. computer science, physics, mathematics.

Example 3. Three friends came to the sports camp - Peter, Boris and Alexey. Each of them is fond of two sports. It is known that there are six such sports: football, hockey, skiing, swimming, tennis, badminton. It is also known that:

1. Boris is the eldest;
2. a football player younger than a hockey player;
3. playing football and hockey and Peter live in the same house;
4. when a quarrel arises between a skier and a tennis player, Boris reconciles them;
5. Peter can't play tennis or badminton.

What sports does each boy enjoy?

Solution. Let's draw up a table and reflect the conditions of the problem in it, filling in the corresponding cells with the numbers 0 and 1, depending on whether the corresponding statement is false or true.

Since there are six types of sports, it turns out that all the boys are interested in different sports.

From condition 4 it follows that Boris is not interested in skiing or tennis, and from conditions 3 and 5 that Peter does not know how to play football, hockey, tennis and badminton. Consequently, Peter’s favorite sports are skiing and swimming. Let’s put this in the table, and fill the remaining cells of the “Skiing” and “Swimming” columns with zeros.

The table shows that only Alexey can play tennis.

From conditions 1 and 2 it follows that Boris is not a football player. Thus, Alexey plays football. Let's continue filling out the table. Let's enter zeros into the empty cells of the line “Alexey”.

We finally get that Boris is interested in hockey and badminton. The final table will look like this:

Answer: Peter enjoys skiing and swimming, Boris plays hockey and badminton, and Alexey plays football and tennis.

Logical expressions. Each compound statement can be expressed in the form of a formula (logical expression), which includes logical variables, denoting statements, and signs of logical operations, denoting logical functions.

To write a compound statement in the form of a logical expression in a formal language (the language of algebra of logic), in a compound statement it is necessary to identify simple statements and logical connections between them.

Let us write in the form of a logical expression the compound statement “(2 - 2 = 5 or 2-2 = 4) and (2 2 ≠ 5 or 2-2 ≠ 4)". Let's analyze the compound statement. It contains two simple statements:

A =“2 2 = 5” - false (0),

B = “2 2 = 4 >> - true (1).

Then the compound statement can be written in the following form:

"(A or IN) And (⌐A or (⌐ IN)".

Now you need to write the statement in the form of a logical expression, taking into account the sequence of logical operations. When performing logical operations, the following order of their execution is defined: inversion, conjunction, disjunction. Parentheses can be used to change the specified order:

F = (A v IN) & (⌐ A v ⌐ IN).

The truth or falsity of compound statements can be determined purely formally, guided by the laws of propositional algebra, without referring to the semantic content of the statements.

Let us substitute the values ​​of logical variables into the logical expression and, using the truth tables of basic logical operations, we obtain the value of the logical function:

F = (AvB)&(⌐ Av⌐ B) = (0v1)&(1v0) = 1 & 1 = 1 .

Truth tables. For each compound statement (logical expression), it is possible to construct a truth table that determines its truth or falsity for all possible combinations of the initial values ​​of simple statements (logical variables).

When constructing truth tables, it is advisable to be guided by a certain sequence of actions.

First, you need to determine the number of rows in the truth table. It is equal to the number of possible combinations of logical variable values ​​included in a logical expression. If the number of logical variables is equal n, That:

number of lines = 2 n .

In our case, the logical function F = (AvB)&(⌐ Av⌐ B) has 2 variables and therefore the number of rows in the truth table must be 4.

Secondly, it is necessary to determine the number of columns in the truth table, which is equal to the number of logical variables plus the number of logical operations.

In our case, the number of variables is two, and the number of logical operations is five, that is, the number of columns of the truth table is seven.

Thirdly, it is necessary to construct a truth table with the specified number of rows and columns, designate the columns and enter into the table possible sets of values ​​of the original logical variables.

Fourthly, it is necessary to fill out the truth table by column, performing basic logical operations in the required sequence and in accordance with their truth tables (Table 4.4). We can now determine the value of a Boolean function for any set of Boolean variable values.

Table 4.4. Logic function truth table

F=(AvB)&(⌐ Av⌐ B)

						(AvB)&(⌐Av⌐B)

Equivalent logical expressions. Logical expressions for which the last columns of the truth tables coincide are called equivalent. To denote equivalent logical expressions, the “=” sign is used.

Let us prove that logical expressions ⌐A &⌐B And ⌐(AvB) are equivalent. Let's first build a truth table for the logical expression ⌐A &⌐B(Table 4.5).

Table 4.5. Logical Expression Truth Table ⌐A& ⌐B

				⌐A&⌐ IN

Now let's build a truth table for a logical expression ⌐(AvB) (Table 4.6).

Table 4.6. Logical Expression Truth Table ⌐(AvB)

			⌐(AvB)

The values ​​in the last columns of the truth tables are the same, therefore, the logical expressions are equivalent:

⌐A & ⌐B = ⌐(AvB).

Basic logical operations

Negation (inversion), from the Latin inversio - I turn over:

Corresponds to the particle NOT, the phrase NOT TRUE THAT;

Designation: not A, A, -A;

truth table:

The inverse of a Boolean variable is true if the variable itself is false, and conversely, the inverse is false if the variable is true.

Example: A = (It's snowing outside).

A=(It is not true that it is snowing outside)

A=(It's not snowing outside);

Logical addition (disjunction), from the Latin disjunctio - I distinguish:

Corresponds to the union OR;

Designation: +, or, or, V;

Truth table:

A disjunction is false if and only if both statements are false.

Example: F=(The sun is shining outside or there is a strong wind blowing);

Logical multiplication (conjunction), from the Latin conjunctio - I connect:

Corresponds to the conjunction AND

(in natural language: both A and B, both A and B, A together with B, A, despite B, A, while B);

Designation: H, , &, u, ^, and;

Truth table:

A conjunction is true if and only if both statements are true.

Example: F=(The sun is shining outside and a strong wind is blowing);

Any complex statement can be written using the basic logical operations AND, OR, NOT. Using logical circuits AND, OR, NOT, you can implement a logical function that describes the operation of various computer devices.

2) A truth table is a table that describes a logical function.

In this case, a “logical function” is understood as a function in which the values ​​of the variables (function parameters) and the value of the function itself express logical truth. For example, in two-valued logic they can take the values ​​“true” or “false” (either or).

Tabular assignment of functions is found not only in logic, but for logical functions tables turned out to be especially convenient, and since the beginning of the 20th century this special name has been assigned to them. Truth tables are especially often used in Boolean algebra and in similar systems of many-valued logic.

Conjunction is a logical operation, in its application as close as possible to the union “and”. Logical multiplication, sometimes simply “AND”.

Disjunction is a logical operation, in its application as close as possible to the conjunction “or” in the sense of “either this, or that, or both at once.” logical addition, sometimes just “OR”.

Implication is a binary logical connective, in its application close to the conjunctions “if... then...” The implication is written as a premise and consequence; arrows of a different shape and directed in a different direction are also used (the point always points to the consequence).

Equivalence (or equivalence) is a two-place logical operation. Usually indicated by the symbol ≡ or ↔.

7. Logical expressions, truth tables of logical expressions.

A logical expression is a record or oral statement that, along with constants, necessarily includes variable quantities (objects). Depending on the values ​​of these variables, a logical expression can take one of two possible values: TRUE (logical 1) or FALSE (logical 0)

A complex logical expression is a logical expression composed of one or more simple (or complex) logical expressions connected using logical operations.

Logical operations and truth tables

Logical multiplication CONJUNCTION - this new complex expression will be true only if both original simple expressions are true. A conjunction defines the connection of two logical expressions using the conjunction AND.

Logical addition - DISUNCTION - this new complex expression will be true if and only if at least one of the original (simple) expressions is true. Disjunction defines the connection of two logical expressions using the conjunction OR

Logical negation: INVERSION - if the original expression is true, then the result of the negation will be false, and vice versa, if the original expression is false, then the result of the negation will be true/ This operation means that the NOT particle or the word FALSE is added to the original logical expression.

Logical implication: IMPLICATION - connects two simple logical expressions, of which the first is condition (A), and the second (B) is a consequence of this condition. The result of IMPLICATION is FALSE only when condition A is true and consequence B is false. It is denoted by the symbol “therefore” and expressed by the words IF…, THEN…

Logical equivalence: EQUIVALENCE - determines the result of comparing two simple logical expressions A and B. The result of EQUIVALENCE is a new logical expression that will be true if and only if both original expressions are simultaneously true or false. Indicated by the "equivalence" symbol

The order of logical operations in a complex logical expression:

1. inversion

2. conjunction

3. disjunction

4. implication

5. equivalence

Parentheses are used to change the specified order of operations.

Construction of truth tables for complex expressions:

Number of lines = 2n + two lines for the title (n is the number of simple statements)

Number of columns = number of variables + number of logical operations

When constructing a table, it is necessary to take into account all possible combinations of the logical values ​​0 and 1 of the original expressions. Then - determine the order of actions and draw up a table taking into account the truth tables of basic logical operations.

EXAMPLE: create a truth table for a complex logical expression D = notA & (B+C)

A, B, C are three simple statements, therefore:

number of lines = 23 +2 = 10 (n=3, because there are three input elements A, B, C)

number of columns: 1) A

4) not A is the inversion of A (denoted by E)

5) B + C is the disjunction operation (denoted by F)

6) D = not A & (B+C), i.e. D = E & F is the conjunction operation

A B C E = not A (not 1) F = B+C (2+3) D = E&F (4*5)

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, the output function of each element in the previous tier is recorded and 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”, “AND-NOT”, “OR-NOT”, “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 involving 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 task of synthesizing logical circuits and the task of analyzing logical circuits. 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 :

x	y	z					f
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

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:

x	y	z			f
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

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:

x	y	z			f
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

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.