Mostrar código-fonte de Álgebra booliana

{{mais notas|data=janeiro de 2014}}
{{Não confundir com|Álgebra booliana (estrutura)}}
Em [[álgebra abstrata]], '''álgebras boolianas'''{{nota de rodapé|O [[Acordo Ortográfico de 1990]] prescreve, na Base V, item 2c: ''Escrevem-se com '''i''', e '''não com e''', antes da sílaba tónica/tônica, os adjetivos e substantivos derivados em que entram os sufixos mistos de formação vernácula '''-iano''' e '''-iense''', os quais são o resultado da combinação dos sufixos '''-ano''' e '''-ense''' com um '''i''' de origem analógica (baseado em palavras onde '''-ano''' e '''-ense''' estão precedidos de '''i''' pertencente ao tema: horaciano, italiano, duriense, flaviense, etc.): açoriano, acriano (de Acre), camoniano, goisiano (relativo a Damião de Góis), siniense (de Sines), sofocliano, torriano, torriense [de Torre(s)]''. É precisamente o caso de '''booliano(a)''', que antes do Acordo se grafava com '''e'''}} (ou '''álgebras de Boole''') são estruturas algébricas que "captam as propriedades essenciais" dos operadores lógicos e de conjuntos, ou ainda oferecem uma estrutura para se lidar com "afirmações",<ref name="Scheinerman2003">Edward R. Scheinerman. ''[http://books.google.com/books?id=2jlz6_IkF3UC&pg=PA27 Matemática Discreta - Uma Introdução]''. Cengage Learning Editores; 2003. ISBN 978-85-221-0291-4. p. 27.</ref> são assim denominadas em homenagem ao matemático [[George Boole]].<ref name="LipschutzLipson2004">Seymour Lipschutz; Marc Lipson. ''[http://books.google.com/books?id=2S9bwDmD1P0C&pg=PA454 Matemática Discreta: Coleção Schaum]''. Bookman; 2004. ISBN 978-85-363-0361-1. p. 454.</ref>

== História ==
{{Main|George Boole}}
O termo "álgebra booliana" é uma homenagem a [[George Boole]], um [[matemático]] inglês autodidata. Boole introduziu o sistema algébrico, inicialmente, em um pequeno panfleto, o ''The Mathematical Analysis of Logic'', publicado em 1847, em resposta a uma controvérsia em curso entre [[Augustus De Morgan]] e [[William Hamilton]], e mais tarde como um livro mais substancial, '' The Laws of Thought'', publicado em 1854. A formulação de Boole difere das descritas acima em alguns aspectos importantes. Por exemplo, a conjunção e a disjunção em Boole não era um duplo par de operações. A álgebra booliana surgiu na década de 1860, em artigos escritos por William Jevons e [[Charles Sanders Peirce]].<ref name="Souza2002">Hélio Augusto Godoy de Souza. ''[http://books.google.com/books?id=NFJ0MNh9PV4C&pg=PA198 Documentario, Realidade E Semiose]''. Annablume; 2002. ISBN 978-85-7419-224-6. p. 198.</ref> A primeira apresentação sistemática de álgebra booliana e reticulados distributivos é devido ao 1890 Vorlesungen de Ernst Schröder . O primeiro tratamento extensivo de álgebra booliana em inglês foi em 1898 na ''Universal Algebra'' de Whitehead.<ref name="BOLZANI2004">CAIO AUGUSTUS MORAIS BOLZANI. ''[http://books.google.com/books?id=tgTlPE10u68C&pg=PA45 Residências Inteligentes]''. Editora Livraria da Fisica; 2004. ISBN 978-85-88325-25-8. p. 45.</ref><ref name="NullLobur">Linda Null; Julia Lobur. ''[http://books.google.com/books?id=vn-ISIU82t4C&pg=PA140 Princípios Básicos de Arquitetura e Organização de Computadores]''. Bookman; ISBN 978-85-7780-766-6. p. 140.</ref>

== Definição ==
Uma álgebra booliana é uma [[enupla|6-upla]] <math>(X, \vee, \wedge, \neg, 0, 1)</math> consistindo de um conjunto <math>X</math> munido de duas [[operação binária|operações binárias]] <math>\vee</math> (também denotado por <math>+</math>, é geralmente chamado de "[[disjunção lógica|ou]]") e <math>\wedge</math> (também denotado por <math>\ast</math> ou por <math>\cdot</math>, é geralmente chamado de "[[conjunção lógica|e]]"), uma [[operação unária]] <math>\neg</math> (também denotada por <math>\sim</math> ou por uma barra superior, é geralmente chamado de "[[negação|não]]"), e duas [[constante matemática|constantes]] <math>0</math> (também denotada por <math>\bot</math> ou por <math>F</math>, geralmente chamado de "zero" ou de "falso") e <math>1</math> (também denotada por <math>\top</math> ou por <math>V</math>, geralmente chamado de "um" ou de "verdadeiro"), e satisfazendo os seguintes axiomas, [[quantificação universal|para quaisquer]] <math>a, b, c \in X</math>:

{| class="wikitable" style="width:100%"
|-
| [[Associatividade|Propriedades Associativas]]
|| <math>(a \vee b) \vee c = a \vee (b \vee c)</math>
|| <math>(a \wedge b) \wedge c = a \wedge (b \wedge c)</math>
|-
| [[Comutatividade|Propriedades Comutativas]]
|| <math>a \vee b = b \vee a</math>
|| <math>a \wedge b = b \wedge a</math>
|-
| [[Lei de absorção|Propriedades Absortivas]]
|| <math>a \wedge(a \vee b )= a</math>
|| <math>a \vee (a \wedge b )= a</math>
|-
| [[Distributividade|Propriedades Distributivas]]
|| <math>a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)</math>
|| <math>a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)</math>
|-
| [[Elemento neutro|Elementos Neutros]]
|| <math>a \vee 0 = a</math>
|| <math>a \wedge 1 = a</math>
|-
| Elementos Complementares
|| <math>a \vee \neg a = 1</math>|| <math>a \wedge \neg a = 0</math>
|}

