Álgebra booleana

Na matemática, na lógica e na ciência da computação, as álgebras booleanas (ou álgebras de Boole) são estruturas algébricas que "captam as propriedades essenciais" dos operadores lógicos e de conjuntos.

História

Recebeu o nome de boleana em homenagem a George Boole, matemático inglês, que foi o primeiro a defini-las como parte de um sistema de lógica em meados do século XIX. Mais especificamente, a álgebra booleana foi uma tentativa de utilizar técnicas algébricas para lidar com expressões no cálculo proposicional. Hoje, as álgebras booleanas têm muitas aplicações na electrônica. Foram pela primeira vez aplicadas a interruptores por Claude Shannon, no século XX.

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 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 $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$

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 \vee b) \wedge (\neg a \vee \neg 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.

Ver também

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