Matemática Discreta para Ciência da Computação Álgebra de Conjuntos 3 de 9

Prévia do material em texto

Matemática Discreta para Ciência da Computação - P. Blauth Menezes 1
Matemática Discreta para
Ciência da Computação
P. Blauth Menezes
blauth@inf.ufrgs.br
Departamento de Informática Teórica
Instituto de Informática / UFRGS
 
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 2
Matemática Discreta para Ciência da Computação
P. Blauth Menezes
1 Introdução e Conceitos Básicos
2 Lógica e Técnicas de Demonstração
3 Álgebra de Conjuntos
4 Relações
5 Funções Parciais e Totais
6 Endorrelações, Ordenação e Equivalência
7 Cardinalidade de Conjuntos
8 Indução e Recursão
9 Álgebras e Homomorfismos
10 Reticulados e Álgebra Booleana
11 Conclusões
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 3
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 4
3.1 Introdução
♦ Álgebra, desde a sua origem até a sua forma atual
• refere-se a cálculos
♦ Desenvolvida de forma informal ou formal
• praticamente em todos os níveis de escolaridade
• exemplo: operações aritméticas (adição, multiplicação…) sobre R
♦ Álgebras, em CC, destaca-se a partir de 1950
• Teoria dos Autômatos e Linguagens Formais
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 5
♦ De certa forma, toda a CC é construída sobre álgebras
• Álgebra: denominação alternativa para a Matemática Discreta
∗ Diretrizes Curriculares do MEC para Computação e Informática
♦ Conceito de Álgebra é introduzido adiante
• informalmente: operações definidas sobre um conjunto
• Álgebra de Conjuntos: operações definidas sobre todos os conjunto
♦ Desejável para o estudo da Álgebra de Conjuntos
• Diagramas de Venn: representação diagramática
∗ auxilia o entendimento dos conceitos e raciocínios
• Paradoxo de Russell: importante!
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 6
♦ Operações sobre conjuntos
• Não-Reversíveis: mais usuais
∗ União
∗ Intersecção
• Reversíveis: especialmente importantes para CC
∗ Complemento
∗ Conjunto das Partes
∗ Produto Cartesiano
∗ União Disjunta
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 7
Obs: Lógica × Álgebra dos Conjuntos
Relação direta entre conetivos lógicos e operações sobre conjuntos
• facilita muito o estudo da Álgebra de Conjuntos
Conetivo Lógico Operação sobre Conjuntos
negação complemento
disjunção união
conjunção intersecção
Relação Lógica Relação sobre Conjuntos
implicação continência
equivalência igualdade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 8
♦ Propriedades sobre os conetivos são válidas na Teoria
dos Conjuntos
• substituindo cada conetivo
• pela correspondente operação sobre conjuntos
• exemplo
∗ idempotência do ∧ e do ∨ (da ∩ e da ∪)
∗ comutatividade do ∧ e do ∨ (da ∩ e da ∪)
∗ associatividade do ∧ e do ∨ (da ∩ e da ∪)
∗ distributividade do ∧ sobre o ∨ (da ∩ sobre a ∪) e vice-versa
∗ dupla negação (duplo complemento)
∗ DeMorgan
♦ Pode-se intuir que provas na Teoria dos Conjuntos
• são, em grande parte, baseadas em resultados da lógica
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 9
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.5 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 10
3.2 Diagramas de Venn
♦ Linguagem diagramática
• auxilia o entendimento de definições
• facilita o desenvolvimento de raciocínios
• permite identificação e compreensão fácil e rápida dos
∗ componentes e relacionamentos
♦ Diagramas de Venn
• universalmente conhecidos e largamente usados
• usam figuras geométricas, em geral representadas no plano
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 11
Exp: Diagramas de Venn
• um dado conjunto A
• um determinado elemento b ∈ B
• o conjunto C = { 1, 2, 3 }
b
1
2
3
A B C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 12
Exp: Diagramas de Venn
• { a, b } ⊆ { a, b, c }
• A ⊆ B
• para um dado conjunto universo U, um conjunto C ⊆ U
a
b
c
B
A C
U
Em geral
• U é representado por um retângulo
• demais conjuntos por círculos, elipses, etc
• emC ⊆ U, o conjunto C é destacado, para auxiliar visualmente
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 13
Exp: Aplicação dos Diagramas de Venn
Considere que
BA
C
pode-se intuir que a noção de subconjunto é transitiva, ou seja
A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C
Teorema: Transitividade da Continência
Suponha A, B e C conjuntos. Se A ⊆ B e B ⊆ C, então A ⊆ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 14
Prova: (direta)
(X ⊆ Y sss todos os elementos de X também são de Y)
Suponha que A, B e C são conjuntos qq e que A ⊆ B e B ⊆ C
Seja a ∈ A. Então:
• a ∈ A ⇒ pela definição de subconjunto, dado que A ⊆ B
• a ∈ B ⇒ pela definição de subconjunto, dado que B ⊆ C
• a ∈ C
Portanto, para qq a ∈ A, a ∈ C
Logo, pela definição de subconjunto, A ⊆ C
∗ como fica a demonstração se A for vazio?
∗ neste caso, não existe elemento a ∈ A…
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 15
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.6 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 16
3.3 Paradoxo de Russell
Conjunto
 coleção de zero ou mais elementos distintos os quais não
