aula 18 Setembro

Prévia do material em texto

30/9/2008
1
Doutorado em Difusão do Conhecimento 2008.1
O que é lógica simbólica?
� “É uma linguagem equipada com regras para 
deduzir a verdade de uma sentença a partir de uma 
outra.”
� Considere a sentença:
� Seja n o menor número natural que não pode ser definido 
com menos de 20 palavras.
� Quantas palavras a sentença possui?
� Lógica simbólica X linguagem natural
� Ganha em precisão, mas sacrifica a expressividade
Doutorado em Difusão do Conhecimento 2008.1
lógica simbólica
� Lógica proposicional
� Lógica de 1ª ordem
� Lógica de 2ª ordem
� Cada lógica possui a noção de fórmula atômica
� Cada sentença é construída a partir das fórmulas 
atômicas, seguindo regras precisas
Maior número de 
regras que nos 
permite construir 
fórmulas mais 
complexas.
30/9/2008
2
Doutorado em Difusão do Conhecimento 2008.1
lógica e Computação
� Relação simbiótica:
☯ Os computadores fornecem o ambiente concreto para a 
implementação da lógica.
☯ A Lógica fornece a linguagem e os métodos para o 
estudo teórico da ciência da computação.
☯ Considere o seguinte problema em Teoria da 
complexidade:
☯ Soma 10: Dado um conjunto finito de inteiros, existe 
algum subconjunto cuja soma dos elementos resulte 10?
Doutorado em Difusão do Conhecimento 2008.1
Problema Soma 10
Dado o conjunto {-26, -16, -12, -8, -4, -2, 7, 8, 27}
� Existe ou não existe um subconjunto de números cuja 
soma resulte 10?
� Quantas possibilidades temos? 29 = 512 subconjuntos
� Complexidade
� Classe de problemas P
� Classe de problemas NP
30/9/2008
3
Doutorado em Difusão do Conhecimento 2008.1
Problema Soma 10
� Problemas polinomiais e a classe P
� Um problema computacional é polinomial se existe um 
algoritmo polinomial para o problema. Problemas desse 
tipo são considerados "fáceis" do ponto de vista 
computacional. 
� Um problema é não-polinomial se não existe algoritmo 
polinomial que resolva o problema. Problemas desse tipo 
são considerados computacionalmente intratáveis. Para 
resolver um problema desse tipo é preciso, 
essencialmente, testar todos os candidatos a solução. 
Doutorado em Difusão do Conhecimento 2008.1
Problema Soma 10
� A classe NP de problemas
� Um problema de decisão está em NP se for 
possível verificar, em tempo polinomial, se 
uma suposta solução é, de fato, uma solução. 
ex. Considere o conjunto {-26, -4, -2, 7, 8, 27}
� não se sabe se o problema está em P ou não.
NP = P?
=> O Instituto Clay oferece um prêmio de US$1 Milhão
30/9/2008
4
Doutorado em Difusão do Conhecimento 2008.1
Problema SAT
� O problema SAT consiste em verificar se uma 
expressão booleana na FNC é satisfatível.
Exemplo:
(A v ~B v ~D v ~F) ^ (C v B v ~D) ^ (~A v F v D)
☺ Experimente atribuir o valor True às variáveis A, B, F e 
o valor False às variáveis C, D.
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� Origem –
� trabalhos de Boole (álgebra Booleana).
� Frege – Begriffsschrift (1879).
� Fórmulas atômicas são proposições
� A = “Aristóteles está morto”
� B = “Barcelona fica na França”
� C = “Gisele é alta”
� São os blocos básicos usados para construir sentenças
30/9/2008
5
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� Proposição – Sentenças declarativas.
� Cada sentença possui um valor verdade
� + exemplos:
� A = “Vasco da Gama descobriu o Brasil.” (falso)
� B = “Salvador é a capital da Bahia.” (verdadeiro)
� C = “David é um professor.” (verdadeiro)
� D = “52 – 42 = 10”. (falso)
� E = “5 < 3”. (falso) – igual a 3 > 5
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� E quando o valor verdade é questionável?
� C = “Gisele é alta”
� Em alguns casos, talvez fizesse sentido termos valores 
entre 0 e 1.
� Poderíamos atribuir 0.75 para a sentença C, se Gisele 
fosse mais alta que 75% das brasileiras
� Lógica Fuzzy faz isso, as lógicas clássicas não!
30/9/2008
6
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� Na verdade, o conteúdo das sentenças não é 
relevante para a lógica proposicional
� Por isso, as sentenças são denotadas com letras 
maiúsculas.
� A veracidade das fórmulas atômicas não importa.
� O que interessa é o relacionamento entre a verdade 
de uma sentença com relação a da outra.
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� A linguagem contém palavras para representar
� not (~)
� and (^)
� or (v)
� implies (→)
� If and only if (↔)
� Esses símbolos representam conceitos precisos e 
invariáveis. 
� Não dependem do contexto!
30/9/2008
7
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� A ^ B sempre tem o mesmo significado que B ^ A
� Isso nem sempre é verdade na linguagem natural
� Ela ficou gravemente doente e ela foi ao médico
� Ela foi ao médico e ela ficou gravemente doente
� As sentenças acima não possuem o mesmo significado!
� Esse descompasso acontece com v (or) ?
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional
� Como definir precisamente os símbolos da 
linguagem (~, ^, v, → , ↔) ? 
� ~ e ^ como primitivos
� Definimos os outros símbolos em função deles
� ~ e ^ não são definidos em termos de outros 
símbolos. 
� a semântica deles é descrita de forma não ambígua
30/9/2008
8
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (sintaxe)
� Qual a gramática da linguagem?
� (R0) qualquer fórmula atômica é uma fórmula
� (R1) se F é uma fórmula, então ~F é uma fórmula
� (R2) se F e G são fórmulas, então (F ^ G) é uma fórmula
� (C1) se F ou (F) é uma fórmula, então, vemos F e (F) como a 
mesma fórmula
� Definição 1 – A fórmula ~F é a negação de F e a fórmula (F ^ G) 
é a conjunção de F e G.
� Definição 2 – uma seqüência finita de símbolos é uma fórmula na 
LP se e somente se ela for construída a partir de fórmula 
atômicas pela repetida aplicação de R1 e de R2
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (sintaxe) 
� Exemplo 
� ~(~(A ^ B) ^ ~C) é uma fórmula
� ((A~^) B(C~ não é uma fórmula
� Os símbolos ~ e ^ são suficientes para descrever a 
sintaxe da LP
� As fórmulas que incluem v, → , ↔ são abreviações 
de fórmulas mais complicadas envolvendo apenas 
~ e ^
30/9/2008
9
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (sintaxe) 
� (C1) leva a algumas ambigüidades
� F = A ^ B, então ~F = ~A ^ B ?
� Definição 2 – sub-fórmula
� Qualquer fórmula é sub-fórmula dela mesma
� Qualquer sub-fórmula de F é também sub-fórmula de ~F
� Qualquer sub-fórmula de F ou G é também uma sub-
fórmula de (F ^ G)
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (sintaxe) 
� Exemplo –
Seja A e B fórmulas atômicas e F a fórmula ~(~A ^ ~B)
� A ^ ~B é um sub-string, e não uma sub-fórmula
� A, B, ~A, ~B, (~A ^ ~B) e ~(~A ^ ~B) são sub-fórmulas
� Existe uma ordem entre os operadores
� Se não existir parêntesis, ~ possui prioridade sobre ^
� Exemplos:
� ~(A ^ B)
� ~A ^ B
30/9/2008
10
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (semântica) 
� Tabelas Verdade
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (semântica) 
� Definição 3
� (A v B) é uma abreviação para ~(~A ^ ~B) 
� Tabela verdade para (A v B)
30/9/2008
11
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (semântica) 
� (A → B) é uma abreviação para (B v ~A)
� Tabela verdade para (A → B)
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (semântica) 
� O uso coloquial do “se então” é diferente!!!
� (A → B) é verdade sempre que A é falso
� Na lógica, falso pode implicar em qualquer coisa
� Observe o exemplo:
� “Se eucomi ovos no café da manhã, então o mundo acaba 
a meia noite”. (E → M)
� Suponha que eu não comi ovos no café da manhã, logo E 
é falso
� → representa um “se então” simplificado. 
� conexão causal e seqüência temporal (ignorado!)
30/9/2008
12
Doutorado em Difusão do Conhecimento 2008.1
Lógica Proposicional (semântica) 
� (A ↔ B) é abreviação para (A → B) ^ (B → A)
� Tabela verdade para (A ↔ B)
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
� Exercício:
� F = ((~A → B) ^ C) v ~(A ^ D)
� Sabendo-se que os valores de A, B, C, e D são 1, 0, 1, e 0, qual o 
valor de F? 
30/9/2008
13
Doutorado em Difusão do Conhecimento 2008.1
Sumário ...
� LP é uma linguagem
� Seu dicionário contém as palavras ~, ^, v, → , ↔
� ( e ) são utilizado apenas como pontuação
� ~ e ^ são considerados primitivos
� v, → , e ↔ são definidos em termos de ~ e ^ 
� O dicionário contém um infinito número de fórmulas 
atômicas
� A gramática é formada pelas regras R0, R1, R2, e pelas 
convenções C1 e C2.
� LP possui regras para dedução
� A semântica da LP é dada pelas tabelas verdade
Doutorado em Difusão do Conhecimento 2008.1
Validade, Satisfatibilidade, e Contradição
Seja S = {A1, ..., An} o conjunto das fórmulas atômicas
Seja F(S) o conjunto de todas as fórmulas que podem ser 
construídas a partir das fórmulas atômicas em S
� Definição 4
� A função A: S→ {0, 1} atribui valores às fórmulas em S
� também atribuímos valores a todas as fórmulas a F(S) 
� Exemplo 
� Seja A e B fórmulas atômicas, Seja A a função que atribui 
valores a A e B, tal que A(A) = 1 e A(B) = 0. Então, 
� A(A ^ B) = 0, 
� A(A v B) = 1 , 
� A(A ^ (C v ~C)) = 1
30/9/2008
14
Doutorado em Difusão do Conhecimento 2008.1
Validade, Satisfatibilidade, e Contradição
� Seja A a função que atribui valores a S, e seja F 
uma fórmula. 
� Se A(F) = 1, então F é válido sob as atribuições de A
� Dizemos que A modela F
� Escrevemos A ╞ F
� Um fórmula é válida se for verdadeira sob 
qualquer atribuição de valores (tautologia)
╞ F
� (C v ~C) é uma tautologia
Doutorado em Difusão do Conhecimento 2008.1
Validade, Satisfatibilidade, e Contradição
� Uma fórmula é satisfatível se houver uma linha 
da tabela para a qual o seu valor seja 1
� Uma fórmula é uma contradição se não houver 
uma linha da tabela para a qual o seu valor 
seja 1
� (C ^ ~C) é uma contradição
30/9/2008
15
Doutorado em Difusão do Conhecimento 2008.1
Problema da decisão
� Dada uma certa entrada, é feita uma 
pergunta e a resposta é sim ou não.
� Dada uma fórmula F como entrada, 
� ╞ F?
� F é satisfatível?
Doutorado em Difusão do Conhecimento 2008.1
Problema da decisão 
� Determine se 
(A ^ (A → B)) → B 
é válida, satisfatível, ou uma contradição. 
30/9/2008
16
Doutorado em Difusão do Conhecimento 2008.1
Problema da decisão 
� Determine se 
((A → B) → A) ^ ~A 
é válida, satisfatível, ou uma contradição. 
Doutorado em Difusão do Conhecimento 2008.1
Problema da decisão 
� Nem sempre a tabela verdade é um método 
eficiente
� Se F contém n fórmulas atômicas, teremos que 
computar 2n linhas 
� Se F tiver, por exemplo 23 fórmulas atômicas... 
obter a tabela verdade é inviável!
� Existem outros métodos para se determinar 
satisfatibilidade e validade?
30/9/2008
17
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
1. Mostre que ~ e v podem ser os símbolos primitivos na LP. 
Mostre também que os cada um dos outros símbolos (^, → , 
↔ ) pode ser definido em função de ~ e v.
2. Encontre a tabela verdade para as fórmulas:
� (~A → B) v ((A ^ ~C) ↔ B)
� (A → B) ^ (A → ~B)
� (A → (B v C)) V (C → ~A)
Doutorado em Difusão do Conhecimento 2008.1
Conseqüência e Equivalência
� G é uma conseqüência de F se para toda atribuição 
A, se A ╞ F então A ╞ G 
� F╞ G (G é uma conseqüência de F)
� A ╞ F significa A(F) = 1 (A modela F)
� G╞ F - toda atribuição que modela G também modela F
� ╞ F - toda atribuição modela F (tautologia)
� A noção de conseqüência está relacionada com 
implicação
� F╞ G se F → G for uma tautologia
30/9/2008
18
Doutorado em Difusão do Conhecimento 2008.1
Conseqüência e Equivalência
� F╞ G se F → G for uma tautologia
� Para que F → G não seja uma tautologia
� A ╞ ~(F → G)
� A ╞ ~(~F v G)
� A ╞ F ^ ~G
� A ╞ F e A ╞ ~G
Isso acontece se e somente se G não for conseqüência de F
� Como determinar se uma fórmula é conseqüência ou não de 
outra fórmula?
Doutorado em Difusão do Conhecimento 2008.1
Problema da Conseqüência
� Pela tabela verdade
� Se os valores verdade de F → G forem todos 1, G é 
conseqüência de F
� Se F for uma contradição, qualquer G pode ser conseqüência 
de F
30/9/2008
19
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Verifique a seguinte conseqüência:
� (F ^ G)╞ F
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Verifique a seguinte conseqüência:
� F╞ (F v G)
30/9/2008
20
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Verifique a seguinte conseqüência:
� (F ^ ~F) ╞ G
Doutorado em Difusão do Conhecimento 2008.1
Equivalência
� Se F╞ G e G╞ F
� F e G são equivalentes ► F ≡ G
� Duas fórmulas F e G são equivalentes se 
� F ↔ G é uma tautologia (┬)
� Exemplos de equivalência:
� (A ^ B) ≡ (B ^ A) e (A v B) ≡ (B v A) 
� (A ^ ┬) ≡ A e (A v ┬) ≡ ┬
� (A ^ ┴) ≡ ┴ e (A v ┴) ≡ A
� (A ^ (B v C)) ≡ ((A ^ B) v (A ^ C)) (^-distrib.)
� (A v (B ^ C)) ≡ ((A v B) ^ (A v C)) (v-distrib.)
� ~(A ^ B) ≡ (~A v ~B) e ~( A v B) ≡ (~A ^ ~B) (Leis de Morgan)
30/9/2008
21
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Verifique a seguinte conseqüência:
� ((C ^ D) v A) ^ ((C ^ D) v B) ^ (E v ~E) ≡ (A ^ B) v (C ^ D)
� ((C ^ D) v A) ^ ((C ^ D) v B) ≡ (A ^ B) v (C ^ D)
� (C ^ D) v (A ^ B) ≡ (A ^ B) v (C ^ D)
� (A ^ B) v (C ^ D) ≡ (A ^ B) v (C ^ D)
� Poderíamos ter verificado essa equivalência utilizando uma 
tabela verdade de 32 linhas
Doutorado em Difusão do Conhecimento 2008.1
Provas Formais
� Seja F = {F1, F2, F3, ...}
� A ╞ F
� se A ╞ Fi para cada fórmula Fi em F
� Uma fórmula G é conseqüência de F (F ╞ G)
� Se A ╞ F implica em A ╞ G para toda atribuição A
ΛF é a conjunção de todas as fórmulas em F
� Obter a tabela verdade de ΛF→ G pode ser inviável
� Uma outra abordagem é derivar G a partir de F
30/9/2008
22
Doutorado em Difusão do Conhecimento 2008.1
Provas Formais
� Exemplo:
� Seja F o conjunto de fórmulas
{ A, (A →B), (B →C), (C →D), (D →E), (E →F), (F →G)}
� Suponha que cada fórmula em F seja verdade
� Então, se A e (A →B) são verdade
Podemos concluir que B tem que ser verdade!!!
� Quais os valores de C, D, E, F, G?
� Cada uma dessas fórmulas é uma conseqüência de F
ΛF = A ^ (A →B) ^ (B →C) ^ (C →D) ^ (D →E) ^ (E →F) ^ (F →G)
� A tabela verdade para ΛF →G possui 128 linhas
Doutorado em Difusão do Conhecimento 2008.1
Provas Formais
� Uma lógica possui regras para deduzir o valor verdade de uma 
sentença a partir de outra
� Essas regras fornecem o sistema formal de prova
� Consiste de um conjunto básico de regras de derivação
� Permite deduzir fórmulas a partir de conjuntos de fórmulas
� Vários passos de derivação
� Cada passo é uma aplicação de uma regra básica
� A lista desses passos forma a prova formal de G a partir de F
30/9/2008
23
Doutorado em Difusão do Conhecimento 2008.1
Provas Formais
� A ambição de um sistema de prova formal é tornar o 
processo raciocínio infalível
� Se duas pessoas discordarem sobre F ╞ G
� Basta realizar a “computação” e verificar!
� Escrevemos F ├ G
� Como abreviação de “G pode ser derivado a partir de F “
� Exemplo de regra de derivação
Se F ├ A e F ├ B entãoF ├ (A ^ B) (^-Introdução)
Doutorado em Difusão do Conhecimento 2008.1
Regras Básicas para Derivação
30/9/2008
24
Doutorado em Difusão do Conhecimento 2008.1
Mais Regras para Derivação
Doutorado em Difusão do Conhecimento 2008.1
Exemplo H = {(~A v B), (~A v C), (A v ~D)}
H ├ D → (A ^ B ^C) ?
30/9/2008
25
Doutorado em Difusão do Conhecimento 2008.1
Otimizando a prova (regra Modus Ponens)
� Na prova anterior, o símbolo → foi introduzido e 
eliminado várias vezes.
� Se a regra 
� Premissa: F ├ (~F v G), F ├ F
� Conclusão: F ├ G
Doutorado em Difusão do Conhecimento 2008.1
Regra da Tautologia
� Estabelece que (~G v G) pode ser derivada de a partir 
de qualquer conjunto de fórmulas.
30/9/2008
26
Doutorado em Difusão do Conhecimento 2008.1
Regra da Contradição
� Estabelece que qualquer fórmula G pode ser derivada 
de uma contradição (F ^ ~F).
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Prove que se P → Q, então ~Q → ~F (contra-positiva)
� Premissa: F U {F} ├ G
� Conclusão: F U {~G} ├ ~F
30/9/2008
27
Doutorado em Difusão do Conhecimento 2008.1
Pegue seu lápis!
Prove que se P → Q, então ~Q → ~F (contra-positiva)
� Premissa: F U {F} ├ G
� Conclusão: F U {~G} ├ ~F