Методическая разработка по теме: «Использование метода битовых цепочек при решении систем логических уравнений»

Методическая разработка по теме:

«Использование метода битовых цепочек при решении систем логических уравнений»

Рыжова Н.И.

учитель информатики и ИКТ

МОУ лицей № 4 г. Ейска Краснодарского края

г.Ейск

2013 год

Содержание

1.      Вступление

2.      Уравнения с импликацией в произведении

3.      Задания для самостоятельной работы учащихся

4.      Ответы к заданиям

5.      Заключение

6.      Список используемой литературы

Вступление

В своей работе по подготовке учащихся к сдаче Единого Государственного Экзамена я часто сталкиваюсь с трудностями понимания учащихся решения задания №23 на системы логических уравнений. Это задание относится к заданиям высокого уровня сложности. В Интернет и печатных изданиях есть огромное количество публикаций по этой теме. Изучая и просматривая эти работы я пришла к выводу о том, что это огромное «море» теоретического и практического материала необходимо осмыслить, систематизировать и выработать методику преподавания данной темы на дополнительных и факультативных занятиях для подготовке к ЕГЭ.

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

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

Уравнения с импликацией в произведении

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) Ù (x₅ ® x₆) = 1

(y₁ ® y₂) Ù (y₂ ® y₃) Ù (y₃ ® y₄) Ù (y₅ ® y₆)= 1

(Øy₁Úx₁)Ù(Øy₁Úx₂) Ù (Øy₃Úx₃) Ù (Øy₄Úx₄)Ù(Øy₅ Úx₅) Ù(Øy₆ Ú x₆)= 1

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

Из определения импликации следует, что импликация истинна если x_i <= x_i+1. Поэтому, если x1=1, то остальные xi в цепочке решения должны все быть равны 1. Если же в цепочке решений идут последовательно нули (0000…..) и в каком-то месте появилась 1, то все оставшиеся будут только 1. Например в решении 0000скачок1111, скачок может быть только один раз. Из второго уравнения мы можем тоже самое сказать и для аргумента y.

Из 3-го уравнения Øy_i Ú x_i= y_i ® x_i поэтому y_i <= x_i

Начинаем выписывать корни:

Для X=1 1 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1

0 0 0 1 1 1         7 наборов корней

0 0 1 1 1 1

0 1 1 1 1 1

1 1 1 1 1 1

Для X=0 1 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1           6 наборов корней

0 0 0 1 1 1

0 0 1 1 1 1

0 1 1 1 1 1

Для X=0 0 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1           5 наборов корней

0 0 0 1 1 1

0 0 1 1 1 1

Для X=0 0 0 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1           4 наборов корней

0 0 0 1 1 1

Для X=0 0 0 0 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1           3 наборов корней

Для X=0 0 0 0 0 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1         2 наборов корней

Для X=0 0 0 0 0 0

Матрица решений по Y будет

0 0 0 0 0 0           1 набор корней

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

К=7+6+5+4+3+2+1=28 решений

Рассмотрим еще один пример

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) Ù (x₅ ® x₆) = 1

(x₁® Øy₁) Ù (x₂® Øy₂) Ù (x₃® Øy₃) Ù (x₄® Øy₄) Ù(x₅® Øy₅) Ù(x₆® Øy₆)=1

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

Из первого уравнения имеем x_i <= x_i+1. Из второго уравнения имеем x_i <= Øy_i.

Из второго уравнения видим, что нет четкого перехода от 0 к 1:

Если x_i=0, то y_i может быть равным либо 0, либо 1. Если же x_i=1, то y_i может быть равным только 0.

На основании этих свойств битовых цепочек начинаем выписывать корни.

Для X=1 1 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0            1 набор корней

Для X=0 1 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0            2 набора корней

1 0 0 0 0 0

Для X=0 0 1 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 1 0 0 0 00            4 набора корней

1 0 0 0 0 0

1 1 0 0 0 0

Для X=0 0 0 1 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 1 0 0 0

0 1 0 0 0 0

0 1 1 0 0 00            8 наборов корней

1 0 0 0 0 0

1 0 1 0 0 0

1 1 0 0 0 0

1 1 1 0 0 0

