Seja Bem-Vindo. Este site tem recursos de leitura de texto, basta marcar o texto e clicar no ícone do alto-falante   Click to listen highlighted text! Seja Bem-Vindo. Este site tem recursos de leitura de texto, basta marcar o texto e clicar no ícone do alto-falante

Aula 01 – Teoria da Computação

Introdução.

Elementos de matemática discreta

Em função das crescentes aplicações de computadores no nosso dia a dia, a organização Association for Computing Machinery (ACM) – passou a recomendar que todos os cursos de engenharia dos EUA incluíssem em seus currículos um curso de matemática discreta, pois se trata da matemática que fundamenta a Computação. Essa recomendação se deu no ano de 1968. Hoje em dia, após o surgimento de microcomputadores e da internet, essa recomendação é muito mais pertinente.

A matemática discreta é a parte da matemática que está interessada no estudo de estruturas discretas (e não contínuas). Como os computadores não podem representar números reais, a matemática discreta é a base não só para Linguagens Formais e Autômatos, mas também, para qualquer curso de Computação com ênfase em teoria. Nesta seção será feita a introdução aos fundamentos de matemática discreta. Os assuntos que veremos incluem conjuntos, relações e funções. Falaremos também sobre conjuntos enumeráveis, que é um tópico um pouco mais avançado, mas fundamental para o conteúdo do presente curso.

A teoria de conjuntos é uma área relativamente recente da matemática. Seu principal autor, George Cantor, publicou seus trabalhos a partir de 1874 (CANTOR, 1874) e vale dizer que não foram muito bem aceitos no início, apesar de rigorosamente corretos. Sua contribuição ao conhecimento matemático é essencial para o nosso entendimento de coleções ou conjuntos com uma infinidade de elementos. Aparentemente, somente matemáticos e teólogos se interessam pelo infinito. Não fosse, entretanto, os trabalhos de Cantor, talvez a própria Computação não teria tido um desenvolvimento tão bem-sucedido no início do século passado.

Por serem objetos matemáticos primitivos, conjuntos não possuem definições formais, apesar de contarem com uma teoria bem definida. Isto quer dizer que não há como caracterizá-los por uma única propriedade, de forma simples. Você não vai encontrar facilmente na literatura matemática algo do tipo “Um conjunto é….”. Aliás, partir para este tipo de abordagem pode trazer muitos problemas que estão totalmente fora do nosso escopo. São os famosos problemas de fundamentação da teoria dos conjuntos. Por enquanto é bom saber somente que eles existem, mas não interferem no uso corriqueiro e em aplicações da teoria dos conjuntos. Ficamos então com o entendimento que um conjunto é qualquer coleção (no sentido informal) de objetos, sendo estes abstratos, concretos, em quantidade finita ou não. Para indicar que um certo objeto a pertence à coleção (conjunto) A, utiliza-se a notação “a ∈ A”. Esta notação “a ∈ A”, é um predicado lógico, uma proposição, que é verdadeira ou falsa, conforme o elemento pertença ou não ao conjunto (Aqui um link para vídeos de revisão de matemática discreta que inclui teoria dos conjuntos).

Pode-se especificar um conjunto particular via uma propriedade, desta forma o conjunto é formado somente por aqueles objetos que satisfaçam a esta propriedade. Se falarmos do conjunto dos times de futebol que disputam a primeira divisão do Campeonato Brasileiro de Futebol em 2017, teremos um conjunto de 20 equipes. Outro exemplo de especificação é o conjunto dos objetos que são distintos deles mesmos. Como não há objeto que possa ser distinto de si mesmo, este conjunto é na realidade o conjunto vazio.

Formalmente, propriedades são especificadas através de uma linguagem lógica que faz uso dos conectivos lógicos: conjunção (∧), disjunção (∨), negação (¬) e implicação (→). Além destes conectivos, utilizamos os quantificadores existencial (∃) e universal (∀) e o predicado identidade (=) que indica quando dois objetos são o mesmo objeto. Na prática, outros predicados são usados, sempre relativos ao domínio dos conjuntos que estão sendo especificados. Por exemplo, se estamos lidando com números Naturais, é usual fazermos uso do predicado de comparação (<) e, por vezes, das operações de soma e multiplicação. A especificação de conjuntos é feita formalmente, a partir de outro conjunto: o conjunto que fornece os elementos que satisfazem (ou não) a propriedade. Em teoria dos conjuntos, este mecanismo de especificação é denominado de Axioma da especificação. É importante que você se recorde da definição de ocorrência de variável livre e ligada em uma fórmula da lógica de primeira ordem. Confira nos exemplos a seguir se ainda se lembra disso. Como o único conceito primitivo na teoria dos conjuntos (TC) é a pertinência (∈), as fórmulas da linguagem básica de TC só tem ocorrência de “∈” para formar predicados atômicos, além da igualdade =. Observe que se φ(x) for a fórmula ¬(x=x) e A for um conjunto arbitrário, então {x¬(x=x)} é o subconjunto vazio de A .

