Решение систем логических уравнений с помощью битовых векторов

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

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

Задание №23 на решение системы логических уравнений остается в ЕГЭ одним из самых сложных. Решение этой системы не только проверяет знание логических операций и умение считать у наших школьников, но и учит рассуждать, строить логические цепочки. Существует много вариантов решения
задания №23, но мы рассмотрим решения всех систем методом отображений, который разнообразен в своем применении.

«Оптимизированный метод отображения для решения задачи 23 из КИМ ЕГЭ по информатике и ИКТ» Носкин Андрей Николаевич, учитель информатики ВКК, кандидат военных наук, доцент
ГБОУ Лицей №1575 г. Москва

Еще один метод решения систем логических уравнений: «метод битовых цепочек». Суть метода заключается в следующем:

• Решение системы логических уравнений – это набор битов, из которых можно составить битовую цепочку или битовый вектор.
• Битовый вектор рассматривается как единый объект.
• Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов).
• Нужно выделить элементарные уравнения и записать ограничения «на русском языке». Например, это могут быть ограничения типа «соседние биты всегда различны» или «в битовом векторе не может быть двух соседних нулей».
• Количество решений находится по правилам комбинаторики.

Для изучения предлагаю следующие материалы:

• Видеоразбор Поляков К.Ю.
• Статья К.Ю. Полякова и М.А. Ройтберга «Системы логических уравнений: решение с помощью битовых цепочек»

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

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

Основные логические операции

• Отрицание (инверсия, логическое НЕ)

Смысл операции: результат меняется на противоположный (вместо истины — ложь, вместо лжи — истина).

• Логическое сложение (дизъюнкция, логическое ИЛИ)

Смысл операции: результат — истина, если хотя бы один операнд — истина (операндом называется то значение или та переменная, над которым (которой) осуществляется операция).

Обозначения: V или +.

• Логическое умножение (конъюнкция, логическое И)

Смысл операции: результат — истина, если оба операнда — истина.

Обозначения: Λ или &.

• Исключающее ИЛИ (сложение по модулю 2, строгая дизъюнкция)

Смысл операции: результат — истина, если операнды различны.

Смысл операции: из лжи может следовать что угодно, а из истины — только истина.

Смысл операции: результат — истина, если операнды одинаковы.

Если в логическом выражении используется несколько логических операций, то их порядок определяется приоритетами логических операций:

Операцию “импликация” можно выразить через “ИЛИ” и “НЕ”:

Операцию “эквиваленция” также можно выразить через “ИЛИ” и “НЕ”:

Поразрядные (побитовые) логические операции

Кроме обычных логических операций, применимых по отношению к логическим переменным, возможны поразрядные (побитовые) логические операции, выполняемые для пар “одноименных” (соответствующих одним и тем же разрядам) битов двух целых чисел. При этом двоичное значение 1 рассматривается как “истина”, а значение 0 — как “ложь”. Результатом выполнения поразрядной логической операции является целое число.

Для каждой пары битов выполняется логическая операция “И”.

Для каждой пары битов выполняется логическая операция “ИЛИ”.

Основные законы алгебры логики

Закон непротиворечия (высказывание не может быть одновременно истинным и ложным)

Закон исключения третьего (либо высказывание, либо его отрицание должно быть истинным)

Закон двойного отрицания

Законы де Моргана

Законы рефлексивности (идемпотенции)

Свойства логических констант 1 и 0

Полезно запомнить следующее правило: если известно количество решений уравнения F(x₁, х₂, . х_n) = 1, то количество возможных решений “противоположного” уравнения F(x₁, х₂, . х_n) = 0 равно разности количества всех возможных комбинаций значений переменных х₁, х₂. х_n (которое равно 2 n ) и количества решений уравнения F(x₁, х₂, . х_n) = 1 (и, соответственно, наоборот):

Это правило легко доказать, рассмотрев полную таблицу истинности логической функции F(x₁, х₂, . х_n): если исключить из нее строки, соответствующие значению F = 1, то останутся строки, соответствующие значению F = 0,и наоборот.

Разбор типовых задач

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

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

1) Анализируется первое уравнение:

Последняя выполняемая операция здесь — И, поэтому:

Следует обратить внимание: в обеих частях записаны одни и те же тождества, только в первом случае они записаны “как есть”, а во втором — с отрицаниями. Тогда, если (х₁ ≡ х₂) = 1 и (х₃ ≡ х₄) = 1, то первая запись будет истинной, но тогда ¬(x₁ ≡ х₂) и ¬(х₃ ≡ х₄) оба будут ложными, и вторая запись ложна. И наоборот, при (х₁ ≡ х₂) = 0 и (х₃ ≡ х₄) = 0 первая запись будет ложной, а вторая (с отрицаниями) — истинной. Не подходит ни тот, ни другой вариант. “Спасает положение” то, что тождества в обеих записях соединены операцией ИЛИ, т.е. оба раза достаточно, чтобы единице было равно хотя бы одно из этих тождеств.

Вывод: чтобы первое уравнение системы было равно 1, нужно, чтобы либо (х₁ ≡ х₂) = 1 и (х₃ ≡ х₄) = 0, либо, наоборот, (х₁ ≡ х₂) = 0 и (х₃ ≡ х₄) = 1.

Первое из этих “либо” даёт такие варианты значений переменных, когда х₁ и х₂ одинаковы, а х₃ и х₄ различны:

Второе “либо”, аналогично, даёт варианты, в которых, наоборот, х₁ и х₂ различны, а х₃ и х₄ одинаковы:

Всего — 8 вариантов.

2) Добавляется в анализ второе уравнение:

Рассуждая аналогично и учитывая, что для х₃ и х₄ возможные варианты “унаследованы” от предыдущего уравнения, получается, что в вариантах значений х₅, х₆, добавленных этим вторым уравнением, для одинаковых значений х₃ и х₄ должны быть разными значения х₅ и х₆, а для различных значений х₃ и х₄ — одинаковые значения х₅ и х₆:

Итого из 8 предыдущих вариантов благодаря второму уравнению получается 16 (вдвое больше).

3) Очевидно, такая тенденция сохранится и дальше, ведь уравнения системы — типовые. Значит, добавление в рассмотрение третьего уравнения, пропущенного в записи системы и использующего переменные х₅, х₆, х₇, x₈, снова удвоит количество вариантов значений переменных: из 16 их получится 32.

Аналогично, последнее, четвёртое уравнение системы (переменные х₇, х₈, х₉, х₁₀) снова удваивает количество вариантов, “унаследованное” от предыдущего уравнения. В итоге для всей системы уравнений получается 64 возможных варианта значений переменных x₁ — x₁₀.

Ответ: 64 варианта значений переменных.

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

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

Как и всегда при решении задач с системами логических уравнений, нужно сначала проанализировать каждое уравнение в отдельности. При этом, первое и второе уравнения заданной системы практически идентичны (с точностью до имён переменных — “игреки” вместо “иксов”), и это существенно облегчает работу.

Анализируя первое уравнение:

Таблица истинности логической операции следования: единственная ситуация, при которой её результат равен нулю, — когда из единицы следует нуль, а во всех других случаях эта операция возвращает единицу:

Кроме того, поскольку все отдельные операции следования в первом уравнении соединены операцией И, для выполнения заданного в нём равенства требуется, чтобы все операции следования давали в результате единицу.

Чтобы найти все возможные комбинации значений переменных, задействованных в первом уравнении, удобнее всего выполнить построение дерева решений: это позволит не запутаться и не пропустить какие-то варианты. При построении дерева на каждом его очередном шаге анализируется очередная пара переменных и для каждой имеющейся ветви определяются дальнейшие варианты ветвления. Слева указываются логические операции следования, которые и анализируются на соответствующих шагах (уровнях дерева). Ключевым моментом при построении дерева является уже отмеченный выше факт, что для получения единичного результата из нуля может следовать любое значение второй переменной, а из единицы — только единица.

Основную идею при построении данного дерева можно условно выразить фразой: “размножаются только нули”. То есть если имеется начало набора значений пяти переменных, которое на данный момент завершается нулём, то продолжить его можно как нулём, так и единицей (в дереве имеется ветвление), но если текущая последовательность заканчивается единицей, то продолжать её можно только единицей, и в дереве не будет никакого ветвления, а только продолжение уже существующей ветви.

Полный набор возможных значений переменных, удовлетворяющих первому уравнению, тогда содержится в самой нижней строке построенного дерева (в его “листьях”): (х₁х₂х₃х₄х₅) = (00000), (00001), (00011), (00111), (01111), (11111).

