03_Algebra_bin_boole

•
PUC-CAMPINAS

Danilo Freitas Silva
15/11/2013
E aí, curtiu este material?
Ajude a incentivar outros estudantes a melhorar o conteúdo
Gostou desse material? Compartilhe! 🧡
Introdução à Ciência da Computação

1.095 Materiais compartilhados
Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Prévia do material em texto
Capítulo 3: Álgebra Binária Booleana
�
O Conceito de Função
O conceito de variável e de função de uma variável nos é familiar. O campo de uma variável, isto é, o intervalo de valores que pode ser assumido por uma variável x, pode ser especificado de inúmeras maneiras. Por exemplo, x pode variar sobre o campo dos reais de menos até mais infinito; ou x pode ser restrita ao intervalo de -17 a -4; ou pode ainda ser restrita a valores inteiros de 1 a 10 e assim por diante.
Uma função é uma regra através da qual se determina o valor de uma segunda variável (dependente) “y” a partir do valor da variável (independente) “x”, sendo esta dependência representada por “y = f(x)”. 
Exemplo. Seja uma função matemática descrita por: y = 5x2 + 3. A relação funcional entre x e y pode ser dada por:
	X
	y = f(x)
	0
	3
	1
	8
	2
	23
	3
	48
As variáveis dependente (y) e independente (x) não precisam ser numéricas como na tabela a seguir, onde são descritos os significados das luzes de um semáforo:
	X
	y = f(x)
	Verde
	Prossiga
	Amarelo
	Devagar
	Vermelho
	Pare
�
Tipos de Função
As funções são classificadas como contínuas, quando podem assumir quaisquer valores dentro de um dado intervalo e discretas, caso só possam assumir alguns valores, como as funções booleanas usadas nos computadores. 
�
Funções Booleanas
Em sistemas digitais como no caso dos computadores, encontramos variáveis que são particulares no sentido de só poderem assumir dois valores, geralmente denominados verdadeiro e falso, aos quais se associam os números binários 1 e 0. Este tipo de variável é denominado variável binária ou lógica, e as funções algébricas definidas para as variáveis binárias são conhecidas como álgebra booleana, em homenagem a Charles Boole, que no século XIX desenvolveu a álgebra das variáveis binárias. Uma variável lógica é uma variável que tem três propriedades:
A variável lógica só pode assumir um de dois valores possíveis;
Os valores são expressos por afirmações declarativas, como no exemplo do semáforo;
Os dois valores possíveis, expressos por afirmações declarativas, devem ser tais que, com base em raciocínio humano, ou seja, com base na lógica, sejam mutuamente exclusivos.
Suponha que o semáforo do exemplo anterior, só pudesse estar “verde” ou “vermelho”. Neste caso, a variável “x” da tabela do semáforo seria uma variável lógica. As hipóteses possíveis seriam:
“O semáforo está verde”, o que seria representado por “x = verde” ou;
“O semáforo está vermelho”, representado por “x = vermelho”. Devido à mútua exclusividade, ao afirmarmos que “x = vermelho” também estamos dizendo que “x = não- verde”.
	
Com variáveis lógicas podemos representar qualquer coisa: temperatura, pressão, distância, velocidade, tempo, etc. Ao se considerar a relação funcional entre variáveis do ponto de vista matemático, não nos interessa o que é representado por elas. Assim, devemos dar aos dois valores possíveis de uma variável lógica, nomes que permitam considerar a variável independentemente do que ela possa representar:
	
Seja a versão simplificada da tabela do exemplo do semáforo:
	X
	Y = f(X)
	
	X
	Y = f(X)
	Verde
	Prossiga
	 -> a qual é equivalente a: ->
	1
	1
	Vermelho
	Pare
	
	0
	0
 “X” é a variável lógica independente e “Y” é a variável lógica dependente. Os valores 1 e 0 na tabela da direita são atribuídos arbitrariamente no caso de “X” para as cores “verde” e “vermelho”; e no caso da variável “Y” para os comandos “prossiga” e “pare”. Normalmente associamos ao valor 1 as idéias de verdadeiro, positivo, ativo, etc; e ao valor 0 as idéias de falso, inativo, etc.
�
Funções Booleanas Básicas
Existem várias funções booleanas, mas apenas umas popucas são necessárias para expressar a maioria dos problemas. No caso de funções com apenas uma variável independente temos:
	função 
	negação
	
	função
	coincidência
	X
	Y = não(X)
	
	X
	Y = (X)
	1
	0
	
	1
	1
	0
	1
	
	0
	0
Na função coincidência, Y assume o valor de X sempre. Na função negação ocorre o contrário. Vamos agora considerar o caso em que “Y” é função das variáveis booleanas “X” e “Z”. Neste caso, as duas funções mais comuns são:
	
	função e
	
	
	
	função ou
	
	X
	Z
	Y = (X e Z)
	
	X
	Z
	Y = (X ou Z)
	0
	0
	0
	
	0
	0
	0
	0
	1
	0
	
	0
	1
	1
	1
	0
	0
	
	1
	0
	1
	1
	1
	1
	
	1
	1
	1
