Булевы функции не обращаются в единицу одновременно. Когда?

[EUgeneUS]

$v$ - вектор булевых переменных длиной $n$

$f_1(v), f_2(v)$ - две булевых функции, заданных на векторах длины $n$.

Задача: убедиться, что $f_1(v), f_2(v)$ не обращаются в единицу одновременно. То есть, что не существует такого $v_0$, что $f_1(v_0) = f_2(v_0)=1$

В качестве собственных попыток решения.

1. Функцию задаем в ДНФ.
2. От ДНФ переходим к СДНФ. Известно, что СДНФ единственна для заданной функции, с точностью до перестановки "множителей" в конъюнкциях, и перестановки "слагаемых" в дизъюнкциях.
3. Проверяем, что в этих функциях нет одинаковых конъюнкций.

Очевидно, это необходимое условие.
Но будет ли оно достаточным? Что сильно сомнительно.
А если не будет, то как проверить? Бруте-форс по всем значениям переменных не предлагать.

[Geen]

EUgeneUS в сообщении #1703946 писал(а):

нет одинаковых конъюнкций

Могут быть "подмножества"
Упустил, что сДНФ...

[Mihr]

EUgeneUS в сообщении #1703946 писал(а):

Но будет ли оно достаточным? Что сильно сомнительно.

Как-то я не очень понял формулировку вопроса.
СДНФ ведь как раз и состоит из всех таких конституент единицы, на которых данная функция равна 1 (и только из них). Если таковых конституент нет, значит, рассматриваемые функции одновременно не обращаются в единицу. В чём здесь могут быть сомнения?

А построить произведение (конъюнкцию) данных функций и убедиться, что это произведение тождественно равно нулю, - не будет ли проще?

[mihaild]

Geen в сообщении #1703947 писал(а):

Могут быть "подмножества"

В СДНФ не могут.

EUgeneUS в сообщении #1703946 писал(а):

Бруте-форс по всем значениям переменных не предлагать

Переход к СДНФ это уже примерно брутфорс.
Если хочется побыстрее, то важно, как функции заданы изначально (переходы между представлениями могут быть долгими). Если в ДНФ - то нужно проверить, что любая пара (терм из $f$, терм из $g$) содержит хотя бы один несовместный литерал.
Это дает время $O(nmk)$, где $m$ и $k$ - количество термов в $f$ и $g$. Почти наверняка должно быть возможно за $O(n \cdot (m + k))$ какими-то правильным поиском паттерна в строке, но сходу не могу сообразить.

[EUgeneUS]

mihaild в сообщении #1703949 писал(а):

СДНФ ведь как раз и состоит из всех таких конституент единицы, на которых данная функция равна 1 (и только из них). Если таковых конституент нет, значит, рассматриваемые функции одновременно не обращаются в единицу. В чём здесь могут быть сомнения?

Да, спасибо. Видимо, зря сомневался.

mihaild в сообщении #1703949 писал(а):

ереход к СДНФ это уже примерно брутфорс.

Спасибо.
Возможно, немного поможет, что единиц будет порядка $n/2$ или меньше.

mihaild в сообщении #1703949 писал(а):

как функции заданы изначально (переходы между представлениями могут быть долгими).

Считаем, что задана в ДНФ.

[mihaild]

EUgeneUS в сообщении #1703951 писал(а):

Возможно, немного поможет, что единиц будет порядка $n/2$ или меньше

Единиц - это в смысле аргументов, на которых функция принимает значение $1$? (оно же число термов в СДНФ)

[EUgeneUS]

mihaild в сообщении #1703952 писал(а):

Единиц - это в смысле аргументов, на которых функция принимает значение $1$? (оно же число термов в СДНФ)

да.

[Geen]

EUgeneUS в сообщении #1703957 писал(а):

mihaild в сообщении #1703952 писал(а):

Единиц - это в смысле аргументов, на которых функция принимает значение $1$? (оно же число термов в СДНФ)

да.

То есть число аргументов $2^n$, а из них только порядка $ n$ дают 1? А каков порядок $n$?

[mihaild]

EUgeneUS в сообщении #1703951 писал(а):

Возможно, немного поможет, что единиц будет порядка $n/2$ или меньше.

Тогда СДНФ имеет $O(n)$ термов, и строится за $O(n^2)$. Ну а дальше пересечение двух СДНФ находится за их размер (хотя бы хеш-таблицей), итого сложность $O(n^2)$. Быстрее получится, только если у нас термов совсем мало (иначе это просто размер входа).

