Álgebra booliana

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", são assim denominadas em homenagem ao matemático George Boole.

História

Ver artigo principal: George Boole

O termo "álgebra booleana" é uma homenagem a George Bolas, 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. 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 em 1898 na Universal Algebra de Whitehead.

Definição

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

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

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

• $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 "xor" 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

Dado uma álgebra booleana sobre $X$, é válido para quaisquer $a,b\in X$:

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

A 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

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.

Anéis Booleanos

Dado uma álgebra booleana sobre $X$, é possível obter um anel com unidade $(X,+,\cdot ,0,1)$ em que as operações são definidas como:

• $x+y=x\veebar y$
• $x\,\cdot \,y=x\wedge y$

Neste anel, todo elemento é seu próprio oposto (isto é, $x+x=0$ para todo $x\in X$). O anel assim obtido é chamado de anel booleano.

Ideais e Filtros

Num anel booleano $X$, um conjunto $I\subseteq X$ é um ideal de $X$ se e somente se satisfaz as seguintes condições:

• $0\in I$ e $1\notin I$
• Se $x\in I$ e $y\leq x$ então $y\in I$
• Se $x\in I$ e $y\in I$ então $x\vee y\in I$

Essa noção coincide com a de ideal próprio de teoria dos anéis.

A ideia dual à de ideal é a de filtro. Um conjunto $F\subseteq X$ é um filtro de $X$ se e somente se satisfaz as seguintes condições:

• $1\in I$ e $0\notin I$
• Se $x\in I$ e $x\leq y$ então $y\in I$
• Se $x\in I$ e $y\in I$ então $x\wedge y\in I$

Ver também

• Reticulado
• Ultrafiltro
• Princípio do terceiro excluído
• Números binários
• Lógica binária
• Tabela verdade
• Função booleana
• Circuito digital
• Forma canónica
• Sistema formal
• Mapa de Karnaugh
• Diagrama de Venn
• Álgebra de Heyting