Решение систем логических уравнений, задание 27 ЕГЭ по информатике
презентация к уроку по информатике и икт (11 класс) по теме

Слайд 1

Решение систем логических уравнений, ЕГЭ 2014 Вишневская М.П. МАОУ «Гимназия №3» Фрунзенского района г. Саратова

Слайд 2

Демо-версия ЕГЭ 2014

Слайд 3

Решение _1в Перепишем данную систему : ¬ (х 1 ≡ х 2 ) • ¬(х 1 ≡ х 3 ) = 0 ¬ (х 2 ≡ х 3 ) • ¬(х 2 ≡ х 4 ) = 0 ………………………… ¬ (х 8 ≡ х 9 ) • ¬(х 8 ≡ х 10 ) = 0 Используем закон де Моргана: (х 1 ≡ х 2 ) + (х 1 ≡ х 3 ) = 1 ( х 2 ≡ х 3 ) + ( х 2 ≡ х 4 ) = 1 ……………………… ( х 8 ≡ х 9 ) + ( х 8 ≡ х 10 ) = 1 Рассмотрим уравнение: (х 1 ≡ х 2 ) + ( х 1 ≡ х 3 ) = 1 Найдем, когда оно = 0. Это – дизъюнкция, поэтому оно = 0 при (х 1 ≡ х 2 ) = 0 и (х 1 ≡ х 3 ) = 0, а это возможно в двух случаях: х 1 х 2 х 3 0 1 1 1 0 0

Слайд 4

Решение _1в Исключим эти наборы из решения. Останутся следующие наборы значений (битовые цепочки): х 1 х 2 х 3 0 0 0 0 0 1 1 0 если х i = х i+1 , х i+2 = 0 или 1 1 1 1 если х i = 1, х i+1 =0, то х i+2 = 1 0 1 0 если х i = 0, х i+1 =1, то х i+2 = 0 0 1 Заметим, что при присоединении каждого следующего х будет добавляться два набора: х 1 х 2 х 3 х 4 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 8 наборов, добавляем х 5 – 10 наборов, х 6 – 12 наборов, х 7 - 14 1 1 1 0 х 8 – 16, х 9 – 18, х 10 – 20 наборов . 1 1 1 1 Ответ: 20 наборов . 0 1 0 1 0 1 0

Слайд 5

Решение_2в 1. Используем методы, описанные выше, и придем к системе уравнений: (х 1 ≡ х 2 ) + (х 1 ≡ х 3 ) = 1 (х 2 ≡ х 3 ) + (х 2 ≡ х 4 ) = 1 ……………………… (х 8 ≡ х 9 ) + (х 8 ≡ х 10 ) = 1 2. Исключим, как и в 1-м варианте решения, те наборы значений, при которых уравнения = 0. Останется: х 1 х 2 х 3 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 1 3 . Построим отображение пары х 1 ,х 2 на пару х 2 ,х 3 : х 1 ,х 2 х 2 ,х 3 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 4. Т.к. все уравнения системы однородны, то можно распространить это отображение на оставшиеся пары.

Слайд 6

Решение_2в х 1 ,х 2 х 2 ,х 3 х 3 ,х 4 х 4 ,х 5 х 5 ,х 6 х 6 ,х 7 х 7 ,х 8 х 8 ,х 9 х 9 ,х 10 0 0 1 1 1 1 1 1 1 1 1 0 1 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 1+9+9+1=20 Ответ: 20 наборов

Слайд 7

Задание 1, ЕГЭ 2014 Сколько существует различных наборов логических переменных х1, х2, х3, х4, х5, х6, y1, y2, y3, y4, y5, y6 , которые удовлетворяют всем перечисленным ниже условиям? В ответе не нужно перечислять все различные наборы наборов переменных x1, x2, …x6, y1, y2, ...y6 , при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Слайд 8

Решение

Слайд 9

Решение Из этого уравнения следует, что Y i + Y i+1  0, т.е. Y i , Y i+1 ≠ 0 Рассмотрим первое уравнение : Рассмотрим второе уравнение: Из этого уравнения следует, что ¬ Y i + ¬ Y i+1 + Y i+ 2  0, т.е. Y i , Y i+1 ≠ 1 и Y i+ 2 ≠ 0

Слайд 10

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

Слайд 11

Решение Запрещены пары x i = 0 , y i = 1 (I = 1…6). Т. о. если y i = 1 , то x i может принимать одно значение – 1 , если y i = 0, то x i = 1 или x i = 0. Как проще записать? Перепишем полученное дерево в виде битовых цепочек: y 1 y 2 y 3 y 4 y 5 y 6 1 0 1 0 1 0 эта цепочка даст 2 3 наборов 1 0 1 0 1 1 эта цепочка даст 2 2 наборов 1 0 1 1 1 1 эта цепочка даст 2 1 наборов 1 1 1 1 1 1 эта цепочка даст 2 0 наборов 0 1 0 1 0 1 эта цепочка даст 2 3 наборов 0 1 0 1 1 1 эта цепочка даст 2 2 наборов 0 1 1 1 1 1 эта цепочка даст 2 1 наборов Ответ: 29 наборов логических переменных Рассмотрим первое уравнение :

Слайд 12

