aula 11 02

Prévia do material em texto

Prova de Implicações
Uma implicação é verdadeira quando a verdade do seu antecedente acarreta a verdade 
do seu consequente.
Ex.: Considere a implicação:
“Se chove, então a rua está molhada”.
Observe que a implicação não afirma nem que está chovendo nem que a rua está 
molhada, mas que existe uma certa relação de causa e efeito entre chover e a rua estar 
molhada.
Quando sabemos que uma implicação é verdadeira, não podemos concluir que seu 
antecedente é verdadeiro, nem que seu consequente é verdadeiro, mas que não 
podemos considerar seu antecedente verdadeiro e seu consequente falso.
Essa análise da relação entre o antecedente e o consequente de uma implicação 
verdadeira nos leva a considerar que para provar implicações, podemos utilizar o 
seguinte método.
Método da Suposição
Para provar uma implicação “se p, então q”, é suficiente fazer o seguinte:
1) Supor que o antecedente p é verdadeiro;
2) Provar que o consequente q é verdadeiro, usando p como premissa (hipótese).
Ex.: Proposição:
P(p, q) = Se n é um número natural par, então n² é um número natural par.
Definição: seja n∈ℕ . Dizemos que n é par se existe um número natural k tal que 
n = 2k.
Prova: p → q
Suponha que n é par. 
Então, n = 2k, em que k∈ℕ .
Desta forma, n2=2 k 2=2 .2 k 2=22 k2 , em que 2 k 2∈ℕ .
Logo, n² é par e portanto P(p, q) é V.
Método da Contraposição
Para provar que p → q, basta fazer o seguinte:
1) Supor que a negação do consequente, ¬q, é verdadeira;
2) provar que a negação do antecedente, ¬p, é verdadeira, usando ¬q como 
premissa 
 ( p q ≡ ¬q¬ p )
Ex.: Seja x um número natural qualquer. 
P(p, q) = Se x² é par, então x é par.
Prova: x não é par → x² não é par.
Supondo que x é ímpar, temos que x = 2n + 1, n∈ℕ . 
Logo, x2=2 n+1 2=4n 24 n+1=2 2n22n 1 , 2n 22n∈ℕ . 
Assim, x² é impar, ou seja, x² não é par.
Tautologia (t): é uma proposição que é sempre verdadeira independentemente dos 
valores-verdade das afirmações que compõem a proposição.
Exs.: p → p, (¬ ¬ p) ↔ p, p ∨ ¬ p , 
 (p → q ) ↔ (¬q → ¬p)
Contradição (c): proposição que é sempre falsa.
Exs.: p ∧ ¬ p , p ↔ ¬p
Método de Redução ao Absurdo (Prova por Contradição)
A prova por contradição consiste em acrescentar a negação da conclusão ao conjunto 
de premissas e mostrar, através das regras de inferência, que esta inclusão leva 
logicamente a uma contradição.
Conjunto de premissas: { p1, p2,⋯ , pn }
Quero provar que {p1, p2,⋯ , pn}  q .
Basta mostrar que {p1, p2,⋯ , pn ,¬q}  { pi ∧ ¬ pi} , ou seja, ¬q → c, onde 
c é uma contradição.
Ex.: Proposição: √2 não é um número racional.
Premissas:
I. Todo número racional positivo pode ser escrito como uma fração de dois 
números naturais a e b, com b≠0 .
II. Toda fração a/b de dois números naturais pode ser simplificada até uma fração 
c/d, onde c e d não possuem fatores comuns.
III.Todo número natural é par ou ímpar de maneira exclusiva. Os números pares 
podem ser escritos na forma “2m”, m∈ℕ e os ímpares, na forma “2n + 1”, 
n∈ℕ .
IV.Se o quadrado de um número é par, então este número é par.
PROVA: Supor que √2 é um número racional. Logo, de (I), temos que √2=ab 
De (II), segue que √2= cd , em que c e d não possuem fatores em comum. 
Elevando ambos os membros da igualdade ao quadrado, temos que 2= c
2
d 2
, ou seja, 
c2=2d 2 (1).
De (III), concluímos que c² é par. De (IV), é possível concluir que c é par.
Portanto, de (III), temos que:
c = 2m (2)
Substituindo (2) em (1), segue que:
(2m)² = 2d² e, daí, 4m² = 2d² ↔ 2m² = d², ou seja, d² é par, e, consequentemente, 
d é par, e portanto, d = 2n.
Assim, c = 2m e d = 2n, acarretando que c e d possuem 2 como um fator comum, 
contradizendo a premissa (II). 
Portanto, √2 não é um número racional.
Função Proposicional
p(x) torna-se uma proposição sempre que x for substituído por a∈A , ou seja, p(x) 
é uma sentença com a propriedade que p(a) é V ou F.
Ex.: p x : x27 é uma função proposicional se A=ℝ , e não se A=ℂ 
Outra maneira de lidar com funções proposicionais, observando que p(x) pode ser V 
para todo x∈A , para algum x 0∈A ou para nenhum x∈A
Quantificadores: ∀ , ∃
Notação: 
∀ = para todo ou qualquer que seja (quantificador universal)
∀ x∈A p x  ou ∀ x , p  x 
∃ = existe, para algum, para ao menos um (quantificador existencial)
∃ x∈A p x ou ∃ x , p x 
Negação: proposições com quantificadores
Ex.: “ Todos os homens são mentirosos”
não é verdade que (todos os homens são mentirosos)
existe ao menos um homem que não é mentiroso
 ¬ ∀ x∈H  (x é mentiroso) equivale a
 ∃ x∈H  (x não é mentiroso) 
Teorema (De Morgan)
 ¬ ∀ x∈A px  ↔ ∃ x∈A¬ p x 
 ¬ ∃ x∈A p x ↔ ∀ x∈A¬ px 
Dado que ¬ ∀ x∈A px  ↔ ∃ x∈A¬ p  x  , para mostrar que ∀ x , p x
é falso, basta que ∃ x0 , p x0 é falso. 
Tal x 0 é denominado de CONTRA-EXEMPLO