Теория и практика решения задания 18 ЕГЭ по информатике

МБОО «Лицей села Верхний Мамон»

Теория и практика решения задания 18 ЕГЭ по информатике

Автор:

учитель информатики МБОО «Лицей села Верхний Мамон»

ВКК Мирошников Роман Сергеевич

Мнемоническое правило

Соционика – это информационная психология

Один из ее главных принципов – дополнение до целого ( дополнение противоположностью )

Решающая формула

В алгебре логики есть формула дополнения до целого:

А  ¬А = 1

В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:

А  ¬А = 0

Типы задания 18

• Задания на отрезки
• Задания на множества
• Задания на поразрядную конъюнкцию
• Задания на условие делимости

Задания на отрезки

( № 376 ) На числовой прямой даны два отрезка: P=[4,15] и Q=[12,20]. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Источник - сайт Полякова К.Ю.

Решающая формула

Для выбора решающей формулы важно внимательно прочитать требование задачи.

В нашей задаче в требовании сказано:

принимает значение 1 при любом значении переменной х.

Выбор решающей формулы очевиден:

А  ¬А = 1

Решение задачи на отрезки

Разделим решение задачи на этапы:

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на отрезки

• Легенда – это удобные нам условные обозначения, которые мы будем использовать при решении.

Введем следующие обозначения:

P = x  P

Q = x  Q

A = x  A

Решение задачи на отрезки

2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.

Было:

((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) = 1

Стало:

(P ∧ Q) → A = 1

Решение задачи на отрезки

3) Решение логического уравнения – вначале это, возможно, самый сложный этап в решении задачи. Но позже, при накоплении опыта, он уже не будет казаться таким уж сложным 

Рассмотрим решение логического уравнения по шагам.

Решение задачи на отрезки

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В :

(P ∧ Q) → A = 1

¬ (P ∧ Q)  A = 1

Решение задачи на отрезки

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :

¬(P ∧ Q)  A = 1, отсюда

¬А = ¬(P ∧ Q)

Ответом в логическом уравнении будет:

А = P ∧ Q.

Решение задачи на отрезки

4) Интерпретация полученного результата .

Наш ответ: А = P ∧ Q .

В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q .

Решение задачи на отрезки

Пересечение отрезков P и Q можно визуализировать: P=[4,15] и Q=[12,20].

15

12

20

4

По условию нашей задачи, нам нужна минимальная длина отрезка А . Находим ее: 15 – 12 = 3 .

Ответ: 3 .

Ответ на сайте Полякова К.Ю.: 3

Задания на отрезки

(№ 360) На числовой прямой даны три отрезка: P=[10,25], Q=[15,30] и R=[25,40]. Какова максимальная длина отрезка A, при котором формула ((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P)

тождественно ложна, то есть принимает значение 0 при любом значении переменной х?

Источник - сайт Полякова К.Ю.

Решающая формула

Для выбора решающей формулы важно внимательно прочитать требование задачи.

В нашей задаче в требовании сказано:

принимает значение 0 при любом значении переменной х.

Выбор решающей формулы очевиден:

А  ¬А = 0

Решение задачи на отрезки

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на отрезки

• Легенда

R = x  R

Q = x  Q

A = x  A

P = x  P

Решение задачи на отрезки

2) Формализация условия

Было:

((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P) = 0

Стало:

( Q → ¬R ) ∧ A ∧ ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

( Q → ¬R ) ∧ A ∧ ¬ P = 0

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В , и переставим множители согласно закону коммутативности умножения:

A ∧ (¬ Q  ¬R ) ∧ ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

A ∧ ( ¬ Q  ¬R ) ∧ ¬ P = 0

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 0 и найдем, чему равно ¬А :

¬А = (¬ Q  ¬R ) ∧ ¬ P

Решение задачи на отрезки

3) Решение логического уравнения

¬А = (¬ Q  ¬R ) ∧ ¬ P

3.3. Упростим выражение для ¬А по закону де Моргана ¬А  ¬В=¬(А  В) :

¬А = ¬ (Q  R ) ∧ ¬ P,

и по другому закону де Моргана ¬А  ¬В =¬(А  В ) :

¬А = ¬ (Q  R  P)

Решение задачи на отрезки

3) Решение логического уравнения

¬А = ¬ (Q  R  P)

3.4. Очевидно, что

А = Q  R  P

Решение задачи на отрезки

4) Интерпретация полученного результата

