2015 2 álgebra de proposições

Prévia do material em texto

3. Álgebra de Proposições (Álgebra Booleana) 
 
PROBLEMA: “FAZER A MÁQUINA PENSAR!” 
 
O que é uma Proposição? 
 
Proposição: É uma sentença declarativa, seja ela expressa de forma afirmativa ou negativa, na 
qual podemos atribuir um valor “V” (verdadeiro) ou “F”(falso). Uma proposição também pode ser 
expressa por símbolos. 
Princípios que regem as Proposições: 
1. Princípio da Identidade: Uma proposição Verdadeira é Verdadeira, e uma proposição Falsa 
é Falsa 
2. Princípio do Terceiro Excluído: Uma proposição ou é verdadeira ou falsa não existindo 
uma terceira possibilidade. 
3. Princípio da Não-Contradição: Uma proposição não pode ser verdadeira e falsa 
simultaneamente. 
Fonte: http://www.infoescola.com/matematica/logica-proposicional/ , por Thiago Trigo 
 
Algumas características do pensamento humano: 
 
- Complexidade 
- Quantidade de símbolos reconhecidos e processados 
- Capacidade de adaptação (aprendizado) 
- Uso de vários modelos de raciocínio lógico 
 
Proposta de modelagem do raciocínio humano: 
 
TESE + ANTÍTESE � SÍNTESE 
 
Tese: Ana somou os valores 
Antítese: Quem soma sabe matemática 
Síntese: Ana sabe matemática 
 
Tese: Errar é humano 
Antítese: A cobra errou o bote 
Síntese: A cobra é humana 
 
Algumas limitações dos computadores: 
 
- incapacidade de reconhecer muitos símbolos, reconhece apenas a presença ou não de energia 
- necessidade de codificar as informações 
- incapacidade de adaptação 
 
Visão simplificada da Teoria de Boole (1850 – Geroge Boole) 
 
- Boole combinou análise matemática e teorias do pensamento criando a Álgebra de Proposições. 
- Proposta da teoria: qualquer coisa (números, letras ou objetos) poderia ser representada por um 
conjunto de símbolos e regras. 
- Introdução do conceito de códigos binários (sim/n/ao, certo/errado, falso/verdadeiro, etc.) 
- Teoria da Informação (1948) – através da codificação binária e da álgebra de proposições os 
computadores passaram a reconhecer e processar as informações (dados). 
 
Álgebra de Proposições (ou Álgebra Booleana) 
 
Principais características: 
 
- Uma proposição pode ser apenas verdadeira ou falsa 
- As proposições podem ser combinadas através do uso e operadores lógicos 
 
Operadores Lógicos 
NÂO (representação:  ) 
E (representação: ∧ ) 
 OU (representação: ∨ ) 
 
Valores Lógicos 
 Verdadeiro ( 1 ) 
 Falso ( 0 ) 
 
Operações Lógicas 
 
 
Operador E Operador OU Operador NÂO 
 
 
0 ٨ 0 = 0 
 
0 ٧ 0 = 0 
 
ȏ 0 = 1 
 
 
0 ٨ 1 = 0 
 
1 ٧ 0 = 1 
 
ȏ 1 = 0 
 
 
1 ٨ 0 = 0 
 
0 ٧ 1 = 1 
 
 
1 ٨ 1 = 1 
 
1 ٧ 1 = 1 
 
 
Prioridade de Operações 
 1° - ȏ (NÂO) 
 2° - ٨ (E) 
 3° - ٧ (OU) 
 
Portas Lógicas 
 
Portas lógicas são dispositivos eletrônicos capazes de implementarem as operações lógicas, que 
operam um ou mais sinais lógicos de entrada para produzir uma e somente uma saída. 
 
- Representação gráfica de algumas portas lógicas: 
 
 
 
 
 
 
 
Equações Lógicas 
 
As equações lógicas são expressões similares as equações matemáticas, a diferença é que as 
variáveis assumem valores lógicos (0 ou 1). A seguir vemos alguns exemplos de soluções de 
equações lógicas. 
 
A = B ٨ C ٧ D 
 
Assim com nas equações matemáticas iremos atribuir valores às variáveis B, C e D e encontrar o 
NÃO E OU 
valor de A. Lembre-se que temos diferentes prioridades para as operações. Vamos resolver a 
equação, a princípio, para os valores B = 0, C = 0 e D = 0: 
 
Temos então: 
 
A = 0 ٨ 0 ٧ 0 
A = 0 ٧ 0 
A = 0 
 
Note que A = 0 para B = 0, C = 0 e D = 0. Observe também que iremos indicar sempre qual 
operação está sendo resolvida a cada linha da solução. 
 
Usualmente, ao resolver uma equação lógica, construímos o que chamamos de tabela verdade. 
Esta tabela apresenta todas as soluções possíveis para a equação. No caso do exemplo acima 
teremos então: 
 
A = B ٨ C ٧ D B C D 
0 0 0 0 
1 0 0 1 
0 0 1 0 
1 0 1 1 
0 1 0 0 
1 1 0 1 
1 1 1 0 
1 1 1 1 
 
Em nossos exercícios com as operações lógicas não iremos construir tabelas verdades, apenas 
iremos encontrar uma das soluções para a equação lógica conforme o exemplo a seguir. 
 
