Table of values ​​of logical operations. The problem of synthesizing logic circuits in a Boolean basis

Select the lines where
and write down the conjunctions of all variables, whereby, if a variable in this set is equal to 1, then we write it itself, and if the variable = 0, then its negation.

For this example

the conjunction of these disjunctions will be the desired formula:

Definition: Conjunction called elementary, if all the variables included in it are different. The number of letters included in an elementary conjunction or elementary disjunction is called rank.

The number 1 is considered an elementary conjunction of rank 0. A variable is considered an elementary conjunction or an elementary disjunction of rank 1. The number 0 is considered an elementary disjunction of rank 0. Any conjunction of variables that is not identically false can be reduced to an elementary form, and any disjunction of letters that is not identically true , can also be reduced to elementary form. To do this, we need to apply the properties of commutativity, idempotency and associativity of conjunction and disjunction.

It has been rigorously proven that any Boolean algebra formula can be expressed using the operations , &, . Intuitively, this fact is obvious; let us recall the algorithm for composing a formula using a truth table. In this case, we use only these operations. This form of recording is called disjunctive normal form(DNF). This is a kind of mechanism for normalizing logic algebra formulas.

Definition: DNF is a disjunction of various elementary conjunctions (i.e., each conjunction consists of elementary statements or their negations).

CNF is defined similarly - conjunctive normal form.

Definition: If in a DNF all elementary conjunctions have the same rank, equal to the number of variables on which the DNF depends, then it is called perfect (SDNF).

Theorem. For any function that is not identically false, there exists a unique SDNF.

Consequence . Any Boolean function that is not identically false can be represented as a superposition &,,, and the negation applies only to variables.

Definition: A system of logical operations is called functionally complete if, using these operations and constants of this system, any function of Boolean algebra can be represented.

Systems (&,,); (,); (&,),(/) – are functionally complete

(&,) – functionally incomplete.

We will accept these facts without proof, and when solving problems, we will try to represent any formula using (&,,). Later we will discuss in more detail the issue of functional completeness and incompleteness of the system of operations.

Topic 1.7. Methods for simplifying logical expressions. Methods for solving logical problems.

Let's consider an example of solving a logical problem.

Example :

After discussing the composition of the expedition participants, it was decided that two conditions must be met.

If Arbuzov goes, then Bryukvin or Vishnevsky should go

If Arbuzov and Vishnevsky go, then Bryukvin will go

Draw up a logical formula for decision-making in symbolic form, simplify the resulting formula and formulate a new condition for forming an expedition based on it.

Let us introduce variables and the corresponding elementary statements.

- Arbuzov will go

- Bryukvin will go

- Vishnevsky will go

Then the developed conditions for the formation of the expedition will look like this:

Let's create a general formula and simplify the expression

those. if Arbuzov goes, then Bryukvin will go.

Example:

If the weather is good tomorrow, we will go to the beach or go to the forest. Let's create a formula for our behavior for tomorrow.

– good weather

- we'll go to the beach

- we'll go to the forest

Now let's construct the negation of this phrase

That. we will receive the statement “Tomorrow the weather will be good, and we will not go to the forest or to the beach.

Anyone can build a truth table and check this statement.

Example :

Brown, John and Smith were detained on suspicion of the crime. One of them is a respected old man in the city, the second is an official, and the third is a well-known swindler. During the investigation, the old man told the truth, the fraudster lied, and the third detainee told the truth in one case and lied in the other.

Here's what they said:

Brown: I did it. It's not John's fault. (B&D)

John: It's not Brown's fault. Criminal Smith. (B&S)

Smith: It's not my fault. Blame Brown (S&B)

Let us describe these statements formally:

Brown committed the crime

John committed the crime

- Smith committed the crime

Then their words are described by the following expressions:

Brown:

John:

Smith:

Because according to the conditions of the problem, two of these are false and one is true, then

Let's create a truth table

Only case 2 remains, i.e. criminal Smith, and both of his statements are false.

hence - false and - true

= 1 – John is a respected old man

It remains that Brown is an official, and since - false, then – true.

Using the laws and identities of Boolean algebra, you can simplify logical expressions.

