Álgebra booliana

Predefinição:Mais notas Predefinição:Não confundir com Em álgebra abstrata, álgebras boolianasPredefinição:Nota de rodapé (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

Predefinição:Main 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. 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.

Definição

Uma álgebra booliana é uma 6-upla $(X,\vee ,\wedge ,\mathrm{\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 $\mathrm{\neg }$ (também denotada por $\sim$ ou por uma barra superior, é geralmente chamado de "não"), e duas constantes $0$ (também denotada por $\mathrm{\perp }$ ou por $F$, geralmente chamado de "zero" ou de "falso") e $1$ (também denotada por $\mathrm{\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 \mathrm{\neg }a=1$	$a\wedge \mathrm{\neg }a=0$

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

Exemplos

• O exemplo mais simples de álgebra booliana 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$

$\mathrm{\neg }$ $0$ $1$ $1$ $0$

• Um outro exemplo de álgebra booliana é 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$ $?$ $?$

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

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

Teoremas

Dado uma álgebra booliana 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

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

Leis de De Morgan

• $\mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b$
• $\mathrm{\neg }(a\wedge b)=\mathrm{\neg }a\vee \mathrm{\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

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

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

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

Ordem

Dado uma álgebra booliana 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 $\le$ definida como $a\le 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 boolianas $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(\mathrm{\neg }a)=\mathrm{\neg }f(a)$.

Um isomorfismo entre duas álgebras boolianas $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
• 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