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

Задание 23 ЕГЭ по информатике.

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

Видео:Системы логических уравнений - 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)

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

Т.к. 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 наборов):

Видео:ПОДГОТОВКА К ЕГЭ. ИНФОРМАТИКА. УРОК 2. РЕШЕНИЕ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ОТОБРАЖЕНИЯСкачать

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

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

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

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

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

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

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

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

📸 Видео

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

Система логических уравнений. Метод отображений.Скачать

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

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

ЕГЭ. Информатика. Задание 23. Решение системы логических уравнений методом отображенияСкачать

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

Системы логических уравнений содержащие НЕОДНОТИПНЫЕ УРАВНЕНИЯ [Алгебра логики] #8Скачать

Системы логических уравнений содержащие ОДНОТИПНЫЕ УРАВНЕНИЯ [Алгебра логики] #9Скачать

Решение систем логических уравнений (метод формул)Скачать

Системы логических уравнений и логические уравнения - ЕГЭ по Информатике - Задание №23Скачать

Сколько решений имеет лог. уравнение (!(A *B) + C) IMP (!A * !B + D) = 1. Информатика, ЕГЭ, логикаСкачать

Сколько решений имеет логическое уравнение: (A импликация В) ИЛИ (C импликация D). ЕГЭ(информатика)Скачать

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

Системы логических уравнений ЕГЭ 2019Скачать

Решение системы уравнений методом Гаусса. Бесконечное множество решенийСкачать

Решение систем логических уравнений. Часть 1. 09042020Скачать

ЕГЭ информатика 2020. Задание 23. Системы логических уравнений. Досрочный ЕГЭ 2020Скачать

Логические выражения, таблицы истинности ,структурная логическая схемаСкачать