possuem qualquer ordem associada
Existem conjuntos de conjuntos. Então:
um conjunto pode ser elemento de si mesmo?
Def: Conjunto ordinário
• conjunto que não pertence a si mesmo
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 17
♦ A definição
S = { A  A é um conjunto ordinário }
conjunto de todos os conjuntos que não são elementos de si
mesmos
• determina uma contradição
• Paradoxo de Russell
Teorema: Paradoxo de Russell
Não é conjunto
S = { A  A é um conjunto ordinário }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 18
Prova: (por absurdo)
Negação da tese. Suponha que S é um conjunto
Construção da contradição. S é um elemento de si mesmo?
Caso 1. Suponha que S ∈ S
• S ∈ S ⇒ pela definição de conj. ordinário
• S não é um conj. ordinário ⇒ pela definição de S
• S ∉ S
Caso 2. Suponha que S ∉ S
• S ∉ S ⇒ pela definição de conj. ordinário
• S é um conj. ordinário ⇒ pela definição de S
• S ∈ S
Contradição!!! Logo, é absurdo supor que S é conjunto
Portanto, S não é conjunto
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 19
♦ Portanto, a notação por compreensão
• permite definir algo que não é um conjunto
• S seria um subconjunto do conjunto de todos os conjuntos
• como Snão é conjunto
não existe o conjunto de todos os conjuntos
ou seja:
nem toda coleção de elementos constitui um conjunto
♦ Como evitar o paradoxo (se desejado)
• restringir que a, em { a  p(a) }, assuma valores em um dado A
{ a ∈ A  p(a) }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 20
♦ Importante conseqüência do Paradoxo de Russell
• definição de uma estrutura matemática sobre uma coleção de
elementos.
♦ Estrutura Matemática Pequena × Grande
• pequena, se a coleção de elementos é conjunto
• grande, se a coleção de elementos não é conjunto
♦ Álgebra de Conjuntos
• álgebra grande
• operações sobre a coleção (não-conjunto) de todos os conjuntos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 21
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.7 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 22
3.4 Operações Não-Reversíveis
As mais comuns nos estudos da Álgebra de Conjuntos
3.4.1 União
A B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 23
Def: União, Reunião
A e B conjuntos
A ∪ B
A ∪ B = { x  x ∈ A ∨ x ∈ B }
Relacionando com a Lógica
• união corresponde à disjunção
• símbolo ∪ lembra símbolo ∨
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 24
Exp: União
• Dígitos = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• Vogais = { a, e, i, o, u }
• Pares = { 0, 2, 4, 6,… }
Dígitos ∪ Vogais = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, e, i, o, u }
Dígitos ∪ Pares = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16,… }
.
1
3
5
7
9
0
2
4
6
8
10
12
14
16...
Pares
a
e
i
o
u
Vogais
1
3
5
7
9
0
2
4
6
8
Dígitos Dígitos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 25
Exp: União
• A = { x ∈ N  x > 2 }, B = { x ∈ N  x2 = x }
A ∪ B = { 0, 1, 3, 4, 5, 6,… }
• R (reais ), Q (racionais) e I (irracionais)
R ∪ Q = R R ∪ I = R Q ∪ I = R
• Conjunto universo U e A ⊆ U
∅ ∪ ∅ = ∅ U ∪ ∅ = U
U ∪ A = U U ∪ U = U
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 26
♦ Propriedades da união
Elemento Neutro (qual o elemento neutro da disjunção?)
A ∪ ∅ = ∅ ∪ A = A (exercício)
Idempotência
A ∪ A = A (exercício)
Comutatividade
A ∪ B = B ∪ A (exercício)
Associatividade
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 27
Associatividade
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A B
C
A B
C
B ∪ C A ∪ B
A B
C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 28
Teorema: Associatividade da União
Suponha que A, B e C são conjuntos quaisquer. Então:
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Prova: (direta)
(X = Y ⇔ X ⊆ Y e Y ⊆ X)
Suponha que A, B e C são conjuntos quaisquer. Dois casos:
• A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C caso 1
• (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C) caso 2
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 29
Caso 1. Suponha x ∈ A ∪ (B ∪ C)
• x ∈ A ∪ (B ∪ C) ⇒ pela definição união
• x ∈ A ∨ x ∈ (B ∪ C) ⇒ pela definição união
• x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇒ pela associatividade do conetivo ∨
• (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇒ pela definição união
• x ∈ (A ∪ B) ∨ x ∈ C ⇒ pela definição união
• x ∈ (A ∪ B) ∪ C
• Portanto, A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 30
Caso 2. Suponha x ∈ (A ∪ B) ∪ C
• x ∈ (A ∪ B) ∪ C ⇒ pela definição união
• x ∈ (A ∪ B) ∨ x ∈ C ⇒ pela definição união
• (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇒ pela associatividade do conetivo ∨
• x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇒ pela definição união
• x ∈ A ∨ x ∈ (B ∪ C) ⇒ pela definição união
• x ∈ A ∪ (B ∪ C)
• Portanto, (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C)
Logo, A ∪ (B ∪ C) = (A ∪ B) ∪ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 31
♦ Significado da associatividade?
• não existe precedência entre operações de união
• parênteses podem ser omitidos
• A ∪ (B ∪ C) ou (A ∪ B) ∪ C pode ser denotado
A ∪ B ∪ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 32
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.8 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 33
3.4.2 Intersecção
A B
Def: Intersecção
A e B conjuntos
A ∩ B
A ∩ B = { x  x ∈ A ∧ x ∈ B }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 34
♦ Relacionando com a Lógica
• intersecção corresponde à conjunção
• símbolo ∩ lembra símbolo ∧
♦ Conjuntos disjuntos
• conjuntos independentes ou conjuntos mutuamente exclusivos
• conjuntos A e B sendo ambos não-vazios
A ∩ B = ∅
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 35
Exp: Intersecção, Conjuntos Disjuntos
Dígitos = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Vogais = { a, e, i, o, u }
Pares = { 0, 2, 4, 6,… }
Dígitos ∩ Vogais = ∅ conjuntos disjuntos
Dígitos ∩ Pares = { 0, 2, 4, 6, 8 }
.
1
3
5
7
9
10
12
14
16...
Pares
a
e
i
o
u
Vogais
1
3
5
7
9
0
2
4
6
8
Dígitos Dígitos 0
2
4
6
8
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 36
Exp: Intersecção, Conjuntos Disjuntos
A = { x ∈ N  x > 2 }, B = { x ∈ N  x2 = x }
A ∩ B = ∅ conjuntos disjuntos
R (reais ), Q (racionais) e I (irracionais)
R ∩ Q = Q R ∩ I = I 
Q ∩ I = ∅ conjuntos disjuntos
Conjunto universo U e A ⊆ U
∅ ∩ ∅ = ∅ U ∩ ∅ = ∅
U ∩ A = A U ∩ U = U
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 37
♦ Propriedades da intersecção
Elemento Neutro (qual o elemento neutro da conjunção?)
A ∩ U = U ∩ A = A (exercício)
Idempotência
A ∩ A = A (exercício)
Comutatividade
A ∩ B = B ∩ A (exercício)
Associatividade
A ∩ (B ∩ C) = (A ∩ B) ∩ C (exercício)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 38
♦ Propriedades da união e da intersecção
Distributividade da intersecção sobre a união
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A B
C
A B
C
A B
C
B ∪ C
A B
C
A ∩ B A ∩ C
A ∩ (B ∪ C) =
(A ∩ B) ∪ (A ∩ C)
Distributividade da união sobre a intersecção
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 39
Teorema: Distributividade da intersecção sobre a união
Suponha que A, B e C são conjuntos quaisquer. Então:
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Prova: (direta)
Suponha que A, B e C são conjuntos quaisquer. Então:
• x ∈ A ∩ (B ∪ C) ⇔ pela definição de intersecção
• x ∈ A ∧ x ∈ (B ∪ C) ⇔ pela definição de união
• x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇔ pela distributividade do ∧ sobre o ∨
• (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇔ pela definição de intersecção
• x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) ⇔ pela definição de união
• x ∈ (A ∩ B) ∪ (A ∩ C)
Logo, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 40
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 41
3.5 Operações Reversíveis
♦ Operação reversível
• a partir do resultado, pode-se recuperar os operando originais
• Importante em muitas aplicações na Computação e Informática
Exp: Back Tracking (ilustrativo)
Operação de débito e crédito em um terminal bancário automático
• composição de diversas pequenas operações componentes
Queda de sistema (luz…) entre duas operações componentes
• sistema poderia ficar inconsistente
• exemplo: débito realizado, mas o crédito, não
• fundamental desfazer o que foi parcialmente feito
• recuperação facilitada quando a operação é reversível
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 42
Exp: Construção de Estruturas Complexas (ilustrativo)
Construção de Estruturas Complexas.
• compondo estruturas elementares já conhecidas
• em geral, é desejável que uma alteração realizada em uma
estrutura elementar seja refletida na estrutura composta
• possível se conhecido os elementos originais da estrutura
• informação facilitada quando a operação é reversível
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 43
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 44
3.5.1 Complemento
A
U
A
U
~A
Def: Complemento
Complemento de um conjunto A ⊆ U
A' ou ~A
~A = { x ∈ U  x ∉ A }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 45
♦ Relacionando com a Lógica
• complemento corresponde à negação
• símbolo ~ é um dos usados para a negação
Exp: Complemento
Dígitos = { 0, 1, 2,…, 9 } conjunto universo e A = { 0, 1, 2 }
• ~A = { 3, 4, 5, 6, 7, 8, 9 }
0
1
2
Dígitos
3 4
5
6
7
8
9
0
1
2
Dígitos
3 4
5
6
7
8
9
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 46
Exp: …Complemento
N conjunto universo e A = { 0, 1, 2 }
• ~A = { x ∈ N  x > 2 }
Para qualquer conjunto universo U
• ~∅ = U
• ~U = ∅
R conjunto universo
• ~Q = I
• ~I = Q
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 47
Exp: Complemento, União e Intersecção
U conjunto universo. Para qualquer A ⊆ U
• A ∪ ~A = U p ∨ ¬p é tautologia
• A ∩ ~A = ∅ p ∧ ¬p é contradição
♦ Propriedade Duplo Complemento
• para qualquer A ⊆ U
~~A = A
• relacionamento com lógica
∗ A: todos elementos x tais que x ∈ A
∗ ~A: todos elementos x tais que x ∉ A ¬(x ∈ A)
∗ ~~A: todos elementos x tais que ¬¬(x ∈ A) x ∈ A
• complemento é reversível: ~(~A) = A
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 48
♦ Propriedade DeMorgan
• relacionada com o complemento
• envolve a união e a intersecção
~(A ∪ B) = ~A ∩ ~B ¬(p ∨ q) ⇔ ¬p ∧ ¬q
~(A ∩ B) = ~A ∪ ~B ¬(p ∧ q) ⇔ ¬p ∨ ¬q
A B
U
A B
U
A B
U
A B
U
~(A ∪ B) = ~A ∩ ~BA ∪ B ~A ~B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 49
♦ Essa propriedade permite concluir
• intersecção pode ser calculada em termos do complemento e união
A ∩ B = ~(~A ∪ ~B)
• união pode ser calculada em termos do complemento e intersecção
A ∪ B = ~(~A ∩ ~B)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 50
♦ Diferença: derivada da intersecção e complemento
A B
Def: Diferença
A e B conjuntos
A - B
A - B = A ∩ ~B = { x  x ∈ A ∧ x ∉ B }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 51
Exp: Diferença
Dígitos = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Vogais = { a, e, i, o, u }
Pares = { 0, 2, 4, 6,… }
• Dígitos - Vogais = Dígitos
• Dígitos - Pares = { 1, 3, 5, 7,9 }
.
1
3
5
7
9
0
2
4
6
8
10
12
14
16...
Pares
a
e
i
o
u
Vogais
1
3
5
7
9
0
2
4
6
8
Dígitos Dígitos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 52
Exp: …Diferença
A = { x ∈ N  x > 2 } e B = { x ∈ N  x2 = x }
• A - B = { 3, 4, 5, 6,… }
• B - A = { 0, 1 }
R (reais ), Q (racionais) e I (irracionais)
• R - Q = I
• R - I = Q
• Q - I = Q
Universo U e A ⊆ U
• ∅ - ∅ = ∅
• U - ∅ = U
• U - A = ~A
• U - U = ∅
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 53
♦ Por que a operação de diferença é não-reversível?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 54
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 55
3.5.2 Conjunto das Partes
♦ Para um conjunto A
• A ⊆ A
• ∅ ⊆ A
♦ Para qualquer elemento a ∈ A
• { a } ⊆ A
♦ Seguindo o racionínio
• definição de uma operação unária
• Conjunto das Partes
∗ aplicada a um conjunto A
∗ resulta no conjunto de todos os subconjuntos de A
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 56
Def: Conjunto das Partes, Conjunto Potência
A conjunto
P(A) ou 2A
P(A) = { X  X ⊆ A }
Exp: Conjunto das Partes
A = { a }, B = { a, b } e C = { a, b, c }
• P(∅) = { ∅ }
• P(A) = { ∅, { a } }
• P(B) = { ∅, { a }, { b }, { a, b } }
• P(C) = { ∅, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } }
Quantos elementos tem P(X)?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 57
Exp: …Conjunto das Partes
D = { a, ∅, { a, b } }
• P(D) = { ∅, { a }, { ∅ }, { { a, b } }, { a, ∅ }, { a, { a, b } }, { ∅, { a,
b } }, { a, ∅, { a, b } } }
Quantos elementos tem P(X)?
♦ Número de elementos de P(X)
• número de elementos de
∗ X é n
∗ P(X) é 2n
• justifica a notação 2X
∗ prova por indução introduzida adiante
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 58
♦ Reversabilidade de P(X)?
• uma solução: união de todos os conjuntos de P(X)
• como fica o cálculo da união se o número de elementos do
conjunto das partes for infinito?
∗ não será discutido
Exp: Reversabilidade do Conjunto das Partes
Resultante: { ∅, { a } }
• Operando: ∅ ∪ { a } = { a }
Resultante: { ∅, { a }, { b }, { a, b } }
• Operando: ∅ ∪ { a } ∪ { b } ∪ { a, b } = { a, b }
Resultante: { ∅, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } }
• Operando: ∅ ∪ { a } ∪ { b } ∪ { c } ∪ { a, b } ∪ { a, c } ∪ { b, c } ∪ 
{ a, b, c } = { a, b, c }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 59
Obs: Álgebra de Conjuntos Pequena
Álgebra de Conjuntos é uma álgebra grande
• operações sobre a coleção (não-conjunto) de todos os conjuntos
Se for desejado uma Álgebra de Conjuntos pequena??
• definir sobre P(U)
• para cada U, uma álgebra diferente
• qq operando A é tal que A ∈ P(U)
União, intersecção, diferença e complemento
• fechadas sobre P(U)
Conjunto das partes
• não necessariamente é fechada sobre P(U) por quê?Matemática Discreta para Ciência da Computação - P. Blauth Menezes 60
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 61
3.5.3 Produto Cartesiano
♦ Noção de seqüência finita
• necessária para definir produto cartesiano
∗ em particular, seqüência de dois elementos
♦ Seqüência de n componentes: n-upla ordenada
• n objetos (não necessariamente distintos) em uma ordem fixa
♦ 2-upla ordenada ou par ordenado
〈x, y〉 ou (x, y)
♦ n-upla ordenada
〈x1, x2, x3,…,xn〉 ou (x1, x2, x3,…,xn)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 62
♦ Não confundir
〈x1, x2, x3,…,xn〉 com { x1, x2, x3,…,xn }
♦ A ordem é importante
 〈x, y〉 ≠ 〈y, x〉
