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?



Começou com Aristóteles
Argumeto


Estudo do raciocínio
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, quando
I[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



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[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
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]=?

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,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 satisfazível,
I[H]=I[G]
Exemplo de Tautologia

A fórmula H=PvP é uma tautologia, pois
toda I[H]=T
I[H]=T DI[PvP]=T
D I[P]=T e/ou I[P]=T
D I[P]=T e/ou I[P]=F
(D 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 D I[P^P]=T
D I[P]=T e I[P]=T
D 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^QQ


H2=P1^P2^QQ


Tautologia
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
D I[P^Q]=T
D I[P]=T e I[Q]=T
D I[P]=F e I[Q]=F
D I[PvQ]=F
D I[(PvQ)]=T
D I[G]=T
D I[H]=T
D 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 D H é contraditória
H é válida a H é satisfazível
(a quer dizer “se … então…”)
 H não é satisfazível D H é contraditória
Relações entre as Propriedades
Semânticas (cont.)

Dadas 2 fórmulas H e G,

H implica G D (H  G) é tautologia

H equivale a G D (H  G) é tautologia


Provar que (H  G) e (G  H)
Transitividade da equivalência
 E  H e H  G a 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 D
{H1^H2^...^Hn} é satisfatível
Equivalências


D aqui quer dizer “o mesmo que, equivale a”
e a quer dizer “se … então …”
Cuidado: Há uma diferença entre eles:
 H equivale a G D
{H é tautologia D G é tautologia}? (1)
 H equivale a G a
{H é tautologia D G é tautologia}? (2)
Equivalência e Validade
H equivale a G D
{H é tautologia D G é tautologia} (1)
é dividida em 2 implicações:
 H equivale a G a
{H é tautologia D G é tautologia} (2)
e
 {H é tautologia D G é tautologia} a
H equivale a G (3)

Contra-exemplo de
Equivalência e Validade

{H é tautologia D G é tautologia} a
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 D Falso) a Falso
Verdadeiro a Falso, o que é falso
Proposições

Equivalência e Validade


Proposição 1: H equivale a G a{H é
tautologia D G é tautologia}
Implicação e Validade


Proposição 2: H implica a G a{H é
tautologia aG é tautologia }
Proposição 3: {{H implica G} e {H é
tautologia}} a{G é tautologia}
Proposição 1 –
Equivalência e Validade

H equivale a G a  Passos:
{H é tautologia D G
 prop2,
é tautologia} (2)
prop2 aprop1 [1]
 prop3,
prop3 aprop2 [2]
 Prova do tipo
prop3 aprop2 e
 Portanto,
prop2 aprop1
prop3,
[3]
prop3 aprop2,
prop2 aprop1
Proposição 2 –
Implicação e Validade




H implica a G a
{H é tautologia aG é tautologia}(4)
Pode ser reescrito como:
G implica a H a
{G é tautologia aH é tautologia} (5)
Portanto,
H equivale a G a
{H é tautologia D G é tautologia} (2)
E prop2 aprop1
Lema (implicação)

(A (B C)) equivale a ((A^B)  C)




Olhar tabelas verdade
H equivale a G a
{H é tautologia aG é tautologia}(4)
é
exatamente deste tipo!
Portanto, (4) equivale a
{{H implica G} e {H é tautologia}} a {G é
tautologia}
prop3 aprop2
Proposição 3 –
Implicação e Validade
Dadas 2 fórmulas H e G, então
{{H implica G} e {H é tautologia}} a{G é
tautologia}
 Supondo
{H implica G} e
{H é tautologia}
 Para
{G é tautologia}
ser verdade, então
{G é tautologia} D toda I[G]=T

Proposição 3 –
Implicação e Validade (cont.)
{G é tautologia} D toda I[G]=T
 Mas se {H é tautologia}, toda I[H]=T
 Como {H implica G}, então toda I[G]=T
 {G é tautologia}