Решение системы логических уравнений методом дерева
Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности и декомпозиция.
Задача: Решить систему логических уравнений:
Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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 2 → x 3)*…*( xm -1 → xm ) = 1.
Предположим, что 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.
Источник
Методы решения систем логических уравнений
статья по информатике и икт (10 класс) по теме
Решить систему логических уравнений можно, например, с помощью таблицы истинности (если количество переменных не слишком велико) или с помощью дерева решений, предварительно упростив каждое уравнение.
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 решения.
Сложность решения систем логических уравнений состоит в громоздкости полного дерева решений. Метод рассуждений позволяет не строить все дерево полностью, но понять при этом, сколько оно будет иметь ветвей. Рассмотрим этот метод на конкретных примерах.
Пример 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 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение : Упростим систему. Построим таблицу истинности части первого уравнения:
Источник
Решение системы логических уравнений методом дерева
Предположим, что x1 – истинно, тогда из первого уравнения получаем, что x2 также истинно. Далее из второго уравнения получаем, что x3 истинно, и т.д. до xm = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы.
Пусть теперь x1 – ложно, тогда из первого уравнения следует, что x2 может быть как истинным, так и ложным, то есть может принимать значения как 0, так и 1.
В случае, если x2 истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. В случае, когда x2 – ложно получаем, что для x3 есть две возможности, 0 и 1, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных (m+1 решение, в каждом решении по m значений переменных):
Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Получив единицу, все остальные значения переменных также становятся единицами, получив же ноль, возможны два варианта 0 и 1. Для одного уравнения дерево состоит из двух уровней, для двух уравнений добавляется одна переменная и соответственно один уровень дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m+1.
В случае трудностей в рассуждениях и построении дерева решений можно искать решение с использованием таблиц истинности, для одного – двух уравнений.
Система двух уравнений истина в четырех случаях (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). При этом сразу видно, что существует решение, состоящее из одних нулей и еще m решений, в которых добавляется по одной единице, начиная с последней позиции до заполнения всех возможных мест. Можно предположить, что общее решение будет иметь такой же вид. Хотя это, конечно, не решение, но ответ таким образом угадать можно. Для того, чтобы такой подход стал решением, требуется доказательство, что предположение верно.
Решая систему, любым из вышеописанных методов, получим 5 различных решений: (0; 1; 0), (0; 1; 1), (1; 0; 1), (1; 1; 0), (1; 1; 1). Для системы из трех уравнений имеем 8 решений – (0; 1; 0; 1), (0; 1; 1; 0), (0; 1; 1; 1), (1; 0; 1; 0), (1; 0; 1; 1), (1; 1; 0; 1), (1; 1; 1; 0), (1; 1; 1; 1).
Проанализировав данную систему логических уравнений, можно сделать вывод: если первая переменная любого уравнения принимает значение 0, то вторая переменная этого же уравнения обязательно примет значение 1, в противном случае, произвольное значение 1 или 0.
Обозначим Nk – общее количество решений системы k уравнений, N_k^0, N_k^1 – количество решений этой системы, последняя переменная которых соответственно равна 0 или 1. Понятно, что N_1^0 = 1, N_1^1 = 2.
Для представленной системы, получаем такое рекуррентное соотношение, с начальными условиями N1 = 3, N2 = 5. Такому соотношению соответствуют числа Фибоначчи, то есть элементам числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …, в которой каждое последующее число равно сумме двух предыдущих чисел.
Сравнив начальные значения с последовательностью Фибоначчи, получаем, что количество различных решений равно (n+2)-му члену последовательности Фибоначчи Fn+2.
Источник