Def: Produto Cartesiano
A e B conjuntos
A × B
A × B = { 〈a, b〉  a ∈ A e b ∈ B }
♦ Produto cartesiano de A com ele mesmo
A × A = A2
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 63
Exp: Produto Cartesiano
A = { a }, B = { a, b } e C = { 0, 1, 2 }
A × B = { 〈a, a〉, 〈a, b〉 }
B × C = { 〈a, 0〉, 〈a, 1〉, 〈a, 2〉, 〈b, 0〉, 〈b, 1〉, 〈b, 2〉 } (não-comut.)
C × B = { 〈0, a〉, 〈0, b〉, 〈1, a〉, 〈1, b〉, 〈2, a〉, 〈2, b〉 }
A2 = { 〈a, a〉 }
B2 = { 〈a, a〉, 〈a, b〉, 〈b, a〉, 〈b, b〉 }
A × N = { 〈a, 0〉, 〈a, 1〉, 〈a, 2〉, 〈a, 3〉,… }
(A × B) × C = (não-associatividade)
    { 〈〈a, a〉,0〉, 〈〈a, a〉,1〉, 〈〈a, a〉,2〉, 〈〈a, b〉,0〉, 〈〈a, b〉,1〉, 〈〈a, b〉,2〉 }
A × (B × C) =
    { 〈a,〈a, 0〉〉, 〈a,〈a, 1〉〉, 〈a,〈a, 2〉〉, 〈a,〈b, 0〉〉, 〈a,〈b, 1〉〉, 〈a,〈b, 2〉〉 }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 64
