Generation of near-optimal universal Boolean functions

摘要

A Boolean function U(z1, z2,…,zm) is universal for given n≥1 if it realizes all Boolean functions f(x1,…,xn) by substituting for each zj a variable of the set {0, 1, x1,…,xn, 1,…,n}). An easily applied method based on linear algebra is developed for finding universal Boolean functions having a small number m of arguments. It is shown that this number is asymptotically minimal.