Системы логических уравнений в задачах ЕГЭ по информатике

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

К.Ю. Поляков,
М.А. Ройтберг
Системы логических
уравнений в задачах
ЕГЭ по информатике
К.Ю. Поляков, М.А. Ройтберг, 2015-2016
http://kpolyakov.spb.ru

2. Постановка задачи (ЕГЭ-2011)

Системы логических уравнений в задачах ЕГЭ по информатике
2
Постановка задачи (ЕГЭ-2011)
Сколько решений имеет система уравнений:
x1 x2 x1 x2 x3 x4 x3 x4 1
x3 x4 x3 x4 x5 x6 x5 x6 1
...
x7 x8 x7 x8 x9 x10 x9 x10 1
где
x1 , x2 , , x10 – логические переменные.
2011: Решаемость 3,2%
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

3. Методы решения

Системы логических уравнений в задачах ЕГЭ по информатике
3
Методы решения
1) замена переменных
2) последовательное подключение уравнений
3) метод отображения (Е.А. Мирончик)
«Информатика. Первое сентября»
1. Е. А. Мирончик, Метод отображения // Информатика,
№ 10, 2013, с. 18-26.
2. Е.А. Мирончик, Люблю ЕГЭ за В15, или Еще раз про
метод отображения // Информатика, № 7-8, 2014,
с. 26-32.
трудоёмко
длинная запись решения
2012: Решаемость 13,2%
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

4. Аналогии с алгеброй

Системы логических уравнений в задачах ЕГЭ по информатике
4
Аналогии с алгеброй
Алгебра
Логика
Обычно уравнение имеет
одно или несколько
решений.
Уравнение может иметь
большое, но конечное
число решений.
Элементарные уравнения:
линейные, квадратные.
Элементарные уравнения
не выделяются.
Методы преобразования:
законы сложения и
умножения, формулы
сокращенного умножения,
свойства степеней.
Методы преобразования:
законы логики (см. далее).
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

5. Формулы логики – I

Системы логических уравнений в задачах ЕГЭ по информатике
5
Формулы логики – I
A. Свойства 0, 1 и отрицания
Свойства 0 и 1
a 0 0
a 1 a
Свойства отрицания
a a 0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
a 0 a
a 1 1
a a 1
a a
http://kpolyakov.spb.ru

6. Формулы логики – II

Системы логических уравнений в задачах ЕГЭ по информатике
6
Формулы логики – II
Б. Дизъюнкция и конъюнкция
Сочетательный закон
a (b c) (a b) c
a (b c) (a b) c
Переместительный закон
a b b a
a b b a
Закон повторения
a a a
a a a
Распределительный закон
a (b c) a b a c
a b c ( a b) ( a c )
Правила де Моргана
a b a b
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
a b a b
http://kpolyakov.spb.ru

7. Формулы логики – III

Системы логических уравнений в задачах ЕГЭ по информатике
7
Формулы логики – III
В. Импликация
Определение импликации
a b a b
Свойства импликации
a b a b
a b b a
a (b c) (a b) c
b a
a (b c) a (b c) a b c
(a b) c (a b) c a b c
a (b c) (a b) (a c)
a (b c) (a b) (a c)
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

8. Формулы логики – IV

Системы логических уравнений в задачах ЕГЭ по информатике
8
Формулы логики – IV
Г. Эквивалентность
Представление через базис:
(a b) a b a b
( a b) a b a b
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

9. Основные идеи

Системы логических уравнений в задачах ЕГЭ по информатике
9
Основные идеи
1) Решение системы уравнений – это битовая
цепочка (битовый вектор)
X x1 x2 xN ( xi {0,1}
для любого i
)
2) Битовый вектор рассматривается как единый
объект.
3) Уравнения – это ограничения на битовый
вектор (ограничения на комбинации битов).
4) Нужно выделить элементарные уравнения и
записать ограничения «на русском языке».
5) Количество решений находится по правилам
комбинаторики.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