Na função “e” Y só assume o valor 1 caso as variáveis X, Z sejam simultaneamente iguais a 1 (X e Z iguais a 1); Na função “ou” Y assume o valor 1 caso X seja 1 ou Z seja1 ou ambos.
�
Expressões Booleanas
Usando funções booleanas podemos escrever expressões matemáticas representando situações que envolvam uma tomada de decisão. Seja por exemplo a questão:
“João irá ao cinema mas apenas se conseguir um carro emprestado e Maria também puder ir.”
Para transformarmos esta sentença em um problema matemático devemos associar a cada afirmação uma variável booleana para depois compormos a função que a representa. 
Variável X = empréstimo do carro. Como X só pode assumir dois valores, vamos estipular que: 
X = 1 significa que João conseguiu o empréstimo do carro.
X = 0 significa que ninguem emprestou o carro para João.
Variável Z = compania da Maria. De forma análoga ao caso anterior podemos estipular que:
Z = 1 significa que Maria irá ao cinema.
Z = 0 significa que Maria não poderá ir.
Variável Y = ida de João ao cinema
Y = 1 significa que João irá ao cinema.
Y = 0 significa que João não poderá ir.
Sabemos que Y depende de X e Z, logo Y = f(X,Z). Montando uma tabela com todas as possibilidades descobrimos que a relação entre X,Z,Y é: Y = (X e Z)
	X
	Z
	Y = f(X,Z)
	SIGNIFICADO
	0
	0
	0
	João não irá ao cinema porque está sem carro e Maria não pode ir.
	0
	1
	0
	João não irá ao cinema porque está sem carro.
	1
	0
	0
	João não irá ao cinema porque Maria não pode ir.
	1
	1
	1
	João irá ao cinema com Maria usando um carro emprestado.
Vejamos agora um sentença transformada em problema matemático, utilizando
 a Tabela Verdade “OU”.
EXEMPLO: Vou ao cinema se eu tiver dinheiro para o ingresso ou se alguém
pagar para mim. 
X = Ter dinheiro ( 0 = não ter $ , 1= ter $)
Z = Alguém pagar para mim ( 0 = ninguém pg p/ mim , 1= alguém pg)
Y = X OU Z - Decisão (0= não ir ao cinema , 1= ir ao cinema)
	X
	Z
	Y = f(X,Z)
	SIGNIFICADO
	0
	0
	0
	 Não fui ao cinema porque não tenho dinheiro e ninguém pagou.
	0
	1
	1
	 Vou ao cinema porque alguém vai pagar. 
	1
	0
	1
	 Vou ao cinema porque tenho dinheiro.
	1
	1
	1
	 Vou ao cinema porque tenho dinheiro e alguém vai pagar.
As linguagens de programação de computadores possuem formas de escrever expressões como a do exemplo acima (ou bem mais complexas), as quais podem ser avaliadas pelo computador. Desta forma, usando álgebra booleana em um computador é possível criar programas que resolvam problemas que possuam uma solução lógica.
FUNÇÕES BOOLEANAS - Estudo Completo 
A notação 0 e 1
	A = 0 ==> A = F 	| ou tensões elétricas, geralmente
 	A = 1 ==> A = V 	| 0 V e +5 V.
 
	0 e 1 são valores lógicos de uma variável (não são números).
Funções Lógicas
a) a função AND
	Z = A AND B ou Z = A SYMBOL 217 \f "Symbol" B ou Z = AB (A e B)
 	Imagine o seguinte circuito:
	Convenções:	chave aberta = 0
 		chave fechada = 1
 		lâmpada apagada = 0
 		lâmpada acesa = 1
	
	A tabela verdade é o mapa onde se coloca todas as possíveis situações com seus respectivos resultados. A tabela reflete o modo como a função se comporta perante todas as situações possíveis:
 	CHAVE A		CHAVE B		CHAVE C
 	 abertaaberta			apagada
	 aberta	 	fechada		apagada
	 fechada		aberta			apagada
	 fechada		fechada		acesa
	ou:
	A B Z=f(A,B)
	0 0 0
	0 1 0
	1 0 0
	1 1 1
	A porta and é um circuito que executa a função AND:
	
	Pode-se descrever a função AND para qualquer número de entradas. A saída Z permanecerá no estado 1 se, e somente se, as N entradas forem iguais a 1 e permanecerá no estado 0 nos demais casos. O número de situações possíveis (número de linhas da tabela verdade) é igual a 2N, onde N é o número de variáveis.
b) a função OR
	Z = A + B ou Z = A SYMBOL 218 \f "Symbol" B (A ou B)
	Imagine o seguinte circuito:
	Tabela Verdade:
	 A	| B 	| Z = A + B			
	---------------------------------
	 0 	| 0 	| 0
	 0 	| 1 	| 1
	 1 	| 0 	| 1
	 1 	| 1 	| 1
	Porta Lógica OR:
c) a função NOT (complemento)
	A função NOT, ou função complemento, inverte o estado da variável.
	Z = SYMBOL 216 \f "Symbol"A (não A)
	A | Z = A
	------------------
	0 | 1
	1 | 0
