При решении системы логических уравнений была сделана замена переменных zi xi yi (7 видео)

Содержание

Задача №23. Решение систем логических уравнений.
При решении системы логических уравнений была сделана замена переменных zi xi yi
Решение систем логических уравнений
🌟 Видео

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

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

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

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

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

При решении системы логических уравнений была сделана замена переменных zi xi yi

РАЗОБРАННЫЕ ПРИМЕРЫ ЗАДАЧ:

Решение. Все “сомножители”2 имеют форму xf=xi+1, они должны быть равны 1. Это значит, что любые два соседних бита должны быть равны. Существует всего две таких цепочки:

Ответ: два решения.

Задача 2. Сколько различных решений имеет система уравнений
(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1
(x3 ˅ x4) ˄ ((x3 ˄ x4) → x5) = 1
(x4 ˅ x5) ˄ ((x4 ˄ x5) → x6) = 1
(x5 ˅ x6) ˄ ((x5 ˄ x6) → x7) = 1
(x6 ˅ x7) ˄ ((x6 ˄ x7) → x8) = 1
(x7 ˅ x8) = 1
где x1,x2,…,x8 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение:
Решим систему с помощью битовых цепочек. Битовая цепочка — это набор единиц и нулей для переменных x1. x8, при которых система будет истинна.

Цепочки строятся по определенным правилам, которые можно вывести из системы. Рассмотрим первое уравнение:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1

Для получения истины выражение (x1 ˅ x2) обязательно должно быть истинно, то есть в уравнении не может быть двух подряд идущих нулей.

Кроме этого, выражение ((x1 ˄ x2) → x3) тоже должно быть истинно. Ложным оно будет в том случае, если x1 и x2 будет равны 1, а x3 — 0. То есть после двух подряд идущих единиц не может быть нуля.

Каждое следующее уравнение связано с предыдущим:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1

То есть два правила, которые мы вывели, применяются не только к каждому уравнению, но и ко всей цепочке.

Первая очевидная цепочка для набора иксов — все единицы:

Рассмотрим цепочки, в которых может быть только один нуль. По правилу нуля не может быть после двух единиц:

x1 1 0 1
x2 1 1 0
x3 1 1 1
x4 1 1 1
x5 1 1 1
x6 1 1 1
x7 1 1 1
x8 1 1 1

Рассмотрим цепочки с двумя нулями. По правилу два нуля не могут находиться рядом:

x1 1 0 1 0 1
x2 1 1 0 1 0
x3 1 1 1 0 1
x4 1 1 1 1 0
x5 1 1 1 1 1
x6 1 1 1 1 1
x7 1 1 1 1 1
x8 1 1 1 1 1

Построим оставшиеся цепочки:

x1 1 0 1 0 1 0 1 0 1
x2 1 1 0 1 0 1 0 1 0
x3 1 1 1 0 1 0 1 0 1
x4 1 1 1 1 0 1 0 1 0
x5 1 1 1 1 1 0 1 0 1
x6 1 1 1 1 1 1 0 1 0
x7 1 1 1 1 1 1 1 0 1
x8 1 1 1 1 1 1 1 1 0

Получается, что для данной системы существует 9 различных решений.

Задание: Сколько различных решений имеет система уравнений
((x1 ˄ x2) ˅ (¬x1 ˄ ¬x2)) → ((x3 ˄ x4) ˅ (¬x3 ˄ ¬x4)) = 1
((x3 ˄ x4) ˅ (¬x3 ˄ ¬x4)) → ((x5 ˄ x6) ˅ (¬x5 ˄ ¬x6)) = 1
((x5 ˄ x6) ˅ (¬x5 ˄ ¬x6)) → ((x7 ˄ x8) ˅ (¬x7 ˄ ¬x8)) = 1
((x7 ˄ x8) ˅ (¬x7 ˄ ¬x8)) → ((x9 ˄ x10) ˅ (¬x9 ˄ ¬x10)) = 1
где x1,x2,…,x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Для начала давайте рассмотрим одну из частей нашей системы:

Данное выражение будет истинно, если переменные x1 и x2 будут одновременно равны либо единице, либо нулю, что, фактически, совпадает с таблицей истинности для эквиваленции (тождества). То есть мы его можем записать так:

Упростим так всю нашу систему:
(x1 ≡ x2) → (x3 ≡ x4) = 1
(x3 ≡ x4) → (x5 ≡ x6) = 1
(x5 ≡ x6) → (x7 ≡ x8) = 1
(x7 ≡ x8) → (x9 ≡ x10) = 1

Теперь все стало проще. Обратите внимание, что каждая часть следования вполне самостоятельна, например (x1 ≡ x2) никак не связана переменными с (x3 ≡ x4). То есть мы можем упростить нашу систему еще раз:

A → B = 1
B → C = 1
C → D = 1
D → E = 1

Теперь давайте найдем все возможные комбинации переменных А-Е для этой системы. В импликации (следовании) ложь может быть только в одном случае, если первое выражение истинно, а второе — ложно. То есть при построении цепочек мы должны избежать комбинации 1,0:

A | 1 | 0 | 0 | 0 | 0 | 0
B | 1 | 1 | 0 | 0 | 0 | 0
C | 1 | 1 | 1 | 0 | 0 | 0
D | 1 | 1 | 1 | 1 | 0 | 0
E | 1 | 1 | 1 | 1 | 1 | 0

Переменные A-E в основной системе являются эквиваленцией, то есть на каждую истину или ложь принимают по два различных варианта. То есть для каждого столбца в нашей таблице предусмотрено 25 = 32 варианта.

Например, первый столбец — 1 1 1 1 1, то есть в каждое тождество системы должно давать 1, а это возможно в двух вариантах иксов: 0 ≡ 0 или 1 ≡ 1, то есть на каждую единицу таблицы приходится два варианта. То же самое и с нулями.

Всего в таблице у нас получилось 6 различных цепочек, каждая принимает по 32 варианта, то есть общее количество комбинаций: 6*32=192 комбинации.

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

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

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Рабочие листы и материалы для учителей и воспитателей

Более 2 500 дидактических материалов для школьного и домашнего обучения

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

Первый способ: самый простой – «табличный».

Он подходит для тех систем, где все уравнения однотипны, т.е. второе уравнение подобно первому, третье – второму и т.д. Каждое новое уравнение в системе должно содержать переменные, которые есть в предыдущем уравнении. Количество общих переменных не должно быть больше 2. Желательно, чтобы общие переменные имели одинаковые значения, т.е. были «парой». В противном случае, этот метод становится не эффективным и нужно решать СЛУ по-другому.

Пример 1. (демонстрационный вариант 2016 года)

Шаг 1. Найдём количество решений для первого уравнения. Из уравнения видно, что если две соседних переменные не равны, то следующая пара переменных обязательно должна быть равной: (x _i ≠ y _i )→(x _i+1 = y _i+1 ).

И наоборот, если первая пара переменных одинаковая, то следующая должна иметь разные значения: (x _i = y _i )→(x _i+1 ≠ y _i+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 наборов переменных.

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

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

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

Берем первую строку таблицы: x ₂ =0, y ₂ =1

Смотрим в таблице 1 чему будут равны переменные x ₁ и y ₁ : при x ₂ =0, а y ₂ =1, значения переменных x ₁ и y ₁ могут быть либо x ₁ =0, y ₁ =0, либо x ₁ =1, y ₁ =1.

Если x ₂ =1, а y ₂ =0, то x ₁ и y ₁ также могут быть либо x ₁ =0, y ₁ =0, либо x ₁ =1, y ₁ =1.

И так далее заполняем всю таблицу:

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

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

Всего в данной системе 8 уравнений.

Итого: 8*2*2*2*2*2*2*2=1024 решения.

Но такое простое решение подходит не для всех систем. Бывает, что даже для одного уравнения СЛУ трудно (невозможно) построить таблицу истинности, не говоря уже о том, чтобы объединить в таблице два уравнения.

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

Этот способ особенно эффективен, когда вы видите, что после замены можно получить логическую операцию – импликацию.

Шаг 1. Введем замены:

Тогда система уравнений примет более простой вид:

Можно переписать СЛУ в виде одного уравнения:

Как и СЛУ, это уравнение будет истинно только в том случае, когда каждый из множителей будет принимать значение ИСТИНА.

Шаг 2. Построим таблицу истинности для нашего уравнения, в которую войдут только те строки, при которых уравнение истинно.

Внутри скобок – операция импликация между двумя соседними переменными: Z _i →Z _i+1

Импликация принимает значение истина, если первая переменная будет меньше или равна второй переменной.

Это значит, что для того, чтобы всё уравнение (вся система) была истинна, необходимо и достаточно, чтобы Z _i ≤ Z _i+1

Шаг 3. Для каждого из набора решений Z ₁ -Z ₅ найдем количество решений x.

Возьмём первую строчку таблицы истинности: Z ₁ = 0, Z ₂ = 0, Z ₃ = 0, Z ₄ = 0, Z ₅ = 0

Импликация принимает значение ЛОЖЬ в одном единственном случае (1→0)

Общее количество решений: 1+3+9+27+81+243=364

Метод с заменой выражений очень хорош, но также не универсален. Есть такие СЛУ, где не подходит ни один из способов. Такие системы можно попытаться решить «целиком», не дробя на отдельные уравнения.

Третий способ: Анализ всей системы уравнений.

Решение: табличный способ не эффективен, т.к. слишком много общих переменных (x1,x2,x3). Метод замены не эффективен, т.к. корневая операция – конъюнкция.

Перепишем систему в следующем виде:

Для того, чтобы все уравнение было истинно, необходимо и достаточно, чтобы каждый из множителей принимал значение ИСТИНА.

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

Если в результате операции x ₁ *x ₂ была получена ЛОЖЬ, то x ₃ может принимать любое значение (0 или 1)

Если в результате операции x ₁ *x ₂ была получена ИСТИНА, то x ₃ может принимать только одно значение (1)

Следовательно, всего мы получаем 7 вариантов решений (для первого множителя).

Всего таких множителей 4, каждый из которых даст 7 решений. Итого: 7*7*7*7=2401 набор.