Заранеe благодарен.
Необычная система уравнений
Необычная система уравнений
Необходимо решить систему уравнений. При условии, что неизвестные могут принимать значения или 0 или 1. Пытался применить целочисленное программирование – не получается. B алгебре Жигалкина не нашел похожих задач. Метод перебора не подходит (по условию). После почти месяца поисков пришел в тупик. Подскажите, пожалуйста, где хотя бы можно посмотреть, что-то подобное. И, вообще, кто-то стыкался c такой системой?
![$$a*f*d*b*c \oplus b*a*c \oplus b \oplus b*c \oplus a*c \oplus f*d*c \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b*a*d*c \oplus b*d*c + a*f*d*b \oplus a*f*d*b*c + b*a*c \oplus a*f*d*b*c =1 \\1 \oplus a*f*d*b*c \oplus b*a*c \oplus b \oplus b*c \oplus a*c \oplus f*d*c \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b*a*d*c \oplus b*d*c =0 \\1 \oplus f*d \oplus c \oplus b \oplus a*c \oplus a*f*d \oplus f*d*c \oplus b*a*d*c \oplus b*d*c \oplus f*b*d*c \oplus b*a*c=0 \\ f*d*c \oplus b*c \oplus b*d*c \oplus c \oplus b \oplus a*f*d*b*c \oplus a*c*d \oplus b*a*d*c \oplus a*c =0 \\ a*c \oplus f*d*c \oplus b*d*c \oplus a*c*f*d \oplus a*f*d*b*c \oplus a*f*d \oplus f*b*d \oplus b*c \oplus b*a*c \oplus d \oplus a*c*d=0 \\ 1 \oplus b*d \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b \oplus b*a*c \oplus f*b*d*c \oplus a*c*f*d \oplus b*c=1 \\ a*c \oplus b*c \oplus f*b*c \oplus f*b \oplus b*a*c \oplus b*a \oplus f*d*c \oplus b*d \oplus a*c*f*d \oplus a*f*d \oplus a*f*d*b \oplus d \oplus f*d \oplus b*d*c \oplus f*b*d*c \oplus f*b*d =1 \\ c \oplus a \oplus c*d \oplus b \oplus a*c \oplus f \oplus f*d \oplus a*f*d \oplus f*c \oplus f*d*c=0$$ $$a*f*d*b*c \oplus b*a*c \oplus b \oplus b*c \oplus a*c \oplus f*d*c \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b*a*d*c \oplus b*d*c + a*f*d*b \oplus a*f*d*b*c + b*a*c \oplus a*f*d*b*c =1 \\1 \oplus a*f*d*b*c \oplus b*a*c \oplus b \oplus b*c \oplus a*c \oplus f*d*c \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b*a*d*c \oplus b*d*c =0 \\1 \oplus f*d \oplus c \oplus b \oplus a*c \oplus a*f*d \oplus f*d*c \oplus b*a*d*c \oplus b*d*c \oplus f*b*d*c \oplus b*a*c=0 \\ f*d*c \oplus b*c \oplus b*d*c \oplus c \oplus b \oplus a*f*d*b*c \oplus a*c*d \oplus b*a*d*c \oplus a*c =0 \\ a*c \oplus f*d*c \oplus b*d*c \oplus a*c*f*d \oplus a*f*d*b*c \oplus a*f*d \oplus f*b*d \oplus b*c \oplus b*a*c \oplus d \oplus a*c*d=0 \\ 1 \oplus b*d \oplus f*b*d \oplus a*f*d \oplus a*f*d*b \oplus b \oplus b*a*c \oplus f*b*d*c \oplus a*c*f*d \oplus b*c=1 \\ a*c \oplus b*c \oplus f*b*c \oplus f*b \oplus b*a*c \oplus b*a \oplus f*d*c \oplus b*d \oplus a*c*f*d \oplus a*f*d \oplus a*f*d*b \oplus d \oplus f*d \oplus b*d*c \oplus f*b*d*c \oplus f*b*d =1 \\ c \oplus a \oplus c*d \oplus b \oplus a*c \oplus f \oplus f*d \oplus a*f*d \oplus f*c \oplus f*d*c=0$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24a%2Af%2Ad%2Ab%2Ac%20%5Coplus%20b%2Aa%2Ac%20%5Coplus%20b%20%5Coplus%20b%2Ac%20%5Coplus%20a%2Ac%20%5Coplus%20f%2Ad%2Ac%20%5Coplus%20f%2Ab%2Ad%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%2Ab%20%5Coplus%20b%2Aa%2Ad%2Ac%20%5Coplus%20b%2Ad%2Ac%20%2B%20a%2Af%2Ad%2Ab%20%5Coplus%20a%2Af%2Ad%2Ab%2Ac%20%2B%20b%2Aa%2Ac%20%5Coplus%20a%2Af%2Ad%2Ab%2Ac%20%3D1%20%5C%5C1%20%5Coplus%20a%2Af%2Ad%2Ab%2Ac%20%5Coplus%20b%2Aa%2Ac%20%5Coplus%20b%20%5Coplus%20b%2Ac%20%5Coplus%20a%2Ac%20%5Coplus%20f%2Ad%2Ac%20%5Coplus%20f%2Ab%2Ad%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%2Ab%20%5Coplus%20b%2Aa%2Ad%2Ac%20%5Coplus%20b%2Ad%2Ac%20%3D0%20%5C%5C1%20%5Coplus%20f%2Ad%20%5Coplus%20c%20%5Coplus%20b%20%5Coplus%20a%2Ac%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20f%2Ad%2Ac%20%5Coplus%20b%2Aa%2Ad%2Ac%20%5Coplus%20b%2Ad%2Ac%20%5Coplus%20f%2Ab%2Ad%2Ac%20%5Coplus%20b%2Aa%2Ac%3D0%20%5C%5C%20f%2Ad%2Ac%20%5Coplus%20b%2Ac%20%5Coplus%20b%2Ad%2Ac%20%5Coplus%20c%20%5Coplus%20b%20%5Coplus%20a%2Af%2Ad%2Ab%2Ac%20%5Coplus%20a%2Ac%2Ad%20%5Coplus%20b%2Aa%2Ad%2Ac%20%5Coplus%20a%2Ac%20%3D0%20%5C%5C%20a%2Ac%20%5Coplus%20f%2Ad%2Ac%20%5Coplus%20b%2Ad%2Ac%20%5Coplus%20a%2Ac%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%2Ab%2Ac%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20f%2Ab%2Ad%20%5Coplus%20b%2Ac%20%5Coplus%20b%2Aa%2Ac%20%5Coplus%20d%20%5Coplus%20a%2Ac%2Ad%3D0%20%5C%5C%201%20%5Coplus%20b%2Ad%20%5Coplus%20f%2Ab%2Ad%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%2Ab%20%5Coplus%20b%20%5Coplus%20b%2Aa%2Ac%20%5Coplus%20f%2Ab%2Ad%2Ac%20%5Coplus%20a%2Ac%2Af%2Ad%20%5Coplus%20b%2Ac%3D1%20%5C%5C%20a%2Ac%20%5Coplus%20b%2Ac%20%5Coplus%20f%2Ab%2Ac%20%5Coplus%20f%2Ab%20%5Coplus%20b%2Aa%2Ac%20%5Coplus%20b%2Aa%20%5Coplus%20f%2Ad%2Ac%20%5Coplus%20b%2Ad%20%5Coplus%20a%2Ac%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20a%2Af%2Ad%2Ab%20%5Coplus%20d%20%5Coplus%20f%2Ad%20%5Coplus%20b%2Ad%2Ac%20%5Coplus%20f%2Ab%2Ad%2Ac%20%5Coplus%20f%2Ab%2Ad%20%3D1%20%5C%5C%20c%20%5Coplus%20a%20%5Coplus%20c%2Ad%20%5Coplus%20b%20%5Coplus%20a%2Ac%20%5Coplus%20f%20%5Coplus%20f%2Ad%20%5Coplus%20a%2Af%2Ad%20%5Coplus%20f%2Ac%20%5Coplus%20f%2Ad%2Ac%3D0%24%24)
Заранеe благодарен.
Заранеe благодарен.
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Например, можно применить метод исключения неизвестных, в какой-то степени аналог исключения неизвестных в линейных системах.
Последний раз редактировалось AV_77 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Ujhart писал(а):Source of the post
Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.
Нет. Возьмите учебник Куроша (по-моему "Введение в алгебру" или что-то похожеe) и почитайте там про результанты.
Последний раз редактировалось AV_77 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Задача NP-полная. Называется "Выполнимость" или как вариант "3-Выполнимость". Так что только перебор.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Я считаю, что полный перебор, это последнеe дело, что может быть в таких случаях. Какой то известный метод решения уже eсть, так как я применил для решения этой системы функцию msolve({..},2) в Maple9,5 и это дало мне правильный ответ . Теперь постараюсь найти описании этой функции . Может eсли кто знает где посмотреть, то киньте cсылку.
Метод исключения не подойдет, так как при исключение eсть операция деления, a она не подходит так как неизвестные и их сумма по модулю 2 могут принимать значения 0.
Метод исключения не подойдет, так как при исключение eсть операция деления, a она не подходит так как неизвестные и их сумма по модулю 2 могут принимать значения 0.
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Перелапатил инет, но ничего подобного не нашел. Oстается надежда на коллективное сознание и на помощь зала.
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Оптимальным был бы метод перебора, почему в условии он исключен?
Последний раз редактировалось Pyotr 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
Метод перебора исключен потому, что необходимо не только решить данную систему, a и найти алгоритм, который бы давал возможность решать подобные системы уравнений. Это хорошо, что здесь 5 неизвестных, a eсли их будет 250 или 500? Так что метод перебора сразу отпадает.
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Необычная система уравнений
AV_77 писал(а):Source of the postUjhart писал(а):Source of the post
Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.
Нет. Возьмите учебник Куроша (по-моему "Введение в алгебру" или что-то похожеe) и почитайте там про результанты.
Как Вы видете приминения теории результантов к данной системе?
Последний раз редактировалось Ujhart 30 ноя 2019, 10:43, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость