Truth tables for logical operations how to solve. Identical conversions of logical expressions

Today we will talk about a subject called computer science. Truth table, types of functions, the order of their execution - these are our main questions, to which we will try to find answers in the article.

Usually this course is taught in high school, but the large number of students is the reason for a lack of understanding of some of the features. And if you are going to devote your life to this, then you simply cannot do without passing the unified state exam in computer science. Truth table, transformation of complex expressions, solving logical problems - all this can be found in the ticket. Now we will take a closer look at this topic and help you get more points on the exam.

The subject of logic

What is this subject - computer science? Truth table - how to build it? Why is the science of logic needed? We will now answer all these questions.

Computer science is a pretty fascinating subject. It cannot cause difficulties in modern society, because everything that surrounds us, in one way or another, refers to a computer.

The basics of the science of logic are taught by high school teachers in computer science lessons. Truth tables, functions, simplification of expressions - all this should be explained by the teacher of computer science. This science is simply necessary in our life. Take a closer look, everything obeys some laws. You threw the ball, it flew up, but then fell back to the ground, this happened due to the presence of the laws of physics and the force of gravity. Mom makes soup and adds salt. Why don't we get grains when we eat it? It's simple, the salt is dissolved in water, obeying the laws of chemistry.

Now pay attention to how you speak.

• "If I take my cat to the veterinary clinic, he will be vaccinated."
• "Today was a very difficult day because the check came."
• “I don’t want to go to university because today there will be a colloquium,” and so on.

Everything you say is bound to obey the laws of logic. This applies to both business and friendly conversation. It is for this reason that it is necessary to understand the laws of logic in order not to act at random, but to be sure of the outcome of events.

Functions

In order to compile a truth table for the problem proposed to you, you need to know logical functions. What it is? A logical function has some variables that are statements (true or false), and the value of the function itself should give us the answer to the question: "Is the expression true or false?"

All expressions take the following values:

• True or False.
• And or L.
• 1 or 0.
• Plus or minus.

Here, give preference to the method that is more convenient for you. In order to compose a truth table, we need to list all the combinations of variables. Their number is calculated by the formula: 2 to the power of n. The result of the calculation is the number of possible combinations, the variable n in this formula denotes the number of variables in the condition. If the expression has many variables, then you can use a calculator or make a small table for yourself with the raising of two to a power.

In total, seven functions or connections are distinguished in logic that connect expressions:

• Multiplication (conjunction).
• Addition (disjunction).
• Corollary (implication).
• Equivalence.
• Inversion.
• Schaeffer's stroke.
• Pierce's arrow.

The first operation in the list is called "logical multiplication". It can be marked graphically with an inverted check mark, & or *. The second operation in our list is logical addition, graphically indicated as a check mark, +. An implication is called a logical consequence, it is indicated as an arrow pointing from a condition to a consequence. Equivalence is indicated by a double-headed arrow, the function has a true value only in those cases when both values ​​take either the value "1" or "0". Inversion is called logical negation. Schaeffer's stroke is called a function that negates conjunction, and Peirce's arrow is called a function that negates disjunction.

Basic binary functions

The logical truth table helps to find the answer in the problem, but for this you need to remember the tables of binary functions. They will be provided in this section.

Conjunction (multiplication). If there are two, then as a result we get the truth, in all other cases we get a lie.

The result is false with logical addition, we have only in the case of two false inputs.

A logical consequence has a false result only when the condition is true and the effect is false. Here you can give an example from life: “I wanted to buy sugar, but the store was closed”, therefore, sugar was never bought.

Equivalence is true only in cases where the input data values ​​are the same. That is, with pairs: "0; 0" or "1; 1".

In the case of inversion, everything is elementary, if there is a true expression at the input, then it is converted to false, and vice versa. The picture shows how it is indicated graphically.

The Schiffer stroke will produce a false result only if there are two true expressions.

In the case of Pierce's arrow, the function will be true only if we have only false expressions as input.

In what order to perform logical operations

Please note that building truth tables and simplifying expressions is only possible if the order of operations is correct. Remember in what sequence they need to be carried out, this is very important for obtaining the correct result.

