Álgebra booliana – Wikipédia, a enciclopédia livre

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (N • L • A)). (Janeiro de 2014)

 Nota: Não confundir com Álgebra booliana (estrutura).

Em álgebra abstrata, álgebras boolianas^{[nota 1]} (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]

Ver artigo principal: 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.^[3] 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.^[4][5]

Uma álgebra booliana é 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 booliana com somente um elemento.

• 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 {\mathcal {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.

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

• ${\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)}$

Dado uma álgebra booliana sobre ${\displaystyle X}$, é válido para quaisquer ${\displaystyle a,b\in X}$:

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

A 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.

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.

• 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

Notas

Referências

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