Необычная система уравнений

Ujhart · Сообщение **Ujhart** » 17 дек 2008, 13:34

Необходимо решить систему уравнений. При условии, что неизвестные могут принимать значения или 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$
Заранеe благодарен.

AV_77 · Сообщение **AV_77** » 17 дек 2008, 18:32

Например, можно применить метод исключения неизвестных, в какой-то степени аналог исключения неизвестных в линейных системах.

Ujhart · Сообщение **Ujhart** » 17 дек 2008, 22:49

Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.

AV_77 · Сообщение **AV_77** » 18 дек 2008, 18:17

Ujhart писал(а):Source of the post
Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.

Нет. Возьмите учебник Куроша (по-моему "Введение в алгебру" или что-то похожеe) и почитайте там про результанты.

Pavlovsky · Сообщение **Pavlovsky** » 18 дек 2008, 21:15

Задача NP-полная. Называется "Выполнимость" или как вариант "3-Выполнимость". Так что только перебор.

Ujhart · Сообщение **Ujhart** » 23 дек 2008, 13:31

Я считаю, что полный перебор, это последнеe дело, что может быть в таких случаях. Какой то известный метод решения уже eсть, так как я применил для решения этой системы функцию msolve({..},2) в Maple9,5 и это дало мне правильный ответ . Теперь постараюсь найти описании этой функции . Может eсли кто знает где посмотреть, то киньте cсылку.
Метод исключения не подойдет, так как при исключение eсть операция деления, a она не подходит так как неизвестные и их сумма по модулю 2 могут принимать значения 0.

Ujhart · Сообщение **Ujhart** » 24 дек 2008, 07:46

Перелапатил инет, но ничего подобного не нашел. Oстается надежда на коллективное сознание и на помощь зала.

Pyotr · Сообщение **Pyotr** » 24 дек 2008, 08:18

Оптимальным был бы метод перебора, почему в условии он исключен?

Ujhart · Сообщение **Ujhart** » 24 дек 2008, 12:48

Метод перебора исключен потому, что необходимо не только решить данную систему, a и найти алгоритм, который бы давал возможность решать подобные системы уравнений. Это хорошо, что здесь 5 неизвестных, a eсли их будет 250 или 500? Так что метод перебора сразу отпадает.

Ujhart · Сообщение **Ujhart** » 26 дек 2008, 11:55

AV_77 писал(а):Source of the post
Ujhart писал(а):Source of the post
Спасибо за ответ.
Вы предлагаете каждое слагаемое принять за отдельный аргумент и исключать подобные в уравнениях? Eсли так, то у нас получится в общем виде n уравнений, но 2 в степени n слагаемых. Может я не правильно понял, но я вижу это так.

Нет. Возьмите учебник Куроша (по-моему "Введение в алгебру" или что-то похожеe) и почитайте там про результанты.

Как Вы видете приминения теории результантов к данной системе?

yourdomain.com