• logical negation;
• multiplication;
• addition;
• consequence;
• equivalence;
• negation of multiplication (Schaeffer's stroke);
• negation of addition (Pierce's arrow).

Example # 1

Now we propose to consider an example of constructing a truth table for 4 variables. It is necessary to find out in what cases F = 0 for the equation: notA + B + C * D

The answer to this task will be to enumerate the following combinations: "1; 0; 0; 0", "1; 0; 0; 1" and "1; 0; 1; 0". As you can see, making a truth table is pretty simple. Once again, I would like to draw your attention to the order of actions. In a specific case, it was as follows:

1. Inversion of the first simple expression.
2. The conjunction of the third and fourth expressions.
3. Disjunction of the second expression with the results of previous calculations.

Example No. 2

Now we will consider another task that requires building a truth table. Computer science (examples were taken from the school course) can also have as an assignment. Let's take a quick look at one of them. Is Vanya guilty of stealing the ball if the following is known:

• If Vanya did not steal or Petya did steal, then Seryozha took part in the theft.
• If Vanya is not guilty, then Seryozha did not steal the ball either.

Let's introduce designations: I - Vanya stole the ball; P - Petya stole; S - Seryozha stole.

According to this condition, we can compose the equation: F = ((non-I + P) implication C) * (non-I implication not C). We need those options where the function takes on a true value. Next, you need to create a table, since this function has as many as 7 actions, we will omit them. We will only enter the input data and the result.

Note that in this problem we used plus and minus instead of the signs "0" and "1". This is also acceptable. We are interested in combinations where F = +. After analyzing them, we can draw the following conclusion: Vanya participated in the theft of the ball, since in all cases where F takes the value +, And has a positive value.

Example No. 3

Now we suggest that you find the number of combinations when F = 1. The equation has the following form: F = notA + B * A + notB. We compose a truth table:

Answer: 4 combinations.

Basic logical operations

Negation (inversion), from the Latin inversio - inverting:

Corresponds to the particle NOT, the phrase is WRONG WHAT;

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 is not snowing outside);

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

Matches union OR;

Designation: +, or, or, V;

Truth table:

Disjunction is false if and only if both statements are false.

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

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

Matches union AND

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

Designation: Ч,, &, and, ^, 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. With the help of logical circuits AND, OR, it is NOT possible to implement a logical function that describes the operation of various computer devices.

2) Truth table is a table describing a logical function.

In this case, a "logical function" means 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 on the values ​​"true" or "false" (either, or).

The tabular definition of functions is found not only in logic, but tables turned out to be especially convenient for logical functions, and from the beginning of the 20th century this special name was assigned to them. Truth tables are especially often used in Boolean algebra and in similar multi-valued logic systems.

A conjunction is a logical operation, which in its application is as close as possible to the conjunction "and". Logical multiplication, sometimes just "AND".

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

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

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 a verbal statement, which, along with constants, necessarily includes variable quantities (objects). Depending on the values ​​of these variables, the 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 associated with logical operations.

Logic operations and truth tables

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

Logical addition - DISJUNCTION - 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 OR conjunction

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, the result of the negation will be true / This operation means that the particle NOT or the word WRONG is added to the original logical expression, WHAT

Logical inference: IMPLICATION - connects two simple logical expressions, of which the first is a condition (A), and the second (B) is a consequence of this condition. The result of the IMPLICATION is FALSE only if condition A is true and consequence B is false. It is designated 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 symbol "equivalence"

The order of performing 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.

Building 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 - to determine the order of actions and draw up a table, taking into account the truth tables of the main logical operations.

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

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

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

number of columns: 1) A

4) not A is the inverse of A (denote by E)

5) B + C is a disjunction operation (denote F)

6) D = notA & (B + C), i.e. D = E & F is a conjunction operation

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

Algebra of logic

Algebra of logic

Algebra of logic(eng. algebra of logic) - one of the main sections of mathematical logic, in which the methods of algebra 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 proved 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 true and false in different proportions.

Logical statement Is any declarative sentence in respect of which it can be unambiguously asserted that its content is true or false.

For example, “3 times 3 equals 9”, “Arkhangelsk north of Vologda” are true statements, and “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 10-A grade student A. A. Ivanov, computer science is an interesting subject," depending on A. A. Ivanov's interests, can take on the meaning of "truth" or "Lying".

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 meanings "true" and "false", such truth values ​​as "probably", "possible", "impossible", etc. are used.

In algebra, logics differ simple(elementary) utterances, denoted by Latin letters (A, B, C, D, ...), and complex(composite), composed of several simple ones using logical connectives, for example, such as "Not", "and", "or", "then 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 us denote as A the statement "Algebra of logic is successfully applied in the theory of electrical circuits", and through V- "Algebra of logic is used in the synthesis of relay-contact circuits."

Then the compound statement "The algebra of logic is successfully applied in the theory of electrical circuits and in the synthesis of relay-contact circuits" can be briefly written as A and B; here "and" is a logical connective. Obviously, since elementary statements A and B are true, then the compound statement 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 recorded in the form of a table. Such tables are called truth tables.

