Introdução a Lógica
46 pág.

Introdução a Lógica

Disciplina:Elementos de Lógica13 materiais100 seguidores
Pré-visualização7 páginas
⋅(x+y) =®
hip.

x′ ⋅1 =®
B3

x′
Contradic¸a˜o. Logo, o complemento e´ u´nico.

4. Semiabsorc¸a˜o: x + (x′ ⋅ y) = x + y
x + (x′ ⋅ y) =®

B5

(x + x′) ⋅ (x + y) =®
B4

1 ⋅ (x + y) =®
B3

x + y
5. x ⋅ (y + (x ⋅ z)) = (x ⋅ y) + (x ⋅ z)
x ⋅ (y + (x ⋅ z)) =®

B5

(x ⋅ y) + (x ⋅ (x ⋅ z)) =®
B1

(x ⋅ y) + (x ⋅ x ⋅ z) =®
Idemp.

(x ⋅ y) + (x ⋅ z)

31

4.2 Propriedades

Exerc´ıcio 4.2.1 Mostre que, para quaisquer x, y, z ∈ B:
1. x ⋅ x = x
2. x ⋅ 0 = 0
3. Involuc¸a˜o: (x′)′ = x
4. De Morgan: (x + y)′ = x′ ⋅ y′ e (x ⋅ y)′ = x′ + y′
5. Absorc¸a˜o: x + (x ⋅ y) = x e x ⋅ (x + y) = x
6. x ⋅ (x′ + y) = x ⋅ y
7. x + (y ⋅ (x + z)) = (x + y) ⋅ (x + z)
8. (x + y) ⋅ (x′ + y) = y e (x ⋅ y) + (x′ ⋅ y) = y
9. (x + (y ⋅ z))′ = (x′ ⋅ y′) + (x′ ⋅ z′) e (x ⋅ (y + z))′ = (x′ + y′) ⋅ (x′ + z′)

10. (x + y) ⋅ (x + 1) = x + (x ⋅ y) + y e (x ⋅ y) + (x ⋅ 0) = x ⋅ (x + y) ⋅ y
11. (x + y) + (y ⋅ x′) = x + y e (x ⋅ y) ⋅ (y + x′) = x ⋅ y
12. x + ((x′ ⋅ y) + (x ⋅ y))′ = x + y′
13. ((x ⋅ y) ⋅ z) + (y ⋅ z) = y ⋅ z
14. (y′ ⋅ x) + x + ((y + x) ⋅ y′) = x
15. ((x′ + z′) ⋅ (y + z′))′ = (x + y′) ⋅ z
16. (x ⋅ y) + (x′ ⋅ z) + (x′ ⋅ y ⋅ z′) = y + (x′ ⋅ z)
17. (x ⋅ y′) + (y ⋅ z′) + (x′ ⋅ z) = (x′ ⋅ y) + (y′ ⋅ z) + (x ⋅ z′)
18. x ⋅ y′ = 0 se, e somente se, x ⋅ y = x.
19. (x ⋅ y′) + (x′ ⋅ y) = y se, e somente se, x = 0.
20. x + y = 0 se, e somente se, x = 0 e y = 0.
21. x = y se, e somente se, (x ⋅ y′) + (y ⋅ x′) = 0.

32

4.3 Reticulados

4.3 Reticulados

Um conjunto parcialmente ordenado [A,≼] e´ composto por um conjunto na˜o vazio A
e uma relac¸a˜o bina´ria ≼ em A reflexiva, antissime´trica e transitiva, isto e´, para quaisquer
x, y, z ∈ A,

• Reflexiva: Se x ≼ y e y ≼ x enta˜o x = y.
• Antissime´trica: Se x ≼ y e y ≼ x enta˜o x = y.
• Transitiva: Se x ≼ y e y ≼ z enta˜o x ≼ z.

Seja [A,≼] e x, y ∈ A. O supremo de x e y e´ o elemento s ∈ A tal que
S1 x ≼ s,
S2 y ≼ s e
S3 se existir algum z ∈ A com x ≼ z e y ≼ z enta˜o s ≼ z.

O ı´nfimo de x e y e´ o elemento i ∈ A tal que
i1 i ≼ x,
i2 i ≼ y e
i3 se existir algum z ∈ A com z ≼ x e z ≼ y enta˜o z ≼ i.

Notac¸a˜o: s = x ∨ y = x + y e i = x ∧ y = x ⋅ y
Um reticulado e´ um conjunto parcialmente ordenado no qual existe supremo e ı´nfimo