♦ Conclusões
• Não-Comutatividade
∗ B × C e C × B são diferentes
∗ (B × C) ∩ (C × B) = ∅ disjuntos
• Não-Associatividade
∗ (A × B) × C e A × (B × C) são diferentes por quê?
Exp: Produto Cartesiano
A = { 0, 1, 2 }
• A × ∅ = ∅ por quê?
• ∅ × A = ∅ por quê?
• ∅2 = ∅
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 65
♦ Distributividade do produto cartesiano sobre a união
A × (B ∪ C) = (A × B) ∪ (A × C) exercício
♦ Distributividade do produto cartesiano sobre a
intersecção
A × (B ∩ C) = (A × B) ∩ (A × C) exercício
♦ Reversabilidade do produto cartesiano ?
• como fazer?
• nem sempre é válida
∗ quando o produto cartesiano resulta no vazio por quê?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 66
Exp: Reversabilidade do Produto Cartesiano
{ 〈a, a〉, 〈a, b〉 }
• Operandos: { a } e { a, b }
{ 〈a, a〉, 〈a, b〉, 〈b, a〉, 〈b, b〉 }
• Operandos: { a, b } e { a, b }
{ 〈a, 0〉, 〈a, 1〉, 〈a, 2〉, 〈a, 3〉,… }
• Operandos: { a } e N
{ 〈〈a, a〉, 0〉, 〈〈a, a〉, 1〉, 〈〈a, a〉, 2〉, 〈〈a, b〉, 0〉, 〈〈a, b〉, 1〉, 〈〈a, b〉, 2〉 }
• Operandos: { 〈a, a〉, 〈a, b〉 } e { 0, 1, 2 }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 67
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 68
3.5.4 União Disjunta
♦ Pessoas da família Silva e Souza
• Silva = { João, Maria, José }
• Souza = { Pedro, Ana, José }
♦ Conjunto resultante da união
Silva ∪ Souza = { João, Maria, Pedro, Ana, José }
• José ocorre uma única vez
• não reflete uma “reunião familiar”
∗ José Silva não é o mesmo José Souza
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 69
♦ União disjunta
• distingue elementos com mesma identificação
• garante que não existem elementos em comum
∗ associa uma identificação do conjunto origem
∗ um tipo de “sobrenome”
〈elemento, identificação do conjunto origem〉
Def: União Disjunta
A + B ou A ∪ B
A + B = { 〈a, A〉a ∈ A } ∪ { 〈b, B〉b ∈ B }
A + B = { 〈a, 0〉a ∈ A } ∪ { 〈b, 1〉b ∈ B }
A + B = { aAa ∈ A } ∪ { bBb ∈ B }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 70
♦ Diversas formas de denotar elementos de A + B
• importante é distinguir o conjunto originário
Exp: União Disjunta
Silva = { João, Maria, José } e Souza = { Pedro, Ana, José }
Silva + Souza = { 〈João, Silva〉, 〈Maria, Silva〉, 〈José, Silva〉,
〈Pedro, Souza〉, 〈Ana, Souza〉, 〈José, Souza〉 }
D = { 0, 1, 2,…, 9 }, V = { a, e, i, o, u } e P = { 0, 2, 4, 6,… }
D + V = { 0D, 1D, 2D,…, 9D, aV, eV, iV, oV, uV }
D + P = { 0D, 1D, 2D,…, 9D, 0P, 2P, 4P, 6P,… }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 71
Exp: …União Disjunta
A = { x ∈ N  x > 2 } e B = { x ∈ N  x2 = x }
• A + B = { 0B, 1B, 3A, 4A, 5A, 6A,… }
A = { a, b, c }
• ∅ + ∅ = ∅
• A + ∅ = { 〈a, A〉, 〈b, A〉, 〈c, A〉 }
• A + A = { 〈a, 0〉, 〈b, 0〉, 〈c, 0〉, 〈a, 1〉, 〈b, 1〉, 〈c, 1〉 }
♦ Reversabilidade da união disjunta?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 72
Exp: Reversabilidade da União Disjunta
{ 0D, 1D, 2D,…, 9D, aV, eV, iV, oV, uV }
• Operandos: { 0, 1, 2,…, 9 } e { a, e, i, o, u }
{ 0D, 1D, 2D,…, 9D, 0N, 1N, 2N, 3N… }
• Operandos: { 0, 1, 2,…, 9 } e N
∅
• Operandos: ∅ e ∅
{ 〈a, 0〉, 〈b, 0〉 }
• Operandos: { a, b } e ∅
{ 〈a, 0〉, 〈b, 0〉, 〈a, 1〉, 〈b, 1〉, 〈c, 1〉 }
• Operandos: { a, b } e { a, b, c }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 73
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 74
3.6 Relação entre Lógica e Álgebra de
Conjuntos
Propriedade Lógica Teoria dos Conjuntos
Idemp p ∧ p ⇔ p
p ∨ p ⇔ p
A ∩ A = A
A ∪ A = A
Comut p ∧ q ⇔ q ∧ p
p ∨ q ⇔ q ∨ p
A ∩ B = B ∩ A
A ∪ B = B ∪ A
Associat p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 75
Propriedade Lógica Teoria dos Conjuntos
Distrib p ∧ (q ∨ r) ⇔
(p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ⇔
(p ∨ q) ∧ (p ∨ r)
A ∩ (B ∪ C) =
(A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C)
Negação/
Compl
¬¬p ⇔ p
p ∧ ¬p ⇔ F
p ∨ ¬p ⇔ V
~~A = A
A ∩ ~A = ∅
A ∪ ~A = U
DeMorgan ¬(p ∧ q) ⇔ ¬p ∨ ¬q
¬(p ∨ q) ⇔ ¬p ∧ ¬q
~(A ∪ B) = ~A ∩ ~B
~(A ∩ B) = ~A ∪ ~B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 76
Propriedade Lógica Teoria dos Conjuntos
Elemento Neutro p ∧ V ⇔ p
p ∨ F ⇔ p
A ∩ U = A
A ∪ ∅ = A
Elemento Absorvente p ∧ F ⇔ F
p ∨ V ⇔ V
A ∩ ∅ = ∅
A ∪ U = U
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 77
♦ Importante exercício proposto no Capítulo 2
• qq dos conetivos ¬, ∧, ∨, → e ↔
∗ pode ser expresso usando somente ¬ e ∧
• importante em diversas aplicações da Computação e Informática
∗ exemplo: Técnicas Digitais
• mesmo resultado vale para a Álgebra de Conjuntos
∗ usando somente ~ e ∩
• exercício:
∗ como → e ↔ podem ser expressos na Álgebra de Conjuntos?Matemática Discreta para Ciência da Computação - P. Blauth Menezes 78
♦ Relações Lógicas × Relações sobre Conjuntos
Relação Lógica Teoria dos Conjuntos
Implicação/Continência p ⇒ p A ⊆ B
Equivalência/Igualdade p ⇔ q A = B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 79
♦ Como visto no Capítulo 2
• p(x) é uma proposição p tq descreve alguma propriedade de x ∈ U
♦ Lógica × Teoria dos Conjuntos
• A = { x  p(x) } e B = { x  q(x) }
∗ A ⊆ B se e somente se (∀x ∈ U) (p(x) ⇒ q(x)) continência
∗ A = B se e somente se (∀x ∈ U) (p(x) ⇔ q(x)) igualdade
• exemplo
∗ A = U se e somente se (∀x ∈ U) (p(x) ⇔ V) universo
∗ A = ∅ se e somente se (∀x ∈ U) (p(x) ⇔ F) vazio
• Justifica o fato de que qq continência ou igualdade
∗ decorrência de alguma implicação ou igualdade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 80
♦ Correlação entre Lógica e Álgebra de Conjuntos
• não é casual
• ambas são um caso particular de uma álgebra abstrata
∗ denominada Álgebra de Boole
∗ vista adiante
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 81
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 82
3.7 Álgebra de Conjuntos nas
Linguagens de Programação
♦ Já discutido: nem toda linguagem de programação
• possui boas facilidades para tratar conjuntos
♦ Pascal (lembrando)
• tipos de dados baseados em conjuntos finitos
• variáveis conjuntos sobre estes tipos de dados
• constantes conjuntos (também finitos)
♦ Pascal: operações não-reversíveis sobre conjuntos:
• união: +
• intersecção: * 
• diferença: - 
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 83
Exp: Trechos de Programas em Pascal
Suponha o tipo de dados
dias_semana = set of (seg, ter, qua, qui,
sex, sab, dom)
variáveis
feriado, trabalho, feriado_trabalho,
úteis, parados: dias_semana
trechos de programas
feriado := [qua, sab]
trabalho := [seg,…, sex]
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 84
Os trechos de programas em Pascal
feriado_trabalho := trabalho * feriado
úteis := trabalho – feriado
parado := [sab, dom] + feriado
correspondem, na Teoria dos Conjuntos
• feriado_trabalho = trabalho ∩ feriado { qua }
• úteis = trabalho – feriado { seg, ter, qui, sex }
• parado = { sab, dom } ∪ feriado { qua, sab, dom }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 85
Exp: Programa Completo em Pascal
Programa capaz de ler uma linha de texto e determinar o número de
• vogais
• consoantes
• outros símbolos
• total de caracteres lidos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 86
program numero_caracteres(input, output);
type
alfabeto = set of ‘a’..’z’;
var
n_vogais, n_consoantes, n_outros,
total: integer;
vogais, consoantes: alfabeto;
caractere: char;
begin
vogais := [‘a’, ‘e’, ‘i’, ‘o’, ‘u’];
consoantes := [‘a’..‘z’] – vogais;
n_vogais := 0;
n_consoantes := 0;
n_outros := 0;
read(caractere);
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 87
while not eoln
do begin
if caractere in vogais
then n_vogais := n_vogais + 1
else if caractere in consoantes
then n_consoantes := n_consoantes + 1
else n_outros := n_outros + 1;
read(caractere)
end;
total := n_vogais + n_consoantes + n_outros;
writeln(‘vogais = ’, n_vogais);
writeln(‘consoantes: ’, n_consoantes);
writeln(‘outros símbolos: ’, n_outros);
writeln(‘total de símbolos: ’, total)
end.
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 88
♦ Construções similares a do produto cartesiano
• reversíveis
∗ arranjos (arrays)
∗ registros (records)
• abordagem mais adequada
∗ quando do estudo do conceito de função
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 89
3 – Álgebra de Conjuntos
3.1 Introdução
3.2 Diagramas de Venn
3.3 Paradoxo de Russell
3.4 Operações Não-Reversíveis
3.4.1 União
3.4.2 Intersecção
3.5 Operações Reversíveis
3.5.1 Complemento
3.5.2 Conjunto das Partes
3.5.3 Produto Cartesiano
3.5.4 União Disjunta
3.6 Relação entre Lógica e Álgebra de Conjuntos
3.7 Álgebra de Conj. nas Linguagens de Programação
3.8 Álgebra de Conj. e Teoria da Computação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 90
3.8 Álgebra de Conjuntos e Teoria da
Computação
♦ Álgebra de Conjuntos
• fundamental no estudo da Teoria da Computação
♦ Teoria da Computação
• meios para correta aplicação e entendimento dos conceitos de
∗ algoritmo
∗ computabilidade
∗ conseqüentemente, do que é solucionável em um computador
• conceitos mínimos que qq estudante necessita saber
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 91
♦ Lembre-se: linguagem (formal) L sobre alfabeto ∑
L ⊆ ∑*
♦ Complemento da linguagem L
~L = { x ∈ ∑*  x ∉ L }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 92
Exp: Complemento de Linguagens
Linguagens sobre ∑ = { a, b }
• L1 = { ε }
• L2 = { a }* = { ε, a, aa, aaa,… }
• Palíndromos = { ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,… }
Complementos das linguagens
• ~L1 = { a, b, aa, ab, ba, bb, aaa,… }
• ~L2 = { b, ab, ba, bb, aab, aba, baa, abb, bab, bba, bbb,… }
• ~Palíndromos = { x ∈ ∑*  x ∉ Palíndromos }
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 93
Obs: Reconhecimento de Linguagens × Complemento
Lembre-se: compilador é um software
• traduz um programa escrito na linguagem de programação
• para um código executável no sistema computador.
• estruturado em análise e síntese
∗ análise é responsável pelo reconhecimento da linguagem
∗ verifica se um programa p válido para a linguagem L
p ∈ L
• se p ∈ L, passa para a síntese
• se p ∉ L, alertar o programador (correção do programa!)
• portanto, a análise de um compilador verifica se
p ∈ L ou p ∈ ~L
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 94
Obs: Hierarquia de Linguagens e Problema da Parada
Importante assunto da Teoria da Computação
• limites do que é possível computar em um computador
Capítulo 2 – Lógica e Técnicas de Demonstração
• Máquina de Turing: formalização do conceito de algoritmo
Limite do que é possível reconhecer
• existe uma Máquina de Turing que reconhece
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 95
Nesse contexto: linguagens são agrupadas em classes
• hierarquia (continência própria)
 Linguagens
Recursivas
(existe um algoritmo
capaz de responder
"pertence" ou "não pertence")
 Linguagens Enumeráveis Recursivamente
(existe um algoritmo
capaz de responder "pertence")
Universo de Todas as Linguagens
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 96
♦ Linguagens Recursivas
• existe um algoritmo (Máquina de Turing) que sempre pára
• capaz de determinar se
p ∈ L ou p ∈ ~L
MT(L)p
∈
∉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 97
♦ Linguagens Enumeráveis Recursivamente
• existe um algoritmo (Máquina de Turing)
• capaz de determinar se p ∈ L
• entretanto, se p ∈ ~L, o algoritmo pode
∗ parar identificando que p ∈ ~L
∗ ficar em loop infinito
MT(L)p
∈
∉ ou
LOOP
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 98
♦ Contradiz a intuiçãopois estabelece que
 reconhecer o complemento de uma linguagem pode ser
impossível, mesmo que seja possível reconhecer a linguagem
♦ Linguagens Não-Computáveis
• não existe algoritmo (Máquina de Turing) capaz de determinar se
p ∈ L ou p ∈ ~L
♦ Problema da Parada
• se qq Máquina de Turing pára determinando se p ∈ L ou p ∈ ~L
∗ não tem solução computacional
• baseado nesse resultado prova-se
∗ inúmeros problemas não possuem solução computacional
∗ inclui muitos problemas interessantes e importantes para CC
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 99
Teorema: Complemento de Ling. Recursiva é Recursiva
Se L sobre ∑ é recursiva, então ~L também é recursiva
Prova: (direta)
Suponha L linguagem recursiva sobre ∑
Então existe Máquina de Turing MT(L) que aceita L e sempre pára
MT(L)p
Inverte
∈
∉
∈
∉
MT'(L)
Inverte ∈
∉
∈
∉
Portanto, o complemento de uma linguagem recursiva é recursiva
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 100
Teorema: Intersecção de Ling. Recursivas é Recursiva
Se L1 e L2 sobre ∑ são recursivas, então L1 ∩ L2 também é recursiva
Prova: (direta)
Suponha L1 e L2 linguagens recursivas sobre ∑
Então existem Máquinas de Turing MT(L1) e MT(L2) tq aceitam L1 e L2
e sempre param
MT(L1)
p
∉
∈
∉
MT(L1∩L2)
∈
MT(L2)
∉
Portanto, a intersecção de duas linguagens recursivas é recursiva
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 101
♦ Outros resultados (exercícios)
• união de duas linguagens recursivas é recursiva
• complemento de uma linguagem enumerável recursivamente não
necessariamente é enumerável recursivamente
• uma linguagem é recursiva sss a linguagem e seu complemento
são enumeráveis recursivamente
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 102
Matemática Discreta para Ciência da Computação
P. Blauth Menezes
1 Introdução e Conceitos Básicos
2 Lógica e Técnicas de Demonstração
3 Álgebra de Conjuntos
4 Relações
5 Funções Parciais e Totais
6 Endorrelações, Ordenação e Equivalência
7 Cardinalidade de Conjuntos
8 Indução e Recursão
9 Álgebras e Homomorfismos
10 Reticulados e Álgebra Booleana
11 Conclusões
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 103
Matemática Discreta para
Ciência da Computação
P. Blauth Menezes
blauth@inf.ufrgs.br
Departamento de Informática Teórica
Instituto de Informática / UFRGS