Задача по дискретке (формулы с побитовыми операциями)

[technocrator]

Подскажите, пожалуйста, где можно найти теорию по алгоритму решения задачи

Цитата:

Даны $n$ неотрицательных целых чисел. Проверить, можно ли составить формулу, используя побитовые И («&»), ИЛИ («|»), НЕ («˜»), круглые скобки («(», «)») и данные числа, чтобы ее результатом являлось число $s$

Явно не прямой перебор требуется, тут или что-то вроде динамического программирования, или использование свойств битовых масок, скорее всего, должно быть, но конкретной инфы не нахожу :(

[zykov]

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

-- 24.03.2023, 23:54 --

Думаю, если переобозначить по-другому - так что биты в данной позиции из разных чисел образуют слово и есть набор таких слов по количеству бит в целом числе, то можно считать, что это задаёт логическую функцию.
По битам из каждого слова функция должна генерировать желаемый бит-результат.

Тогда всё просто. Если есть два одинаковых слова для которых результат будет разным, то такой функции нет.
Иначе функция есть, т.к. набор И, ИЛИ, НЕ является полным.