Technological map of a lesson in computer science on the topic “Solving logical problems” for 8th grade students

Lesson 27§22. Logical problems and methods for solving them

Lesson content:

22.1. Method of Reasoning 22.2. Problems about knights and knaves 22.3. Matching tasks. Table method. 22.4. Using truth tables to solve logical problems 22.5. Solving logical problems by simplifying logical expressions is THE MOST IMPORTANT. Questions and assignments Materials for the lesson

22.3. Matching tasks. Table method. 22.4. Using truth tables to solve logical problems
22.2. Problems about knights and knaves	22.5. Solving logical problems by simplifying logical expressions

22.3. Matching tasks. Table method

Many logical problems involve the consideration of several finite sets and connections between their elements. To solve such problems, they often resort to tables or graphs. The success of solving the problem largely depends on how well their structure is chosen.

Example 5 . At the summer camp, Alyosha, Borya, Vitya and Grisha lived in the same tent. They are all of different ages, study in different grades (from 7th to 10th) and are involved in different clubs: mathematics, aircraft modeling, chess and photography. It turned out that the photographer is older than Grisha, Alyosha is older than Vitya, and the chess player is older than Alyosha. On Sunday, Alyosha and the photographer played tennis, and at the same time Grisha lost to an airplane modeler in the towns.

Let's determine who is involved in which circle.

In this problem we are talking about an expressive form (predicate) of the form “Student x studies in circle y.” It is necessary to determine such values of x and y that the statement form turns into a true statement.

Let's make a table:

Let's consider the conditions:

1) the photographer is older than Grisha; 2) Alyosha is older than Vitya, and the chess player is older than Alyosha; 3) on Sunday Alyosha and the photographer played tennis, and at the same time Grisha lost to an aircraft model designer in the towns.

We can draw conclusions: Grisha is not a photographer (1); the chess player is not Alyosha or Vitya (2); Alyosha is not a photographer or an aircraft modeller, Grisha is not a photographer or an aircraft modeller (3). Let's note this in the table:

The available information is enough to state that Alyosha studies mathematics, and Grisha studies chess:

From the fact that Grisha is a chess player, and conditions (1) and (2), it follows that we can arrange the students by age (in ascending order): Vitya - Alyosha - chess player Grisha - photographer. Therefore, Borya is a photographer. This is enough to completely fill out the table:

So, Alyosha is in a math club, Borya is in a photography club, Vitya is in an aircraft modeling club, Grisha is in a chess club.

Draw your own conclusion about which of the children is in which class.

22.4. Using truth tables to solve logical problems

The apparatus of logical algebra allows one to apply universal methods based on the formalization of the conditions of the problem to a wide class of logical problems.

One of these methods is the construction of a truth table based on the conditions of the problem and its analysis. To do this you should:

1) select elementary (simple) statements from the problem conditions and designate them with letters; 2) write down the condition of the problem in the language of logical algebra, combining simple statements into compound statements using logical operations; 3) build a truth table for the resulting logical expressions; 4) choose a solution - a set of logical variables (elementary statements), in which the values of logical expressions correspond to the conditions of the problem; 5) make sure that the resulting solution satisfies all the conditions of the problem.

Example 6 . Three divisions A, B, C of a trading company sought to obtain maximum profit at the end of the year. Economists have made the following assumptions:

1) if A receives the maximum profit, then B and C will receive the maximum profit; 2) A and C will or will not receive the maximum profit at the same time; 3) a necessary condition for division C to obtain maximum profit is to obtain maximum profit for division B.

At the end of the year, it turned out that one of the three assumptions was false, and the other two were true.

Let's find out which of the named divisions received the maximum profit.

Let's consider elementary statements:

• A - “A will receive the maximum profit”; • B - “B will receive the maximum profit”; • C - “C will receive the maximum profit.”

Let us write down the forecasts made by economists in the language of logical algebra:

Let's create a truth table for F1, F2, F3.

