Lógica de Predicados (propriedades)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lógica de Predicados 
 Propriedades semânticas
Propriedades
 Tautologia
 Satisfabilidade
 Implicação
 Equivalência
 Relações entre propriedades
 (H→G) é uma tautologia ⇔ H implica G
 (H↔G) é uma tautologia ⇔ H equivale a G
 O conjunto de propriedades semânticas da Lógica de predicados 
é análogo ao conjunto de propriedades apresentado para Lógica 
Proposicional, mas as técnicas utilizadas nas demonstrações são 
diferentes 
Satisfabilidade de fórmulas
 Uma fórmula H é satisfazível quando existe pelo menos uma 
interpretação I, tal que I[H]=T
 As fórmulas H1, H2, H3 e H4 são satisfazíveis
I1[H1] = I2[H2] = I3[H3] = I4[H4] = T
a) H1=p(x,y), I1 é uma interpretação sobre os naturais N, tal que: I1[p]=“<”, 
I1[x]=5 e I1[y]=9
b) H2= (∀x)p(x,y), I2 é uma interpretação sobre os naturais N, tal que: 
I2[p]=“>=” e I2[y]=0
c) H3= (∀x) (∃y) p(x,y), I3 é uma interpretação sobre os naturais N, tal que: 
I3[p]=“<” 
d) H4= (∀x) (∃y) p(x,y) →p(x,y), I4 é uma interpretação sobre N, tal que: 
I4[p]=“<”, I4[x]=5 e I4[y]=9
Satisfabilidade de fórmulas
 Considere H=¬((∀x)p(x,y)) ↔ (∃x)(¬p(x,z))
 Se I é uma interpretação sobre o conjunto dos números naturais
I[p(x,y)] = T ⇔ xI e yI são números pares.
I[y]=4, I[z]=6
 Quais os símbolos livres?
 Como temos uma relação de equivalência na fórmula H, então
I[H] = T ⇔ I[¬((∀x)p(x,y)) ] = I[(∃x)(¬p(x,z))]
 Demonstre que I[¬((∀x)p(x,y)) ] = T e I[(∃x)(¬p(x,z))] = T
Satisfabilidade de fórmulas
 Demonstre que I[¬((∀x)p(x,y)) ] = T e I[(∃x)(¬p(x,z))] = T
 I[¬((∀x)p(x,y))] = T ⇔ I[(∀x)p(x,y)] = F
 ⇔ ∃d∈N; <x←d> I[p(x,y)] = F
 ⇔ ∃d∈N; d e/ou 4 são números ímpares
 ⇔ ∃d∈N; d é um número ímpar
I[(∃x)(¬p(x,z))] = T ⇔ ∃d∈N; <x←d> I[¬p(x,z)] = T
 ⇔ ∃d∈N; <x←d> I[p(x,z)] = F
 ⇔ ∃d∈N; d e/ou 6 são números ímpares
 ⇔ ∃d∈N; d é um número ímpar
 I[¬((∀x)p(x,y)) ] = I[(∃x)(¬p(x,z))] = T
 I[H] = T
Validade de fórmulas
 Não-validade = não é tautologia!
 H é satisfazível, mas não é uma tautologia
 Considere H=¬((∀x)p(x,y)) ↔ (∃x)(¬p(x,z))
 Por denifição H não é válida ⇔ ∃ interpretação J; J[H]=F
 Se J[H] = F ⇔ J[¬((∀x)p(x,y))] ≠ J[(∃x)(¬p(x,z))]
Validade de fórmulas
 Tautologia (válida)
 Considere G=¬((∀x)p(x)) ↔ (∃x)(¬p(x))
 Demonstração
 G é tautologia sse para qualquer interpretação J, J[G]=T
 Se J[G]=T
 J[¬((∀x)p(x))] = J[(∃x)(¬p(x))] = T 