Axioma da Especificação.

Seja φ(x) uma fórmula na linguagem, onde x ocorre livre em φ(x) . Seja A um conjunto. {a/a ∈ A e φ(a)} é um subconjunto de A .

Dado um subconjunto arbitrário B de um conjunto A, a propriedade x ∈ B especifica B . Ou seja, B e {x/x ∈ A e x ∈ B} são o mesmo conjunto. Como identificar conjuntos, ou seja, como sabemos que dois conjuntos são iguais? Ora, dois conjuntos são iguais se ambos possuem os mesmos elementos. Além disso, dizemos que A está incluído em B se todo elemento de A também é elemento de B . Usando este conceito de inclusão entre conjuntos, podemos dizer que dois conjuntos B e C são iguais, se, e somente se, B ⊆ C e C ⊆ B.

Inclusão entre conjuntos.

Sejam B e C conjuntos. Dizemos que B está incluído em C, ou que C contém B, se, e somente se, todo elemento de B é também um elemento de C .

Em lógica, isto é descrito como ∀ x ((x∈B) → (x∈C)) .

Quando for possível, podemos apresentar um conjunto enumerando seus elementos. Por exemplo, podemos falar do conjunto dos símbolos {►, ◊ e °}. Isto é, o conjunto com 3 elementos que são enumerados anteriormente. Costumamos escrevê-los entre chaves para evitar ambiguidades. Daí o conjunto em questão é descrito por {►, ◊ e °}. Na definição de produto cartesiano a seguir, usamos pares ordenados (b, c) de elementos de a∈A e b∈B . Um par ordenado (a,b) é definido formalmente como sendo o conjunto {{b},{b, c}}, observe que a relação de inclusão entre conjuntos indica uma ordem na qual b vem antes de c no par ordenado. Daí o nome “par ordenado”.

Sejam B e C subconjuntos de A. Definimos:

– União:

B∪C é especificado por {x/x∈A e ((x∈B)∨(x∈C))}

– Interseção:

B∩C é especificado por { x/x∈A e ((x∈B)∧(x∈C))}

– Complemento em A :

CAB é especificado por {x/x∈A e ¬(x∈B)}

– Diferença:

B−C é especificado por {x/x∈A e ((x∈B)∧¬(x∈C))}

– Produto Cartesiano:

B×C é especificado por {(x, y)/(x∈A) e (y∈B)}

– Conjunto potência:

℘(A) é especificado por {B/B⊆A}

Existem algumas igualdades entre conjuntos que podem ser verificadas para quaisquer conjuntos em geral. Sejam conjuntos. Então as seguintes igualdades valem:

  • A∩A=A, A∩B=B∩A
  •  A∪B=B∪A
  •  A∩∅=∅, A∪∅=A
  •  A∩(B∪C)=(A∩B)∪(A∩C).

A figura abaixo representa tais igualdades.

Conjuntos A, B e C.
Conjuntos A, B e C.

Entre os seres humanos, a relação de ser-mãe-de pode ser vista como o conjunto dos pares ordenados de seres humanos, onde o segundo é mãe do primeiro. Desta forma, podemos usar TC para falar de relações familiares, tais como a relação de “ser-mãe-de”, “ser-pai-de”, “ser-irmão-de”, ou mesmo relações não familiares, tais como “ser-amigo-de”, “ser-colega-de”, “ser-conterrâneo-de”.

Relações entre elementos de dois conjuntos, mesmo que estes sejam diferentes, são facilmente especificadas usando o produto cartesiano. Por exemplo, a relação de posse entre seres humanos e automóveis é um subconjunto de Humanos × Autos . Alguns seres humanos não possuem carros. Por exemplo, se um certo h não possui carros, saberemos isso ao verificarmos que não existe nenhum par ordenado na forma (h, a) no conjunto Humanos × Autos, onde a pode ser tomado como cada elemento em Autos.

