NOÇÕES DE LÓGICA MATEMÁTICA

NOÇÕES DE ÁLGEBRA BOOLEANA

"Uma das características da investigação científica é procurar padrões ou semelhanças entre fenômenos observados"(livro I). Vimos que o Cálculo Proposicional e a Teoria dos Conjuntos possuem algumas propriedades em comum ou sejam são estruturas matemáticas que, juntamente com operações ou relações entre seus objetos obedecem certas regras." Podemos comparar uma estrutura matemática a um esqueleto humano pois, embora as aparências externas das pessoas sejam diferentes, a forma e a disposição dos ossos são as mesmas."(livro I). Assim, vamos definir, uma estrutura matemática, Álgebra Booleana, que incorpora as propriedades básicas do Cálculo Proposicional e da Teoria dos Conjuntos, ou seja, é um outro modelo de uma mesma estrutura matemática. O conceito de Álgebra Booleana foi formulado pelo matemático inglês George Boole por volta de 1850.

Por ÁLGEBRA BOOLEANA entendemos um conjunto B={p, q, r , ..} junto com duas operações binárias + e · em B, uma operação singular em B e dois elementos distintos 0 e 1 de B tais que valem as seguintes propriedades: (para todo p , q , r em B ) :
 
Associativa (p + q) + r = p + (q + r) (p · q) · r = p · (q · r)
Comutativa p + q = q + p p · q = q · p
Idempotente p + p = p p · p = p
Absorção (p · q) + p = p (p + q) · p = p
Distributiva p + (q · r) = (p + q) · (p + r) p · (q + r) = (p · q) + (p · r)
Propriedades do 0 p + 0 = p p · 0 = 0
Propriedades do 1 p + 1 = 1  p · 1 = p
Quaisquer que seja p em B, existe p’ em B tal que p + p’ = 1 p · p’ = 0

Indicamos uma Álgebra Booleana por [ B , + , · , ’ , 0 , 1 ].

- A operação p · q pode ser denotada simplesmente por pq eliminando o operador · .

- É normal a seguinte terminologia na Álgebra Booleana :
p · q : encontro de p e q.
p + q : junção de p e q.
p’ : complemento de p.
0 : elemento zero.
1 : elemento unitário.

Uma expressão booleana, uma fórmula e uma expressão na álgebra do conjuntos,são correspondentes se substituimos ’ , + , · , = , 0 , 1 respectivamente por   ~ , Ú , Ù , Û , F , V ou ainda por ’, È , Ç , = , Æ , U
(considerando-se p , q ,.. como: elementos de B , variáveis proposicionais ou conjuntos respectivamente).

Exemplo: (p’ + (q · r))’ corresponde a ~(~ p Ú (q Ù r)) ou ainda a (p’ È (q Ç r))’

Para formalizar as semelhanças entre o Cálculo Proposicional e a Álgebra Booleana, notemos que o conjunto das proposições é uma Álgebra de Boole em relação à conjunção, à disjunção e à negação.

 


APLICAÇÕES DE ÁLGEBRA BOOLEANA : MAPA DE KARNAUGH

De modo sucinto podemos dizer que o MAPA DE KARNAUGH,  idealizado em 1950 por MauriceKarnaugh, é um método de simplificação de expressões lógicas fundamentado em teoremas da Álgebra Booleana e utilizando representações gráficas. Utilizando o mapa de Karnaugh podemos simplificar fórmulas ou expressões booleanas em FND COMPLETA, sem o uso direto de propriedades para obter tais simplificações.

REPRESENTAÇÃO GRÁFICA : Temos as seguintes representações gráficas (mapas), de acordo com o número de variáveis (aqui representadas por letras maiúsculas) das expressões: (no que se segue entende-se AB como A · B)
a) Duas variáveis:

  A’
B    
B’    
b) Três variáveis :
  AB AB’  A’B’  A’B
C        
C’        
c) Quatro variáveis :
  AB  AB’  A’B’  A’B
CD        
CD’        
C’D’        
C’D        
Em cada mapa:

·Os quadrados de cima e os de baixo são adjacentes; os da esquerda e os da direita são adjacentes.
·Os quadrados adjacentes diferem apenas por uma variável .
·Cada quadrado indicará um DISJUNCTO da FNDCOMPLETA que está sendo representada.
·Cada DISJUNCTO será representado escrevendo 1 no respectivo quadrado.

