−Table of Contents
Boolean algebras
Abbreviation: BA nbsp nbsp nbsp nbsp nbsp Search: Boolean algebras Boolean rings
Definition
A \emph{Boolean algebra} is a structure A=⟨A,∨,0,∧,1,−⟩ of type ⟨2,0,2,0,1⟩ such that
0,1 are identities for ∨,∧: x∨0=x, x∧1=x
− gives a complement: x∧−x=0, x∨−x=1
∨,∧ are associative: x∨(y∨z)=(x∨y)∨z, x∧(y∧z)=(x∧y)∧z
∨,∧ are commutative: x∨y=y∨x, x∧y=y∧x
∨,∧ are mutually distributive: x∧(y∨z)=(x∧y)∨(x∧z), x∨(y∧z)=(x∨y)∧(x∨z)
Definition
A \emph{Boolean algebra} is a structure A=⟨A,∨,0,∧,1,−⟩ of type ⟨2,0,2,0,1⟩ such that
⟨A,∨,0,∧,1⟩ is a bounded distributive lattice
− gives a complement: x∧−x=0, x∨−x=1
Morphisms
Let A and B be Boolean algebras. A morphism from A to B is a function h:A→B that is a homomorphism:
h(x∨y)=h(x)∨h(y), h(−x)=−h(x)
It follows that h(x∧y)=h(x)∧h(y), h(0)=0, h(1)=1.
Definition
A \emph{Boolean ring} is a structure A=⟨A,+,0,⋅,1⟩ of type ⟨2,0,2,0⟩ such that
⟨A,+,0,⋅,1⟩ is a commutative ring with unit
⋅ is idempotent: x⋅x=x
Remark: The term-equivalence with Boolean algebras is given by x∧y=x⋅y, −x=x+1, x∨y=−(−x∧−y) and x+y=(x∨y)∧−(x∧y).
Definition
A \emph{Boolean algebra} is a Heyting algebra A=⟨A,∨,0,∧,1,→⟩ such that
→0 is an involution: (x→0)→0=x
Examples
Example 1: ⟨P(S),∪,∅,∩,S,−⟩, the collection of subsets of a sets S, with union, intersection, and setcomplementation.
Basic results
Properties
Classtype | variety |
---|---|
Equational theory | decidable in NPTIME |
Quasiequational theory | decidable |
First-order theory | decidable |
Congruence distributive | yes |
Congruence modular | yes |
Congruence n-permutable | yes, n=2 |
Congruence regular | yes |
Congruence uniform | yes |
Congruence extension property | yes |
Definable principal congruences | yes |
Equationally def. pr. cong. | yes |
Amalgamation property | yes |
Strong amalgamation property | yes |
Epimorphisms are surjective | yes |
Locally finite | yes |
Residual size | 2 |
Finite members
Number of algebras ={1if size=2n0otherwise.