логика в задачах ЕГЭ // Информатика, № 10, 2015, с. 38-42.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Множества и логика в задачах ЕГЭ по информатике презентация
Содержание
- 1. Множества и логика в задачах ЕГЭ по информатике
- 2. Постановка задачи На числовой прямой даны два
- 3. Постановка задачи Для какого наибольшего натурального числа
- 4. Что нужно знать о множествах?
- 5. Что нужно знать о множествах? A·B –
- 6. Множества и логические функции Множество задаётся логической
- 7. Базовые задачи (ЕГЭ) Задача 1. Каким должно
- 8. Базовые задачи (ЕГЭ) Задача 2. Каким должно
- 9. Общий подход к решению Свести задачу к
- 10. Задачи с отрезками На числовой прямой даны
- 11. Задачи с отрезками Упрощение выражения: ⇐
- 12. Задачи с отрезками-II На числовой прямой даны
- 13. Задачи с отрезками-II Упрощение выражения: ⇐
- 14. Множества чисел Элементами множеств А, P и
- 15. Множества чисел ⇐ Задача 1 Решение:
- 16. Множества чисел-II Элементами множеств А, P
- 17. Множества чисел-II ⇐ Задача 2 Решение:
- 18. Делимость Для какого наибольшего натурального числа a
- 19. Делимость ⇐ Задача 1 Решение:
- 20. Amin ← amax Почему максимальное число a дает минимальное множество A?
- 21. Делимость-II Для какого наибольшего натурального числа a
- 22. Делимость-II ⇐ Задача 1 Решение: Упрощение
- 23. Делимость-III Для какого наименьшего натурального числа a
- 24. Делимость-III ⇐ Задача 2 Решение: Упрощение
- 25. Делимость-III Переход к
- 26. Делимость-IV Для какого наименьшего натурального числа a
- 27. Делимость-IV Делится
- 28. Делимость-V Для какого наименьшего натурального числа a
- 29. Делимость-IV ⇐ Задача 2 Решение:
- 30. Побитовые логические операции ZN = (x ∈
- 31. Побитовые логические операции Что такое Z53: Биты
- 32. Главная ошибка После упрощения: Вывод: Логические значения! Натуральные числа!
- 33. Побитовые логические операции Биты 5, 4, 2,
- 34. Побитовые логические операции Биты 5, 4, 2,
- 35. Побитовые логические операции Двойственность операций
- 36. Побитовые логические операции Биты 4, 2 и
- 37. Побитовые логические операции Если в числе x
- 38. Побитовые логические операции Вариант 1: Вариант 2:
- 39. Побитовые логические операции Вариант 1: Вариант 2:
- 40. Побитовые логические операции Метод А.В. Здвижковой (г. Армавир):
- 41. Побитовые логические операции Решение: Биты 5, 3,
- 42. Побитовые логические операции-II Заданное условие: Определите
- 43. Побитовые логические операции-II Упрощение выражения (до суммы):
- 44. Побитовые логические операции-III Определите наибольшее натуральное
- 45. Побитовые логические операции-III Упрощение выражения: Решение:
- 46. Побитовые логические операции-IV Определите наименьшее натуральное
- 47. Побитовые операции–IV Упрощение выражения: Решение:
- 48. Побитовые логические операции (V) (А.Г. Гильдин). Определите
- 49. Побитовые логические операции (V) Упрощение выражения:
- 50. Побитовые логические операции (VI) (М.В. Кузнецова). Определите
- 51. Побитовые логические операции (V) Упрощение выражения:
- 52. Побитовые логические операции (V) Вариант с другими
- 53. Побитовые логические операции (VI) Определите наименьшее натуральное
- 54. или Побитовые логические операции (V) Упрощение выражения:
- 55. Нерешаемая задача Попытка решения: Логическое ИЛИ между битами! 1
- 56. Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru
Слайд 2Постановка задачи
На числовой прямой даны два отрезка: P = [37; 60]
и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х.
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х.
Элементами множеств А, P и Q являются натуральные числа, причём
P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}.
Известно, что выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
Слайд 3Постановка задачи
Для какого наибольшего натурального числа А выражение
¬ДЕЛ(x, А) → (ДЕЛ(x,
6) → ¬ДЕЛ(x, 4))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?
Определите наименьшее натуральное число A, такое что выражение
(x & 53 ≠ 0) → ((x & 41 = 0) → (x & A ≠ 0))
тождественно истинно?
Слайд 4
Что нужно знать о множествах?
A
(все натуральные)
U – универсальное
множество
– дополнение A до универсального множества
(НЕ делятся на 6)
Слайд 6Множества и логические функции
Множество задаётся логической функцией
x ∈ A
⇔
x ∈ A·B
⇔ x ∈ A+B
⇔ A(x) = 1
Слайд 7Базовые задачи (ЕГЭ)
Задача 1. Каким должно быть множество A для того,
чтобы множество A + B совпадало с универсальным множеством?
Другие решения:
Слайд 8Базовые задачи (ЕГЭ)
Задача 2. Каким должно быть множество A для того,
чтобы множество совпадало с универсальным множеством?
Слайд 9Общий подход к решению
Свести задачу к одной из базовых задач
Задача 1.
Задача 2.
Использовать готовое решение:
Задача 1.
Задача 2.
Задача 2.
Использовать готовое решение:
Задача 1.
Задача 2.
Слайд 10Задачи с отрезками
На числовой прямой даны два отрезка:
P = [37;
60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х.
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х.
P = (x ∈ P), Q = (x ∈ Q), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
Слайд 12Задачи с отрезками-II
На числовой прямой даны два отрезка:
P = [10;
20] и Q = [25; 55]. Укажите наибольшую возможную длину такого отрезка A, что выражение
(x ∈ A) → ((x ∈ P) ∨ (x ∈ Q))
истинно при любом значении переменной х.
(x ∈ A) → ((x ∈ P) ∨ (x ∈ Q))
истинно при любом значении переменной х.
P = (x ∈ P), Q = (x ∈ Q), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
Слайд 14Множества чисел
Элементами множеств А, P и Q являются натуральные числа, причём
P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}.
Известно, что выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
P = (x ∈ P), Q = (x ∈ Q), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
Слайд 15Множества чисел
⇐ Задача 1
Решение:
P = {2, 4, 6, 8, 10, 12},
Q = {4, 8, 12, 116}
Упрощение выражения:
Слайд 16
Множества чисел-II
Элементами множеств А, P и Q являются натуральные числа, причём
P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }.
Известно, что выражение
((x ∈ A) → ¬(x ∈ P)) ∧ (¬(x ∈ Q) → ¬(x ∈ A))
истинно при любом значении переменной х. Определите наибольшее возможное количество элементов множества A.
P = (x ∈ P), Q = (x ∈ Q), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
Слайд 17Множества чисел-II
⇐ Задача 2
Решение:
P = { 2, 4, 6, 8, 10,
12, 14, 16, 18, 20}
Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }
Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }
Упрощение выражения:
Слайд 18Делимость
Для какого наибольшего натурального числа a выражение
¬ДЕЛ(x, a) → (ДЕЛ(x, 6)
→ ¬ДЕЛ(x, 4))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?
DN = (x ∈ DN), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Слайд 19
Делимость
⇐ Задача 1
Решение:
D6∙D4 ≤ A=Da
Упрощение выражения:
Одновременно делятся
на 6 и на
4!
D6∙D4 = D12
любой делитель 12!
max
Слайд 21Делимость-II
Для какого наибольшего натурального числа a выражение
¬ДЕЛ(x, a) → (¬ ДЕЛ(x,
21) ∧ ¬ДЕЛ(x, 35))
тождественно истинно?
тождественно истинно?
DN = (x ∈ DN), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Слайд 22Делимость-II
⇐ Задача 1
Решение:
Упрощение выражения:
Делятся
на 21 или на 35!
D21+D35 = Da
нет
такого a!
max
D21+D35 < Da
Общий делитель 21 и 35!
Слайд 23Делимость-III
Для какого наименьшего натурального числа a выражение
ДЕЛ(x, a) → (¬ ДЕЛ(x,
21) ∨ ДЕЛ(x, 35))
тождественно истинно?
тождественно истинно?
DN = (x ∈ DN), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Слайд 24Делимость-III
⇐ Задача 2
Решение:
Упрощение выражения:
Не делятся
на 21 или делятся на 35!
нет
такого a!
Слайд 25
Делимость-III
Переход к другой импликации:
Делится на A и на 21:
Делится на 35:
Этот
сомножитель добавляется с помощью A!
min
k, m – натуральные
Слайд 26Делимость-IV
Для какого наименьшего натурального числа a выражение
(ДЕЛ(x, a) ∧ ДЕЛ(x, 21))
→ ДЕЛ(x, 18)
тождественно истинно?
тождественно истинно?
DN = (x ∈ DN), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Слайд 28Делимость-V
Для какого наименьшего натурального числа a выражение
¬ДЕЛ(x, 18) → (¬ДЕЛ(x,21) →
¬ДЕЛ(x, a))
тождественно истинно?
тождественно истинно?
DN = (x ∈ DN), A = (x ∈ A)
Вводим утверждения:
Заданное условие:
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Слайд 30Побитовые логические операции
ZN = (x ∈ ZN), A = (x
∈ Za)
Вводим утверждения:
Заданное условие:
Определите наименьшее натуральное число a, такое что выражение
(x & 53 ≠ 0) → ((x & 41 = 0) → (x & a ≠ 0))
тождественно истинно.?
Число a определяет множество Za или условие A.
Слайд 31Побитовые логические операции
Что такое Z53:
Биты 5, 4, 2, 0 числа x
нулевые!
Среди битов 5, 4, 2, 0 числа x есть ненулевые!
Слайд 33Побитовые логические операции
Биты 5, 4, 2, 0 числа x нулевые!
Z30 ⇒
Биты 4, 3, 2, 1 числа x нулевые!
Z53 ⇒
63 = 111111 = 53 or 30
Слайд 34Побитовые логические операции
Биты 5, 4, 2, 0 числа x нулевые!
Z30 ⇒
Биты 4, 3, 2, 1 числа x нулевые!
Z53 ⇒
20 = 010100 = 53 and 30
Только в одну сторону!
Слайд 35
Побитовые логические операции
Двойственность операций И и ИЛИ
только для левой части импликации!
Доказательство:
От
противного:
Слайд 37Побитовые логические операции
Если в числе x не равен 0 хотя бы
один бит, который равен 1 в b or c
Слайд 41Побитовые логические операции
Решение:
Биты 5, 3, 0 нулевые!
Биты 5, 4, 2, 0
нулевые!
amin = 101002 = 20
Логическое ИЛИ между битами!
Слайд 42Побитовые логические операции-II
Заданное условие:
Определите наибольшее натуральное число a, такое что выражение
(x
& a ≠ 0) → ((x & 20 = 0) → (x & 5 ≠ 0))
тождественно истинно.
тождественно истинно.
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 43Побитовые логические операции-II
Упрощение выражения (до суммы):
Решение:
Импликация без инверсий:
5
= 00101
Биты 4, 2 нулевые!
Биты 2, 0 нулевые!
amax = 101012 = 21
a = 1, 4, 5, 16, 17, 20, 21
23 – 1 = 7
Слайд 44Побитовые логические операции-III
Определите наибольшее натуральное число a, такое что выражение
(x &
a ≠ 0) → ((x & 12 = 0) → (x & 21 = 0))
тождественно истинно.
тождественно истинно.
Заданное условие:
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 45
Побитовые логические операции-III
Упрощение выражения:
Решение:
amax = 11002 = 12
21 =
10101
a = 4, 8, 12
22 – 1 = 3
Слайд 46Побитовые логические операции-IV
Определите наименьшее натуральное число a, такое что выражение
( (x & 28 ≠ 0) ∨ (x & 45 ≠ 0))
→ ((x & 48 = 0) → (x & a ≠ 0))
тождественно истинно.
→ ((x & 48 = 0) → (x & a ≠ 0))
тождественно истинно.
Заданное условие:
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 48Побитовые логические операции (V)
(А.Г. Гильдин). Определите наименьшее натуральное число a, такое
что выражение
(x & 19 = 0) ∧ (x & 38 ≠ 0) ∨
((x & 43 = 0) → ((x & a = 0) ∧ (x & 43 = 0)))
тождественно истинно.
(x & 19 = 0) ∧ (x & 38 ≠ 0) ∨
((x & 43 = 0) → ((x & a = 0) ∧ (x & 43 = 0)))
тождественно истинно.
Заданное условие:
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 49
Побитовые логические операции (V)
Упрощение выражения:
Решение:
a = 1, 2, 3, 8, 9,
10, 11,
32, 33, 34, 35, 40, 41, 42, 43
Все, у которых единицы только в разрядах 5, 3, 1 и 0!
24 – 1 = 15
Слайд 50Побитовые логические операции (VI)
(М.В. Кузнецова). Определите наименьшее натуральное число a, такое
что выражение
(( (x & 13 ≠ 0) ∨ (x & a ≠ 0)) → (x & 13 ≠ 0)
∨ ((x & a ≠ 0) ∧ (x & 39 = 0))
тождественно истинно.
(( (x & 13 ≠ 0) ∨ (x & a ≠ 0)) → (x & 13 ≠ 0)
∨ ((x & a ≠ 0) ∧ (x & 39 = 0))
тождественно истинно.
Заданное условие:
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 51
Побитовые логические операции (V)
Упрощение выражения:
Решение:
a = 1, 4, 5, 8, 9,
12, 13
39 = 100111
Слайд 53Побитовые логические операции (VI)
Определите наименьшее натуральное число a, такое что выражение
((x
& 23 ≠ 0) ∧ (x & 45 ≠ 0)) →
((x & a ≠ 0) ∧ (x & 23 ≠ 0))
тождественно истинно.
((x & a ≠ 0) ∧ (x & 23 ≠ 0))
тождественно истинно.
Заданное условие:
ZN = (x ∈ ZN), A = (x ∈ Za)
Вводим утверждения:
Слайд 56Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru
