Презентация "Теория и практика решения задания 18 ЕГЭ по информатике" – проект, доклад

Автор: учитель информатики МБОУ «Лицей» первой квалификационной категории Мурзина Ольга Ивановна

МБОУ «Лицей» г. Арзамас МКУ ГИМК

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

Арзамас, 2017

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

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

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

Решающая формула А  ¬А = 1 А  ¬А = 0

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

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

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

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

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

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

4 12 20

По условию нашей задачи, нам нужна минимальная длина отрезка А. Находим ее: 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 при любом значении переменной х. Выбор решающей формулы очевиден:

Легенда

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

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

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

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

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

¬А = ¬ (Q  R  P)

3.4. Очевидно, что А = Q  R  P

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

А = Q  R  P

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

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

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

10

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

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

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

(№ 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.

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 = 11102 & 01012 = 01002 = 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 = 111012 C = (x & 12 ≠ 0) 12 = 11002 ¬С или инверсия 12 = 00112

В или 29 = 111012 ¬С или инверсия 12 = 00112 А = В ¬ С х111012 00112 100012 А = 100012 = 17

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

(№ 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 ¬А = (¬В  С) Очевидно: А = В ¬С

B = (x & 49 ≠ 0) В или 49 = 1100012 C = (x & 33 ≠ 0) 33 = 1000012 ¬С или инверсия 33 = 0111102

В или 49 = 1100012 ¬С или инверсия 33 = 0111102 А = В ¬ С х1100012 0111102 0100002 А = 100002 = 16

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

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

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

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

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

Было: ¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

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

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

¬А → (¬21 ∧ ¬35) = 1 А (¬21 ∧ ¬35) = 1 ¬А = ¬21 ∧ ¬35 Очевидно, что А = 21  35

4) Интерпретация полученного результата А = 21  35 В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …

4) Интерпретация полученного результата А = 21  35 Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем А = НОД (21, 35) = 7

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

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

Легенда А = ДЕЛ(x,А) 6 = ДЕЛ(x,6) 4 = ДЕЛ(x,4)

Было: ¬ДЕЛ(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 своим ученикам или друзьям? (да, нет, не знаю).

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