Upload
internet
View
168
Download
8
Embed Size (px)
Citation preview
SEMÂNTICA
Roteiro
Revisão; Sintática x Semântica; Interpretação Semântica; Propriedades Básicas; Relações entre Propriedades.
Revisão
O que é lógica? Estudo do raciocínio
Começou com Aristóteles Argumeto
Proposições e premissas Consequência Lógica
Revisão
Revisão
Objetivo: descobrir se o argumento é válido
Argumento dedutivo Conclusão a partir das premissas
Indutivo Probabilidade
Revisão
Alfabeto – Lógica Proposicional Símbolos de pontuação: ( ) , Símbolos de verdade: true, false Símbolos proposicionais: P, Q, R, S,
P1, Q1, P2, Q2... Conectivos proposicionais: ,v,^, ,
Semântica Existe uma diferença entre os objetos e seu
significado Existe um mundo sintático e um mundo
semântico Sintático – símbolos do alfabeto e fórmulas
(consideradas apenas como concatenções de símbolos)
Semântico – significado dos símbolos e fórmulas Em Lógica, semântica é a associação entre
um objeto sintático e seu significado, de forma a, num nível de representação, garantir inferências
[Gaiarsa]
Semântica
P (símbolo sintático) representa“Está chovendo”
Q representa“A rua está molhada”
Quando a fórmula (P^Q ) é Verdadeira?
Interpretação Depende das condições climáticas e se
a rua é coberta, ou seja, depende da interpretação de P e Q
I[P]=T ou I[P]=F (e também I[Q])
A fórmula (P^Q ) é Verdadeira, quandoI[P]=T e I[Q]= T
Se I[P]=T ou I[Q]=F então, como ^ é interpretado como a conjunção da interpretação dos fatos P e Q,
I[P^Q]=F
Interpretação Função binária – só possui em sua imagem 2
elementos Uma Interpretação I, em Lógica Proposicional,
é uma função binária t;l que: O domínio de I é o conjunto de fórmulas
proposicionais A imagem é o conjunto {T,F} O valor da interpretação I, tendo como
argumentos os símbolos de verdade true e false, é dado por I[true]=T e I[false]=F
Dado um símbolo proposicional P, I[P] pertence a {T,F}
Interpretação de fórmulas Dado uma fórmula E e uma
interpretação I, então o significado de E (I[E]) é dado pelas seguintes regras: Se E=P, onde P é um símbolo
proposicional, I[E]=I[P] Se H é uma fórmula e E=H, então
I[E]=I[H]=T se I[H]=F e I[E]=I[H]=F se I[H]=T
Interpretação de fórmulas (cont.)
Se H e G são fórmulas, e E=(HvG), então I[E]=I[HvG]=T se I[H]=T e/ou I[G]=T e I[E]=I[HvG]=F se I[H]=F e I[G]=F
Se H e G são fórmulas, e E=(H^G), então I[E]=I[H^G]=T se I[H]=T e I[G]=T e I[E]=I[H^G]=F se I[H]=F e/ou I[G]=F
Se H e G são fórmulas, e E=(HG), então I[E]=I[HG]=T se I[H]=F e/ou I[G]=T e I[E]=I[HG]=F se I[H]=T e I[G]=F
Se H e G são fórmulas, e E=(HG), então I[E]=I[HG]=T se I[H]=I[G] I[E]=I[HG]=F se I[H]= I[G]
Interpretação de uma fórmula
Se temos a fórmula H=((P)v(Q))R e a interpretação I[P]=T,I[Q]=F,I[R]=T
I[H] = True
Interpretação de uma fórmula (cont.) Se E = ((P)^Q)(RvP1) e
H=(EP) e as interpretações I e J I[P]=T,I[Q]=F,I[R]=T,I[P1]=F I[H]=?
True J[P]=F,J[Q]=T,J[R]=F J[H]=?
False
Propriedades semânticas básicas Uma fórmula H é uma tautologia (ou é
válida) se e somente se para toda interpretação I, I[H]=T
H é factível ou satisfazível se existe uma interpretação I tal que I[H]=T
H é contraditória ou insatisfazível se e somente se para toda interpretação I, I[H]=F
H é Falsificável se existe uma interpretação I tal que I[H]=F
Propriedades semânticas básicas (cont.)
Dados H e uma interpretação I, I satisfaz H se e somente se I[H]=T
Dadas 2 fórmulas H e G,HG para toda interpretação I, se I[H]=T então I[G]=T
Dadas H e G,HG para toda interpretação I ser satisfazível, I[H]=I[G]
Exemplo de Tautologia A fórmula H=PvP é uma tautologia,
pois toda I[H]=T I[H]=T I[PvP]=T
I[P]=T e/ou I[P]=T I[P]=T e/ou I[P]=F
aqui quer dizer “o mesmo que, equivale a”)
Exemplo de Satisfatibilidade
A fórmula H=(PvQ) é satisfazível, pois há interpretações que a interpretam como verdadeira.
H é tautologia? Por quê?
Exemplo de Contradição A fórmula H=(P^P) é contraditória Suponham (por absurdo) que exista
I[H]=T
I[H]=T I[P^P]=T I[P]=T e I[P]=T
I[P]=T e I[P]=F
Exercícios Quais das fórmulas abaixo são
tautologias, satisfazíveis ou contraditórias?
H1=P1^P2^QQ Tautologia
H2=P1^P2^QQ Satisfatível
H3=(PvP)(Q^Q) Contraditória
Implicação Se E=((P^Q)VQ) e H=(P^Q) e G=(PQ)
E G? E H? H G? H E? G H? G E?
Exercício
Prove que se temos as fórmulas proposicionais H=(P^Q) e G=P, então H G
Se H=F, G=? Tabela Verdade Se I[H] = T
Equivalência
Exemplo (Lei de Morgan)H=(P^Q) e G=(PvQ)
Temos que demonstrar que, para toda interpretação I, I[H]=I[G]
Casos I[H]=T e I[H]=F
(P^Q) (PvQ) ? Caso I[H]=TI[H]=T I[P^Q]=T I[P]=T e I[Q]=T I[P]=F e I[Q]=F I[PvQ]=F I[(PvQ)]=T I[G]=T I[H]=T I[H]=I[G]
Caso I[H]=F Exercício ou Olhar tabelas
verdade das 2 fórmulas
Equivalência
Exemplos: P P (eliminação da dupla
negação) P Q P V Q (definição de em
termos de e V) (P V Q) P ^ Q (Lei de Morgan 1) (P ^ Q) P V Q (Lei de Morgan 2) P ^ (Q V R) (P ^ Q) V(P ^ R)
Relações entre as Propriedades Semânticas
Validade e factibilidade H é válida H é contraditória H é válida H é satisfazível (quer dizer “se … então…”) H não é satisfazível H é
contraditória
Relações entre as Propriedades Semânticas (cont.)
Dadas 2 fórmulas H e G, H implica G (H G) é tautologia H equivale a G (H G) é tautologia
Provar que (H G) e (G H) Transitividade da equivalência
E H e H G E G
Relações entre as Propriedades Semânticas (cont.)
Satisfabilidade Seja {H1,H2,...Hn} um conjunto de
fórmulas {H1,H2,...Hn} é satisfatível
{H1^H2^...^Hn} é satisfatível
Equivalências
aqui quer dizer “o mesmo que, equivale a” e quer dizer “se … então …”
Cuidado: Há uma diferença entre eles: H equivale a G H é tautologia G é tautologia}? (1) H equivale a G H é tautologia G é tautologia}? (2)
Equivalência e Validade H equivale a G H é tautologia G é tautologia} (1)é dividida em 2 implicações:
H equivale a G H é tautologia G é tautologia} (2)e H é tautologia G é tautologia} H equivale a G (3)
Contra-exemplo de Equivalência e Validade
H é tautologia G é tautologia} H equivale a G (3)
H=P e G=Q, que não são equivalentes “H equivale a G” é falsa
No entanto, o antecedente é verdadeiro H e G não são tautologias
(Falso Falso) Falso Verdadeiro Falso, o que é falso
Proposições
Equivalência e Validade Proposição 1: H equivale a G H é
tautologia G é tautologia} Implicação e Validade
Proposição 2: H implica a G H é tautologia G é tautologia }
Proposição 3: {{H implica G} e {H é tautologia}} {G é tautologia}
Proposição 1 –Equivalência e Validade H equivale a G
H é tautologia G é tautologia} (2)
Prova do tipo prop3 prop2 e
prop2 prop1
Passos: prop2,
prop2 prop1 [1] prop3,
prop3 prop2 [2] Portanto,
prop3, [3] prop3 prop2, prop2 prop1
Proposição 2 – Implicação e Validade H implica a G H é tautologia G é tautologia}(4) Pode ser reescrito como:
G implica a H G é tautologia H é tautologia} (5) Portanto,
H equivale a G H é tautologia G é tautologia} (2) E prop2 prop1
Lema (implicação) (A (B C)) equivale a ((A^B) C)
Olhar tabelas verdade H equivale a G H é tautologia G é tautologia}(4)
é exatamente deste tipo! Portanto, (4) equivale a
{{H implica G} e {H é tautologia}} {G é tautologia}
prop3 prop2
Proposição 3 – Implicação e Validade Dadas 2 fórmulas H e G, então{{H implica G} e {H é tautologia}} {G é
tautologia} Supondo {H implica G} e {H é tautologia} Para {G é tautologia} ser verdade, então{G é tautologia} toda I[G]=T
Proposição 3 – Implicação e Validade (cont.)
{G é tautologia} toda I[G]=T Mas se {H é tautologia}, toda
I[H]=T Como {H implica G}, então toda
I[G]=T {G é tautologia}