Example :

Exercise:

Construction of truth tables and logical functions

Logic function is a function in which variables take only two values: logical one or logical zero. The truth or falsity of complex propositions is a function of the truth or falsity of simple ones. This function is called the Boolean judgment function f(a, b).

Any logical function can be specified using a truth table, on the left side of which a set of arguments is written, and on the right side - the corresponding values ​​of the logical function. When constructing a truth table, it is necessary to take into account the order in which logical operations are performed.

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.

Algorithm for constructing truth tables for complex expressions :

number of lines = 2 n + line for title ,

n is the number of simple statements.

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

· determine the number of variables (simple expressions);

· determine the number of logical operations and the sequence of their execution.

3. Fill in the columns with the results of performing logical operations in the designated sequence, taking into account the truth tables of basic logical operations.

Example: Create a truth table for a logical expression:

D= A & (BVC)

Solution:

1. Determine the number of lines:

There are three simple statements at the input: A, B, C, therefore n = 3 and the number of lines = 23 +1 = 9.

2. Determine the number of columns:

simple expressions (variables): A, B, C;

intermediate results (logical operations):

A- inversion (denoted by E);

BVC- disjunction operation (denoted by F);

as well as the desired final value of the arithmetic expression:

D= A & (BVC) . i.e. D = E & F is a conjunction operation.

Fill in the columns taking into account the truth tables of logical operations.

font-size:12.0pt">Construction of a logical function using its truth table:

Let's try to solve the inverse problem. Let a truth table be given for some logical function Z (X,Y):

font-size:12.0pt">1 .

Since there are two lines, we get the disjunction of two elements: () V () .

We write each logical element in this disjunction as a conjunction of function arguments X and Y: ( X & Y) V ( X & Y).

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”, truth values ​​such 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.

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 connecting 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

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

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

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

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

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 conversion

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 that change the order of operations.

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.

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 premise 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:

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 the points of 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 considered to be 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 function values ​​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$.

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 entered 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

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

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.

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”.

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:

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.

Definition 1

Logic function– a function whose variables take one of two values: $1$ or $0$.

Any logical function can be specified using a truth table: the set of all possible arguments is written on the left side of the table, and the corresponding values ​​of the logical function are written on the right side.

Definition 2

Truth table– a table that shows what values ​​a compound expression will take for all possible sets of values ​​of the simple expressions included in it.

Definition 3

Equivalent are called logical expressions whose last columns of truth tables coincide. Equivalence is indicated using the $«=»$ sign.

When compiling a truth table, it is important to consider the following order of logical operations:

Figure 1.

Parentheses take precedence in executing the order of operations.

Algorithm for constructing a truth table of a logical function

Determine the number of lines: number of lines= $2^n + 1$ (for title line), $n$ – number of simple expressions. For example, for functions of two variables there are $2^2 = 4$ combinations of sets of variable values, for functions of three variables there are $2^3 = 8$, etc.

Determine the number of columns: number of columns = number of variables + number of logical operations. When determining the number of logical operations, the order of their execution is also taken into account.

Fill columns with the results of logical operations in a certain sequence, taking into account the truth tables of basic logical operations.

Figure 2.

Example 1

Create a truth table for the logical expression $D=\bar(A) \vee (B \vee C)$.

Solution:

Let's determine the number of lines:

number of lines = $2^3 + 1=9$.

Number of variables – $3$.

1. inverse ($\bar(A)$);
2. disjunction, because it is in parentheses ($B \vee C$);

3. disjunction ($\overline(A)\vee \left(B\vee C\right)$) is the required logical expression.

   Number of columns = $3 + 3=6$.

Let's fill in the table, taking into account the truth tables of logical operations.

Figure 3.

Example 2

Using this logical expression, construct a truth table:

Solution:

Let's determine the number of lines:

The number of simple expressions is $n=3$, which means

number of lines = $2^3 + 1=9$.

Let's determine the number of columns:

Number of variables – $3$.

Number of logical operations and their sequence:

1. negation ($\bar(C)$);
2. disjunction, because it is in parentheses ($A \vee B$);
3. conjunction ($(A\vee B)\bigwedge \overline(C)$);
4. negation, which we denote by $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$);
5. disjunction ($A \vee C$);
6. conjunction ($(A\vee C)\bigwedge B$);
7. negation, which we denote by $F_2$ ($\overline((A\vee C)\bigwedge B)$);

8. disjunction is the desired logical function ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

We learn to compose logical expressions from statements, define the concept of “truth table”, study the sequence of actions for constructing truth tables, learn to find the meaning of logical expressions by constructing truth tables.

Lesson objectives:

1. Educational:
   1. Learn to form logical expressions from statements
   2. Introduce the concept of “truth table”
   3. Study the sequence of actions for constructing truth tables
   4. Learn to find the meaning of logical expressions by constructing truth tables
   5. Introduce the concept of equivalence of logical expressions
   6. Learn to prove the equivalence of logical expressions using truth tables
   7. Strengthen the skills of finding the values ​​of logical expressions by constructing truth tables
2. Educational:
   1. Develop logical thinking
   2. Develop attention
   3. Develop memory
   4. Develop students' speech
3. Educational:
   1. Develop the ability to listen to teachers and classmates
   2. Cultivate accuracy in notebook keeping
   3. Cultivate discipline

Lesson progress

Organizational moment

Hello guys. We continue to study the basics of logic and the topic of our lesson today is “Composing logical expressions. Truth tables." After studying this topic, you will learn how logical forms are made from statements and how to determine their truth by compiling truth tables.

Checking homework

Write down solutions to homework problems on the board
Everyone else, open your notebooks, I’ll go by and check how you did your homework.
Let's do the logical operations again
In what case will the compound statement be true as a result of the logical multiplication operation?
A compound statement formed as a result of the operation of logical multiplication is true if and only if all the simple statements included in it are true.
In what case will the compound statement be false as a result of the logical addition operation?
A compound statement formed as a result of the operation of logical addition is false if all simple statements included in it are false.
How does inversion affect a statement?
Inversion makes a true statement false and, conversely, a false statement true.
What can you say about implication?
Logical consequence (implication) is formed by combining two statements into one using the figure of speech “if..., then...”.
Designated A-> IN
A compound statement formed using the operation of logical consequence (implication) is false if and only if a false conclusion (second statement) follows from a true premise (the first statement).
What can you say about the logical equivalence operation?
Logical equality (equivalence) is formed by combining two statements into one using the figure of speech “... if and only if...”, “... in that and only in that case...”
A compound statement formed by the logical operation of equivalence is true if and only if both statements are simultaneously either false or true.

Explanation of new material

Okay, we’ve reviewed the material covered, let’s move on to a new topic.

In the last lesson, we found the value of a compound statement by substituting the original values ​​of the incoming logical variables. And today we will learn that it is possible to construct a truth table that determines the truth or falsity of a logical expression for all possible combinations of the initial values ​​of simple statements (logical variables) and that we can determine the values ​​of the original logical variables, knowing what result we need.

Let's look again at our example from the last lesson.

and build a truth table for this compound statement

When constructing truth tables, there is a certain sequence of actions. Let's write it down

1. It is necessary to determine the number of rows in the truth table.

• number of lines = 2 n, where n is the number of logical variables

Recorded. Building a truth table
What do we do first?
Determine the number of columns in a table
How do we do this?
We count the number of variables. In our case, the logical function contains 2 variables
Which?
A and B
So how many rows will there be in the table?
The number of rows in the truth table must be 4.
What if there are 3 variables?
Number of lines = 2³ = 8
Right. What do we do next?
We determine the number of columns = the number of logical variables plus the number of logical operations.
How much will it be in our case?
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.
Fine. Further?
We build a 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 and fill out the truth table by columns.
Which operation will we perform first? Just be mindful of parentheses and priorities
You can do the logical negation first, or find the value in the first bracket first, then the inverse and the value in the second bracket, then the value between those brackets

Now we can determine the value of a logical function for any set of logical variable values
Now write down the item “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 the logical expressions ┐ A& ┐ B and AvB are equivalent. Let's first build a truth table for a logical expression

