Lógica de Primeira-Ordem

Prévia do material em texto

Lógica de Primeira-Ordem
Prof. Francicleber Ferreira
12 de Maio de 2018
1 A Linguagem da Lógica de Primeira-Ordem
1.1 O alfabeto.
O alfabeto da lógica de primeira-ordem é composto por:
• Variáveis: V ar = {x, y, z, . . . , x0, x1, x2, . . . }
• (Símbolos de) constante: c, s, . . . , c0, c1, c2, . . .
• Símbolos funcionais: f , g, h, . . . , f0, f1, . . .
• Símbolos relacionais: R, P , Q, . . .P0, P1, . . .
• Igualdade: ≈.
• Conectivos: ∧, ∨, →, ↔, ¬.
• Quantificadores: ∀, ∃.
• Símbolos de pontuação: (, ), [, ], {, }, . . .
1.2 Vocabulário.
Um vocabulário (ou conjunto de símbolos, ou assinatura) é um conjunto com-
posto por símbolos de constate, símbolos funcionais e símbolos relacionais onde,
a cada símbolo funcional e cada símbolo relacional é associado uma aridade (um
número natural).
Ex.: Vocabulário da aritmética
Sar = {+,×, s, 0}
onde + e × são símbolos funcionais binários, s é um símbolo funcional unário e
0 um símbolo de constante.
Vocabulário da teoria dos grafos
Sgr = {E}
onde E é um símbolo relacional binário.
Vocabulário da teoria dos conjuntos
Sset = {∈}
onde ∈ é um símbolo relacional binário.
1
1.3 S-Termos.
O conjunto TS dos S-termos é definido indutivamente:
- toda variável x é um S-termo;
- toda constante c ∈ S é um S-termo;
- se f ∈ S é um símbolo funcional n-ário e t1, . . . , tn são S-termos, então
ft1 . . . tn é um S-termo.
1.4 S-Fórmulas.
O conjunto LS das fórmulas é definido indutivamente:
- se R ∈ S é um símbolo relacional de aridade n e t1, . . . , tn são S-termos,
então Rt1 . . . tn é uma S-fórmula atômica.
- se φ e ψ são S-fórmulas, então (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ), (¬φ)
são S-fórmulas.
- se x é uma variável e φ é uma S-fórmula, então ∀xφ e ∃xφ são S-fórmulas.
2 Semântica da Lógica de Primeira-Ordem
2.1 S-Estrutura.
Dado um vocabulário S, uma S estrutura é um par A = (A, σ) onde A é o
domínio de A e σ uma função que associa a cada símbolo de constante c ∈ S um
elemento σ(c) = cA, a cada símbolo funcional f ∈ S de aridade n uma função
n-ária σ(f) = fA : An → A sobre A e a cada símbolo relacional R ∈ S de
aridade n uma relação n-ária σ(R) = RA ⊆ An sobre A.
Quando o vocabulário S = {R1, . . . , Rn, f1, . . . fm, c1, . . . , ck} é finito, costu-
mamos escrever uma S-estrutura A como uma sequência
A = (A,RA1 , . . . , RAn, fA1 , . . . , fAm, cA1 , . . . , cAk}
Ex.: Seja S = {R, f, c} um vocabulário onde R é um símbolo relacional
binário, f é um símbolo funcional unário e c é um símbolo de constante. Seja
A a seguinte S-estrutura
A = (A,RA, fA, cA)
onde A = {e, f, g},
RA = {(e, f), (e, g), (f, g)},
fA(e) = f , fA(f) = g, fA(g) = g,
cA = e.
2.2 Atribuição de variáveis.
Dado um conjunto A, uma atribuição de variáveis sobre A é uma função
β : V ar → A
que associa a cada variável um elemento de A.
2
2.3 Interpretação.
Dado um vocabulário S, uma S-interpretação é um par
I = (A, β)
onde A é uma S-estrutura e β é uma atribuição de variáveis sobre o domínio de
A.
2.4 Interpretação dos termos.
Dada uma S-interpretação I = (A, β), definimos a função
I : TS → A
sobre o conjunto dos termos recursivamente como:
I(x) = β(x)
I(c) = cA
I(ft1 . . . tn) = f
A(I(t1), . . . , I(tn))
2.5 Relação de satisfação |=.
Dada uma S-interpretação I = (A, β), definimos a relação de satisfação |= entre
S-interpretações e S-fórmulas como
I |= Rt1 . . . tn sse (I(t1), . . . , I(tn)) ∈ RA
I |= t1 ≈ t2 sse I(t1) = I(t2)
I |= (φ ∧ ψ) sse I |= φ e I |= ψ
I |= (φ ∨ ψ) sse I |= φ ou I |= ψ
I |= (φ→ ψ) sse se I |= φ, então I |= ψ
I |= (¬φ) sse I 6|= φ
I |= ∀xφ sse para todo a ∈ A, I xa |= φ
I |= ∃xφ sse existe a ∈ A, I xa |= φ
3