Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

Boolean Algebra as a Fragment of the Theory of Boolean Toposes

Basic identities of Boolean algebra are considered, and their categorical analogs are proved.     

从布尔代数到布尔微积分

布尔函数作为最简单的有限值函数具有特殊的重要性．它在包括信息、控制等许多领域有着广泛的应用．本文综合介绍有关布尔函数的理论基础．包括从布尔代数到布尔微积分的主要理论结果,它们在信息与控制中的一些重要应用,以及其前沿动态与新进展．介绍的一个重点是矩阵半张量积在这些领域的应用．     

Unification in Boolean rings

We show that two Boolean terms which are unifiable have a most general unifier, which can be described using the terms themselves and a single unifier. Techniques for finding a single unifier are given.     

A Shortest 2-Basis for Boolean Algebra in Terms of the Sheffer Stroke

In this article, we present a short 2-basis for Boolean algebra in terms of the Sheffer stroke and prove that no such 2-basis can be shorter. We also prove that the new 2-basis is unique (for its length) up to applications of commutativity. Our proof of the 2-basis was found by using the method of proof sketches and relied on the use of an automated reasoning program. This revised version was published online in August 2006 with corrections to the Cover Date.     

Short Single Axioms for Boolean Algebra

We present short single equational axioms for Boolean algebra in terms of disjunction and negation and in terms of the Sheffer stroke. Previously known single axioms for these theories are much longer than the ones we present. We show that there is no shorter axiom in terms of the Sheffer stroke. Automated deduction techniques were used in several parts of the work.     

A sparse matrix algorithm on the Boolean vector machine

The Boolean Vector Machine (BVM) is a large network of extremely small processors with very small memories operating in SIMD mode using bit serial arithmetic. Individual processors communicate via a hardware implementation of the Cube Connected Cycles (CCC) network. A prototype BVM with 2048 processing elements, each with 200 binary bits of memory, is currently being built using VLSI technology.

The BVM's bit-serial arithmetic and the small memories of individual processors are apparently a drawback to its effectiveness when applied to large numerical problems. In this paper we analyze an implementation of a basic matrix-vector iteration algorithm for sparse matrices on the BVM. We show that a 2²⁰ Pe BVM can deliver over 1 billion (10⁹) useful floating-point operations per second for this problem. The algorithm is expressed in a new language (BVL) which has been defined for programming the BVM.     

Boolean difference techniques in fault tree analysis

For an electrical, mechanical, or hybrid system described diagramatically as a network of interconnected components, fault tree modeling of system reliability as a function of individual component failure probabilities gives rise to logic expressions obtained from the network connections. Application of the method of Boolean differences in the analysis of such Boolean expressions is discussed, and it is shown that the influence of the status of specific components on the reliability of the total system may be investigated by straightforward algebraic operations on the network failure function.     

多值Boole过程

采用文献[1]中定义的扩展Allen-Givone代数概念将Boo1e过程沦扩充，提出了多值Boo1e过程的概念及其运算，为精确统一描述多值逻辑电路的逻辑功能和定时行为提供了一种解析途径。提出基于Allen-Givone代数的带状波形概念，用实值的加、减、乘、除运算为电路的异步特性提出了解析化的理论基础。这种数学分析与离散数学相结合的途径能相对精确地描述电路的时滞模型。在多值逻辑电路设计自动化技术的测试、模拟、综合等领域中，这种方法有它的应用前景。     

Sub-effect algebras and Boolean sub-effect algebras

 We show that Boolean effect algebras may have proper sub-effect algebras and conversely. Properties of lattice effect algebras with two blocks are shown. One condition of the completness of effect algebras is given. We also show that a lattice effect algebra associated to an orthomodular lattice can be embedded into a complete effect algebra iff the orthomodular lattice can be embedded into a complete orthomodular lattice.     

Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky

The paper by Roman Smolensky is a nice example of the art of studying mathematical structures that are, on the one hand, motivated by real computational problems but are, on the other hand, not obviously related.Dedicated to the memory of Roman Smolensky     

概率逻辑系统是与集合代数同态的布尔代数

联结词的本质是命题的运算,只有对所有命题都适用的真值函数才能用于定义联结词.概率逻辑中由于命题的内涵相关性,任何[0,1]上的函数都不能完全适用于任意命题的运算,概率逻辑的联结词不能定义成真值函数.各种算子可以作为一种计算方法使用和研究,但不能代表一个逻辑系统研究系统的性质.概率逻辑系统是概率空间的逻辑表示,是与概率空间中的事件域(集合代数)同态的布尔代数.用事件域上的集合函数精确定义各种联结词,与经典二值逻辑相容,与事实相符,能够在经典逻辑框架内实现概率命题演算.     

基于布尔语义的Gentzen推导模型

布尔模型是信息检索系统的一种基础模型。给出了命题逻辑和布尔代数间的一种新的对应关系,其中布尔代数中的不等式对应Gentzen系统中的矢列式,使得当一个不等式在任意布尔代数中为真,当且仅当它所对应的矢列式是可证的。并且使得在信息检索中,针对信息的推理可以有效地转为偏序集上的运算。讨论的命题逻辑语言的运算符为、ù、ú;并且定义了项(a|t|t1ùt2|t1út2其中a是一个元素)来替代原先的公式和表示布尔代数中的元素。此外,定义了以布尔代数为论域的赋值v,将命题逻辑中的项赋值为布尔代数中的元素,并且如果tΔΓt vtΔΔt v,则矢列式ΓT D为真。最后给出了Gentzen系统下的可靠性和完备性定理的证明。     

Sensitivity versus block sensitivity of Boolean functions

Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with . The best known separation previously was due to Rubinstein. We also report results of computer search for functions with at most 13 variables.     

Completion of Boolean algebras in MSet

Two important algebraic structures in many branches of mathematics as well as in computer science are M-sets (sets with an action of a monoid M on them) and Boolean algebras. Of particular significance are complete Boolean algebras. And in the absence of the desired completeness one often considers extensions which remedy this lack, preferably in a “universal” way as a normal completion. Combining these two structures one gets M-Boolean algebras (Boolean algebras with an action of M on them, which are a special case of Boolean algebras with operators).The aim of this paper is to study the general notion of an internally complete poset in a topos, in the sense of Johnstone, and use it to give a minimal normal completion for an M-Boolean algebra.     

Backdoor Sets of Quantified Boolean Formulas

We generalize the notion of backdoor sets from propositional formulas to quantified Boolean formulas (QBF). This allows us to obtain hierarchies of tractable classes of quantified Boolean formulas with the classes of quantified Horn and quantified 2CNF formulas, respectively, at their first level, thus gradually generalizing these two important tractable classes. In contrast to known tractable classes based on bounded treewidth, the number of quantifier alternations of our classes is unbounded. As a side product of our considerations we develop a theory of variable dependency which is of independent interest.