МЕТОД РЕШЕНИЯ СИСТЕМ ЛОГИЧЕСКИХ УРАВНЕНИЙ

МЕТОД РЕШЕНИЯ СИСТЕМ ЛОГИЧЕСКИХ УРАВНЕНИЙ

Аннотация. В статье приводится метод решения систем логических уравнений. Системы логических уравнений включены в Единый государственный экзамен по информатике. Решение систем вызывает трудности у учащихся школ. Представленный метод помогает упростить решение.

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

Тема «Математическая логика» традиционно вызывает трудности у школьников при изучении, и, как следствие, задачи на эту тему в ЕГЭ по информатике являются одними из самых наименее решаемых задач. Некоторые сложности, с которыми сталкиваются учащиеся, рассматриваются в [8, 9].

В данной статье предлагается один из методов решении задачи ЕГЭ-23. В задании ЕГЭ-23 выпускники должны решить систему логических уравнений. Методы решения таких систем рассматриваются и предлагаются разными авторами [1 – 7].

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

Пример 1. Рассмотрим задачу [6].

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

¬(x1  x2)  ¬(x2  x3) = 1

¬(x2  x3)  ¬(x3  x4) = 1

...

¬(x8  x9)  ¬(x9  x10) = 1

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

Решение.

Проанализировав систему, видим, что уравнения одинаковые с точностью до переменных, при этом зависящие от одних и тех же переменных. Первое уравнение зависит от переменных x1, x2, x3, а второе уравнение – от переменных x2, x3, x4.

Уравнения представляют собой дизъюнкцию двух выражений, и дизъюнкция должна принимать значение «истина».

Если первое выражение ¬(x1  x2) истинно, то тогда значение второго выражения может быть и «истина» и «ложь».

Если же первое выражение ¬(x1  x2) ложно, то значение второго выражения может быть только

«истина».

Запишем решения первого уравнения с помощью таблицы истинности:

x1           x2           x3

0             0             1

                1             0

                               1

1             0             0

                               1

                1             0

После построения такой таблицы найдем закономерность:

–             пары (0,0) и (1,1) дают по одной паре (0,1) и (1,0), соответственно;

–             пары (0,1) и (1,0) дают по две пары (1,0) и (1,1), (0,0) и (0,1).

Можно сделать вывод: пары с разными значениями дают 2 пары (одна с одинаковыми значениями, другая – с разными), а пары с одинаковыми – дают пары с разными.

Запишем решение далее по шагам, на 1 шаге рассматриваем пару (x1, x2). Для уравнения с 10 переменными получим 9 шагов.

1             2од + 2разн

2             2разн+2од+2разн= 2од+4разн

3             4од+6разн

4             6од+10разн

5             10од+16разн

6             16од+26разн

7             26од+42разн

8             42од+68разн

9             68од+110разн

Получаем общий ответ: 68+110=178 решений.

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

Рассмотрим еще несколько примеров задач, решаемых с помощью предлагаемого метода по шагам.

Пример 2. «Дана система логических уравнений

(x1  x2)  (y1  y2)  (x1  y1) = 0 (x2  x3)  (y2  y3)  (x2  y2) = 0

…

(x6  x7)  (y6  y7)  (x6  y6) = 0 (x7  y7) = 0

где x1, x2, …, x7, y1, y2, …, y7 – логические переменные. Найдите количество решений этой системы» [6].

Решение.

Проанализировав систему, видим, что уравнения одинаковые с точностью до переменных, при этом зависящие от одних и тех же переменных. Первое уравнение зависит от переменных x1, x2, y1, y2, а второе уравнение – от переменных x2, x3, y2, y3.

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

«ложь»:

(x1  x2) = 0, (y1  y2) = 0, (x1  y1) = 0.

Запишем решения первого уравнения с помощью таблицы истинности:

x1           y1           x2           y2

0             0             0              0

1             0

0             0

0             1             1

1             0

1             0             1              0

Заметим при этом сразу, что пара (1, 1) не удовлетворяет условию (x1  y1) = 0, поэтому такие пары не рассматриваем далее.

После построения такой таблицы найдем закономерность:

–             пара (0, 0) дает пары (0, 0) и (1, 0);

–             пара (0, 1) дает пары (0, 0), (0,1), (1,0);

–             пара (1, 0) дает пару (1,0).

Запишем решение далее по шагам, на 1 шаге рассматриваем пару (x1, y1). Для этой пары имеем 3 набора, далее для 2 пары получаем 6 наборов, и так далее записываем количество наборов для всех пар:

1             100 + 101 + 110

2             200 + 101 + 310

3             300 + 101 + 610

4             400 + 101 + 1010

5             500 + 101 + 1510

6             600 + 101 + 2110

7             700 + 101 + 2810

Получаем общий ответ: 7 + 1 + 28 = 36 решений.

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

(x1  y1) (x2  y2) =1 (x2  y2) (x3  y3) = 1 (x3  y3) (x4  y4) =1 (x4  y4) (x5  y5) =1 (x5  y5) (x6  y6) =1

где x1, x2, …, x6    и y1, y2, …, y6    – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов» [6].

Решение.

Проанализировав систему, видим, что уравнения одинаковые с точностью до переменных, при этом зависящие от одних и тех же переменных. Первое уравнение зависит от переменных x1, x2, y1, y2, а второе уравнение – от переменных x2, x3, y2, y3.

Уравнения представляют собой импликацию выражений, которая должна принимать значение «истина». Следовательно, в каждом уравнении не подходят наборы, когда первое выражение «истина», а второе – «ложь»:

(x1  y1) = 1, (x2  y2) = 0.

Выражение (x1  y1) представляет собой эквивалентность, и принимает значение «истина» в случае, когда и x1, y1 имеют одинаковые значения.

