Lógica e Matemática Discreta

Lógica e Matemática Discreta

1. Indução Finita

   • 1ª Forma
     • Passo 1: Caso inicial, mostrar que vale para n0
       • Passo 2: admitir que vale para k (hipóteses de indução)
         • Passo 3: calcular para k+1, usando a hipótese de indução. Para calcular para k+1 normalmente é necessário agregar aos dois lados da equação ( se for uma igualdade) o fator referente a k+1, seguindo a lógica da afirmação inicial.
           • Exemplo: 1²+2²+...+n²=n(n+1)(2n+1)/6.
             • p/ n=k. 1²+2²+..k²=k(k+1)(2k+1)/6
               • Para provar para k+1, somamos o fator (k+1)² nos dois lados da equação para n=k
                 • 1²+2²+..k²+(k+1)²=k(k+1)(2k+1)/6 + (k+1)²
                   • Manipulando a equação, usando como objetivo a forma apresentada,
                     • 1²+2²+..k²+(k+1)²=(k+1)(2k²+7k+6) = (k+1)(k+2)(2k+3)
                       • Conclusão: pelo princípio da indução finita a afirmação P(n) vale para n>=1
           • Para desigualdades o raciocínio é mais complexo, e deve-se criar situações lógicas para concluir o PIF.
   • 2ª Forma (Indução FORTE):
     • Passo 1: Caso inicial, mostrar que vale para n0
       • Passo 2: admitir que vale para n tal que a<=n<=k (hipóteses de indução)
         • Passo 3: provar para k+1, usando a hipótese de indução.
   • Princípio da Boa Ordem
   • Seja P(n) uma afirmação sobre o número natural n>=n0, com n0 fixo. Se para n0 a afirmação é verdadeira. Para k>n0, se a afirmação vale para n=k, então é verdadeira para n=k+1

2. ANÁLISE COMBINATÓRIA

   • Princípio da Contagem: número de maneiras de tomar decisões que envolve mais de uma decisão, é o produto das possibilidades das decisões se e somente se uma decisão independe da outra.
   • 1ª Existem restrições específicas que precisa ser analisadas separadamente. Ex. posições específicas de localização
     • NÃO
       • 2ª Pergunta: a ordem faz diferença?
         • NÂO
           • Combinação: n!/[k!(n-k)!]. n tota de conjuntos e k total do subconjunto
             • Número de subconjuntos de A com k elementos. Ou seja, a ordem não faz diferença. Ex 12345 é igual a 13245
         • SIM
           • 3ª Pergunta: o número de elementos escolhidos (p) é igual a quantidade de elementos possíveis (n)?
             • SIM
               • SIM! Permutação: n!
                 • Permutação Circular: (n-1)!
                 • Permutação com repetição (rm, quantidade de elementos repetidos): n!/(r1!r2!...)
                 • Ordenar uma sequência de objetos onde cada situação formada é diferente da outra. Ou seja a sequencia é importante. Ex. A ordem 12345 é diferente de 13245
             • NÃO
               • NÃO! Arranjo (n!/(n-p)!): ocorre quando o número de escolhas é menor que a quantidade presente no conjunto. Ex. 5 cartas retiradas de um baralho com 52 cartas, onde a ordem faz diferença
     • SIM
       • Inicia-se a contagem de possibilidades pela mais restritiva.
         • Número ímpares com 4 algarismos distintos:
           • 1º. 4 algarismos
             • 2º O último algarismo só pode ser (1,3,5,7,9). 5 possibilidades
               • 3º O primeiro algarismo não pode ser 0 nem igual ao último. 8 possibilidades
                 • 4º O segundo algarismo deve ser diferente dos outros 2. (8 possibilidades)
                   • 5º o quarto algarismo deve ser diferente de todos. (7 possibilidades)
         • Quando não é possível ter certeza das possibilidades, pq depende de uma outra decisão, deve-se separar em mais de um caso ou mudar a ordem de análise (a que for mais conveniente)

3. Conjuntos

   • Cardinalidade: números de elementos
   • Partes de A P(A) : conjunto dos subconjuntos de A

4. Teorema Fundamental da Aritmética

   • Todo número inteiro positivo pode ser escrito como produto de números primos e essa fatoração é única