Matematica Discreta: - GabrielZoppo/PI4 GitHub Wiki

6- Técnicas de Demostração

-Usadas para validar ou refutar argumentos

-teorema:proposição do tipo p->q que é uma taltologia (p=>q)

-4 formas: prova direta, por contraposição, Resolução ao absurdo (RAA), indução.

A) Prova Direta: dado p-> q, supõe p é verdadeiro e provamos que q é verdadeira

p:hipótese

q:tese

EX: Se n e m são pares então n+m é par.

Prova: Sejam n e m pares,então existem k1 e k2 E /N tal que

n = 2k1 e m = 2k2

então n+m = 2k1 + 2k2 = 2(k1+k2).

Como(k1 + k2) E /N, então vale 2(k1 + k2) é um nº par.

B) Prova por contraposição: provar que p->q é baseado em mostrar que

-|q ->-|p

EX: Dado n ∈ /N, avalie se

(n! > n+1) -> (n > 2) (n<= 2) -> n!<= n+1) -> agora provamos que vale para n = 0,1 e 2 ou seja: Se n = 0, 0! <=1 Se n = 1, 1! <=2 Se n = 2, 2! <=3

C)Prova por RAA

1)Supomos p é verdadeiro

2)Negamos q

3)Chegamos em uma contradição,normalmente (q ∧ ¬q)

Ex: Prove por RAA que 0 é o unico elemento neutro da adição p: 0 é elemento neutro q: 0 é o unico

1º)Supomos que 0 é E.N 2º)0 não pe o unico, ou seja (∃ e ∈ |N) (e /= 0 e é E.N) 3º)Como 0 é E.N vale que 0 + n = n + 0 = n (n=e) 0 + e = e + 0 = e (i) 4º)Como e é E.N vale que e + n = n + e = n (n=0) e + 0 = 0 + e = 0 (ii)

Por transitividade em (i) e (ii),tems que e = 0, o que é um absurdo, pois e/= 0 na 2ª parte da prova. Portanto , 0 é unico E.N da adição

7) Regras de Inferência

A)modus ponens : (MP) (p->q) ^ p logo q B) modus tolens: (MT) (p->q) ^ não q logo não p C)Silagismo hipotético (SH) (p->q)^(q->r) logo p->r

  1. t -> g
  2. não t -> m
  3. g -> c
  4. não c logo m
  1. t -> c SH(1,3)
  2. não t MT(5,4)
  3. m MP(2,6) Portanto a fórmula é valida

prove por R.I que (p->) ^ (|-q) ^ (-|p -> r) logo r

⚠️ **GitHub.com Fallback** ⚠️