Bloco Lógico que executa a função NOT = inversor
d) a função NAND
	A função NAND é a função AND combinada com a função NOT.
	Z = SYMBOL 216 \f "Symbol"(A SYMBOL 217 \f "Symbol" B) 
	Tabela verdade:
	A | B | Z = SYMBOL 216 \f "Symbol"(A SYMBOL 217 \f "Symbol" B)
	-----------------------
	0 | 0 | 1
	0 | 1 | 1
	1 | 0 | 1
	1 | 1 | 0
	Porta Lógica:
	
e) a função NOR
	A função NOR é a função OR combinada com a função NOT.
	Z = SYMBOL 216 \f "Symbol"(A SYMBOL 218 \f "Symbol" B) 
	Tabela Verdade: 
	A | B | Z = SYMBOL 216 \f "Symbol"(A SYMBOL 218 \f "Symbol" B)
	-----------------------
	0 | 0 | 1
	0 | 1 | 0
	1 | 0 | 0
	1 | 1 | 0
	Porta Lógica:
	
f) a função XOR - Exclusive-Or
	Z = A SYMBOL 197 \f "Symbol" B
	Z = 1 quando A ou B, na exclusão da outra variável, tiver valor lógico 1.
	Tabela Verdade:
	A | B | Z = A SYMBOL 197 \f "Symbol" B exclusivamente A ou exclusivamente B
	-----------------------
	0 | 0 | 0
	0 | 1 | 1
	1 | 0 | 1
	1 | 1 | 0
	Porta Lógica:
	
g) a função X-NOR - Exclusive-Nor
	A função Exclusive-Nor é a função Exclusive-Or combinada com a função NOT.
	Z = SYMBOL 216 \f "Symbol"(A SYMBOL 197 \f "Symbol" B)
	Tabela Verdade:
	A | B | Z = SYMBOL 216 \f "Symbol"(A SYMBOL 197 \f "Symbol" B)
	-----------------------
	0 | 0 | 1
	0 | 1 | 0
	1 | 0 | 0
	1 | 1 | 1
	Porta Lógica:
	
 
h) a função Implicação
	Z = A SYMBOL 174 \f "Symbol" B (A implica B)
	Considere o seguinte exemplo: usa-se a variável A para representar a afirmação: "Está chovendo", isto é, quando está chovendo A = V e quando não está, A = F. Usa-se B para representar a afirmação "As pessoas estão usando guarda-chuvas". Suponha que se deseje escrever uma equação lógica que diga que A implica B, ou seja, que a ocorrência da chuva implica o uso do guarda-chuva. Se introduzir-se a variável Z = A SYMBOL 174 \f "Symbol" B, Z será relacionada a A e B pela seguinte maneira: (Tabela Verdade)
	A | B | Z = A SYMBOL 174 \f "Symbol" B (a ocorrência de A leva a ocorrência de B)
	----------------------
	0 | 0 | 1
	0 | 1 | 1
	1 | 0 | 0
	1 | 1 | 1
	Se a situação com respeito a A e B for consistente com a idéia de que A implica B, então Z será verdadeira. A única possibilidade que não é consistente com a idéia de A implicar B é que A seja verdadeiro e B seja falso. Neste caso, B será falso.
Teoremas da Álgebra de Boole
	Variáveis Lógicas => só dois valores
	Sistema binário de numeração => só dois dígitos
	Para definir uma função:
Expressão lógica: Z = A SYMBOL 218 \f "Symbol" (B SYMBOL 217 \f "Symbol" C),
Tabela Verdade, ou
A função é definida como tendo valores 1 nas linhas 3,4,5,6 e 7 da coluna Z de uma tabela verdade de três variáveis.
	linha no. 	A B C Z
	0 		0 0 0 0
	1 		0 0 1 0
	2 		0 1 0 0
	3 		0 1 1 1
	4 		1 0 0 1
	5 		1 0 1 1
	6 		1 1 0 1
	7 		1 1 1 1
Propriedades das funções lógicas:
1) Comutatividade:
	Z = A SYMBOL 217 \f "Symbol" B = B SYMBOL 217 \f "Symbol" A 		AND
	Z = A SYMBOL 218 \f "Symbol" B = B SYMBOL 218 \f "Symbol" A 		OR
	Z = A SYMBOL 197 \f "Symbol" B = B SYMBOL 197 \f "Symbol" A 		XOR
2) Associatividade:
	Z = (A SYMBOL 217 \f "Symbol" B) SYMBOL 217 \f "Symbol" C = A SYMBOL 217 \f "Symbol" (B SYMBOL 217 \f "Symbol" C) 	AND
	Z = (A SYMBOL 218 \f "Symbol" B) SYMBOL 218 \f "Symbol" C = A SYMBOL 218 \f "Symbol" (B SYMBOL 218 \f "Symbol" C) 	OR
	Z = (A SYMBOL 197 \f "Symbol" B) SYMBOL 197 \f "Symbol" C = A SYMBOL 197 \f "Symbol" (B SYMBOL 197 \f "Symbol" C) 	XOR
3) Princípio da Dualidade
	Se trocarmos os sinais SYMBOL 218 \f "Symbol" (OR) e SYMBOL 217 \f "Symbol" (AND) entre si e trocarmos os 0s e 1s entre si, teremos substituído a equação original por outra igualmente válida.
	Ex.: 0 SYMBOL 217 \f "Symbol" 0 = 0 => 1 SYMBOL 218 \f "Symbol" 1 = 1