Выражение (x2  y2) представляет собой дизъюнкцию, и принимает значение «ложь» в случае, когда и x2, y2 одновременно принимают значение «ложь».

Запишем решения первого уравнения с помощью таблицы истинности:

x1           y1           x2           y2

0             1

0             0             1              0

1

0             0

0             1             1

1             0

1

0             0

1             0             1

1             0

1

0             1

1             1             1              0

1

После построения таблицы найдем закономерность:

–             пары (0,0) и (1,1) дают три пары решений (0,1), (1,0) и (1,1);

–             пары (0,1) и (1,0) дают четыре пары решений (0,0), (0,1), (1,0) и (1,1).

Можно сделать вывод: пары с разными значениями дают 4 пары (две с одинаковыми значениями, две – с разными), а пары с одинаковыми – дают 3 пары (одну с одинаковыми значениями, две – с разными).

Запишем решение далее по шагам, на 1 шаге рассматриваем пару (x1, y1). Для этой пары имеем 3 набора, далее для 2 пары получаем 6 наборов, и так далее записываем количество наборов для всех пар:

1             2од + 2разн

2             6од+8разн

3             22од+28разн

4             78од+100разн

5             278од+356разн

6             990од+1268разн

Получаем общий ответ: 990 + 1268 = 2258 решений.

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

(x1 (x2  y1))  (y1  y2) = 1

(x2 (x3  y2))  (y2  y3) = 1

...

(x8 (x9  y8))  (y8  y9) = 1 (x9  y9) = 1

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

количество таких наборов» [6].

Решение.

Проанализировав, как и в предыдущих примерах, систему, видим, что уравнения одинаковые с точностью до переменных, при этом зависящие от одних и тех же переменных. Первое уравнение зависит от переменных x1, x2, y1, y2, а второе уравнение – от переменных x2, x3, y2, y3.

Уравнения представляют собой конъюнкцию двух выражений, и конъюнкция должна принимать значение «истина». Следовательно, выражения (x1 (x2  y1)) и (y1  y2) должны принимать значение «истина» одновременно.

И первое, и второе выражения – это импликация, которая должна принимать значение «истина». Следовательно, в каждом уравнении не подходят наборы, когда первая переменная в выражении «истина», а вторая – «ложь».

В первом выражении при x1 = 1 x2 и y1 могут быть только «1», в противном случае все выражение примет значение «ложь».

Во втором выражении при y1 = 1 y2 может быть только «1», в противном случае также все выражение примет значение «ложь».

Запишем решения первого уравнения с помощью таблицы истинности:

x1           y1           x2           y2

0             0

0             0             0              1

1             1

0             1             0              1

1             1

1             1             1              1

Заметим при этом сразу, что пара (1, 0) не удовлетворяет условию (x1 (x2  y1)) = 1, поэтому такие пары не рассматриваем далее.

После построения таблицы истинности найдем закономерность:

–             пара (0, 0) дает пары (0, 0), (0,1) и (1, 1);

–             пара (0, 1) дает пары (0,1) и (1,1);

–             пара (1, 1) дает пару (1,1).

Запишем решение далее по шагам, на 1 шаге рассматриваем пару (x1, y1). Для этой пары имеем 3 набора, далее для 2 пары получаем 6 наборов, и так далее записываем количество наборов для всех пар:

1             100 + 101 + 111

2             100 + 201 + 311

3             100 + 301 + 611

4             100 + 401 + 1011

5             100 + 501 + 1511

6             100 + 601 + 2111

7             100 + 701 + 2811

8             100 + 801 + 3611

9             100 + 901 + 4511

Получаем общий ответ: 1 + 9 + 45 = 36 решений.

ЛИТЕРАТУРА

1.            Бадагиева, Е.З. Решение систем логических уравнений с опорой на построение таблицы истинности // Информатика в школе. – 2017. –

№4(127). – С. 40 – 45.

2.            Балабанов, А.А., Орлова, Д.А. Решение систем логических уравнений на основе совместного применения рекуррентного метода и теоретико-множественного подхода // Электронные информационные системы. – 2015. – №3(6). – С. 76 – 89.

3.            Бушмелева, Н.А. Решение систем логических уравнений методом отображений // Педагогическое искусство. – 2018. – №2. – С. 29 – 32.

4.            Криветченко, О.В. Типологизация методов решения систем логических уравнений информационные технологии в прикладных исследованиях // Информационные технологии в прикладных исследованиях. Сборник научных трудов. – Новосибирск, 2013. – Выпуск 3. – С. 249 – 267.

5.            Поляков, К.Ю., Ройтберг, М.А. Системы логических уравнений: решение с помощью битовых цепочек // Информатика. – 2014. – № 12.

– С. 4 – 12.

6.            Поляков, К.Ю. Сайт Константина Полякова. – http://kpolyakov.spb.ru/download/ege2020kp.7z.

7.            Семенов, С.М. Решение систем логических уравнений в задачах ЕГЭ по информатике // Сборник научных трудов Четырнадцатой Международной научно-практической конференции «Применение технологий «1С» для повышения эффективности деятельности организаций образования». Москва, 28-29 января 2014 г. – С. 368 – 370.

8.            Фирсова, С.А. Применение пакета "MATHCAD" для визуализации решения некоторых заданий ЕГЭ по информатике // Информационные и инновационные технологии в образовании. Сборник материалов III-й Всероссийской научно-практической конференции. под ред. С.С. Белоконовой. – 2019. – С. 199 – 200.

9.            Шантарович, Е.А., Фирсова, С.А. Понятие логического мышления и его составляющих // Педагогическая наука и педагогическая практика. Сборник научных трудов по материалам Международной научно-практической конференции. Санкт-Петербург, 30 января 2020 г. – 2020. – С. 54 – 56.