R é uma relação entre elementos de A e de B se, e somente se, R ⊆ A × B.

Um tipo especial de relação é a funcional. Uma função de F de A em B é qualquer relação na qual para cada a existe um, e somente um, b, tal que (a, b) ∈ F. Isto também implica que todo elemento de a está relacionado com algum b ∈ B. Como cada a possui um, e somente um, b, podemos denominar tal b por F(a). Por exemplo, cada ser humano possui uma, e somente uma, mãe biológica. Quando Maria é mãe de João, podemos denotar Maria por Mae− de(João). Neste caso, também se chama b de imagem de a via F.

F é uma função de A em B se, e somente se, F ⊆ A × B e para todo a ∈ A existe um, e somente um, b ∈ B, tal que (a, b) ∈ F . Obs.: Quando (a, b) ∈ F e F é função, pode-se denotar b por F (a).

Estamos interessados em dois tipos especiais de funções: as injetivas e as sobrejetivas.

Seja F uma função de A em B.

  • F é injetiva se, e somente se, para todo a1 e a2, se F (a1) = F (a2) então a1 = a2.
  • F é sobrejetiva se, e somente se, para todo b ∈ B existe a ∈ A tal que F (a) = b.

As funções injetivas de A em B não podem ter nenhum elemento do contra-domínio (B) que não seja imagem de alguém do domínio (A). Funções injetivas têm imagens diferentes a partir de elementos de A que sejam diferentes. Visto como função a relação de “ser-mãe-de” não é injetiva. Pois caso Maria tenha João e Amália como filhos, então Mae(João) = Mae(Amalia), mas João e Amália não são iguais.

Analise o axioma da especificação e imagine porque ele pressupõe o conjunto A. Sua aplicação é imediata para a definição/especificação de subconjuntos de A. Seria possível prescindir de A? Ou seja, o que acontece se usarmos somente a propriedade representada por φ(x), sem menção à A? Reflita sobre a seguinte tentativa de especificarmos um conjunto: {x/¬(x ∈ x)}.

Observe a especificação do conjunto potência. Ela é um pouco diferente das outras especificações. Por que isto acontece?

Na fórmula ∃y(¬ (y=0) ∧ y+x=z) a ocorrência de y em y=0 é ligada ao quantificador existencial e as ocorrências de z e x são livres, pois não estão no escopo de nenhum quantificador. Na fórmula ∀x((x∈z) → (x∈y)) as ocorrências de z e y são livres e as duas ocorrências de z são ligadas.

Quando queremos introduzir um objeto matemático, ou até mesmo um conceito matemático, podemos fazer isso essencialmente de duas formas distintas.

A primeira alternativa é definirmos este objeto usando objetos que já estão definidos. A segunda alternativa é fazemos um elenco de todas as propriedades relevantes que nosso objeto ou conceito satisfaz.

Por exemplo, sendo suc a função sucessor no conjunto dos números naturais, que a cada n associa n +1, a propriedade ¬∃y (suc (y) = x) só é verdadeira quando x é o número 0 (zero). Dizemos que ¬∃y (suc (y) = x) é uma definição do número zero, quando estamos no domínio dos números naturais, ou seja, a fórmula ¬∃y (suc (y) = x) define 0, pois é verdade se, e somente se, x = 0 . Mostramos ser possível definir logicamente o número zero somente com o auxílio do conceito de “sucessor”. Outro exemplo é, a partir da soma de números naturais e do número 0, definirmos a relação de ordem “menor que”. Isto é feito com a fórmula ∃y(¬(y=0)∧x+y=z), que indica que x < z . Esta forma de introdução de um objeto/conceito é exatamente o que se faz em algumas linguagens de programação quando as usamos para definir um tipo de dado que não é explicitamente dado pelas mesmas. Por exemplo, quando fazemos um programa definindo números complexos como pares de números reais e as operações de soma, produto etc. através de funções.

Introduzir novos conceitos e objetos via definição é a forma mais usada por programadores e por matemáticos. Entretanto, nem sempre é possível sua aplicação. Quando não é possível aplicar definições? Quando o conceito ou objeto que você quer introduzir não pode ser definido a partir de outros conceitos mais básicos. Por exemplo, a relação “maior que” não pode ser definida se não tivermos a adição à nossa disposição. Neste caso, o melhor que podemos fazer é especificar as propriedades que são essenciais. Isto se faz teorizando o “maior que”, indicando tratar-se de uma relação com certas propriedades. O resultado é uma Teoria que especifica as relações logicamente semelhantes à relação de “maior que”. A lista de fórmulas/propriedades que especifica o conceito é de fato uma axiomatização da Teoria. A Teoria propriamente dita é formada por todas as propriedades que podem ser demonstradas a partir desta axiomatização. Estas propriedades são chamadas de teoremas.

