MD Logica Matematica Pt. IV Novo

Matemática Discreta
Lógica matemática pt. IV
• Teoremas
• Implicações, implicação recı́proca, implicação contrapositiva
• Dupla implicação
Lógica matemática pt. IV Matemática Discreta

Teoremas
O que é um teorema?
Um teorema é uma proposição p para a qual existe uma

demonstração, isto é, uma justificativa irrefutável de que p é
verdadeira.
Um exemplo:
Teorema
Existe um número primo ı́mpar.
Demonstração:
3 é um número primo ı́mpar. □
(Lembrando: para afirmar que uma proposição do tipo

∃x ∈ U | p(x) é verdadeira, basta exibir um exemplo)
Obs: o sı́mbolo □ indica o fim de uma demonstração.

Implicação
Grande parte dos teoremas são enunciados em formato de
implicação. Frequentemente as demonstrações dos teoremas
envolve implicações. Implicações são proposições no formato “se...,
então ...”. Mais precisamente:
Definição: implicação
Sejam p e q proposições. A proposição composta p ⇒ q que se lê
“p implica q”, ou “se p, então q”, é definida por
p q p⇒q
V V V
V F F
F V V
F F V
p é chamada hipótese, ou premissa, de p ⇒ q. q é chamada tese,

ou conlcusão, de p ⇒ q.

Implicação
p q p⇒q
V V V
V F F
F V V
F F V
!!! Uma implicação não é uma relação de causa e efeito. Ela

simplesmente diz que sempre que a hipótese é verdadeira, a tese é
verdadeira.
Exemplos:
• “se 2 · 3 = 6, então 6 é par”=(V ⇒ V ) = V (aqui existe relação
de causa e efeito)
• “se a soma dos ângulos internos de todo triângulo é 180o , então
6 é par”=(V ⇒ V ) = V (embora aqui não exista relação de causa
e efeito)

Implicação
p q p⇒q
V V V
V F F
F V V
F F V
Exemplos:
• “se 2 + 2 = 5, então a quantidade de átomos na terra é
finita”=(F ⇒ V )=V
• “se 2 + 2 = 5, então todo polinômio real admite uma raiz”
=(F ⇒ F )=V
(Moral: partindo de uma premissa falsa, pode-se chegar a qualquer
conclusão. )

Implicação
Exemplos:
• Um diálogo dos Simpsons:
Sr. Burns, para Smithers: “Sabe Smithers, acho que eu vou doar 1
milhão de dólares para o orfanato local...”’
(pausa)
Sr. Burns: “... quando os porcos voarem.”’
(os dois gargalham)
(um porco passa voando, e os dois ficam muito surpresos)
Smithers: “Vai doar o milhão de dólares agora, senhor?”
Sr. Burns: “Não, prefiro não”
“se os porcos voam, então o sr. Burns doa US$ 1M para o

orfanato”
=(F ⇒ F ) = V , assumindo que os porcos não voam
=(V ⇒ F ) = F , depois de saber que os porcos voam

Implicação
Uma lei de trânsito diz: “é proibido aos menores de 18 anos
dirigir.” Interpretando como uma implicação, esta lei pode ser
expressa como:
“se uma pessoa dirige, então ela deve ser maior de 18 anos”.
• Se uma pessoa maior de 18 anos está dirigindo, a lei está sendo
respeitada. (V ⇒ V = V )
• Se uma pessoa maior de 18 anos não está dirigindo, a lei está
sendo respeitada. (F ⇒ V = V )
• Se uma pessoa menor de 18 anos não está dirigindo, a lei está
sendo respeitada. (F ⇒ F = V )
• Se uma pessoa menor de 18 anos está dirigindo, a lei está sendo
desrespeitada. (V ⇒ F = F )
De maneira geral,
Teorema 1
Uma implicação p ⇒ q é falsa exatamente quando a hipótese p é
verdadeira e a tese q é falsa.
Implicação
Teorema 1
Uma implicação p ⇒ q é falsa exatamente quando a hipótese p é
verdadeira e a tese q é falsa.
Teorema 2
Sejam p e q proposições. Então, p ⇒ q ≡ ¬p ∨ q.
Demonstração: Pelo Teorema 1, ¬(p ⇒ q)≡(p ∧ ¬q). Note que

