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

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

Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15)

Скачать:

Предварительный просмотр:

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

Решить систему логических уравнений можно, например, с помощью таблицы истинности (если количество переменных не слишком велико) или с помощью дерева решений, предварительно упростив каждое уравнение.

1. Метод замены переменных.

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

Рассмотрим применение этого метода на конкретном примере.

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

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).

Тогда система уравнений будет выглядеть так:

Построим дерево решений полученной системы:

Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:

Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:

Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.

2. Метод рассуждений.

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

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Первое и второе уравнения содержат независимые переменные, которые связаны третьим условием. Построим дерево решений первого и второго уравнений.

Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:

Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.

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

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение : Упростим систему. Построим таблицу истинности части первого уравнения:

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

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

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

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

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

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

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

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

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

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

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

Обозначения: 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 виде таблицы (“матрицы решений”). Анализируемые цифры в ней выделены подчеркиванием.