Validade de fórmulas
 J[¬((∀x)p(x))] = J[(∃x)(¬p(x))] = T 
 J[¬((∀x)p(x))] = T ⇔ J[(∀x)p(x)] = F 
 ⇔ ∃d∈U; <x←d> J[p(x)] = F
 J[(∃x)(¬p(x))] = T ⇔ ∃d∈U; <x←d> J[¬p(x)] = T
 ⇔ ∃d∈U; <x←d> J[p(x)] = F
Portanto, J[p(x)] = F e J[¬p(x)] = T
Logo J[¬((∀x)p(x))] = T e J[(∃x)(¬p(x))] = T 
J[G] = T
Tautologia!
Validade de fórmulas 
 Considere H= (∃y)(∀x)q(x,y)) → (∀x)(∃y)(q(x,y)) 
 H é tautologia. Suponha por contradição que H não é tautologia, logo 
existe uma interpretação I no domínio U, tal que I[H]=F
 Temos uma implicação, logo
 Se I[H]=F então I[(∃y)(∀x)q(x,y))] = T e I[(∀x)(∃y)(q(x,y))] = F
Validade de fórmulas
 Demonstração
I[(∃y)(∀x)q(x,y))] = T ⇔ ∃d∈U; <y←d> I[(∀x)q(x,y))] = T
 ⇔ ∃d∈U; ∀e∈U, <x←e> <y←d> I[q(x,y))] = T
 ⇔ ∃d∈U; ∀e∈U, qI(e,d) = T
I[(∀x)(∃y)(q(x,y))] = F ⇔ ∃r∈U; <x←r> I[(∃y)q(x,y))] = F
⇔ ∃r∈U; ∀s∈U, <y←s> <x←r> I[q(x,y))] = F
⇔ ∃r∈U; ∀s∈U, qI(r,s) = F
 As afirmações obtidas são contraditórias, logo tautologia! 
Implicações e equivalências entre fórmulas
 Implicação 
 H = (∀x)p(x) implica G=p(a)
 Seja I[H] = T. Demonstre G[T]
I[H] = T⇔ I[(∀x)p(x)] = T
 ⇔ ∀d∈U; <x←d> I[p(x)] = T
 ⇔ ∀d∈U; pI(d) = T
 ⇔ pI(aI) = T
 ⇔ I[p(a)] = T
 ⇔ I[G] = T
Portanto, se I[H] = T, então I[G]=T. Logo, H implica G
Equivalência entre fórmulas
 Equivalência
 Sejam E1 = (∀x)(H∨G) e E2 = (H∨ (∀x)G) fórmulas equivalentes
 Logo E1 equivale a E2 ⇔ ∀I, I[E1] = I[E2]
 Seja a interpretação I no domínio U, tal que I[E1]=T
 I[E1]=T ⇔ I[(∀x)(H∨G)] = T
 ⇔ ∀d∈U; <x←d> I[H∨G] = T
 ⇔ ∀d∈U; <x←d> I[H] = T e/ou <x←d> I[G] = T 
I[E1]=T ⇔ ∀d∈U; I[H] = T e/ou <x←d> I[G] = T 
 ⇔ I[H] = T e/ou ∀d∈U; <x←d> I[G] = T 
 ⇔ I[H] = T e/ou I[(∀x)G] = T 
 ⇔ I[H∨ (∀x)G] = T
 ⇔ I[E2]=T
Portanto, I[E1] = I[E2]=T, logo E1 equivale a E2
Equivalência entre fórmulas
 Sejam H = (∃x)(p(x)→r(x)) e G = (∀x)p(x)→(∃x)r(x) fórmulas 
equivalentes e I[H]=F
 I[H]=F ⇔ I[(∃x)(p(x)→r(x))] = F
 ⇔ ∀d∈U; <x←d> I[(p(x)→r(x))] = F (implicação!)
 ⇔ ∀d∈U; <x←d> I[p(x)] = T e ∀d∈U; <x←d> I[r(x)] = F
 ⇔ I[(∀x)p(x)] = T e I[(∃x)r(x)] = F
 ⇔ I[(∀x)p(x) → (∃x)r(x)] = F
 ⇔ I[G]=F
Portanto, I[H] = I[G]=F, logo H equivale a G
	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