Метод отображения для решения систем логических уравнений

Решение систем логических уравнений методом отображения

Задание 23 ЕГЭ по информатике.

По мнению составителей ЕГЭ, задание на решение системы логических уравнений остается одним из самых сложных, относится к высокому уровню сложности, хотя за него дают 1 балл. Это задание незаслуженно находится в первой части, так как оно не только проверяет знание логических операций, но и учит рассуждать, строить логические цепочки. При оценке ответа нет возможности квалифицировать ошибку, так как ответ, как и логическое высказывание, бывает либо истинным, либо ложным. А поводов дать неверный в этом случае ответ много: можно написать наугад, а можно решить все от от начала до конца, проделать все логические преобразования, выстроить верную цепочку рассуждений и в последнем действии допустить арифметическую ошибку.

Решение систем логических уравнений методом отображений Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Бушмелева Н.А.

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

Похожие темы научных работ по математике , автор научной работы — Бушмелева Н.А.

Текст научной работы на тему «Решение систем логических уравнений методом отображений»

РЕШЕНИЕ СИСТЕМ ЛОГИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ОТОБРАЖЕНИЙ

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

Ключевые слова: информатика, Единый государственный экзамен, система логических уравнений, метод отображений, количество решений.

Задачи, предлагаемые на ЕГЭ по информатике и ИКТ, решение которых сводится к решению системы логических уравнений или к поиску количества решений системы логических уравнений, с каждым годом становятся все разнообразнее, интереснее и сложнее. Одна и та же система логических уравнений может быть решена различными способами (метод рассуждений, графический метод, построение дерева решений, использование таблиц истинности, метод отображений и др.), важно уметь выбрать для ее решения метод, который позволит получить правильный ответ как можно быстрее. Особенностями этого задания являются его сложность при сравнительно небольшом оценочном балле, невозможность формализации, необходимость использования дополнительных знаний, например по комбинаторике. Практика показывает, что в условиях постоянной нехватки учебного времени учащимся не только сложно научиться решать системы логических уравнений нового типа, но и разобраться в уже готовом решении. К сожалению, различные известные способы решения систем логических уравнений не позволяют сформировать какой-то один подход к решению этой задачи. В результате решение задачи вызывает серьезные затруднения у школьников.

Рассмотрим один из методов решения систем логических уравнений — метод отображений. Этот метод удобно применять для поиска количества решений систем, содержащих однотипные логические уравнения. В таких системах количество решений очередного уравнения закономерно зависит от количества решений предыдущего уравнения. Кроме того, этот способ решения систем логических уравнений позволяет ученику следовать вполне определенному алгоритму.

Задача № 1. Найти количество решений системы логических уравнений с шестью переменными.

\Х1 ^ Х2) + (х2 ^ хз) = 1 (X ^ X) + (X ^ х4) = 1

(х4 ^ х5) +(х5 ^ х6) =1

Решение. Система состоит из четырех уравнений, каждое уравнение имеет по три переменных, все уравнения системы однотипны. Идея решения этой системы методом отображений следующая: для пары переменных хг, Х2 найти все возможные

© Бушмелева Н. А., 2018

значения переменной хз, удовлетворяющие первому уравнению системы. Затем, зная значения переменных Х2, хз, найти все возможные значения переменной Х4, удовлетворяющие второму уравнению системы. Таким образом, зная значения переменных хг, х+1 , найти все возможные значения переменной х,+2, что позволит определить новую пару значений х,+1, х,+2.

Итак, на каждом шаге решения системы известны возможные значения пар х,, х+1 — 00, 01, 10, 11. Множество значений пар х,+1, х,+2 — такое же — 00, 01, 10, 11. Следовательно, исходное множество пар отображается само в себя. Нужно построить такое отображение. Удобнее всего это сделать с помощью таблицы, в которой перечислим все пары х,, х+ь и соответствующие им х+2, обращающие 1-е уравнение в верное равенство. Из таблицы видно, что пара х,, х+ь, равная 00, приводит к двум парам х+ь, х,+2 — 00 и 01, пара 01 также приводит к двум парам — 10 и 11, пара 10 дает только одну пару 01, а из пары 11 получается две пары — 10 и 11. Эти факты обозначены стрелками.

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

На основании полученной таблицы можно указать зависимость Я количества решений системы уравнений от количества участвующих в ней переменных. В ячейку с парой 00 входит одна стрелка от 00. Это означает, что количество вхождений в решения системы пары 00 (х+1, х+2) определяется только количеством вхождений в решения системы пары 00 (х,, х,+1), то есть Я (00) = Я (00). Аналогично, в ячейку с парой 01 входят стрелки, ведущие от ячеек с 00 и 10, то есть Я (01) = Я (00) + Я (10). Дальнейший анализ таблицы позволяет записать Я (10) = R (01) + R (11), так как в пару 10 ведут стрелки от 01 и 11, и Я (11) = Я (01) + R (11), так как в пару 11 входят стрелки, ведущие от 01 и 11.

