Matemática Discreta - 2 (ILC)

Question 1

O que é um conjunto? O que é um conjunto vazio?

Answer 1

Um conjunto é uma coleção desordenada de objetos distintos chamados elementos. Um conjunto vazio é um conjunto sem nenhum elemento.

Question 2

O que significa dizer que A é subconjunto de B? Todo conjunto é subconjunto de si mesmo ? Como provar que dois conjuntos são iguais? Como usar a definição de subconjunto para mostrar que dois conjuntos A e B são iguais?

Answer 2

A é um subconjunto de B se e somente se todo elemento que estiver presente em B também estiver presente em A. Por essa definição, temos também que todo conjunto é subconjunto de si mesmo. Para mostrar igualdade de conjuntos, mostre que um elemento x pertence a A se e somente se ele também pertence a B. Em outras palavras, mostre que A é subconjunto de B e B também é subconjunto de A.

Question 3

O que é o conjunto potência de um conjunto S? E o produto cartesiano de dois conjuntos A e B? Qual é a sua notação?

Answer 3

O conjunto potência de um conjunto S é o conjunto de todos os subconjuntos de S. O produto cartesiano é o conjunto de todos os pares ordenados (a,b) em que a pertence a A e b pertence a B. A notação do conjunto potência é 𝒫(S). A notação do produto cartesiano é A x B.

Question 4

Quais são as principais operações que é possível realizar com conjuntos? Qual o resultado dessas operações?

Answer 4

• A união B (conjunto com todos os elementos presentes em A ou B)
• A intersecção B (conjunto com todos os elementos presentes tanto em A quanto em B)
• A-B (conjunto de todos os elementos que estão em A mas não estão em B)
• Complemento de A (todos os elementos que não estão em A)

Question 5

O que é uma sequência? Qual é a sua notação?

Answer 5

Uma sequência é uma função que mapeia um subconjunto dos inteiros a um conjunto S. Nós usamos an para denotar a imagem do inteiro n.

Question 6

Como definir uma função de forma recursiva? Que outro nome damos para essa definição?

Answer 6

Para definir uma função de forma recursiva, definimos o valor da função quando x = 0 e, para x > 0, definimos o valor como uma função dos valores anteriores. Essa definição também pode ser chamada de relação de recorrência.

Question 7

O que é a cardinalidade de um conjunto? O que significa dizer que dois conjuntos possuem a mesma cardinalidade?

Answer 7

A cardinalidade de um conjunto é a quantidade de elementos dentro dele. Dois conjuntos possuem a mesma cardinalidade se e somente se é possível construir uma função bijetora que mapeia os elementos de A aos elementos de B.

Question 8

Como mostrar que dois conjuntos A e B possuem a mesma cardinalidade usando apenas funções injetoras?

Answer 8

É possível mostrar que dois conjuntos A e B possuem a mesma cardinalidade construindo uma função injetora que mapeia A para B e outra função que mapeia B para A.

Question 9

O que significa dizer que um conjunto é contável?

Answer 9

Um conjunto é contável se ele for finito ou se possuir a mesma cardinalidade que o conjunto dos números naturais.

Question 10

O conjunto dos números naturais é contável? E o dos inteiros ? E os racionais? E os reais?

Answer 10

O conjunto dos números naturais, inteiros e racionais é contável. Os reais não.

Question 11

O conjunto de todos os algoritmos que podem ser escritos em uma determinada linguagem é contável? Justifique.

Answer 11

É. Um programa de computador nada mais é do que um conjunto de valores que podem ser 0 ou 1. Isso quer dizer que todo programa pode ser escrito como um número formado apenas pelos algarismos 0 ou 1. Visto que todos os números envolvidos são naturais, esse conjunto não pode ter mais elementos que os números naturais e por isso a cardinalidade deve ser menor ou igual à dos números naturais.

Question 12

O que significa dizer que uma função é computável? Toda função é computável?

Answer 12

Significa dizer que é possível escrever um algoritmo capaz de encontrar os valores dessa função. Existem funções que não são computáveis.

Question 13

Existem funções que não são computáveis? Justifique.

Answer 13

O conjunto de algoritmos que podem ser feitos é um conjunto contável. Por outro lado, existem conjuntos que não são contáveis

Question 14

Como construir uma prova por indução fraca de uma proposição P?

Answer 14

Primeiro, mostre que o caso base (geralmente P(1)) é verdadeiro. Isso é chamado de passo base. Então mostre que, se P(k) é verdadeiro para um k arbitrário, P(k + 1) também será. Isso é chamado de passo indutivo.

Question 15

Explique por que e em quais situações a indução fraca é uma forma válida de demonstração.

Answer 15

Indução fraca é uma forma válida em situações onde se existe um menor elemento no conjunto para o qual se deseja realizar a prova. Ela é uma forma válida porque provamos que a afirmação é verdadeira tanto para o menor elemento quanto para o sucessor de um elemento qualquer. Visto que todo elemento no conjunto é sucessor do menor elemento ou sucessor de um sucessor distante do menor elemento, então a propriedade é válida para todos os números.