p ⇒ q é a negação de ¬(p ⇒ q). Logo,
p ⇒ q ≡ ¬¬(p ⇒ q)≡¬(p ∧ ¬q) ≡ ¬p ∨ ¬¬q ≡ ¬p ∨ q,
onde a penúltima equivalência se dá por uma das leis de De

Morgan. □
Obs: toda operação lógica binária pode ser escrita em termos de ∧,
∨ e ¬ (não vamos provar, por enquanto)

Implicação recı́proca e contrapositiva
Dada uma implicação p ⇒ q, temos associadas duas outras
implicações importantes:
A Recı́proca de p ⇒ q, é q ⇒ p,
A contrapositiva de p ⇒ q, é ¬q ⇒ ¬p.
• Veremos que a contrapositiva de p ⇒ q é logicamente equivalente
a p ⇒ q, o que nos dará uma ferramenta de demonstração.
• p ⇒ q não é equivalente a sua recı́proca q ⇒ p: colocando
p = V e q = F temos
(V ⇒ F ) = F ̸= V = (F ⇒ V ). □
Obs sobre notação: p ⇒ q também pode ser lido como “p é uma

condição suficiente para q”, ou como “q é uma condição necessária
para p”.
Um exemplo para ilustrar a diferença acima é o seguinte, para o
universo dos reais: “se x é racional, então x 2 é racional” é
verdadeira, porém “se x 2 é racional, então x é racional”.
Dupla implicação
Obs sobre notação: p ⇒ q também pode ser lido como “p é uma

condição suficiente para q”, ou como “q é uma condição necessária
para p”.
Para ilustrar, considere p=“Ana é mineira” e q=“Ana é brasileira”.
Obviamente, ser a condição de ser mineira é suficiente para a
condição de ser brasileira, mas não é necessária.
Definição: dupla implicação
Sejam p e q proposições. Escrevemos p ⇔ q e dizemos que “p se e
somente se q” quando valerem p ⇒ q e q ⇒ p. Isto é, por
definição,
p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p).
De acordo com a notação no topo do slide, p ⇔ q é o mesmo que

dizer que p é uma condição necessária e suficiente para q.

MD Logica Matematica Pt. IV Novo

Enviado por

Direitos autorais:

Formatos disponíveis

MD Logica Matematica Pt. IV Novo

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

MD Logica Matematica Pt. IV Novo

Enviado por

Direitos autorais:

Formatos disponíveis

Matemática Discreta

Lógica matemática pt. IV

Lógica matemática pt. IV Matemática Discreta

Um teorema é uma proposição p para a qual existe uma

(Lembrando: para afirmar que uma proposição do tipo

Lógica matemática pt. IV Matemática Discreta

p é chamada hipótese, ou premissa, de p ⇒ q. q é chamada tese,

Lógica matemática pt. IV Matemática Discreta

!!! Uma implicação não é uma relação de causa e efeito. Ela

Lógica matemática pt. IV Matemática Discreta

Lógica matemática pt. IV Matemática Discreta

“se os porcos voam, então o sr. Burns doa US$ 1M para o

Lógica matemática pt. IV Matemática Discreta

Demonstração: Pelo Teorema 1, ¬(p ⇒ q)≡(p ∧ ¬q). Note que

p ⇒ q ≡ ¬¬(p ⇒ q)≡¬(p ∧ ¬q) ≡ ¬p ∨ ¬¬q ≡ ¬p ∨ q,

onde a penúltima equivalência se dá por uma das leis de De

Lógica matemática pt. IV Matemática Discreta

Obs sobre notação: p ⇒ q também pode ser lido como “p é uma

Obs sobre notação: p ⇒ q também pode ser lido como “p é uma

De acordo com a notação no topo do slide, p ⇔ q é o mesmo que

Lógica matemática pt. IV Matemática Discreta

Você também pode gostar