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

Автор:

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

первой квалификационной категории

Мурзина Ольга Ивановна

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

МКУ ГИМК

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

Арзамас, 2017

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

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

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

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

А  ¬А = 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].

4

12

15

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

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

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

принимает значение 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].

15

25

30

40

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

15

25

30

40

10

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

15

25

30

40

10

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

Ответ: 20.

А = Q  R  P

Ответ на сайте Полякова К.Ю.: 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

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

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 = 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)

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

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

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

Было:

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

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

тождественно истинна (то есть принимает значение 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 своим ученикам или друзьям?

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

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