Question 16

Por que a indução matemática não se encaixa na falácia de implorar a pergunta?

Answer 16

Para ser uma falácia de implorar a pergunta, a prova deve ter como premissa o que se deseja provar (ou seja, a premissa deveria ser que P é verdadeiro para todo número). No caso da prova por indução, apenas concluímos que P(k+1) é verdadeiro se assumirmos P(k) é verdadeiro, mas não afirmamos que ele seja.

Question 17

Como construir uma prova por indução forte de uma proposição P?

Answer 17

Primeiro, mostre que o caso base (geralmente P(1)) é verdadeiro. Isso é chamado de passo base. Então mostre que, se P(1), P(2), …, P(k) é verdadeiro para um k arbitrário, P(k + 1) também será. Isso é chamado de passo indutivo.

Question 18

Em que situações é melhor usar indução fraca ao invés de indução forte? Em que situações o contrário ocorre?

Answer 18

Indução fraca deve ser preferida quando é fácil demonstrar que P(K) implica em P(K + 1). Indução forte deve ser preferida quando essa demonstração é difícil mas é fácil provar P(K + 1) a partir de um P(J) (J menor que k e maior que o caso base).

Question 19

O que diz o princípio da boa ordenação ?

Answer 19

Ele diz que todo conjunto não vazio dos números maiores ou igual a zero possui um elemento que é menor que todos os outros.

Question 20

Como é possível usar o princípio da boa ordenação em uma prova por indução?

Answer 20

É possível usar o princípio da boa ordenação para construir provas por indução matemática. Para isso, mostre que a afirmação vale para o menor elemento. Também mostre que se ela vale para um elemento, ela vale para seu sucessor. A conclusão é que ela vale para todos os elementos do conjunto.

Question 21

Como é possível usar o princípio da boa ordenação em uma prova por contradição?

Answer 21

Assuma que existe um subconjunto dos naturais que é solução para um determinado problema. Pelo princípio da boa ordenação, ele possui um menor elemento que podemos chamar de c. Mostre que a única forma de c existir é se existirem elementos menores que ele, o que contradiz a premissa que ele é o menor elemento.

Question 22

Como definimos uma estrutura ou um conjunto de forma recursiva?

Answer 22

Começamos com o passo base onde listamos todos os elementos que fazem parte do conjunto/estrutura. Então definimos o passo recursivo onde adicionamos novos elementos à estrutura usando os elementos já existentes.

Question 23

Dê uma definição recursiva de todas as palavras que podem ser criadas em uma linguagem a partir de um alfabeto.

Answer 23

Passo base:
- A palavras vazia (“”) pode ser formada em qualquer linguagem.

Passo indutivo:
- Se a palavra p faz parte da linguagem e o caractere c faz parte do alfabeto, então podemos obter uma nova palavra ao adicionar o caractere c ao final da palavra p.

Question 24

Dê uma definição recursiva do tamanho de uma string.

Answer 24

Passo base:
- Tamanho da string vazia (“”) é 0.

Passo indutivo:
- Tamanho da string que começa com a string s e termina com o caractere x é o tamanho da string s + 1.

Question 25

Dê uma definição recursiva para a função fatorial.

Answer 25

Passo base:
- Fatorial de 0 é 1.

Passo indutivo:
- Se n > 0, fatorial de n é n * fatorial (n - 1).

Question 26

Dê uma definição recursiva para a estrutura árvore binária completa.

Answer 26

Passo base:
- Um vértice isolado é uma árvore binária completa.

Passo indutivo:
- Se A1 e A2 são árvores sem nenhum vértice em comum, é possível criar uma nova árvore binária completa criando um novo vértice v e conectando ele a A1 e A2.

Question 27

Como funciona a prova por indução estrutural ? Para que ela serve?

Answer 27

A prova por indução estrutural serve para demonstrar que propriedade vale para toda estrutura formada a partir de uma regra recursiva. Para isso, são necessárias duas etapas: primeiro, demonstra-se essa propriedade para o caso base. Então, demonstra-se que etapas do passo recursivo mantém essa propriedade.

Question 28

Dê exemplos de formas de mostrar que uma prova por indução (fraca ou forte) é inválida.

Answer 28

• Mostre que o passo base não foi devidamente comprovado
• Mostre que o passo indutivo não está construído de forma correta.
• Mostre que o passo indutivo, apesar de válido para a maioria dos k, não é válido para alguns elementos do domínio.

Question 29

Qual a maior limitação matemática das provas por indução ?

Answer 29

Provas por indução podem ser usadas para provar que algo é verdade, mas dizem muito pouco sobre o porquê esse algo ser verdade. Por isso, outras provas são preferíveis quando se deseja extrair mais informações sobre as demonstrações.