INTRODUÇÃO AOS SISTEMAS LÓGICOS

INTRODUÇÃO AOS

SISTEMAS LÓGICOS

SISTEMAS LÓGICOS

PROF. ANDRÉ MONTEVECCHI

PROFA. ANNA TOSTES

24/10/2011

Prof. André Montevecchi / Profa. Anna Tostes 1

SUMÁRIO

• Àlgebra de Proposições

• Operadores Lógicos

• Expressões e Equações Lógicas

• Circuito Lógico

• Propriedades da Álgebra Booleana

• Simplificação de Expressões Lógicas

24/10/2011

Prof. André Montevecchi / Profa. Anna Tostes

2

ÁLGEBRA DE PROPOSIÇÕES

Proposição é o enunciado de uma verdade que se

quer demonstrar

Toda proposição é uma frase mas nem toda frase é

uma proposição

ÁLGEBRA DE BOOLE

Proposta por George Boole em 1854

Álgebra ordinária dos reais:

• Variáveis podem assumir valores no intervalo

(-∞;+∞)

Álgebra de Boole:

• Variáveis booleanas só podem assumir um

número finito de valores (dois, verdadeiro ou

falso)

ÁLGEBRA DE BOOLE

É conhecida por álgebra de proposições

Uma frase é uma proposição apenas quando

admite um dos dois valores lógicos:

• Falso (0)

• Verdadeiro (1)

• Mas nunca ambas ao mesmo tempo

ÁLGEBRA DE PROPOSIÇÕES

Frases que não são proposições

• Pare!

• Quer uma xícara de café?

• Eu não estou bem certo se esta cor me

agrada

ÁLGEBRA DE PROPOSIÇÕES

Frases que são proposições

• A lua é o único satélite do planeta terra (Verdadeiro)

• A cidade de Salvador é a capital do estado do Amazonas (Falso)

• O numero 712 é ímpar (Falso)

• Raiz quadrada de dois é um número irracional (Verdadeiro)

• 10 > 23 (Verdadeiro)

OPERADORES LÓGICOS

Construir novas proposições a partir de

proposições já existentes

Principais operadores lógicos:

• Conjunção

• Disjunção

• Negação

CONJUNÇÃO

Considere duas proposições (p e q)

Se p e q forem verdadeiras (1)

• Então a conjunção de ambas será

verdadeira (1)

Se uma das duas for falsa (0)

• Então a conjunção (s) também será falsa

(0)

CONJUNÇÃO

Intervalo fechado de 1 a 5:

1 ≤ x ≤ 5

= 1 ≤ x E x ≤ 5

1 5

CONJUNÇÃO

P Q P AND Q

Falso Falso Falso

Falso Verdadeiro Falso

Verdadeiro Falso Falso

Verdadeiro Verdadeiro Verdadeiro

CONJUNÇÃO

P Q P AND Q

0 0 0

0 1 0

1 0 0

1 1 1

CONJUNÇÃO

Notação: X • Y = X e Y

A porta AND ( E ) implementa essa relação

• Pode ter duas (p, q) ou mais entradas

• A saída (s) assumirá o valor

• 1 se, e somente se, todas as entradas

forem iguais a 1

• Caso uma, ou mais entradas sejam

iguais a 0, a saída terá valor 0

CONJUNÇÃO

A porta AND ( E ):

CONJUNÇÃO

CONJUNÇÃO

CONJUNÇÃO

CONJUNÇÃO

DISJUNÇÃO

Considere duas proposições (p e q)

Se p e q forem falsas (0)

• Então a disjunção de ambas (s) será falsa

Se uma delas for verdadeira (1)

• Então a disjunção também será

DISJUNÇÃO

Intervalo aberto: menor que 1 e maior que 5

1 > x > 5

= 1 > x OU x > 5

1 5

DISJUNÇÃO

P Q P AND Q

Falso Falso Falso

Falso Verdadeiro Verdadeiro

Verdadeiro Falso Verdadeiro

Verdadeiro Verdadeiro Verdadeiro

DISJUNÇÃO

P Q P AND Q

0 0 0

0 1 1

1 0 1

1 1 1

DISJUNÇÃO

Notação: X + Y = X ou Y

A porta OR ( OU ) implementa essa relação

• Pode ter duas (p, q) ou mais entradas

• A saída (s) assumirá o valor

• 0 se, e somente se, todas as entradas

forem iguais a 0

• Caso uma, ou mais entradas forem

iguais a 1, a saída terá valor 1

DISJUNÇÃO

A porta OR ( OU ):

DISJUNÇÃO

DISJUNÇÃO

DISJUNÇÃO

DISJUNÇÃO

NEGAÇÃO

Considere uma proposição p

Se p for falsa (0)

• Então a negação será verdadeira (1) Se p for verdadeira (1)

• Então a negação será falsa (0)

Também chamada de complementação ou inversão

P Q

Falso Verdadeiro

Verdadeiro Falso

NEGAÇÃO

NEGAÇÃO

P Q

0 1

1 0

NEGAÇÃO

Notação: x’ = não (x)

A porta NOT (NÃO) implementa essa relação

• Também é chamada de INVERTER

(INVERSOR)

• Só tem uma entrada (p)

• A saída assumirá o valor

• 1, se a entrada for igual a 0

• 0, se a entrada for igual a 1

NEGAÇÃO

A porta NOT (NÃO):

NEGAÇÃO

NEGAÇÃO

EXPRESSÕES LÓGICAS

Feita com a combinação dos operadores lógicos

AND, OR, NOT

Exemplo: suponha x, y, z variáveis lógicas

x’ + y z

z + (x + y)’

(x y’)’ + z

EXPRESSÕES LÓGICAS

Prioridade de Conectivos

• A ordem de avaliação de uma expressão,