Для X=0 0 0 0 1 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 1 0 0            16 наборов корней

. . . . .  .

1 1 1 0 0 0

1 1 1 1 0 0

Для X=0 0 0 0 0 1

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 1 0            32 набора корней

. . . . .  .

1 1 1 1 0 0

1 1 1 1 1 0

Для X=0 0 0 0 0 0

Матрица решений по Y будет

0 0 0 0 0 0

0 0 0 0 0 1            64 набора корней

. . . . .  .

1 1 1 1 1 0

1 1 1 1 1 1

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

К=1+2+4+8+16+32+64=127 решений

Рассмотрим еще один пример

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

(x₁ Ú x₂) Ù (Øx₁ Ú Øx₂) Ù (x₁ ® Øy₁)=1

(x₂ Ú x₃) Ù (Øx₂ Ú Øx₃) Ù (x₂ ® Øy₂)=1

. . . . . . . . . . . . . . . .

(x₆ Ú x₇) Ù (Øx₆ Ú Øx₇) Ù (x₆ ® Øy₆)=1

X₇ ® Øy₇=1

где x₁, …, x₄, y₁, …, y₄, z₁, …, z₄, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Сгруппируем первые две скобки в каждом уравнении. Из теории(смотрите часть 1) видно, что это строгая дизъюнкция аргументов x_i Å x_i+1. Перегруппируем уравнения, тат как произведение скобок равно 1.

Получаем после замены и перегруппировки:

(x₁ Å x₂) Ù(x₁ ® Øy₁)=1

(x₁ Å x₂) Ù(x₁ ® Øy₁)=1

. . . . . . . . . . . .

(x₁ Å x₂) Ù(x₁ ® Øy₁)=1

X₇ ® Øy₇=1

Затем

(x₁ Å x₂) Ù(x₂ Å x₃) Ù(x₃ Å x₄) Ù(x₄ Å x₅) Ù(x₅ Å x₅) Ù(x₆ Å x₇)=1

(x₁® Øy₁) Ù(x₂®Øy₂) Ù(x₃®Øy₃) Ù(x₄®Øy₄) Ù(x₅®Øy₅) Ù(x₆® Øy₆) (x₇® Øy₇)=1

По свойству строгой дизъюнкции (она истинна только если аргументы разные:либо0 1, либо 1 0) из первого уравнения получаем две битовые цепочки или «пилы»: первая пила начинающаяся с 0, вторая пила начинающаяся с 1. Для аргументов

x₁ x₂ x₃ x₄ x₅ x₆ x₇

0  1  0 1  0  1 0 (первая пила, начинающаяся с 0)

1  0  1 0  1  0 1 (вторая пила, начинающаяся с 1)

Разберем корни для первой пилы

Для X=0 1 0 1 0 1 0

Матрица решений по Y будет такова, что всего в цепочке решений по Х ровно 4 нуля, а для Y они дадут матрицу решений от 0000 до 1111, т.е. 16 строк-решений, там где в цепочке решений по X будут единицы в матрице решений по Y ,будут также 1. Эта логика построения цепочек следует из второго уравнения. В нем если x_i=0, то y_i может быть равным либо 0, либо 1. Если же x_i=1, то y_i может быть равным только 0.

Матрица решений по Y будет

   0   1   0    1   0    1    0

0   1  0  0  1  0  0  1  0  0   1

Для X=1 0 1 0 1 0 1

Матрица решений по Y будет такова, что всего в цепочке решений по Х ровно 3 нуля, а для Y они дадут матрицу решений от 000 до 111, т.е. 8 строк-решений, там где в цепочке решений по X будут единицы в матрице решений по Y ,будут также 1. Эта логика построения цепочек следует из второго уравнения. В нем если x_i=0, то y_i может быть равным либо 0, либо 1. Если же x_i=1, то y_i может быть равным только 0.

Матрица решений по Y будет

1   0    1   0    1    0    1

0  0  1  0  0  1  0  0   1  0

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

К=16+8=24 решений

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

Задания для самостоятельной работы учащихся

Задание 1

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

(Øx₁ ® x₂) Ù Ø(x₁ ® Øx₃) Ù (Øx₂ ® y₁) = 1