Um teorema é uma proposição que possui uma demonstração. O exemplo mais conhecido e popular de teorema talvez seja o de Pitágoras: “Em um triângulo retângulo, o quadrado da hipotenusa é igual à soma dos quadrados dos catetos”. Existem diversas provas deste teorema, algumas são totalmente visuais enquanto outras são totalmente descritas em linguagem natural e construídas na forma de argumentação. Uma argumentação, ou um argumento, é uma sequência de proposições onde se distingue uma conclusão e algumas hipóteses. A Lógica (com letra maiúscula, pois se trata de uma área de conhecimento humano) tem como objeto de estudo as argumentações válidas. Pode-se dizer que a Lógica é a área do conhecimento humano que estuda ou estabelece quando um argumento é bom ou válido. Em assuntos de Matemática, tais como o nosso estudo de Linguagens Formais e Autômatos, um argumento não é válido se ele não estabelece uma conclusão falsa a partir de premissas ou hipóteses verdadeiras. Argumentos, válidos ou não, são sequências de proposições, sendo que há uma proposição diferenciada – a conclusão -, e algumas proposições que são hipóteses. Proposições são sentenças que possuem valor de verdade, ou seja, podem ser falsas ou verdadeiras. Não é a toda sentença da linguagem natural que podemos atribuir um valor de verdade. Por exemplo, as seguintes sentenças não podem ter valor de verdade: “Feche a porta!”, “O programa parou?” e “Este carro azul estacionado à porta de sua casa”. A primeira é um comando, a segunda uma pergunta e a terceira é uma descrição. Proposições são geralmente representadas por sentenças que declaram um estado de coisas (state-of-affairs), isto é, sentenças declarativas, tais como “O carro estacionado à porta de sua casa é azul”, “A porta está fechada” e o “O programa parou”. Podemos não saber se “A porta está fechada” é uma sentença verdadeira ou não, pois podemos não saber a que porta a sentença se refere. Mas, com certeza, saberemos dizer se a mesma é verdade ou não, uma vez que a referência à porta esteja totalmente determinada, o que incluirá conhecer o estado da mesma, isto é, se fechada ou não. A Lógica não tem a “verdade” como objeto de estudo. Ela se utiliza de um conceito arbitrado de verdade para estudar quando um argumento é válido ou bom. Argumentos são formados de uma ou mais premissas e de uma conclusão.

Sendo Pi as premissas e C a conclusão, dizemos que um argumento P1, P2,⊃ Pn  C é válido, se, e somente se, em qualquer situação em que cada uma das Pi ‘s é verdadeira, então C também é verdadeira.

Argumentos válidos são devido a sua forma, e não ao seu conteúdo, ou a verdade factual das sentenças que o formam. Por exemplo, o argumento “Todo ser humano é mortal, bombeiros são seres humanos, então bombeiros são mortais” e o argumento “Todo guerreiro é corajoso, covardes são guerreiros, então covardes são corajosos” são na realidade instâncias do mesmo argumento formal,
que é “Todo B é A, c ́s são B ́s, então c ́s são A ́s”. No entanto, a primeira instância do argumento tem uma conclusão verdadeira no mundo atual, enquanto a segunda tem uma conclusão falsa. Isto se deve ao fato de uma das premissas não poder ser verdadeira no estado de coisas que são atribuídas ao nosso dia a dia. Ambos os casos usam o mesmo argumento formal, que é válido ou bom. Um exemplo de um argumento inválido ou ruim é: Alguns franceses são europeus, alguns parisienses são europeus, então alguns parisienses são franceses. Note que a versão formal deste argumento é “Alguns A ́s são B ́s e alguns C ́s são B ́s, então alguns C ́s são A ́s”. Interpretando A como o conjunto dos homens e C como o das mulheres e B como seres humanos, teremos um estado de coisas em que as premissas são verdadeiras e a conclusão falsa, portanto, o argumento é ruim ouinválido. Desde a Grécia antiga, onde a disciplina de Lógica teve um florescimento significativo, os argumentos utilizados na matemática passaram a ser formados de padrões lógicos, ou argumentos formais válidos, bem estabelecidos de forma a que o simples encadeamento destes argumentos (válidos) garantem a conclusão verdadeira a partir de premissas (supostas) como verdadeiras. Esta atitude lógico-demonstrativa é que deu suporte à matemática como “ciência” das proposições necessárias. A forma com que se lida com as demonstrações matemáticas é a mesma desde Euclides (300 a.C). Por exemplo, uma proposição que é uma negação (não P ), será sempre
provada na forma “suponha P verdadeira e obtenha uma contradição, portanto P “. Apenas a título de ilustração, vamos acompanhar uma das demonstrações mais antigas do conhecimento humano. Vamos provar que √2 não é um número racional. Esta prova se encontra nos Elementos de Euclides (livro X proposição 117). Vejamos uma versão moderna desta demonstração:

Suponha que √2 é racional, então existem a e b primos entre si, com b não nulo, tal que √2 = a/b . Pela definição de √2, temos que a2=a2/b2, portanto a2= 2b2, sendo um número par, pois quadrado de par é par. Como a é par, então a = 2c para algum c e, portanto 4c2 = 2b2, portanto, 2c2 = b2 . Concluímos que b2 é par e, portanto b também é par. Como a e b são pares, não podem ser primos entre si. Contradição! Conclui-se que não existem tais a e b.

Um exemplo em teoria dos conjuntos é a demonstração de que se A⊆B, então A∩C⊆B∩C. Esta demonstração ilustra como é o argumento típico para a prova de um condicional, ou seja, uma proposição na forma “Se P1 então P2”. Vejamos: Suponha que A⊆B, então todo a∈A é tal que a∈B. Seja C um conjunto e considere um elemento x∈A∩C. Pela definição de ∩ temos que x∈A e x∈C. Pela afirmação acima x∈A implica em x∈B, portanto temos que x∈B e x∈C,  daí x∈B∩C .

Concluímos então que “Se x∈A∩C, então x∈B∩C “. Portanto, temos A∩C⊆B∩C. Finalmente, concluímos que “Se A⊆B, então A∩C⊆B∩C “. Neste curso vamos nos deparar algumas vezes com demonstrações como as que acompanhamos anteriormente. Passamos agora a estudar algumas propriedades dos conjuntos infinitos. Suponha que o hotel Hilbert tenha uma quantidade infinita de quartos, numerados como H0, H1, H2,… o hotel Cantor também tem uma quantidade infinita de quartos, numerados como C0, C 1, C2,…. Ambos os hotéis estão lotados, há hospedes em todos os quartos. Devido a um vazamento de gás, o hotel Cantor é fechado e todos os hóspedes são realocados no hotel Hilbert. Para tanto, o gerente, Sr. Dedekind, rearranja os hóspedes da seguinte forma: hóspedes do hotel Hilbert que estão no quarto Hn devem se mudar para o quarto H2n e hóspedes do hotel Cantor no quarto Cn devem se mudar para o hotel Hilbert no quarto H2n+1.

Esse processo ilustra vários conceitos sobre conjuntos em primeiro lugar, o conjunto dos quartos em cada um dos hotéis é enumerável, porque existe um quarto para cada número natural. Um conjunto S é enumerável se existe uma função bijetora f :ℕ→ S .

Além disso, a solução dada pelo gerente do hotel mostra que a união de 2 conjuntos enumeráveis também é enumerável. Lembre-se: se os conjuntos S1 e S2 são enumeráveis então a sua união, S1∪S2 também é enumerável.

Um exemplo é o conjunto ℤ dos inteiros. Ele é enumerável porque você pode criar a função bijetora definindo f(n) = n/2 se n é par e f (n) = −(n +1)/2 se n é ímpar.

Agora vamos pensar no conjunto de todas as cadeias de caracteres (strings) não vazias que podemos formar com os caracteres ‘a’, ‘b’ e ‘c’. O nosso conjunto é S = {a, b, c, aa, ab, ac, ba, bb, bc, …} Observe que se você sabe escrever um programa de computador que imprime uma destas cadeias em cada linha, então podemos associar o natural n à cadeia que aparece na n-ésima linha (supondo que as linhas são numeradas a partir do 0). Portanto, o conjunto anterior é enumerável.

Cantor publicou em 1891 uma prova de que o conjunto dos números reais não é enumerável usando a técnica da diagonalização. Pesquise na internet sobre essa demonstração. (sugestão)

Click to listen highlighted text!