Форум » Логические уравнения » Решение систем из уравнений типа (x1 ∨ x2) ∧ ((x1 ∧ x2) →x3) ∧ ¬ (x1 ∧ y1) = 1 » Ответить

Решение систем из уравнений типа (x1 ∨ x2) ∧ ((x1 ∧ x2) →x3) ∧ ¬ (x1 ∧ y1) = 1

taiv: Как решать такие системы уравнений? Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям? (x1 ∨ x2) ∧ ((x1 ∧ x2) →x3) ∧ ¬ (x1 ∧ y1) = 1 (x2 ∨ x3) ∧ ((x2 ∧ x3) →x4) ∧ ¬ (x2 ∧ y2) = 1 ... (x5 ∨ x6) ∧ ((x5 ∧ x6) →x7) ∧ ¬ (x5 ∧ y5) = 1 (x6 ∨ x7) ∧ ¬(x6 ∧ y6) = 1 x7 ∧ y7 = 0 Методом отображений не получается, решение с сайта https://inf-ege.sdamgia.ru/problem?id=7768 непонятно (как именно подсчитываются решения из дерева)

Ответов - 14

MEA: Мне не попадались системы не решаемые методом отображений и эта не из того числа. Метод отображения - это просто выявление закономерности что на что влияет. Но другой вопрос как построить отображение. Два первых уравнения связаны общей парой x2, x3. Но рядом с каждой парой следует написать (лучше маленькие) 0 и 1 для Y. И стрелки вести от каждого подходящего 0 (y) и каждой подходящей 1. Таким образом просчитаете до x6, x7. По последним двум уравнениям построить отображение x6, x7 в y6, y7

Поляков: taiv пишет: (x1 ∨ x2) ∧ ((x1 ∧ x2) →x3) ∧ ¬ (x1 ∧ y1) = 1 (x2 ∨ x3) ∧ ((x2 ∧ x3) →x4) ∧ ¬ (x2 ∧ y2) = 1 ... (x5 ∨ x6) ∧ ((x5 ∧ x6) →x7) ∧ ¬ (x5 ∧ y5) = 1 (x6 ∨ x7) ∧ ¬(x6 ∧ y6) = 1 x7 ∧ y7 = 0 Вот решение через битовые цепочки. Перегруппируем уравнения, учитывая, что ¬ (x1 ∧ y1) = 1 равносильно (x1 ∧ y1) = 0:[pre2] (x1 ∨ x2) ∧ (x2 ∨ x3) ∧ ... ∧ (x6 ∨ x7) = 1 ((x1 ∧ x2) →x3) ∧ ((x2 ∧ x3) →x4) ∧ ... ∧ ((x5 ∧ x6) →x7) = 1 x1 ∧ y1 = x2 ∧ y2 = ... = x7 ∧ y7 = 0[/pre2]Из первого уравнения следует, что в битовой цепочке x1x2x3x4x5x6x7 не должно быть двух соседних нулей. Из второго следует, что за двумя единицами не должно быть нуля. В сумме все это значит, что сначала в X-цепочке идет чередование нулей и единиц, а потом - цепочка единиц до конца. Легко выписать все такие X-решения: [pre2] 0101010 0101011 0101111 0111111 1111111 1010101 1010111 1011111[/pre2]Теперь подключаем третье уравнение. При xi = 1 значение yi единственно - оно должно быть равно 0, то есть, единицы в X-решении не увеличивают числа решений системы при подключении y-ов. А при xi = 0 может быть два варианта, yi = {0, 1}. Поэтому нулевые биты в X-цепочке в два раза увеличивают количество решений. Таким образом, первое X-решение, содержащее 4 нуля, дает 24 = 16 решений системы, цепочки с тремя нулями - по 8 решений, цепочки с двумя нулями - по 4, с одним нулем - по 2, и цепочка из одних единиц - одно решение. Сложив все это вместе, получаем как раз 45.

MEA: Поляков пишет: не должно быть двух соседних нулей. Из второго следует, что за двумя единицами не должно быть нуля. Т. Е. Описание куда можно пойти, а куда нет. Решение битовыми цепочками это - когда дерево решений, которое можно построить в виде многодольного ориентированного графа (стрелки метода отображений) описывают словами.


Поляков: MEA пишет: Решение битовыми цепочками это - когда дерево решений, которое можно построить в виде многодольного ориентированного графа (стрелки метода отображений) описывают словами. Фактически да. Здесь много рассуждений, но взамен мало вычислений. Кому что нравится.

MEA: Поляков пишет: Фактически да. Здесь много рассуждений, но взамен мало вычислений. Кому что нравится. Да, о вкусах не спорят, но начиная вычислять в большинстве случаев закономерности так прозрачны, что вычислять много не надо...

dbaxps: Особенность его в том, что ему очень легко научить. Можно даже не анализировать таблицы истинности, а сходу строить стрелочные диаграммы. Базовый документ [url=http://kpolyakov.spb.ru/download/mea-2013-10.pdf] http://kpolyakov.spb.ru/download/mea-2013-10.pdf.[/url] Техника предложенная в http://kpolyakov.spb.ru/download/mea-2016-8.pdf остается до сих пор не слишком популярной. Хотя примеры ее применения к Р-45 и Р-46 наглядно демонстрируют , что работа с парами не всегда является доминирующим подходом с точки зрения прозрачности и быстроты получения результата. То же самое касается поста https://mapping-metod.blogspot.com/2019/03/blog-post.html. Причем все стратегии МЕА суть чистая математика, где не обязательно понимать как получен глубокий результат, чтобы успешно его применить, причем зачастую в различных областях

avs: Остается только один вопрос "Как успеть решить эту систему за 10 минут на ЕГЭ в стрессовой ситуации?" Вызывает большие сомнения, что эти задания проверяют уровень знания математической логики школьников. Более того, такие задания фактически не имеют практического применения при обучении в высшей школе.

MEA: Логику проверяют это точно. В стрессовом состоянии все ведут себя по разному - кто-то в ступор, кто-то активизируется на максимум. А зачем такие задания или другие на этом форуме не решается... Как и вопрос приемственности высшей и средней школы. Задание на логику более, чем сейчас(!) 18.

dbaxps: Детальное понимание Метода Отображений позволяет решить любую из 3-ех в течении 20 минут. Я повторюсь - обучение в высшей школе потребует от Вас изучения оригинальных статей и работ,если Вы, действительно, хотите получить профессиональные навыки. Зачастую ЕГЭ 23 можно решить примением битовых масок быстрее чем Методом Отображений 10-15 мин. В порядке исключения ни более ни менее.

MEA: dbaxps пишет: позволяет решить любую из 3-ех в течении 20 минут. Всё зависит от системы. Есть и за 5 минут вместе с проверкой, а есть и такие, которые часами "не берутся" независимо от способа решения. Смысл в выявлении зависимости при решении любым способом. Битовые цепочки часто бывают хороши, когда система известная и треугольная матрица или чередование 0 и 1 идёт. Но такие системы методом отображений решаются тоже быстро чаще всего это отображение двухэлементных множеств. Всё зависит от системы...

dbaxps: Елена Александровна, За последние три года я не припомню сложных 23-их на основной волне ЕГЭ. В EGE23.PDF можно нарваться на проблему, но детям такие задачи не предлагались по крайней мере в моем регионе

MEA: Да, сложных нет в ЕГЭ. Обидно, что задание в тестовой части. Арифметическая ошибка, ошибка по утомляемости перечеркивают всё. Сделал преобразование - получил плюс, определил закономерность ещё плюс, досчитал ещё плюс ответил на вопрос как изменится ответ при добавлении уравнения... Ещё +...

dbaxps: Прямой ответ дать Вам не особенно трудно :- Задача 18 (классика) 1) Отрезки 2) Побитная конъюнкция 3) Деление Корректное решение (с точки зрения формальной логики) любого из трех класссических клонов требует знание Алгебры предикатов. мех-мат либо ИВТ специализация 1-ый курс "Алгебра логики и исчисление предикатов" в обязательном порядке Задача 18 (2018 клон) 1) Методы линейной и нелинейной оптимизации (Линейное программирование в частности ) Мехмат, эконом-фак 1-ый курс. 23 - теория почитайте основные работы МЕА , вместо просмотра роликов в Сети поймете связь с "Теорией графов" (мех-мат либо ИВТ специализация 1-ый курс) http://kpolyakov.spb.ru/download/mea-2013-10.pdf (ЕГЭ 23) http://kpolyakov.spb.ru/download/mea-2016-8.pdf (ЕГЭ 23) http://kpolyakov.spb.ru/download/mea18bit.pdf (ЕГЭ 18-ая классика)

dbaxps: Техника дублирования стрелок систематически применялась МЕА при решение систем с импликацией( и не только). Чтобы не быть голословным привожу ссылку :- https://mapping-metod.blogspot.com/2019/03/23-7768.html



полная версия страницы