ALGEBRA BOOLEANAS

Em álgebra abstrata, álgebras booleanas (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",^[1] são assim denominadas em homenagem ao matemático George Boole.^[2]

Índice

  [esconder] 

• 1História
• 2Definição
• 3Exemplos
• 4Teoremas
• 5Ordem
• 6Homomorfismos e isomorfismos
• 7Ver também
• 8Referências

História[editar | editar código-fonte]

Ver artigo principal: George Boole

O termo "álgebra booleana" é uma homenagem a George Boole, ummatemá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 booleana surgiu na década de 1860, em artigos escritos por William Jevons e Charles Sanders Peirce.^[3] A primeira apresentação sistemática de álgebra booleana e reticulados distributivos é devido ao 1890 Vorlesungen de Ernst Schröder . O primeiro tratamento extensivo de álgebra booleana em inglês foi um 1898 na Universal Algebra de Whitehead.^[4][5]

Definição[editar | editar código-fonte]

Uma álgebra booleana é uma 6-upla ${\displaystyle (X,\vee ,\wedge ,\neg ,0,1)}$ consistindo de um conjunto ${\displaystyle X}$ munido de duas operações binárias ${\displaystyle \vee }$ (também denotado por ${\displaystyle +}$, é geralmente chamado de "ou") e ${\displaystyle \wedge }$ (também denotado por ${\displaystyle \ast }$ ou por ${\displaystyle \cdot }$, é geralmente chamado de "e"), uma operação unária ${\displaystyle \neg }$ (também denotada por ${\displaystyle \sim }$ ou por uma barra superior, é geralmente chamado de "não"), e duas constantes ${\displaystyle 0}$ (também denotada por ${\displaystyle \bot }$ ou por ${\displaystyle F}$, geralmente chamado de "zero" ou de "falso") e ${\displaystyle 1}$ (também denotada por ${\displaystyle \top }$ ou por ${\displaystyle V}$, geralmente chamado de "um" ou de "verdadeiro"), e satisfazendo os seguintes axiomas, para quaisquer ${\displaystyle a,b,c\in X}$:

Propriedades Associativas	${\displaystyle (a\vee b)\vee c=a\vee (b\vee c)}$	${\displaystyle (a\wedge b)\wedge c=a\wedge (b\wedge c)}$
Propriedades Comutativas	${\displaystyle a\vee b=b\vee a}$	${\displaystyle a\wedge b=b\wedge a}$
Propriedades Absortivas	${\displaystyle a\wedge (a\vee b)=a}$	${\displaystyle a\vee (a\wedge b)=a}$
Propriedades Distributivas	${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)}$	${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)}$
Elementos Neutros	${\displaystyle a\vee 0=a}$	${\displaystyle a\wedge 1=a}$
Elementos Complementares	${\displaystyle a\vee \neg a=1}$	${\displaystyle a\wedge \neg a=0}$

Alguns autores também incluem a propriedade ${\displaystyle 0\neq 1}$, para evitar a álgebra booleana com somente um elemento.

Exemplos[editar | editar código-fonte]

• O exemplo mais simples de álgebra booliana com mais de um elemento é o conjunto ${\displaystyle \{0,1\}}$ munido das seguintes operações:

${\displaystyle \vee }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle 1}$

${\displaystyle \wedge }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 0}$         ${\displaystyle 1}$

${\displaystyle \neg }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle 0}$

• Um outro exemplo de álgebra booliana é o conjunto ${\displaystyle \{0,1,?\}}$ (o elemento ${\displaystyle ?}$ é geralmente chamado de "desconhecido" ou de "talvez") munido das seguintes operações:

${\displaystyle \vee }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle ?}$         ${\displaystyle 1}$         ${\displaystyle ?}$

${\displaystyle \wedge }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle ?}$         ${\displaystyle 0}$         ${\displaystyle ?}$         ${\displaystyle ?}$

${\displaystyle \neg }$         ${\displaystyle 0}$         ${\displaystyle 1}$         ${\displaystyle ?}$         ${\displaystyle 1}$         ${\displaystyle 0}$         ${\displaystyle ?}$

• Dado um conjunto ${\displaystyle A}$, o conjunto ${\displaystyle P(A)}$ das partes de ${\displaystyle A}$ munido das operações ${\displaystyle a\vee b=a\cup b}$, ${\displaystyle a\wedge b=a\cap b}$, ${\displaystyle \neg a=A\setminus a}$, e onde ${\displaystyle 0=\varnothing }$ e ${\displaystyle 1=A}$, é uma álgebra booliana.
• O intervalo ${\displaystyle [0,1]}$ munido das operações ${\displaystyle a\vee b=\mathrm {max} \{a,b\}}$, ${\displaystyle a\wedge b=\mathrm {min} \{a,b\}}$, e ${\displaystyle \neg a=1-a}$, é uma álgebra booliana. Essa álgebra booliana recebe o nome de lógica fuzzy.

Teoremas[editar | editar código-fonte]

Dado uma álgebra booliana sobre ${\displaystyle X}$, são válidos para quaisquer ${\displaystyle a,b\in X}$:

Propriedades Idempotentes

• ${\displaystyle a\vee a=a}$
• ${\displaystyle a\wedge a=a}$

Dupla Negação

• ${\displaystyle \neg (\neg a)=a}$

Leis de De Morgan

• ${\displaystyle \neg (a\vee b)=\neg a\wedge \neg b}$
• ${\displaystyle \neg (a\wedge b)=\neg a\vee \neg b}$

Leis de absorção|Propriedades Absorventes

• ${\displaystyle a\vee (a\wedge b)=a}$
• ${\displaystyle a\wedge (a\vee b)=a}$

Elementos Absorventes

• ${\displaystyle a\vee 1=1}$
• ${\displaystyle a\wedge 0=0}$

Negações do Zero e do Um

• ${\displaystyle \neg 0=1}$
• ${\displaystyle \neg 1=0}$

Definições alternativas da operação binária ${\displaystyle \veebar }$ (também denotado por ${\displaystyle \oplus }$, é geralmente chamado de "xor" ou de "ou exclusivo")

• ${\displaystyle a\veebar b=(a\vee b)\wedge (\neg a\vee \neg b)}$
• ${\displaystyle a\veebar b=(a\wedge \neg b)\vee (\neg a\wedge b)}$

Ordem[editar | editar código-fonte]

Dado uma álgebra booliana sobre ${\displaystyle X}$, é válido quantificação universal|para quaisquer ${\displaystyle a,b\in X}$:

• ${\displaystyle a\vee b=b}$ se e somente se ${\displaystyle a\wedge b=a}$

A relação binária|relação ${\displaystyle \leq }$ definida como ${\displaystyle a\leq b}$ se e somente se uma das duas condições equivalentes acima é satisfeita é uma relação de ordem em ${\displaystyle X}$. O supremo e o ínfimo do conjunto ${\displaystyle \{a,b\}}$ são ${\displaystyle a\vee b}$ e ${\displaystyle a\wedge b}$, respectivamente.

Homomorfismos e isomorfismos[editar | editar código-fonte]

Um homomorfismo entre duas álgebras boolianas ${\displaystyle A}$ e ${\displaystyle B}$ é uma função ${\displaystyle f:A\to B}$ que para quaisquer ${\displaystyle a,b\in A}$:

• ${\displaystyle f(a\vee b)=f(a)\vee f(b)}$
• ${\displaystyle f(a\wedge b)=f(a)\wedge f(b)}$
• ${\displaystyle f(0)=0}$
• ${\displaystyle f(1)=1}$

Uma consequência é que ${\displaystyle f(\neg a)=\neg f(a)}$.

Um isomorfismo entre duas álgebras boolianas ${\displaystyle A}$ e ${\displaystyle B}$ é um homomorfismo bijetor entre ${\displaystyle A}$ e ${\displaystyle B}$. O inverso de um isomorfismo é um isomorfismo. Se existe um isomorfismo entre ${\displaystyle A}$ e ${\displaystyle B}$, dizemos que ${\displaystyle A}$ e ${\displaystyle B}$ são isomorfos.

Ver também[editar | editar código-fonte]

• Reticulado
• 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

Referências

1. Ir para cima↑ Edward R. Scheinerman. Matemática Discreta - Uma Introdução. Cengage Learning Editores; 2003. ISBN 978-85-221-0291-4. p. 27.
2. Ir para cima↑ Seymour Lipschutz; Marc Lipson. Matemática Discreta: Coleção Schaum. Bookman; 2004. ISBN 978-85-363-0361-1. p. 454.
3. Ir para cima↑ Hélio Augusto Godoy de Souza. Documentario, Realidade E Semiose. Annablume; 2002. ISBN 978-85-7419-224-6. p. 198.
4. Ir para cima↑ CAIO AUGUSTUS MORAIS BOLZANI. Residências Inteligentes. Editora Livraria da Fisica; 2004. ISBN 978-85-88325-25-8. p. 45.
5. Ir para cima↑ Linda Null; Julia Lobur. Princípios Básicos de Arquitetura e Organização de Computadores. Bookman; ISBN 978-85-7780-766-6. p. 140.

[Esconder] v • e Sistemas digitais
Categoria:Eletrônica digital
Componentes	Porta lógica • Circuito digital • Circuito integrado
Aplicações	Lógica booliana • Processamento digital de sinais • Arquitetura de computadores
Teoria	Som digital • Fotografia digital • Vídeo digital

Este artigo sobre Lógica é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Categorias: 

• Álgebra
• Álgebra booliana
• Síntese lógica
• Lógica
• Ciência da computação
• Circuitos digitais
• Computação