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

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

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

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); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

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

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

(А ∧ В) ∨ (¬А ∧ ¬В)=0

(В ∧ C) ∨ (¬B ∧ ¬C)=0

(С ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

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

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

		X1 ≡ X2

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

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

Ответ: 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\/y1 =1

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

Решение :

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

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

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

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

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

		X1 ∧ X10	¬X1 ∧ ¬ X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Обратите внимание на последний столбец, он совпадает с результатом действия X1 ≡ X10.

X1 ≡ X10

После упрощения получим:

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

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

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

(X1 ≡ X10) = 0

Рассмотрим последнее уравнение: (X1 ≡ X10) = 0 , т.е. х1 не должно совпадать с х10. Чтобы первое уравнение было равно 1, должно выполняться равенство (X1 ≡ X2)=1, т.е. х1 должно совпадать с х2.

Построим дерево решений первого уравнения:

Рассмотрим второе уравнение: при х10=1 и при х2=0 скобка должна быть равна 1 (т.е. х2 совпадает с х3); при х10=0 и при х2=1 скобка (X2 ≡ X10)=0 , значит, скобка (X2 ≡ X3) должна быть равна 1 (т.е. х2 совпадает с х3):

Рассуждая таким образом, построим дерево решений для всех уравнений:

Таким образом, система уравнений имеет всего 2 решения.

Ответ: 2.

Пример 3.

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

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

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Решение:

Построим дерево решений 1-го уравнения:

Рассмотрим второе уравнение:

• При х1=0 : вторая и третья скобки будут равны 0; чтобы первая скобка была равна 1, должны у1=1 , z1=1 (т.е. в этом случае - 1 решение)
• При х1=1 : первая скобка будет равна 0; вторая или третья скобка должна быть равна 1; вторая скобка будет равна 1 при у1=0 и z1=1; третья скобка будет равна 1 при у1=1 и z1=0 (т.е. в этом случае - 2 решения).

Аналогично для остальных уравнений. Отметим полученное кол-во решений у каждого узла дерева:

Чтобы узнать кол-во решений для каждой ветви, перемножим полученные числа по отдельности для каждой ветви (слева напрво).

1 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 решение

2 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 решения

3 ветвь: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 решения

4 ветвь: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 решения

5 ветвь: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 решения

Сложим полученные числа: всего 31 решение.

Ответ: 31.

3. Закономерное увеличение количества корней

В некоторых системах количество корней очередного уравнения зависит от количества корней предыдущего уравнения.

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Упростим первое уравнение: (x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тогда система примет вид:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

И т.д.

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

4 уравнение имеет 12 корней;

5 уравнение имеет 14 корней

8 уравнение имеет 20 корней.

Ответ: 20 корней.

Иногда количество корней растет по закону чисел Фибоначчи.

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

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

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

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ 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 наборов.

Ответ: 1024

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

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

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

¬x9 ∨ x10 = 1,

где 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 наборов.

Ответ: 11

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

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 , ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

				Кол-во наборов

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

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

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Наборы	Обозн .	Формула	Количество наборов
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255

Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. В математике существуют определенные задачи, которые посвящены логике высказываний. Чтобы решить данного рода уравнения необходимо обладать неким багажом знаний: знания законов логики высказываний, знания таблиц истинности логических функций 1 или 2 переменных, методы преобразования логических выражений. Кроме того, необходимо знать следующие свойства логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Любую логическую функцию от \ переменных - \можно задать таблицей истинности.

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

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Начнем решение с \[Х1\] и определим какие значения данная переменная может принимать: 0 и 1. Далее рассмотрим каждое их вышеприведенных значений и посмотрим, какое может быть при этом \[Х2.\]

Как видно из таблицы наше логическое уравнение имеет 11 решений.

Где можно решить логическое уравнение онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

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

Константа С имеет значение 1 или 0.

Логическое уравнение может иметь от 0 до различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:

Действительно, пусть задано уравнение:

В этом случае можно перейти к эквивалентному уравнению:

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

Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций :

Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции , что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения.

В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи.

В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений.

Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.

Задача 18

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

Ответ: Система имеет 36 различных решений.

Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений.

Построим дерево решений для импликации () - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева

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

Вот эти наборы: {(1, 1), (0, 1), (0, 0)}

Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная уже имеет значения на дереве, то на всех ветвях, где переменная имеет значение 1, переменная также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная имеет значение 0, даст разветвление на две ветви, где переменная получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:

имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:

Второе уравнение нашей системы аналогично первому:

Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных может быть скомбинировано с каждым решением для переменных , то общее число решений равно 36.

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

Задача 19

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

Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.

Из уравнения следует, что когда имеет значение 1(одно такое решение существует), то и имеет значение 1. Таким образом, существует один набор, на котором и имеют значения 1. При , равном 0, может иметь любое значение, как 0, так и 1. Поэтому каждому набору с , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.

Задача 20

Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:

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

Это уравнение имеет два решения, когда все равны либо 1, либо 0.

Задача 21

Сколько решений имеет уравнение:

Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:

Построим дерево решений для этого уравнения:

Задача 22

Сколько решений имеет следующая система уравнений?

Носкин Андрей Николаевич,
учитель информатики
высшей квалификационной категории,
кандидат военных наук, доцент
ГБОУ Лицей №1575 город Москва

Оптимизированный метод отображения для решения задачи 23 из КИМ ЕГЭ по информатике и ИКТ

Одной из самой трудной задачей в КИМ ЕГЭ является задача 23, в которой надо найти количество различных наборов значений логических переменных, которые удовлетворяют указанному условию.
Данная задача является едва ли не самым сложным заданием КИМ ЕГЭ по информатике и ИКТ. С ним, как правило, справляются не более 5% экзаменуемых {1}.
Такой маленький процент учеников, которые справились с данным заданием объясняется следующим:
- ученики могут путать (забыть) знаки логических операций;
- математические ошибки в процессе выполнения расчетов;
- ошибки в рассуждениях при поиске решения;
- ошибки в процессе упрощения логических выражений;
- учителя рекомендуют решать данную задачу, после выполнения всей работы, так как вероятность допущения
ошибок очень велика, а «вес» задачи составляет всего лишь один первичный балл.
Кроме того, некоторые учителя сами с трудом решают данный тип задач и поэтому стараются решать с детьми более простые задачи.
Также усложняет ситуацию, что в данном блоке существует большое количество разнообразных задач и невозможно подобрать какое-то шаблонное решение.
Для исправление данной ситуации педагогическим сообществом дорабатываются основные две методики решения задач данного типа: решение с помощью битовых цепочек {2} и метод отображений {3}.
Необходимость доработки (оптимизации) данных методик обусловлена тем, что задачи постоянно видоизменяются как по структуре, так и по количеству переменных (только один тип переменных Х, два типа переменных Х и Y, три типа: X, Y, Z).
Сложность освоения данными методиками решения задач подтверждается тем, что на сайте К.Ю. Полякова существует разборов данного типа задач в количестве 38 штук{4}. В некоторых разборах приведены более одного типа решения задачи.
Последнее время в КИМ ЕГЭ по информатике встречаются задачи с двумя типа переменных X и Y.
Я оптимизировал метод отображения и предлагаю своим ученикам пользоваться усовершенствованным методом.
Это дает результат. Процент моих учеников, которые справляются с данной задачей варьируется до 43% от сдающих. Как правило, ежегодно у меня сдает ЕГЭ по информатике от 25 до 33 человек из всех 11-х классов.
До появления задач с двумя типами переменными метод отображения ученики использовали очень успешно, но после появления в логическом выражении Y, я стал замечать, что у детей перестали совпадать ответы с тестами. Оказалось, они не совсем четко стали представлять, как составить таблицу отображений с новым типом переменной. Тогда мне пришла мысль, что для удобства надо все выражение привести к одному типу переменной, как удобно детям.
Приведу более подробно данную методику. Для удобства буду ее рассматривать на примере системы логических выражений, приведенных в {4}.
Сколько различных решений имеет система логических уравнений

(x 1 ^ y 1) = (¬x 2 V ¬ y 2 )
(x 2 ^ y 2) = (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5 ) = (¬ x 6 V ¬ y 6 )

где x 1 , …, x 6 , y 1 , …, y 6 , - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
1. Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У . Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z.
2. Теперь перепишем систему с новыми однотипными переменными. Сложность задачи будет заключаться во внимательной записи при замене переменных.

(z 1 ^ z 2) = (¬z 3 V ¬ z 4 )
(z 3 ^ z 4) = (¬ z 5 V ¬ z 6 )
...
(z 9 ^ z 10 ) = (¬ z 11 V ¬ z 12)

3. Построим таблицу, в которой переберем все варианты z 1 , z 2 , z 3 , z 4 , поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2 4); уберем из таблицы такие значения z 4 , при которых первое уравнение не имеет решения (зачеркнутые цифры).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Анализируя таблицу, строим правило отображения пар переменных (например, паре Z 1 Z 2 =00 соответствует пара Z 3 Z 4 = 11) .

5. Заполняем таблицу, вычисляя количество пар переменных, при котором система имеет решение.

6. Складываем все результаты: 9 + 9 + 9 + 27 = 54
7. Ответ: 54.
Приведенная выше оптимизированная методика решения задачи 23 из КИМ ЕГЭ позволила ученикам вновь обрести уверенность и решать успешно этот тип задачи.

Литература:

1. ФИПИ. Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ. Режим доступа: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. К.Ю. Поляков, М.А. Ройтберг. Системы логических уравнений: решение с помощью битовых цепочек. Журнал Информатика, № 12, 2014, с. 4-12. Издательский дом "Первое сентября", г.Москва.
3. Е.А. Мирончик, Метод отображения. Журнал Информатика, № 10, 2013, с. 18-26. Издательский дом "Первое сентября", г.Москва.