(Øx₂ ® x₃) Ù Ø(x₂ ® Øx₄) Ù (Øx₃ ® y₂) = 1

...

(Øx₆ ® x₇) Ù Ø(x₆ ® Øx₈) Ù (Øx₇ ® y₆) = 1

(Øx₇ ® x₈) Ù Ø(x₇ ® Øy₇) = 1

(Øy₇ ® y₈) = 1

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

Задание 2

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

(x₁ ® (x₂ Ú y₂)) Ù (y₁ ® y₂) = 1

(x₂ ® (x₃ Ú y₃)) Ù (y₂ ® y₃) = 1

...

(x₇ ® (x₈ Ú y₈)) Ù (y₇ ® y₈) = 1

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

Задание 3

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) = 1

(у₁ ® у₂) Ù (у₂ ® у₃) Ù (у₃ ® у₄) = 1

(Øy₁ Ú x₁) Ù (Øx₂ Ú y₂) = 1

где x₁,x₂,…,x_4, у₁,у₂,…,у₄ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Задание 4

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) Ù (x₄ ® x₅) Ù (x₅ ® x₆) = 1

(у₁ ® у₂) Ù (у₂ ® у₃) Ù (у₃ ® у₄) Ù (у₄ ® у₅) Ù (у₅ ® у₆) = 1

x₁ Ú y₁  = 1

где x₁,x₂,…,x_6, у₁,у₂,…,у₆ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Задание 5

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

(x₁ ® Øx₂) Ù (x₁ ® Øx₃) Ù (x₁ ® Øx₄) Ù (x₁ ® Øx₅) = 1

(Øу₁ ® у₂) Ù (у₂ ® Øу₃) Ù (Øу₃ ® у₄) Ù (у₄ ® Øу₅) = 1

(Øx₁ Ú y₁ ) Ù  x₁= 1

где x₁,x₂,…,x_5, у₁,у₂,…,у₅ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Задание 6

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) = 1

(y₁ ® y₂) Ù (y₂ ® y₃) Ù (y₃ ® y₄) = 1

 (z₁ ® z₂) Ù (z₂ ® z₃) Ù (z₃ ® z₄) = 1

 x₁ Ú y₁  Ú z₁ = 1

где x₁,x₂,…,x_4, у₁,у₂,…,у_4, z₁,z₂,…,z₄ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Задание 7

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄) Ù (x₄ ® x₅) = 1

(y₁ ® y₂) Ù (y₂ ® y₃) Ù (y₃ ® y₄) Ù (y₄ ® y₅) = 1

(z₁ ® z₂) Ù (z₂ ® z₃) Ù (z₃ ® z₄) Ù (z₄ ® z₅) = 1

x₃ Ù y₄ Ù z₅  = 0

где x₁, …, x₅, y₁, …, y₅, z₁, …, z₅, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Ответы к заданиям

1)      128

2)      1012

3)      15

4)      13

5)       

6)      61

7)      156

Заключение

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

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

Список используемой литературы

1. Бочаров В.А., Маркин В.И. Введение в логику. – М.: ФОРУМ: ИНФРА-М, 2008.

2. Брюшинкин В.Н. Логика: Учебник для студентов гуманитарных вузов. – М., 2001.

3. Войшвилло Е.К., Дегтярев М.Г. Логика: Учеб. Для студентов высших учебных заведений. – М.: Изд- ВЛАДОС-ПРЕСС, 2001.

4. Войшвилло Е.К., Дегтярев М.Г. Логика как часть теории познания и научной методологии (фундаментальный курс). Учебное пособие для студентов философских факультетов и преподавателей логики. В 2 книгах. М.: Наука, 1994.

5. Горбатов В.В. Логика: Учебно-практическое пособие. – М.: МЭСИ, 2008

Интернет-ресурсы

1. Авторский сайт Константина Полякова http://kpolyakov.spb.ru

2. http://www.logic-books.info/taxonomy/term/21 и http://www.logic-books.info/taxonomy/term/22 – Учебная литература по логике и математической логике.

3. http://philosophy.ru/library/logic_math/ – Библиотека книг П.Д. Савкина по математической логике.

4. http://eqworld.ipmnet.ru/ru/library/mathematics/logic.htm: Библиотека книг по математической логике