Поляков решение систем логических уравнений

К.Ю. Поляков, М.А. Ройтберг, 2014 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг. — презентация

Презентация была опубликована 6 лет назад пользователемАркадий Воронец

Похожие презентации

Презентация по предмету «Математика» на тему: «К.Ю. Поляков, М.А. Ройтберг, 2014 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг.». Скачать бесплатно и без регистрации. — Транскрипт:

1 К.Ю. Поляков, М.А. Ройтберг, Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг

2 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Постановка задачи (ЕГЭ-2011) : Решаемость 3,2% Сколько решений имеет система уравнений: где– логические переменные.

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

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

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

6 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – II 6 Б. Дизъюнкция и конъюнкция Сочетательный закон Переместительный закон Закон поглощения Распределительный закон Правила де Моргана

7 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – III 7 В. Импликация и эквивалентность Определение импликации Свойства импликации Эквивалентность

8 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Основные идеи 8 1)Решение системы уравнений – это битовая цепочка (битовый вектор) 2)Битовый вектор рассматривается как единый объект. 3)Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов). 4)Нужно выделить элементарные уравнения и записать ограничения «на русском языке». 5)Количество решений находится по правилам комбинаторики. для любого i

9 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 9 Задача 1. «соседние биты одинаковы» Решения: 00000, Задача 2. «соседние биты различны» Решения: 01010, «биты чередуются»

10 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 10 Задача 3. «запрещена комбинация 10» Решения: , , , , , , «после первой единицы все следующие биты – 1» «все нули, потом все единицы» Для уравнения с N переменными: N+1 решений.

11 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 11 Задача 4. «запрещена комбинация 1 0» Решения: , , , , , , «слева от каждого нулевого бита (начиная с 3-го) должны стоять два нуля» «все нули, потом все единицы» Для уравнения с N переменными: N+2 решений. «запрещена комбинация » и ещё:

12 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 12 Задача 5. «запрещена комбинация 00» Сколько есть цепочек длиной N, в которых нет двух соседних нулей? ?

13 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример Все цепочки длиной нет 00! непересекающиеся множества! <0, 1>

14 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 14 1, 1, 2, 3, 5, 8, 13, 21, 34, … Числа Фибоначчи <0, 1> <01, 10, 11>Рекурсия: ЕГЭ-11 (B6) Динамическое программирование: ЕГЭ-22 (B13), ЕГЭ-15 (B9) !

15 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё пример 15 Задача 6. «запрещена комбинация 1 0» «после двух единиц подряд следуют только единицы»

16 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, И снова – рекуррентные уравнения 16 Структура решения: 11 1 «хвост»«голова» нет комбинации 11 последний бит – 0 : одна «голова» (пустая) : одна «голова» (0) «голов»

17 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Последний пример 17 Задача 7. Последовательность выполнения: запрещена комбинация 1 0 на последнем шаге Сколько решений у уравнения Начальное значение:

18 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «запрещено 00» «после двух единиц идут только единицы» Если не трогать : 11 1 «хвост»«голова» «запрещено 00 и 11» «биты чередуются»

19 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Варианты отличаются местом последнего нуля: , , , , , , , , Учитываем : 1 решение 2 решения нулевых бита, 2 2 вариантов

20 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Как перевести на русский язык? ?

21 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «очередной бит равен хотя бы одному из 2-х следующих» «запрещены комбинации 100 и 011» 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются. 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются … … = 20 «после 01 или 10 биты чередуются»

22 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ

23 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ решений: X = 0000, 0001, 0011, 0111, решений: Y = 0000, 0001, 0011, 0111, 1111 без ограничений! Связь X и Y:

24 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ X: Y:Y: = 15

25 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Замена переменных: …

26 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ К одному уравнению: Решения:

27 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Переход к исходным переменным: Каждый бит в Z даёт удвоение вариантов в X! ! 5 бит

28 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 28 Замена переменных:

29 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 29 Решение: «запрещена комбинация 01» «все единицы, потом – все нули» 8 решений: Но в z i ! !

30 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 30 2 решения: (0;1) и (1;0) 1 решение: (1;1) Каждый 0 удваивает количество решений! ! ZZ X,Y =

31 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Основные шаги решения 31 1)упрощение уравнений с помощью эквивалентных преобразований 2)замена переменных (если возможно) 3)исследование структуры всех решений 4)подсчёт количества решений по формулам комбинаторики

32 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург РОЙТБЕРГ Михаил Абрамович д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ, зам. руководителя Федеральной комиссии по разработке КИМ ЕГЭ по информатике и ИКТ

Задача №23. Решение систем логических уравнений.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x9, y1, y2, . y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N_i+1 = N_i + 1. Тогда для десяти переменных получим 11 наборов.

Решение систем логических уравнений различного типа

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, . x₄, y₁. y₄, z₁. z₄, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, . x₄, y₁, . y₄, z₁, . z₄, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Поляков решение систем логических уравнений

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5 ) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.

3) Уравнение (1) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, слева будут нули, а справа — единицы.

4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.

5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.

6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 5 комбинаций.

Правильный ответ: 5+5+1=11 комбинаций.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?

(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, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Конъюнкция истина тогда и только тогда, когда каждое высказывание истинно.

Для первого выражения это означает, что, если х1 равен 1, то х2, х3 и х4 также равны 1, т. е. для х1. х4 решения существуют только в виде «1111», «0111», «0011», «0001» и «0000».

Применив преобразование импликации ко второму выражению, увидим, что оно аналогично первому.

В третьем выражении из «y» следует соответствующее ему «x», это означает, что если y = 1, то и x = 1.

Следовательно, первому набору для x «1111» соответствует 5 наборов y. Второму — 4, третьему — 3, и. т. д.

Следовательно, ответ: 5 + 4 + 3 + 2 + 1 = 15.

Сколько существует различных наборов значений логических переменных x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) = 1

(¬x1 ∧ y1 ∧ z1) ∨ (x1 ∧ ¬y1 ∧ z1) ∨ (x1 ∧ y1 ∧ ¬z1) = 1

(¬x2 ∧ y2 ∧ z2) ∨ (x2 ∧ ¬y2 ∧ z2) ∨ (x2 ∧ y2 ∧ ¬z2) = 1

(¬x3 ∧ y3 ∧ z3) ∨ (x3 ∧ ¬y3 ∧ z3) ∨ (x3 ∧ y3 ∧ ¬z3) = 1

(¬x4 ∧ y4 ∧ z4) ∨ (x4 ∧ ¬y4 ∧ z4) ∨ (x4 ∧ y4 ∧ ¬z4) = 1

В ответе не нужно перечислять все различные наборы значений переменных

x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Рассмотрим первое уравнение. Ему удовлетворяют следующие наборы переменных x₁, x₂, x₃, x₄: 1111, 0111, 0011, 0001, 0000.

Рассмотрим оставшиеся уравнения для первого набора x₁, x₂, x₃, x₄: 1111. Во втором уравнении первая скобка будет равна 0. Из второй и третьей скобок ясно, что переменные y₁ и z₁ могут принимать значения 01 или 10. Имеем два набора решений второго уравнения. Аналогично для третьего, четвёртого и пятого уравнений. Таким образом, для набора x₁, x₂, x₃, x₄: 1111, получаем 16 наборов переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ (см. рис).

Рассмотрим второй набор переменных x₁, x₂, x₃, x₄: 0111. В этом случае из второго уравнения ясно, что переменные y₁ и z₁ могут принимать значения 11. Для оставшихся уравнений ситуация аналогична первому набору. Таким образом, для набора x₁, x₂, x₃, x₄: 0111, получаем 8 наборов переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ (см. рис).

Проведя аналогичные рассуждения для наборов 0011, 0001 и 0000, получаем, соответственно 4, 2 и 1 набор переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ соответственно.