Embed Size (px)
Citation preview
LÓGICA PROPOSICIONAL
Prof. Cesar Tacla/UTFPR/Curitiba
Slides baseados no capítulo 1 de DA SILVA, F. S. C.; FINGER M. e de MELO A. C. V.. Lógica para Computação. Thomson Pioneira Editora, 2006.
Conceitos básicos
• PROPOSIÇÃO – Enunciado/sentença ao qual se pode atribuir um valor-verdade,
i.e. verdadeiro ou falso. – acreditar/desacreditar; concordar/discordar; afirmar/negar
– Exemplos:
• Chove em Curitiba agora. • João gosta de jogar futebol. • Tweety é um pássaro.
– Contraexemplos
• Feche a porta! Sentença imperativa, não podemos dizer se é F ou V • Que horas são? Sentença interrogativa, idem.
Conceitos básicos
• Proposição: restrições – Uma sentença se refere a uma só proposição
• SEM AMBIGUIDADES DA LINGUAGEM NATURAL • Ex. todo homem ama uma mulher (todos amam a mesma
mulher?) ou • o homem viu a mulher com o binóculo (que segura o binóculo ou
por meio de um binóculo?)
– O contexto deve estar definido para atribuirmos valor-verdade a uma proposição
– Não há proposições autorreferentes na lógica clássica proposicional • Ex: esta sentença é falsa // o que ocorre se ela for V?
Conceitos básicos
• Construção de proposições complexas
Chove em Curitiba E uso guarda-chuva
Piu-piu é um pássaro OU Piu-piu é um mamífero
Se Piu-piu é um pássaro ENTÃO Piu-piu tem asas
É falso que Piu-piu é um mamífero
E = conjunção
OU = disjunção
SE – ENTÃO* = implicação
É FALSO QUE = negação
*implicação não é necessariamente uma relação causal
LINGUAGEM PROPOSIONAL
SÍMBOLOS PROPOSICIONAIS E DE CONECTIVOS
Chove em Curitiba E uso guarda-chuva
p q
Tweety é um pássaro OU Tweety é um mamífero
r s
Se Tweety é um pássaro ENTÃO Tweety tem asas
r → u
É falso que Tweety é um mamífero
u
E = = conjunção
OU = = disjunção
SE-ENTÃO = → = implicação
É FALSO QUE = = negação
Linguagem proposicional
• LINGUAGEM
– Alfabeto: símbolos da linguagem
– Gramática: para construir fórmulas bem formadas
– Semântica: significado das fórmulas
Linguagem Proposicional
• Alfabeto é composto por:
– Um conjunto infinito e contável de símbolos proposicionais (ou átomos): P = {p, q, r, s , t, u, ...}
– Conectivo unário da negação:
– Conectivos binários:
– Pontuação: ( )
Linguagem proposicional
• Gramática: regras de formação de fbf – fbf = fórmulas bem-formadas – Llp =conjunto das fórmulas proposicionais
[fonte: (Silva, Finger e Melo, 2006)]
Linguagem proposicional
A
¬A
¬q
A
¬ ¬A
¬¬ q
¬A
(A B)
¬A p
¬q
(¬q p)
A
p
Exemplos de geração de FBF
Fórmula atômica
Linguagem proposicional
(A B)
(A B)
(A B)
p
q
¬A p
¬r
Exemplos de geração de FBF
(A p)
((A q) p)
(((¬A p) q) p)
(((¬r p) q) p)
Linguagem proposicional
(A B)
(A B)
(A B)
p
q
¬A p
¬r
(p (q (¬r p)))
Exemplos de geração de FBF
Linguagem proposicional
(A B)
(A B)
(A B)
p
¬A p
¬r
(p ( (¬r p)))
A gramática não permite gerar UMA FÓRMULA MAL-FORMADA
Linguagem proposicional
• Omissão de parênteses (1/2)
– Parênteses mais externos podem ser omitidos
– Uso repetido de IMPLICAÇÃO: parênteses aninham-se à direita
(p (q (¬r p))) ≡ p (q (¬r p))
¬r → p → q → p ≡ (¬r → (p → (q → s)))
Linguagem proposicional
• Omissão de parênteses (2/2)
– Uso repetido de E: parênteses aninham-se à esquerda
– Uso repetido de OU: parênteses aninham-se à esquerda
– Precedência dos operadores: NEG > E > OU > IMPLICAÇÃO
¬r p s → q p ≡ ((((¬r) p) s) → (q p))
¬r p q s ≡ ((¬r p) q) s)
¬r p q s ≡ ((¬r p) q) s)
Linguagem proposicional
• Prioridade dos operadores ou conectivos
NEG > E > OU > IMPLICAÇÃO
¬r p s → q p ≡ ((((¬r) p) s) → (q p))
Exemplo
Linguagem Proposicional
• SUBFÓRMULAS Exemplos
p = {p}
¬p = {¬p, p}
p q = {p, q, p q}
¬p ¬q → r = {p, q, r, ¬p, ¬q, ¬p ¬q, ¬p ¬q → r}
Subfórmulas
CASOS
• Básico: A=p subf(A) = {p} para toda fórmula atômica p A
• A = ¬B subf(A) = {¬B} ⊔ subf(B)
• A = B C subf(A) = {B C} ⊔ subf(B) ⊔ subf(C)
• A = B C subf(A) = {B C} ⊔ subf(B) ⊔ subf(C)
• A = B → C subf(A) = {B → C} ⊔ subf(B) ⊔ subf(C)
Subfórmulas
Exemplo de aplicação dos casos indutivos do slide anterior
A = (¬p ¬q) → r
Subf(A)
= {(¬p ¬q) → r} ⊔ subf((¬p ¬q) ) ⊔ subf(r)
= {(¬p ¬q) → r} ⊔ {(¬p ¬q)} ⊔ subf(¬p) ⊔ subf(¬q) ⊔ {r}
= {(¬p ¬q) → r} ⊔ {(¬p ¬q)} ⊔ {¬p} ⊔ subf(p) ⊔ {¬q} ⊔ subf(q) ⊔ {r}
= {(¬p ¬q) → r} ⊔ {(¬p ¬q)} ⊔ {¬p} ⊔ {p} ⊔ {¬q} ⊔ {q} ⊔ {r}
= {(¬p ¬q) → r, (¬p ¬q), ¬p, p, ¬q, q, r}
Tamanho ou Complexidade das Fórmulas
• Quantidade de símbolos proposicionais e conectivos
• Exemplos:
|p| = 1
|¬p| = 2
|p q| = 3
|(¬p ¬q) → r| = 7
Tamanho ou Complexidade das fórmulas
|p| = 1 para toda fórmula atômica p P
|¬A| = 1 + |A|
|A ∘ B| = 1 + |A| + |B| tal que ∘ {→, , }
EXPRESSÃO DE IDEIAS
• Para computar com símbolos lógicos, temos que transformar fatos e regras em proposições
• Exemplos: Pessoas podem ser crianças, adolescentes, adultas ou idosas p q r s Idosos são adultos: s → t Adultos e Empregados t u Crianças e adolescentes vão para escola (p q) → e
SEMÂNTICA
Na lógica proposicional clássica consiste em atribuir valores verdade às fórmulas: verdadeiro ou falso.
V: P {0, 1} ou {F, V} ou {F, T} // 0 = FALSO
Em seguida, estende-se a valoração para todas as fórmulas da LP:
V: Llp {0, 1} ou {T, F} ou {V, F}
SEMÂNTICA
V(¬A) = 1 sse V(A) = 0
V(AB) = 1 sse V(A) = 1 e V(B) = 1
V(AB) = 1 sse V(A) = 1 ou V(B) = 1
V(A→B) = 1 sse V(A) = 0 ou V(B) = 1
Primeiro valora-se as subfórmulas e, então, a fórmula
SEMÂNTICA
A B (A B)
0 0 0
0 1 0
1 0 0
1 1 1
A B (A B)
0 0 0
0 1 1
1 0 1
1 1 1
A B (A B)
0 0 1
0 1 1
1 0 0
1 1 1
A ¬A 0 1
1 0
SEMÂNTICA
• Valoração de uma fórmula complexa: inicia pela valoração das subfórmulas mais internas
Exemplo:
(¬p ¬q) → r
Valoração dos átomos:
V(p) = 1 V(q) = 0 V(r) = 1
V((¬p)) = 0
V((¬q)) = 1
V((¬p ¬q)) = 1
V((¬p ¬q) → r) = 1
SEMÂNTICA
Satisfazibilidade e Validade para uma fórmula A • Satisfazível se existe ao menos uma valoração V de seus átomos tal
que V(A) = 1;
• Insatisfazível se para toda valoração V de seus átomos V(A) = 0;
• Válida ou tautológica se toda valoração V de seus átomos é tal que V(A) = 1;
• Falsificável se existe pelo menos uma valoração V de seus átomos tal que V(A) = 0.
• Contingente se é satisfazível e falsificável
SEMÂNTICA
• Relações entre as definições satisfazibilidade e validade Válida satisfazível Insatisfazível falsificável A é válida ¬ A é insatisfazível A é insatisfazível ¬ A é válida A é satisfazível ¬ A é falsificável A é falsificável ¬ A é satisfazível
Há fórmulas que são tanto satisfazíveis como falsificáveis = contingentes Ex: p q p q p q
TABELAS-VERDADE
• Método exaustivo para verificar satisfazibilidade das fórmulas:
– Construa uma tabela com uma coluna para cada subfórmula de A, colocando os átomos nas colunas mais a esquerda e a fórmula A mais a direita (na última coluna)
– Para cada valoração possível para os átomos de A, inserir uma linha
– Fazer a valoração para cada átomo e calculá-la para cada subfórmula segundo as regras de valoração
Consequência Lógica
• Representa-se 𝐴 ⊨ 𝐵
• Lê-se:
a fórmula B é consequência lógica da fórmula A, se toda
valoração V que satisfaz A também satisfaz B
V(A) = 1 implica em V(B) =1
V(B) pode ser 1 e V(A)=0, ainda assim A acarreta B
Observe que
Consequência Lógica
Para verificarmos se 𝐴 ⊨ 𝐵, basta verificar se A B é válida.
• Exercício: com o método dedutivo da tabela-verdade verifique se p q r ⊨ p r
Consequência Lógica
• Considere um conjunto de fórmulas Γ (gama maiúsculo): ={ A1, A2 … An }
• Queremos saber se acarreta A
⊨ A
• Para isto, toda valoração V que satisfaz todas as fórmulas de deve satisfazer A.
Consequência Lógica
• Exemplo: verificar Modus Ponens
Modus (método) que afirma o Ponens (consequente) ou, alguns dizem, Método que afirma o consequente afirmando o antecedente = Modus ponendo ponens.
p q, p ⊨ q
Teorema da dedução
Γ, 𝐴 ⊨ 𝐵 𝑠𝑠𝑒 Γ ⊨ 𝐴 → 𝐵
Exemplo p q, p ⊨ q pelo teorema da dedução tem-se: p q ⊨ p q !!!
Equivalência lógica
𝐴 ≡ 𝐵 𝑠𝑠𝑒 A ⊨ 𝐵 ∧ 𝐵 ⊨ 𝐴
Tabela-verdade é um método que permite a verificação de equivalências: basta que as colunas das valorações de A e B sejam idênticas.
outra forma, é verificar se (A B ) (B A ) é válida
Equivalências notáveis Dupla Negação (DN) ¬¬p ≡ p
Idempotente (IP) p p ≡ p p p ≡ p
Comutativa (COM) p q ≡ q p p q ≡ q p
Associativas (ASS) p (q r ) ≡ ( p q ) r p (q r ) ≡ ( p q ) r
Leis De Morgan (DM) ¬(p q) ≡ ¬p ¬q ¬(p q) ≡ ¬p ¬q
Leis Distributivas (DIS) p (q r ) ≡ (p q) (p r) p (q r ) ≡ (p q) (p r)
Contrapositiva da implicação
ou da condicional (CP) p q ≡ ¬q ¬p
Reescrita da implicação ou
condicional (COND) p q ≡ ¬p q
Reescrita da Bicondicional (BI) p q ≡ (p q) (q p)
Identidade (ID) p 0 ≡ p p 0≡ 0
p 1 ≡ 1 p 1 ≡ p
Complementares (COMPLE) p ¬p ≡ 1 p ¬p ≡ 0
