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

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

2011: Решаемость 3,2%

Сколько решений имеет система уравнений:

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

замена переменных
последовательное подключение уравнений
метод отображения (Е.А. Мирончик) (динамическое программирование)

«Информатика. Первое

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

Алгебра

Логика

Элементарные уравнения: линейные, квадратные.

Элементарные уравнения не выделяются.

Методы преобразования: законы

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

A. Свойства 0, 1 и отрицания

Свойства 0

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

Б. Дизъюнкция и конъюнкция

Сочетательный закон

Переместительный закон

Закон повторения

Распределительный закон

Правила

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

В. Импликация

Определение импликации

Свойства импликации

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

Г. Эквивалентность

Представление через базис:

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

Решение системы уравнений – это битовая цепочка (битовый вектор)
Битовый вектор

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

Задача 1.

«соседние биты одинаковы»

Решения: 00000, 11111

Задача 2.

«соседние биты различны»

Решения: 01010,

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

Задача 3.

«запрещена комбинация 10»

Решения: 000000, 000001, 000011, 000111,
001111,

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

Задача 4.

«запрещена комбинация 1→0»

Решения: 000000, 000001, 000011, 000111,

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

Задача 5.

«запрещена комбинация 00»

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

нет 00!

непересекающиеся множества!

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

1, 1, 2, 3, 5, 8, 13, 21, 34,

Ещё пример

Задача 6.

«запрещена комбинация 1→0»

«после двух единиц подряд следуют только единицы»

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

Структура решения:

«хвост»

«голова»

нет комбинации 11
последний бит – 0

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

Задача 7.

Последовательность выполнения:

запрещена комбинация 1→0 на последнем шаге

Начальное значение:

Решения уравнения

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

Группировка по вертикали:

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

Решение:

000000, 000001, 000011, 000111, 001111, 011111, 111111

000000, 000001, 000011, 000111,

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

Уравнение связи:

без ограничений!

Ограничения:

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

X:
000000
000001
000011
000111
001111
011111
111111

Y:
000000
000001
000011
000111
001111
011111
111111
7
6
5
4
3
2
1

7 + 6 + 5 + 4 + 3 +

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

Замена переменных:

Решения: Z = 010101010,
Z = 101010101

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

Решения: Z = 010101010,
Z = 101010101

29 + 29

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

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

5 решений:
X = 0000, 0001, 0011, 0111, 1111

5 решений:

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

X:
0000
0001
0011
0111
1111

Y:
0000
0001
0011
0111
1111
5
4
3
2
1

5 + 4 + 3 + 2 + 1 =

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

Замена переменных:

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

К одному уравнению:

Решения:

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

Переход к исходным переменным:

5 бит

5 бит

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

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

«очередной бит равен хотя бы одному из 2-х следующих»

«запрещены комбинации

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

«запрещено 00»

«после двух единиц идут только единицы»

«хвост»

«голова»

«запрещено 00 и 11»

«биты

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

Варианты отличаются местом последнего нуля:

11111111, 01111111, 10111111, 01011111, 10101111,
01010111,

Демо-вариант ЕГЭ-2018

Демо-вариант ЕГЭ-2018

Демо-вариант ЕГЭ-2018

только x

только y

уравнения связи

Все X-решения:

Все Y-решения:

0000000
1000000
1100000
1110000
1111000
1111100
1111110
1111111

0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111

Демо-вариант ЕГЭ-2018

Все X-решения:

Все Y-решения:

0000000
1000000
1100000
1110000
1111000
1111100
1111110
1111111

0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111

2
3
3
3
3
3
3
2

2+3+3+3+3+3+3+2 = 22

*111111
**11111
0**1111
00*1111
000**11
0000**1
00000**
000000*

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

Замена переменных:

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

Решение:

«запрещена комбинация 01»

«все единицы, потом – все

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

2 решения: (0;1) и (1;0)

1 решение: (1;1)

0000000
1000000
1100000
1110000

1111000
1111100
1111110
1111111

Z

Z

128
64
32
16

8
4
2
1

X,Y

X,Y

128 +

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

Запрещены комбинации:

Запрещено 01x!

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

запрещено 01x и 100
01 может стоять только

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

Замена переменных:

Решения: 010101, 101010

«биты чередуются»

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

В другой форме:

Ограничения

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

Ограничение:

Запрещено:

(0,0)

(1,0) или (0,1)

X=11111111

стыкуется со всеми! (N+1 решений)

остальные –

Ещё одна задача (2018)

Ещё одна задача(2018)

Решения:

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

упрощение уравнений с помощью эквивалентных преобразований
замена переменных (если возможно)
исследование

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

Как можно рассказать детям (II)?

Как можно рассказать детям (III)?

Демо-2016

Пробное тестирование