Второе уравнение по структуре полностью совпадает с первым. Поэтому анализировать его нет необходимости, и можно сразу записать набор возможных для него значений переменных: (y₁y₂y₃y₄y₅) = (00000), (00001), (00011), (00111), (01111), (11111).

Если бы в условии задачи присутствовали только рассмотренные два уравнения, то, поскольку в них нет общих переменных, решением этой системы уравнений были бы все возможные попарные сочетания найденных наборов значений “иксов” и “игреков”. Именно третье уравнение, в котором одной логической операцией связаны один из “иксов” и один из “игреков”, является “ключом”, определяющим выбор: какие из найденных комбинаций наборов значений (х₁х₂х₃х₄х₅) и (y₁y₂y₃y₄y₅) подходят, а какие — нет.

Запись этого третьего уравнения:

Согласно ему, из всех найденных пар наборов значений “иксов” и “игреков” для решения подходят только такие, в которых значения указанных переменных соответствуют истинности заданной логической операции, т.е.:

• когда в наборе значений (y₁y₂y₃y₄y₅) пятая цифра равна нулю, в пару с ним годятся любые наборы значений (х₁х₂х₃х₄х₅), поскольку, что бы в них ни стояло в пятой позиции (0 или 1), результат операции у₅→ х₅ = 1 в любом случае будет равен 1 (см. таблицу истинности для этой операции);

• когда в наборе значений (y₁y₂y₃y₄y₅) пятая цифра равна единице, в пару с ним годятся только такие наборы значений (х₁х₂х₃х₄х₅), в которых пятая цифра равна 1.

Удобнее и нагляднее всего расписать все получаемые комбинации значений х и y виде таблицы (“матрицы решений”). Анализируемые цифры в ней выделены подчеркиванием.

Урок по информатике и ИКТ на тему «Системы логических уравнений: решение с помощью битовых цепочек» (10 класс физико-информационный профиль)

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Кейс «Системы логических уравнений: решение с помощью битовых цепочек»

Предмет: Информатика и ИКТ

Класс: 10 кл физико-информационный профиль (а также 11кл при подготовке к ЕГЭ).

Время занятия: 2 урока

Вид кейса: обучающий

Тип кейса: аналитический

Тема урока: Решение Систем логических уравнений с помощью битовых цепочек.

Цель: Выработка умений и навыков аналитической деятельности при решении логических уравнений. Выработка умений и навыков обучающихся к работе со специальным набором учебно-методических материалов (кейсом) по решению логических задач и максимально активизировать каждого обучающегося в самостоятельную работу по решению кейса.

обобщить знания о преобразовании логических выражений;

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

развивать инициативу, любознательность, умственную активность;

формировать коммуникативные навыки, умения вырабатывать и аргументировать самостоятельные решения, навыки сотрудничества в группах.

Оборудование: набор учебно-методических материалов (кейс) для самостоятельной работы, компьютеры подключенные к Интернету и локальной сети, мультимедиа проектор, интерактивная доска.

Во время проведения ЕГЭ-2011 в контрольно-измерительных материалах (КИМ) впервые появилась задача, в которой требовалось найти количество решений системы логических уравнений. Автором этой интересной и сложной задачи, давшей начало целому классу задач, был Сергей Федорович Сопрунов, известный, в частности, своими методическими материалами по преподаванию языка Лого. Ему же в основном принадлежат идеи, на которых основаны приводимые далее решения.

При первом знакомстве с задачей состояние учеников (и учителей!) было близко к шоковому, об этом говорит и крайне низкий процент выполнения этого задания на
ЕГЭ- 2011 — 3,2% (значительно меньше, чем для самой сложной задачи по программированию, С4). В прошедшие годы (2012–2014) эта задача прочно обосновалась в КИМ, не смотря на многочисленные претензии учителей информатики. В первую очередь это связано с тем, что она действительно оказалась сложной. Многие педагоги, в том числе и в известных на всю страну физико-математических школах, открыто рекомендуют своим ученикам не решать эту задачу вообще или решать ее в последнюю очередь, когда все остальное решено и осталось свободное время. В то же время, как показал опыт, задача является хорошим ориентиром при изучении логики и позволяет сильным ученикам проявить себя при сдаче ЕГЭ.

