Отправлено: 16.03.19 07:48. Заголовок: Решение систем из уравнений типа (x1 ∨ x2) ∧ ((x1 ∧ x2) →x3) ∧ ¬ (x1 ∧ y1) = 1

Как решать такие системы уравнений?


Сколько существует различных наборов значений логических переменных 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 непонятно (как именно подсчитываются решения из дерева)

 Отправлено: 16.03.19 11:14. Заголовок: Мне не попадались си..

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

 Отправлено: 17.03.19 00:13. Заголовок: taiv пишет: (x1 W..

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:

 (x1 ∨ x2) ∧ (x2 ∨ x3) ∧ ... ∧ (x6 ∨ x7) = 1 
 ((x1 ∧ x2) →x3) ∧  ((x2 ∧ x3) →x4) ∧ ... ∧ ((x5 ∧ x6) →x7) = 1 
 x1 ∧ y1 = x2 ∧ y2 = ...  = x7 ∧ y7 = 0

Из первого уравнения следует, что в битовой цепочке x₁x₂x₃x₄x₅x₆x₇ не должно быть двух соседних нулей. Из второго следует, что за двумя единицами не должно быть нуля. В сумме все это значит, что сначала в X-цепочке идет чередование нулей и единиц, а потом - цепочка единиц до конца. Легко выписать все такие X-решения:

 0101010 
 0101011 
 0101111 
 0111111 
 1111111 
 1010101 
 1010111 
 1011111

Теперь подключаем третье уравнение. При xi = 1 значение yi единственно - оно должно быть равно 0, то есть, единицы в X-решении не увеличивают числа решений системы при подключении y-ов. А при xi = 0 может быть два варианта, yi = {0, 1}. Поэтому нулевые биты в X-цепочке в два раза увеличивают количество решений. Таким образом, первое X-решение, содержащее 4 нуля, дает 2⁴ = 16 решений системы, цепочки с тремя нулями - по 8 решений, цепочки с двумя нулями - по 4, с одним нулем - по 2, и цепочка из одних единиц - одно решение. Сложив все это вместе, получаем как раз 45.

 Отправлено: 17.03.19 02:28. Заголовок: Поляков пишет: не д..

Поляков пишет:

цитата:

не должно быть двух соседних нулей. Из второго следует, что за двумя единицами не должно быть нуля.

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

 Отправлено: 17.03.19 09:02. Заголовок: MEA пишет: Решение б..

MEA пишет:

цитата:

Решение битовыми цепочками это - когда дерево решений, которое можно построить в виде многодольного ориентированного графа (стрелки метода отображений) описывают словами.

Фактически да. Здесь много рассуждений, но взамен мало вычислений. Кому что нравится.

 Отправлено: 17.03.19 09:58. Заголовок: Поляков пишет: Факт..

Поляков пишет:

цитата:

Фактически да. Здесь много рассуждений, но взамен мало вычислений. Кому что нравится.

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

 Отправлено: 21.03.19 11:16. Заголовок: Метод отображений

Особенность его в том, что ему очень легко научить. Можно даже не анализировать таблицы истинности, а сходу строить стрелочные диаграммы. Базовый документ [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. Причем все стратегии МЕА суть чистая математика, где не обязательно понимать как получен глубокий результат, чтобы успешно его применить, причем зачастую в различных областях

 Отправлено: 23.03.19 17:45. Заголовок: Остается только один..

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

 Отправлено: 23.03.19 18:01. Заголовок: Логику проверяют это..

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

 Отправлено: 23.03.19 20:44. Заголовок: Демо Версии ЕГЭ Информатика 2019,2018,2017 №23

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

 Отправлено: 23.03.19 21:38. Заголовок: dbaxps пишет: позв..

dbaxps пишет:

цитата:

позволяет решить любую из 3-ех в течении 20 минут.

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

 Отправлено: 23.03.19 21:57. Заголовок: REPLY

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

 Отправлено: 23.03.19 23:15. Заголовок: Да, сложных нет в ЕГ..

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

 Отправлено: 23.03.19 20:12. Заголовок: Какие вопросы ЕГЭ имеют имеют значение для Высшей школы ?

Прямой ответ дать Вам не особенно трудно :-
Задача 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-ая классика)

 Отправлено: 24.03.19 12:07. Заголовок: Метод отображений и задача 7768

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