Basic operations of Boolean 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, denoted symbolically by a bar above ($ 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" (saying A); “Mars is not a planet of 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 with respect to one quantity is called unary... The table of values ​​of this operation has the form

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 some set of points, then $ A↖ (-) $ is the complement of the set A, that is, 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 values ​​(operands) and connects two or more statements using a link "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 no sign is put between the statements: AB. An example of logical multiplication: "This triangle is isosceles and right-angled." A given statement can only be true 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

Utterance A ∧ V is true only if both statements - A and V are true.

Geometrically, a conjunction can be represented as follows: if A, B A ∧ V there is an intersection of sets A and V.

3. Disjunction(lat. disjunction- separation) - logical addition, an operation that connects two or more statements using a bundle "or"(for example, "A or B"), which is symbolically denoted by the sign ∨ (A∨ V) 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 are met, or at least one of the conditions.

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

Utterance A∨ V false only if both statements - A and V are false.

Geometrically logical addition can be represented as follows: if A, B Are some sets of points, then A ∨ V Is the union of sets A and V, that is, the figure uniting both the square and the circle.

4. Strictly separating disjunction, addition modulo two- a logical operation that connects two statements using a link "or", used in the exclusive sense, which is symbolically denoted by the signs ∨ ∨ or ⊕ ( A ∨ ∨ B, A ⊕ V) and reads: "Either A or B"... An example of addition modulo two is the saying "This triangle is obtuse or acute." The statement is true if any of the conditions are met.

The truth table of the operation has the form

A	V	A⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Statement A ⊕ B is true only when statements A and B have different meanings.

5. Implication(lat. implisito- closely related) - a logical operation that connects two statements using a bundle "If ... then" into a complex statement, which is symbolically denoted by the sign → ( A → V) and reads: "If A, then B", "A entails B", "B follows from A", "A implies B"... The sign ⊃ (A ⊃ B) is also used to denote implication. An example of an implication: "If the resulting quadrangle is a square, then a circle can be described around it." This operation links two simple logical expressions, the first being a condition and the second being a consequence. The result of an operation is false only when the premise is true and the effect 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	V	A→V
1	0	0
0	1	1
0	0	1
1	1	1

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

6. Equivalence, double implication, equivalence(lat. aequalis- equal and valentis- valid) - a logical operation that allows two statements A and V get a new statement A ≡ B which reads: "A is equivalent to B"... The following symbols are also used to denote equivalence: ⇔, ∼. This operation can be expressed by ligaments "Then and only then", "necessary and sufficient", "equivalent"... An example of equivalence is the statement: "A triangle will be rectangular if and only if one of the angles is 90 degrees."

The truth table of the equivalence operation has the form

A	V	A∼ V
1	0	0
0	1	0
0	0	1
1	1	1

The operation of equivalence is the opposite of addition modulo two and has the result "true" if and only if the values ​​of the variables coincide.

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

The priority of performing logical operations is as follows: negation ( "not") has the highest priority, then conjunction ( "and"), after 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. At the same time, elementary statements that form a compound statement may be completely unrelated in meaning, but this does not interfere with determining the truth or falsity of a compound statement. For example, the statement “If five is more than two ( A), then Tuesday always comes after Monday ( V) "- implication A→ V, 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 V 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 can be, for example, this: "This ball is completely red or completely blue." Therefore, if the statement A"This ball is completely red" is true, and the statement V“This ball is completely blue” is true, then the compound statement is a lie, because the ball cannot be both red and blue at the same time.

Examples of problem solving

Example 1. Determine for the indicated values ​​of X 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 the last is the implication operation. The disjunction operation ∨ is false if and only if both operands are false. The truth table for the implication is

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. Specify the set of integer values ​​X for which the expression ¬ ((X> 2) → (X> 5)) is true.

Solution. The negation operation is applied to the whole 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 implication operation takes on the value "false" only in one case: when from the truth follows false. And this is done only for X = 3; X = 4; X = 5.

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

Solution. Let's consider all the suggested words in sequence:

1) for the word ass 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.

Boolean expressions and their transformation

Under logical expression you should understand such a record that can take the logical value "true" or "false". With this definition, it is necessary to distinguish among logical expressions:

• expressions that use comparison operations ("greater than", "less than", "equal", "not equal", etc.) and take logical values ​​(for example, the expression a> b, where a = 5 and b = 7, is equal to the value "false");
• direct logical expressions associated with logical values ​​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 for performing 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 no particular order);
4. execution of logical operations (at the beginning operations of negation, then operations of logical multiplication, logical addition, the last operations of implication and equivalence are performed).

Boolean expressions can use parentheses that change the order in which operations are performed.

Example. Find the value of an 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: truth ∨ A ∧ true ∧ ¬В ∧ ¬true.

Negation operations should now be performed, followed by logical multiplication and addition:

5) ¬В = ¬false = true; ¬true = false;

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

7) true ∨ false = true.

Thus, the result of a boolean expression given values ​​is "true".

Note. Considering that the original expression is, in the end, 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 conversions of logical expressions

In the algebra of logic, the basic laws are fulfilled, which make it possible to carry out identical transformations of logical expressions.

Law	For ∨	For ∧
Propelling	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Combinative	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Junction	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↖ (-) $
Idempotencies	A ∨ A = A	A ∧ A = A
Absorption	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Gluing	(A ∧ B) ∨ (A↖ (-) ∧ B) = B	(A ∨ B) ∧ (A↖ (-) ∨ B) = B
Variable operation 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 negation	$ A↖ (=) $ = A

Proofs of these statements are made on the basis of constructing 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 bring them to a certain form by using the basic laws of the algebra of logic. Under simplification of the formula, which does not contain the operations of implication and equivalence, is understood to be an equivalent transformation that leads to a formula that contains either fewer than the original number of operations or fewer variables.

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

Let's look at examples of some of the 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.

For transformation here you can apply the law of idempotency, the distribution law; an inverse variable operation and a constant operation.

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 converting, de Morgan's rule, the operation of a variable with its inversion, an operation with a constant are applied

Examples of problem solving

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

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

We get 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 in the case when a falsehood follows from the true premise. Therefore, for a given expression, the premise A ∨ B must take on the value "true", and the consequence, that is, 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 the terms have the value “false”, that is, B - “false”; ¬C - "false", and therefore, the variable C has the value "true";

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

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

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

Solution. Let's write 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

