Системы логических уравнений в задачах ЕГЭ по информатике

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа № 18»

городского округа город Салават Республики Башкортостан

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

в задачах ЕГЭ по информатике

Автор: Жилина Л.В., учитель информатики высшей категории МБОУ «СОШ № 18» г.Салаватаг

Салават,

2018г.

Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.

Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.

Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.

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

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

(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?

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

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

…

((x7y7)(x8y8))  (x7x8)  (y7y8) =1

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

Решение. Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2 можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1, y1) и определив значение пары (x2, y2) , мы найдем пару (x3, y3), которая, в свою очередь, приведет к паре (x4, y4) и так далее.

Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.

Таблица истинности:

 

Построение таблицы истинности трудоемко и неэффективно по времени, поэтому применяем второй способ – логические рассуждения. Произведение равно 1 тогда и только тогда, когда каждый множитель равен 1.

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

(x1x2) =1

(y1y2) =1

Рассмотрим первое уравнение. Следование равно 1, когда 00, 01, 11, значит (x1y1)=0 при (01), (10), то пара (x2y2) может быть любой (00), (01), (10), (11), а при (x1y1)=1, то есть (00) и (11) пара (x2y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.

Составим связи между парами (x1, y1) и (x2, y2).

Составим таблицу для вычисления количества пар на каждом этапе.

Общее количество пар 1+1+1+22=25

2) (23.160 Поляков К.Ю.) Сколько различных решений имеет система логических уравнений

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

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

...

(x6  (x7  y7))  (y6  y7) = 1

x7  y7 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,y1), (x2,y2) первого уравнения.

(x1  (x2  y2))=1

(y1  y2) = 1

Решением второго уравнения являются пары (00), (01), (11).

Найдем решения первого уравнения. Если x1=0, то x2 , y2 – любые, если x1=1, то x2 , y2 принимает значение (11).

Составим связи между парами (x1, y1) и (x2, y2).

Составим таблицу для вычисления количества пар на каждом этапе.

Учитывая решения последнего уравнения x7  y7 = 1, исключим пару (10). Находим общее число решений 1+7+0+34=42

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

(x1  x2)  (x3  x4) = 1

(x3  x4)  (x5  x6) = 1

(x5  x6)  (x7  x8) = 1

(x7  x8)  (x9  x10) = 1

x1  x3  x5  x7  x9 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x3,x4) первого уравнения.

(x1  x2)  (x3  x4) = 1

Исключим из решения пары, которые в следовании дают 0 (10), это пары (01, 00, 11) и (10).

Составим связи между парами (x1,x2), (x3,x4)

3)Составим таблицу для вычисления количества пар на каждом этапе.

Учитывая решения последнего уравнения x1  x3  x5  x7  x9 = 1,

x1 =1, x3 =1, x5 =1, x7 =1, x9 = 1.

Находим общее число решений 0+0+1+5=6.

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

(X1  X2)  (¬X1  ¬X2)  (X1  X3) = 1

(X2  X3)  (¬X2  ¬X3)  (X2  X4) = 1

...

(X7  X8)  (¬X7  ¬X8)  (X7  X9) = 1

(X8  X9)  (¬X8  ¬X9)  (X8  X10) = 0

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x2,x3) первого уравнения.

(X1  X2)  (¬X1  ¬X2)  (X1  X3) = 1

Исключим из решения пары, которые в сумме дают 0, это пары (01), (11) и (10), (00). Составим связи между парами (x1,x2), (x2,x3)

3)Составим таблицу для вычисления количества пар на каждом этапе, учитывая решения последнего уравнения (x8  x9)  (¬x8  ¬x9)  (x8  x10) = 0

x8 =0 x9=1, x10=1 и x8 =1 x9=0, x10=0.

Находим общее число решений 8+0+0+8=16.

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

Список литературы:

Е.А.Мирончик. Метод отображения // Информатика, № 10, 2013, с. 18-26

Е.А. Мирончик. Люблю ЕГЭ за В15, или Ещё раз про метод отображения // Информатика, № 7-8, 2014, с. 26-32.

К.Ю. Поляков. Преподавание, наука и жизнь.  [Электронный ресурс],-

http://kpolyakov.spb.ru/school/ege.htm