A problem of Boolean function approximation by some set of basic functions is investigated. The solution is constructed by a Boolean functional tree, where leaves are assigned by variables and nodes correspond to basic functions. The objective function is considered as the sum of squared deviations between training set and the solution of the problem. A genetic programming algorithm with a steady state replacement scheme is proposed. In evolutionary process we use a randomized local search and an optimized crossover constructed in accordance with gene transmitting properties and the given objective. Local search is based on the neighbourhood with respect to subtree updating. Experimental evaluations are carried out on instances with even-n-parity and n-mux problems. The experiment shows that optimized operators outperform the randomized versions. We also compare our results with those of some state-of-the-art heuristic algorithms.