В статье сравниваются мощности некоторых классов булевых функций, бесповторных в полном бинарном базисе B2 = {&, ∨, ⊕}. Бесповторные функции представляются помеченными корневыми деревьями, среди которых выделяются канонические. Далее приводится алгоритм, позволяющий преходить от канонических деревьев к полным бинарным каноническим деревьям. Данный алгоритм связывает два принципиально различных подхода к построению однозначного представителя для бесповторной в B₂ функции. Представление бесповторных функций в виде полных бинарных канонических деревьев позволяет доказать,что среди всех бесповторных функций от n переменных, доля функций, в каноническом представлении которых содержится хотя бы одна k-местная фунция &, ∨ или ⊕ экспоненциально стремится к нулю с ростом величины k. Данный результат представляет интерес для тестирования бесповторных функций.

1. Вороненко А. А. О проверяющих тестах для бесповторных функций // Математические вопросы кибернетики. — 2002. — вып. 11. — С. 163-176.

2. Зубков О. В. О числе бесповторных булевых функций в базисе {&,;∨, ⊕,−}//, Дискретный анализ и исследование операций. — 2003. — серия 1, Т. 10, N 1. — С.41 -60.