Задание 2, ЕГЭ 2014 Сколько существует различных наборов логических переменных х 1 , х 2 , х 3 , х 4 , х 5 , х 6 , x 7 , y 1 , y 2 , y 3 , y 4 , y 5 , y 6 , y 7 , которые удовлетворяют всем перечисленным ниже условиям? В ответе не нужно перечислять все различные наборы наборов переменных x 1 , x 2 , …x 7 , y 1 , y 2 , ...y 7 , при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Слайд 13

Решение Перепишем систему в равносильном виде: Рассмотрим систему уравнений без y в виде: ( x 1 + x 2 ) ( x 2 + x 3 ) ( x 3 + x 4 ) ( x 4 + x 5 ) ( x 5 + x 6 ) ( x 6 + x 7 ) =1 (¬x 1 + ¬x 1 + x 3 )(¬x 2 + ¬x 3 + x 4 )(¬x 3 + ¬x 4 + x 5 ) (¬x 4 + ¬x 5 + x 6 ) (¬ x 5 + ¬ x 6 + x 7 )= 1 Очевидно, что x i + x i+1  0, т.е. x i , x i+1 ≠ 0 и ¬ x i + ¬ x i+1 + x i+ 2  0, т.е. x i , x i+1 ≠ 1 и x i+ 2 ≠ 0

Слайд 14

Решение Следуя логике решения предыдущего задания, получаем набор битовых цепочек: x 1 x 2 x 3 x 4 x 5 x 6 x 7 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 Рассмотрим последние 7 уравнений: 1…7

Слайд 15

Решение Заметим, что из последних 7 уравнений следует, что если x i = 1 , то y i может принимать два значения: 0 и 1. Если x i = 0 , y i = 1. x 1 x 2 x 3 x 4 x 5 x 6 x 7 1 0 1 0 1 0 1 эта цепочка даст 2 4 набора значений 1 0 1 0 1 1 1 эта цепочка даст 2 5 набора значений 1 0 1 1 1 1 1 эта цепочка даст 2 6 набора значений 1 1 1 1 1 1 1 эта цепочка даст 2 7 набора значений 0 1 0 1 0 1 0 эта цепочка даст 2 3 набора значений 0 1 0 1 0 1 1 эта цепочка даст 2 4 набора значений 0 1 0 1 1 1 1 эта цепочка даст 2 5 набора значений 0 1 1 1 1 1 1 эта цепочка даст 2 6 набора значений Ответ : 360 наборов логических переменных

Слайд 16

Задание 3, ЕГЭ 2015 Сколько существует различных наборов логических переменных х 1 , х 2 , х 3 , х 4 , х 5 , х 6 , y 1 , y 2 , y 3 , y 4 , y 5 , y 6 , которые удовлетворяют всем перечисленным ниже условиям? В ответе не нужно перечислять все различные наборы наборов переменных x 1 , x 2 , … x 6 , y 1 , y 2 , ... y 6 , при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. ( x 1  y 1 )  ((  x 1   y 1 )  (  x 2   y 2 )) = 1 (x 2  y 2 )  ((  x 2   y 2 )  (  x 3   y 3 )) = 1 (x 3  y 3 )  ((  x 3   y 3 )  (  x 4   y 4 )) = 1 (x 4  y 4 )  ((  x 4   y 4 )  (  x 5   y 5 )) = 1 ( x 5  y 5 )  ((  x 5   y 5 )  (  x 6   y 6 )) = 1 x 6  y 6 = 1

Слайд 17

Решение (метод отображений) Перепишем систему: ( x 1 + y 1 ) ● ((  x 1 +  y 1 )  (  x 2 +  y 2 )) = 1 (x 2 + y 2 ) ● ((  x 2 +  y 2 )  (  x 3 +  y 3 )) = 1 (x 3 + y 3 ) ● ((  x 3 +  y 3 )  (  x 4 +  y 4 )) = 1 (x 4 + y 4 ) ● ((  x 4 +  y 4 )  (  x 5 +  y 5 )) = 1 ( x 5 + y 5 ) ● ((  x 5 +  y 5 )  (  x 6 +  y 6 )) = 1 x 6 + y 6 = 1 Рассмотрим первое уравнение системы: ( x 1 + y 1 ) ● ((  x 1 +  y 1 )  (  x 2 +  y 2 )) = 1 Построим для него таблицу истинности, заметив, что x i = y i ≠ 0 х 1 , y 1 х 2 , y 2 значение 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1

Слайд 18

Решение (метод отображений) х 1 , y 1 х 2 , y 2 0 1 0 1 1 0 1 0 1 1 1 1 х 1 , y 1 х 2 , y 2 значение 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 Учитывая, что все уравнения системы однородны, можно распространить это отображение на оставшиеся пары.

Слайд 19

Решение (метод отображений) х 1 , y 1 х 2 , y 2 х 3 , y 3 х 4 , y 4 х 5 , y 5 х 6 , y 6 0 1 1 3 7 15 31 63 1 0 1 3 7 15 31 63 1 1 1 1 1 1 1 1 3 Ответ: 127 наборов значений Осталось проанализировать последнее уравнение : x 6 + y 6 = 1 Очевидно, что ни один из полученных ответов не обнуляет это уравнение.

Слайд 20

Источники информации К.Ю. Поляков, М.А. Ройтберг . Системы логических уравнений: решение с помощью битовых цепочек // Информатика, № 12, 2014, с. 4-12. http://kpolyakov.narod.ru/school/ege.htm