Условие:
Есть логический преобразователь, на вход которому подается логическая функция от 20 переменных, не являющаяся тождественной ложью (то есть имеющая значение ИСТИНА хотя бы для одного набора значений переменных). Работает преобразователь следующим образом:
1. Строится таблица истинности данной функции.
2. Из полученной таблицы истинности берутся наборы переменных, для которых значение функции равно ИСТИНЕ.
3. Для каждого такого набора составляется полная конъюнкция всех 20 переменных, причем если значение этой переменной в наборе равно ЛЖИ, то в конъюнкции эта переменная будет с отрицанием, если значение переменной равно ИСТИНЕ, то в конъюнкции эта переменная будет без изменений.
4. Между всеми полученными полными конъюнкциями ставятся операции ⊕ (Исключающее ИЛИ).
5. Все переменные с отрицанием заменяются по следующему правилу: $\overline{X}=(X\oplus 1)$.
6. Раскрываются все скобки по правилу: $X \land (Y \oplus Z) = X \land Y \oplus X \land Z$. После раскрытия скобок должно получиться выражение, которое может содержать некоторые отдельные переменные, конъюнкции переменных и константу ИСТИНА, соединенные Исключающим ИЛИ.
7. Из выражения убираются повторяющиеся конъюнкции. В результате у нас получается новая форма записи исходной функции. Гарантируется, что для каждой входной функции эта форма уникальна.
8. Производится проверка, остались ли в получившейся форме записи выражения операции конъюнкции. Если остались – преобразователь возвращает ЛОЖЬ, если нет – возвращает ИСТИНА.
Сколько существует таких функций от 20 переменных, которые можно подать на вход преобразователю и для которых он вернет ИСТИНУ? В ответе укажите целое число.