[realeugene]

mihaild в сообщении #1703949 писал(а):

переходы между представлениями могут быть долгими

Угу, в общем случае задача NP-полная.

[mihaild]

В более общем случае.
По функции $f$ с $m$ термами построим две матрицы $m \times n$: $f$ и $\bar f$. Строки - термы, столбцы - переменные. $f^0_{ij} = 1$ если $x_j$ входит в $i$-й терм, $\bar f_{ij} = 1$ если $\overline{x_j}$ входит в $i$-й терм, остальные элементы матриц равны нулю.
$i$-й терм $f$ и $k$-й терм $f$ несовместны если для некоторого $j$, $x_j$ входит в один из них и $\overline{x_j}$ во второй. Это означает, что $(f \cdot \bar{g}^T + \bar{f} \cdot g^T)_{i, k} \neq 0$. Т.е. условие выполнено, если в матрице $f \cdot \bar{g}^T + \bar{f} \cdot g^T$ нет нулевых элементов.
Для вычисления этой матрицы, нам нужно перемножить две пары матриц $m \times n$ и $n \times k$. Что можно сделать за $O(\max(m, n) \cdot \max(n, k) \cdot n^{\omega - 2 + o(1)})$. Может быть для булевых матриц есть что-то более эффективное, но сходу не нашел.

[EUgeneUS]

mihaild в сообщении #1703981 писал(а):

В более общем случае.

Спасибо!

Я же правильно понимаю, что этот алгоритм применим для функций в ДНФ, не обязательно в СДНФ?

-- 01.10.2025, 08:16 --

Пара слов, откуда задача.

Есть объекты, у которых есть $n$ признаков.
Имеется описание классификации этих объектов на естественном языке.
Задача: формализовать классификацию таким образом, чтобы можно было быстро (в реалтайм) классифицировать объекты.
Такие задачи могут повторяться (с новым описанием классификации).

Так как описание на естественном языке (и формулируется человеком), можно ожидать:

1. что она будет в виде
"Класс А: условия отнесения к классу
Класс Б: условия отнесения к классу
и т.д.
"

Вообще говоря, в условиях одного класса может (но не обязательно) использоваться отрицание условий другого класса:
"Класс А: условия отнесения к классу
Класс Б: условия отнесения к классу - объект не попал в класс А и выполнены условия...
и т.д.
"

2. Количество классов будет небольшим. Скажем до 10, может быть до 20.

3. Количество условий в классе будет небольшим - человек их должен в память поместить

ИМХО, в таком случае удобно описывать условия в виде набора булевых функций в ДНФ (по одной на каждый класс).

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

[mihaild]

EUgeneUS в сообщении #1703985 писал(а):

Я же правильно понимаю, что этот алгоритм применим для функций в ДНФ, не обязательно в СДНФ?

Да. Для СДНФ вряд ли можно придумать что-то лучше хеш-таблицы (можно бор для гарантированной асимптотики, но на практике будет медленнее).

EUgeneUS в сообщении #1703985 писал(а):

ИМХО, в таком случае удобно описывать условия в виде набора булевых функций в ДНФ

А сколько признаков? Проблема в том, что ДНФ для отрицания ДНФ может быть большой.

[EUgeneUS]

mihaild в сообщении #1704001 писал(а):

А сколько признаков?

Обещают, что десяток - другой.
Но я бы не закладывался на это.
Во-1-х. Это сейчас их десяток, а завтра будет три десятка
Во-2-х. Не булевые, а категорийные, признаки придется "распиливать" на несколько булевых - по количеству категорий в признаке.
Оцениваю - до сотни.
UPD: до сотни - это признаков вообще.
А в каждой конкретной классификации, скорее всего будет использовано сильно меньше (да, где-то до одного-двух десятков). Просто потому, что человеку с сотней признаков будет тяжело работать и описывать это всё на естественном языке

[Sender]

mihaild в сообщении #1704001 писал(а):

Проблема в том, что ДНФ для отрицания ДНФ может быть большой.

Вроде в исходной задаче и не требуется строить отрицание ДНФ. Или вы к тому, что некоторые признаки могут быть отрицаниями принадлежности к тому или иному классу? В этом случае да, размер ДНФ в исходных переменных может нарастать каскадно, если это произойдёт, возможно, имеет смысл обратиться к булевым решателям.