Semântica na Lógica Proposicional

Prévia do material em texto

SEMÂNTICA
(na Lógica Proposicional)
Roteiro
 Sintática x Semântica;
 Interpretação Semântica;
 Propriedades Básicas;
 Relações entre Propriedades.
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 concatenaçõ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]
Qual a cor de cada palavra 
abaixo?
● Diga rapidamente:
Qual a cor de cada palavra 
abaixo?
● Diga rapidamente:
VERDE
AMARELO
AZUL
VERMELHO
LARANJA
PRETO
Qual a cor de cada palavra 
abaixo?
● Seria mais fácil?
绿
黄
蓝色
红
橙
黑
Não para um Chinês... (tradução do Google Translator)
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
 Interpretação é uma função de valoração
 I : LLP   {T, F}→
 I[P] = T ou I[P] = F (idem para I[Q])
 Se tivermos que I[P] = T e 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 seu contradomínio 2 
elementos
Wff da lógica proposicional
T
F
Interpretação
 Uma interpretação I, em Lógica Proposicional, é uma 
função binária tal que:
 O domínio de I é o conjunto de fórmulas proposicionais bem 
formadas (LLP)
 O contradomínio é o conjunto {T, F}
 O valor da interpretação I, tendo como argumentos os 
símbolos da 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=(HG), então
 I[E]=I[HG]=T se I[H]=F e/ou I[G]=T e
 I[E]=I[HG]=F se I[H]=T 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]=I[G]
 I[E]=I[HG]=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=(EP) 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]=?
 True
 
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 (ou ainda satisfatível) 
se existe uma interpretação I tal que I[H]=T
 H é contraditória ou insatisfazível  (ou ainda 
insatisfatí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,HG para toda 
interpretação I, se I[H]=T então I[G]=T
 Dadas H e G,HG para toda interpretação I ser 
satisfatível, I[H]=I[G]
Exemplo de Tautologia
 A fórmula H=PvP é uma tautologia, pois toda I[H]=T
 I[H]=T  ⇔ I[PvP]=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 Satisfazibilidade
 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=P1vP2vQQ
 Tautologia
 H2=P1^P2^QQ
 Satisfatível
 H3=(PvP)(Q^Q)
 Contraditória
Implicação
 Se E=((P^Q)VQ) e
 H=(P^Q) e
 G=(PQ)
 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]=T
I[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
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
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27