On the Hamming distance between almost all Boolean functions

A precise estimate of the Hamming distance between almost all Boolean functions is presented.     

A new normal form of Boolean functions

A new normal form of Boolean functions based on the sum (mod 2), product and negation is presented. Let n = {1, 2,…, n}, let A_s be the family of s-element subsets of a set A and let π_a?φx_a = 1. Then every Boolean function ?(x₁,x₂,…,x_n) has a normal form

$\text{?(x}{}_1\text{,x}{}_2\text{,…,x}{}_{\mathrm{n}}\text{=}\text{∑}\text{s=0}\text{n}\text{⊕}\text{Π}\text{A∈n}{}_{\mathrm{s}}\text{1⊕d}{}_{\mathrm{A}}\text{Π}\text{a∈A}\text{x}{}_{\mathrm{a}}$

with unique coefficients d_A? {0, 1}. A transformation of Galois normal form into the present normal form is also shown.     

Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

The problem of constructing simple disjunctive normal forms (DNFs) of Boolean functions with a small number of zeros is considered. The problem is of interest in the complexity analysis of Boolean functions and in its applications to data analysis. The method used is a further development of the reduction approach to the construction of DNFs of Boolean functions. A key idea of the reduction method is that a Boolean function is represented as a disjunction of Boolean functions with fewer zeros. In a number of practically important cases, this technique makes it possible to considerably reduce the complexity of DNF implementations of Boolean functions.     

Boolean function minimization in the class of disjunctive normal forms

The survey focuses on minimization of boolean functions in the class of disjunctive normal forms (d.n.f.s) and covers the publications from 1953 to 1986. The main emphasis is on the mathematical direction of research in boolean function minimization: bounds of parameters of boolean functions and algorithmic difficulties of minimal d.n.f. synthesis). The survey also presents a classification of minimization algorithms and gives some examples of minimization heuristics with their efficiency bounds.Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 25, pp. 68–116, 1987.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

On the normal completion of a Boolean algebra

A familiar construction for a Boolean algebra A is its normal completion, given by its normal ideals or, equivalently, the intersections of its principal ideals, together with the embedding taking each element of A to its principal ideal. In the classical setting of Zermelo-Fraenkel set theory with Choice, is characterized in various ways; thus, it is the unique complete extension of A in which the image of A is join-dense, the unique essential completion of A, and the injective hull of A.Here, we are interested in characterizing the normal completion in the constructive context of an arbitrary topos. We show among other things that it is, even at this level, the unique join-dense, or alternatively, essential completion. En route, we investigate the functorial properties of and establish that it is the reflection of A, in the category of Boolean homomorphisms which preserve all existing joins, to the complete Boolean algebras. In this context, we make crucial use of the notion of a skeletal frame homomorphism.     

On the corona theorem for almost periodic functions

LetAP ⁺ (R ⁿ ) denote the Banach algebra of all continuous almost periodic functions onR ⁿ whose Bohr-Fourier spectrum is contained in an additive semi-group [0, ) ⁿ . We show that the maximal ideal space ofAP ⁺ (R ⁿ ) may have a nonempty corona and we characterize all for which the corona is empty. Analogous results are established for algebras of almost periodic functions with absolutely convergent Fourier series.     

On properties of almost all matroids

We give several results about the asymptotic behaviour of matroids. Specifically, almost all matroids are simple and cosimple and, indeed, are 3-connected. This verifies a strengthening of a conjecture of Mayhew, Newman, Welsh, and Whittle. We prove several quantitative results including giving bounds on the rank, a bound on the number of bases, the number of circuits, and the maximum circuit size of almost all matroids.     

On Boolean ranges of Banaschewski functions

We construct a countable lattice \({\varvec{\mathcal {S}}}\) isomorphic to a bounded sublattice of the subspace lattice of a vector space with two non-iso-morphic maximal Boolean sublattices. We represent one of them as the range of a Banaschewski function and we prove that this is not the case of the other. Hereby we solve a problem of F. Wehrung. We study coordinatizability of the lattice \({\varvec{\mathcal {S}}}\). We prove that although it does not contain a 3-frame, the lattice \({\varvec{\mathcal {S}}}\) is coordinatizable. We show that the two maximal Boolean sublattices correspond to maximal Abelian regular subalgebras of the coordinatizating ring.     

On certain arithmetic functions involving the greatest common divisor

The paper deals with asymptotics for a class of arithmetic functions which describe the value distribution of the greatest-common-divisor function. Typically, they are generated by a Dirichlet series whose analytic behavior is determined by the factor ζ²(s)ζ(2s − 1). Furthermore, multivariate generalizations are considered.     

On the arithmetic Walsh coefficients of Boolean functions

We generalize to the arithmetic Walsh transform (AWT) some results which were previously known for the Walsh–Hadamard transform of Boolean functions. We first generalize the classical Poisson summation formula to the AWT. We then define a generalized notion of resilience with respect to an arbitrary statistical measure of Boolean functions. We apply the Poisson summation formula to obtain a condition equivalent to resilience for one such statistical measure. Last, we show that the AWT of a large class of Boolean functions can be expressed in terms of the AWT of a Boolean function of algebraic degree at most three in a larger number of variables.