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

Методика решения задач ЕГЭ по теме «Системы логических уравнений» №23

Презентация может быть сипользована для подготовки к ЕГЭ по предмету Информатика. В ней объединены существующие методы и приемы по решению задачи высокго уровня первой части ЕГЭ.

Просмотр содержимого документа
«Методика решения задач ЕГЭ по теме «Системы логических уравнений» №23»

Методика решения задач ЕГЭ

ГБОУ «Гимназия №1

Сколько существует различных наборов значений логических переменных х1, х2,… (y1, y2, …), которые удовлетворяют всем перечисленным ниже условиям:

… (система логических уравнений)

В ответе не нужно перечислять все различные наборы х1, х2, … (y1, y2, …), при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов

Спецификация задания №23

согласно КИМ в 2017 ( «ФИПИ»)

Умение строить и преобразовывать логические выражения

Требования к проверяемым элементам содержания

Высказывания, логические операции, кванторы, истинность высказывания

Проверяемые требования к уровню подготовки

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

Высокий (единственный в 1-й части)

Примерное время выполнения

  • Задание сложное, его невозможно формализовать;
  • Большое количество приемов и методов решения;
  • Большая сложность при маленьком количестве баллов (лучше решить №24, чем №23);
  • Требует базовых знаний по комбинаторике.

Необходимые знания и умения

  • Базовые и дополнительные логические операции;
  • Законы алгебры логики;
  • Структуры данных – деревья;
  • Метод замены переменных;
  • Метод отображения (динамическое программирование);
  • Основы комбинаторики;
  • Навыки преобразования и анализа логических выражений.

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

  • отрицание (НЕ) : A , , not A
  • конъюнкция (И) : A ˄ B , A  B, AB, А&B, A and B
  • дизъюнкция (ИЛИ) : A ˅ B , A+ B, A | B, А or B
  • импликация (следствие) : А B
  • эквивалентность (равенство): A В, A  B, A  B
  • исключающее «или» (сложение по модулю 2) : A B , A xor B

Базовые логические операции НЕ, И, ИЛИ

Видео:Решение биквадратных уравнений. 8 класс.Скачать

Решение биквадратных уравнений. 8 класс.

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

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

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

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

Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 1). Для этого применяют операцию логического отрицания. Затем, если в уравнениях есть сложные логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом объединяем уравнения в одно, равносильное системе, с помощью логической операции «И». После этого, следует сделать преобразования полученного уравнения на основе законов алгебры логики и получить конкретное решение системы.

Решение 1: Применяем инверсию к обеим частям первого уравнения:

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

Представим импликацию через базовые операции «ИЛИ», «НЕ»:

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

Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе:

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

Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:

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

Полученное уравнение, имеет одно решение: A =0, B=0 и C=1.

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

Решение 2: Составим таблицу истинности для системы:

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

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

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

Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=1.

Способ декомпозиции. Идея состоит в том, чтобы зафиксировать значение одной из переменных (положить ее равной 0 или 1) и за счет этого упростить уравнения. Затем можно зафиксировать значение второй переменной и т.д.

Решение 3: Пусть A = 0, тогда:

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

Из первого уравнения получаем B =0, а из второго – С=1. Решение системы: A = 0, B = 0 и C = 1.

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

Задача: Сколько решений имеет уравнение ( A → B ) + ( C → D ) = 1? Где A, B, C, D – логические переменные.

Решение: Введем новые переменные: X = A → B и Y = C → D . С учетом новых переменных уравнение запишется в виде: X + Y = 1.

Дизъюнкция верна в трех случаях: (0;1), (1;0) и (1;1), при этом X и Y является импликацией, то есть является истинной в трех случаях и ложной – в одном. Поэтому случай (0;1) будет соответствовать трем возможным сочетаниям параметров. Случай (1;1) – будет соответствовать девяти возможным сочетаниям параметров исходного уравнения. Значит, всего возможных решений данного уравнения 3+9=15.

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

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

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

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

Предположим, что x 1 – истинно, тогда из первого уравнения получаем, что x 2 также истинно, из второго — x 3=1, и так далее до xm = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы. Пусть теперь x 1=0, тогда из первого уравнения имеем x 2 =0 или x 2 =1.

Когда x 2 истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. При x 2=0 получаем, что x 3=0 или x 3=, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных ( m +1 решение, в каждом решении по m значений переменных):

Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m +1.

Видео:Решение уравнения методом замены переменнойСкачать

Решение уравнения методом замены переменной

Задача №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)

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

z1z2z3z4z5z6z7z8z9
010101010
101010101

Т.к. 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) переменных:

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

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

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

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, . x4, y1, . y4, z1, . z4, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

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

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

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

📹 Видео

Алгебра Система уравнений Метод замены переменной № 6.22 9 классСкачать

Алгебра Система уравнений Метод замены переменной № 6.22  9 класс

Преобразование логических выражений / Упрощение выражений (практика) [Алгебра логики] #6Скачать

Преобразование логических выражений / Упрощение выражений (практика) [Алгебра логики] #6

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

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

Удобная замена переменной ➜ Быстрый способ решенияСкачать

Удобная замена переменной ➜ Быстрый способ решения

9 класс. Алгебра. Решение уравнений методом замены переменной.Скачать

9 класс. Алгебра. Решение уравнений методом замены переменной.

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ. | МатематикаСкачать

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ.  | Математика

Математический анализ, 20 урок, Метод замены переменнойСкачать

Математический анализ, 20 урок, Метод замены переменной

Как решать неравенства? Часть 1| МатематикаСкачать

Как решать неравенства? Часть 1| Математика

Зачётный способ решить дробно рациональное уравнение методом заменыСкачать

Зачётный способ решить дробно рациональное уравнение методом замены

Математика это не ИсламСкачать

Математика это не Ислам

9 класс, 11 урок, Методы решения систем уравненийСкачать

9 класс, 11 урок, Методы решения систем уравнений

Решение уравнений методом замены переменной.Скачать

Решение уравнений методом замены переменной.

Как решить уравнение #россия #сша #америка #уравненияСкачать

Как решить уравнение #россия #сша #америка #уравнения

Реакция на результаты ЕГЭ 2022 по русскому языкуСкачать

Реакция на результаты ЕГЭ 2022 по русскому языку

решение уравнения с заменой переменнойСкачать

решение уравнения с заменой переменной

КАК РЕШАТЬ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ. ЕГЭ по информатике. Задание 23Скачать

КАК РЕШАТЬ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ. ЕГЭ по информатике. Задание 23

Как решать уравнения с модулем или Математический торт с кремом (часть 1) | МатематикаСкачать

Как решать уравнения с модулем или Математический торт с кремом (часть 1) | Математика

Пример 47. Решить систему методом замены переменнойСкачать

Пример 47. Решить систему методом замены переменной
Поделиться или сохранить к себе: