Как решать системы булевых уравнений

Как решать системы булевых уравнений

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

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

Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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 ₁ – истинно, тогда из первого уравнения получаем, что x ₂ также истинно, из второго — x ₃=1, и так далее до x_m = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы. Пусть теперь x ₁=0, тогда из первого уравнения имеем x ₂ =0 или x ₂ =1.

Когда x ₂ истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. При x ₂=0 получаем, что x ₃=0 или x ₃=, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных ( 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)

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

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

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

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

Основные логические операции

• Отрицание (инверсия, логическое НЕ)

Смысл операции: результат меняется на противоположный (вместо истины — ложь, вместо лжи — истина).

• Логическое сложение (дизъюнкция, логическое ИЛИ)

Смысл операции: результат — истина, если хотя бы один операнд — истина (операндом называется то значение или та переменная, над которым (которой) осуществляется операция).

Обозначения: V или +.

• Логическое умножение (конъюнкция, логическое И)

Смысл операции: результат — истина, если оба операнда — истина.

Обозначения: Λ или &.

• Исключающее ИЛИ (сложение по модулю 2, строгая дизъюнкция)

Смысл операции: результат — истина, если операнды различны.

Смысл операции: из лжи может следовать что угодно, а из истины — только истина.

Смысл операции: результат — истина, если операнды одинаковы.

Если в логическом выражении используется несколько логических операций, то их порядок определяется приоритетами логических операций:

Операцию “импликация” можно выразить через “ИЛИ” и “НЕ”:

Операцию “эквиваленция” также можно выразить через “ИЛИ” и “НЕ”:

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

Кроме обычных логических операций, применимых по отношению к логическим переменным, возможны поразрядные (побитовые) логические операции, выполняемые для пар “одноименных” (соответствующих одним и тем же разрядам) битов двух целых чисел. При этом двоичное значение 1 рассматривается как “истина”, а значение 0 — как “ложь”. Результатом выполнения поразрядной логической операции является целое число.

Для каждой пары битов выполняется логическая операция “И”.

Для каждой пары битов выполняется логическая операция “ИЛИ”.

Основные законы алгебры логики

Закон непротиворечия (высказывание не может быть одновременно истинным и ложным)

Закон исключения третьего (либо высказывание, либо его отрицание должно быть истинным)

Закон двойного отрицания

Законы де Моргана

Законы рефлексивности (идемпотенции)

Свойства логических констант 1 и 0

Полезно запомнить следующее правило: если известно количество решений уравнения F(x₁, х₂, . х_n) = 1, то количество возможных решений “противоположного” уравнения F(x₁, х₂, . х_n) = 0 равно разности количества всех возможных комбинаций значений переменных х₁, х₂. х_n (которое равно 2 n ) и количества решений уравнения F(x₁, х₂, . х_n) = 1 (и, соответственно, наоборот):

Это правило легко доказать, рассмотрев полную таблицу истинности логической функции F(x₁, х₂, . х_n): если исключить из нее строки, соответствующие значению F = 1, то останутся строки, соответствующие значению F = 0,и наоборот.

Разбор типовых задач

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

В ответе не нужно перечислять все различные наборы значений х₁, х₂, . х₁₀, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

1) Анализируется первое уравнение:

Последняя выполняемая операция здесь — И, поэтому:

Следует обратить внимание: в обеих частях записаны одни и те же тождества, только в первом случае они записаны “как есть”, а во втором — с отрицаниями. Тогда, если (х₁ ≡ х₂) = 1 и (х₃ ≡ х₄) = 1, то первая запись будет истинной, но тогда ¬(x₁ ≡ х₂) и ¬(х₃ ≡ х₄) оба будут ложными, и вторая запись ложна. И наоборот, при (х₁ ≡ х₂) = 0 и (х₃ ≡ х₄) = 0 первая запись будет ложной, а вторая (с отрицаниями) — истинной. Не подходит ни тот, ни другой вариант. “Спасает положение” то, что тождества в обеих записях соединены операцией ИЛИ, т.е. оба раза достаточно, чтобы единице было равно хотя бы одно из этих тождеств.

Вывод: чтобы первое уравнение системы было равно 1, нужно, чтобы либо (х₁ ≡ х₂) = 1 и (х₃ ≡ х₄) = 0, либо, наоборот, (х₁ ≡ х₂) = 0 и (х₃ ≡ х₄) = 1.

Первое из этих “либо” даёт такие варианты значений переменных, когда х₁ и х₂ одинаковы, а х₃ и х₄ различны:

Второе “либо”, аналогично, даёт варианты, в которых, наоборот, х₁ и х₂ различны, а х₃ и х₄ одинаковы:

Всего — 8 вариантов.

