Системы логических уравнений Метод отображения Педагогический марафон Романенко О.В. г. Наро-Фоминск 24 марта 2014 Мирончик Ел. А. Мирончик Ек. А. Куда-нибудь. - презентация

1 Системы логических уравнений Метод отображения Педагогический марафон Романенко О.В. г. Наро-Фоминск 24 марта 2014 Мирончик Ел. А. Мирончик Ек. А. Куда-нибудь ты обязательно дойдешь, конечно, если не остановишься на полпути. Чеширский кот Л.Кэрролл «Алиса в стране чудес»

2 (x1x2)>(x2x3) = 1 (x2x3)>(x3x4) = 1... (x6x7)>(x7x8) = 1 ((x 1 x 2 ) (x 3 x 4 )) (¬(x 1 x 2 ) ¬(x 3 x 4 )) = 1 ((x 3 x 4 ) (x 5 x 6 )) (¬(x 3 x 4 ) ¬(x 5 x 6 )) = 1... ((x 7 x 8 ) (x 9 x 10 )) (¬(x 7 x 8 ) ¬(x 9 x 10 )) = 1 (x 1 ¬x 2 ) (¬x 1 x 2 ) (x 3 x 4 ) (¬x 3 ¬x 4 ) = 1 (x 3 ¬x 4 ) (¬x 3 x 4 ) (x 5 x 6 ) (¬x 5 ¬x 6 ) = 1... (x 7 ¬x 8 ) (¬x 7 x 8 ) (x 9 x 10 ) (¬x 9 ¬x 10 ) = 1 Метод отображения 1) 2) 3) 4) 5) В15 из демо-версии ЕГЭ-2014

3 Метод отображения Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, x3, x4, x5, x6, x7, x8 ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям? (x1x2)>(x2x3) = 1 (x2x3)>(x3x4) = 1... (x6x7)>(x7x8) = 1 В от­ве ­ те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ ры зна­че­ний пе­ре­мен­ных x1, x2, x3, x4, x5, x6, x7, x8 при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

4 Метод отображения Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено три переменных. Зная x 1 и x 2, можем найти все возможные значения x 3, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x 2 и x 3 можем найти x 4, удовлетворяющее второму уравнению. То есть, зная пару ( x 1, x 2 ) и определив значение x 3, мы найдем пару ( x 2, x 3 ), которая, в свою очередь, приведет к паре ( x 3, x 4 ) и так далее. На каждом шаге имеем множество исходных пар из набора (00, 01, 10, 11) и множество полученных пар из такого же набора (00, 01, 10, 11). Исходное множество пар отображается само в себя. Построим такое отображение. (x1x2)>(x2x3) = 1 (x2x3)>(x3x4) = 1... (x6x7)>(x7x8) = 1

5 Метод отображения Сначала построим таблицу, в которой в первых двух столбцах переберем все варианты x 1, x 2, а в третий столбец впишем только такие значения x 3, которые приведут первое уравнение к верному равенству. По таблице строим правило отображения множества пар само в себя. Задача станет напоминать задачу о количестве путей от города A до города K.

6 x1x1 x2x2 x3x (x1x2) (x2x3) = 1 (x2x3) (x3x4) = 1... (x6x7) (x7x8) = 1 Метод отображения « » должна быть истинна. Из истины может следовать только истина, а из лжи всё, что угодно

7 x1x2x1x2 x2x3x2x3 x1x1 x2x2 x3x Метод отображения

8 F (00) = F (00) + F (10) F (01) = F (10) F (10) = F (01) F (11) = F (01) + F (11) x1x2x1x2 x2x3x2x3 Метод отображения Пусть F() это функция, вычисляющая количество пар на следующем шаге

9 x1x2x1x2 x2x3x2x3 Метод отображения x3x4x3x4 x4x5x4x x5x6x5x6 x6x7x6x x7x8x7x8 x1x2x1x2 x1x2x1x2x1x2x1x2 x2x3x2x3x2x3x2x3 x3x4x3x4x3x4x3x4 x4x5x4x5x4x5x4x5 x5x6x5x6x5x6x5x6 x6x7x6x7x6x7x6x7 x7x8x7x8x7x8x7x

10 Метод отображения Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1, x 2,... x 10, ко­то­рые удо­ вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям? ((x 1 x 2 ) (x 3 x 4 )) (¬(x 1 x 2 ) ¬(x 3 x 4 )) = 1 ((x 3 x 4 ) (x 5 x 6 )) (¬(x 3 x 4 ) ¬(x 5 x 6 )) = 1... ((x 7 x 8 ) (x 9 x 10 )) (¬(x 7 x 8 ) ¬(x 9 x 10 )) = 1 В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ ры зна­че­ний пе­ре­мен­ных x 1, x 2, … x 10 при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

11 ((x 1 x 2 ) (x 3 x 4 )) (¬(x 1 x 2 ) ¬(x 3 x 4 )) = 1 ((x 3 x 4 ) (x 5 x 6 )) (¬(x 3 x 4 ) ¬(x 5 x 6 )) = 1... ((x 7 x 8 ) (x 9 x 10 )) (¬(x 7 x 8 ) ¬(x 9 x 10 )) = 1 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x « » истинна, только если оба операнда истинны x 1 x 2 x 3 x Если x 1 и x 2 равны, то x 3 и x 4 различны, и наоборот

12 x1x2x1x2 x3x4x3x4 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x

13 F (00) = F (01) + F (10) F (01) = F (00) + F (11) F (10) = F (00) + F (11) F (11) = F (01) + F (10) x1x2x1x2 x3x4x3x4 Метод отображения

14 x1x2x1x2 x1x2x1x2x1x2x1x2 x3x4x3x4x3x4x3x4 x5x6x5x6x5x6x5x6 x7x8x7x8x7x8x7x8 x 9 x x1x2x1x2 x3x4x3x x5x6x5x6 x7x8x7x8 x 9 x

15 Метод отображения Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1, x 2,... x 10, ко­то­рые удо­ вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям? (x 1 ¬x 2 ) (¬x 1 x 2 ) (x 3 x 4 ) (¬x 3 ¬x 4 ) = 1 (x 3 ¬x 4 ) (¬x 3 x 4 ) (x 5 x 6 ) (¬x 5 ¬x 6 ) = 1... (x 7 ¬x 8 ) (¬x 7 x 8 ) (x 9 x 10 ) (¬x 9 ¬x 10 ) = 1 В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ ры зна­че­ний пе­ре­мен­ных x 1, x 2, … x 10 при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

16 (x 1 ¬x 2 ) (¬x 1 x 2 ) (x 3 x 4 ) (¬x 3 ¬x 4 ) = 1 (x 3 ¬x 4 ) (¬x 3 x 4 ) (x 5 x 6 ) (¬x 5 ¬x 6 ) = 1... (x 7 ¬x 8 ) (¬x 7 x 8 ) (x 9 x 10 ) (¬x 9 ¬x 10 ) = 1 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x « » истинна, если истинно хотя бы одно высказывание

17 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x x1x2x1x2 x3x4x3x4

18 F (00) = F (00) +F (01) +F (10) +F (11) F (01) = F (01) + F (10) F (10) = F (01) + F (10) F (11) F (00) +F (01) +F (10) +F (11) Метод отображения x1x2x1x2 x3x4x3x4

19 x1x2x1x2 Метод отображения x1x2x1x2x1x2x1x2 x3x4x3x4x3x4x3x4 x5x6x5x6x5x6x5x6 x7x8x7x8x7x8x7x8 x 9 x x1x2x1x2 x3x4x3x4 x5x6x5x6 x7x8x7x8 x 9 x

20 Метод отображения Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1, x 2,... x 10, ко­то­рые удо­ вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям? В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ ры зна­че­ний пе­ре­мен­ных x 1, x 2, … x 10 при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

21 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x « » истинна, если истинно хотя бы одно высказывание 0 1 « » ложна, если ложно каждое высказывание

22 Метод отображения x1x2x1x2 x3x4x3x4 x1x1x1x1 x2x2x2x2 x3x3x3x3 x4x4x4x x2x3x2x

23 Метод отображения x1x2x1x2 x3x4x3x4 x2x3x2x x4x5x4x5 x6x7x6x7 x5x6x5x x1x2x1x2 x1x2x1x2x1x2x1x2 x2x3x2x3x2x3x2x3 x3x4x3x4x3x4x3x4 x4x5x4x5x4x5x4x5 x5x6x5x6x5x6x5x x7x8x7x8 1 x6x7x6x7x6x7x6x7 x7x8x7x8x7x8x7x8 x8x9x8x9x8x9x8x9 x 9 x

24 Метод отображения Сколько существует различных наборов значений логических переменных x1, x2, … x10, которые удовлетворяют всем перечисленным ниже условиям? ¬(x1 x2) ( (x1 ¬x3) (¬x1 x3) ) = 0 ¬(x2 x3) ( (x2 ¬x4) (¬x2 x4) ) = 0 … ¬(x8 x9) ( (x8 ¬x10) (¬x8 x10) ) = 0 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. В15 из демо-версии ЕГЭ-2014

25 Метод отображения x1x1x1x1 x2x2x2x2 x3x3x3x « » ложна, если ложно хотя бы одно высказывание « » ложна, если ложно каждое высказывание 1 ¬(x1 x2) ( (x1 ¬x3) (¬x1 x3) ) = 0 0 1

26 Метод отображения x1x2x1x2 x2x3x2x x1x1x1x1 x2x2x2x2 x3x3x3x x1x1x1x1 x2x2x2x2 x3x3x3x

27 Метод отображения x8x9x8x9 x3x4x3x4 x 9 x 10 x4x5x4x5 x6x7x6x7 x5x6x5x6 x1x2x1x2 x1x2x1x2x1x2x1x2 x2x3x2x3x2x3x2x3 x3x4x3x4x3x4x3x4 x4x5x4x5x4x5x4x5 x5x6x5x6x5x6x5x x7x8x7x8 2 x6x7x6x7x6x7x6x7 x7x8x7x8x7x8x7x8 x8x9x8x9x8x9x8x9 x 9 x x1x2x1x2 x2x3x2x