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, n 2=2 k 2 =2 .2 k 2=22 k 2  , 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,
2
2
2
2
2
x = 2 n+ 1  =4n 4 n+ 1=2  2n 2n  1 , 2n 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, p 2, ⋯, p n }
Quero provar que { p 1, p 2, ⋯, p n }  q .
Basta mostrar que {p 1, p 2, ⋯, p n ,¬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:
a
Supor que √2 é um número racional. Logo, de (I), temos que √2=
b
De (II), segue que √2=
c
, em que c e d não possuem fatores em comum.
d
2
Elevando ambos os membros da igualdade ao quadrado, temos que 2= c 2 , ou seja,
d
2
c =2 d
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 ∃ x 0 , p x 0 é falso.
Tal x 0 é denominado de CONTRA-EXEMPLO