Introdução a matemática discreta

Introdução a matemática discreta

1. Pensamento matemático

   • Proposições (Qualquer sentença que pode ser verdadeira ou falsa)
     • Existem proposições que ainda não foram provadas ou refutadas, elas são chamadas de conjecturas.
     • Falsa
     • Verdadeira
       • Se provada, é um teorema
       • Se for uma lei ou um princípio, é um axioma e não precisa ser provado
     • Trabalhando com proposições (Procurando situações lógicas em que as expressões sejam válidas)
       • - Podemos formar outras proposições a partir do que já temos. - Para este mapa, considere P e Q duas proposições.
       • (¬): Negação; neste estado, ¬P, é o contrário do estado lógico de P, pois ¬P nega P. Se P é verdade ¬P é falso, e se P é falso, ¬P é verdade.
       • (↔) Bijeção; neste caso temos uma implicação de ambos os lados, ou seja, P ↔ Q (lemos, P se e somente se Q), então para que essa expressão seja válida, Se P for verdade, então Q deve herdar esse estado verdadeiro, e da mesma forma se Q for verdade P deve herdade esse estado verdadeiro. Deve-se perceber que na implicação, se P for falso, Q é verdade, porém na bijeção, o teste acontecerá "indo e voltando", nos dois lados, então não pode haver falso se um for verdade.
       • (∨) : Disjunção inclusiva; (ou, ou ambas), assim uma pode ser verdadeira, ou ambas podem ser verdade. P ∨ Q, Então para que essa expressão seja válida, P ou Q, ou ambas deve ser verdade.
       • (→) : Implicação; devemos validar uma segunda proposição, se uma primeira for validada, logo P → Q (lemos, se P, então Q), assim para que essa expressão seja válida, se obtermos a verdade em P, Q deve herdar esse estado verdadeiro. Porém quando P é falso, não podemos falar nada sobre o estado de Q, pois a "implicação" valida Q pela verdade, e nada é dito sobre o estado de Q se P é falso, e pelo benefício da dúvida, afirmamos Q. Na computação não existe a dúvida, então Q precisa ser algo, então a afirmamos pois não foi refutado
       • (∧) : Conjução; (e), assim todas as proposições devem ser verdadeiras. P ∧ Q (lemos P e Q), Então para que essa expressão seja válida, P e Q deve ser verdade.
       • (EX-OR): Disjunção exclusiva; neste estado consideramos o teste de proposições na forma 'ou', assim ou uma, ou outra é verdade, mas não ambas. P (EX-OR) Q, Então para que essa expressão seja válida, ou P ou Q, deve ser verdade, mas não ambas.
       • O predicado agrupa várias proposições de uma lista padronizada, a nível infinito ou finito. Por exemplo: A² + A + 1 é primo. Este predicado mapeia cada A para uma proposição desta lista de A itens , e é escrito como P(A): "A² + A + 1" é primo
         • Quando queremos falar de todo A do predicado, usamos o quantificador universal ∀, assim podemos falar das propriedades em todo conjunto de proposições reunidas pelo predicado. Ex: ∀A ∈ N, A²+A+1 é primo. Porém essa afirmação é inválida, pois existe A nos naturais, tal que essa expressão não é verdade. Então precisamos do quantificador ∃.
         • Quando queremos falar de um único A do predicado, usamos o quantificador existencial ∃, assim podemos falar da veracidade de algo para um ou mais casos do predicado, pois existe um ou alguns elementos tais que a sentença existencial é verdadeira. Ex: ∃A ∈ N, A²+A+1 não é primo, isto é válido pois P(40) não é primo.
         • Fim