10. Типичные ограничения

Системы логических уравнений в задачах ЕГЭ по информатике
10
Типичные ограничения
Задача 1.
( x1 x2 ) ( x2 x3 ) ( x4 x5 ) 1
«соседние биты одинаковы»
Решения: 00000, 11111
Задача 2.
( x1 x2 ) ( x2 x3 ) ( x4 x5 ) 1
«соседние биты различны»
«биты чередуются»
Решения: 01010, 10101
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

11. Типичные ограничения

Системы логических уравнений в задачах ЕГЭ по информатике
11
Типичные ограничения
Задача 3.
( x1 x2 ) ( x2 x3 ) ( x5 x6 ) 1
«запрещена комбинация 10»
«после первой единицы все следующие биты – 1»
«все нули, потом все единицы»
Решения: 000000, 000001, 000011, 000111,
001111, 011111, 111111
Для уравнения с N переменными: N+1 решений.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

12. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
12
Более сложный пример
Задача 4.
(( x1 x2 ) x3 ) (( x2 x3 ) x4 ) (( x4 x5 ) x6 ) 1
«запрещена комбинация 1 0»
«запрещена комбинация xi xi 1 1, xi 2 0»
«слева от каждого нулевого бита (начиная с 3-го)
должны стоять два нуля»
«все нули, потом все единицы»
Решения: 000000, 000001, 000011, 000111,
001111, 011111, 111111
и ещё: 101111
Для уравнения с N переменными: N+2 решений.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

13. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
13
Более сложный пример
Задача 5.
( x1 x2 ) ( x2 x3 ) ( x5 x6 ) 1
«запрещена комбинация 00»
?
Сколько есть цепочек длиной N, в которых нет
двух соседних нулей?
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

14. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
14
Более сложный пример
KN – количество «правильных» цепочек длиной N
K1 2 {0, 1}
Все цепочки длиной
K 2 3 {01, 10, 11}
N
K N 2
нет 00!
1
0
1
K N K N 1 K N 2
непересекающиеся
множества!
K N 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

15. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
15
Более сложный пример
K1 2 {0, 1}
K 2 3 {01, 10, 11}
K N K N 1 K N 2
KN
!
Рекурсия: ЕГЭ-11 (B6)
Динамическое
программирование:
ЕГЭ-22 (B13), ЕГЭ-15 (B9)
1, 1, 2, 3, 5, 8, 13, 21, 34, …
Числа Фибоначчи FN
K N FN 2
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

16. Ещё пример

Системы логических уравнений в задачах ЕГЭ по информатике
16
Ещё пример
Задача 6.
( x1 x2 x3 ) ( x2 x3 x4 ) ( x4 x5 x6 ) 1
«запрещена комбинация 1 0»
«после двух единиц подряд следуют только единицы»
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

17. И снова – рекуррентные уравнения

Системы логических уравнений в задачах ЕГЭ по информатике
17
И снова – рекуррентные уравнения
Структура решения:
«голова»
«хвост»
0
1
1
m
нет комбинации 11
последний бит – 0
m 0 : одна «голова» (пустая)
m 1 : одна «голова» (0)
m 1 : Fm 1 «голов»
1
N m
N
K N Fm 1
m 0
N 6 : K N 1 1 2 3 5 8 13 33
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

18. Последний пример

Системы логических уравнений в задачах ЕГЭ по информатике
19
Демо-вариант ЕГЭ-2017
( x1 ( x2 y1 )) ( y1 y2 ) 1
( x2 ( x3 y2 )) ( y2 y3 ) 1
...
( x5 ( x6 y5 )) ( y5 y6 ) 1
x6 y6 1
xi ( xi 1 yi ) 1
xi xi 1 1
xi yi 1
Группировка по вертикали:
( x1 ( x2 y1 )) ... ( x5 ( x6 y5 )) 1
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
x6 y6 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

19. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
20
Демо-вариант ЕГЭ-2017
( x1 x2 ) ( x2 x3 ) ... ( x5 x6 ) 1
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
( x1 y1 ) ... ( x5 y5 ) ( x6 y6 ) 1
Решение:
( x1 x2 ) ( x2 x3 ) ... ( x5 x6 ) 1
000000, 000001, 000011, 000111, 001111, 011111, 111111
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
000000, 000001, 000011, 000111, 001111, 011111, 111111
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

20. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
21
Демо-вариант ЕГЭ-2017
Уравнение связи:
( x1 y1 ) ... ( x5 y5 ) ( x6 y6 ) 1
Ограничения:
xi 0 yi {0, 1} без ограничений!
xi 1 yi 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

21. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
22
Демо-вариант ЕГЭ-2017
X:
7 000000
6 000001
5 000011
4 000111
3 001111
2 011111
1 111111
Y:
000000
000001
000011
000111
001111
011111
111111
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

22. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
23
Демо-вариант ЕГЭ-2016
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
...
( x8 y8 ) ( x9 y9 )
Замена переменных:
z1 ( x1 y1 )
z2 ( x2 y2 )
…
z9 ( x9 x9 )
z1 z 2 , z2 z3, z8 z9
z1 z 2 , z2 z3, z8 z9
( z1 z2 ) ( z2 z3 ) ( z2 z3 ) ( z8 z9 ) 1
!
Биты чередуются!
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
Решения: Z = 010101010,
Z = 101010101
http://kpolyakov.spb.ru

23. Демо-вариант ЕГЭ-2016

Системы логических уравнений в задачах ЕГЭ по информатике
24
Демо-вариант ЕГЭ-2016
Решения: Z = 010101010,
Z = 101010101
zi ( xi yi )
9 битов
zi 0 ( xi , yi ) (0,1) (1,0)
zi 1 ( xi , yi ) (0,0) (1,1)
!
0 и 1 дают по
2 решения!
29 + 29 = 1024
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

24. Демо-вариант ЕГЭ-2016

Системы логических уравнений в задачах ЕГЭ по информатике
25
Демо-вариант ЕГЭ-2015
( x1 x2 ) ( x1 x2 x3 ) ( x1 y1 ) 1
( x2 x3 ) ( x2 x3 x4 ) ( x2 y2 ) 1
( x6 x7 ) ( x6 x7 x8 ) ( x6 y6 ) 1
( x7 x8 ) ( x7 y7 ) 1
xi xi 1 1
«запрещено 00»
( xi xi 1 xi 2 ) 1
«после двух единиц
идут только единицы»
x8 y8 1
Если не трогать Y :
«голова»
«хвост»
0
1
1
1
«запрещено 00 и 11»
«биты чередуются»
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

25. Демо-вариант ЕГЭ-2015

Системы логических уравнений в задачах ЕГЭ по информатике
26
Демо-вариант ЕГЭ-2015
Варианты отличаются местом последнего нуля:
11111111, 01111111, 10111111, 01011111, 10101111,
01010111, 10101011, 01010101, 10101010
Учитываем
Y:
xi yi 1
xi yi 1
xi 1 yi 1
1 решение
xi 0 yi {0, 1} 2 решения
01011111
2 нулевых бита, 22 вариантов
K 8 2 2 (2 2 2 2 ) 61
0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
1
2
3
4
http://kpolyakov.spb.ru

26. Демо-вариант ЕГЭ-2015

Системы логических уравнений в задачах ЕГЭ по информатике
27
Демо-вариант ЕГЭ-2014
( x1 x2 ) ( x1 x3 x1 x3 ) 0
( x2 x3 ) ( x2 x4 x2 x4 ) 0
( x8 x9 ) ( x8 x10 x8 x10 ) 0
( x1 x2 ) ( x1 x3 ) 0
( x2 x3 ) ( x2 x4 ) 0
?
Как перевести на
русский язык?
( x8 x9 ) ( x8 x10 ) 0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