Boolean expressions can be used to describe geometric areas. In this case, the problem is formulated as follows: for a given geometric region, write down such 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 area using a logical expression using examples.

Example 1. An image of a geometric area is specified. Write a boolean expression describing the set of points that belong 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 - circle centered at the origin $ x ^ 2 + y ^ 2 ≤ 1 $. Their intersection D1 $ ∩ $ D2 is the desired domain.

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

2)

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

Note. When constructing a logical expression, weak inequalities are used, which means that the boundaries of the figures also belong to the shaded area. If strict inequalities are used, then the boundaries will not be taken into account. Borders that do not belong to the region are usually shown with a dotted line.

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

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

Solution. The sought area is the intersection of three half-planes. We build on the plane (x, y) straight lines y = x; y = -x; y = 2. These are the boundaries of the area, and the last boundary y = 2 does not belong to the area, so we draw it with a dotted line. To fulfill the inequality y ≥ x, it is necessary that the points are to the left of the line y = x, and the inequality y = -x is satisfied for the 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, it 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 as follows: Y = X. The function Y is called function of conductivity.

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

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

The circuit can also contain closure contacts. In this case, the open contact as a switch ensures that the light comes on when the button is released, and not pressed. For such circuits, the disconnecting switch is described by negation.

The two schemes are called tantamount to if the current passes through one of them when it also passes through the other. Of the two equivalent circuits, the simpler is the circuit, the conductivity function of which contains fewer elements. The task of finding the simplest schemes among the equivalent is very important.

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

The algebra of logic mathematics is very handy for describing how computer hardware functions. Any information when processed on a computer is represented in binary form, that is, it is encoded by some sequence of 0 and 1. The processing of binary signals corresponding to 0 and 1 is performed in the computer by logical elements. Logic gates that perform basic logical operations AND, OR, NOT, are shown in Fig.

Symbols of logic elements are standard and are used when composing 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 given, either high or low, at the output. These levels correspond to one of the states of the binary system: 1 - 0; TRUE 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. Conventional designation on the OR circuit, 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 of the English word and.

Electronic logic circuits are composed of 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.

Building Boolean Expression Truth Tables

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

A convenient form of notation for 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. 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. With the help of a given truth table, it is possible to 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 according to a given table function.

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

The algorithm for constructing DNF is as follows:

1. in the truth table of the function, sets of arguments are selected 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 together by the operation of a logical sum (disjunction);
3. for arguments that are false, the negation operation is applied to 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 has the form

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

