Boolean algebras abstract the algebra of sets.
Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.
On the other hand, the theory of a Boolean algebra with a distinguished subalgebra is undecidable.
Both the decidability results and undecidablity results extend in various ways to Boolean algebras in extensions of first-order logic.
The results of such functions can be combined using the using the boolean functions: AND, NOT, OR, IF-THEN-ELSE, each of which is Turing-computable.
In one direction, an arbitrary Boolean algebra yields a topological space, and in the other direction, from a (compact Hausdorff and totally disconnected) topological space, one obtains a Boolean algebra.
An example of such an algebraic encoding is the Lindenbaum-Tarski algebra, a Boolean algebra corresponding to classical propositional logic.
Boolean negation is uniquely determined in the sense that if $\osim _1 $and $\osim _2 $are Boolean negations, then $\osim _1 A$ and $\osim _2 A$ are interderivable; ortho negation is not uniquely determined, see Restall 2000.
The main results are the following: (i) feedforward networks with finitely many processing units are computationally equivalent to Boolean circuits with finitely many gates; (ii) recurrent networks with finitely many units are equivalent to finite state automata; (iii) networks with unbounded tapes or an unbounded number of units are equivalent to Turing machines (Šíma & Orponen 2003).
The point of the procedure is to avoid the evaluation of the function for specific inputs in the determination of the global property, and it is this feature — impossible in the Boolean logic of classical computation — that leads to the speed-up relative to classical algorithms.
Such a class has many models besides the collection of all binary relations on a given universe that was considered in the 1800s, just as there are many Boolean algebras besides the power set Boolean algebras studied in the 1800s.
