Система логических уравнений информатика 10 класс

Методы решения систем логических уравнений
статья по информатике и икт (10 класс) по теме

Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15)

Скачать:

Предварительный просмотр:

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

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

1. Метод замены переменных.

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

Рассмотрим применение этого метода на конкретном примере.

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

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

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

Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).

Тогда система уравнений будет выглядеть так:

Построим дерево решений полученной системы:

Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:

Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:

Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.

2. Метод рассуждений.

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

Пример 1. Сколько существует различных наборов значений логических переменных 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, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

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

Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:

Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.

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

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

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

Решение : Упростим систему. Построим таблицу истинности части первого уравнения:

Урок по информатике и ИКТ на тему «Системы логических уравнений: решение с помощью битовых цепочек» (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]. Обсуждение. Экспертиза между группами результатов работы групп по поиску по поиску оптимального решения для каждой из предложенных задач.

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

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

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

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