para quaisquer dois elementos. Assim, supremo e ı´nfimo podem ser entendidos como operac¸o˜es
bina´rias em A. Denota-se um reticulado por [A,≼,+, ⋅]. Um reticulado e´ complementado
quando

RC1 Existe um menor elemento 0, isto e´, para todo x ∈ A, 0 ≼ x.
RC2 Existe um maior elemento 1, ou seja, para todo x ∈ A, x ≼ 1.
RC3 Para todo elemento x ∈ A existe x′ ∈ A tal que x + x′ = 1 e x ⋅ x′ = 0.
Um reticulado e´ distributivo quando para quaisquer x, y, z ∈ A,
RD x + (y ⋅ z) = (x + y) ⋅ (x + z) e x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z).
Um reticulado complementado e distributivo e´ uma a´lgebra de Boole.

33

4.3 Reticulados

Exerc´ıcio 4.3.1 Indique os diagramas de Hasse que representam a´lgebras de Boole, justifi-
cando.

	
  

4.4 Expresso˜es, Formas e Func¸o˜es

Uma expressa˜o booleana e´:

b1. Qualquer s´ımbolo de varia´vel.

b2. Se α e β sa˜o expresso˜es boolenas enta˜o α + β, α ⋅ β e α′ tambe´m sa˜o.
Um literal e´ uma expressa˜o do tipo varia´vel ou varia´vel complementada. Um produto

fundamental e´ ou um literal ou um produto de literais em que na˜o aparec¸a um s´ımbolo de
varia´vel repetido. Uma expressa˜o booleana e´ uma expressa˜o em soma de produtos ou esta´
na forma normal (disjuntiva )quando e´ um produto fundamental ou a soma de produtos
fundamentais.

Exemplo 4.4.1 Seja [B,+, ⋅,′ ] uma a´lgebra de Boole.
expressa˜o literal produto fundamental FN

x
√ √ √ √

x′ √ √ √ √
xy′z √ √ √

xy′z + x′yz′ √ √(x + y)′z √
xyx′ √

Uma func¸a˜o booleana e´ uma func¸a˜o f ∶ {0,1}n → {0,1} para algum n ≥ 1.
As poss´ıveis representac¸o˜es de uma func¸a˜o booleana sa˜o por uma tabela ou por um Mapa

de Karnaugh (Maurice Karnaugh 1924-). O mapa de Karnaugh e´ uma representac¸a˜o
matricial que armazena somente os valores 1 da func¸a˜o de modo que o produto de varia´veis
de entrada que diferem apenas por um fator sejam adjacentes.

34

4.4 Expresso˜es, Formas e Func¸o˜es

Exemplos 4.4.2 Considere as func¸o˜es.

1. f ∶ {0,1}2 → {0,1} tal que f(1,1) = 0, f(1,0) = 1, f(0,1) = 1 e f(0,0) = 0.
x1 x2 f(x1, x2)
1 1 0
1 0 1
0 1 1
0 0 0

x1 x′1
x2 0 1
x′2 1 0

2. Seja a func¸a˜o f ∶ {0,1}3 → {0,1} tal que f(1,1,1) = f(1,1,0) = f(0,1,1) = f(0,0,1) = 1
e f(1,0,1) = f(1,0,0) = f(0,1,0) = f(0,0,0) = 0.

x1 x2 x3 f(x1, x2, x3)
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 1
0 0 0 0

x1x2 x1x′2 x′1x′2 x′1x2
x3 1 1 1
x′3 1

Podemos associar a cada func¸a˜o booleana uma expressa˜o. No exemplo anterior item 1, a`s
linhas 2 e 3 ficam associados os produtos fundamentais x1x′2 e x′1x2, respectivamente. Assim,
a func¸a˜o fica associada a` expressa˜o booleana na forma normal

f(x1, x2) = x1x′2 + x′1x2.
No item 2, a`s linhas 1, 2, 5 e 7 ficam associados os produtos fundamentais x1x2x3, x1x2x′3,

x′1x2x3 e x′1x′2x3, respectivamente. Enta˜o, a func¸a˜o fica associada a` expressa˜o booleana na
forma normal

f(x1, x2, x3) = x1x2x3 + x1x2x′3 + x′1x2x3 + x′1x′2x3.
Para func¸o˜es com um nu´mero maior de varia´veis, o mapa e´ a representac¸a˜o mais sinte´tica.

Considere o mapa a seguir.