2) Добавляется в анализ второе уравнение:

Рассуждая аналогично и учитывая, что для х₃ и х₄ возможные варианты “унаследованы” от предыдущего уравнения, получается, что в вариантах значений х₅, х₆, добавленных этим вторым уравнением, для одинаковых значений х₃ и х₄ должны быть разными значения х₅ и х₆, а для различных значений х₃ и х₄ — одинаковые значения х₅ и х₆:

Итого из 8 предыдущих вариантов благодаря второму уравнению получается 16 (вдвое больше).

3) Очевидно, такая тенденция сохранится и дальше, ведь уравнения системы — типовые. Значит, добавление в рассмотрение третьего уравнения, пропущенного в записи системы и использующего переменные х₅, х₆, х₇, x₈, снова удвоит количество вариантов значений переменных: из 16 их получится 32.

Аналогично, последнее, четвёртое уравнение системы (переменные х₇, х₈, х₉, х₁₀) снова удваивает количество вариантов, “унаследованное” от предыдущего уравнения. В итоге для всей системы уравнений получается 64 возможных варианта значений переменных x₁ — x₁₀.

Ответ: 64 варианта значений переменных.

Задача 2. Сколько существует различных наборов значений логических переменных x₁, х₂, х₃, х₄, х₅, у₁, у₂, у₃, у₄, у₅, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных x₁, х₂, х₃, х₄, х₅, y₁, у₂, у₃, у₄, у₅, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Как и всегда при решении задач с системами логических уравнений, нужно сначала проанализировать каждое уравнение в отдельности. При этом, первое и второе уравнения заданной системы практически идентичны (с точностью до имён переменных — “игреки” вместо “иксов”), и это существенно облегчает работу.

Анализируя первое уравнение:

Таблица истинности логической операции следования: единственная ситуация, при которой её результат равен нулю, — когда из единицы следует нуль, а во всех других случаях эта операция возвращает единицу:

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

Чтобы найти все возможные комбинации значений переменных, задействованных в первом уравнении, удобнее всего выполнить построение дерева решений: это позволит не запутаться и не пропустить какие-то варианты. При построении дерева на каждом его очередном шаге анализируется очередная пара переменных и для каждой имеющейся ветви определяются дальнейшие варианты ветвления. Слева указываются логические операции следования, которые и анализируются на соответствующих шагах (уровнях дерева). Ключевым моментом при построении дерева является уже отмеченный выше факт, что для получения единичного результата из нуля может следовать любое значение второй переменной, а из единицы — только единица.

Основную идею при построении данного дерева можно условно выразить фразой: “размножаются только нули”. То есть если имеется начало набора значений пяти переменных, которое на данный момент завершается нулём, то продолжить его можно как нулём, так и единицей (в дереве имеется ветвление), но если текущая последовательность заканчивается единицей, то продолжать её можно только единицей, и в дереве не будет никакого ветвления, а только продолжение уже существующей ветви.

Полный набор возможных значений переменных, удовлетворяющих первому уравнению, тогда содержится в самой нижней строке построенного дерева (в его “листьях”): (х₁х₂х₃х₄х₅) = (00000), (00001), (00011), (00111), (01111), (11111).

Второе уравнение по структуре полностью совпадает с первым. Поэтому анализировать его нет необходимости, и можно сразу записать набор возможных для него значений переменных: (y₁y₂y₃y₄y₅) = (00000), (00001), (00011), (00111), (01111), (11111).

Если бы в условии задачи присутствовали только рассмотренные два уравнения, то, поскольку в них нет общих переменных, решением этой системы уравнений были бы все возможные попарные сочетания найденных наборов значений “иксов” и “игреков”. Именно третье уравнение, в котором одной логической операцией связаны один из “иксов” и один из “игреков”, является “ключом”, определяющим выбор: какие из найденных комбинаций наборов значений (х₁х₂х₃х₄х₅) и (y₁y₂y₃y₄y₅) подходят, а какие — нет.

Запись этого третьего уравнения:

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

• когда в наборе значений (y₁y₂y₃y₄y₅) пятая цифра равна нулю, в пару с ним годятся любые наборы значений (х₁х₂х₃х₄х₅), поскольку, что бы в них ни стояло в пятой позиции (0 или 1), результат операции у₅→ х₅ = 1 в любом случае будет равен 1 (см. таблицу истинности для этой операции);

• когда в наборе значений (y₁y₂y₃y₄y₅) пятая цифра равна единице, в пару с ним годятся только такие наборы значений (х₁х₂х₃х₄х₅), в которых пятая цифра равна 1.

Удобнее и нагляднее всего расписать все получаемые комбинации значений х и y виде таблицы (“матрицы решений”). Анализируемые цифры в ней выделены подчеркиванием.