Product Code Database
Example Keywords: kindle -wii $82
   » Wiki: Free Boolean Algebra
Tag Wiki 'Free Boolean Algebra'.

Free Boolean algebra

In , a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that:
  1. Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean operations, and
  2. The generators are as independent as possible, in the sense that there are no relationships among them (again in terms of finite expressions using the Boolean operations) that do not hold in every Boolean algebra no matter which elements are chosen.

A simple example
The of a free Boolean algebra can represent independent . Consider, for example, the propositions "John is tall" and "Mary is rich". These generate a Boolean algebra with four atoms, namely:
  • John is tall, and Mary is rich;
  • John is tall, and Mary is not rich;
  • John is not tall, and Mary is rich;
  • John is not tall, and Mary is not rich.

Other elements of the Boolean algebra are then logical disjunctions of the atoms, such as "John is tall and Mary is not rich, or John is not tall and Mary is rich". In addition there is one more element, FALSE, which can be thought of as the empty disjunction; that is, the disjunction of no atoms.

This example yields a Boolean algebra with 16 elements; in general, for finite n, the free Boolean algebra with n generators has 2 n atoms, and therefore 2^{2^n} elements.

If there are many , a similar situation prevails except that now there are no atoms. Each element of the Boolean algebra is a combination of finitely many of the generating propositions, with two such elements deemed identical if they are logically equivalent.

Category-theoretic definition
In the language of , free Boolean algebras can be defined simply in terms of an %

Page 1 of 1


Pages:  ..   .. 
Items:  .. 


General: Atom Feed Atom Feed  .. 
Help:  ..   .. 
Category:  ..   .. 
Media:  ..   .. 
Posts:  ..   ..   .. 


Page:  .. 
Summary:  .. 
1 Tags
10/10 Page Rank
634 Page Refs
1s Time