envolvendo conectivos lógicos, será da

esquerda para a direita

• Deve-se respeitar as prioridades dos

conectivos, sendo a primeira a mais alta: • (1) NÃO, (2) E, (3) OU

• Pode-se mudar a ordem de avaliação por

meio de parênteses

EXPRESSÕES LÓGICAS

Prioridade de Conectivos

• Considere a expressão:

x + y' • z

• A sua avaliação será feita na seguinte

ordem de prioridade: • Negação de (y): y’

• Conjunção com (z): y' • z

• Disjunção com (x): (y' • z) + x

EXPRESSÕES LÓGICAS

Para verificar o resultado da expressão, pode-se

criar a tabela-verdade

O resultado final depende dos valores de entrada

das variáveis lógicas

EXPRESSÕES LÓGICAS

TABELA-VERDADE

• O procedimento para a criação da tabela

verdade a partir de uma equação Booleana

é: 1. Criar colunas para as variáveis de entrada e listar todas as

combinações possíveis, utilizando a fórmula no de

combinações = 2n (n é o número de variáveis de entrada)

2. Criar uma coluna para cada variável de entrada que

apareça complementada na equação e anotar os valores

resultantes

3. Avaliar a equação seguindo a ordem de precedência, a

partir do nível de parêntesis mais internos

EXPRESSÕES

LÓGICAS

• EXEMPLO: TABELA VERDADE DE Y + Z + X’

x y z y + z x' y + z + x’

0 0 0 0 1 1

0 0 1 1 1 1

0 1 0 1 1 1

0 1 1 1 1 1

1 0 0 0 0 0

1 0 1 1 0 1

1 1 0 1 0 1

1 1 1 1 0 1

EXPRESSÕES LÓGICAS

Qual seria a tabela-verdade para as expressões

abaixo:

① x + y' • z

② z + (x + y)’

③ (x y’)’ + z

EXPRESSÕES LÓGICAS

Tabela-verdade: (y’ • z) + x

EQUAÇÕES LÓGICAS OU

BOOLEANA

Quando atribuímos uma expressão lógica a uma

variável lógica, temos uma equação lógica

(booleana)

Exemplo:

• S = X + (Y’ Z) X

CIRCUITO LÓGICO

Conjunto de portas lógicas e respectivas conexões

que simbolizam uma equação booleana

São formados pelas portas lógicas já apresentadas

• Existem outras portas lógicas além de AND,

OR e NOT que serão vistas mais para

frente • Exemplo: NOR, NAND, XOR, XNOR

CIRCUITO LÓGICO

NOT

AND

OR

CIRCUITO LÓGICO

Nos circuitos lógicos do computador, os sinais

binários são representados por níveis de tensão

• É utilizada a álgebra de boole

É considerado como uma caixa preta

• O conteúdo implementa um tipo de porta ou

uma combinação das mesmas

CIRCUITO LÓGICO

CAIXA PRETA

CIRCUITO LÓGICO

CIRCUITO LÓGICO

1

1

0 = 1

0

0

CIRCUITO LÓGICO

1

1

0 = 1

CAIXA PRETA

CIRCUITO LÓGICO

Instruções para criação do circuito

1. Identificar as variáveis independentes da expressão

2. Para cada uma destas, traçamos uma linha (da esquerda para a direita), representando os fios que conduzem os valores

3. Desenhar as portas necessárias para representar cada uma das sub-expressões, na mesma ordem tomada para a avaliação: ( ), NOT, AND, OR

CIRCUITO LÓGICO

Equação: s = x + y' • z

CIRCUITO LÓGICO

Equação: s = x + y' • z

CIRCUITO LÓGICO

Equação: s = x + y' • z

CIRCUITO LÓGICO

Se fosse desejado que a operação de disjunção

ocorresse antes da conjunção, seria necessário o uso

de parênteses

• Notação:

S = ( x + y' ) • z

• Seria o mesmo circuito?

CIRCUITO LÓGICO

Se fosse desejado negar toda a expressão,

também se usaria parênteses, e essa ação seria a

última a ser avaliada.

• Notação:

S = ( x + y' • z )’

• Seria o mesmo circuito?

CIRCUITO LÓGICO

Para simplificar os circuitos lógicos, são utilizadas

propriedades da álgebra booleana

Vantagem:

• Menor custo

• Maior eficiência

PROPRIEDADES DA ÁLGEBRA

BOOLEANA

PROPRIEDADES DA ÁLGEBRA

BOOLEANA

Absorção: prova

p + (p’ • q) = (p + q) - distributiva

(p + p’) • (p + q) = (p + q) - tautologia

1 • (p + q) = (p + q) - identidade

(p + q) = (p + q)

SIMPLIFICAÇÃO DE

EXPRESSÕES

Aplicar repetidamente as propriedades da álgebra

booleana

• Até que não possa mais ser simplificada

• Ou até que a expressão utilize a menor

quantidade de portas possíveis (operadores

lógicos)

SIMPLIFICAÇÃO DE

EXPRESSÕES

1. Simplifique a expressão booleana: A . (A + B)

A . (A + B) = A . A + A . B (distributiva) = A + A . B (idempotência)

= A . 1 + A . B (identidade)

= A . (1 + B) (distributiva)

= A . 1 (identidade)

= A

SIMPLIFICAÇÃO DE

EXPRESSÕES

2. Prove que: A . (A + B) = A

A . (A + B) = A . A + A . B (distributiva) = A + A . B (idempotência)

= A . 1 + A . B (identidade)

= A . (1 + B) (distributiva)

= A . 1 (identidade)

= A

(c.q.d)

EXERCÍCIO

24/10/2011

Prof. André Montevecchi / Profa. Anna Tostes

68

EXERCÍCIOS

EXERCÍCIOS