Resolver a equação lógica para os valores B = 1, C = 0 e D = 1: 
A = ȏ ( C ٨ B ٨ ȏ C ٧ D ٧ ( C ٧ B ٨ D ) ) 
A = ȏ ( 0 ٨ 1 ٨ ȏ 0 ٧ 1 ٧ ( 0 ٧ 1 ٨ 1 ) ) 
A = ȏ ( 0 ٨ 1 ٨ ȏ 0 ٧ 1 ٧ ( 0 ٧ 1 ) ) 
A = ȏ ( 0 ٨ 1 ٨ ȏ 0 ٧ 1 ٧ 1 ) 
A = ȏ ( 0 ٨ 1 ٨ 1 ٧ 1 ٧ 1 ) 
A = ȏ ( 0 ٧ 1 ٧ 1 ) 
A = ȏ 1 
 
A = 0 
 
 
Observe que para a solução da equação lógica apresentada forma observadas as regras relativas 
à prioridade entre as operações lógicas, ao uso de parênteses e ainda foram indicadas as 
operações resolvidas a cada passo. Esta indicação é necessária para que nos acostumarmos a 
seguir o “caminho lógico” para a solução do problema. 
 
Outra possibilidade de solução para a mesma equação é resultado de uma análise cuidadosa da 
mesma antes de iniciarmos a resolução. Se observarmos a prioridade das operações, iremos 
verificar que, sem desrespeitar as regras, poderemos resolver algumas operações 
simultaneamente, veja a seguir esta outra solução: 
 
A = ȏ ( C ٨ B ٨ ȏ C ٧ D ٧ ( C ٧ B ٨ D ) ) 
A = ȏ ( 0 ٨ 1 ٨ ȏ 0 ٧ 1 ٧ ( 0 ٧ 1 ٨ 1 ) ) 
A = ȏ ( 0 ٨ 1 ٧ 1 ٧ ( 0 ٧ 1 ) ) 
A = ȏ ( 0 ٧ 1 ٧ 1 ) 
A = ȏ 1 
 
A = 0 
 
Como pode ser observado, a solução fica mais “curta”. Um aspecto importante a se destacar é o 
fato de isto só é possível em função da análise do problema antes de começar a resolver cada 
linha, o que é resultado do desenvolvimento do raciocínio lógico. 
 
Somador Parcial Binário 
 
Com exemplo da aplicação das portas lógicas para fazer o computador pensar é apresentado a 
seguir um circuito lógico simples chamado de “somador parcial binário”. Este circuito é capas de 
realizar a operação de soma entre dois números binários de um dígito. 
 
 
 
 
 
Observe que as operações lógicas realizadas em cada porta podem ser agrupadas gerando, ao 
final, equações lógicas. 
 
 
- Exercícios Propostos: 
1) P = ȏ ( A ٧ B ٨ ȏ C ٨ D ٧ ( A ٨ B ٧ C ) ) 
para A = 1, B = 1, C = 0 e D = 0 
2) Q = A ٧ B ٨ ( ȏ C ٨ D ٨ ( A ٧ B ٨ ( C ٨ ȏ P ) ) ) 
para A = 1, B = 1, C = 0, D = 0 e P (encontrado no exercíco 1) 
3) R = ( A ٧ C ٨ ȏ ( B ٧ C ) ) ٨ A ٧ ( P ٨ Q ) 
 
para A = 1, B = 1, C = 0, D = 0, P e Q (encontrados nos exercícios 1 e 2) 
 
4) S = ȏ ( A ٨ B ٧ ȏ C ٨ D ) ٨ ( P ٧ Q ٨ R ) ) 
 
para A = 1, B = 1, C = 0, D = 0, P, Q e R (encontrados nos exercícios 1, 2 e 3) 
 
 
- Exercícios extras: 
 
Resolver as equações lógicas a seguir para os valores dados 
 
1) P = A ∨ B ∧  ( B ∧ C ∨  ( C ∨  A ∧ D ) ) para A = 0, B = 0, C = 0 e D = 0 
 
2) Q =  (D ∨ C ∧  B ∨ ( C ∧ A ∧ B ∨  C ) ) para A = 1, B = 0, C = 0 e D = 1 
 
3) R =  ( A ∨ B ∧ ( C ∨ D ) ) ∧ ( B ∨  C ∧ D ) para A = 0, B = 0, C = 0 e D = 0 
 
4) S = A ∨ B ∧ ( C ∨  D ∧ A ∧ ( B ∨ C)) para A = 1, B = 0, C = 0 e D = 1 
 
5) T = (A ∨ ( B ∧  C ) ∧ B ∧  D ) ∧ C ∨ D para A = 0, B = 1, C = 1 e D = 0 
 
6) U = ( A ∨  ( B ∧ C ) ∨ C ∧  D ) ∨ ( A ∧ C) para A = 1, B = 0, C = 1 e D = 0 
 
7) X =  ( A ∧ B ∨ ( C ∨ D ) ) ∨ ( B ∨  C ∧ D ) para A = 0, B = 0, C = 0 e D = 0 
 
8) Y = A ∧ B ∨ ( C ∨  D ∨ A ∧ ( B ∨ C)) para A = 1, B = 0, C = 0 e D = 1 
 
9) W = (A ∨ ( B ∧  C ) ∧ B ∨  D ) ∧ C ∨ D para A = 0, B = 1, C = 1 e D = 0 
 
10) Z = ( A ∨  ( B ∧ C ) ∨ C ∨  D ) ∧ A ∧ C para A = 1, B = 0, C = 1 e D = 0