А = Q  R  P

Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р .

Решение задачи на отрезки

Пересечение отрезков R и Q можно визуализировать: Q=[15,30] и R=[25,40].

30

25

40

15

Отрезок P=[10,25] нанесем на наш чертеж и объединим с пересечением:

25

30

15

40

10

Решение задачи на отрезки

А = Q  R  P

40

25

30

10

15

По условию нашей задачи, нам нужна максимальная длина отрезка А . Находим ее: 30 – 10 = 20 .

Ответ: 20 .

Ответ на сайте Полякова К.Ю.: 20

27

2. Задания на множества

(№ 386) Элементами множеств А, P, Q являются натуральные числа, причём P={1,2,3,4,5,6}, Q={3,5,15}. Известно, что выражение (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

истинно (т.е. принимает значение 1 при любом значении переменной х. Определите наименьшее возможное количество элементов в множестве A.

Источник - сайт Полякова К.Ю.

Решение задачи на множества

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на множества

• Легенда

A = x ∈ A

P = x ∈ P

Q = x ∈ Q

Решение задачи на множества

2) Формализация условия

Было:

(x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1

Стало:

¬ A → (¬P ∧ Q)  ¬ Q = 1

Решение задачи на множества

3) Решение логического уравнения

¬ A → (¬P ∧ Q)  ¬ Q = 1

3.1. Представим логическое следование в базовых логических операциях и сгруппируем:

A  ((¬P ∧ Q)  ¬ Q) = 1

Решение задачи на множества

A  (( ¬P ∧ Q)  ¬Q) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = (¬P ∧ Q)  ¬Q

Решение задачи на множества

¬А = (¬P ∧ Q)  ¬Q

3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:

¬А = ( ¬P  ¬Q)  (Q  ¬Q)

Q  ¬Q = 1

¬А = ( ¬P  ¬Q)

Решение задачи на множества

¬А = ( ¬P  ¬Q)

По закону де Моргана:

¬А = ¬(P  Q)

3.4. Очевидно, что

А = P  Q

Решение задачи на множества

А = P  Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P =  1, 2, 3 , 4, 5 , 6  и Q = { 3 , 5 ,15}, таким образом A = { 3 , 5 }

и содержит только 2 элемента.

Ответ: 2

Ответ на сайте Полякова: 2

2. Задания на множества

(№ 368) Элементами множеств А, P, Q являются натуральные числа, причём P={2,4,6,8,10,12} и Q={4,8,12,116}. Известно, что выражение (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

истинно (т. е. принимает значение 1 ) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Источник - сайт Полякова К.Ю.

Решение задачи на множества

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на множества

• Легенда

A = x ∈ A

P = x ∈ P

Q = x ∈ Q

Решение задачи на множества

2) Формализация условия

Было:

(x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1

Стало:

P → ((Q ∧ ¬ A) → ¬ P) = 1

Решение задачи на множества

3) Решение логического уравнения

P → ((Q ∧ ¬ A) → ¬ P) = 1

3.1. Представим первое логическое следование (в скобках) в базовых логических операциях :

P → ( ¬ (Q ∧ ¬ A)  ¬ P) = 1

Решение задачи на множества

P → ( ¬ (Q ∧ ¬ A)  ¬ P) = 1

Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:

¬ P  ( ¬ (Q ∧ ¬ A)  ¬ P) = 1

¬ P  ¬ Q  A  ¬ P = 1

Решение задачи на множества

A  ( ¬ P  ¬ Q  ¬ P) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = ( ¬ P  ¬ Q  ¬ P)

Решение задачи на множества

¬А = ¬ P  ¬ Q  ¬ P

3.3. Упростим выражение для ¬А по формуле А  А = А :

¬А = ¬ P  ¬ Q

Далее, по закону де Моргана получаем:

¬А = ¬( P  Q)

Решение задачи на множества

¬А = ¬(P  Q)

3.4. Очевидно, что

А = P  Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P =  2, 4 , 6, 8 , 10, 12  и

Q = { 4 , 8 , 12 , 16}, таким образом

A = { 4 , 8 , 12 }

и содержит только 3 элемента, сумма которых 4+8+12=24 .

Ответ: 24

Ответ на сайте Полякова: 24

3. Задания на поразрядную конъюнкцию

(№ 379) Обозначим через m & n пораз-рядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14 & 5 = 1110 2  & 0101 2  = 0100 2  = 4. Для какого наименьшего неотрицательного целого числа А формула (x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0))

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение задачи на поразрядную конъюнкцию

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