x1x2 x1x′2 x′1x′2 x′1x2
x3x4 1
x3x′4
x′3x′4 1 1
x′3x4 1

A func¸a˜o associada e´:

f(x1, x2, x3, x4) = x1x′2x3x4 + x1x2x′3x′4 + x′1x2x′3x′4 + x1x′2x′3x4.
35

4.4 Expresso˜es, Formas e Func¸o˜es

4.5 Circuitos Lo´gicos

Caracter´ısticas gerais:

• Descargas ele´tricas alta e baixa, 1 e 0, respectivamente.

• Flutuac¸o˜es de voltagem sa˜o ignoradas.

• O sinal 1 faz com que o interruptores feche e o 0 abra.

x = 1 x = 0

• Combinac¸a˜o de interruptores x e y em paralelo.

x1 = 1

x2 = 0	
  
1

Esta combinac¸a˜o pode ser associada a` operac¸a˜o boolena x + y e a` porta lo´gica OU.

	
  	
  	
  	
  	
  	
  	
  	
  	
  

x1 x2 x1 + x2
1 1 1
1 0 1
0 1 1
0 0 0

x2

x1 x1+x2

36

4.5 Circuitos Lo´gicos

• Combinac¸a˜o de interruptores x e y em se´rie.

	
  
x1 = 1 x2 = 0 0

Esta combinac¸a˜o pode ser associada a` operac¸a˜o boolena x ⋅ y e a` porta lo´gica E.

	
  	
  	
  	
  	
  	
  	
  	
  	
  

x1 x2 x1 . x2
1 1 1
1 0 0
0 1 0
0 0 0

x2

x1 x1.x2

• Um inversor (negac¸a˜o) corresponde a` operac¸a˜o una´ria booleana ′.

	
  
x1 x'1
1 0
0 1

x'1 x1

Observe que, circuitos podem ser associados a func¸o˜es booleanas, isto e´, a expresso˜es
booleanas.

37

4.5 Circuitos Lo´gicos

Exemplo 4.5.1 Ao circuito

	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  

fica associada a expressa˜o booleana

x1x
′
2x3x4 + x1x2x′3x′4 + x′1x2x′3x′4 + x1x′2x′3x4.

4.6 Minimizac¸a˜o

Considere a expressa˜o do Exemplo 4.5.1

x1x
′
2x3x4 + x1x2x′3x′4 + x′1x2x′3x′4 + x1x′2x′3x4

e a manipulac¸a˜o alge´brica:

α1 x1x′2x3x4 + x1x2x′3x′4 + x′1x2x′3x′4 + x1x′2x′3x4 = B2
α2 x1x′2x3x4 + x1x′2x′3x4 + x1x2x′3x′4 + x′1x2x′3x′4 = B5
α3 x1x′2x4(x3 + x′3) + (x1 + x′1)x2x′3x′4 = B4
α4 x1x′2x4 1 + 1x2x′3x′4 = B3
α5 x1x′2x4 + x2x′3x′4

Cada uma das linhas desta manipulac¸a˜o e´ uma expressa˜o booleana associada a` mesma
func¸a˜o booleana. Tanto α1 quanto α5 esta˜o na forma normal, e α5 e´ a forma simplificada
ou mı´nima de α1.

Vamos tratar agora de minimizac¸a˜o de circuitos atrave´s do mapa de Karnaugh. Devemos
agrupar todas as ocorreˆncias adjacentes contendo uns de forma a obter a maior combinac¸a˜o
poss´ıvel. Assim reduziremos o nu´mero de parcelas na expressa˜o.

x1x2 x1x′2 x′1x′2 x′1x2
x3x4 1
x3x′4
x′3x′4 1 1
x′3x4 1

38

4.6 Minimizac¸a˜o

Observe que, tomar ce´luas adjacentes corresponde a` simplicac¸a˜o alge´brica com o uso dos
axiomas da distributividade, complementaridade e elemento neutro.

Finalmente, o circuito de Exemplo 4.5.1 e´ equivalente a um circuito menor.

	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  

x2

x2

x1

x4

x3
x4

Exemplo 4.6.1 Considere o mapa de Karnaugh com oito produtos fundamentais.

x1x2 x1x′2 x′1x′2 x′1x2
x3x4 1 1
x3x′4 1 1
x′3x′4 1 1
x′3x4 1 1

Dois poss´ıveis agrupamentos de uns.

x1x2 x1x′2 x′1x′2 x′1x2
x3x4 1 1
x3x′4 1 1
x′3x′4 1 1
x′3x4 1 1