Solution. We select the sets of argument values ​​in which the function is equal to 1. These are the first and fourth rows of the table (the header row is not taken into account 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 the negation with respect to 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 the sums formed from the variables and their negations for the true values.

The algorithm for constructing the 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 by the operation of a logical product (conjunction);
3. for arguments that are true, the negation operation is put down in the constructed record.

Examples of problem solving

Example 1. Consider the previous example, that is, 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 (the title line is not taken into account 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 the negation with respect to 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 row, this is the second set of the formula, the first element): X1 ∨ $ (X2) ↖ (-) $ ∧ $ ( X1) ↖ (-) $ ∨ X2.

Thus, a record of the logical function in the 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 boolean function for a given truth table:

The sought 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 sought formula: X1 ∧ X2 ∧ X ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∪ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $.

The formula is rather 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 logic problems

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

Examples of problem solving

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

Solution. Obviously, the solution will result in a table in which the required 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. Create a schedule of lessons 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 physics - 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 is easily solved if you draw up the appropriate table:

	1st lesson	2nd lesson	3rd lesson
Computer science	1	1	0
Maths	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. informatics, 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 oldest;
2. one who plays football is younger than one who plays hockey;
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 cannot play tennis or badminton.

What kinds of sports do each of the boys enjoy?

Solution. Let's compose 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 kinds of sports, it turns out that all the boys are fond of different sports.

From condition 4 it follows that Boris is not fond of skiing or tennis, but from conditions 3 and 5 that Peter does not know how to play football, hockey, tennis and badminton. Hence, Peter's favorite sports are skiing and swimming. Let's enter this into the table, and fill the remaining cells of the "Ski" and "Swimming" columns with zeros.

The table shows that only Alexei 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 in the table. Let's enter zeros in the empty cells of the line "Alexey".

Finally, we get that Boris is fond of hockey and badminton. The final table will look like this:

Answer: Peter is fond of skiing and swimming, Boris plays hockey and badminton, and Alexey plays football and tennis.

Task 1 # 10050

\ ((x \ wedge y) \ vee (x \ wedge \ overline y) \ vee (y \ wedge z) \ vee (z \ wedge x) \)

Make her truth table. For your answer, enter the number of sets \ ((x, \) \ (y, \) \ (z), \) for which the function is 1.

1. Simplify \ ((x \ wedge y) \ vee (x \ wedge \ overline y). \)

By the law of distribution \ ((y \ wedge x) \ vee (x \ wedge \ overline y) \) = \ (x \ wedge (y \ vee \ overline y). \)\ (y \ vee \ overline y = 1 \) (if \ (y = 0, \) then \ (\ overline y \ vee y = 1 \ vee 0 = 1, \) if \ (y = 1, \) then \ (\ overline y \ vee y = 0 \ vee 1 = 1). \) Then \ (x \ wedge (y \ vee \ overline y) = x \ wedge 1 = x. \)

2. Simplify \ ((y \ wedge z) \ vee (z \ wedge x). \) By the law of distribution \ ((y \ wedge z) \ vee (z \ wedge x) = z \ wedge (y \ vee x). \)

3. We get: \ ((x \ wedge y) \ vee (x \ wedge \ overline y) \ vee (y \ wedge z) \ vee (z \ wedge x) = x \ vee z \ wedge (y \ vee x). \)

4. The truth table contains 8 lines (lines are always \ (2 ^ n, \) where \ (n \) is the number of variables). In our case, there are 3 variables.

5. Fill in the truth table.

\ [\ begin (array) (| c | c | c | c | c | c | c |) \ hline x & y & z & y \ vee x & z \ wedge (y \ vee x) & F = x \ vee z \ wedge (y \ vee x) \\ \ hline 0 & 0 & 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 & 0 & 0 \\ \ hline 0 & 1 & 0 & 1 & 0 & 0 \\ \ hline 0 & 1 & 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 1 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 1 & 1 \\ \ hline \ end (array) \]

Since the disjunction \ (x \ vee z \ wedge (y \ vee x) \) is true if at least one of the statements included in it is true, then for \ (x = 1 \) \ (F = 1 \) for any \ (y \) and \ (z \) (lines 5-8 in the truth table ).

Consider the case when \ (x = 0. \) Then the value of the function will depend on the value \ (z \ wedge (y \ vee x). \) If \ (z \ wedge (y \ vee x) \) is true, then and \ (F \) is true, if false then \ (F \) is false. Consider the case when \ (F = 1. \) The conjunction \ ((z \ wedge (y \ vee x)) \) is true if all statements included in it are true, that is, \ (y \ vee x = 1 \) and \ (z = 1. \) \ (x = 0, \) means \ (y \ vee x = 1, \) when \ (y = 1 \) (line 4).

If one of the statements included in the conjunction is false, then the entire conjunction is false. If \ (x = 0 \) and \ (y = 0, \) then \ (y \ vee x = 0. \) Then \ (z \ wedge (x \ vee y) = 0 \) for any \ (z \) (lines 1-2). Since \ (x = 0, \) and the second statement in the disjunction \ ((z \ wedge (x \ vee y)), \) is also false, then the whole function is false. If \ (x = 0 \) and \ (y = 1, \) then \ (y \ vee x = 1. \) If \ (z = 0, \) \ (z \ wedge (y \ vee x) = 0. \) Then \ (F = 0 \) (line 3). The case when \ (z = 1, \) \ (y = 1, \) \ (x = 0, \) was considered in the previous paragraph.

We have built a truth table. We see that there are 5 sets in it, for which \ (F = 1. \) Therefore, the answer is 5.

Answer: 5

Quest 2 # 10051

The logical function \ (F \) is given by the expression:

\ ((x \ wedge \ overline y \ wedge z) \ vee (x \ rightarrow y) \)

Make her truth table. For your answer, enter the number of sets \ ((x, \) \ (y, \) \ (z), \) for which the function is 0.

\ [\ begin (array) (| c | c | c | c | c | c | c | c | c |) \ hline x & y & z & \ overline y & x \ wedge \ overline y & x \ wedge \ overline y \ wedge z & \ overline x & \ overline x \ vee y & x \ wedge \ overline y \ wedge z \ vee \ overline x \ vee y \\ \ hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \ hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \ hline \ end (array) \]

1. \ (x \ rightarrow y \) = \ (\ overline x \ vee y. \)

2. Note that for \ (y = 1 \) \ (F = 1, \) since the disjunction is true if at least one expression included in it is true (lines 3-4, 7-8 in the truth table). Similarly, for \ (\ overline x = 1, \) that is, for \ (x = 0, \) \ (F = 1 \) (lines 1-4).

3. For \ (x = 1 \) and \ (y = 0 \) \ (\ overline x \ vee y = 0, \) \ (x \ wedge \ overline y = 1. \) For \ (z = 1 \) \ (x \ wedge \ overline y \ wedge z = 1 \) and \ (F = 1, \) since one of the expressions (line 6) is true, and for \ (z = 0 \) \ (x \ wedge \ overline y \ wedge z = 0 \) and \ (F = 0, \) since both expressions included in the disjunction are false (line 5).

According to the constructed truth table, we see that for one set \ ((x, \) \ (y, \) \ (z) \) \ (F = 0. \)

Answer: 1

Task 3 # 10052

The logical function \ (F \) is given by the expression:

\ ((\ overline (z \ vee \ overline y)) \ vee (w \ wedge (z \ equiv y)) \)

Make her truth table. As an answer, enter the sum of the values ​​\ (z, \) \ (y \) and \ (w, \) for which \ (F = 1. \)

\ [\ begin (array) (| c | c | c | c | c | c | c | c | c |) \ hline w & y & z & \ overline y & z \ vee \ overline y & \ overline ( z \ vee \ overline y) & z \ equiv y & w \ wedge (z \ equiv y) & \ overline z \ vee \ overline y \ vee w \ wedge (z \ equiv y) \\ \ hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \ hline 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \ hline 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \ hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \ hline \ end (array) \]

1. \ ((\ overline (z \ vee \ overline y)) = \ overline z \ wedge y \)

2. The truth table will have \ (2 ^ 3 = 8 \) lines.

3. If \ (z = 1 \) and \ (y = 1, \) \ (then (z \ equiv y) = 1 \) (since the equivalence is true if and only if both statements are simultaneously false or true) ... \ (\ overline z \ wedge y = 0 \) \ ((0 \ wedge 1 = 0). \) If \ (w = 1, \) \ (w \ wedge (z \ equiv y) = 1 \) \ ((1 \ wedge 1 = 1) \) and \ (F = 1, \) since the disjunction is true if at least one of the statements included in it is true (line 8 in the truth table). If \ (w = 0, \) \ (w \ wedge (z \ equiv y) = 0 \) \ ((0 \ wedge 1 = 0) \) and \ (F = 0, \) since both statements, included in the disjunction are false (line 4).

4. Similarly for \ (z = 0, y = 0. \) \ ((z \ equiv y) = 1, \) \ (\ overline z \ wedge y = 0 \) \ ((1 \ wedge 0 = 0 ). \) Then again the value of the function will depend on \ (w. \) For \ (w = 1 \) \ (w \ wedge (z \ equiv y) = 1, \)\ (F = 1, \) since one of the statements included in the disjunction is true (line 5), and for \ (w = 0 \) \ (w \ wedge (z \ equiv y) = 0, \)\ (F = 0, \) since all statements are false (line 1).

5. If \ (z = 0 \) and \ (y = 1, \) then \ (\ overline z \ wedge y = 1 \) \ ((1 \ wedge 1 = 1). \) Since \ (( z \ equiv y) = 0 \) (after all, the values ​​\ (z \) and \ (y \) are different), will be false for any \ (w. \) Then, since the value of the variable \ (w \) will not affect on the value of the function, for \ (z = 0 \) and \ (y = 1 \) \ (w \) can be either 0 or 1. \ (F = 1, \) since one of the statements included in disjunction, true (lines 3, 7).

6. If \ (z = 1 \) and \ (y = 0, \) then \ (\ overline z \ wedge y = 0 \ wedge 0 = 0. \) Since \ ((z \ equiv y) = 0, \) \ (w \ wedge (z \ equiv y) = w \ wedge 0 \) will be false for any \ (w \) (that is, \ (w \) can be 0 and 1). Hence, for \ (z = 1 \) and \ (y = 0 \) \ (F \) will always be false (since both statements included in the disjunction are false, lines 2, 5).

7. \ (F = 1 \) for the following sets \ (z, \) \ (y, \) \ (w: \) (0, 0, 1), (0, 1, 1), (1, 1 , 1), (0, 1, 0). If we add up the values, we get 7.

Answer: 7

Quest 4 # 10053

The logical function \ (F \) is given by the expression:

\ (a \ wedge ((\ overline (b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a)) \)

Make her truth table. As an answer, enter the sum of the values ​​\ (a, \) \ (b \) and \ (c, \) for which \ (F = 1. \)

\ [\ begin (array) (| c | c | c | c |) \ hline a & b & c & F \\\ hline 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 \ \ \ hline 0 & 1 & 0 & 0 \\ \ hline 0 & 1 & 1 & 0 \\ \ hline 1 & 0 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 \\ \ hline \ end (array) \]

1. In the truth table \ (2 ^ 3 = 8 \) lines.

2. For \ (a = 0 \) \ (F = 0 \) for any values ​​\ (b \) and \ (c, \) since the conjunction is true if and only if all statements included in it are true (lines 1-4 in the truth table).

3. Consider the cases when \ (a = 1. \) If \ (\ overline ((b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a) = 1, \) then \ (F = 1 \) (since both statements will be true), otherwise \ (F = 0 \) (since one statement will be false). De Morgan's law \ (\ overline (b \ wedge c) = \ overline b \ vee \ overline c. \) Then, taking into account that \ (a = 1, \) \ (\ overline ((b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a) = \ overline b \ vee \ overline c \ vee \ overline b \ vee \ overline c = \ overline b \ vee \ overline c. \)

4. If \ (\ overline b = 0 \) and \ (\ overline c = 0 \) (simultaneously, that is, for \ (b = 1 \) and \ (c = 1), \) then \ (\ overline b \ vee \ overline c = 0 \) and \ (F = 0 \) (line 8). In other cases \ (\ overline b \ vee \ overline c = 1 \) and \ (F = 1 \) (lines 5-7).

5. The sets \ ((x, \) \ (y, \) \ (z), \) for which \ (F = 1: \) (1, 0, 0), (1, 1, 0), ( 1, 0, 1). The sum of the values ​​is 5.

Answer: 5

Task 5 # 10054

The logical function \ (F \) is given by the expression:

\ (((a \ wedge b) \ vee (b \ wedge c)) \ equiv ((d \ rightarrow a) \ vee (b \ wedge \ overline c)) \)

Make a truth table. As an answer, enter the sum of the values ​​\ (a, \) at which \ (F = 0. \)

\ [\ begin (array) (| c | c | c | c | c |) \ hline a & b & c & d & F \\\ hline 0 & 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 0 & 1 & 1 \\ \ hline 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 1 & 0 \\ \ hline 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 & 0 \\ \ hline 1 & 1 & 0 & 1 & 1 \\ \ hline 1 & 0 & 1 & 0 & 0 \\ \ hline 1 & 0 & 0 & 1 & 0 \\ \ hline 0 & 1 & 1 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 & 0 \\ \ hline 0 & 1 & 0 & 1 & 0 \\ \ hline \ end (array) \]

1. According to the law of distribution \ ((a \ wedge b) \ vee (b \ wedge c) = b \ wedge (a \ vee c). \)

2. \ (d \ rightarrow a = \ overline d \ vee a. \)

3. \ (((a \ wedge b) \ vee (b \ wedge c)) \ equiv ((d \ rightarrow a) \ vee (b \ wedge \ overline c)) = b \ wedge (a \ vee c) \ equiv (\ overline d \ vee a \ vee (b \ wedge \ overline c)). \)

4. If \ (b = 0, \) then the left side of the function is 0 \ ((0 \ wedge (a \ vee c) = 0). \) \ (b \ wedge \ overline c = 0 \ wedge \ overline c = 0. \) This means that for \ (b = 0 \) \ (c \) can be anything, since it does not affect the value of the function. \ (F = 1, \) if \ (\ overline d \ vee a = 0 \) (then one of the expressions included in the disjunction will be true). This is done with \ (\ overline d = 0 \) \ ((d = 1) \) and \ (a = 0 \) (lines 2, 3). For other \ (d \) and \ (a \) \ (\ overline d \ vee a = 0, \) it means \ (F = 0, \) since the equivalence operation is true if and only if both statements are simultaneously true or false (lines 1, 10 in the truth table).

5. If \ (b = 1, \) then \ (b \ wedge (a \ vee c) = 1 \ wedge (a \ vee c) = a \ vee c. \) \ (b \ wedge \ overline c = 1 \ wedge \ overline c = \ overline c. \) Then we have that \ (a \ vee c \ equiv \ overline d \ vee a \ vee \ overline c. \) If \ (a = 1, \) then \ (a \ vee c = 1 \) and \ (\ overline d \ vee a \ vee \ overline c = 1, \) since the disjunction is true if at least one of the expressions is true (and both disjunctions contain \ (a = 1). \) Then, if \ (b = 1 \) and \ (a = 1, \) \ (F = 1 \) for any \ (c \) and \ (d \) (lines 5, 7, 8, 11).

If \ (a = 0, \) then \ (a \ vee c = 0 \ vee c = c, \) and \ (\ overline d \ vee a \ vee \ overline c = \ overline d \ vee \ overline c. \) We have: \ (c \ equiv (\ overline d \ vee \ overline c). \) For \ (c = 1 \) \ (1 \ equiv \ overline d. \) For \ (d = 1 \) \ (F = 0, \) since the statements are different (line 4), for \ (d = 0 \) \ (F = 1, \) since both statements are true (line 14). For \ (c = 0 \) \ (0 \ equiv (\ overline d \ vee 1). \) Since \ (\ overline d \ vee 1 \) is a disjunction in which one of the statements is true, the whole disjunction is true. Then \ (0 \ equiv 1, \) which is not true, which means \ (F = 0 \) for any \ (d \) (lines 9, 16).

According to the constructed table, we see that \ (F = 0 \) for \ (a = 0 \) (lines 1, 4, 9, 10, 16) and for \ (a = 1 \) (lines 6, 12, 13, 15). Then the sum of the values ​​is 0 * 5 + 1 * 4 = 4.

Answer: 4

Task 6 # 10055

The logical function \ (F \) is given by the expression:

\ ((a \ equiv (b \ vee \ overline c)) \ rightarrow (c \ wedge (b \ vee a)) \)

Make a truth table. As an answer, enter the sum of the values ​​\ (c, \) for which \ (F = 1. \)

\ [\ begin (array) (| c | c | c | c |) \ hline a & b & c & F \\\ hline 0 & 0 & 0 & 1 \\ \ hline 0 & 0 & 1 & 0 \ \ \ hline 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 1 \\ \ hline 1 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 \\ \ hline 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 \\ \ hline \ end (array) \]

The table contains \ (2 ^ 3 = 8 \) rows.

1. An implication is false if and only if false follows from a true statement. Hence, \ (F = 0, \) if a \ (c \ wedge (b \ vee a) = 0. \) In other cases \ (F = 1. \) Consider for what values ​​\ (a, \) \ (b \) and \ (c \) \ (a \ equiv (b \ vee \ overline c) = 1 \)(if \ (a \ equiv (b \ vee \ overline c) = 0, \) then \ (F = 1 \) for any value \ (c \ wedge (b \ vee a) = 0). \)

If \ (a = 0, \) then to execute \ (a \ equiv (b \ vee \ overline c) = 1, \) necessary \ (b \ vee \ overline c = 0 \) (after all, the equivalence operation is true if and only if both statements are true or both are false). For the disjunction \ ((b \ vee \ overline c) \) to be false, both statements included in it must be false, that is, \ (b = 0 \) and \ (\ overline c = 0 \) \ (( c = 1). \) For such values \ (c \ wedge (b \ vee a) = 1 \ wedge (0 \ vee 0) = 0. \) Then \ ((a \ equiv (b \ vee \ overline c)) \ rightarrow (c \ wedge (b \ vee a)) = 1 \ rightarrow 0 = 0, \)\ (F = 0. \) This corresponds to line 2 from the truth table.

If \ (a = 1, \) then to execute \ (a \ equiv (b \ vee \ overline c) = 1, \)\ (b \ vee \ overline c = 1. \) This is done in several cases. If \ (b = 1, \) then \ (c \) can be equal to both zero and one, because one of the statements included in the disjunction is already true. For \ (c = 1 \) \ (c \ wedge (b \ vee a) = 1 \ wedge 1 = 1, \) then \ (F = 1 \) (since \ (1 \ rightarrow 1 = 1, \) line 7). For \ (c = 0 \) \ (c \ wedge (b \ vee a) = 0 \ wedge 1 = 0, \) hence, \ (F = 0 \) \ ((1 \ rightarrow 0 = 0, \) line 6). If \ (b = 0, \) then \ (\ overline c = 1 \) \ ((c = 0, \) then one of the statements included in the disjunction will be true). In this case \ (c \ wedge (b \ vee a) = 0 \ wedge (0 \ vee 1) = 0. \)\ (F = 0, \) since \ (1 \ rightarrow 0 = 0 \) (line 5).

2. For other values ​​\ (a, \) \ (b \) and \ (c \) \ (F = 1, \) because \ (a \ equiv (b \ vee \ overline c) = 0 \)(lines 1, 3, 7, 8).

3. From the compiled truth table we see that \ (F = 1 \) for \ (c = 0 \) (lines 1, 4) and for \ (c = 1 \) (lines 3, 7, 8). The sum of the values ​​is 0 * 2 + 1 * 3 = 3. \ (2 ^ 4 = 16 \) lines.

1. Since the conjunction is false, if at least one of the statements is false, then for \ (d = 0 \) \ (F = 0 \) for any \ (a, \) \ (b \) and \ (c \) (lines 1, 6-10, 12, 14 in the truth table).

2. Consider the case when \ (d = 1. \) Then \ ((a \ rightarrow b) \ wedge (b \ equiv c) \ wedge d = (a \ rightarrow b) \ wedge (b \ equiv c) \ wedge 1 = (a \ rightarrow b) \ wedge (b \ equiv c). \) For \ (b = 1 \) \ (a \ rightarrow b = a \ rightarrow 1 = 1 \) for any \ (a, \) since the implication is false if and only if false follows from a true statement. If \ (c = 1, \) then \ (b \ equiv c = 1, \) since the equivalence operation is true when both expressions are true or both are false, and \ (F = 1 \) (since all expressions included into conjunction are true). This corresponds to lines 4 and 5. If \ (c = 0, \) then \ (b \ equiv c = 0, \) \ (F = 0, \) since one of the expressions included in the conjunction is false (lines 11 and 16).

For \ (b = 0: \) if \ (a = 1, \) then \ (a \ rightarrow b = 1 \ rightarrow 0 = 0, \) then one of the expressions included in the conjunction is false, and \ (F = 0 \) for any \ (c \) (lines 13 and 15). If \ (a = 0, \) then \ (a \ rightarrow b = 0 \ rightarrow 0 = 1. \) If \ (c = 0, \) then \ (b \ equiv c = 0 \ equiv 0 = 1, \)\ (F = 1, \) since both expressions included in the conjunction are true (line 2). If \ (c = 1, \) then \ (b \ equiv c = 0 \ equiv 1 = 0, \)\ (F = 0, \) since one of the expressions included in the conjunction is false (line 3).

Thus, \ (F = 1 \) for \ (d = 1 \) (lines 2, 4, 5). The sum of the values ​​\ (d \) is 1 * 3 = 3.

Construction of truth tables for complex statements.

Boolean priority

1) inversion 2) conjunction 3) disjunction 4) implication and equivalence

How to make a truth table?

By definition, the truth table of a logical formula expresses the correspondence between various sets of variable values ​​and the values ​​of a formula.

For a formula that contains two variables, there are only four such sets of variable values:

(0, 0), (0, 1), (1, 0), (1, 1).

If the formula contains three variables, then there are eight possible sets of variable values ​​(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0 ), (1, 0, 1), (1, 1, 0), (1, 1, 1).

The number of sets for a formula with four variables is sixteen, and so on.

A convenient form of notation for finding the values ​​of a formula is a table containing, in addition to the values ​​of variables and formula values, also the values ​​of intermediate formulas.

Examples.

1. Let's create a truth table for the formula 96% "style =" width: 96.0% ">

The table shows that for all sets of values ​​of the variables x and y, the formula takes the value 1, that is, is identically true.

2. Truth table for formula 96% "style =" width: 96.0% ">

The table shows that for all sets of values ​​of the variables x and y, the formula takes the value 0, that is, is identically false .

3. Truth table for formula 96% "style =" width: 96.0% ">

The table shows that formula 0 "style =" border-collapse: collapse; border: none ">

Conclusion: we got all units in the last column. This means that the meaning of a complex statement is true for any values ​​of simple statements K and C. Therefore, the teacher reasoned logically correctly.