Teoremas:
(SYMBOL 216 \f "Symbol"A = A
A SYMBOL 218 \f "Symbol" 0 = A
A SYMBOL 218 \f "Symbol" 1 = 1
A SYMBOL 218 \f "Symbol" A = A
A SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"A = 1
A ( 1 = A
A ( 0 = 0
A ( A = A
A ( (A = 0
A SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" B) = A
A SYMBOL 217 \f "Symbol" (A SYMBOL 218 \f "Symbol" B) = A
(A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) = A
(A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (A SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"B) = A
A SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B) = A SYMBOL 218 \f "Symbol" B
A SYMBOL 217 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" B) = A SYMBOL 217 \f "Symbol" B
A SYMBOL 218 \f "Symbol" (B SYMBOL 217 \f "Symbol" C) = (A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (A SYMBOL 218 \f "Symbol" C)
A SYMBOL 217 \f "Symbol" (B SYMBOL 218 \f "Symbol" C) = (A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" C)
(A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" C) = (A SYMBOL 218 \f "Symbol" C) SYMBOL 217 \f "Symbol" ((A SYMBOL 218 \f "Symbol" B)
(A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" C) = (A SYMBOL 217 \f "Symbol" C) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B)
(A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" C) SYMBOL 218 \f "Symbol" (B SYMBOL 217 \f "Symbol" C) = (A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" C)
(A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" C) SYMBOL 217 \f "Symbol" (B SYMBOL 218 \f "Symbol" C) = (A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" C)
	A equação (17) indica que a álgebra de variáveis lógicas é distributiva:
	A SYMBOL 217 \f "Symbol" (B SYMBOL 218 \f "Symbol" C) = (A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" C)
	ou pode ser fatorado um fator comum:
	(A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f"Symbol" C) = A SYMBOL 217 \f "Symbol" (B SYMBOL 218 \f "Symbol" C)
 \ / |
	fator comum ----------
Exercício:Mostrar o Teorema 21 através da tabela-verdade.
Funções de Duas Variáveis
	Existem 16 funções de duas variáveis. As funções f0 e f15 não são funções de A e B. As funções f3, f5, f10 e f12 são funções de uma variável (f10 e f12 são funções NOT). A seguir a relação de todas as funções de duas variáveis, a partir da tabela verdade para duas variáveis (A e B). As funções são também expressas usando apenas as funções AND, OR e NOT (as expressões são demonstradas usando uma tabela verdade. Por exemplo, f6:
	A 	B 	SYMBOL 216 \f "Symbol"A 	SYMBOL 216 \f "Symbol"B 	SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B 	A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B 	(SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B)
 	0 	0 	1 	1 	 0 		 0 		0
 	0 	1 	1 	0 	 1 		 0 		1
 	1 	0 	0 	1 	 0 		 1 		1
 	1 	1 	0 	0 	 0 		 0 		0
	ou seja, (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) = A SYMBOL 197 \f "Symbol" B.
	As 16 funções:
	A 0 0 1 1
	B 0 1 0 1 	Função
	f0 0 0 0 0 f = 0
	f1 0 0 0 1 f = A SYMBOL 217 \f "Symbol" B (and)
	f2 0 0 1 0 f = SYMBOL 216 \f "Symbol"(A SYMBOL 174 \f "Symbol" B) = A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B
	f3 0 0 1 1 f = A
	f4 0 1 0 0 f = SYMBOL 216 \f "Symbol"(B SYMBOL 174 \f "Symbol" A) = SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B
	f5 0 1 0 1 f = B
	f6 0 1 1 0 f = A SYMBOL 197 \f "Symbol" B = (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B)
	f7 0 1 1 1 f = A SYMBOL 218 \f "Symbol" B (or)
	f8 1 0 0 0 f = SYMBOL 216 \f "Symbol"(A SYMBOL 218 \f "Symbol" B) (nor)
	f9 1 0 0 1 f = SYMBOL 216 \f "Symbol"(A SYMBOL 197 \f "Symbol" B) = (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" B)
	f10 1 0 1 0 f = SYMBOL 216 \f "Symbol"B
	f11 1 0 1 1 f = B SYMBOL 174 \f "Symbol" A = A SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"B
	f12 1 1 0 0 f = SYMBOL 216 \f "Symbol"A
	f13 1 1 0 1 f = A SYMBOL 174 \f "Symbol" B = SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" B
	f14 1 1 1 0 f = SYMBOL 216 \f "Symbol"(A SYMBOL 217 \f "Symbol" B) (nand)
	f15 1 1 1 1 f = 1
 Teoremas de De Morgan
(1) o complemento de um produto lógico (AND) de variáveis é igual a soma lógica (OR) dos complementos de cada variável.
	SYMBOL 216 \f "Symbol"(A SYMBOL 217 \f "Symbol" B SYMBOL 217 \f "Symbol" C SYMBOL 217 \f "Symbol" ...) = SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"B SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"C SYMBOL 218 \f "Symbol" ...
(2) o complemento de uma soma lógica (OR) de variáveis é igual ao produto lógico (AND) dos complementos de cada variável.
	SYMBOL 216 \f "Symbol"(A SYMBOL 218 \f "Symbol" B SYMBOL 218 \f "Symbol" C SYMBOL 218 \f "Symbol" ...) = SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"C SYMBOL 217 \f "Symbol" ...
(1) é dual a (2) => Princípio da Dualidade.
Exercício: Mostrar que f2 (A ( (B) é o complemento de f13 ((A ( B) através de De Morgan.
Diagramas de Venn
	O diagrama de Venn divide o espaço em regiões mutuamente exclusivas => útil para visualizar geometricamente os teoremas da álgebra boolena.
a) A SYMBOL 218 \f "Symbol" SYMBOL 216 \f "Symbol"A = 1 => o 1 representa o universo de interesse.
	
b) (A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) = 1
c) A SYMBOL 218 \f "Symbol" B = (A SYMBOL 217 \f "Symbol" SYMBOL 216 \f "Symbol"B) SYMBOL 218 \f "Symbol" (A SYMBOL 217 \f "Symbol" B) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B)
	
	Interseção : A SYMBOL 217 \f "Symbol" B
	União: A SYMBOL 218 \f "Symbol" B
	Os diagramas de Venn dividem o universo (o retângulo) em 2n áreas identificáveis diferentes, onde n é o número de variáveis.
	No esquema	a) 1 variável => 21 = 2 áreas
 		b) e c) 2 variáveis => 22 = 4 áreas
	Os diagramas de Venn são úteis quando se deseja a visualização geométrica de funções booleanas, podendo também ser usados para estabelecer ou verificar teoremas algébricos booleanos.
	d) Diagrama de Venn de 3 variáveis => 23 = 8 áreas
	
	Exercício.: Usar um diagrama de Venn para verificar o teorema da equação (19), isto é,
	(A SYMBOL 218 \f "Symbol" B) SYMBOL 217 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 218 \f "Symbol" C) = (A SYMBOL 217 \f "Symbol" C) SYMBOL 218 \f "Symbol" (SYMBOL 216 \f "Symbol"A SYMBOL 217 \f "Symbol" B)
Exercício: Mostrar o Teorema 18 através de diagramas de Venn.
Exemplos de aplicação dos teoremas da Álgebra de Boole
	Uma operação lógica que une duas variáveis lógicas, como a função AND, etc., é muitas vezes denominada de conetivo. Funções de mais de duas variáveis são formadas pela aplicação repetida destes conetivos de duas variáveis.
	Os teoremas booleanos servem para simplificar expressões algébricas:
Ex. 1: Simplificar w = xy + SYMBOL 216 \f "Symbol"(yx)z
	w = xy + SYMBOL 216 \f "Symbol"(xy)z 		pois AB = BA (comutatividade)
	Se v = xy => w = v + SYMBOL 216 \f "Symbol"vz 	pois a função de variáveis lógicas é uma variável lógica.
	w = v + z 		pois A + SYMBOL 216 \f "Symbol"AB = A + B (teo. 14)
	w = xy + z
Ex. 2: Simplificar w = x (SYMBOL 216 \f "Symbol"x + y)
	w = x (SYMBOL 216 \f "Symbol"x + y) = xy 	A (SYMBOL 216 \f "Symbol"A + B) = AB (teo. 15)
ou
	w = x (SYMBOL 216 \f "Symbol"x + y) = xSYMBOL 216 \f "Symbol"x + xy 	A (B + C) = AB + AC
 		 = 0 + xy 	ASYMBOL 216 \f "Symbol"A = 0
 		 = xy 	A + 0 = A
Ex. 3: Simplificar w = SYMBOL 216 \f "Symbol"x ( x + y) + SYMBOL 216 \f "Symbol"z + zy
	w = SYMBOL 216 \f "Symbol"x(x+y)+SYMBOL 216 \f "Symbol"z+zy = SYMBOL 216 \f "Symbol"x(x+y)+SYMBOL 216 \f "Symbol"z+y 	A + SYMBOL 216 \f "Symbol"AB = A + B (SYMBOL 216 \f "Symbol"A = z)
	w = xSYMBOL 216 \f "Symbol"x+SYMBOL 216 \f "Symbol"xy+SYMBOL 216 \f "Symbol"z+y = SYMBOL 216 \f "Symbol"xy+SYMBOL 216 \f "Symbol"z+y 	A(B+C) = AB+AC e SYMBOL 216 \f "Symbol"AA=ASYMBOL 216 \f "Symbol"A=0
	w = y+SYMBOL 216 \f "Symbol"xy+SYMBOL 216 \f "Symbol"z = y+ySYMBOL 216 \f "Symbol"x+SYMBOL 216 \f "Symbol"z 		A+B = B+A; AB = BA
	w = y + SYMBOL 216 \f "Symbol"z 			A + AB = A
	Exemplos da aplicação dos teoremas de De Morgan:
Ex. 4: Simplificar v = SYMBOL 216 \f "Symbol"(w + wSYMBOL 216 \f "Symbol"x + yz)
	v = SYMBOL 216 \f "Symbol"(w+wSYMBOL 216 \f "Symbol"x+yz) = SYMBOL 216 \f "Symbol"w . SYMBOL 216 \f "Symbol"(wSYMBOL 216 \f "Symbol"x) . SYMBOL 216 \f "Symbol"(yz) 	Teo. de De Morgan
	v = SYMBOL 216 \f "Symbol"w (SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"��SYMBOL 216 \f "Symbol"x)(SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"z)Teo. de De Morgan
	v = SYMBOL 216 \f "Symbol"w (SYMBOL 216 \f "Symbol"w + x)(SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"z) 			SYMBOL 216 \f "Symbol"��SYMBOL 216 \f "Symbol"A = A
	v = SYMBOL 216 \f "Symbol"w (SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"z) 			A(A+B) = A, A = SYMBOL 216 \f "Symbol"w
ou:
	v = SYMBOL 216 \f "Symbol"(w + wSYMBOL 216 \f "Symbol"x + yz) = SYMBOL 216 \f "Symbol"(w + yz) 		A + AB = A
	v = SYMBOL 216 \f "Symbol"(w + yz) = SYMBOL 216 \f "Symbol"w . SYMBOL 216 \f "Symbol"(yz) 		 Teo. de De Morgan
	v = SYMBOL 216 \f "Symbol"w (SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"z) 			Teo. de De Morgan
Ex. 5: Simplificar v = SYMBOL 216 \f "Symbol"{w [(x+y(z+SYMBOL 216 \f "Symbol"w))]}
	v = SYMBOL 216 \f "Symbol"{w [(x+y(z+SYMBOL 216 \f "Symbol"w))]} = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"[x + y(z+SYMBOL 216 \f "Symbol"w)] 	De Morgan
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x . SYMBOL 216 \f "Symbol"[y(z + SYMBOL 216 \f "Symbol"w)] 		De Morgan
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x [SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"(z + SYMBOL 216 \f "Symbol"w)] 		De Morgan
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x (SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"zw) 		De Morgan e SYMBOL 216 \f "Symbol"��SYMBOL 216 \f "Symbol"A = A
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"z.w 		A (B + C) = AB + BC
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"z 			A + SYMBOL 216 \f "Symbol"AB = A + B (A = SYMBOL 216 \f "Symbol"w)
	v = SYMBOL 216 \f "Symbol"w + SYMBOL 216 \f "Symbol"x(SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"z) 			AB + AC = A (B + C)
	Os exemplos seguintes ilustram o uso dos teoremas (20) e (21):
Ex. 6: Simplificar v = wx + xSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z
	v = wx + xSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z + xy 			Teo. (20)
	v = wx + x(SYMBOL 216 \f "Symbol"y + y) + yz + xSYMBOL 216 \f "Symbol"z 			AB + AC = A(B + C)
	v = wx + x + yz + xSYMBOL 216 \f "Symbol"z 			SYMBOL 216 \f "Symbol"A + A = 1 e A . 1 = A
	v = x + yz + xSYMBOL 216 \f "Symbol"z 				A + AB = A
	v = x + yz 				A + AB = A
Ex. 7: Simplificar v = (w + x + y)(w + SYMBOL 216 \f "Symbol"x + y)(SYMBOL 216 \f "Symbol"y + z)(w + z)
	v = (w + y)(SYMBOL 216 \f "Symbol"y + z)(w + z) 			(A+B)(A+SYMBOL 216 \f "Symbol"B) = A
								A = w + y, B = x
	v = (w + y)(SYMBOL 216 \f "Symbol"y + z) 				Teo. (21)
Exemplos adicionais
	Como foi visto, afirmações e condições relativamente complexas podem ser expressas sob a forma de expressões algébricas booleanas. A partir daí usamos os teoremas da álgebra booleana para encontrar expressões mais simples e equivalentes, ilustrando assim, como o conceito de variável lógica e sua álgebra associada é usado para executar um processo de raciocínio lógico.
Ex. 1: Uma estudante consulta o catálogo da universidade e fica sabendo que pode se matricular em determinada disciplina somente se ela satisfizer uma das seguintes condições:
Já completou sessenta créditos e é uma estudante de Análise de Sistemas regularmente matriculada;
Completou sessenta créditos e é uma estudante de Análise e tem o consentimento do CEATEC ;
Completou menos de sessenta créditos e é uma estudante de Análise com matrícula especial;
É uma estudante regularmente matriculada e tem o consentimento do CEATEC;
É uma estudante de Análise e não tem o consentimento do CEATEC.
Encontre uma expressão mais simples que indique a possibilidade de a estudante matricular-se na disciplina.
SOLUÇÃO: Introduzimos as variáveis w, x, y, z e v para representar as seguintes situações:
w = a estudante completou sessenta créditos;
x = a estudante é aluna de Análise de Sistemas;
y = a estudante tem matrícula regular;
z = a estudante tem o consentimento do CEATEC;
v = a estudante pode se matricular na disciplina.
	Ou seja, se y = V ou y = 1 => a estudante tem matrícula regular, ou se y = F ou y = 0 => a estudante tem matrícula especial. Quando as variáveis w, x, y e z assumem valores tais que v = verdadeiro, a estudante pode se matricular. A especificação de quando isto ocorre pode ser feita pela equação algébrica lógica:
	v = wxy + wxz + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z
	A simplificação, usando os teoremas de álgebra booleana:
	v = wxy + wxz + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z
	v = wxy + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + x(SYMBOL 216 \f "Symbol"z + zw)
	v = wxy + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + x(SYMBOL 216 \f "Symbol"z + w)
	v = wxy + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z + xw
	v = wx(y + 1) + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z 
	v = wx + SYMBOL 216 \f "Symbol"wxSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z 
	v = x(w + SYMBOL 216 \f "Symbol"w.SYMBOL 216 \f "Symbol"y) + yz + xSYMBOL 216 \f "Symbol"z 
	v = x(w + SYMBOL 216 \f "Symbol"y) + yz + xSYMBOL 216 \f "Symbol"z 
	v = xw + xSYMBOL 216 \f "Symbol"y + yz + xSYMBOL 216 \f "Symbol"z 
	A expressão é idêntica à do exemplo 6 do sub-ítem anterior, portanto:
	v = x + yz
	Assim, a estudante poderá se matricular na disciplina (v = 1) se for uma aluna de Análise (x = 1) ou se simultaneamente tiver matrícula regular (y = 1) e consentimento do Instituto (z = 1).
Ex. 2: Há cinco livros v, w, x, y e z, numa prateleira. Você deve selecionar alguns entre eles de modo a satisfazer todas as condições a seguir:
1. Selecionar v ou w ou ambos;
2. Selecionar x ou z ou não ambos;
3. Selecionar v e z juntos ou nenhum dos dois;
4. Se selecionar y também deve selecionar z;
5. Se selecionar w também deve selecionar v e y.
SOLUÇÃO: A expressão que satisfaz todas as condições é dada por u:
	u = (v + w)(x SYMBOL 197 \f "Symbol" z)SYMBOL 216 \f "Symbol"(v SYMBOL 197 \f "Symbol" z)(y SYMBOL 174 \f "Symbol" z)(w SYMBOL 174 \f "Symbol" vy)
Transformando nas expressões equivalentes usando somente as funções AND, OR e NOT:
	u = (v + w)(xSYMBOL 216 \f "Symbol"z + SYMBOL 216 \f "Symbol"xz)(vz + SYMBOL 216 \f "Symbol"v.SYMBOL 216 \f "Symbol"z)(SYMBOL 216 \f "Symbol"y + z)(SYMBOL 216 \f "Symbol"w + vy)
	u = (vz + SYMBOL 216 \f "Symbol"vwSYMBOL 216 \f "Symbol"z)(xSYMBOL 216 \f "Symbol"z + SYMBOL 216 \f "Symbol"xz)(SYMBOL 216 \f "Symbol"y + z)(SYMBOL 216 \f "Symbol"w + vy)
	u = (vSYMBOL 216 \f "Symbol"wz + vyz)(xSYMBOL 216 \f "Symbol"y.SYMBOL 216 \f "Symbol"z + SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"yz + SYMBOL 216 \f "Symbol"xz)
	u = vSYMBOL 216 \f "Symbol"w.SYMBOL 216 \f "Symbol"x.SYMBOL 216 \f "Symbol"yz + vSYMBOL 216 \f "Symbol"w.SYMBOL 216 \f "Symbol"xz + vSYMBOL 216 \f "Symbol"xyz
	u = vSYMBOL 216 \f "Symbol"xz (SYMBOL 216 \f "Symbol"w.SYMBOL 216 \f "Symbol"y + SYMBOL 216 \f "Symbol"w + y)
	u = vSYMBOL 216 \f "Symbol"xz (SYMBOL 216 \f "Symbol"w + y)
	Devemos selecionar v e z e rejeitar x e, ao mesmo tempo, se rejeitarmos w, não importa se selecionamos ou rejeitamos y.
Diagramas de Circuitos Lógicos
	Existe uma correspondência entre uma expressão lógica e um diagrama de portas lógicas. Por exemplo considere a expressão simplificada do exemplo anterior:
	u = vSYMBOL 216 \f "Symbol"xz(SYMBOL 216 \f "Symbol"w + y)Agora como ficaria a implementação em circuitos lógicos da expressão original, sem a simplificação ?
	u = (v + w)(xSYMBOL 216 \f "Symbol"z + SYMBOL 216 \f "Symbol"xz)(vz + SYMBOL 216 \f "Symbol"v.SYMBOL 216 \f "Symbol"z)(SYMBOL 216 \f "Symbol"y + z)(SYMBOL 216 \f "Symbol"w + vy)
	A simplificação de expressões lógicas, como acabou-se de ver, leva a uma implementação física, através de circuitos lógicos, bem mais econômica (no exemplo acima foram economizadas oito portas lógicas, sem contar os inversores).
Simplificação de Circuitos Lógicos: Mapeamento
	Consideremos a expressão booleana Z = A.SYMBOL 216 \f "Symbol"B + SYMBOL 216 \f "Symbol"A.B + A.B. Um diagrama lógico dessa expressão (figura 6.1 a) e da expressão simplificada (figura 6.1 b) a seguir:
(a) circuito lógico não simplificado
	
(b) circuito lógico simplificado
	
(c) tabela verdade
	A | B | Z
 -----------------
 	 0 | 0 | 0
 	 0 | 1 | 1
 	 1 | 0 | 1
 	 1 | 1 | 1
	Figura 6.1
	Notar que devem ser usadas seis portas, contando os inversores, para implementar esse circuito lógico, que executa a lógica detalhada na tabela verdade acima (figura 6.1c). Do exame da tabela verdade, e determinado que uma única porta OR de 2 entradas executará a função. Verifica-se que a porta OR mostrada acima (figura 6.1b) será o método mais simples de executar esta lógica. Os circuitos lógicos das figuras (6.1a) e (6.1b) executam exatamente a mesma função lógica. Obviamente um projetista escolheria o circuito mais simples, e menos dispendioso, mostrada na figura (6.1b). A simplificação obtida foi feita pelo simples exame da tabela verdade e pelo reconhecimento do padrão OR. Porém, existem métodos sistemáticos de simplificação, além dos já vistos, e de obtenção da expressão algébrica de uma função lógica através da tabela verdade.
Expressões booleanas de soma-de-produtos
	Considere a seguinte tabela verdade (figura 6.2a) de três variáveis (A, B e C). Observe que só duas combinações de variáveis irão gerar uma saída 1. Estas combinações são mostradas nas quinta e oitava linhas da tabela verdade:
(a)	A	B	C	|	Z
	--------------------------------------
	0	0	0	|	0
	0	0	1	|	0
	0	1	0	|	0
	0	1	1	|	0
	1	0	0	|	1	SYMBOL 222 \f "Symbol" A.SYMBOL 216 \f "Symbol"B.SYMBOL 216 \f "Symbol"C
	1	0	1	|	0
	1	1	0	|	0
	1	1	1	|	1	SYMBOL 222 \f "Symbol" A.B.C
(b) Expressão booleana:
	Z = A. SYMBOL 216 \f "Symbol"B. SYMBOL 216 \f "Symbol"C + A.B.C
(c) Circuito lógico AND-OR
	
Figura 6.2
	Da quinta linha, dizemos que uma entrada "um A E um não B E um não C irá gerar uma saída 1". Isto é mostrado do lado da linha, como a expressão booleana A.SYMBOL 216 \f "Symbol"B.SYMBOL 216 \f "Symbol"C. A outra combinação de variáveis que irá gerar uma saída 1 é mostrada na oitava linha. Nessa linha se lê que "um A E um B E um C irá gerar uma saída 1". A expressão booleana equivalente é mostrada do lado da linha como A.B.C. Estas duas combinações possíveis são depois submetidas juntas a uma operação OR para formar a expressão booleana completa da tabela verdade. A expressão completa é mostrada na figura 6.2b. Esta expressão é chamada de soma-de-produtos de uma expressão booleana. É conhecida também como forma de termos mínimos. O diagrama lógico da figura 6.2c executa a lógica desta função.
Expressões booleanas de produto-de-somas
	Considere a tabela verdade OR da figura 6.3b. A expressão booleana desta tabela verdade pode ser escrita de duas formas. A primeira é a expressão de soma-de-produtos a partir dos 1s de saída da tabela verdade, como já visto no item anterior. Cada 1 na coluna de saída torna-se um termo a ser submetido a uma operação OR na expressão de termos mínimos. A expressão de termos mínimos para a tabela verdade é mostrada na figura 6.3c como Z = SYMBOL 216 \f "Symbol"A.B + A.SYMBOL 216 \f "Symbol"B + A.B.
	A segunda forma de se obter a expressão lógica é a forma de termos máximos ou produto-de-somas. Este tipo de expressão é desenvolvida a partir dos 0s na coluna de saída da tabela verdade. Para cada 0 na coluna de saída, é desenvolvido um termo submetido a uma operação OR. Notar que a variáveis de entrada são invertidas e depois submetidas a uma operação OR. A expressão de termos máximos para a tabela verdade OR é mostrada na figura 6.3a. A expressão de termos máximos para a tabela verdade OR é mostrada como Z = A + B. Para a tabela verdade da figura 6.3, a expressão booleana de termos máximos revela-se a mais simples. Tanto as expressões de termos mínimos quanto as de termos máximos descrevem a lógica da tabela verdade na fig. 6.3.
	(a) Expressão booleana de termos máximos: Z = A + B
	(b) Tabela verdade OR
		A	B	|	Z
	 ------------------------------------
		0	0	|	0	SYMBOL 222 \f "Symbol" Inverte as variáveis SYMBOL 222 \f "Symbol" A + B
		0	1	|	1	SYMBOL 222 \f "Symbol" SYMBOL 216 \f "Symbol"A .B
		1	0	|	1	SYMBOL 222 \f "Symbol" A. SYMBOL 216 \f "Symbol"B
		1	1	|	1	SYMBOL 222 \f "Symbol" A. B
	(c) Expressão boolena de termos mínimos: Z = SYMBOL 216 \f "Symbol"A.B + A.SYMBOL 216 \f "Symbol"B + A.B
Figura 6.3
�PAGE �
�PAGE �71�
_1174735581/o�_	�
_1174735615/ö+7��
_1174735584/¾�þ	�
_1174735574/È�_	�
_946449926.bin
_915888402/Ñ�Ñ
�
_917265070/ø ½��