Системы логических уравнений в задачах ЕГЭ по информатике
Муниципальное бюджетное общеобразовательное учреждение
«Средняя общеобразовательная школа № 18»
городского округа город Салават Республики Башкортостан
Системы логических уравнений
в задачах ЕГЭ по информатике
Автор: Жилина Л.В., учитель информатики высшей категории МБОУ «СОШ № 18» г.Салаватаг
Салават,
2018г.
Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.
|
Раздел курса |
Средний процент выполнения по группам заданий |
|
Кодирование информации и измерение ее количества |
54,7 |
|
Информационное моделирование |
75,3 |
|
Системы счисления |
64,7 |
|
Основы алгебры логики |
43,2 |
|
Алгоритмизация и программирование |
46,4 |
|
Основы информационно- коммуникационных технологий |
68,2 |
Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.
|
№ задания |
Проверяемые элементы содержания |
Уровень сложности задания |
|
2 |
Умение строить таблицы истинности и логические схемы |
Б |
|
17 |
Умение осуществлять поиск информации в сети Интернет |
П |
|
18 |
Знание основных понятий и законов математической логики |
П |
|
23 |
Умение строить и преобразовывать логические выражения |
В |
Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.
Успешность решения системы логических уравнений зависит от знания законов логики и от четкого применения методов решения системы.
Рассмотрим решение системы логических уравнений методом отображения.
(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?
((x1y1)(x2y2)) (x1x2) (y1y2) =1
((x2y2)(x3y3)) (x2x3) (y2y3) =1
…
((x7y7)(x8y8)) (x7x8) (y7y8) =1
где x1,x2,…,x8, у1,у2,…,у8 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение. Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2 можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1, y1) и определив значение пары (x2, y2) , мы найдем пару (x3, y3), которая, в свою очередь, приведет к паре (x4, y4) и так далее.
Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.
Таблица истинности:
|
x1 |
y1 |
x2 |
y2 |
x1y1 |
x2y2 |
(x1y1)(x2y2) |
(x1x2) |
(y1y2) |
(x1x2) (y1y2) |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Построение таблицы истинности трудоемко и неэффективно по времени, поэтому применяем второй способ – логические рассуждения. Произведение равно 1 тогда и только тогда, когда каждый множитель равен 1.
(x1y1)(x2y2))=1
(x1x2) =1
(y1y2) =1
Рассмотрим первое уравнение. Следование равно 1, когда 00, 01, 11, значит (x1y1)=0 при (01), (10), то пара (x2y2) может быть любой (00), (01), (10), (11), а при (x1y1)=1, то есть (00) и (11) пара (x2y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.
Составим связи между парами (x1, y1) и (x2, y2).
|
(x1, y1) |
(x2, y2) |
|
00 |
|
|
|
|
|
|
10 |
|
11 |
|
00
01
01
10
11Составим таблицу для вычисления количества пар на каждом этапе.
|
x1,y1 |
x2,y2 |
x3,y3 |
x4,y4 |
x5,y5 |
x6,y6 |
x7,y7 |
x8,y8 |
|
|
00 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
01 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
11 |
1 |
4 |
7 |
10 |
13 |
16 |
19 |
22 |
Общее количество пар 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).
|
(x1, y1) |
(x2, y2) |
|
|
|
|
|
|
|
|
10 |
|
11 |
|
00
01
01
Составим таблицу для вычисления количества пар на каждом этапе.
|
x1,y1 |
x2,y2 |
x3,y3 |
x4,y4 |
x5,y5 |
x6,y6 |
x7,y7 |
|
|
00 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
01 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
11 |
1 |
4 |
8 |
13 |
19 |
26 |
34 |
Учитывая решения последнего уравнения 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 (10), это пары (01, 00, 11) и (10).
Составим связи между парами (x1,x2), (x3,x4)
|
(x1,x2) |
(x3,x4) |
|
|
|
|
|
|
|
|
10 |
|
|
|
11
3)Составим таблицу для вычисления количества пар на каждом этапе.
Учитывая решения последнего уравнения x1 x3 x5 x7 x9 = 1,
x1 =1, x3 =1, x5 =1, x7 =1, x9 = 1.
|
(x1,x2) |
(x3,x4) |
(x5,x6) |
(x7,x8) |
(x9,x10) |
|
|
00 |
0 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
0 |
|
10 |
1 |
1 |
1 |
1 |
1 |
|
11 |
1 |
2 |
3 |
4 |
5 |
Находим общее число решений 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)
|
(x1,x2) |
(x2,x3) |
|
|
|
|
01 |
|
|
|
10 |
|
11 |
|
01
10
3)Составим таблицу для вычисления количества пар на каждом этапе, учитывая решения последнего уравнения (x8 x9) (¬x8 ¬x9) (x8 x10) = 0
x8 =0 x9=1, x10=1 и x8 =1 x9=0, x10=0.
|
(x1,x2) |
(x2,x3) |
(x3,x4) |
(x4,x5) |
(x5,x6) |
(x6,x7) |
(x7,x8) |
(x8,x9) |
(x9,x10) |
|
|
00 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
8 |
|
01 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
0 |
|
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
0 |
|
11 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
8 |
1
8Находим общее число решений 8+0+0+8=16.
Успешность решения зависит от уверенного знания метода отображения, чего можно добиться многократным решением систем уравнений. И да осилит дорогу идущий.
Список литературы:
Е.А.Мирончик. Метод отображения // Информатика, № 10, 2013, с. 18-26
Е.А. Мирончик. Люблю ЕГЭ за В15, или Ещё раз про метод отображения // Информатика, № 7-8, 2014, с. 26-32.
К.Ю. Поляков. Преподавание, наука и жизнь. [Электронный ресурс],-
http://kpolyakov.spb.ru/school/ege.htm