Now remember that out of three predictions F1, F2, F3, one turned out to be false, and the other two turned out to be true. This situation corresponds to the fourth row of the table.

Thus, divisions B and C received the maximum profit.

Download lesson materials

Solving logical problems (lesson notes + presentation)

Let's find out how you can solve logic problems using tables. The topic is explained using specific examples.

Slide 9 – the task opens. The grandmother knew that one of her grandchildren, let's call him truthful, told the truth both times; the second, let's call him a joker, told a lie both times; the third, let's call him a cunning one, told the truth once, and another time - a lie. Name the truthful, the joker and the cunning. Which grandson broke the vase?

Seryozha: I didn’t break it. Vasya didn’t break it.

Vasya: I didn’t break Seryozha. Kolya broke the vase.

Kolya: I didn’t break it. Seryozha broke the vase. Can you quickly solve this problem without using tables?

Now let's try to solve it using a truth table. I'm building a table on the board. And filling it out in accordance with each boy's statement.

Let's consolidate this method.

Slide 10 opens. The case of John, Brown and Smith is being examined. it is known that one of them found and hid the treasure. During the investigation, each of the suspects made two statements:

Smith

: I did not do it.
Brown did it. John
: Brown is not guilty.
Smith did it. Brown
: I didn't do it. John didn't do this. the court found that one of them lied twice, the other told the truth twice, the third lied once, and told the truth once. Which suspect should be acquitted?

I call one student to the board so that he can solve the problem according to the model. If necessary, I help him by asking leading questions.

But the tabular method of solving problems is not always applicable. Look at the next problem. Slide 11 opens. Alla, Valya, Sima, Dasha took part in the gymnastics competitions. It has been suggested:

1) Sima will be first, Valya second;

2) Sima will be second, Dasha third;

3) Alla will be second, Dasha fourth.

It turned out that in each assumption only one statement is true. What place did each of the girls take? Is it possible to apply our method here? To do this, let's turn to the properties of logical operations. Let's break down children's complex statements into simple ones and label each of them with a letter.

Sima will be first – C1

Valya the second – B2

Sima will be second – C2

Dasha third – D3

Alla will be the fourth – A4

Dasha will be fourth – D4

Since one of the statements is true and the other is false, we can conclude the following.

С1+В2=1, С1*В2=0
C2+D3=1, C2*D3=0
A2+D4=1, A2*D4=0

The logical product of true statements will be true.

(C1+B2)*(C2+D3)*(A2+D4)=1

Further, by applying the laws and obtaining contradictions, we will obtain the only correct solution.

C1*D3*A2=1

This means that Sima took first place, Alla – second, Dasha third. Consequently, Valya took fourth place.

Let's secure it. Slide 11 of the presentation opens. I call one student to the board so that he can solve the problem according to the model. If necessary, I help him by asking leading questions.

Computer science lesson (8th grade) on the topic “Solving logical algebra problems”

Subject:

Solving problems on the topic “Algebra of Logic”

Goals:

educational

– introducing students to methods for solving logical problems;

developing

– development of students’ logical thinking, memory, attention, intellectual abilities using ICT, as well as interest in the branch of computer science – logical algebra;

educational

– work to increase knowledge of the basic concepts and laws of logical algebra, achieving conscious mastery of the material by students using the acquired knowledge in practice.

During the classes

Let's look at examples of solving problems in various ways

Example 1Check the equivalence of the expressions A ~ E and (Ā ∧ Ē) v (A ∧ E).

Solution. To check, you should create a truth table containing as many rows as possible sets of values of the variables included in the expression. For two variables (A and E), the number of sets is four. To the two columns for the variable values (A and E), you need to add a number of columns equal to the number of operations in the expression. Thus, you need to create a table containing 4 rows and 7 columns.

Let's fill the first 2 columns (A and E) with all combinations of variable values. Let us write as column headings all the operations of the expression in the order of their execution (in accordance with priorities and parentheses). Let's calculate the values of these operations: first the expressions in brackets, then the result of their addition.

