Álgebra booliana

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Álgebra booleana)
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde janeiro de 2014).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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 oferece um estrutura para se lidar com "afirmações",[1] são assim denominadas em homenagem ao matemático George Boole.[2]

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

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

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



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

Exemplos[editar | editar código-fonte]

  • O exemplo mais simples de álgebra booleana com mais de um elemento é o conjunto \{0, 1\} munido das seguintes operações:
    \vee         0         1    
    0         0         1    
    1         1         1    
    \wedge         0         1    
    0         0         0    
    1         0         1    
    \neg         0         1    
    1         0    
  • Um outro exemplo de álgebra booleana é o conjunto \{0, 1, ?\} (o elemento ? é geralmente chamado de "desconhecido" ou de "talvez") munido das seguintes operações:
    \vee         0         1         ?    
    0         0         1         ?    
    1         1         1         1    
    ?         ?         1         ?    
    \wedge         0         1         ?    
    0         0         0         0    
    1         0         1         ?    
    ?         0         ?         ?    
    \neg         0         1         ?    
    1         0         ?    
  • Dado um conjunto A, o conjunto P(A) das partes de A munido das operações a \vee b = a \cup b, a \wedge b = a \cap b, \neg a = A \setminus a, e onde 0 = \varnothing e 1 = A, é uma álgebra booleana.
  • O intervalo [0, 1] munido das operações a \vee b = \mathrm{max}\{a, b\}, a \wedge b = \mathrm{min}\{a, b\}, e \neg a = 1 - a, é uma álgebra booleana. Essa álgebra booleana recebe o nome de lógica fuzzy.

Teoremas[editar | editar código-fonte]

Dado uma álgebra booleana sobre X, são válidos para quaisquer a, b \in X:

Propriedades Idempotentes

  • a \vee a = a
  • a \wedge a = a

Dupla Negação

  • \neg (\neg a) = a

Leis de De Morgan

  • \neg (a \vee b) = \neg a \wedge \neg b
  • \neg (a \wedge b) = \neg a \vee \neg b

Leis de absorção|Propriedades Absorventes

  • a \vee (a \wedge b) = a
  • a \wedge (a \vee b) = a

Elementos Absorventes

  • a \vee 1 = 1
  • a \wedge 0 = 0

Negações do Zero e do Um

  • \neg 0 = 1
  • \neg 1 = 0

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

  • a \veebar b = (a \vee b) \wedge (\neg a \vee \neg b)
  • a \veebar b = (a \wedge \neg b) \vee (\neg a \wedge b)

Ordem[editar | editar código-fonte]

Dado uma álgebra booleana sobre X, é válido quantificação universal para quaisquer a, b \in X:

  • a \vee b = b se e somente se a \wedge b = a

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


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

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

  • f(a \vee b) = f(a) \vee f(b)
  • f(a \wedge b) = f(a) \wedge f(b)
  • f(0) = 0
  • f(1) = 1

Uma consequência é que f(\neg a) = \neg f(a).

Um isomorfismo entre duas álgebras booleanas A e B é um homomorfismo bijetor entre A e B. O inverso de um isomorfismo é um isomorfismo. Se existe um isomorfismo entre A e B, dizemos que A e B são isomorfos.


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

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


Referências

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