Попарно неравносильные означают, что для любой формулы во множестве формул на общем множестве переменных нет равносильной ей. Любые две формулы достаточно свести к их полным дизъюнктивной или конъюнктивной нормальным формам (ДНФ, КНФ), чтобы установить их равносильность или неравносильность. Можно и по таблицам истинности проверять.
Попытаюсь объяснить наглядно. В случае N переменных имеется 2^N различных наборов значений этих переменных: если выписать в таблице по столбцам переменые X1...XN, то их значения, состоящие из 1 и 0 займут 2^N различных строк. В этой же таблице можно ввести колонку результата F, имеющую 2^N значений. Так как неравносильные формулы дают различный результат, получаем, что каждая формула даёт набор из M=2^N значений. Количество таких наборов 2^M. Таким образом, имеем количество неравносильных формул 2^(2^N).
Пример для N=2.
Имеем 2^N наборов значений переменных (в данном случае 4).
В этом случае F может принимать следующие возможные значения:
F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1