Учителями информатики было предложено несколько методов решения систем логических уравнений, большинство из которых сводилось к последовательному подключению уравнений: сначала вычисляется количество решений первого уравнения, потом — системы из первых двух уравнений и т.д. К сожалению, все решения этого типа получаются достаточно громоздкими [4–7]. Тем не менее процент выполнения этого задания уже через год повысился до 13,2% [8]. К сожалению, аналитические отчеты Федеральной комиссии за 2013 и 2014 годы не публиковались, поэтому отследить дальнейшее развитие ситуации по официальным источникам невозможно.

Актуальна ли эта проблема для вас?

Какова причина данной ситуации?

Как собираетесь выходить из данной ситуации?

Удовлетворяют ли вас известные вам методы решения систем логических уравнений?

Как вы считаете есть ли альтернативные методы решения данных задач?

Решение — битовый вектор.

Учитель сообщает тему урока и дает комментарии об объеме работ, формулирование вместе с учащимися цели и задач урока, ознакомление с критериями оценок и прогнозируемого результата, объяснение порядка работы с кейсом. (Так как работа рассчитана на 2 урока учащиеся заранее к первому уроку знакомятся с частью материала кейса – повторение ранее изученного материала: логические операции, законы логики, методы преобразования логических выражений) Основные материалы кейса обучающиеся получают непосредственно на занятии и работают с ним, также знакомятся с рекомендованной учителем дополнительной литературой, часть заданий по работе с кейсом выполняется дома индивидуально каждым. Ознакомление обучающихся с заданием кейса в бумажном и электронном виде (в школьных компьютерах через локальную сеть и Дневник. ru дома).

Первый этап дискуссии — организация дискуссии в подгруппах:

— обсуждение решения по заданию кейса, поиск аргументов и решений (обучающийся, познакомившись с заданием, самостоятельно анализирует ситуацию, представляют свои решения в дискуссии с другими членами подгруппы);

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

Второй этап дискуссии (второй урок –организация общей дискуссии в классе для принятия окончательных решений:

— выступления подгрупп, каждая группа предлагает свою версию выполненного задания (публичная, устная презентация решений);

— участие в обсуждении обучающихся других подгрупп;

— участие в обсуждении учителя.

Итоговая стадия работы над кейсом — заключительная презентация результатов решения задания (сравнение нескольких вариантов решения). Затем идет обобщающее выступление учителя — анализ ситуаций и оценивание работы каждой подгруппы учителем.

Применяя ранее полученные знания и новую информацию (материалы кейса) освоить альтернативный метод решения характерных типов задач с системами логических уравнений, затрачивая минимум усилий и используя максимум знаний?

Учитель предъявляет кейс, проясняет смыслы представленных в нем заданий. Учащиеся разбиваются на мини группы, знакомятся с представленной информацией. Учатся применять имеющиеся знания по пройденному теоретическому материалу (алгебра логики) для решения логических систем уравнений. Делают умозаключения (индуктивное и по аналогии) и выводы по решению данного типа задач на основе аргументации.

Решение — битовый вектор

Пусть задана некоторая система логических (часто говорят — булевых) уравнений от переменных x1 x2,…, xN вида

Слово “логических” означает, что переменные x1 x2,…, xN — логические, то есть принимают значения 0 или 1, и выражения F1. FM, зависящие от этих переменных, — тоже логические (множество их возможных значений — <0, 1>). Решением этой системы называется такой вектор значений X x1x2…xN , при котором все уравнения обращаются в тождества. Поскольку все переменные, входящие в решение X, логические (0 или 1), все решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками, или битовыми векторами.

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

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

Для начала мы разберем несколько простых уравнений и систем, а затем перейдем к более сложным, которые использовались в задачах ЕГЭ прошлых лет. Отметим, что для проверки правильности решений систем логических уравнений можно использовать бесплатную программу, которая размещена на сайте [4].

Подведение итогов – второй урок.

Представление результатов групповой работы.

Проверка правильности решений систем логических уравнений используя бесплатную программу, которая размещена на сайте [4]. Обсуждение. Экспертиза между группами результатов работы групп по поиску по поиску оптимального решения для каждой из предложенных задач.

Что нужно знать:

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО…», «ТОГДА И ТОЛЬКО ТОГДА»

правила преобразования логических выражений;