Закономерности получены, можно вычислить количество решений системы на

Пара х1, х2 х2, хз хз, х4 х4, х5 х5, хб

На последнем шаге пара 00 может быть получена 1 способом, пара 01-8 способами, пара 10-12 способами, пара 11 — также 12 способами. Для того чтобы получить количество наборов значений переменных Хг, Х2, хз, Х4, Х5, Хб, на которых заданная система имеет решение, нужно вычислить сумму 1+8+12+12=33.

Ответ: система имеет 33 решения.

Задача № 2. Найти количество решений системы логических уравнений с шестью переменными.

х^ * Ху I (Ху — ) — 1 Решение. Отображение множества пар значений двух переменных в себя:

Щ(00) = Щ(00) + Щ(10) ЩШ) = 0 Щ0) = Щ(11) Щ(11) = Щ(01) + Щ(11)

Пара Хг, Х2 Х2, Хз Хз, Х4 Х4, Х5 Х5, Хб Хб, Х7 Х7, Х8

00 1 2 3 5 7 9 11

01 1 0 0 0 0 0 0

10 1 1 2 2 2 2 2

11 1 2 2 2 2 2 2

Ответ: система имеет 15 решений.

Задача № 3. Найти количество решений системы логических уравнений с восемью переменными.

\Х1 ^ х2) + (Х2 ^ Хз) — 1 х^ * х^ I (х — х^) — 1 (х3 ^х4) + (х4 ^х5) — 1

х4 * х5 1 (х5 — хб ) 1

(х5^ хб) + (хб ^ х7) — 1

х^ * ху I (ху — ) — 1

Решение. Данная система содержит уравнения двух типов: уравнения, стоящие на нечетных местах, вида (хг ^ хг++ (хг+1 ^ хг.+2) — 1 (1 = 1, 3, 5), и уравнения, стоящие на

четных местах, вида хг * хг+1 + (хг+1 — хг.+2) — 1 (1 = 2, 4, 6).

Анализ системы позволяет сделать вывод о том, что правила перехода от одной пары значений переменных к другой меняются следующим образом:

• для уравнений, стоящих на • для уравнений, стоящих на четных

нечетных местах (см. задачу № 1) местах (см. задачу № 2)

Я (00) = Я (00) Я(00) = Я(00) + Я(10)

Я (01) = Я (00) + Я (10) ^01) = 0

Я (10) = Я (01) + Я (11) Щ0) = Я(11)

Я (11) = Я (01) + Я (11) и(и) = я(01) + Щ1)

Пара х1, х2 х2, хз хз, х4 х4, х5 х5, хб хб, х7 х7, хв

00 1 1 3 3 7 7 17

01 1 2 0 6 0 11 0

10 1 2 2 4 4 10 10

11 1 2 4 4 10 10 21

Ответ: система имеет 48 решений.

Задачи с системами логических уравнений являются наиболее трудоёмкими в ЕГЭ по информатике и ИКТ. Решение предлагаемого набора заданий позволяет в условиях недостатка времени продемонстрировать возможности метода отображений для подсчета количества решений систем однотипных логических уравнений, отработать методику его использования, а также продемонстрировать применение этого метода в более сложных ситуациях. Но необходимо помнить, что решение систем логических уравнений методом отображений не сводится к механическому выполнению определенных действий. Поскольку все этапы решения должны выполняться безошибочно, то только точное понимание понятий, лежащих в основе метода, даст возможность ученику быстро и аккуратно проверить собственное решение.

1. Авдошин С. М. Решение систем однородных логических уравнений // Информатика. 2012. № 11. С. 24-43.

2. Поляков К. Ю., Ройтберг М. А. Системы логических уравнений: решение с помощью битовых цепочек // Информатика. 2014. № 12. С. 4-2.

И. Д. Демакова, И. Ю. Шустова

ПЕДАГОГ КАК ВОСПИТАТЕЛЬ: ЗНАЧИМЫЕ ХАРАКТЕРИСТИКИ ВОСПИТАТЕЛЬНОЙ ДЕЯТЕЛЬНОСТИ, ПРИНЦИП СО-БЫТИЙНОСТИ

В статье анализируются основные характеристики воспитательной деятельности педагога в условиях утверждения гуманистической парадигмы: ценности профессиональной деятельности педагога как воспитателя, цели, приоритеты и функции воспитательной деятельности, содержание деятельности педагога-воспитателя, ориентированной на развитие ребенка. Раскрыт со-бытийный принцип воспитания, в основе которого лежит ценностно-смысловое взаимодействие взрослых и детей.

© Демакова И. Д., Шустова И. Ю, 2018

* Статья публикуется при поддержке гранта РФФИ. Проект № 17-0600117а.

Задача №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 наборов):