Prof.ª Dr.ª Donizete Ritter MÓDULO IV PARTE 1: Álgebra

1

Prof.ª Dr.ª Donizete Ritter

MÓDULO IV – PARTE 1:

Álgebra Booleana

Bacharelado em Sistemas de Informação

Disciplina: Lógica

Álgebra de Boole

• HISTÓRIA

• A Álgebra de Boole e aplicável ao projeto dos circuitos lógicos e funcionabaseada em princípios da lógica formal.

• Álgebra Booleana é uma área da matemática que trata de regras eelementos de lógica. O nome “booleana” é uma retribuição da comunidadecientífica ao matemático inglês George Boole (1815 - 1864), quedesenvolveu uma análise matemática sobre a Lógica e em 1854 publicouum livro no qual propôs os princípios básicos dessa álgebra.

Boole percebeu que poderia estabelecer um conjunto de símbolosmatemáticos para substituir certas afirmativas da lógica formal.Publicou suas conclusões em 1854 no trabalho “Uma AnáliseMatemática da Lógica”.

Claude B. Shannon mostrou (em sua tese de Mestrado no MIT)que o trabalho de Boole poderia ser utilizado para descrever aoperação de sistemas de comutação telefônica. As observações deShannon foram divulgadas em 1938 no trabalho "Uma AnáliseSimbólica de Relés e Circuitos de Comutação".

DEFINIÇÃO DE ÁLGEBRA DE BOOLE• A Álgebra de Boole é um sistema matemático composto por operadores,

regras, postulados e teoremas. Usa funções e variáveis, como na álgebraconvencional, que podem assumir apenas um dentre dois valores, zero (0)ou um (1).

• Trabalha, basicamente com três operadores, o operador AND, simbolizadopor (.) e o operador OR, simbolizado por (+), além do operador unárioNOT. O operador AND é conhecido como produto lógico e o operadorOR e conhecido como soma lógica. Os mesmos correspondem,respectivamente, as operações de interseção e união da teoria dosconjuntos.

• Tais princípios baseiam-se em um sistema de álgebra (álgebra dasproposições) onde se pode determinar se uma sentença é falsa ouverdadeira utilizando-se para isso as funções ou operadores lógicos: E,OU e NÃO (AND, OR, NOT). Assim, “choveu ontem à tarde” é umproposição (pode ser falsa ou verdadeira).

• Porém algumas proposições são compostas de subproposições ligadas porconectivos, no nosso caso representado pelos operadores lógicos: e, ou enão. No caso dessas proposições, o operador lógico usado é que definirá ovalor lógico (se verdadeiro ou falso).

INTRODUÇÃO A ÁLGEBRA DE BOOLE

• O postulado básico da álgebra de Boole é a existência de uma variávelbooleana tal que:

x≠0 ↔ x=1

x≠1 ↔x=0

• A álgebra de Boole é um sistema algébrico que consiste do conjunto{0,1}, duas operações binárias chamadas OR (operador: +) e AND (.) euma operação unária NOT.

• A operação OR é chamada de soma lógica ou união, a operação AND éconhecida por produto lógico ou interseção e a operação NOT é ditacomplementação ou ainda inversão (não confundir com a soma denúmeros binários).

George Boole estabeleceu dois princípios fundamentais em que assenta alógica booleana, e que são:

• princípio da não contradição: “Uma proposição não pode ser,simultaneamente, verdadeira e falsa”.

• princípio do terceiro excluído: “Uma proposição só pode tomar um dosdois valores possíveis - ou é verdadeira ou é falsa - não sendo possívelterceira hipótese”

• Como já foi referido, Boole desenvolveu a sua álgebra a partir de duasgrandezas: falso e verdadeiro.

• Também os computadores digitais fazem uso de sinais binários (0 e 1).Estes sinais pretendem representar os níveis de tensão, isto é, o 0 significaque não há passagem de corrente elétrica e 1 significa passagem decorrente elétrica.

• Daqui, podemos fazer a analogia entre a linguagem dos computadores e aálgebra de Boole da seguinte forma:

• 0/Falso/Não passa corrente elétrica,

• 1/Verdadeiro/Passa corrente elétrica.

• Operadores: As variáveis booleanas são representadas por letrasmaiúsculas, A, B, C,...

• Operadores Booleanos Fundamentais:

AND, OR e NOT.

• Operador AND (interseção).

• Definição: A operação lógica AND entre duas ou mais variáveis somenteapresenta resultado 1 se todas as variáveis estiverem no estado lógico 1. Aconjunção é representada pelo conectivo "." (ponto, como se fosse amultiplicação pois também é designada por produto lógico).

• Considerando todos os "arranjos" possíveis dos valores lógicos de duasproposições, A e B, podemos estabelecer a "tabela verdade" que apresentaos resultados possíveis da conjunção lógica.

• Símbolo Lógico:

• Tabela Verdade:

• Operador OR (união).

• Definição: A operação lógica OR entre duas ou mais variáveis apresentaresultado 1 se pelo menos uma das variáveis estiver no estado lógico 1. Adisjunção inclusiva é representada pelo conectivo "+" (sinal de soma, poisrepresenta a adição lógica). A tabela verdade desta operação lógica é:

• Símbolo Lógico:

• Tabela Verdade:

• Operador NOT (inversor).

• Definição: A operação de complementação de uma variável éimplementada através da troca do valor lógico da referida variável.

• Símbolo Lógico:

• Tabela Verdade:

• Operadores Booleanos Secundários:

• NAND, NOR, XOR E XNOR

• Operador NAND:

• Definição: A porta NAND (NÃO E) equivale a uma porta AND seguidapor uma porta NOT, isto é, ela produz uma saída que é o inverso da saídaproduzida pela porta AND.

• Símbolo Lógico:

• Tabela Verdade:

• Operador NOR:

• Definição: A porta NOR equivale a uma porta OR seguida por uma portaNOT, isto é, ela produz uma saída que é o inverso da saída produzida pelaporta OR.

• Símbolo Lógico:

• Tabela Verdade:

• Operador XOR (OU exclusivo)

• Definição: A operação lógica XOR entre duas variáveis A e B apresentaresultado 1 se uma e somente uma das duas variáveis estiver no estadológico 1 (ou seja se as duas variáveis estiverem em estados lógicosdiferentes).

• Símbolo Lógico:

• Tabela Verdade:

• Operador XNOR (negativo de OU exclusivo)

• Definição: A operação lógica XNOR entre duas variáveis A e B apresentaresultado 1 se e somente se as duas variáveis estiverem no mesmo estadológico.

• Símbolo Lógico:

• Tabela Verdade:

PROPRIEDADES BÁSICAS

• Sendo x uma variável booleana, então:

• A álgebra booleana é comutativa e associativa com relação às duasoperações binárias. Sendo x, y, z variáveis booleanas, então:

• Na álgebra booleana, a soma é distributiva sobre o produto e o produto édistributivo sobre a soma,

• Notemos que estas propriedades apresentam-se aos pares e que em cadapar, uma equação pode ser obtida da outra mediante a troca de 1 por 0 e 0por 1 além de permutarmos os AND’s pelos OR’s .

• Isto é conhecido como princípio da dualidade da álgebra de Boole (obs:todas estas expressões podem ser provadas por indução finita, bastandoprovar uma equação e a sua dual estará provada).