Comments 14
Может иметь смысл расширение матрицы с 2D на 3D. Или до размерности соответствующей количеству переменных.
0
Давно уже ищу способы решения такой задачки, может кто с хабра подскажет?
Есть кейс: пару сотен булевых функций от примерно 5 сотен переменных. Задача: для заданного вектора результатов найти значения переменных или хотя бы упростить исходную систему для возможности полного перебора. Этакие булевые СЛАУ.
Есть кейс: пару сотен булевых функций от примерно 5 сотен переменных. Задача: для заданного вектора результатов найти значения переменных или хотя бы упростить исходную систему для возможности полного перебора. Этакие булевые СЛАУ.
0
Это же типичная задача SAT, разве нет? Перегоняете все свои функции в КНФ форму, добавляете вспомогательные переменные, соответствующие выходам функций, задаете им соответствующие значения, затем запускаете SAT солвер, он вам и найдет какое-то решение, из которого можно будет достать входные значения.
0
Как сказал CaptainTrunky, Ваша задача легко укладывается в SAT. Но решение SAT вам позволит найти значения переменных. Что касается минимизации, то тут или аналитически или генерируя все возможные решения SAT задачи (ALL-SAT). Размер результата очень сильно зависит от КНФ, вплоть до невообразимых величин, тут важна информация о самой КНФ: встречаемость литералов в конъюнктах, отношение колиества переменных к количеству конъюнктов и т.п. Касательно ALL-SAT, могу дать пару соображений.
0
Спасибо, теперь хоть буду знать в какую сторону копать.
До этого начал уже придумывать способы ухода в базис Жегалкина и дальше аналогично методу Гаусса в СЛАУ решать их (хотя проверял только на 3 переменных и трех уравнениях, так что на возможность такого решения для 100+ переменных не ручаюсь). Собственно размеры уравнений в базисе пугает (в пределе 2^n коньюнкций по (1;n) переменных), хоть и очень разряженная матрица получается, а ощущение неправильности способа решения не покидает и почти уже бросил затею, т.к. играюсь для себя.
До этого начал уже придумывать способы ухода в базис Жегалкина и дальше аналогично методу Гаусса в СЛАУ решать их (хотя проверял только на 3 переменных и трех уравнениях, так что на возможность такого решения для 100+ переменных не ручаюсь). Собственно размеры уравнений в базисе пугает (в пределе 2^n коньюнкций по (1;n) переменных), хоть и очень разряженная матрица получается, а ощущение неправильности способа решения не покидает и почти уже бросил затею, т.к. играюсь для себя.
0
Можно еще попробовать навести оптимизацию при помощи булевых счетчиков. Задаем дополнительные ограничения на кол-во определенных литералов, после чего инкрементально увеличиваем счетчик от нуля до тех пор, пока не придем к SAT решению. Счетчики тоже могут получиться невообразимо большими, но что поделать. Как и tvi, могу помочь более детально.
0
Не понятен Ваш способ. Я правильно понимаю что Вы задаете ограничение на количество конъюнктов, в которых будет распространяться приписывание литерала? Но тогда где гарантия, что мы найдем все решения (ведь без них мы не получим минимизации)?
0
На практике в FPGA все равно булевы функции записываются в LUT (Look-Up Table), это такая ПЗУ-шка на N входов и в ней хранится битовая таблица 2^N.
Минимизировать надо, если из К155ЛА3 собирать логику :)
Минимизировать надо, если из К155ЛА3 собирать логику :)
0
Sign up to leave a comment.
Еще раз о минимизации булевых функций