Множества и логика в задачах ЕГЭ по информатике

1. Множества и логика в задачах ЕГЭ по информатике

К.Ю. Поляков
Множества и логика
в задачах ЕГЭ по
информатике
Множества и логика в задачах ЕГЭ //
Информатика, № 10, 2015, с. 38-42.
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

2. Постановка задачи

Множества и логика в задачах ЕГЭ по информатике
2
Постановка задачи
На числовой прямой даны два отрезка: P = [37; 60] и Q =
[40; 77]. Укажите наименьшую возможную длину такого
отрезка A, что выражение
(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.
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

3. Постановка задачи

Множества и логика в задачах ЕГЭ по информатике
3
Постановка задачи
Для какого наибольшего натурального числа А
выражение
¬ДЕЛ(x, А) (ДЕЛ(x, 6) ¬ДЕЛ(x, 4))
тождественно истинно (то есть принимает
значение 1 при любом натуральном значении
переменной х)?
Определите наименьшее натуральное число A,
такое что выражение
(x & 53 0) ((x & 41 = 0) (x & A 0))
тождественно истинно?
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

4. Что нужно знать о множествах?

Множества и логика в задачах ЕГЭ по информатике
4
Что нужно знать о множествах?
U – универсальное
множество
(все натуральные)
A
(делятся на 6)
A – дополнение A до
универсального множества
(НЕ делятся на 6)
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

5. Что нужно знать о множествах?

Множества и логика в задачах ЕГЭ по информатике
5
Что нужно знать о множествах?
A
B
A·B – пересечение (A B)
A
B
A+B – объединение (A B)
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

6. Множества и логические функции

Множества и логика в задачах ЕГЭ по информатике
6
Множества и логические функции
Множество задаётся логической функцией
A
x A
A(x) = 1
A
A( x) 1 x A
x A
A
B
A( x) B( x) 1 x A·B
A
B
A ( x) B( x) 1 x A+B
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

7. Базовые задачи (ЕГЭ)

Множества и логика в задачах ЕГЭ по информатике
7
Базовые задачи (ЕГЭ)
Задача 1. Каким должно быть множество A для того,
чтобы множество A + B совпадало с универсальным
множеством?
A B U A B 1
B A 1
Amin B
Другие решения:
A B
К.Ю. Поляков, 2016-2017
A B
http://kpolyakov.spb.ru

8. Базовые задачи (ЕГЭ)

Множества и логика в задачах ЕГЭ по информатике
8
Базовые задачи (ЕГЭ)
Задача 2. Каким должно быть множество A для того,
чтобы множество A B совпадало с универсальным
множеством?
A B U A B 1
B A 1
A B
A B
A B
A B
Amax B
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

9. Общий подход к решению

Множества и логика в задачах ЕГЭ по информатике
9
Общий подход к решению
1. Свести задачу к одной из базовых задач
Задача 1. A B 1
B A 1
Задача 2. A B 1 B A 1
2. Использовать готовое решение:
Задача 1. Amin B
Задача 2. Amax B
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

10. Задачи с отрезками

Множества и логика в задачах ЕГЭ по информатике
10
Задачи с отрезками
На числовой прямой даны два отрезка:
P = [37; 60] и Q = [40; 77]. Укажите наименьшую
возможную длину такого отрезка A, что
выражение
(x P) → (((x Q) ¬(x A)) → ¬(x P))
истинно при любом значении переменной х.
Вводим утверждения:
P = (x P), Q = (x Q),
A = (x A)
Заданное условие:
P (Q A P )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

11. Задачи с отрезками

Множества и логика в задачах ЕГЭ по информатике
11
Задачи с отрезками
Упрощение выражения:
P (Q A P ) P (Q A P)
P Q A P
P Q A
A B 1 Задача 1
Решение:
P Q
Amin B P Q P Q
P = [37; 60], Q = [40; 77]
Amin = [40; 60]
К.Ю. Поляков, 2016-2017
длина 20
http://kpolyakov.spb.ru

12. Задачи с отрезками-II

Множества и логика в задачах ЕГЭ по информатике
12
Задачи с отрезками-II
На числовой прямой даны два отрезка:
P = [10; 20] и Q = [25; 55]. Укажите наибольшую
возможную длину такого отрезка A, что
выражение
(x A) → ((x P) (x Q))
истинно при любом значении переменной х.
Вводим утверждения:
P = (x P), Q = (x Q),
A = (x A)
Заданное условие:
A ( P Q)
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

13. Задачи с отрезками-II

Множества и логика в задачах ЕГЭ по информатике
13
Задачи с отрезками-II
Упрощение выражения:
A ( P Q) A P Q
A B 1 Задача 2
P Q
Решение:
Amax B P Q
P = [10; 20], Q = [25; 55]
Нельзя перекрыть!
Q
P
10
20 25
Amax = [25; 55]
К.Ю. Поляков, 2016-2017
55
x
длина 30
http://kpolyakov.spb.ru

14. Задачи с отрезками-III

Множества и логика в задачах ЕГЭ по информатике
14
Задачи с отрезками-III
На числовой прямой даны два отрезка:
P = [10; 20] и Q = [25; 55]. Укажите наименьшую
возможную длину такого отрезка A, что
выражение
((x P) (x Q)) → (x A)
истинно при любом значении переменной х.
Вводим утверждения:
P = (x P), Q = (x Q),
A = (x A)
Заданное условие:
( P Q) A
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

15. Задачи с отрезками-III

Множества и логика в задачах ЕГЭ по информатике
15
Задачи с отрезками-III
Упрощение выражения:
( P Q) A A P Q
A B 1
Задача 1
P Q
Решение:
Amin B P Q
P
10
P = [10; 20], Q = [25; 55]
Нужно перекрыть!
Q
20 25
Amin = [10; 55]
К.Ю. Поляков, 2016-2017
55
x
длина 45
http://kpolyakov.spb.ru

16. Множества чисел

Множества и логика в задачах ЕГЭ по информатике
16
Множества чисел
Элементами множеств А, 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)
Заданное условие:
P (Q A P )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

17. Множества чисел

Множества и логика в задачах ЕГЭ по информатике
17
Множества чисел
Упрощение выражения:
P (Q A P ) P (Q A P)
P Q A P
P Q A
A B 1 Задача 1
Решение:
P Q
Amin B P Q P Q
P = {2, 4, 6, 8, 10, 12}, Q = {4, 8, 12, 116}
Amin = {4, 8, 12}
К.Ю. Поляков, 2016-2017
сумма 24
http://kpolyakov.spb.ru

18. Множества чисел-II

Множества и логика в задачах ЕГЭ по информатике
18
Множества чисел-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)
Заданное условие:
( A P ) ( Q A)
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

19. Множества чисел-II

Множества и логика в задачах ЕГЭ по информатике
19
Множества чисел-II
Упрощение выражения:
( A P ) (Q A) ( A P) (Q A)
A Q P Q A P A
A Q P Q A
A P Q
A B 1 Задача 2
Решение:
Amax B P Q
P Q
P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }
Amax = { 3, 9, 15, 21, 24, 27, 30 }
К.Ю. Поляков, 2016-2017
7 шт.
http://kpolyakov.spb.ru

20. Делимость

Множества и логика в задачах ЕГЭ по информатике
20
Делимость
Для какого наибольшего натурального числа a
выражение
¬ДЕЛ(x, a) (ДЕЛ(x, 6) ¬ДЕЛ(x, 4))
тождественно истинно (то есть принимает
значение 1 при любом натуральном значении
переменной х)?
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Вводим утверждения:
DN = (x DN), A = (x A)
Заданное условие: A (D6 D4 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

21. Делимость

Множества и логика в задачах ЕГЭ по информатике
21
Делимость
Упрощение выражения:
A (D6 D4 )
A ( D 6 D4 )
A D6 D4
A B 1 Задача 1
D6 D 4
Решение:
Amin B D6 D4 D6 D4
D6·D4 = D12
D6·D4 A=Da
Одновременно
делятся
на 6 и на 4!
12
любой делитель 12!
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

22. Amin  amax

Множества и логика в задачах ЕГЭ по информатике
22
Amin amax
Почему максимальное число a дает
минимальное множество A?
a=6
0
6
12
18
24
30
36
x
a=12
0
12
24
36
x
0
12
24
36
x
a=24
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

23. Делимость-II

Множества и логика в задачах ЕГЭ по информатике
23
Делимость-II
Для какого наибольшего натурального числа a
выражение
¬ДЕЛ(x, a) (¬ ДЕЛ(x, 21) ¬ДЕЛ(x, 35))
тождественно истинно?
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Вводим утверждения:
DN = (x DN), A = (x A)
Заданное условие:
A (D21 D35 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

24. Делимость-II

Множества и логика в задачах ЕГЭ по информатике
24
Делимость-II
Упрощение выражения:
A (D21 D35 )
A D21 D35
A B 1 Задача 1
D21 D35
Решение:
Делятся
Amin B D21 D35 D21 D35 на 21 или на 35!
D21+D35 = Da
D21+D35 < Da
нет такого a!
max
Общий делитель 21 и 35!
К.Ю. Поляков, 2016-2017
7
http://kpolyakov.spb.ru

25. Делимость-III

Множества и логика в задачах ЕГЭ по информатике
25
Делимость-III
Для какого наименьшего натурального числа a
выражение
ДЕЛ(x, a) (¬ ДЕЛ(x, 21) ДЕЛ(x, 35))
тождественно истинно?
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Вводим утверждения:
DN = (x DN), A = (x A)
Заданное условие:
A (D21 D35 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

26. Делимость-III

Множества и логика в задачах ЕГЭ по информатике
26
Делимость-III
Упрощение выражения:
A (D21 D35 )
A D21 D35
A B 1 Задача 2
D21 D35
Решение:
Amax B D21 D35
D21 D35 Da
нет такого a!
Не делятся
на 21 или
делятся на 35!
D21 D35 A Da
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

27. Делимость-III

Множества и логика в задачах ЕГЭ по информатике
27
Делимость-III
Переход к другой импликации:
!
A D21 D35 ( A D 21 ) D35
Если число делится на a и на 21, оно должно
делиться на 35!
Делится на A и на 21:
x a k 21 m 3 7 m
Делится на 35:
x 35 q 5 7 q
k, m – натуральные
a 5 r
min
Этот сомножитель
добавляется с
помощью A!
К.Ю. Поляков, 2016-2017
5
http://kpolyakov.spb.ru

28. Делимость-IV

Множества и логика в задачах ЕГЭ по информатике
28
Делимость-IV
Для какого наименьшего натурального числа a
выражение
(ДЕЛ(x, a) ДЕЛ(x, 21)) ДЕЛ(x, 18)
тождественно истинно?
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Вводим утверждения:
DN = (x DN), A = (x A)
Заданное условие:
( A D21 ) D18
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

29. Делимость-IV

Множества и логика в задачах ЕГЭ по информатике
29
Делимость-IV
( A D21 ) D18
!
Если число делится на A и на 21, оно должно
делиться на 18!
Делится на A и на 21:
x a k 21 m 3 7 m
Делится на 18:
x 18 q 2 3 3 q
Эти сомножители
добавляются с
помощью A!
К.Ю. Поляков, 2016-2017
a 2 3 3 r
min
18
http://kpolyakov.spb.ru

30. Делимость-V

Множества и логика в задачах ЕГЭ по информатике
30
Делимость-V
Для какого наименьшего натурального числа a
выражение
¬ДЕЛ(x, 18) (¬ДЕЛ(x,21) ¬ДЕЛ(x, a))
тождественно истинно?
DN – множество чисел, делящихся на N
A = Da – множество чисел, делящихся на a
Вводим утверждения:
DN = (x DN), A = (x A)
Заданное условие:
D18 ( D21 A )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

31. Делимость-IV

Множества и логика в задачах ЕГЭ по информатике
31
Делимость-IV
D18 ( D21 A )
D18 D21 A
A B 1 Задача 2
D18 D21
Решение:
Amax B D18 D21
D18 D21 Da
нет такого a!
D18 D21 A Da
!
Нельзя перекрывать
другие числа!
К.Ю. Поляков, 2016-2017
Делятся
на 18 или
на 21!
Варианты:
A D18 , D36 , ...
A D21, D42 , ...
http://kpolyakov.spb.ru

32. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
32
Побитовые логические операции
Определите наименьшее натуральное число a,
такое что выражение
(x & 53 0) ((x & 41 = 0) (x & a 0))
тождественно истинно.?
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
Число a
ZN = (x ZN), A = (x Za)
определяет
множество Za или
Заданное условие:
Z53 (Z 41 A)
К.Ю. Поляков, 2016-2017
условие A.
http://kpolyakov.spb.ru

33. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
33
Побитовые логические операции
Что такое Z53:
биты 5 4 3 2 1 0
53 = 110101
x = abcdef
x & 53 = ab0d 0f = 0
Что такое Z 53 :
биты 5 4 3 2 1 0
53 = 110101
x = abcdef
x & 53 = ab0d 0f 0
К.Ю. Поляков, 2016-2017
Биты 5, 4, 2, 0 числа x
нулевые!
Среди битов 5, 4, 2, 0 числа
x есть ненулевые!
http://kpolyakov.spb.ru

34. Главная ошибка

Множества и логика в задачах ЕГЭ по информатике
34
Главная ошибка
После упрощения:
биты 5 4 3 2 1 0
21 = 010101
11 = 001011
Вывод:
Z 21 Z11 A 1
Натуральные
числа!
21 or 11 or a 1
a 21 or 11
a 21 or 11 20
К.Ю. Поляков, 2016-2017
!
Логические
значения!
Это ИНОГДА
проходит!
? Это min или max?
http://kpolyakov.spb.ru

35. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
35
Побитовые логические операции
Z53 Z30 ?
биты 5 4 3 2 1 0
53 = 110101 Z53
30 = 011110 Z30
63 = 111111 = 53 or 30
Биты 5, 4, 2, 0 числа x
нулевые!
Биты 4, 3, 2, 1 числа x
нулевые!
Z53 Z30 Z 63 Z 53 or 30
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

36. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
36
Побитовые логические операции
Z53 Z30 ?
биты 5 4 3 2 1 0
53 = 110101 Z53
30 = 011110 Z30
20 = 010100 = 53 and 30
Биты 5, 4, 2, 0 числа x
нулевые!
Биты 4, 3, 2, 1 числа x
нулевые!
Z53 Z30 Z 20 Z 53 and 30
Только в одну сторону!
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

37. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
37
Побитовые логические операции
Z b Z c Z b or c
Z b Z c Z b and c
К.Ю. Поляков, 2016-2017
Двойственность
операций И и ИЛИ
только для левой
части импликации!
http://kpolyakov.spb.ru

38. Замена

Множества и логика в задачах ЕГЭ по информатике
39
Побитовые логические операции
Биты 4, 2 и 0
нулевые!
Биты 4 и 0 нулевые!
Zb Z c 1
биты 4 3 2 1 0
биты 4 3 2 1 0
Zb : 21 = 10101
Z c : 17 = 10001
! Множество единичных битов c входит во
множество единичных битов b!
Z 21 Z 7 0
?
биты 4 3 2 1 0
биты 4 3 2 1 0
Zb : 21 = 10101
1
Z c : 7 = 00111
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

39. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
40
Побитовые логические операции
Zb ( A Z c ) ?
Z b ( A Z c ) ( Z b A) ( Z b Z c )
Вариант 1:
Zb Z c 1
! a – любое!
Вариант 2:
Zb Z c 0 Zb A 1
! Множество единичных битов a входит во
множество единичных битов b!
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

40. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
41
Побитовые логические операции
Метод А.В. Здвижковой (г. Армавир):
!
Строим импликацию так, чтобы избавиться
от всех инверсий!
Z53 (Z 41 A)
К.Ю. Поляков, 2016-2017
Z 53 (Z 41 A )
Z 53 Z 41 A
Z41 A Z53
(Z 41 A) Z53
http://kpolyakov.spb.ru

41. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
42
Побитовые логические операции
(Z 41 A) Z53
Решение:
Логическое
ИЛИ между
битами!
биты 5 4 3 2 1 0
41 = 101001
a = ??????
1 1
53 = 110101
amin = 101002 = 20
К.Ю. Поляков, 2016-2017
Биты 5, 3, 0
нулевые!
Биты 5, 4, 2, 0
нулевые!
? Другие a?
http://kpolyakov.spb.ru

42. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
43
Побитовые логические операции-II
Определите наибольшее натуральное число a,
такое что выражение
(x & a 0) ((x & 20 = 0) (x & 5 0))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
A (Z 20 Z5 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

43. Побитовые логические операции-II

Множества и логика в задачах ЕГЭ по информатике
44
Побитовые логические операции-II
Упрощение выражения (до суммы):
A (Z 20 Z5 ) A (Z 20 Z5 )
A Z 20 Z5 Z20 Z5 A
Импликация без инверсий: (Z 20 Z5 ) A
Решение:
биты 4 3 2 1 0
Биты 4, 2 нулевые!
Z 20 : 20 = 10100
Z 5 : 5 = 00101
amax = 101012 = 21
a = 1, 4, 5, 16, 17, 20, 21
Биты 2, 0 нулевые!
? Другие a?
? Сколько?
23 – 1 = 7
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

44. Побитовые логические операции-II

Множества и логика в задачах ЕГЭ по информатике
45
Побитовые логические операции-III
Определите наибольшее натуральное число a,
такое что выражение
(x & a 0) ((x & 12 = 0) (x & 21 = 0))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
A (Z12 Z 21 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

45. Побитовые логические операции-III

Множества и логика в задачах ЕГЭ по информатике
46
Побитовые логические операции-III
Упрощение выражения:
! От него
A (Z12 Z 21 ) A Z12 Z 21
ничего не
Z12 (A Z21 ) зависит!
Решение:
(Z12 A) (Z12 Z21)
биты 4 3 2 1 0
Z12 : 12 = 1100
Z21 : 21 = 1101011
Z12 A
0
amax = 11002 = 12
? Другие a?
a = 4, 8, 12
22 – 1 = 3
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

46. Побитовые логические операции-III

Множества и логика в задачах ЕГЭ по информатике
47
Побитовые логические операции-IV
Определите наименьшее натуральное число a,
такое что выражение
( (x & 28 0) (x & 45 0))
((x & 48 = 0) (x & a 0))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
( Z 28 Z 45 ) (Z 48 A )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

47. Побитовые логические операции-IV

Множества и логика в задачах ЕГЭ по информатике
48
Побитовые операции–IV
Упрощение выражения:
( Z 28 Z 45 ) (Z 48 A )
Решение:
(Z28 Z45 ) (Z48 A)
Z 48 A Z 28 Z 45
биты 5 4 3 2 1 0
Z 28 : 28 = 11100
Z 45 : 45 = 101101
Z 61
Z 28 Z 45 :
= 111101
Z 48 : 48 = 110000
Z 61 :
К.Ю. Поляков, 2016-2017
11 1
a = ??????
= 111101
Логическое ИЛИ
между битами!
? Другие a?
amin = 11012 = 13
http://kpolyakov.spb.ru

48. Побитовые операции–IV

Множества и логика в задачах ЕГЭ по информатике
49
Побитовые логические операции (V)
(А.Г. Гильдин). Определите наименьшее
натуральное число a, такое что выражение
(x & 19 = 0) (x & 38 0)
((x & 43 = 0) ((x & a = 0) (x & 43 = 0)))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
Z19 Z38 (Z 43 ( A Z 43 ))
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

49. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
50
Побитовые логические операции (V)
Упрощение выражения:
Z19 Z38 (Z 43 ( A Z 43 ))
Z19 Z38 Z 43 A Z 43
Z19 Z38 Z 43 A
Z 43 ( A Z19 Z38 )
(Z 43 A) (Z 43 Z19 Z38 )
? Что с этим
делать?
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

50. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
51
Побитовые логические операции
Zb (A Zc Zd ) ?
(Z b A) (Z b Z c ) (Z b Z d )
Вариант 1: Z b Z c 0
Zb A
Вариант 2: Z b Z c 1
(Z b A) (Z b Z d )
Zb A Z d (Z b Z d ) A
Z b or d A
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

51. Побитовые логические операции

Множества и логика в задачах ЕГЭ по информатике
52
Побитовые логические операции (V)
(Z 43 A) (Z 43 Z19 Z38 )
Z 43 Z19 0
биты 5 4 3 2 1 0
Z 43 : 43 = 101011
Z19 : 19 = 10011
Z 43 A
?
Какие подходят?
0
! Не влияют на
решение!
Все, у которых единицы
только в разрядах 5, 3, 1 и 0!
a = 1, 2, 3, 8, 9, 10, 11,
32, 33, 34, 35, 40, 41, 42, 43
К.Ю. Поляков, 2016-2017
24 – 1 = 15
http://kpolyakov.spb.ru

52. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
53
Побитовые логические операции (VI)
(М.В. Кузнецова). Определите наименьшее
натуральное число a, такое что выражение
(( (x & 13 0) (x & a 0)) (x & 13 0)
((x & a 0) (x & 39 = 0))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
(( Z13 A ) Z13 ) A Z 39
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

53. Побитовые логические операции (VI)

Множества и логика в задачах ЕГЭ по информатике
54
Побитовые логические операции (V)
Упрощение выражения:
(( Z13 A ) Z13 ) A Z 39
Z13 A Z13 A Z 39
(Z13 Z13 ) ( A Z13 ) A Z 39
A A Z 39 Z13
A Z 39 Z13 Z13 ( A Z 39 )
Z13 ( A Z39 ) (Z13 A) (Z13 Z39 )
Z13 A
Решение:
биты 5 4 3 2 1 0
13 =
1101
39 = 1100111
1
К.Ю. Поляков, 2016-2017
0
! Не влияет на
решение!
a = 1, 4, 5, 8, 9, 12, 13
http://kpolyakov.spb.ru

54. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
55
Побитовые логические операции (V)
Вариант с другими числами:
(( Z53 A ) Z53 ) A Z 21 Z53 ( A Z 21 )
(Z53 A) (Z53 Z 21 )
Решение:
биты 5 4 3 2 1 0
53 = 110101
21 = 10101
единичных
! Множество
битов числа 21 входит во
! Всегда 1!
a – любое!
множество единичных
битов числа 53!
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

55. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
56
Побитовые логические операции (VI)
Определите наименьшее натуральное число a,
такое что выражение
((x & 23 0) (x & 45 0))
((x & a 0) (x & 23 0))
тождественно истинно.
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
Заданное условие:
( Z 23 Z 45 ) ( A Z 23 )
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

56. Побитовые логические операции (VI)

Множества и логика в задачах ЕГЭ по информатике
57
Побитовые логические операции (V)
Упрощение выражения:
( Z 23 Z 45 ) ( A Z 23 ) Z 23 Z 45 A Z 23
(Z 23 A) (Z 23 Z 23 ) Z 45
A Z 23 Z 45
A (Z 23 Z 45 )
(A Z 23 ) ( A Z 45 )
( A Z 23 ) amin 23
или
( A Z 45 ) amin 45
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

57. Побитовые логические операции (V)

Множества и логика в задачах ЕГЭ по информатике
58
Нерешаемая задача
Z 43 A Z 48
Попытка решения:
биты 5 4 3 2 1 0
Z 43 : 43 = 101011
a = ??????
1
Z 48 : 48 = 110000
!
К.Ю. Поляков, 2016-2017
Логическое ИЛИ
между битами!
С помощью a можно добавить
биты, но нельзя убрать!
http://kpolyakov.spb.ru

58. Нерешаемая задача

Множества и логика в задачах ЕГЭ по информатике
59
Новая задача
Определите наименьшее (и наибольшее)
натуральное число a, такое что выражение
(x & 125 1) ((x & 34 = 2) (x & a = 0))
тождественно истинно.
!
Не ноль!
Вводим множества: ZN = {x: x & N = 0}
Z N {x : x & N 0}
Вводим утверждения:
ZN = (x ZN), A = (x Za)
? Что дальше?
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

59. Новая задача

Множества и логика в задачах ЕГЭ по информатике
60
Преобразование выражений
(x & b = c) = ?
(x & b c) = ?
Вариант 1:
(x & 10 = 1) = 0?
биты 3 2 1 0
10 = 1010
x = abcd
x & 10 = a0c 0 = 1
Единичные биты числа c
= 1 не входят во
множество единичных
битов числа b = 10!
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

60. Преобразование выражений

Множества и логика в задачах ЕГЭ по информатике
61
Преобразование выражений
(x & b = c) = ?
Вариант 2:
(x & 23 = 3) = ?
биты 4 3 2 1 0
23 = 10111
x = abcde
x & 23 = a0cde = 3
(x & b c) = ?
Единичные биты числа
c = 3 входят во множество
единичных битов числа b = 23!
a=c=0
d=e=1
( x & b c) Z b c Z c1 Z c2 Z cq
Z 20 1
Z1 0
Z2 0
Все биты числа c!
( x & b c) Z b c Z c1 Z c2 Z cq
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

61. Преобразование выражений

Множества и логика в задачах ЕГЭ по информатике
62
Новая задача
(x & 125 1) ((x & 34 = 2) (x & a = 0))
Раскрываем импликацию:
(x & 125 1) (x & 34 2) (x & a = 0)
Эквивалентные замены:
( x & 125 1) Z124 Z1
( x & 34 2) Z 32 Z 2
Z124 Z1 Z 32 Z 2 A
Переход к импликации:
Z124 Z32 Z1 Z 2 A 1
( Z124 Z 32 ) ( Z1 Z 2 A)
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

62. Новая задача

Множества и логика в задачах ЕГЭ по информатике
63
Новая задача
( Z124 Z 32 ) ( Z1 Z 2 A)
Z124 (Z1 Z 2 A)
124 or 32 = 124
(Z124 Z1 ) (Z124 Z2 ) (Z124 A)
=0
Z124 A
=0
биты 6 5 4 3 2 1 0
124 = 1111100
1 =
1
2 =
10
amin 2 2 4
? Сколько всего?
amax 124
25 – 1 = 31
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru

63. Новая задача

Множества и логика в задачах ЕГЭ по информатике
64
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
К.Ю. Поляков, 2016-2017
http://kpolyakov.spb.ru