Álgebra booliana: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado

Em linha

Edição atual tal como às 20h05min de 8 de fevereiro de 2023

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]

História

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]

Definição

Uma álgebra booliana é 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 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$

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

$\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 booliana.
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 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

$\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 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 $\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 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(\neg a)=\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

Notas e referências

Notas

↑ O Acordo Ortográfico de 1990 prescreve, na Base V, item 2c: Escrevem-se com i, e não com e, antes da sílaba tónica/tônica, os adjetivos e substantivos derivados em que entram os sufixos mistos de formação vernácula -iano e -iense, os quais são o resultado da combinação dos sufixos -ano e -ense com um i de origem analógica (baseado em palavras onde -ano e -ense estão precedidos de i pertencente ao tema: horaciano, italiano, duriense, flaviense, etc.): açoriano, acriano (de Acre), camoniano, goisiano (relativo a Damião de Góis), siniense (de Sines), sofocliano, torriano, torriense [de Torre(s)]. É precisamente o caso de booliano(a), que antes do Acordo se grafava com e

Referências

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

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

[1] O Acordo Ortográfico de 1990 prescreve, na Base V, item 2c: Escrevem-se com i, e não com e, antes da sílaba tónica/tônica, os adjetivos e substantivos derivados em que entram os sufixos mistos de formação vernácula -iano e -iense, os quais são o resultado da combinação dos sufixos -ano e -ense com um i de origem analógica (baseado em palavras onde -ano e -ense estão precedidos de i pertencente ao tema: horaciano, italiano, duriense, flaviense, etc.): açoriano, acriano (de Acre), camoniano, goisiano (relativo a Damião de Góis), siniense (de Sines), sofocliano, torriano, torriense [de Torre(s)]. É precisamente o caso de booliano(a), que antes do Acordo se grafava com e

[Scheinerman2003-2] Edward R. Scheinerman. Matemática Discreta - Uma Introdução. Cengage Learning Editores; 2003. ISBN 978-85-221-0291-4. p. 27.

[LipschutzLipson2004-3] Seymour Lipschutz; Marc Lipson. Matemática Discreta: Coleção Schaum. Bookman; 2004. ISBN 978-85-363-0361-1. p. 454.

[Souza2002-4] Hélio Augusto Godoy de Souza. Documentario, Realidade E Semiose. Annablume; 2002. ISBN 978-85-7419-224-6. p. 198.

[BOLZANI2004-5] CAIO AUGUSTUS MORAIS BOLZANI. Residências Inteligentes. Editora Livraria da Fisica; 2004. ISBN 978-85-88325-25-8. p. 45.

[NullLobur-6] Linda Null; Julia Lobur. Princípios Básicos de Arquitetura e Organização de Computadores. Bookman; ISBN 978-85-7780-766-6. p. 140.

[nota 1]

[1]

[2]

[3]

[4]

[5]

v d e Sistemas digitais
Componentes	Transístor Resistor Indutor Capacitor Eletrônica impressa Circuito impresso Circuito eletrônico Flip-flop Célula de memória Lógica combinatória Lógica sequencial Porta lógica Circuito booliano Circuito integrado Circuito integrado híbrido Circuito integrado de sinal misto Circuito integrado tridimensional Lógica emitter-coupled DIspositivo lógico programável Arranjo de macrocélulas Arranjo lógico programável Arranjo lógico genérico Dispositivo lógico complexo programável Arranjo de porta programável em campo Arranjo de objeto programável em campo Unidade de processamento tensorial
Teoria	Sinal digital Lógica booliana Síntese lógica Lógica na ciência da computação Arquitetura de computadores Processamento digital de sinais Teoria da troca de sinais Porta equivalente
Aplicações	Hardware Aceleração por hardware Som digital Rádio digital Fotografia digital Vídeo digital Cinematografia digital Televisão digital Ciberliteratura
Eletrônica digital