27. Демо-вариант ЕГЭ-2014

X
Системы логических уравнений в задачах ЕГЭ по информатике
28
Демо-вариант ЕГЭ-2014
( xi xi 1 ) ( xi xi 2 ) 0
«очередной бит равен хотя бы одному из 2-х следующих»
«запрещены комбинации 100 и 011»
«после 01 или 10 биты чередуются»
1) сначала цепочка нулей, потом биты чередуются (1/0)
2) сначала цепочка единиц, потом биты чередуются.
0000000000
0000000001
0000000010
0000000101
…
0101010101
1111111111
1111111110
1111111101
1111111010
…
1010101010
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
10 + 10 = 20
http://kpolyakov.spb.ru

28. Демо-вариант ЕГЭ-2014

Системы логических уравнений в задачах ЕГЭ по информатике
29
Демо-вариант ЕГЭ-2013
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

29. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
30
Демо-вариант ЕГЭ-2013
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
5 решений:
X = 0000, 0001, 0011, 0111, 1111
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
5 решений:
Y = 0000, 0001, 0011, 0111, 1111
Связь X и Y:
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
yi 1 xi 1
yi 0 xi {0, 1}
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
без ограничений!
http://kpolyakov.spb.ru

30. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
31
Демо-вариант ЕГЭ-2013
X:
0000
0001
0011
0111
1111
Y:
0000
0001
0011
0111
1111
5
4
3
2
1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
5 + 4 + 3 + 2 + 1 = 15
http://kpolyakov.spb.ru

31. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
32
Демо-вариант ЕГЭ-2012
(( x1 x2 ) ( x3 x4 )) (( x1 x2 ) ( x3 x4 )) 1
(( x3 x4 ) ( x5 x6 )) (( x3 x4 ) ( x5 x6 )) 1
(( x7 x8 ) ( x9 x10 )) (( x7 x8 ) ( x9 x10 )) 1
Замена переменных:
z1 ( x1 x2 )
z2 ( x3 x4 )
…
z5 ( x9 x10 )
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
( z1 z 2 ) ( z1 z 2 ) 1
( z 2 z3 ) ( z 2 z3 ) 1
( z 4 z5 ) ( z 4 z5 ) 1
http://kpolyakov.spb.ru

32. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
33
Демо-вариант ЕГЭ-2012
(a b) (a b ) a b a b (a b)
( z1 z 2 ) ( z1 z 2 ) 1
( z1 z 2 ) 1
( z 2 z3 ) ( z 2 z3 ) 1
( z 2 z3 ) 1
( z 4 z5 ) ( z 4 z5 ) 1
( z 4 z5 ) 1
К одному уравнению:
( z1 z2 ) ( z2 z3 ) ( z2 z3 ) ( z4 z5 ) 1
Решения:
Z 01010,
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
Z 10101
http://kpolyakov.spb.ru

33. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
34
Демо-вариант ЕГЭ-2012
Переход к исходным переменным:
zi ( xk xk 1 )
zi 0 ( xk , xk 1 ) (0,1), (1,0)
zi 1 ( xk , xk 1 ) (0,0), (1,1)
!
Каждый бит в Z даёт удвоение вариантов в X!
Z 01010,
Z 10101
5 бит
5 бит
K10 2 2 64
5
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
5
http://kpolyakov.spb.ru

34. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
35
Ещё одна задача (2015)
( x1 y1 ) ( x2 y2 x1 y1 ) 1
( x2 y2 ) ( x3 y3 x2 y2 ) 1
( x6 y6 ) ( x7 y7 x6 y6 ) 1
x7 y7 1
Замена переменных:
z1 x1 y1
z 2 x2 y 2
z6 x6 y6
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
z 2 z1 1
z3 z 2 1
z7 z6 1
http://kpolyakov.spb.ru

35. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
36
Ещё одна задача (2015)
z 2 z1 1 ( z2 z1 ) ( z3 z2 ) ( z7 z6 ) 1
Z z1 z2 z3 z4 z5 z6 z7
z3 z 2 1
Решение:
«запрещена комбинация 01»
z7 z6 1
«все единицы, потом – все нули»
!
8 решений: 0000000
1000000
1100000
1110000
Но в zi!
1111000
1111100
1111110
1111111
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

36. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
37
Ещё одна задача (2015)
zi xi yi 0
xi yi 1
zi xi yi 1
xi yi 1
Z
0000000
1000000
1100000
1110000
2 решения: (0;1) и (1;0)
!
Каждый 0 удваивает
количество решений!
1 решение: (1;1)
X,Y
128
64
32
16
Z
1111000
1111100
1111110
1111111
X,Y
8
4
2
1
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

37. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
40
Пробное тестирование (2015)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Замена переменных:
z1 ( x1 y1 )
z 2 ( x2 y 2 )
...
( x5 y5 ) ( x6 y6 )
z6 ( x6 y6 )
( z1 z2 ) ( z2 z3 ) ( z5 z6 ) 1
«биты чередуются»
Решения: 010101, 101010
zi 1 ( xi , yi ) (1,1)
Ответ: 33+33= 54
zi 0 ( xi , yi ) (0,0)(0,1)(1,0)
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

38. И ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
41
Ещё одна задача (2016)
(( x1 y1 ) ( x2 y2 )) ( x1 x2 ) ( y1 y2 ) 1
(( x2 y2 ) ( x3 y3 )) ( x2 x3 ) ( y2 y3 ) 1
(( x7 y7 ) ( x8 y8 )) ( x7 x8 ) ( y7 y8 ) 1
В другой форме:
( x1 x2 ) ( x2 x3 ) ... ( x7 x8 ) 1
( y1 y2 ) ( y2 y3 ) ... ( y7 y8 ) 1
!
Все нули,
потом 1!
(( x1 y1 ) ( x2 y2 )) ... (( x7 y7 ) ( x8 y8 )) 1
Ограничения
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

39. И ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
42
Ещё одна задача (2016)
X
00000000
00000001
...
11111111
Ограничение:
Запрещено:
?
Как стыкуются?
Y
00000000
00000001
...
11111111
( xi yi ) ( xi 1 yi 1 ) 1
xi yi и xi 1 yi 1
Получим 10!
(0,0)
(1,1)
(1,0) или (0,1)
Если есть 0,
то X=Y!
X=11111111 стыкуется со всеми! (N+1 решений)
остальные – только с равными и с Y=11111111!
(+2N решений)
Ответ: 3·8+1= 25
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

40. Пробное тестирование (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
43
Основные шаги решения
1) упрощение уравнений с помощью
эквивалентных преобразований
2) замена переменных (если возможно)
3) исследование структуры всех решений
(«голова+хвост»)
4) подсчёт количества решений по формулам
комбинаторики
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

41. Ещё одна задача (2016)

Системы логических уравнений в задачах ЕГЭ по информатике
44
Как можно рассказать детям?
1) x1 x2 x3 x4 x5 0
2) x1 x2 x3 x4 x5 1
3) ( x1 x2 ) ( x3 x4 ) 1
4) ( x1 x2 ) ( x3 x4 ) 0
5) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
6) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
7) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

42. Ещё одна задача (2016)

Системы логических уравнений в задачах ЕГЭ по информатике
45
Как можно рассказать детям (II)?
8) ( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
9)
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
x2 y3 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

43. Основные шаги решения

Системы логических уравнений в задачах ЕГЭ по информатике
46
Как можно рассказать детям (III)?
10)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Демо-2016
...
( x8 y8 ) ( x9 y9 )
11)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Пробное
тестирование
...
( x5 y5 ) ( x6 y6 )
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

44. Как можно рассказать детям?

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