The last column contains the resulting value of the expression. It coincides with the truth table for the equivalence operation. Therefore, the expressions are equivalent.

Basic laws of algebra logic

For complex logical expressions with a large number of variables, determining their truth by constructing truth tables becomes cumbersome. In such cases, methods of simplifying expressions are used. Simplification is understood as an equivalent transformation of an expression to its normal form.

The normal form of an expression contains only the operators of negation, conjunction and disjunction and does not contain negation of expressions and double negatives.

To simplify, equivalent transformations are used, which are otherwise called the basic laws of logical algebra.

Identical transformations of logical expressions

For all identical transformations, the law of duality is satisfied: if in the transformation formula we replace conjunction with disjunction, disjunction with conjunction, the values 1 with 0, 0 with 1, then the law formulated for conjunction will take the form of a similar law for disjunction, and vice versa.

First of all, during equivalent transformations, they get rid of the negation of expressions, then - from the logical operations of exclusive disjunction, implication and equivalence. The laws of logical algebra are then used to reduce the number of variables in the expression.

Example 2Choose an expression that is equivalent to the expression (A ∧ B) v (Ā ∧ B).

1) A 2) A ∧ B 3) Ā ∧ B 4) B

Solution. In accordance with the law of gluing (A ∧ B) v (Ā ∧ B) = B, therefore, the original expression is equivalent to the expression B. Answer: 4) B.

DETERMINING THE VALUES OF LOGICAL EXPRESSIONS

Expressions that evaluate to Boolean values (true or false) as a result of comparison operations (greater than >, less than <, greater than or equal to ≥, less than or equal to ≤, equal to =, not equal to ≠) are also Boolean expressions. In addition to comparison and logical operations, such expressions can include functions and algebraic operations. The priority for performing these operations is:

Calculation of function values.
Perform algebraic operations (first exponentiation, then multiplication and division, then subtraction and addition).
Perform comparison operations (in recording order).
Performing logical operations (first negation operations, then logical multiplication operations, then logical addition operations, lastly the implication and equivalence operations are performed).

If a Boolean expression uses parentheses, the operations enclosed within them are performed first.

Example 3For which of the following values of the number M is the following expression true? ¬M ≥ 10 ∧ M > 3

1) 1 2) 2 3) 3 4) 4

Solution. According to the priorities of operations, comparison operations should be performed first, then negation, and then conjunction. The negation of the statement M ≥ 10 is the statement M < 10. We obtain the expression M < 10 ∧ M > 3. In order for this expression (conjunction) to be true, both inequalities must be satisfied (i.e., be true). Therefore, the value of M must be greater than 3, but less than 10. Among the proposed values, only one satisfies this condition - the number 4. Answer: 4) 4.

Problems similar to the previous example can be solved using truth tables.

Example 4For which of the following values of the number M is the following expression true? ¬M ≥ 10 ∧ M > 3

1) 1 2) 2 3) 3 4) 4

Solution. Let's create a truth table: we'll indicate all the operations of the expression in the columns of the table, and we'll indicate all the proposed values of M in its rows. Let's calculate the table values:

The last column contains the result of the entire expression. It will be true only for the value of the number M equal to 4. Answer: 4) 4.

Example 5 The tabular form presents monthly data on the sale of product groups for six months. How many product groups showed sales growth in the spring months or reached over 80% in June?

Solution. Let us reformulate the condition of the problem: it is necessary to find groups of goods for which (March < April) ∧ (April < May) v (June > 80).

Let us introduce the notation: A = (March < April) B = (April < May) C = (June > 80)

Then the expression can be written as A ∧ B v C.

A logical expression consists of one conjunction and one disjunction. The meaning of a conjunction expression is true only if both of its constituent simple expressions ((March < April) and (April < May)) are true. The meaning of a disjunction expression will be true if at least one of its constituent simple statements is true.

Let's create a truth table for the source data.

The logical expression is satisfied by 3 entries - 4th, 6th and 7th. Answer: 3.

Homework:

repeat the rules.