Linear equations and interpolation in Boolean algebra

The authors generalize the classical interpolation formula for Boolean functions of n variables. A characterization of all interpolating systems with 2ⁿ elements is obtained. The methods of proof used are intimately related to the solution of linear Boolean equations.     

Solution of Boolean equations

We reconstruct and refine the Boole-Jevons-Schroeder-Poretskii method of solving the inverse problems of logic, which through a misunderstanding is nowadays forgotten. We study characteristic examples of the application of the method with a suitable interpretation of the solutions that result. We give a brief presentation of the algebra of boolean expressions and the princples of its constructive implementation on a computer, making it possible in particular to automate the solution of systems of boolean equations. Translated fromMetody Matematicheskogo Modelirovaniya, 1998, pp. 59–68.     

A very rigid Boolean algebra

A Boolean algebra is constructed having only those endomorphisms corresponding to prime ideals, which are present in any BA. The BA constructed is of powerc, has 2 ^c endomorphisms, and is not rigid in Bonnet’s sense.     

Solution of elementary equations in the Minkowski geometric algebra of complex sets

The solution of elementary equations in the Minkowski geometric algebra of complex sets is addressed. For given circular disks and with radii a and b, a solution of the linear equation in an unknown set exists if and only if ab. When it exists, the solution is generically the region bounded by the inner loop of a Cartesian oval (which may specialize to a limaçon of Pascal, an ellipse, a line segment, or a single point in certain degenerate cases). Furthermore, when a<b<1, the solution of the nonlinear monomial equation is shown to be the region that is bounded by a single loop of a generalized form of the ovals of Cassini. The latter result is obtained by considering the nth Minkowski root of the region bounded by the inner loop of a Cartesian oval. Preliminary consideration is also given to the problems of solving univariate polynomial equations and multivariate linear equations with complex disk coefficients.     

A new model for Boolean algebra

This new model for set theory is a graph. It is similar in many ways to a Venn diagram or Karnaugh map, but it does not pose as a rival, merely as an alternative model which may be useful in some contexts. Defined with reference to the duality of lines and points, the graph is a fitting framework in which to display the rich duality of Boolean algebra.

In the first four sections the graph is developed as a natural embodiment of Boolean theory and it is hoped that it will be seen, not as a more computational device but as helpful for demonstrating Boolean theory. The second half of the article is devoted to practical applications. The graph can be applied (and has been applied in school teaching) extensively in set theory, in logic, in probability, in genetics and in switching circuits, but space does not allow the elaboration of all these in detail. So this article concentrates mainly on one of these applications, switching circuits. The graph is used to simplify and minimize logic circuits with techniques different from Karnaugh's and in some instances more comprehensive.     

On σ-saturations of a Boolean algebra

Nel presente lavoro introduciamo una classe di estensioni di una data algebra di Boole, denominate σ-saturazioni, in cui è definita una nozione di minimalità. II risultato principale consiste nel dimostrare che esistono algebre che non ammettono una σ-saturazione minimale, per cui è possibile ripartire tutte le algebre di Boole in tre classi: σ-sature, σ-saturabili e non σ-saturabili, di cui nessuna è vuota. Vengono inoltre messi in luce i legami esistenti fra i concetti così introdotti equelli noti di algebra completa o σ-perfetta.     

A superatomic Boolean algebra with few automorphisms

Assuming GCH, we prove that for every successor cardinal μ > ω₁, there is a superatomic Boolean algebra B such that |B| = 2^μ and |Aut B| = μ. Under ◊_ω1, the same holds for μ = ω₁. This answers Monk's Question 80 in [Mo]. Received: 1 January 1998 / Revised version: 18 May 1999 / Published online: 21 December 2000     

On generalized circulants over a Boolean algebra

For any given positive integer n, we give a necessary and sufficient condition for an n × nr-circulant (generalized circulant) over the Boolean algebra B = {0, 1} to be idempotent, and we present an algorith to obtain all n × n indempotent r-circulants over B for r = 0, 1,…,n ? 1.     

A very thin thick superatomic Boolean algebra

The existence of a very thin thick superatomic Boolean algebra is consistent with the axioms of set theory.Author partially supported by NSF Grant # MCS-8102599.Presented by Jan Mycielski.     

The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

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.     

Simplifying equations in Arabic algebra

Historians have always seen jabr (restoration) and muqābala (confrontation) as technical terms for specific operations in Arabic algebra. This assumption clashes with the fact that the words were used in a variety of contexts. By examining the different uses of jabr, muqābala, ikmāl (completion), and radd (returning) in the worked-out problems of several medieval mathematics texts, we show that they are really nontechnical words used to name the immediate goals of particular steps. We also find that the phrase al-jabr wa'l-muqābala was first used within the solutions of problems to mean al-jabr and/or al-muqābala, and from there it became the name of the art of algebra.     

On systems of Boolean equations

Systems of Boolean equations are considered. The order of maximal consistent subsystems is estimated in the general and “typical” (in a probability sense) cases. Applications for several well-known discrete problems are given.     

Segmental solutions of Boolean equations

Davio and Deschamps have shown that the solution set, K, of a consistent Boolean equation $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{)=0}$ over a finite Boolean algebra B may be expressed as the union of a collection of subsets of Bⁿ, each of the form {(x₁, …, x_n) | a_i≤x_i≤b_i, a_i?B, b_i?B, i = 1, …, n}. We refer to such subsets of Bⁿ as segments and to the collection as a segmental cover of K. We show that $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{) = 1}$ is consistent if and only if ? can be expressed by one of a class of sum-of-products expressions which we call segmental formulas. The object of this paper is to relate segmental covers of K to segmental formulas for ?.     

Forcing a Boolean algebra with predesigned automorphism group

For suitable groups we will show that one can add a Boolean algebra by forcing in such a way that is almost isomorphic to . In particular, we will give a positive answer to the following question due to J. Roitman: Is a possible number of automorphisms of a rich Boolean algebra?