Matemática Discreta - 2 (ILC) Flashcards
Conjuntos, Indução, Recursão
O que é um conjunto? O que é um conjunto vazio?
Um conjunto é uma coleção desordenada de objetos distintos chamados elementos. Um conjunto vazio é um conjunto sem nenhum elemento.
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?
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.
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?
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.
Quais são as principais operações que é possível realizar com conjuntos? Qual o resultado dessas operações?
- 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)
O que é uma sequência? Qual é a sua notação?
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.
Como definir uma função de forma recursiva? Que outro nome damos para essa definição?
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.
O que é a cardinalidade de um conjunto? O que significa dizer que dois conjuntos possuem a mesma cardinalidade?
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.
Como mostrar que dois conjuntos A e B possuem a mesma cardinalidade usando apenas funções injetoras?
É 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.
O que significa dizer que um conjunto é contável?
Um conjunto é contável se ele for finito ou se possuir a mesma cardinalidade que o conjunto dos números naturais.
O conjunto dos números naturais é contável? E o dos inteiros ? E os racionais? E os reais?
O conjunto dos números naturais, inteiros e racionais é contável. Os reais não.
O conjunto de todos os algoritmos que podem ser escritos em uma determinada linguagem é contável? Justifique.
É. 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.
O que significa dizer que uma função é computável? Toda função é computável?
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.
Existem funções que não são computáveis? Justifique.
O conjunto de algoritmos que podem ser feitos é um conjunto contável. Por outro lado, existem conjuntos que não são contáveis
Como construir uma prova por indução fraca de uma proposição P?
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.
Explique por que e em quais situações a indução fraca é uma forma válida de demonstração.
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.
Por que a indução matemática não se encaixa na falácia de implorar a pergunta?
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.
Como construir uma prova por indução forte de uma proposição P?
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.
Em que situações é melhor usar indução fraca ao invés de indução forte? Em que situações o contrário ocorre?
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).
O que diz o princípio da boa ordenação ?
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.
Como é possível usar o princípio da boa ordenação em uma prova por indução?
É 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.
Como é possível usar o princípio da boa ordenação em uma prova por contradição?
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.
Como definimos uma estrutura ou um conjunto de forma recursiva?
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.
Dê uma definição recursiva de todas as palavras que podem ser criadas em uma linguagem a partir de um alfabeto.
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.
Dê uma definição recursiva do tamanho de uma string.
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.
Dê uma definição recursiva para a função fatorial.
Passo base:
- Fatorial de 0 é 1.
Passo indutivo:
- Se n > 0, fatorial de n é n * fatorial (n - 1).
Dê uma definição recursiva para a estrutura árvore binária completa.
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.
Como funciona a prova por indução estrutural ? Para que ela serve?
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.
Dê exemplos de formas de mostrar que uma prova por indução (fraca ou forte) é inválida.
- 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.
Qual a maior limitação matemática das provas por indução ?
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.
