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

Учитель информатики НОЧУ «Первая Московская гимназия»
Андреева Валентина Юрьевна

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

В 2011 году в ЕГЭ по информатике появилось новое задание – решение системы логических уравнений.  

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

Рассмотрим два примера, каждый из которых решим по-разному

Пример 1:

Сколько существует различных наборов значений логических переменных х1, х2, … х9, которые удовлетворяют всем перечисленным ниже условиям?

 = 1

 = 1

…

 = 1

Где х1, х2, … х9    - логические переменные?

В ответе не нужно перечислять все различные наборы значений переменных х1, х2, … х9, при которых  выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение:

1-й способ решения, используя анализ таблиц истинности (слева направо) и построения таблицы решений.

 Данную систему уравнений начинаем с решения  одного уравнения.

= 1

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

Далее  анализируем 2 уравнение. В нем при  х2=1 и х3=1 существует только одно решение второго уравнения при  х4=0 (см. таблицу истинности для второго уравнения она аналогична, в которой х1 заменим на х2, а х2 – на х3, х3 на х4)

Далее  анализируем 3 уравнение. В нем при х3=1, х4=0, существует только одно решение третьего  уравнения при х5=1

Далее  анализируем 4 уравнение. В нем при х4=0,  х5=1 существует только одно решение четвертого уравнения при х6=1

Далее  анализируем 5 уравнение. В нем  при х5=1,  х6=1существует только одно решение  пятого уравнения при х7=0

Далее  анализируем 6 уравнение. В нем при х6=1,  х7=0 существует только одно решение шестого уравнения  при х8=1

Далее  анализируем 7 уравнение. В нем при х7=0,  х8=1 существует только одно решение, седьмого уравнения при х9=1,  

Таким образом, мы проанализировали таблицу решений для первого набора. В этой ветке имеем 1 решение.

Далее строим дерево решений для второго набора из первого уравнения. При х1=1, существует два набора х2=1, х3=0,  и х2=0, х3=1. Строим таблицу решений для первого набора

Далее  анализируем 2 уравнение. В нем при  х2=1 и х3=0 существует только одно решение второго уравнения при  х4=1 (см. таблицу истинности для второго уравнения она аналогична, в которой х1 заменим на х2, а х2 – на х3, х3 на х4)

Далее  анализируем 3 уравнение. В нем при х3=0, х4=1, существует только одно решение третьего  уравнения при х5=1

Далее  анализируем 4 уравнение. В нем при х4=1,  х5=1 существует только одно решение четвертого уравнения при х6=0

Далее  анализируем 5 уравнение. В нем  при х5=1,  х6=0существует только одно решение  пятого уравнения при х7=1

Далее  анализируем 6 уравнение. В нем при х6=0,  х7=1 существует только одно решение шестого уравнения  при х8=1

Далее  анализируем 7 уравнение. В нем при х7=1,  х8=1 существует только одно решение, седьмого уравнения при х9=0,  

Таким образом, мы проанализировали  вторую ветку из таблицы решений. В этой ветке получили одно решение.

Далее строим дерево решений для третьего  набора из первого уравнения.

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

Итак, в сумме мы имеем 3 решения.

Ответ: 3.

2-й способ решения системы уравнений, используя компьютер

Для проверки правильности решений предлагаю решить систему уравнений на компьютере.  Программа приведена на языке программирования PascalABC. Решаем систему уравнений, приведенную в предыдущем примере:

 = 1

 = 1

…

 = 1

f1 – соответствует 1 уравнению, f2 = второму и т.д. Поскольку все уравнения =1, то результирующая функция f, равна логическому произведению всех семи функций.

Программа выглядит следующим образом:

program b15;

var x1,x2,x3,x4,x5,x6,x7,x8,x9,f,f1,f2,f3,f4,f5,f6,f7: boolean;

   { вводим копии основных переменных }

   x11,x12,x13,x14,x15,x16,x17,x18,x19,f11,f12,f13,f14,f15,f16,f17,f0,

   i:integer;

begin

