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

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

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

Методика решения задач ЕГЭ по теме «Системы логических уравнений» №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

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

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

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

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

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

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

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

Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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.

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

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

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

📸 Видео

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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