Форум » Логические уравнения » Задание 23 № 15835 с сайта РешуЕГЭ » Ответить
Задание 23 № 15835 с сайта РешуЕГЭ
AlbertAbdullin: Здравствуйте. Применил метод отображения. Ответ неверный и не знаю почему.Прилагаю фотографию к моему решению. Подскажите пожалуйста, что я сделал не так? Правильный ответ 31.
Ответов - 7
Поляков: AlbertAbdullin пишет: Применил метод отображения. Здесь проще всего решать через битовые цепочки - все можно сделать устно. Первое уравнение сводится к такому:[pre2](x2->x1)(x3->x2)(x4->x3)(x5->x4)=1[/pre2]Оно имеет 6 решений структуры "все единицы, потом - все нули", так как после нуля не может стоять единица. Все X-решения: 11111, 11110, 11100, 11000, 10000, 0000. Второе уравнение сводится к такому:[pre2](y1->y2)(y2->y3)(y3->y4)(y4->y5)=1[/pre2]Оно имеет 6 решений структуры "все нули, потом - все единицы", так как после единицы не может стоять ноль. Все Y-решения: 00000, 00001, 00011, 00111, 01111, 11111. Если бы не было третьего уравнения, система имела бы 6*6=36 решений - каждое X-решение комбинируется со всеми 6-ю Y-решениями. Последнее уравнение вводит ограничение: исключает те пары X-Y, для которых x1=0 (одно X-решение) и y1 = 0 (пять Y-решений). Таким образом, исключается всего 1*5 = 5 решений. Остаются 36 - 5 = 31.
MEA: Методом отображений это задание можно решить двумя способами: 1. Изменить систему на равносильную (Свести к одному из самых распространенных вариантов. Переход на импликацию, только на вкус решающего) (x1 ∨ ¬x2) ∧(¬y1 ∨ y2)=1 (x2 ∨ ¬x3) ∧(¬y2 ∨ y3)=1 (x3 ∨ ¬x4) ∧ (¬y3 ∨ y4) =1 (x4 ∨ ¬x5) ∧ (¬y4 ∨ y5) =1 x1 ∨ y1 = 1 2. Практически то, что описано Поляковым К.Ю., но без слов только стрелочки :) Построить граф для перехода по x (удобно идти от 5 к 1, две строки 5 столбцов) Построить граф перехода по y Результаты использовать в связующем уравнении, которое тоже можно стрелочками изображать. И никаких частных случаев - это удобно - так, а это - так. Схема перехода - ключ к решению. Оформлять схему стрелками всегда проще, чем описывать словами. Советую избегать устных решений, т.к. при проверке придется не проверять, а еще раз решать. Маленькие шаги зафиксированные на бумаге всегда проще проверить.
Ефремова: Константин Юрьевич, добрый день! Можно ли решить методом отображений следующую систему: (x1 + x2+x3)->!((y1 = y2)*(y2=y3)) = 0 (x4 + x5+x6)->!((y4 = y5)*(y5=y6)) = 0 (x7 + x8+x9)->!((y7 = y8)*(y8=y9)) = 0 (x10 + x11+x12)->!((y10 = y11)*(y11=y12)) = 0 (y1->x1)+(y5->x5)+(y9->x9)+(y11->x11)=0 У меня получился ответ 81, но я в нем сильно не уверена. Большое спасибо!
MEA: Ефремова пишет: Можно ли решить методом отображений следующую систему Да можно. Метод отображения это метод выстраивания связей с помощью стрелок (ориентированного многодольного графа) Перепишем систему: x1 + x2+x3=1 x4 + x5+x6=1 x7 + x8+x9=1 x10 + x11+x12=1 x1=0 x5=0 x9=0 x11=0 (y1 = y2)*(y2=y3)=1 (y4 = y5)*(y5=y6)=1 (y10 = y11)*(y11=y12)=1 y1=1 y5=1 y9=1 y11=1 На основании этой системы можно строить многодольный граф. Решаем все про x, потом все про y. Удаляются узлы y1=0 и x1=1 и т.д. Стрелки в методе могут следовать и от пары к паре, а могут от элемента из множества {0, 1} к {0, 1}. И от {0, 1} к парам. И от каждого элемента одной доли к каждому элементу другой. И еще могут узлы удваиваться и утраиваться (например, в случаях когда возможна подстановка).
Поляков: Ефремова пишет: (x1 + x2+x3)->!((y1 = y2)*(y2=y3)) = 0 (x4 + x5+x6)->!((y4 = y5)*(y5=y6)) = 0 (x7 + x8+x9)->!((y7 = y8)*(y8=y9)) = 0 (x10 + x11+x12)->!((y10 = y11)*(y11=y12)) = 0 (y1->x1)+(y5->x5)+(y9->x9)+(y11->x11)=0 Не думаю, что тут нужен метод отображений. Из последнего уравнения сразу получаем[pre2] x1 = x5 = x9 = x11 = 0 y1 = y5 = y9 = y11 = 1[/pre2]Подставляем эти результаты в первые уравнения, попутно раскрыв импликацию по правилу A->!B=!A+!B:[pre2] !(x2 + x3) + !(1 = y2)*(y2 = y3) = 0 !(x4 + x6) + !(y4 = 1)*(1 = y6) = 0 !(x7 + x8) + !(y7 = y8)*(y8 = 1) = 0 !(x10 + x12) + !(y10 = 1)*(1 = y12) = 0[/pre2]Очевидно, что все yi = 1 (i=1, ...12), иначе второе слагаемое в каждом уравнении не может быть равно нулю. Остались суммы в каждом уравнении:[pre2] x2 + x3 = 1 x4 + x6 = 1 x7 + x8 = 1 x10 + x12 = 1[/pre2]Эти уравнения независимы, в каждом - две переменных, каждое имеет 3 решения (одна комбинация переменных дает 1 в левой части, т.е. не подходит). Например, в 1-м исключается только вариант x2 = x3 = 0. Всего решений 3*3*3*3 = 81. Вы правы.
MEA: Поляков пишет: Не думаю, что тут нужен метод отображений. Смотря что под этим понимать. Все то, что описано словами, представим в виде картинки со стрелочками. Просто схема рассуждений в которой зафиксированы все шаги. Разумеется, что для y вывод раньше понятен :). Но для "порядка" терпеливо доставила все единицы
Ефремова: Огромное спасибо за помощь!
полная версия страницы