38
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

02 - Introdução e conceitos de teoria dos conjuntos

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.