Sintaxe e semântica da Lógica Proposicional

Prévia do material em texto

Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta 
Sintaxe e Semântica da Lógica Proposicional
Prof Edjard Mota
Parte desses slides foram adaptados de aulas do 
professor Eduardo Nakamura
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Linguagem proposicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Uma linguagem proposicional L é composta por
◆ Um Alfabeto (letras maiúsculas, o conjunto {V,F} e os 
conectivos lógicos) 
◆ Símbolos para variáveis e constantes e proposições 
compostas ou fórmulas
● A Gramática de uma linguagem proposicional 
define a sintaxe das expressões
◆ Permite a formação e o reconhecimento de fórmulas bem 
formadas (fbf)
◆ Exemplo: P¬vQ (fórmula incorreta, mal formada)
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Gramática de uma linguagem proposicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. Letras proposicionais do vocabulário são fórmulas em 
L
2. Se α e β são fórmulas em L, então também são 
fórmulas as seguintes expressões:
◆¬α
◆α ∧ β 
◆α ∨ β 
◆α → β
◆α ↔ β
● Somente o que pode ser gerado através dos itens 1 e 2 
em um número finito de passos é uma fórmula em L
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
◆ O PSDB ganhou a eleição ou o PT ganhou a eleição, 
e o Brasil começou a mudar?
◆ O PSDB ganhou a eleição, ou o PT ganhou a eleição 
e o Brasil começou a mudar?
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F
V V V
V F F
V F V
F V F
F V V
F F F
F F V
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F V
V V V V
V F F V
V F V V
F V F V
F V V V
F F F F
F F V F
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F V F
V V V V V
V F F V F
V F V V V
F V F V F
F V V V V
F F F F F
F F V F F
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F V F F
V V V V V V
V F F V F F
V F V V F V
F V F V F F
F V V V V V
F F F F F F
F F V F F F
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F V F F V
V V V V V V V
V F F V F F V
V F V V F V V
F V F V F F F
F V V V V V V
F F F F F F F
F F V F F F F
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R) ?
P Q R P	∨	Q Q	∧	R (P	∨	Q)	∧	R P	∨	(Q	∧	R)
V V F V F F V
V V V V V V V
V F F V F F V
V F V V F V V
F V F V F F F
F V V V V V V
F F F F F F F
F F V F F F F
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Solução: ordem de precedência
1. Parênteses mais internos
2. Negação: ¬
3. Conjunção: ∧
4. Disjunção: ∨
5. Condicional: →
6. Bicondicional: ↔
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Ambiguidade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Solução: ordem de precedência
1. Parênteses mais internos
2. Negação: ¬
3. Conjunção: ∧
4. Disjunção: ∨
5. Condicional: →
6. Bicondicional: ↔
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Lógica proposicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
●Vimos o que é um argumento, mas 
●O que é um argumento válido? !
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Lógica proposicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
●Vimos o que é um argumento, mas 
●O que é um argumento válido? !
Definição 1. Uma interpretação que satisfaz uma 
sentença S é denominada de um Modelo para S.
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Construir a tabela verdade para B: ((p → q) ∧ p) → q
p q p → q (p → q)∧ p ((p → q)∧ p) → q 
V V F V V
V F V F V
F V F F V
F F V F V
Fórmula B é verdade em todas interpretações! !
Lógica Proposicional: Semântica
Chamemos formulas assim de Tautologia!
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Construir a tabela verdade para C: ((p → q) ∧ (p ∧ ¬q)
p q ¬q p → q (p ∧ ¬q) ((p → q)∧ (p ∧ ¬q) 
V T F V F F
V F V F V F
F V F V F F
F F V V F F
Fórmula C é falsa em todas interpretações! !
Lógica Proposicional: Semântica
Chamemos formulas assim de Contradição 
ou Inconsistência!
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Construir a tabela verdade para A : (P → Q) ∨ ¬ S
p q s p → q ¬s (p → q) ∨¬s
F F F 
F F V 
F V F 
F V V 
V F F F V V
V F V F F F
V V F
V V V
Fórmula A pode ser verdadeira ou falsa … !
Lógica Proposicional: Semântica
Chamemos formulas assim de Contingência!
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Definition 2. Um argumento na forma “A1, A2, …, An 
Logo B” é válido se, para qualquer interpretação em que 
A1, A2, …, An sejam satisfeitos, B também é satisfeito. E 
escreve-se 
• Dizemos que A1, A2, …, An implica em B
Quando um argumento é válido?
A1, A2, . . . , An |= B
Lógica Proposicional: Semântica
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
 A ⊨ A 
 A ∧ B ⊨ A 
 A, A → B ⊨ B 
 A → B, ¬ B ⊨ ¬ A
Exemplos de argumentos válidos
 A ⊨ A ∧ B 
Exemplo de um argumentos inválido (⊭)
Isso se verifica, como visto, com tabela verdade
Lógica Proposicional: Semântica
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Definition 3. Validade e Consistência de uma fórmula. 
• Uma sentença A é válida ou uma tautologia (⊨ A) se, e 
somente se A é verdade em todas possíveis 
interpretações. 
 e.g. A ∨ ¬A 
• Uma sentença A é inconsistente (or insatisfatível) se, e 
somente se A é falsa em todas possíveis interpretações. 
 e.g. A ∧ ¬A 
• Uma sentença é consistente (satisfatível) se, e somente 
se ela não é inconsistente.
Lógica Proposicional: Semântica
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
1. Uma fórmula é válida sss sua negação é inconsistente.
2. Uma fórmula é inconsistente sss sua negação é válida.
3. Uma fórmula é inválida sss existe pelo menos uma uma 
interpretação sob a qual ela é falsa.
4. Uma fórmula é consistente (satisfatível) sss existe pelo 
menos uma interpretaçãosob a qual a fórmula é verdade.
5. Se uma fórmula é válida, então ela é consistente, mas 
não vice versa. 
6. Se uma fórmula é inconsistente, então ela é inválida, 
mas não vice versa.
Conceitos importantes … "
Lógica Proposicional: Semântica
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercício em Sala
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Verifique se as proposições abaixo são 
tautologia, contradição ou contingência
1. (P ∧ Q) → (P ∨ Q)
2. (P ∧ Q) ∧ ¬(P ∨ Q)
3. P ∧ Q ↔ ¬Q ∨ ¬P
4. [ (P → Q) → (P ∨ R)] → (Q ∨ R)
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Equivalência lógica
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Duas proposições α e β são logicamente 
equivalentes (α ⇔ β), se ambas possuem 
tabelas-verdade idênticas
● Exemplo
◆ O São Raimundo é o melhor time do Amazonas e vence 
sempre 
◆ O São Raimundo vence sempre e é o melhor time do 
Amazonas
◆ (P ∧ Q) ⇔ (Q ∧ P)
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Equivalência lógica
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Duas proposições α e β são logicamente 
equivalentes (α ⇔ β), se ambas possuem 
tabelas-verdade idênticas
● Exemplo
◆ Jurandir é Garantido ou é Caprichoso
◆ Jurandir é Caprichoso ou é Garantido
◆ (P ∨ Q) ⇔ (Q ∨ P)
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Equivalência lógica
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Duas proposições α e β são logicamente 
equivalentes (α ⇔ β), se ambas possuem 
tabelas-verdade idênticas
● Exemplo
◆ Se Nancy está dormindo, então Freddy Krueger aparece
◆ Se Freddy Krueger não aparece, então Nancy não está 
dormindo
◆ (P → Q) ⇔ (¬Q → ¬P)
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Teorema
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
a ⇔ b se, e somente se, a ↔ b é tautologia.
● Exemplos
◆ (P → Q) ↔ (¬P ∨ Q) é tautologia
◆ Logo, (P → Q) ⇔ (¬P ∨ Q)
◆ [ P → (Q → R) ] ↔ [(P ∧ Q) → R ] é tautologia
◆ Logo, [ P → (Q → R) ] ↔ [(P ∧ Q) → R ]
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercício
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Verifique se as proposições abaixo são 
equivalências lógicas
1. ¬(P ∧ Q) → (P ∧ Q) e (¬P ∨ ¬Q)
2. P ∨ (Q ∧ R) e [ (P ∨ Q) ∧ R) ] 
3. ¬(¬P ∨ Q) e ¬P → ¬Q
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Regras de equivalência
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Duas proposições α e β são logicamente 
equivalentes (α ⇔ β), se ambas possuem 
tabelas-verdade idênticas
◆ Definem que determinados pares de FBFs 
são equivalentes
◆ Portanto, se α ⇔ β, então α pode ser 
substituída por β em qualquer FBFs sem 
mudança em seu valor lógico
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Fundamentos de Teoria da Computação
Regras de equivalência
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fórmula Lei
P∨P	≡	P	
P∧P	≡	P Idempotência
(P∨Q)∨R	≡	P∨(Q∨R)	
(P∧Q)∧R	≡	P∧(Q∧R)
Associativa
P∨Q	≡	Q∨P	
P∧Q	≡	Q∧P Comutativa
(P∧Q)∨R	≡	(P∨R)∧(Q∨R)	
(P∨Q)∧R	≡	(P∧R)∨(Q∧R)
Distributiva
P∨F	≡	P	
P∨V	≡	V
P∧V	≡	P	
P∧F	≡	F Identidade
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Fundamentos de Teoria da Computação
Regras de equivalência
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fórmula Lei
P∨¬P	≡	V	
¬V	≡	F
P∧¬P	≡	F	
¬F	≡	V Complemento
¬¬P	≡	P Involução
¬(P∧Q)	≡	¬P∨¬Q	
¬(P∨Q)	≡	¬P∧¬Q DeMorgan
P→Q	≡	¬P∨Q Condicional
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Fundamentos de Teoria da Computação
Regras de equivalência (resumo)
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fórmula Lei
P∨P	≡	P	
P∧P	≡	P
Idempotência
(P∨Q)∨R	≡	P∨(Q∨R)	
(P∧Q)∧R	≡	P∧(Q∧R) Associativa
P∨Q	≡	Q∨P	
P∧Q	≡	Q∧P Comutativa
(P∧Q)∨R	≡	(P∨R)∧(Q∨R)	
(P∨Q)∧R	≡	(P∧R)∨(Q∧R) Distributiva
P∨F	≡	P	
P∨V	≡	V
P∧V	≡	P	
P∧F	≡	F Identidade
P∨¬P	≡	V	
¬V	≡	F
P∧¬P	≡	F	
¬F	≡	V Complemento
¬¬P	≡	P Involução
¬(P∧Q)	≡	¬P∨¬Q	
¬(P∨Q)	≡	¬P∧¬Q DeMorgan
P→Q	≡	¬P∨Q Condicional
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
1
O	carro	está		
nesta	caixa
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
1
2
O	carro	não		
está	nesta	caixa
O	carro	está		
nesta	caixa
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
1
2
3
O	carro	não		
está	nesta	caixa
O	carro	está		
nesta	caixa
O	carro	não		
está	na	caixa	1
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
1
2
3
Qual é a proposição 
verdadeira?
O	carro	não		
está	nesta	caixa
O	carro	está		
nesta	caixa
O	carro	não		
está	na	caixa	1
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
1
2
3
Qual é a proposição 
verdadeira?
Onde está o carro?
O	carro	não		
está	nesta	caixa
O	carro	está		
nesta	caixa
O	carro	não		
está	na	caixa	1
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
O	carro	não		
está	nesta	caixa
Onde está o carro?
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Fatos verdadeiros
1.Existe um carro em uma dessas caixas
2.Cada caixa possui uma proposição
3.Apenas uma proposição é verdadeira
O	carro	está		
nesta	caixa
O	carro	não		
está	na	caixa	1
1
3
Qual	é	a	proposição	
verdadeira?
Onde	está	o	carro?
Aula 02 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercício
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Demonstre a validade dos seguintes 
argumentos
1. (P → ¬Q)∧Q → ¬P
2. (P → ¬Q)∧(R → Q) ∧ R → ¬P
3. P∧(P → Q)∧[P → (Q → R)] → R
4. (¬P → ¬Q) ∧ Q ∧ (P → Q) → Q
5. (¬P → ¬Q) ∧ (P → R) ∧ Q → R
6. [P ∨(Q ∧ R)] ∧ (¬R ∨ S) ∧ (S → ¬T) → (T → P)