• Легенда

Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:

B = (x & 29 ≠ 0) 

C = (x & 12  ≠  0)

A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

Мы принимаем за истинное высказывание поразрядную конъюнкцию, отличную от нуля, иначе поразрядная конъюнкция теряет свой логический смысл, т.к. всегда можно представить Х всеми нулями.

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

Было:

(x & 29 ≠ 0)→((x & 12 = 0)→(x & А ≠ 0))=1

Стало:

В → ( ¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → ( ¬С → А) = 1

В → (С  А) = 1

(¬В  С)  А = 1

¬А = ¬В  С

¬А = ¬(В  ¬ С)

Очевидно, что

А = В  ¬ С

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С .

Решение задачи на поразрядную конъюнкцию

B = (x & 29 ≠ 0)

В или 29 = 11101 2  

C = (x & 12  ≠  0)

12 = 1100 2

¬С или инверсия 12 = 0011 2

Решение задачи на поразрядную конъюнкцию

В или 29 = 11101 2  

¬С или инверсия 12 = 0011 2

А = В  ¬ С

х 11101 2

0011 2

10001 2

А = 1 0001 2 = 17

Ответ на сайте Полякова: 17

27

3. Задания на поразрядную конъюнкцию

(№ 375) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответ-ствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Решение задачи на поразрядную конъюнкцию

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

• Легенда

Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:

B = (x & 49 ≠ 0) 

C = (x & 33 ≠  0)

A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

Было:

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

Стало:

В → ( ¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → ( ¬С → А) = 1

В → (С  А) = 1

(¬В  С)  А = 1

¬А = (¬В  С)

Очевидно:

А = В  ¬С

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С .

Решение задачи на поразрядную конъюнкцию

B = (x & 49 ≠ 0)

В или 49 = 110001 2  

C = (x & 33  ≠  0)

33 = 100001 2

¬С или инверсия 33 = 011110 2

Решение задачи на поразрядную конъюнкцию

В или 49 = 110001 2

¬С или инверсия 33 = 011110 2

А = В  ¬ С

х 110001 2

011110 2

010000 2

А = 1 0000 2 = 16

Ответ на сайте Полякова: 16

27

4. Задания на условие делимости

(№ 372) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула ¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Источник - сайт Полякова К.Ю.

Решение задачи

на условие делимости

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи

на условие делимости

• Легенда

Легенда простая: А = ДЕЛ(x,А)

21 = ДЕЛ(х,21)

35 = ДЕЛ(x,35)

Решение задачи

на условие делимости

2) Формализация условия

Было:

¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

тождественно истинна (то есть принимает значение 1)

Стало:

¬А → (¬21 ∧ ¬35) = 1

Решение задачи

на условие делимости

3) Решение логического уравнения

¬А → (¬21 ∧ ¬35) = 1

А  (¬21 ∧ ¬35) = 1

¬А = ¬21 ∧ ¬35

Очевидно, что

А = 21  35

Решение задачи

на условие делимости

4) Интерпретация полученного результата

А = 21  35

В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …

Решение задачи

на условие делимости

4) Интерпретация полученного результата

А = 21  35

Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем

А = НОД (21, 35) = 7

Ответ на сайте Полякова: 7

4. Задания на условие делимости

(№ 370) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула ¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Источник - сайт Полякова К.Ю.

Решение задачи

на условие делимости

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи

на условие делимости

• Легенда

А = ДЕЛ(x,А)

6 = ДЕЛ(x,6)

4 = ДЕЛ(x,4)

Решение задачи

на условие делимости

2) Формализация условия

Было:

¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна (то есть принимает значение 1

Стало:

¬А → (6 → ¬4) = 1

Решение задачи

на условие делимости

3) Решение логического уравнения

¬А → (6 → ¬4) = 1

¬А → (¬ 6  ¬4) = 1

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

А = 6  4

Решение задачи

на условие делимости

4) Интерпретация полученного результата

А = 6  4

Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12

Ответ на сайте Полякова: 12

Рефлексия

Оцените, пожалуйста, свой уровень понимания, достигнутый на занятии, по шкале от 0 до 10.

Сможете ли Вы теперь объяснить решение задания 18 своим ученикам или друзьям?

(да, нет, не знаю).

Спасибо за внимание!