Logica Proposicional

Prévia do material em texto

LÓGICA MATEMÁTICA
Lógica Proposicional
PROPOSIÇÕES
Só assume dois valores ( V ou F )
São representadas por letras do alfabeto: 
Exemplos A, B, C, P, Q, R, etc.
OPERADOR CONJUNÇÃO
Operador E - AND
Símbolo: ^
Conjunção
Português:
e; mas; também
Operador Binário
A B A^B
F F F
F V F
V F F
V V V
OPERADOR DISJUNÇÃO
Operador OU - OR
Símbolo: v
Disjunção
Português:
Ou
Operador Binário
A B A v B
F F F
F V V
V F V
V V V
OPERADOR OU-EXCLUSIVO
Operador XOR
Símbolo: ⊕
Português:
Ou x ou y
Operador Binário
A B A ⊕ B
F F F
F V V
V F V
V V F
OPERADOR NOT
Operador Não - NOT
Símbolo: ~
Português
Não, é falso que,
Não é verdade que.
Operador Unário
A ~A
F V
V F
OPERADOR CONDICIONAL
Operador IF- Se
Símbolo: →
Português
Se A então B
Operador Binário
A B A→B
F F V
F V V
V F F
V V V
OPERADOR CONDICIONAL
Português
Se A, então B;
A implica B;
A, logo B;
A somente se B;
B segue A;
A é condição suficiente para B;
B é condição necessária para A;
OPERADOR CONDICIONAL
Seja P a proposição “ Maria aprende matemática 
discreta” e q a proposição “ Maria vai conseguir um 
bom emprego”. Expresse p→q em português:
Se Maria aprender matemática discreta , então ela 
vai conseguir um bom emprego
Maria vai encontrar um bom emprego quando 
aprender matemática discreta
Para conseguir um bom emprego, é suficiente que 
Maria aprenda matemática discreta
OPERADOR CONDICIONAL
Proposição condicional: p→q
Oposta: q→p
Contrapositiva: ~q →~p
Inversa: ~p → ~q
OPERADOR CONDICIONAL
Qual a contrapositiva, a oposta e a inversa da 
proposição condicional: “O time da casa ganha 
sempre que está chovendo.”
Isso é equivalente a “Se está chovendo, então o time 
da casa ganha.”
p: Se está chovendo e q: o time da casa ganha
Oposta: Se o time da casa ganha, então está chovendo
Contrapositiva: Se o time da casa não ganha, então 
não está chovendo.
Inversa: Se não está chovendo, então o time da casa 
não ganha.
OPERADOR BI-CONDICIONAL
Operador: Se e Somente Se
Símbolo: ↔
Operador Binário
A ↔ B≣(A→B) ^ (B→A)
Condição necessária e suficiente
A B A↔B
F F V
F V F
V F F
V V V
OPERADOR BI-CONDICIONAL
Seja a proposição “ Você pode tomar o avião” e q a 
proposição “Você comprou uma passagem”. Então 
p↔q é a proposição:
Você pode tomar um avião se e somente se você 
comprou uma passagem.
TRADUZINDO
Qual a tradução de “ Você pode acessar a Internet a 
partir deste campus somente se você é um “expert” em 
Ciência da computação ou não é um novato” para as 
expressões lógicas?
Proposições:
a: acessar a Internet
c: “expert” em ciência da computação
n: novato
Resposta: a→ ( c v ~n )
TRADUZINDO
Qual a tradução de “ A resposta automática não pode 
ser enviada quando o sistema está sobrecarregado”
Equivale a: Se o sistema está sobrecarregado a 
resposta não pode ser enviada.
Proposições:
p: a resposta automática pode ser enviada
p: o sistema está sobrecarregado
Resposta: q→ ~p
EXERCÍCIOS
Item Pergunta
a) Curitiba é a capitão do Paraná
b) BH é a capital do Pará
c) 2+3=5
d) 5+7=10
e) x+2=11
f) Responda essa questão
Proposição Valor
SIM V
SIM F
SIM V
SIM F
NÃO
NÃO
1) Quais dessas sentenças são proposições? Quais os 
valores verdade das que são proposições?
EXERCÍCIOS
Item Sentença 
a) Hoje é quinta
b) Não há poluição em SP
c) 2+1=3
d)
O verão no Rio é quente e 
ensolarado
Negação
Hoje não é quinta
Há poluição em SP
2+1 ≠ 3
O verão no Rio não é quente 
nem ensolarado
2) Qual a negação de cada proposição a seguir 
EXERCÍCIOS
Não foram descobertos tubarões perto da praia
Nadar na praia é permitido, e foram descobertos 
tubarões perto da praia
Nadar na praia não é permitido ou foram 
descobertos tubarões perto da praia
Se nadar na praia é permitido então não foram 
descobertos tubarões perto da praia
a) ~q
b) p ^ q
c) ~p v q
d) p → ~q
Considere que p e q são as proposições “Nadar na praia é 
permitido” e “Foram descobertos tubarões perto da 
praia”, respectivamente. Expresse cada uma dessas 
proposições como uma sentença em português.
EXERCÍCIOS
Se tubarões não foram descobertos perto da 
praia, então nadar na praia é permitido.
Se nadar na praia não é permitido então 
foram descobertos tubarões perto da praia
Nadar na praia é permitido se e somente se 
não forem descobertos tubarões perto da praia
Nadar na praia não é permitido e ou nadar na 
praia é permitido ou foram descobertos 
tubarões perto da praia.
e) ~q→p
f) ~p→~q
g) p↔~q
h) ~p^(p v ~q)
EXERCÍCIOS
Considere que p e q são proposições. 
p: Você dirige a mais de 104 km/h 
q: Você recebe uma multa por excesso de velocidade
Escreva as proposições usando p, q e os conectores 
lógicos.
a) Você não dirige a mais de 104km/h.
b)
Você dirige a mais de 104km/h, mas 
não recebe uma multa por excesso 
de velocidade
~p
p ^ ~q
EXERCÍCIO
c) Você receberá uma multa por excesso de velocidade se 
dirigir a mais de 104km/h.
d)
Se você não dirigir a mais de 104km/h, você não 
receberá uma multa por excesso de velocidade.
e) Dirigir a mais de 104km/h é suficiente para receber uma 
multa por excesso de velocidade
f) Você recebe uma multa por excesso de velocidade, mas 
você não dirigi a mais de 104km/h
g) Sempre que receber uma multa por excesso de 
velocidade, você estará dirigindo a mais de 104km/h
p→q
~p→~q
p→q
q^~p
q→p
EXERCÍCIO
2+2=4 se e somente se 1+1=2
1+1=2 se e somente se 2+3=4
1+1=2 se e somente se macacos puderem 
voar
0>1 se e somente se 2>1
V
F
F
V
Determine se esses bi-condicionais são verdadeiros ou falsos
EXERCÍCIO
Se 1+1=2, então 2+2=5
Se 1+1=3, então 2+2=4
Se 1+1=3, então 2+2=5
Se macacos puderem voar, então 1+1=3
F
V
V
V
Determine se esses bi-condicionais são verdadeiros ou falsos
EXERCÍCIO
a) Café ou chá vem com o jantar
b) Uma senha deve ter ao menos três dígitos ou 
oito caracteres de comprimento
c)
O pré-requisito para o curso é um curso de 
teoria dos números ou um curso em 
criptografia
d) Você pode jogar usando dólares americanos ou 
euros
E
I
I
E/I
Para cada uma das sentenças determine se é ou 
inclusivo( disjunção) ou exclusivo.
EXERCÍCIO
a) Neva sempre que o vento sopra do nordeste
Resp: Se o vento soprar do nordeste, então nevará.
b) As macieiras florescerão se continuar quente por uma 
semana
Resp: Se continuar quente por uma semana, então as 
macieiras florescerão
Escreva cada uma das proposições da forma “ se p, 
então q”
EXERCÍCIO
c) O Atlético ganhar o Mineiro implica em derrotar o 
Cruzeiro
Resp: Se o Atlético ganhar o Mineiro, então ele ganhou do 
Cruzeiro
d) É necessário andar 8 km para chegar ao topo do monte.
Resp: Se você chegou ao topo do monte, então você andou 8 
km.
Escreva cada uma das proposições da forma “ se p, 
então q”
EXERCÍCIO
e) Para conseguir mandato como professor é suficiente ser 
famoso mundialmente.
Resp: Se você for famoso mundialmente então conseguirá 
mandato de professor
f) Se você dirigir por mais de 400 km terá que comprar 
gasolina.
Resp: Se você dirigir por mais de 400 km, então você terá que 
comprar gasolina.
Escreva cada uma das proposições da forma “ se p, 
então q”
EXERCÍCIO
g) Sua garantia é válida apenas se você comprou seu 
aparelho em menos de 90 dias.
Resp: Se a sua garantia for válida então você deverá ter 
comprado seu aparelho em menos de 90 dias.
h) Maria nadará ao menos que a água esteja muito fria.
Resp: Se a água não estiver muito fria, entãoMaria nadará.
Escreva cada uma das proposições da forma “ se p, 
então q”
EXERCÍCIO
a) Se nevar hoje esquiarei amanhã.
Resposta: p: Nevar hoje; q: esquiarei amanhã; p→q
Oposta:
q→p :Se eu esquiar amanhã então nevou hoje.
Oposta:
q→p :Eu esquiarei amanhã se nevar hoje.
Contrap: ~q→~p: Se eu não esquiar amanhã, então não 
nevou hoje.
Inversa ~p→~q: Se não nevar hoje não esquiarei amanhã 
Determine a oposta, a contrapositiva e a inversa de cada 
uma das proposições condicionais.
EXERCÍCIO
b) Eu venho a aula sempre que há uma prova
Resposta: p: há uma prova; q: vou a aula; p→q
Oposta: q→p : Se vou a aula então há uma prova
Contrap: ~q→~p: Se eu não vou a aula, então não haverá 
prova.
Inversa ~p→~q: Se não há uma prova então não vou a aula. 
Determine a oposta, a contrapositiva e a inversa de cada 
uma das proposições condicionais.
EXERCÍCIO
a) 8 é par ou 6 é ímpar.
b) 8 é par e 6 é ímpar.
c) 8 é ímpar ou 6 é ímpar.
d) 8 é ímpar e 6 é ímpar.
e) Se 8 for ímpar então 6 é ímpar.
f) Se 8 for par então 6 é ímpar.
g) Se 8 for ímpar então 6 é par.
h) Se 8 for ímpar e 6 for par, então 
8<6.
A C Resp
V F V
V F F
F F F
F F F
F F V
V F F
F V V
F F V
Determine o valor lógico de cada proposição abaixo 
EXERCÍCIO
a) A resposta é 2 ou 3.
Resp: A resposta não é 2 e não é 3
b) Pepinos são verdes e tem sementes
Resp: Pepinos não são verdes ou não tem sementes
c) 2 < 7 e 3 é ímpar
Resp: 2 ≥ 7 ou 3 é par
Escreva a negação das sentenças
EXERCÍCIO
a) Se a comida é boa então o serviço é excelente.
Resp: C: comida boa; S: serviço é excelente
Equivale: C→S
Negação: ~(C→S)
Condicional ~(~C v S)
De Morgan C ^ ~S
Equivale: A comida é boa e o serviço não é excelente
Escreva a negação das sentenças
EXERCÍCIO
b) Ou a comida é boa ou o serviço é excelente.
Resp: C: comida boa; S: serviço é excelente
Equivale: C ⊕ S
Equivale: ~(C ↔ S)
Negação ~~(C ↔ S)
Equivale: (C ↔ S)
Resp: A comida é boa se e somente se o serviço for 
excelente
Escreva a negação das sentenças
EXERCÍCIO
c) A comida é boa ou o serviço é excelente.
Resposta 
Alternativa C: comida boa; S: serviço é excelente
Equivale: C v S
Negação ~(C v S)
De Morgan ~C ^ ~S
Português A comida é ruim e o serviço não é excelente.
Escreva a negação das sentenças
EXERCÍCIO
a)
Se os preços subirem, então haverá muitas casas para 
vender e elas serão caras; mas se as casas não forem caras, 
então, ainda assim, haverá muitas casas para vender.
P: preços subirem V: muitas casas para 
vender
C: casas caras
Resposta: P→(V^C) ^ (~C→V)
Escreva cada uma das proposições compostas a seguir 
em notação simbólica usando letras para denotar os 
componentes.
EXERCÍCIO
b)
Tanto ir dormir como ir nadar é uma condição suficiente 
para troca de roupas; no entanto, mudar de roupa não 
significa que vai nadar
D: ir dormir N: ir nadar T: trocar de roupas
Resposta: [(D v N)→T] ^(T→~N)
Escreva cada uma das proposições compostas a seguir 
em notação simbólica usando letras para denotar os 
componentes.
EXERCÍCIO
c) Vai chover ou nevar mas não ambos
C: chover N: nevar
Resposta: C ⊕ N
Resposta alternativa: (C → ~N) ^ (N→~C)
Escreva cada uma das proposições compostas a seguir 
em notação simbólica usando letras para denotar os 
componentes.
EXERCÍCIO
d) Se o cavalo estiver descansado o cavaleiro vencerá
C: cavalo descansado V: cavaleiro vencerá
Resposta: C → V
Escreva cada uma das proposições compostas a 
seguir em notação simbólica usando letras para 
denotar os componentes.
EXERCÍCIO
e)
Um cavalo descansado é uma condição necessária 
para o cavaleiro vencer.
C: cavalo descansado V: cavaleiro vencer
Resposta: V → C
Escreva cada uma das proposições compostas a seguir 
em notação simbólica usando letras para denotar os 
componentes.
EXERCÍCIO
f)
Uma condição suficiente para o cavaleiro vencer é que 
a armadura seja forte ou o cavalo esteja descansado.
C : c a v a l o 
descansado
V: cavaleiro vencer A: armadura forte
Resposta: (A v C) → V
Escreva cada uma das proposições compostas a 
seguir em notação simbólica usando letras para 
denotar os componentes.
PARA LEMBRAR
Se eu falar que estudar é uma condição suficiente para 
passar o que isso quer dizer?
Resposta: que basta você estudar que você vai passar.
Se eu falar que estudar é uma condição necessária 
para passar o que isso quer dizer?
Resposta: que você precisa estudar para passar mas 
não necessariamente só isso, ou
Que se você passou é porque estudou.
TABELA VERDADE
É utilizada para provar qualquer proposição
Possui 2n linhas, onde n é o número de proposições
Exemplo: ( p v ~q ) → ( p ^ q )
p q ~q p v ~q p ^ q (p v q) → (p ^ q)
F F V V F F
F V F F F V
V F V V F F
V V F V V V
TABELA VERDADE
Observando a tabela verdade verificamos que a 
proposição não é verdadeira. Para ser todas as 4 linhas 
teriam que ter valor V
Prioridade dos operadores
Operador Prioridade
~ 1
^ 2
v 3
-> 4
<-> 5
TABELA VERDADE
Tautologia: todas as linhas são V, isto é, é verdadeira 
para qualquer entrada
Contradição: todas as linhas são F, isto é, é falsa para 
qualquer entrada
Contingência: Não é tautologia nem contradição
Se duas proposições tem exatamente a mesma tabela 
verdade, então elas são proposições equivalentes
EXERCÍCIO
Construa a tabela verdade da expressão (~A v ~B)→ 
~(A ^ B)
A B ~A ~B ~A v ~B A^B ~(A ^ B) (~A v ~B)→ 
~(A ^ B)
F F V V V F V V
F V V F V F V V
V F F V V F V V
V V F F F V F V
EQUIVALÊNCIAS LÓGICAS
Equivalências Nome
p ^ V ≣ p Propriedade dos elementos 
neutrosp v F ≣ p
Propriedade dos elementos 
neutros
p v V ≣ V
Propriedade de dominação
p ^ F ≣ F
Propriedade de dominação
p v p ≣ p
Propriedades idempotentes
p ^ p ≣ p
Propriedades idempotentes
EQUIVALÊNCIAS LÓGICAS
Equivalências Nome
~(~p) ≣p Propriedade da Dupla Negação
p v q ≣ q v p
Propriedades Comutativas
p ^ q ≣ q ^ p
Propriedades Comutativas
(p v q) v r ≣ p v (q v r)
Propriedades Associativas
(p ^ q) ^ r ≣ p ^ (q ^ r)
Propriedades Associativas
p v (q ^ r) ≣ (p v q) ^(p v r)
Propriedades Distributivas
p ^ (q v r) ≣ (p ^ q) v(p ^ r)
Propriedades Distributivas
EQUIVALÊNCIAS LÓGICAS
Equivalências Nome
~(p ^ q)≣ ~p v ~q
Leis de De Morgan
~(p v q)≣ ~p ^ ~q
Leis de De Morgan
p v (p ^ q) ≣ p
Propriedade de absorção
p ^ (p v q) ≣ p
Propriedade de absorção
p v ~p ≣ V
Propriedades de negação
p ^ ~p ≣ F
Propriedades de negação
REGRAS DE EQUIVALÊNCIA
Expressão Equivale a Nome Regra Abreviação
P v Q Q v P
Comutativa COM
P ^ Q Q ^ P
Comutativa COM
( P v Q) v R P v (Q v R)
Associativa ASS
( P ^ Q) ^ R P ^ (Q ^ R)
Associativa ASS
~ ( P v Q) ~P ^ ~Q
De Morgan DM
~ ( P ^ Q) ~P v ~Q
De Morgan DM
P →Q ~P v Q Condicional COND
P ~ (~P) Dupla Negação DN
REGRAS DE INFERÊNCIA
De Podemos Deduzir Nome Abreviação
P, P→Q Q Modus Pones MP
P→Q, ~Q ~P Modus Tollens MT
P, Q P ^ Q Conjunção CONJ
P ^ Q P, Q Simplificação SIMP
P P v Q Adição AD
EXERCÍCIO 1
1. A → B v C P
2. ~B P
3. ~ C P
4. ~B ^ ~C 2,3 Conj
5. ~ ( B v C ) 4 DM
6. ~A 1,5 MT
c.q.d.
A→(B v C) ^ ~B ^ ~C → ~A
EXERCÍCIO 2
1. ~A P
2. B P
3. B → ( A v C) P
4. A v C 2,3 MP
5. ~(~A) v C 4 DN
6. ~A → C 5 COND
7. C 1,6 MP
c.q.d.
~A ^ B ^ [ B → (A v C )] → C
REGRAS DE INFERÊNCIA 
ADICIONAIS
De Podemos 
deduzir
Nome Abrev
P→Q, Q→R P→R Silogismo Hipotético SH
P v Q, ~P Q Silogismo Disjuntivo SD
P→Q ~Q → P Contraposição CONT
~Q → P P→Q Contraposição CONT
P ^ P P Auto Referência AUTO
P P ^ P Auto Referência AUTO
(P ^ Q)→R P→(Q→R) ExportaçãoEXPR
P ^ (Q v R) (P ^ Q) v(P ^ R) Distributiva DIST
P v (Q ^ R) (P v Q) ^(P v R) Distributiva DIST