How many columns will there be in the table? 5
Which operation will we perform first? Inversion A, inversion B

Now let's build a truth table for the logical expression AvB
How many rows will there be in the table? 4
How many columns will there be in the table? 4

We all understand that if you need to find a negation for an entire expression, then priority, in our case, belongs to the disjunction. Therefore, we first perform the disjunction and then the inversion. In addition, we can rewrite our Boolean expression AvB. Because we need to find the negation of the entire expression, and not individual variables, then the inversion can be taken out of brackets ┐(AvB), and we know that we first find the value in brackets

We built tables. Now let's compare the values ​​in the last columns of the truth tables, because It is the last columns that are the resulting ones. They coincide, therefore, the logical expressions are equivalent and we can put the “=” sign between them

Problem solving

1.

How many variables does this formula contain? 3
How many rows and columns will there be in the table? 8 and 8
What will be the sequence of operations in our example? (inversion, operations in brackets, operation outside brackets)

2. Using truth tables, prove the equivalence of the following logical expressions:

(A → B) AND (Av┐B)

What conclusion do we draw? These logical expressions are not equivalent

Homework

Prove using truth tables that logical expressions

┐A v ┐B and A&B are equivalent

Explanation of new material (continued)

We have been using the concept of “truth table” for several lessons in a row, and what is a truth table, How do you think?
A truth table is a table that establishes a correspondence between possible sets of values ​​of logical variables and function values.
How did you do your homework, what was your conclusion?
The expressions are equivalent
Remember, in the previous lesson we made a formula from a compound statement, replacing simple statements 2*2=4 and 2*2=5 with variables A and B
Now let's learn how to form logical expressions from statements

Write down the task

Write the following statements in the form of a logical formula:

1) If Ivanov is healthy and rich, then he is healthy

Let's analyze the statement. Identifying simple statements

A – Ivanov is healthy
B – Ivanov is rich

Okay, then what would the formula look like? Just do not forget, so as not to lose the meaning of the statement, place parentheses in the formula

2) A number is prime if it is divisible only by 1 and itself

A - the number is divisible only by 1
B - the number is divisible only by itself
C - the number is prime

3) If a number is divisible by 4, it is divisible by 2

A - divisible by 4
B - divisible by 2

4) An arbitrary number is either divisible by 2 or divisible by 3

A - divisible by 2
B - divisible by 3

5) An athlete is subject to disqualification if he behaves incorrectly towards an opponent or a judge, and if he has taken “doping”.

A - the athlete is subject to disqualification
B - behaves incorrectly towards an opponent
C - behaves incorrectly towards the judge
D - took “doping”.

Problem solving

1. Construct a truth table for the formula

((p&q)→ (p→ r)) v p

Let's explain how many rows and columns there will be in the table? (8 and 7) What will be the sequence of operations and why?

We looked at the last column and concluded that for any set of input parameters the formula takes on a true value; such a formula is called a tautology. Let's write down the definition:

A formula is called a law of logic, or a tautology, if it takes on the identical value “true” for any set of values ​​of the variables included in this formula.
And if all the values ​​are false, what do you think can be said about such a formula?
We can say that the formula is impossible

2. Write the following statements in the form of a logical formula:

The seaport administration issued the following order:

1. If the captain of a ship receives special instructions, he must leave the port on his ship
2. If the master does not receive special instructions, he must not leave the port, or he will henceforth lose access to that port
3. The captain is either deprived of access to this port or does not receive special instructions

We identify simple statements and create formulas

• A - the captain receives special instructions
• B - leaves the port
• C - deprived of access to the port

1. ┐A→(┐B v C)
2. C v ┐A

3. Write down the compound statement “(2*2=4 and 3*3 = 9) or (2*2≠4 and 3*3≠9)” in the form of a logical expression. Construct a truth table.

A=(2*2=4) B=(3*3 = 9)

(A&B) v (┐A&┐B)

Homework

Choose a compound statement that has the same truth table as not (not A and not (B and C)).

1. A&B or C&A;
2. (A or B) and (A or C);
3. A and (B or C);
4. A or (not B or C).