Поскольку
maxal ввёл аппарат бинарных матриц, то приведу описание задачи через бинарные матрицы и операции с ними.
Пусть

- бинарная матрица размера
![$[n \times m]$ $[n \times m]$](https://dxdy-01.korotkov.co.uk/f/8/c/d/8cd87cf327f753bf2971c2fc2349c21282.png)
, где

, причём матрица

состоит из блоков — матриц

, где
![$k \in [1..n]$ $k \in [1..n]$](https://dxdy-01.korotkov.co.uk/f/4/4/4/444e3483710cac8913a41f6f4420689482.png)
, а размер блоков
![$[n \times C^k_n]$ $[n \times C^k_n]$](https://dxdy-01.korotkov.co.uk/f/4/c/c/4cc20d1883e851b2757823ae50e1d2d982.png)
, где

- биноминальный коэффициент.
Пример для n=3:

Столбец такой матрицы - это элемент покрытия множества

,

.
Бинарный вектор

- это выбор конкретного покрытия множества

.
Тогда мы можем сформулировать требования к вектору

:
1.

AND

- это требование "быть покрытием", а

-

-ая строка матрицы

2.

XOR

AND

- это требование "быть Т0-покрытием"
3. Для любых двух векторов-аксиом не существует такой перестановки строк матрицы

, что для любой строки матрицы

битовое AND до и после перестановки с одним и другим вектором-аксиомой равны друг другу.
Третье условие муторно записывать в математической нотации, пишу "заклинание".
Для того, чтобы уйти от полного перебора в п.3 заметим, что из всего класса эквивалентных аксиом нам нужно выбрать одного представителя по какому-то критерию. С учётом введенных обозначений таким критерием может быть минимальным числом, представленным двоичной записью вектора-аксиомы.
Будем представлять вектор-аксиому как набор n векторов-компонент

, соответствующих блокам матрицы

.
Тогда очевидно, что если [i+1..n] векторов-компонент пусты, а

-й вектор-компонент содержит

единиц (бит), то вид этого компонента будет

(младший разряд находится слева).
Такой подход к блочному представлению и поиску минимального числа - представления вектора-аксиомы позволяет немного "сэкономить" на переборах. Плюс разбивает задачу на поиск минимальных векторов - представителей класса эквивалентных аксиом - на подзадачи, где каждая подзадача определена кортежем из количества бит в каждом векторе-компоненте.
Если найден некоторый минимальный вектор с нулевыми [i+1..n] компонентами, то добавление i-ой компоненты с m битами также образует минимальный вектор. Но такой способ построения, по крайней мере, в однопроходном варинте, не даёт возможность построить все вектора-аксиомы — представителей классов эквивалентных векторов.
Однако мы можем ограничить число операций по проверке перестановок: мы можем проверять минимальность не всего вектора, а покомпонентно.
Пусть

- матрица
![$[n \times n]$ $[n \times n]$](https://dxdy-04.korotkov.co.uk/f/7/d/c/7dc3a8876fad504bef531266eea49d9e82.png)
перестановок строк, а

- матрица
![$[m \times m]$ $[m \times m]$](https://dxdy-01.korotkov.co.uk/f/c/0/2/c028fed7f3f25bc55cb37ed5ea71596c82.png)
перестановок столбцов.
Тогда

, а

По условию поиска минимального элемента, перестановка

должна быть такой, чтобы старший ненулевой компонент вектора-аксиомы сохранял свою структуру:

.
Это означает, что

имеет блочный вид:

, где

- матрица
![$[p \times p]$ $[p \times p]$](https://dxdy-03.korotkov.co.uk/f/a/1/2/a12d03b521b62f8b7ef138ce82d5981e82.png)
- матрица перестановки первых

столбцов для которых старший ненулевой вектор-компонент имеет 1.
Тогда

, где

- псевдообратная матрица к

Что можно сказать о структуре матрицы перестановки строк

?
Возможно ли в рамках изложенного сформулировать задачу динамического программирования, например?