Alguns autores também incluem a propriedade <math>0 \neq 1</math>, para evitar a álgebra booliana com somente um elemento.

== Exemplos ==
* O exemplo mais simples de álgebra booliana com mais de um elemento é o conjunto <math>\{0, 1\}</math> munido das seguintes [[tabela de dupla entrada|operações]]:
{|
|-
|
{| class="wikitable"
|-
!     <math>\vee</math>     !!     <math>0</math>     !!     <math>1</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>1</math>    
|-
!     <math>1</math>    
|     <math>1</math>     ||     <math>1</math>    
|}
|
{| class="wikitable"
|-
!     <math>\wedge</math>     !!     <math>0</math>     !!     <math>1</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>0</math>    
|-
!     <math>1</math>    
|     <math>0</math>     ||     <math>1</math>    
|}
|
{| class="wikitable"
|-
!     <math>\neg</math>     !!     <math>0</math>     !!     <math>1</math>    
|-
!
|     <math>1</math>     ||     <math>0</math>    
|}
|}

* Um outro exemplo de álgebra booliana é o conjunto <math>\{0, 1, ?\}</math> (o elemento <math>?</math> é geralmente chamado de "desconhecido" ou de "talvez") munido das seguintes operações:
{|
|-
|
{| class="wikitable"
|-
!     <math>\vee</math>     !!     <math>0</math>     !!     <math>1</math>     !!     <math>?</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>1</math>     ||     <math>?</math>    
|-
!     <math>1</math>    
|     <math>1</math>     ||     <math>1</math>     ||     <math>1</math>    
|-
!     <math>?</math>    
|     <math>?</math>     ||     <math>1</math>     ||     <math>?</math>    
|}
|
{| class="wikitable"
|-
!     <math>\wedge</math>     !!     <math>0</math>     !!     <math>1</math>     !!     <math>?</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>0</math>     ||     <math>0</math>    
|-
!     <math>1</math>    
|     <math>0</math>     ||     <math>1</math>     ||     <math>?</math>    
|-
!     <math>?</math>    
|     <math>0</math>     ||     <math>?</math>     ||     <math>?</math>    
|}
|
{| class="wikitable"
|-
!     <math>\neg</math>     !!     <math>0</math>     !!     <math>1</math>     !!     <math>?</math>    
|-
!
|     <math>1</math>     ||     <math>0</math>     ||     <math>?</math>    
|}
|}

* Dado um conjunto <math>A</math>, o conjunto <math>\mathcal{P}(A)</math> [[conjunto das partes|das partes]] de <math>A</math> munido das operações <math>a \vee b = a \cup b</math>, <math>a \wedge b = a \cap b</math>, <math>\neg a = A \setminus a</math>, e onde <math>0 = \varnothing</math> e <math>1 = A</math>, é uma álgebra booliana.
<!--Como exemplo, abaixo estão as tabelas das operações de <math>P(\{a, b\})</math>:
{|
|-
|
{| class="wikitable"
|-
!     <math>\vee</math>     !!     <math>0</math>     !!     <math>\{a\}</math>     !!     <math>\{b\}</math>     !!     <math>1</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>\{a\}</math>     ||     <math>\{b\}</math>     ||     <math>1</math>    
|-
!     <math>\{a\}</math>    
|     <math>\{a\}</math>     ||     <math>\{a\}</math>     ||     <math>1</math>     ||     <math>1</math>    
|-
!     <math>\{b\}</math>    
|     <math>\{b\}</math>     ||     <math>1</math>     ||     <math>\{b\}</math>     ||     <math>1</math>    
|-
!     <math>1</math>    
|     <math>1</math>     ||     <math>1</math>     ||     <math>1</math>     ||     <math>1</math>    
|}
|
{| class="wikitable"
|-
!     <math>\wedge</math>     !!     <math>0</math>     !!     <math>\{a\}</math>     !!     <math>\{b\}</math>     !!     <math>1</math>    
|-
!     <math>0</math>    
|     <math>0</math>     ||     <math>0</math>     ||     <math>0</math>     ||     <math>0</math>    
|-
!     <math>\{a\}</math>    
|     <math>0</math>     ||     <math>\{a\}</math>     ||     <math>0</math>     ||     <math>\{a\}</math>    
|-
!     <math>\{b\}</math>    
|     <math>0</math>     ||     <math>0</math>     ||     <math>\{b\}</math>     ||     <math>\{b\}</math>    
|-
!     <math>1</math>    
|     <math>0</math>     ||     <math>\{a\}</math>     ||     <math>\{b\}</math>     ||     <math>1</math>    
|}
|
{| class="wikitable"
|-
!     <math>\neg</math>     !!     <math>0</math>     !!     <math>\{a\}</math>     !!     <math>\{b\}</math>     !!     <math>1</math>    
|-
!
|     <math>1</math>     ||     <math>\{b\}</math>     ||     <math>\{a\}</math>     ||     <math>0</math>    
|}
|}-->
* O [[intervalo (matemática)|intervalo]] <math>[0, 1]</math> munido das operações <math>a \vee b = \mathrm{max}\{a, b\}</math>, <math>a \wedge b = \mathrm{min}\{a, b\}</math>, e <math>\neg a = 1 - a</math>, é uma álgebra booliana. Essa álgebra booliana recebe o nome de [[lógica fuzzy]].

== Teoremas ==
Dado uma álgebra booliana sobre <math>X</math>, são válidos [[quantificação universal|para quaisquer]] <math>a, b \in X</math>:

[[Idempotência|Propriedades Idempotentes]]
* <math>a \vee a = a</math>
* <math>a \wedge a = a</math>

Dupla Negação
* <math>\neg (\neg a) = a</math>

Leis de De Morgan
* <math>\neg (a \vee b) = \neg a \wedge \neg b</math>
* <math>\neg (a \wedge b) = \neg a \vee \neg b</math>

Leis de Absorção
* <math>a \vee (a \wedge b) = a</math>
* <math>a \wedge (a \vee b) = a</math>

Elementos Absorventes
* <math>a \vee 1 = 1</math>
* <math>a \wedge 0 = 0</math>

Negações do Zero e do Um
* <math>\neg 0 = 1</math>
* <math>\neg 1 = 0</math>

Definições alternativas da operação binária <math>\veebar</math> (também denotado por <math>\oplus</math>, é geralmente chamado de "[[disjunção exclusiva|xor]]" ou de "ou exclusivo")
* <math>a \veebar b = (a \vee b) \wedge (\neg a \vee \neg b)</math>
* <math>a \veebar b = (a \wedge \neg b) \vee (\neg a \wedge b)</math>

== Ordem ==
Dado uma álgebra booliana sobre <math>X</math>, é válido [[quantificação universal|para quaisquer]] <math>a, b \in X</math>:
* <math>a \vee b = b</math> se e somente se <math>a \wedge b = a</math>

A [[relação binária|relação]] <math>\leq</math> definida como <math>a \leq b</math> se e somente se uma das duas condições equivalentes acima é satisfeita é uma relação de ordem em <math>X</math>. O [[supremo]] e o [[ínfimo]] do conjunto <math>\{a, b\}</math> são <math>a \vee b</math> e <math>a \wedge b</math>, respectivamente.
<!--
São válidas as seguintes propriedades, [[quantificação universal|para quaisquer]] <math>a, b, c, d \in X</math>:
* se <math>a \leq b</math> e <math>c \leq d</math> então <math>a \vee c \leq b \vee d</math>
* se <math>a \leq b</math> e <math>c \leq d</math> então <math>a \wedge c \leq b \wedge d</math>
-->

<!--

* Starting with the propositional calculus with &kappa; sentence symbols, form the Lindenbaum-Tarski algebra|Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). This construction yields a boolian algebra. It is in fact the free boolian algebra on &kappa; generators. A truth assignment in propositional calculus is then a boolian algebra homomorphism from this algebra to {0,1}.

* For any natural number ''n'', the set of all positive divisors of ''n'' forms a distributive lattice if we write ''a'' &le; ''b'' for ''a'' | ''b''. This lattice is a boolian algebra if and only if ''n'' is square-free. The smallest element 0 of this boolian algebra is the natural number 1; the largest element 1 of this boolian algebra is the natural number ''n''.
* Other examples of boolian algebras arise from topology|topological spaces: if ''X'' is a topological space, then the collection of all subsets of ''X'' which are both open and closed forms a boolian algebra with the operations &or;:= &cup; (union) and &and; = &cap; (intersection).
* If ''R'' is an arbitrary [[mathematical ring|ring]] and we define the set of ''central idempotents'' by<br /> ''A'' = { ''e'' &isin; ''R'': ''e''² = ''e'', ''ex'' = ''xe'', &forall;''x'' &isin; ''R'' }<br /> then the set ''A'' becomes a boolian algebra with the operations ''e'' &or; ''f'' = ''e'' + ''f'' - ''ef'' and ''e'' &and; ''f'' = ''ef''.

-->
== Homomorfismos e isomorfismos ==
Um [[homomorfismo]] entre duas álgebras boolianas <math>A</math> e <math>B</math> é uma [[função (matemática)|função]] <math>f: A \to B</math> que para quaisquer <math>a, b \in A</math>:
* <math>f(a \vee b) = f(a) \vee f(b)</math>
* <math>f(a \wedge b) = f(a) \wedge f(b)</math>
* <math>f(0) = 0</math>
* <math>f(1) = 1</math>
Uma consequência é que <math>f(\neg a) = \neg f(a)</math>.

Um isomorfismo entre duas álgebras boolianas <math>A</math> e <math>B</math> é um homomorfismo [[função bijetora|bijetor]] entre <math>A</math> e <math>B</math>. O [[função inversa|inverso]] de um isomorfismo é um isomorfismo. Se existe um isomorfismo entre <math>A</math> e <math>B</math>, dizemos que <math>A</math> e <math>B</math> são isomorfos.

== Ver também ==
* [[Reticulado]]
* [[Ultrafiltro]]
* [[Princípio do terceiro excluído]]
* [[Números binários]]
* [[Lógica binária]]
* [[Tabela verdade]]
* [[Função booliana]]
* [[Circuito digital]]
* [[Forma canónica]]
* [[Sistema formal]]
* [[Mapa de Karnaugh]]
* [[Diagrama de Venn]]
* [[Álgebra de Heyting]]

{{Notas e referências}}

{{Sistemas digitais}}
{{esboço-lógica}}

{{DEFAULTSORT:Álgebra booliana}}
[[Categoria:Álgebra booliana]]
[[Categoria:Síntese lógica]]
[[Categoria:Ciência da computação]]
[[Categoria:Circuitos digitais]]
[[Categoria:Tecnologia da informação]]