Exemplos:
Representar a expressão AB’C + A’B’C + ABC’

     AB   AB’    A’B’   A’B
C      1      1  
C’     1      

Representar a expressão AB’+ A’B + A’B’

      A     A’
B      1
B’      1    1

Podemos construir Mapas de Karnaugh para 5 ou mais variáveis passando para representações gráficas tridimensionais tornando-se inadequado.

SIMPLIFICAÇÃO : Para simplificar procedemos do seguinte modo:

1. Agrupar , traçando ovais ao redor de todos os "1" para formar grupos de 2n "1" adjacentes.
2. Nenhum "1" pode ficar fora dos grupos formados. Se necessário, agrupá-lo sozinho.
3. Quanto maior o grupo, mais simplificada ficará a expressão.
4. Se necessário, um "1" pode ser agrupado mais de uma vez. Nunca agrupá-lo se não houver necessidade.
5. A variável que se repetir em cada grupo permanece na expressão. A variável que não se repete é eliminada.

Exemplos:
a) Simplificando a expressão ABC + AB’C’ + A’BC obtemos a expressão AB’C’ + BC




 

b) Simplificando a expressão AB’+ A’B + A’B’ obtemos A’+ B’



 


c) Simplifique usando um applet apropriado para 4 variáveis.


APLICAÇÕES DE ÁLGEBRA BOOLEANA : ÁLGEBRA DOS CIRCUITOS

A introdução de uma Álgebra Booleana no estudo dos circuitos deve-se ao matemático americano CLAUDE ELWOOD SHANNON (1916-2001) (A Symbolic Analysis of Relay and Switching Circuits - 1938). De modo sucinto mostraremos esse tipo de relacionamento com a Cálculo Proposicional e a Álgebra Booleana.

Um interruptor é um dispositivo ligado a um ponto de um circuito, que pode assumir um dos dois estados, "fechado" ou "aberto". No estado "fechado" (que indicaremos por 1) o interruptor permite que a corrente passe através do ponto, enquanto no estado "aberto" (que indicaremos por 0) nenhuma corrente pode passar pelo ponto.

1.Circuito com um interruptor p:
             p

A indicação "fechado" ou "aberto" do interruptor será conhecida com a indicação de p=1 ou p=0 respectivamente.

2.Circuito com dois interruptores p e q:

· Em paralelo indicado por p + q
                  p

                 q            Neste caso não passa corrente se e somente p=0 e q=0 ou seja, estão ambos "abertos" o que corresponde no Cálculo Proposicional à tabela verdade da disjunção p Ú q .

· Em série indicado por p · q ou pq
           p              q
Neste caso passa corrente se e somente se p=1 e q=1 ou seja, estão ambos "fechados" o que corresponde no Cálculo Proposicional à tabela verdade da conjunção p Ù q .

· Circuitos acoplados contraditórios: quando um abre o outro fecha e reciprocamente correspondendo à tabela verdade da negação.
· Circuitos acoplados equivalentes: se comportam do mesmo modo correspondendo à tabela verdade da bi-implicação p « q .

Exemplo : A expressão booleana correspondente ao esquema abaixo é :
(( p· q) + ((p· q) + q)) = pq + pq + q
Simplificando a expressão:
(( p· q) + ((p· q) + q)) = ( p· q) + q = q (por absorção) representamos o circuito simplificado obtido :



 
 

Exemplo : A expressão e um circuito correspondente à fórmula
( p ® q) Ú ~ r Û~ p Ú q Ú~ r será : p’ + q +r’


Exemplo : Um comitê tem 3 membros . Um projeto passa se e somente se o presidente vota a favor e obtém maioria. Projetar um circuito de modo que cada membro vote a favor apertando um botão e tal que a luz se acenda se o projeto for aprovado.

Solução: Sendo P o presidente e A e B os outros dois membros, a tabela verdade abaixo corresponde às informações dadas onde 1 representa a aprovação do projeto.

Obtendo a FND correspondente temos (P · A · B) + (P · A · B’ ) + (P · A’ · B) que simplificando por Mapa de Karnaugh temos PA + PB = P ( A + B)   sendo simples a representação do circuito.

  P       A      B     ?
1 1 1 1
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0


CELINA ABAR
- 2004 -