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

Покало Нина Александровна

МБОУ СОШ №11 п.Новотерский

Минераловодского района

Ставропольского края

Учитель математики, информатики

Мастер-класс по предмету информатика и ИКТ:

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

в рамках подготовки учащихся к сдаче ЕГЭ на примере задания под номером 23

Аннотация

к материалам Мастер – класс «Решение системы логических уравнений»

Тема занятия рассмотрена на примерах задания № 23 ЕГЭ информатика.

Задание 23 считается одним из самых сложных заданий ЕГЭ по информатике!

За время занятия будет рассмотрено два способа решения систем табличный и графический. Материал можно использовать для подготовки учащихся к ЕГЭ предмет «Информатика», как во время урока, так и на дополнительных занятиях

Мояцель:

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

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

По продолжительности занятие - 40 минут.

Работа будет проходить совместно с группой учащихся и преподавателей «вопрос-ответ» по теме «Алгебра логики».

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

Для решения систем логических уравнений (СЛУ) нельзя выделить какой-то один универсальный способ и применять его для всех задач задания 23.

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

Материал занятия.

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

к ним относятся:

Графический

Табличный

Способ замены выражений простыми переменными

Способ с использованием упрощений логических выражений

За время занятия нами будет рассмотрено два способа: табличный и графический.

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

Что необходимо знать для решения!

(материал может быть подготовлен как справочный - раздаточный, что позволить сделать урок более продуктивным)

Условные обозначения логических операций.

конъюнкция : A /\B , A B, AB, А&B, A and B

дизъюнкция: A \/ B , A+ B, A | B, А or B

о трицание: A , А, notA, не А

и мпликация: А В

эквивалентность: A В, AB, AB

исключающее «или»: AB , AxorB

Первым рассмотримТАБЛИЧНЫЙспособ

на примере:

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

(¬ (x₁ ≡ y₁)) ≡ (x₂≡ y₂)
(¬ (x₂ ≡ y₂)) ≡ (x₃ ≡ y₃)
…
(¬ (x₈ ≡ y₈)) ≡ (x₉ ≡ y₉)

Решение.

Найдём количество решений для первого уравнения

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

Возможные вопросы:

Какая логическая операция используется в уравнении?

Когда эквивалентность истинна?

И дальше идут предположения с последовательным заполнением таблицы1.

Еслиx₁ и y₁ будут имеют разные значения (0,1 или 1,0), то отрицание лжи – истинно (это значение левой части уравнения), следовательно, значения x₂и y₂ должны быть одинаковы (0,0 или 1,1) для получения истинности правой части уравнения, таким образом, получаем первые две строки таблицы

Еслиx₁ и y₁ имеют одинаковые значения (0,0 или 1,1), то отрицание истинности – ложь (это значение левой части уравнения), следовательно, значения x₂и y₂ должны быть разные (0,1 или 1,0) для получения лжи правой части уравнения, чтобы значение эквивалентности левой и правой частей уравнения было истинно. Таким образом, получаем следующие две строки таблицы истинности .

Итого, по первому уравнению мы имеем 8 наборов переменных

(Крешений)

Таблица 1.

Найдём количество решений (К) для второго уравнения.

Рассуждения аналогичны рассуждениям 1.шага

Варианты решений второго уравнения будут точно такими же, как и для первого уравнения

Таблица 2

Добавляем в таблицу 2.два столбца для общих переменных: x₁ и y₁.

Не обращая внимания на столбцы значений x₃ и y_3, заполняем значения для x₁ и y₁ из таблицы 1. с учетом значений x₂ и y_2, исходя из таблицы 2.

Таблица 3

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

Итого: 8*2*2*2*2*2*2*2 = 8*2^n-1 =81024 решения. , где n- количество уравнений.

Ответ: 1024

ГРАФИЧЕСКИЙСПОСОБ. ( В работе также принимают участие присутствующие)

Способ заключается в построении графа (дерева) решений. Решение начинается с анализа первого уравнения, затем присоединяется очередное уравнение.

Пример.

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

X₁\/¬X₂=1

X₂\/¬X₃=1

…

X₉\/¬X₁₀=1

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

Решение:

Вспомним, когда дизъюнкция истинна: истинна во всех случаях, кроме (00)

Решаем первое уравнение:

Если Х₁=0, то ¬X₂=1, а когда это возможно, при каких значениях X₂( 0) .

Если Х₁=1, то ¬X₂ может быть 0 и 1, а

X₂ соответственно 1 и 0

Строим дерево решений :

Таким образом, первое уравнение имеет3 решения:

(00), (10) и (11).

2) Присоединяем второе уравнение:

Р ассматриваем значения Х_{2 .}

Если Х₂=0, то ¬X₃=1, а X₃=0

Если Х₂=1, то ¬X₃ может быть 0 и 1, и

X₃ соответственно 1 и 0.

Добавляем наши рассуждения :

На графе видно, что два уравнения имеют4решения.

П рисоединяем третье уравнение:

Если Х₃=0, то ¬X₄=1, а X₄=0

Если Х₃=1, то ¬X₄ может быть 0 и 1, и

X₄ соответственно 1 и 0.

Добавляя наши рассуждения на графе:

Видим, что 3 уравнения имеют 5 решений.

Можно дальше не продолжать построение графа, а сделать вывод: количество решений (К) больше на 2 количества уравнений (n), следовательно, К = n+2, и таким образом,

4 уравнения имеют 6 решений,

5 уравнений имеет 7 решений, …

9 уравнений имеют 11 решений.

Ответ: 11 решений.

Примеры задания 23 с сайта К.Поляковаhttp://kpolyakov.spb.ru/school/egetest/b23.htm

23 - Системы логических уравнений

Рекомендуемые интернет – ресурсы:

https://inf-ege.sdamgia.ru сайт Дмитрия Гущина

http://kpolyakov.spb.ru/school/egetest/b23.htm сайт Константина Полякова

Вывод: Благодаря вашим знаниям, наша совместная работа была интересной и плодотворной. Успехов вам и до скорой встречи!

Используемая литература:

УМК «Информатика» 10-11 классы Автор Угринович Н.Д. учебник + практикум

Издательство: БИНОМ. Лаборатория знаний 

Интернет – ресурсы:

https://inf-ege.sdamgia.ru сайт Дмитрия Гущина

http://kpolyakov.spb.ru/school/egetest/b23.htm сайт Константина Полякова

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/285826-reshenie-sistem-logicheskih-uravnenij