writeln ('   x1   x2   x3   x4   x5   x6   x7   x8   x9     f1    f2    f3    f4    f5    f6    f7    f    ');

i:=0;  {устанавливавем  счетчик количества решений  = 0}

x11:=0;x12:=0;x13:=0;x14:=0;x15:=0;x16:=0;x17:=0;x18:=0;x19:=0;

For x1:=false to true do

 for x2:=false to true do

  for x3:=false to true do

   for x4:=false to true do

    for x5:=false to true do

     for x6:=false to true do

      for x7:=false to true do

       for x8:=false to true do

        for x9:=false to true do

        begin

f1:=(not x1 and x2 and x3)or(x1 and not x2 and x3) or (x1 and x2 and not x3);

f2:=(not x2 and x3 and x4)or(x2 and not x3 and x4) or (x2 and x3 and not x4);

f3:=(not x3 and x4 and x5)or(x3 and not x4 and x5) or (x3 and x4 and not x5);

f4:=(not x4 and x5 and x6)or(x4 and not x5 and x6) or (x4 and x5 and not x6);

f5:=(not x5 and x6 and x7)or(x5 and not x6 and x7) or (x5 and x6 and not x7);

f6:=(not x6 and x7 and x8)or(x6 and not x7 and x8) or (x6 and x7 and not x8);

f7:=(not x7 and x8 and x9)or(x7 and not x8 and x9) or (x7 and x8 and not x9);

f:=f1 and f2 and f3 and f4 and f5 and f6 and f7;

{задание вспомогательных переменных, для более наглядного отображения таблиц истинности }

        if x1 then x11:=1  else x11:=0; if x2 then x12:=1 else x12:=0;

        if x3 then x13:=1  else x13:=0; if x4 then x14:=1 else x14:=0;

        if x5 then x15:=1  else x15:=0; if x6 then x16:=1 else x16:=0;

        if x7 then x17:=1  else x17:=0; if x8 then x18:=1 else x18:=0;

        if x9 then x19:=1  else x19:=0; if f1 then f11:=1  else f11:=0;

        if f2 then f12:=1  else f12:=0; if f3 then f13:=1  else f13:=0;

        if f2 then f14:=1  else f14:=0; if f2 then f15:=1  else f15:=0;

        if f6 then f16:=1  else f16:=0; if f7 then f17:=1  else f17:=0;

        if f  then f0:=1  else f0:=0;

{ на экран выдаются только решения}

           if F then  begin

                i:=i+1 ;

                writeln (x11:5, x12:5, x13:5, x14:5, x15:5, x16:5, x17:5,       x18:5, x19:5, f11:7, f12:6, f13:6, f14:6, f15:6, f16:6, f17:6, f0:5);

                end;

        end;

        writeln('количество решений = ',i);

        end.

Результат работы программы 

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

Пример 2:

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

…

Где х1, х2,…,х10 – логические переменные. В ответе не нужно перечислять все различные наборы переменных, при которых выполнена данная система равенств, а нужно указать количество таких наборов.

Решение:

Построим таблицу истинности для первого уравнения

Мы видим, что первое уравнение имеет 4 решения. Причем тогда, когда х1=х2, а значение х3 может принимать оба значения (0,1).

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

Построим таблицу истинности для суммы первого и второго уравнений.

Отдельно 2-ое уравнение имеет 4 решения. Когда мы рассматриваем сумму первого и второго уравнений, видно, что в сумме тоже имеем 4 решения, так решение не зависит от значения переменной х4, при этом х1≡х2≡х3.

Вторую таблицу истинности мы построили только для наглядности, нет необходимости в её построении, так как из первой таблицы видно, что наборы из строк 4 и 5 (таблица истинности первого уравнения) выбывают из решения так как  х2≠х3,  и решение будет иметь место только в случае х2=х3 и не зависеть от х4, то есть имеем тоже 4 решения.

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

В результате получаем в ответе 4 решения системы уравнений.

Построим   дерево решений

 Рис.2.

Ответ: 4.

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