Upload
ayrton-jose-lopes
View
297
Download
33
Embed Size (px)
Citation preview
1
2) INTRODUÇÃO E CONCEITOS DE TEORIA DOS CONJUNTOS
1. INTRODUÇÃO.
2. EXPRESSÕES E TERMOS INDEFINIDOS.
3. AXIOMAS, DEFINIÇÕES.
4. DETERMINAÇÕES DE CONJUNTO.
5. PERTINÊNCIA.
6. REPRESENTAÇÕES.
7. DETERMINADOS CONJUNTOS IMPORTANTES.
8. ALFABETOS, PALAVRAS, LINGUAGENS. CONJUNTOS EM LINGUAGEM DE PROGRAMAÇÃO.
1. AS NOTAÇÕES E LINGUAGEM DA MATEMÁTICA
2. INTRODUÇÃO À TEORIA DOS CONJUNTOS
3. DETERMINAÇÃO DE UM CONJUNTO
4. CONJUNTO FUNDAMENTAL
5. CONJUNTO UNITÁRIO E FAMÍLIA DE CONJUNTOS
6. CONJUNTO VAZIO
7. INCLUSÃO DE CONJUNTOS E IGUALDADE ENTRE CONJUNTOS
8. CONJUNTO DAS PARTES DE UM CONJUNTO FINITO (CONJUNTO DE POTÊNCIA)
9. CONJUNTOS DISJUNTOS
10. REPRESENTAÇÕES E ILUSTRAÇÕES
11. TEORIA DE CONJUNTOS E CIÊNCIA DA COMPUTAÇÃO
12. ALFABETOS, PALAVRAS, LINGUAGENS.
REFERÊNCIAS PARA O TÓPICO
2
1 – AS NOTAÇÕES E LINGUAGEM DA MATEMÁTICA
Essa breve discussão sobre a relevância da notação e da linguagem da Matemática é
baseada no excelente texto de Daniel Cordeiro de Morais Filho (MORAIS FILHO, 2012).
O ensino e a aprendizagem da Matemática são intrinsecamente relacionados com a
linguagem matemática, que consiste da linguagem natural e da linguagem simbólica. Na
linguagem matemática a língua materna e a linguagem simbólica interagem para
comunicar as mensagens.
Apesar de universal, de generalizar e de tornar mais simples e direta a exposição e o
desenvolvimento de pensamentos e ideias, a linguagem matemática tem características
peculiares, destacando-se entre elas a precisão e a concisão.
Como qualquer língua natural, a linguagem matemática também possui sua gramática,
sua morfologia (estudo da formação e da estrutura das palavras) e sua sintaxe (estudo
da disposição lógica das palavras nas frases, das frases no discurso e da relação das
frases entre si), que devem ser conhecidos e entendidos para que ocorra uma
comunicação com eficiência e precisão.
Para que servem as notações matemáticas? Uma notação matemática é um conjunto de
símbolos − podendo ser um único símbolo − que representa um objeto, conceito ou
idéia matemática. Esses símbolos podem ser construídos com letras de algum alfabeto,
com algarismo de um sistema de numeração, com figuras representativas, entre outras
opções.
Porém, uma notação matemática requer ter as seguintes características:
1. Deve ser uma forma de comunicação concisa e precisa que contribui para a facilidade
e para a economia da linguagem.
2. Não deve expressar ambigüidades.
3
3. Na medida do possível, deve ter uma foram estética simples, fácil de ser manipulada,
de ser memorizada e no fazer lembrar o objeto ou conceito matemática, toda vez
que é vista.
Lembrando que, em algumas ocasiões, a linguagem matemática se reduz à manipulação
de símbolos, e, portanto, deve-se ter em conta que a escolha de uma notação adequada e
eficaz é um primeiro e grande passo a fim de expressar e manusear os conceitos e
operações matemáticas com eficiência. As notações são tão importantes para a
compreensão de um texto, que muitos deles trazem um índice com as principais
notações utilizadas naquele texto.
Observação 01: Embora atualmente o uso de notações em textos técnicos das mais
variadas áreas seja um fato corriqueiro, este é um processo que levou um longo tempo
para ser sistematizado e tornado prático e de amplo e disseminado uso. São mais de
3.000 anos de história para que isso ocorresse.
Exemplo 01: Um exemplo para o uso da notação matemática e simbólica é a conhecida
regra de integração do trapézio generalizada, que é apresentada como:
[ ]
+
+= =
−
−
=
= +
= + + + + +
= + +
∑ ∑∫
∑
⋯
k 1
k
n nx
1 k k 1xk 0 k 0
0 1 2 n 1 n
n 1
0 n kk 1
hp (x)dx (f(x ) f(x )
2
hf(x ) 2[f(x ) f(x ) f(x )] f(x )
2h
f(x ) f(x ) 2 f(x )2
Alguns cuidados com o uso das notações devem ser tomados. As principais indicações
são de:
a) Usar a notação mais consagrada ou usada ou aquela proveniente de fontes com boa
reputação e credibilidade.
b) Feita a opção, permaneça fiel à sua escolha, e não a modifique ao longo do texto que
está produzindo.
4
c) Se inventar as suas próprias notações, lembre-se de levar em consideração que uma
notação matemática deve atender as características citadas anteriormente.
Algumas das mais populares notações, que serão eventualmente discutidas ao longo
deste texto são como na tabela 1.
Tabela 1: Tabela de notações frequentemente utilizadas.
Símbolo Como se lê Símbolo Como se lê
∃∃∃∃ Existe. Existe um. Existe pelo
menos um
∀∀∀∀ Para todo. Qualquer que seja.
Para cada.
∃∃∃∃! Existe um único. Existe um e
apenas um. Existe um só.
<<<< Menor (do que).
≤≤≤≤ Menor (do que) e igual a >>>> Maior (do que).
≥≥≥≥ Maior (do que) e igual a ≡≡≡≡ Equivalente a. Côngruo a.
≅≅≅≅, ≈≈≈≈ Aproximadamente igual a ⇔⇔⇔⇔ Equivalente logicamente.
∑∑∑∑ Somatório ∴∴∴∴ Então. Portanto. Logo. Donde.
∏∏∏∏ Produtório ⇒⇒⇒⇒ Implica. Acarreta.
∞∞∞∞ Infinito. ∪∪∪∪ União. Reunião.
⊂⊂⊂⊂ Está contido. ∩∩∩∩ Intersecção.
∈∈∈∈ Pertence. ππππ Número pi.
=: , ≡def
Por definição. e Número de Euler.
Observação 02: Para a maioria dos símbolos existe uma justificativa histórica para seu uso
e denominação. Por exemplo, o símbolo ∀∀∀∀, que designa o quantificador universal,
decorre da letra “A” invertida, inicial das palavras “all” do Inglês e “allgemein” do
Alemão, que significam, respectivamente “todo”. A constante ππππ, o número mais
conhecido da Matemática, provêm da primeira letra da palavra “perímetro” em grego,
que é escrita como περίμετρος.
5
Um alfabeto amplamente utilizado para representar objetos matemáticos é o alfabeto
grego, cujas letras podem assumir distintos e variados significados, dependendo da área
em que são utilizadas. O alfabeto grego é apresentado na tabela 2.
Tabela 2: O alfabeto grego.
Minúscula Maiúscula Escreve / lê Minúscula Maiúscula Escreve / lê
αααα ΑΑΑΑ Alfa / alfa νννν ΝΝΝΝ Nu / ni ou nu
ββββ ΒΒΒΒ Beta / beta ξξξξ ΞΞΞΞ Ksi / kiçi
γγγγ ΓΓΓΓ Gama / gama οοοο ΟΟΟΟ Omicron / ómicron
δδδδ ∆∆∆∆ Delta / délta ππππ ou ϖϖϖϖ ΠΠΠΠ Pi / pi
εεεε ΕΕΕΕ Epsílon / epsílson ρρρρ ΡΡΡΡ Ro / ro
ζζζζ ΖΖΖΖ Zeta / dzéta σσσσ ΣΣΣΣ Sigma / sigma
ηηηη ΗΗΗΗ Êta / êta ττττ ΤΤΤΤ Tau / táu
θθθθ ΘΘΘΘ Teta / téta υυυυ ΥΥΥΥ Upsilon / imsílon
ιιιι ΙΙΙΙ Iota / ióta φφφφ ou ϕϕϕϕ ΦΦΦΦ Fi / fi
κκκκ ΚΚΚΚ Kapa / kápa χχχχ ΧΧΧΧ Khi / ki
λλλλ ΛΛΛΛ Lambda / lâmbda ψψψψ ΨΨΨΨ Psi / psí
µµµµ ΜΜΜΜ Um / mi ou mu ωωωω ΩΩΩΩ Ômega / ômega
Veja tudo isso em detalhes e muito mais na referência citada, (MORAIS FILHO, 2012).
Também é relevante conhecer preliminarmente alguns conceitos e terminologias que
são básicos na discussão do dia a dia da disciplina. Embora isso seja feito no
desenvolvimento das temáticas da LMD, antecipa-se alguma nomenclatura destacando:
1. Uma proposição ou um teorema (ou sentença ou frase) é um conjunto de palavras ou
símbolos que exprimem uma afirmação de modo completo. A partir dos fatos
elencados na proposição, se verdadeiros, é possível verificar a veracidade da conclusão
da sentença.
6
2. Lema e corolário são proposições. Lema geralmente é uma proposição “técnica” que
auxilia na demonstração do teorema. Corolário é uma situação particular ou específica
do teorema.
3. Um axioma ou postulado é uma sentença ou afirmação que não pode ou não requer
ser demonstrada. É considerada como consenso inicial necessário à construção ou
aceitação de uma teoria, sendo aceito como verdadeira.
4. Uma definição é uma especificação não contraditória ou não ambígua que
estabelece o significado de um conceito ou de um objeto matemático.
5. Uma conjetura é uma idéia, fórmula ou argumento, a qual não foi provada ser verdadeira
matematicamente, e é baseada em suposições ou idéias com fundamento empírico,
experimental ou lógico.
6. Uma hipótese é conjunto de suposições (afirmações) assumidas serem verdadeiras. Uma
tese é o resultado esperado, a demonstração da proposição, que decorre logicamente
das hipóteses e dos argumentos ai empregados. Assim, uma hipótese é um conjunto de
suposições que se admite serem verdadeiras, e a tese é o que se conclui como
conseqüência lógica das hipóteses e dos desenvolvimentos realizados.
7. Uma demonstração é uma seqüência de argumentos válidos cujas premissas são
verdades estabelecidas (hipóteses consistentes e válidas).
8. Um argumento é uma seqüência de proposições (ou enunciados), no qual uma das
proposições é a conclusão e as demais são as premissas, e que servem para formar
alguma “evidência” para a conclusão.
2 – INTRODUÇÃO
A teoria dos conjuntos, que foi considerada pelo matemático David Hilbert como “o
produto mais extraordinário do pensamento matemático, uma das mais belas realizações
da atividade humana no domínio do puramente inteligível”, foi à criação, sobretudo, do
matemático russo George Cantor.
7
Sem tanta “ênfase” como Hilbert, já que a Teoria dos Conjuntos perdeu significativa
importância com o (felizmente) final do Movimento da Matemática Moderna, ainda se
pode dizer que a teoria tem relevante interesse à Matemática, sobretudo como padrão
de escrita e representação matemática.
No capítulo 1 de (ABE, PAPAVERO, 1992) “Teoria Intuitiva dos Conjuntos” apresenta-se
uma pequena história da criação da teoria dos conjuntos, bem como sua importância e
aplicação a alguma das Ciências. Várias versões podem ser encontradas na WEB, e alguns
exemplos são:
• http://pt.wikipedia.org/wiki/Teoria_dos_conjuntos.
• http://www.smmmfloripa.ufsc.br/soares_art.pdf.
• http://www.ipv.pt/millenium/millenium34/16.pdf.
• Entre outros mais.
Para iniciar uma discussão é bom saber que a noção de conjunto não é suscetível de
definição a partir de noções mais simples. Ou seja, conjunto é uma noção primitiva,
introduzida de modo explícito por George Cantor. Intuitivamente, sob a designação de
conjunto entende-se:
• Toda coleção bem definida de objetos, não importa de que natureza, ou.
• Coleção de elementos suscetíveis de possuírem certas propriedades e de terem entre
si, ou com elementos de outros conjuntos, certas relações, ou.
• O agrupamento em um todo de objetos, bem definidos e discerníveis, de nossa
percepção ou de nosso entendimento, chamados elementos do conjunto.
Exemplo 02: Assim, seriam exemplos de conjuntos:
• O conjunto dos livros de uma biblioteca.
• As vogais do alfabeto: a, e, i, o e u.
• Os alunos que faltam às aulas.
8
Essa abordagem de “não ser suscetível de definição” é o ponto de partida da abordagem
axiomática. Um exemplo notável e usual de uma área da Matemática que a utiliza é a
Geometria Euclidiana, onde o ponto de partida para a construção dos fundamentos da
teoria é tomar conceitos não definidos denominados conceitos primitivos. Mais
especificamente, em um desenvolvimento axiomático de uma Teoria Matemática
qualquer, inicia-se com:
a) Termos indefinidos.
b) Relações indefinidas.
c) Axiomas relacionando os termos indefinidos e as relações indefinidas.
Considerando-se os conceitos primitivos pode-se desenvolver a teoria construindo
definições, teoremas, proposições, aplicações, etc.
Exemplo 03: Um desenvolvimento Axiomático de Geometria Euclidiana plana tem-se:
• São termos indefinidos: ponto, reta, incidente, estar entre.
• Uma relação indefinida é: ponto em uma reta.
• Exemplos de axiomas são:
a) Qualquer que seja a reta existe pontos que pertencem à reta e pontos que não
pertencem à reta.
b) Dados dois pontos distintos existe uma única reta que contém estes pontos.
Analogamente, em um desenvolvimento axiomático (intuitivo) da Teoria dos Conjuntos
considera-se:
a) Termos indefinidos: “elementos” e “conjunto”.
b) Relação indefinida: “elemento pertence a um conjunto” e nesse caso a relação de
pertinência entre elemento e conjunto é dada pela expressão “pertence a”.
c) Dois axiomas, que podem ser especificados como definições, são (HALMOS, 1960):
A1) Axioma de Extensão: Seja X um conjunto. X é completamente determinado pelo
conhecimento dos elementos que pertencem a X .
9
A2) Axioma de Especificação: Seja P(x) uma sentença qualquer e seja X um conjunto.
Existe um conjunto = ∈X x;x X;p(x)é verdadeiro .
Tais conceitos primitivos são relevantes ao desenvolvimento de conteúdos de nosso
interesse imediato, Outros mais podem ser especificados quando necessário.
Observação 03: Existem outros axiomas, mas eles não serão discutidos, dado que a
abordagem de Teoria dos Conjuntos é, no nosso caso, dita informal ou intuitiva.
a) Assim, a Teoria dos Conjuntos aqui apresentada é axiomática no sentido em que se
enuncia e se empregam alguns axiomas de modo a servirem de base para os
conceitos e proposições subseqüentes.
b) Mas é informal (ou intuitiva) no sentido em que a linguagem e a notação empregadas
são aqueles da linguagem natural e não sintática. Uma abordagem mais rigorosa pode
ser vista em “Introdução aos Fundamentos Axiomáticos da Ciência” de Décio Krauser
(KRAUSE, 2002).
Mesmo nessa abordagem axiomática os conceitos primitivos não suscetíveis de
especificação precisa são:
1. Conjunto (ou classe ou coleção ou sistema).
2. Elemento (ou objeto ou membros).
3. A relação de pertinência, entre elemento e conjunto, dado por “pertence a”.
Observação 04: As notações tradicionais para conjunto, elemento e de pertinência, e seus
símbolos são descritos considerando que:
a) Um conjunto é denotado por uma letra latina maiúscula: X,Y,..., A,B,...
b) Os elementos que constituem um conjunto são denotados por letras latinas
minúsculas: x,y,...,a,b,...
c) Ao conjunto X , cujos ou elementos são 1 2x ,x ,... é denotado por = 1 2X x ,x ,... , que se
lê: “ X é o conjunto cujos elementos são 1 2x ,x ,... ”.
10
d) Para indicar que o objeto x pertence ou não a coleção X escreve-se, simbolicamente,
que ∈x X para dizer que “o elemento x pertence ao conjunto X ” ou “x pertence a
X ”. E para dizer que o elemento não pertence ao conjunto, cuja sentença é
simbolizada por ∉x X , escreve-se “o elemento x não pertence ao conjunto X ” ou “x
não pertence a X ”. É a negação da sentença ∈x X .
e) Os símbolos para os quantificadores universal ∀ (qualquer que seja ou para todo) e
existencial ∃ (existe algum ou existe pelo menos um) são empregados para
caracterizarem a relação entre os elementos e sua coleção como, por exemplo,
= ∀X x;p(x) .
3 – DETERMINAÇÃO DE UM CONJUNTO
Um conjunto é bem determinado (ou especificado ou definido ou caracterizado) quando
se sabe quais os elementos que o constituem. Um conjunto pode ser especificado
segundo os axiomas A1 e A2, dos seguintes modos:
1. Por extensão (ou enumeração): O conjunto é determinado pela designação de seus
elementos através da sua enumeração ou listagem, e os elementos são indicados
entre chaves: =X ... .
2. Por especificação (ou caracterização): O conjunto é determinado por uma
característica ou atributo de pertinência tal que um elemento x pertence ao conjunto
X , se x verifica uma proposição característica. Ou seja, o conjunto dos elementos x
que tem a propriedade P é designado por p(x);x tal que x tem a propriedade P .
Exemplo 04: São exemplos de conjuntos numéricos especificados por extensão ou
enumeração:
• ≡ℕ Conjunto dos números naturais = 0,1,2,... .
• ≡ℕ* Conjunto dos números naturais não nulos = 1,2,... .
• ≡ℤ Conjunto dos números inteiros = − −..., 2, 1,0,1,2,... .
• ≡ℤ* Conjunto dos números inteiros não nulos = ± ± 1, 2,...
• ≡ℚ Conjunto dos números racionais = ∈ ∈ℤ ℤ*a b;a e b .
11
• ≡ℝ ℚ/ Conjunto dos números irracionais = números decimais não finitos e não
periódicos.
• ≡ℝ Conjunto dos números reais = racionais e irracionais.
Exemplo 05: Exemplos de conjuntos que podem ser definidos pela sua propriedade
característica (considerando a notação “ ; ” para “tal que”) são:
• =ℕ x;x é um número natural .
• ≡ℕ x;x* é um número natural e diferente de zero .
• =ℤ x;x é um número inteiro .
• =ℤ* x;x é um número inteiro e diferente de zero .
ou, equivalentemente, com as notações de Lógica (como veremos) e usando a
simbologia ; para designar “tal que” e ∈ para designar “pertence a”, tem-se:
• =ℕ x;x é natural .
• = ∈ ∧ ≠ℕ ℕ* x;x x 0 .
• = ∈ ∧ ≠ℤ ℤ* x;x x 0 .
• = = ∈ ∧ ∈ℚ *x a b;a Z b Z .
Observação 05: Note-se que um conjunto X diz-se caracterizado (ou especificado)
quando se dá uma regra que permita decidir sem ambiguidade se um elemento
arbitrário x pertence ou não ao conjunto X .
Assim, em um conjunto definido por enumeração, a ordem dos elementos é indiferente,
mas cada elemento deve figurar uma única vez. Uma definição conjuntista para um
elemento é como:
≡def
x,x x .
que não deve ser confundido com a notação de par ordenado!
4 – CONJUNTO FUNDAMENTAL
12
As noções “elemento” e “conjunto” tem significado relativo, pois um mesmo ente
matemático pode ser elemento em relação a certos entes matemáticos e ser conjunto em
relação a outros entes.
• Por exemplo, uma reta é um elemento do conjunto de todas as retas, mas também é
um conjunto de pontos.
Cumpre-se, portanto, tornarem preciso quais são os entes matemáticos considerados
com o elemento a fim de evitar paradoxos como o de Russel, que pode ser enunciado
como:
Seja Z o conjunto de todos os conjuntos que não contém a si mesmo como membro. Então Z
contém ou não a si mesmo? Ou, em outras palavras:
Uma cidade tem um barbeiro que faz a barba de todos os homens que a si
próprio não se barbeiam. Pergunta-se quem faz a barba do barbeiro.
O paradoxo de Russel surge quando se admite que exista o “conjunto de todos os
conjuntos”. Para evitar o surgimento de paradoxos, que levou a uma crise na Teoria dos
Conjuntos, sendo necessária uma cuidadosa fundamentação axiomática nesta teoria. A
abordagem axiomática mais comum na Teoria dos Conjuntos é a de Zermelo-Fraenkel
(ZFC).
Veja (CONIGLIO, 1997) para detalhes e discussões, pois uma abordagem com este
escopo não pode ser aqui realizada. De modo mais modesto admite-se apenas que não
existe o “conjunto de todos os conjuntos”, e se admite a existência de um conjunto ao
qual pertencem todos os elementos com os quais se está trabalhando. Esse conjunto é o
conjunto fundamental.
Definição 01: Diz-se conjunto fundamental de uma teoria ao conjunto de todos os entes
matemáticos que são sempre considerados como elementos dessa teoria. Esse conjunto
é chamado de conjunto fundamental da teoria (e representado geralmente por U ).
13
Exemplo 06: Dado o conjunto = < <U x;1 x 4 , então:
• Se =ℝU então ∈ ∧ < <ℝx;x 1 x 4 é o conjunto dado (que é infinito).
• Se =ℕU então ∈ ∧ < < =ℕx;x 1 x 4 2,3 é o conjunto dado (que é finito).
Observação 06: No conjunto fundamental U , o conjunto X dos elementos x que
verificam a condição p(x) (ou satisfazem a proposição p(x) ) é indicado por:
= ∈ ∧X x;x U p(x) ou = ∈X x U;p(x) .
5 – CONJUNTO UNITÁRIO E FAMÍLIA DE CONJUNTOS
Considerando-se que em um conjunto bem especificado a ordem dos elementos é
indiferente, mas cada elemento deve figurar uma única vez, ou seja, define-se que se
∈1 2x x então =1 2x x . Tal conjunto denomina-se conjunto unitário determinado pelo
elemento 2x . Veja em (ABE, PARAVERO, 1992), página 21 outro processo de introduzir o
conjunto unitário. Assim:
Definição 02: Diz-se ser conjunto unitário a aquele conjunto X constituído de um único
elemento x , e escreve-se =X x .
Observação 07: É importante, portanto, notar que um conjunto unitário é diferente que o
elemento que o determina.
• Por exemplo: ∈3 3 , mas ≠3 3 .
Definição 03: Um conjunto cujos elementos também são conjuntos diz-se ser uma
família (ou conjunto de conjuntos) de conjuntos ou uma coleção de conjuntos.
Exemplo 07: Exemplos de conjunto unitário e família de conjunto são:
• O conjunto ∈ − + = =ℝ 2x ;x 6x 9 0 3 é um conjunto unitário.
14
• O conjunto 2,3,2,5,6 é uma família cujos elementos são os conjuntos
2,3,2,5,6 .
6 – CONJUNTO VAZIO
Nota-se que o conjunto =X x;x tem a propriedade P é definido pela propriedade P .
Porém às vezes ocorre que nenhum elemento de X é caracterizado por tal propriedade P
e, portanto, nesse caso o conjunto =X x;x tem a propriedade P não possui elemento
algum. Daí tem-se:
Definição 04: Diz-se ser o conjunto vazio, denotado por ∅ ou por , aquele conjunto
tal que qualquer que seja o elemento x , tem-se ∉∅x .
Observação 08: Da definição de conjunto vazio pode-se, alternativamente, “defini-lo”
alternativamente como:
1. ≠ =∅x;x x .
2. ∧¬ =∅x;p(x) p(x) .
Essas especificações decorrem de princípios da Lógica Matemática, como será discutido
na seção apropriada.
LISTA DE EXERCÍCIOS 01: Fazer os exercícios das páginas 29-30 de (ABE, PARAVERO, 1992).
7 – INCLUSÃO DE CONJUNTOS E IGUALDADE ENTRE CONJUNTOS
Dados dois conjuntos X e Y, pode-se ter que todo elemento de X é, também, elemento de
Y. Ou seja, X pode ser parte de Y. Desse modo tem-se:
Definição 05: Um conjunto X é dito ser subconjunto de Y quando todo elemento de X é
também elemento de Y . Para indicar isso se usa a relação ⊂X Y .
Simbolicamente, do ponto de vista da Lógica Matemática, escreve-se:
15
⊂ ≡ ∀ ∈ → ∈def
X Y ( x)(x X x Y) ,
que se lê “ X está contido em Y se qualquer x , se x pertence a X então x pertence a
Y ”.
Observação 09: Neste caso, quando ⊂X Y , diz-se também que X é parte de Y , ou que X
está incluído em Y , ou X está contido em Y ou, ainda, Y contém X .
• E, neste caso a negação de ⊂X Y é indicada por ⊄X Y e isso significa que existe
∃ ∈ ∉x X;x Y .Ou seja, do ponto de vista da Lógica Matemática escreve-se:
⊄ ≡ ∃ ∈ ∧ ∉def
X Y ( x)(x X x Y)
Exemplo 08: Exemplos de inclusões entre conjuntos são
• ⊂3,4 3,4 .
• ⊂3,4 6,4,3 (a ordem dos elementos não é importante).
• ⊂3,4 4,3 .
• ⊂ ⊂ℕ ℤ ℚ .
Observação 10: Note-se no exemplo 07 que = = =X 3,4 4,3 Y . Ou seja, quando ⊂X Y
não se exclui a possibilidade de se ter =X Y . Mas se ⊂X Y e existe um elemento que
pertence a Y e não pertence a X diz-se que X é uma parte própria de Y . Algumas vezes
se diz que ou X está contido propriamente em Y ou que Y contém propriamente X .
Assim, se tem:
Definição 06: Seja ⊂X Y com ≠X Y . Nesse caso diz-se que X é uma parte própria ou X é
um subconjunto próprio de Y .
Simbolicamente, do ponto de vista da Lógica Matemática, tem-se:
⊂ ∧ ≠ ≡ ∈ → ∈ ∧ ∈ ∧ ∉def
X Y X Y (x X x Y) (x Y x X)
Ou, alternativa e equivalentemente: ⊂ ∧ ⊄ ≡ ∃ ∈ ∧ ∉def
X Y Y X ( x)(x Y x X) .
16
Observação 11: Algumas vezes “ X é um subconjunto (podendo ser igual) qualquer de Y ”
é representado por ⊆X Y e “ X é um subconjunto próprio de Y ” é representado por
⊂X Y .
• A definição de parte própria, poderia ser como aquela dada em (ABE, PARAVERO,
1992): Seja ≠∅Y . Diz-se que ⊂X Y é uma parte própria de Y se ≠∅X e ≠X Y .
• Note-se, então, que o conjunto ∅ e qualquer conjunto unitário =X x não possuem
partes próprias.
Exemplo 09: Exemplos para esclarecer a definição são como:
• A relação de inclusão ⊂3,4 6,4,3 mostra que 3,4 é um subconjunto próprio de
6,4,3 .
• Porém o mesmo não ocorre com ⊂3,4 3,4 .
Das definições de conjunto vazio (definição 04) e de subconjunto (definição 05) e tem-se
o seguinte resultado.
Proposição 01: Sejam o conjunto vazio ∅ e um conjunto X qualquer. Então:
a) O conjunto vazio ∅ é subconjunto de qualquer conjunto X , isto é, ∅⊂ ∀X, X .
b) O conjunto ∅ é único.
Prova:
a) Suponha por contradição que isso não é verdade, isto é, que ∅⊄ X . Então deve
existir um ∈∅x tal que ∉x X já que ∅⊄ ≡ ∃ ∈∅∧ ∉def
X ( x)(x x X) (da observação 09).
Porém, da definição de conjunto vazio tem-se ∀ ∉∅x, x , e então se tem um absurdo
lógico, pois não existe elemento algum no conjunto vazio, por definição. Esse
absurdo foi gerado pelo fato de se tomar como verdadeira que ∅⊄ X , logo essa
suposição não é verdadeira, só restando que ∅⊂ X seja qual for o conjunto X .
Uma prova alternativa, decorrente da Lógica Matemática, poderia ser como:
17
Como a sentença ( ∈∅x ) é falsa então a sentença ( ∈∅→ ∈x x X ) é verdadeira,
decorrente da tabela verdade da condicional. Então ( )∅⊂ ≡ ∀ ∈∅→ ∈def
X ( x) x x X é
verdadeiro seja qual for o conjunto X .
• Uma condicional (SE...ENTÃO,→→→→) de duas proposições é falsa se e somente se
p é verdadeira e q é falsa. A tabela-verdade para a fórmula p →→→→ q é como:
p q p → q
V V V
V F F
F V V
F F V
b) Suponha que existam dois conjuntos tais que =∅X e =∅Y . Deve-se provar que
=X Y o que mostraria a unicidade do conjunto vazio, já que X e Y são conjuntos
arbitrários. Seja ∈x X então a sentença ∈ → ∈x X x Y é verdadeira (V), pois ∈x X é
sempre falso (F). Analogamente, Seja ∈x Y então a sentença ∈ → ∈x X x Y é
verdadeira (V), pois ∈x Y é falso (F). E como a conjunção de duas sentenças
verdadeiras é sempre verdadeira então ∈ → ∈ ∧ ∈ → ∈ ≡ =
def
V V
x X x Y x Y x X X Y .
Uma conjunção (E, ∧, &) de duas proposições é verdadeira se e somente se p e q são
verdadeiras. A tabela-verdade para uma fórmula p ∧ q é como:
p q p ∧ q
V V V
V F F
F V F
F F F
Observação 12: A conclusão ( ) ( )∈ → ∈ ∧ ∈ → ∈ ≡ =def
x X x Y x Y x X X Y advém da definição de
subconjunto ⊂ ≡ ∀ ∈ → ∈def
X Y ( x)(x X x Y) e da definição da igualdade de conjunto, onde se
define que o conjunto X é igual ao conjunto Y se ambos têm os mesmo elementos, isto
18
é, se cada elemento pertencente a X pertencer, também a Y , e se cada elemento que
pertence a Y , pertencer também a X . Ou seja:
Definição 07: Diz-se que o conjunto X é igual a um conjunto Y , isto é, =X Y se ⊂X Y e
⊂Y X .
Simbolicamente, do ponto de vista da Lógica Matemática, escreve-se:
( ) ( ) ( )= ≡ ⊂ ∧ ⊂ ≡ ∀ ∈ → ∈ ∧ ∈ → ∈ def def
X Y (X Y) (Y X) x x X x Y x Y x X
ou, equivalentemente, do ponto de vista da Lógica Matemática,
= ≡ ∀ ∈ ↔ ∈def
X Y ( x)(x X x Y)
Observação 13 (corolário da definição): Se = ≡ ∀ ∈ ↔ ∈def
X Y ( x)(x X x Y) então a sentença
≠X Y que denota a relação “o conjunto X não é igual ao conjunto Y ” pode ser
especificada observando que sua conseqüência lógica é como ∃ ∈ ∉x X;x Y ou ∃ ∈ ∉y Y;y X
ou seja:
[ ]≠ ≡ ∃ ∈ ∧ ∉ ∨ ∃ ∈ ∧ ∉def
X Y ( x)(x X x Y) ( y)(y Y y X)
Observação 14: Uma discussão sobre a igualdade entre conjuntos também poderia ser
realizada usando o “princípio da extensionalidade”, que assegura que “dois conjuntos X e
Y são iguais se, e somente se, todo elemento e X pertencer a Y e todo elemento de Y
pertencer a X. Neste caso indica-se isto por X=Y”. Detalhes em (ABE, PARAVERO, 1992).
LISTA DE EXERCÍCIOS 02: Verificar se as seguintes relações ou sentenças são verdadeiras ou
falsas:
19
Solução: Considere F uma designação para falso e V uma designação para verdadeiro,
então (faça os detalhes):
1. ∅⊂∅ V, pois a sentença ( )∀ ∈∅→ ∈∅x;x x é verdadeira, da tabela verdade da
condicional.
2. ∅∈∅ F, pois a sentença ( )∃ ∈∅∧ ∈∅x;x x é falsa, já que ambas as proposições são
falsas, já que por definição ∉∅x .
3. ∅∈ ∅ V, pois ∅ é um conjunto unitário que contem o conjunto vazio como
elemento.
4. ∅ ⊂ ∅ V, pois o conjunto vazio está contido em qualquer conjunto.
5. ∅ ⊂ ∅ F, pois o conjunto vazio não possui nenhum conjunto contendo outro
conjunto contido nele.
6. ∅ ∈∅ F, pois o conjunto vazio é um conjunto que não possui elementos.
7. ∅ ∈ ∅ F, pois o conjunto ∅ tem apenas o conjunto ∅ como elemento, mas não
tem ∅ como elemento.
8. ∅ ⊂ ∅ V, pois o conjunto ∅ está contido em ∅ .
9. ∅ = ∅ F, pois o conjunto ∅ não tem elemento, enquanto ∅ tem um elemento,
que é o próprio vazio.
10. ,∅∈ ∅ ∅ V, pois o conjunto ∅ é um elemento do conjunto ∅ ∅, .
11. ,∅ ∈ ∅ ∅ V, pois o conjunto ∅ é um elemento do conjunto ∅ ∅, .
12. ∅ ⊂ ∅ ∅, V, pois o conjunto vazio está contido no conjunto ∅ ∅, .
13. ,∅ ⊂ ∅ ∅ V, pois ∅ é um subconjunto do conjunto ∅ ∅, .
14. , ,∅ ∅ = ∅ ∅ V, pois todo elemento do conjunto ∅ ∅, e elemento do
conjunto ∅ ∅, e a ordem não é relevante.
15. ∅ = ∅ V, pois o vazio é único.
Proposição 02: Sejam X , Y e Z conjuntos quaisquer. Então para a relação de inclusão
valem as seguintes propriedades:
a) ⊂ ∀X X, X (reflexividade).
20
b) Se ⊂X Y e ⊂Y X então =X Y (anti-simetria).
c) Se ⊂X Y e ⊂Y Z então ⊂X Z (transitividade).
Prova:
a) Da definição 05, de inclusão, ⊂ ≡ ∀ ∈ → ∈def
X Y ( x)(x X x Y) , tem-se que, considerando
∀ ∈x X , por hipótese, então ∀ ∈ → ∈ ≡ ⊂def
( x)(x X x X) X X .
b) Se ⊂ ∧ ⊂(X Y) (Y X) então pela definição de inclusão e de igualdade, definição 07, tem-
se que ∀ ∈ → ∈ ∧ ∀ ∈ → ∈ ≡ =def
( x)(x X x Y) ( x)(x Y x X) X Y .
c) Se ⊂ ∧ ⊂(X Y) (Y Z) então, por definição de inclusão ⊂ ≡ ∀ ∈ → ∈def
X Y ( x)(x X x Y) e
⊂ ≡ ∀ ∈ → ∈def
Y Z ( x)(x Y x Z) , pois ambas valem por hipótese. Logo, também vale que:
( )( ) ( )( )∀ ∈ → ∈ ∧ ∀ ∈ → ∈ → ∀ ∈ → ∈ ≡ ⊂ def
x x X x Y x x Y x Z ( x)(x X x Z) X Z
Observação 15: Utiliza-se na proposição 02 intuitivamente o conceito de relação que é
uma especificação matemática para avaliar ou comparar, entre outras caracterizações,
objetos abstratos (matemáticos) ou concretos. Essa temática será estudada na seção
apropriada.
• Exemplos notáveis de relações são as relações binárias de equivalência e de relações
de ordem, que são frequentemente empregadas para avaliar somente dois objetos
por cada operação.
Proposição 03: Sejam X , Y e Z conjuntos quaisquer. Então para a relação de igualdade
valem as seguintes propriedades:
a) =X X (reflexividade).
b) Se =X Y , então =Y X (simetria).
c) Se =X Y e =Y Z então, =X Z (transitividade).
Prova:
a) Da definição de inclusão (definição 05) tem-se que ∀ ∈ → ∈ ≡ ⊂def
( x)(x X x X) X X e,
analogamente, tem-se que ⊃ ≡ ∀ ∈ → ∈def
X X ( x)(x X x X) . Então pela definição de
igualdade (definição 07), vale que ∀ ∈ ↔ ∈ ≡ =def
( x)(x X x X) X X .
21
Ou, alternativamente, ∈ ↔ ∈x X x X é verdadeira ∀x , logo ∀ ∈ ↔ ∈( x)(x X x X) é
verdadeiro, pela tabela verdade da bicondicional,. Logo, =X X .
Uma bicondicional (SE E SOMENTE SE, ↔) de duas proposições, p ↔↔↔↔ q, é verdadeira
se e somente se p e q são verdadeiras ou se p e q são falsas. A tabela-verdade para
uma fórmula p ↔ q é como:
p q p ↔ q
V V V
V F F
F V F
F F V
b) Se =X Y , então por definição de igualdade entre conjuntos (definição 07) vale o
resultado de que ∀ ∈ → ∈ ∧ ∀ ∈ → ∈( x)(x X x Y) ( x)(x Y x X) . Como a ordem dos
elementos não é importante, é válido que ∧ = ∧(X Y) (Y X) , e então:
∀ ∈ → ∈ ∧ ∀ ∈ → ∈ ≡ =def
( x)(x Y x X) ( x)(x X x Y) Y X
c) Por hipótese valem =X Y e =Y Z , então pela definição de igualdade entre conjuntos
(definição 07) tem-se que ∀ ∈ → ∈( x)(x X x Y) e ∀ ∈ → ∈( x)(x Y x Z) . Assim, vale:
[ ]∀ ∈ ↔ ∈ ∧ ∀ ∈ ↔ ∈ ≡ ∀ ∈ ↔ ∈ ≡ =def def
( x)(x X x Y) ( x)(x Y x Z) ( x)(x X x Z) X Z
8 - CONJUNTO DAS PARTES DE UM CONJUNTO FINITO (CONJUNTO DE POTÊNCIA)
Dado um conjunto X finito, é relevante definir o conjunto das partes de X , P(X) , como
aquele que contém todos os subconjuntos de X , incluindo o vazio e o próprio X . Um
modo de determinar P(X) é pensar em todos os subconjuntos com um elemento,
depois todos os subconjuntos com dois elementos, e assim por diante.
Ou seja, a partir de um conjunto X pode-se sempre considerar em outro conjunto, cujos
elementos são os subconjuntos ou partes de X . Assim, tem-se:
22
Definição 08: Dado um conjunto X , diz-se que P(X) é o conjunto cujos elementos são
todas as partes de X , se é formando pela combinação simples de todos seus elementos.
Chama-se a esse conjunto de o conjunto das partes de X ou conjunto potência de X .
Exemplo 10: Seja =X 1,2,3 então os elementos de P(X) , resultantes das possíveis
combinações simples realizadas com os elementos de X , são:
a) Os conjuntos: ∅, 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3 de modo que:
= ∅P(X) ,1,2,3,1,2,1,3,2,3,X
Isso significa que:
a) Se ∈A P(X) então ⊂A X .
b) Que P(X) , o conjunto das partes de X , nunca é vazio. Tem-se pelo menos ∅∈P(X) e
∈X P(X) .
c) Além disso, ⊂Y X se e somente se ∈Y P(X) .
Além disso, mostra-se que SE o conjunto X tem n elementos ENTÃO o conjunto P(X)
tem n2 elementos. Isto é, vale, ( ) = n(X)n P(X) 2 , onde ( )n X (ou card(X)) designa os “n
elementos do conjunto X ” e ( )n P(X) designa os “ n(X)2 elementos de P(X) ”. Antes de
provar “verificar-se a veracidade” da afirmação através de mais um exemplo.
Exemplo 11: Se P(X) é o conjunto de partes de X e se ( )n P(X) denota o número de
conjuntos, elementos do conjunto P(X) , então vale que ( ) = n(X)n P(X) 2 , pois:
• Se X = ∅∅∅∅ então P(X) = ∅∅∅∅, de onde n(P(X)) = 20 =2n(∅∅∅∅) = 1.
• Se X = a então P(X) = ∅∅∅∅, a, de onde n(P(X)) = 21 = 2.
• Se X = a, b então P(X) = ∅∅∅∅, a, b, a, b, de onde n(P(X)) = 22 = 4.
• Se X = a, b, c então P(X) = ∅∅∅∅, a, b, c, a, b, b, c, a, c, a, b, c, de onde
n(P(X)) = 23 = 8.
23
Assim, pode-se avaliar a quantidade de elementos de P(X) , como:
Proposição 04: Seja P(X) o conjunto das partes de X . Então P(X) tem n2 elementos, se
X tem n elementos.
Prova:
É um fato conhecido que a quantidade de combinações (simples) de p elementos que
podem ser formados com os n elementos de um conjunto com ≤ ≤0 p n é dada por:
= −
n n!
p p!(n p)!
Assim, se X tem n elementos, pode-se formar:
• ( )
( )( )−
= = = = − −
n n n 1 !n!n
p 1 1! n 1 ! 1. n 1 ! conjuntos unitários.
•
= = =
n n! n!
p 2 2!(1) 2! conjuntos de dois elementos.
• ,...,
• = −
n
p n 1 conjuntos de n-1 elementos e,
•
= =
n1
p n conjunto com n elementos, que é o conjunto X.
• ( )
= = = −
n n! n!1
0 0! n 0 ! 1.n! conjunto sem elementos, já que como ∅⊂ X essa condição é
a ela equivalente.
Portanto o número de elementos de P(X) é dado pela soma de todos os conjuntos
formados desse modo. Ou seja, como:
=
= + + + + + − =
∑n
p 0
n
n n n n n n...
p 0 1 2 n 1 n
2
Esse resultado da análise combinatória é provado na proposição 05, e fornece a
quantidade de subconjuntos de um conjunto com n elementos.
24
Com essas notações, vamos olhar o conjunto X = a, b, c sob formalização matemática
apresentada pela proposição 04.
Exemplo 12: Se X = a, b, c, então P(X) = ∅∅∅∅, a, b, c, a, b, a, c, b, c, a, b, c, pois
se tem:
• = = = = −
3 3! 3! 3!
0 0!(3 0)! 1.3! 3! 1 conjunto sem elementos. (conjunto vazio).
• = = = = −
3 3! 3! 3.2!
1 1!(3 1)! 1.2! 2!3 conjuntos com um elemento (conjunto unitário).
• = = = = −
3 3! 3! 3.2.1
2 2!(3 2)! 2.1! 2.1 3 conjuntos com dois elementos.
• = = = = −
3 3! 3! 3!
3 3!(3 3)! 3!0! 3!1 1 conjunto com n elementos, que é o conjunto X.
Assim, é possível observar que P(X) é formado pelo conjunto vazio acrescentado com
as possíveis combinações dos elementos de X, com variação de 1 até n=n(X). Note
novamente que “A quantidade de combinações (simples) de k elementos que podem
ser formados com os n elementos de um conjunto com ≤ ≤0 k n ” é determinada por:
≡
defn n!
k k!(n -k)!
Observação 16: Esse resultado,
≡
defn n!
k k!(n -k)!, pode ser provado ser verdadeiro usando o
método da indução finita. E isso será feito na seção oportunamente.
Observe que para cada inteiro não negativo n , define-se recursivamente o fatorial de n,
denotado por n!, como:
25
( )
≡ ≥
def1, se n =0
n!
n n -1 !, se n 1
Para provar que a soma de todos os conjuntos formados do modo apresentado na
observação 16 resulta m =
=
∑
nn
p 0
n2
p é conveniente provar antes um resultado auxiliar.
Lema 01: Se a e b são números inteiros (reais) e n é um número natural positivo, então
vale o seguinte resultado.
( ) −
=
−
+ =
= + + +
∑n
n n k k
k 0
n 0 n 1 1 0 n
na b a b
k
n n n a b a b ... a b
0 1 n
(4)
Prova: O teorema será provado na seção apropriada usando o método da indução finita.
Proposição 05: Seja P(X) o conjunto das partes de X . Então P(X) tem =n2 n(P(X))
elementos.
Prova: Basta observar que o número de elementos de P(X) é dado pela soma de todos
os conjuntos formados desse modo. Ou seja, como:
=
+ + + + + −
∑n
k 0
nn(P(X)) =
k
n n n n n = ...
0 1 2 n 1 n
(5)
Note-se agora que tomando a=b=1 na expressão (4) do lema 01 tem-se:
( ) −
=
−
+
+ + +
+ + + + −
∑n
nn n k k
k 0
n 0 n 1 1 0 n
n2 = 1 1 = 1 1
k
n n n = 1 1 1 1 ... 1 1
0 1 n
n n n n = ...
0 1 n 1 n
(6)
de modo que, por comparação entre (5) e (6) obtém-se =n2 n(P(X)) .
26
Exemplo 13: Então = ∅P(a,b) ,a,b,a,b tem 2 elementos e =P(X a,b) tem
= =n 22 2 4 elementos, que são seus subconjuntos.
9 – CONJUNTOS DISJUNTOS
No caso em que os conjuntos X e Y quaisquer não tem elementos em comum então se
diz que X e Y são ditos serem disjuntos. Especifica-se essa condição como:
Definição 09: Dados os conjuntos X e Y. Se não existe nenhum elemento de X em Y e se
não existe nenhum elemento de Y em X, diz-se que X e Y são conjuntos disjuntos.
Exemplo 14: Sejam os conjuntos =X 1,2,3 , =Y 3,4,5 e =Z 5,6,7 , então:
a) Os conjuntos =X 1,2,3 e =Y 3,4,5 não são disjuntos, pois tem um elemento (o
número 3) em comum.
b) Os conjuntos =X 1,2,3 e =Z 5,6,7 são disjuntos, pois não tem nenhum elemento
em comum.
10 – REPRESENTAÇÕES E ILUSTRAÇÕES
Objetivando ilustrar relações existentes entre conjuntos e de modo a “facilitar” o
entendimento de algumas definições e demonstrações, podem-se representar essas
relações através de uma propriedade característica ou por diagramas. A forma
tradicional de representação por diagramas é empregar os diagramas de Venn-Euler
(ou Venn) ou diagramas lineares. Na representação por diagrama, é usual traçar uma
linha fechada em torno dos elementos constituintes do conjunto.
Exemplo 15: O diagrama abaixo representa o conjunto A das vogais no conjunto
fundamental (universo) U do alfabeto.
27
Diagrama de Venn para o conjunto das vogais.
Em geral, o diagrama de Venn representa também o conjunto fundamental, que contém
o conjunto representado. Para isso, desenha-se em torno do diagrama um retângulo
representando o conjunto U.
Exemplo 16: Seja =X 1,2,3,4,5,6,7,8,9,10,11,12 e seus subconjuntos: =C 10,11
=A 2,3,4,5,6 Então o diagrama de Venn é determinado por:
Exemplo 17: A relação de inclusão ∀ ∈ → ∈ ≡ ⊂def
( x)(x X x Y) X Y pode ser ilustrada como:
28
Exemplo 18: A relação de disjunção entre os conjuntos X e Y pode ser representada
como:
Exemplo 19: A relação de parte própria ⊄ ≡ ∃ ∈ ∧ ∉def
X Y ( x)(x X x Y) pode ser ilustrada como:
Outro modo de representar as relações entre conjuntos é usar os chamados diagramas
lineares (ou em linha). Por exemplo, Se X e Y são conjuntos com ⊂X Y , o diagrama
linear desses dois conjuntos é obtido escrevendo-se Y em “nível mais elevado” que X e
unindo-se X a Y por meio de “segmentos de reta”. Veja detalhes em (ABE, PAPAVERO,
1994)
11– TEORIA DE CONJUNTOS E CIÊNCIA DA COMPUTAÇÃO
Alguém pode questionar os motivos de se estudar A Teoria dos Conjuntos, que parece
ser abstrata e “inútil” à Computação. Esse pensamento é equivocado, não obstante o
emprego exagerado e equivocado da Teoria dos Conjuntos às mais diversas áreas, que
acabaram cederam espaço das idéias e de procedimentos a elas inerentes para uma
linguagem e terminologia “conjuntista”.
29
Mesmo considerando que o emprego da Teoria dos Conjuntos foi mais acentuado aos
aspectos formais da Teoria do que o compromisso com o desenvolvimento e a
aplicação daquelas áreas, ela ainda é a linguagem da Matemática ou de qualquer
Teoria que busque estudar os aspectos formais duma Ciência.
Considerando que Ciência da Computação é “É o estudo dos algoritmos, suas aplicações
e de sua implementação, na forma de software, para execução em computadores
eletrônicos” http://pt.wikipedia.org/wiki/Ciência_da_Computação, então ela busca
enquanto Ciência construir formalismos para os diversos propósitos e finalidades.
Assim, o estudo da Teoria da Computação está relacionado com três áreas que tratam
dos fundamentos da Ciência da Computação (BRANDÂO, 2011):
• Autômatos e Computabilidade, cujas temáticas são tradicionalmente tratadas em
disciplinas como Métodos Formais (MF), Linguagem Formal e Autômatos (LFA) ou
Teoria da Computação (TC).
• Complexidade, cuja temática é tratada tradicionalmente na disciplina de Projeto e
Análise de Algoritmos (PAA) ou Teoria da Computação (TC).
Na Teoria de Autômatos são discutidas máquinas abstratas que capturam as partes
essenciais de máquinas reais, de modo a estudar a computação de forma simples, sem
entrar nos detalhes de arquiteturas concretas que podem prejudicam a noção de
computação. Autômatos (são diversos os tipos) são empregados para fundamentar e
analisar:
• Processamento de texto.
• Compiladores.
• Projeto de hardware.
• Projeto de software.
• Linguagens de programação.
• Inteligência Artificial.
• Outras mais!
30
Na Teoria da Computabilidade é estudada a capacidade de resolução de problemas de
algoritmos, de modo que se pode indicar quais são os problemas que podem ser
resolvidos através de algoritmos, e quais são os problemas que não podem ser
resolvidos através de algoritmos. Estas indicações são relevantes, pois certos
problemas não podem ser resolvidos por máquinas.
Já a Teoria da Complexidade são estudados problemas computacionais que podem ser
divididos em duas classes: Problemas que são viáveis ou não viáveis de serem
resolvidos eficientemente. Essas classes estão relacionadas com a capacidade de se
resolver os problemas em função do tempo e do espaço, já que o crescimento do
tempo de execução de um programa e a memória utilizada, em função do tamanho de
sua entrada de dados.
Com efeito, uma estrutura teórica é um modelo formal que visa retratar as
propriedades ou comportamentos encontrados em diferentes contextos e situações,
então se pode especificá-la através de um conjunto abstrato de objetos, munido de
operações e relações que devem ser satisfeitas. Todas essas idéias devem ser
formalizadas para não depender de uma particular interpretação ou aplicação.
Sendo necessária a formalização de uma Teoria, então se deve empregar uma
linguagem formal para tal fim, de modo que tal o Sistema Formal deva ser composto
O objetivo destas notas de aulas não é discutir quaisquer umas dessas áreas da
Computação, mas só lembrar que para estudar os aspectos teóricos e práticos
dessas importantes áreas é necessário construir e desenvolver Modelos da
Computação. Modelos estes que decorrem de estruturas teóricas abstratas que são
especificadas em termos de uma linguagem unificadora, integrando os elementos
da Teoria através de agrupamentos bem definidos e de relações bem determinadas.
Deste modo é natural empregar a Teoria dos Conjuntos para realizar tais
especificações.
31
por um conjunto de símbolos e por um conjunto de regras bem determinadas com as
quais se formam determinadas sentenças que são válidas naquela linguagem. Sobre
essa questão (MENEZES, 1997) lembra que:
“A Teoria das Linguagens Formais foi originalmente desenvolvida na
década de 1950 com o objetivo de desenvolver teorias relacionadas com
as linguagens naturais. Entretanto, logo foi verificado que esta teoria era
importante para o estudo das linguagens artificiais e, em especial, para as
linguagens originárias na Ciência da Computação. Desde então, o estudo
das Linguagens Formais desenvolveu-se significativamente e com
diversos enfoques, com destaque para aplicações em análise léxica e
sintática de linguagens de programação, modelos de sistemas biológicos,
desenho de hardware e relacionamentos com linguagens naturais.
Recentemente, inclui-se a ênfase no tratamento de linguagens não-
lineares, como planares, espaciais e n-dimensionais”.
Paulo Fernando Blauth Menezes (www.infufrgs.br)
Sobre a relevância de Sistemas Formais em Ciência da Computação, (PALAZZO, 2009)
lembra que:
“Sistemas formais são de grande importância no estudo da Ciência da
Computação, uma vez que permitem representar domínios, contextos e
objetos que podem ser manipulados por máquinas e, portanto se
encontram dentro do escopo de estudo dos informatas. Linguagens
específicas e precisamente classificadas são empregadas para a sua
descrição e constituem a base mais elementar da modelagem
computacional. Esta disciplina (Linguagens Formais e Autômatos) é pré-
requisito para Teoria da Computação e Compiladores e supõe
conhecimento prévio de Sistemas Discretos, Teoria dos Conjuntos,
Funções e Lógica Computacional...”.
Prof. Luiz A M Palazzo (http://ia.ucpel.tche.br/~lpalazzo/Aulas/LFA/)
32
Exemplo 20: Sendo inviável aqui tratar da relação prática entre a Teoria dos Conjuntos e
uma Teoria da Computação (um Modelo Teórico da Ciência da Computação), é
suficiente apontar que um exemplo concreto do uso da Teoria dos Conjuntos por uma
Linguagem de Programação é o papel central que dos Conjuntos como tipo de dados
padrão em Pascal. Nesta Linguagem um conjunto universo S, o alfabeto, precisa ser
especificado para serem definidas as variáveis que representam subconjuntos de S, isto
é, elementos de P(S).
Exemplo 21: O hardware tem evoluído nas últimas décadas de acordo do a “Lei de
Moore” que declara que “O poder de computação de um chip duplica a cada 18 meses”.
Isso significa que a capacidade de processamento de Computadores e de outros
dispositivos digitais tem crescido de modo exponencial. E tal desenvolvimento também
se refletiu no software, que tem avançado significativamente com novas metodologias
e linguagens de programação.
Torna-se, portanto, relevante desenvolver um conjunto de conhecimentos básicos
sobre o que é Computação, mas que sejam independentes do tipo de computador
utilizado ou da linguagem de programação, permitindo compreender se as novas
soluções tecnológicas propostas se constituem melhoramentos do existente ou se
constituem revoluções.
Além disso, outra característica importante da Teoria da Computação é possibilitar a
melhor compreensão dos limites da área. Há problemas que se sabem serem inviáveis
de resolver por meio de um computador. E existem outros problemas que, embora
sejam resolúveis teoricamente, não o são na prática porque exigem demasiado tempo
ou memória. A teoria da computação investiga e fornece resultados sobre essas
questões.
12 – ALFABETOS, PALAVRAS, LINGUAGENS.
33
Linguagem é um conceito fundamental na Teoria da Computação, pois trata da forma
precisa de expressar problemas, permitindo um desenvolvimento formal adequado ao
estudo de várias temáticas inerentes à Computação.
Assim, o conceito de Linguagem é dos fundamentais em Ciência da Computação,
sendo definido a partir da noção de conjunto. Para a definição de linguagem é
necessário conceituar alfabeto e cadeia de caracteres, entre outros elementos.
Uma Linguagem Formal, ao contrário de uma linguagem natural que não têm certos
compromissos, deve possuir:
• Uma sintaxe bem definida, de modo que dada uma sentença, seja sempre possível
sempre saber se ela pertence ou não a uma linguagem.
• Uma semântica precisa, de modo que não contenha sentenças sem significado ou
ambíguas.
Pode-se mostrar nas pertinentes disciplinas que toda Linguagem Formal deve possuir
um alfabeto associado. Um alfabeto é um conjunto finito não vazio de elementos que
serão definidos como símbolos. Uma palavra sobre um alfabeto é uma seqüência finita
de símbolos de tal alfabeto. O tamanho da palavra define a quantidade de símbolos da
palavra. Uma palavra vazia é aquela constituída de “zero” símbolos.
Assim, neste contexto, as especificações que seguem, mais a título de exemplo, são
construídas usando como base a noção de Símbolo ou Caractere, que é um termo
abstrato básico, não sendo definido formalmente, assim como realizado na Teoria de
Conjuntos. Letras e dígitos são exemplos de símbolos freqüentemente usados numa
O OBJETIVO DESSAS NOTAS DE AULAS EM LMD É APENAS ESTABELECER A BREVE DISCUSSÃO ENTRE
A TEORIA DE CONJUNTOS E MODELOS DA COMPUTAÇÃO QUE UTILIZAM A TEORIA DE CONJUNTOS
COMO LINGUAGEM UNIFICADORA PARA EFETIVAR AS ESTRUTURAS DOS MODELOS.
34
Linguagem. A discussão segue, com adaptações, as apresentadas em (MENEZES, 1997)
e (DIVERIO, MENEZES, 2000).
Definição 10: Um Alfabeto é um conjunto finito de símbolos ou caracteres.
• Um conjunto infinito não é um alfabeto.
• O conjunto vazio é um alfabeto.
Definição 11: Uma Cadeia de Símbolos sobre um conjunto é uma seqüência de zero ou
mais símbolos justapostos. Uma Cadeia de Símbolos Finita é denominada de Palavra.
• O símbolo εεεε denota a cadeia vazia ou palavra vazia ou sentença vazia.
• A notação ∑∑∑∑ representa um conjunto de símbolos (um alfabeto)
• A notação ∑∑∑∑* designa o conjunto de todas as palavras possíveis sobre o alfabeto.
• A notação ∑∑∑∑+ designa ∑∑∑∑*-εεεε.
Exemplo 22: (MENEZES, 1997) Para ilustrar a noção de alfabeto e palavra observe que:
• ∅∅∅∅ e a, b, c são alfabetos.
• O conjunto dos números naturais não é um alfabeto.
• O conjunto das letras 1, b, aa, ab, ba, bb, aaa, ... não é um alfabeto.
• εεεε é uma palavra sobre a, b, c.
• a, e, i, o, u, ai, oi, ui e aeiou são exemplos de palavras sobre o conjunto das vogais.
• 1 e 001 são exemplos de palavras distintas sobre dígitos.
• a, b* = εεεε, a, b, aa, ab, ba, bb, aaa.
• εεεε é uma palavra sobre ∅∅∅∅ (alfabeto).
• ∅∅∅∅* = εεεε (todas as possíveis palavras).
Definição 12: Concatenação de Palavras é uma operação binária, definida sobre uma
linguagem L, a qual associa a cada par de palavras uma palavra formada pela
justaposição da primeira com a segunda palavra.
35
Exemplo 23: (MENEZES, 1997) Seja o alfabeto Σ = a, b e considere as palavras v=baaaa
e w=bb. Então são concatenações.
• v w = baaaabb.
• v ε = v = baaaa.
• w3 = w w w.
• a5 = aaaaa.
Exemplo 24: (MENEZES, 1997) Um alfabeto numa linguagem de programação como
Pascal é o conjunto de todos os símbolos usados nos programas: Letras, dígitos,
caracteres especiais como “>”, “/”, etc., espaço ou “branco”.
Definição 13: Comprimento ou Tamanho de uma Palavra w, representado por w, é o
número de símbolos que compõem a palavra.
Exemplo 25: (MENEZES, 1997) Considere as palavras w=abcd e ε. então
• abcb = 4.
• ε= 0.
Definição 14: Um Prefixo (respectivamente, Sufixo) de uma palavra é qualquer
seqüência inicial (respectivamente, final) de símbolos da palavra. Uma subpalavra de
uma palavra é qualquer seqüência de símbolos contígua da palavra.
Exemplo 26: (MENEZES, 1997) Considere a palavra abcb sobre o alfabeto a, b, c .
Então:
• Os símbolos ε, a, ab, abc, abcb são todos os prefixos.
• Os Símbolos ε, b, cb, bcb, abcb são todos os sufixos.
• Qualquer prefixo ou sufixo é uma subpalavra.
36
Definição 15: Uma Linguagem Formal (LF), ou simplesmente, uma Linguagem, é um
conjunto de palavras sobre um alfabeto ∑∑∑∑. . O conjunto vazio e o conjunto formado
pela palavra vazia são Linguagens sobre ∑∑∑∑.
Exemplo 27: São exemplos de linguagens formais:
• Java.
• C.
• Pascal.
• HTML.
• Basic.
• C#.
• Outras mais.
Definição 16: Um Sistema Formal é composto por um conjunto de símbolos
(caracteres) e por um conjunto de regras com as quais se formam determinadas
expressões (ou formulas ou proposições) que são válidas na Linguagem em questão.
Definição 17: Uma Sintaxe de uma LF é um sistema formal de regras que determina
como as expressões da linguagem podem ser formadas a partir de um conjunto de
caracteres básicos. Assim, a sintaxe trata das propriedades livres da linguagem, como,
por exemplo, a verificação gramatical de um programa.
Definição 18: Uma Semântica de uma LF é uma teoria baseada em regras de
relacionamento entre as expressões da linguagem e determinados objetos (seus
significados). Assim, a semântica da uma interpretação para a linguagem como, por
exemplo, o significado ou valor para o programa. Através da semântica define-se um
subconjunto da linguagem S composto de fórmulas válidas.
Exemplo 28: Considere a LF Pascal e o seguinte comando:
a := b (Pascal)
37
If (<expressão>) <instrução>
• Comando de atribuição correto (sintaxe)
• Substitua valor de a com o valor atual de b (semântica)
Definição 19: Um Argumento é uma seqüência de proposições (ou enunciados), no qual
uma das proposições é a conclusão e as demais são as premissas, e que servem para
formar alguma “evidência” para a conclusão. Um Argumento Dedutivo é aquele cuja
conclusão deve ser verdadeira. Ou seja, em um argumento dedutivo é impossível que a
conclusão seja falsa se as premissas forem verdadeiras.
Definição 20: Chama-se de Proposição todo o conjunto de palavras ou símbolos que
exprimem um pensamento de sentido completo.
Definição 21: Um Problema é uma questão a ser respondida e é descrito por:
1. Uma descrição geral de todos seus parâmetros.
2. A especificação de quais propriedades a resposta ou solução deve satisfazer.
Definição 22: Uma Instância de um problema é obtida ao se fixar valores particulares
de todos os parâmetros do problema
REFERÊNCIAS PARA O TÓPICO
ABE, A. M., PAPAVERO, N. Teoria Intuitiva dos Conjuntos. São Paulo. Editora Makron
Books. 1991. 266 p.
ALENCAR FILHO, E. Teoria Elementar dos Conjuntos. São Paulo. Editora Nobel. 1985.
CASTRUCCI, B. Elementos de Teoria dos Conjuntos. GEEM. São Paulo. 1983. 129 p.
CONIGLIO, M. E. Teoria Axiomática de Conjuntos: Uma Introdução. Disponível em
<http://unicamp.academia.edu/MarceloEstebanConiglio/Papers/831111/Teoria_Axio
matica_de_Conjuntos_uma_Introducao>. 1997.
38
DIVERIO, T. A., MENEZES, P F. B, Teoria da Computação. Série Livros Didáticos. Instituto
de Informática da UFRGS. Editora Sagra-Luzzatto. Porto Alegre. 2000. 205 p.
GERÔNIMO, J.R., FRANCO, V. S. Fundamentos de Matemática: Uma introdução à lógica
matemática, teoria dos conjuntos, relações e funções. Editora da UEM. 2010, 296
p.
GERSTING, J. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro.
Editora LTC. 1995. 518 p.
GRAÇA, D. Apontamentos para Linguagens Formais e Autômatos. Curso de
Informática. 2011/11. Disponível em <http://w3.ualg.pt/~dgraca/Files/LFA/
Apontamentos_LFA.pdf>. 2011. 75 p.
HALMOS. P. R. Teoria Ingênua dos Conjuntos. Coleção Clássicos da Matemática. Editora
Ciência Moderna. Rio de Janeiro. 2001. 178 p.
HEFEZ, A. Curso de Álgebra. Rio de Janeiro. Coleção Matemática Universitária. IMPA. Rio
de Janeiro. 1993. 222 p.
LIPSCHUTZ, S. Teoria dos Conjuntos. Coleção Schaum. Editora McGrawHill. São Paulo.
1972. 337 p.
LIPSCHUTZ, S., LIPSON, M. Matemática Discreta. São Paulo. Coleção Schaum. Editora
Bookman-Artmed. Porto Alegre. 2004. 511 p.
MENEZES, P. B. Matemática Discreta para Computação e Informática. Série Livros
Didáticos Informática URGRS. Editora Bookman-Artmed. Porto Alegre. 2010. 350 p.
MENEZES, P. B., TOSCANI, L. V., LÓPEZ. J. G. Aprendendo Matemática Discreta com
Exercícios. Série Livros Didáticos Informática URGRS. Editora Bookman-Artmed.
Porto Alegre. 2009. 356 p.
MENEZES, P. F. B. Linguagens Formais e Autômatos. Série Livros Didáticos. Instituto de
Informática da UFRGS. Editora Sagra-Luzzatto. Porto Alegre. 1997. 168 p.
MORAIS FILHO, D. C. Um Convite à Matemática. Coleção Professor de Matemática.
Editora SBM. 2012. 455p.
VIEIRA, N. J. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. Rio
de Janeiro. Editora Thomson. 2006.