Embed Size (px)
Citation preview
62
Parte 2. LÓGICA de PREDICADOS
A lógica de predicados de primeira ordem é uma extensão da logica proposicional para uma
linguagem mais rica, portanto de maior poder de expressão. Argumentos como
(1)
Todos os felinos são mamíferos
Alguns felinos são ferozes
Alguns mamíferos são ferozes
(2)
O sucessor de um inteiro par é ímpar
2 é um inteiro par
O sucessor de 2 é ímpar
do ponto de vista da lógica proposicional são da forma p ∧ q → r que não são validados pela
lógica proposicional.
Na lógica de primeira ordem usamos variáveis, quantificadores e predicados para capturar ele-
mentos mais finos da estrutura gramatical.
Na lógica de primeira ordem quantificadores atuam apenas nos objetos do domínio do discurso
e os predicados dizem respeito aos objetos, nas lógica de segunda ordem quantificadores atuam
em varáveis e em conjuntos de variáveis e podemos expressar propriedades de propriedades,
expressas por predicados de segunda ordem, isto é, nas teorias de primeira ordem, os predica-
dos são frequentemente associados a conjuntos enquanto que nas teorias de ordem superior, os
predicados podem ser interpretados como conjuntos de conjuntos. Isso permite analisar argu-
mentos como
Dumbo é um elefante
elefante é uma espécie
Dumbo é uma espécie
que não é formalizado de modo apropriado em lógica de primeira ordem.
A lógica de primeira ordem é o padrão para a formalização axiomática da matemática. A Aritmé-
tica de Peano, por exemplo, e a Teoria de Conjuntos de Zermelo–Fraenkel são axiomatizações da
Teoria dos Números e da Teoria de Conjuntos.
Os fundamentos da lógica de primeira ordem foram desenvolvidos de forma independente por
Gottlob Frege e Charles Sanders Peirce.
8. LINGUAGENS DA LÓGICA DE PRIMEIRA ORDEM
8.1. Discussão informal. O que queremos formalizar com a Lógica de predicados? Sentenças
como
• Todos os pássaros são mais leves que algum mamífero.
• Todo aluno é mais novo que algum professor.
63
• Todo número primo maior ou igual a dois é ímpar.
• Todo anel de divisão finito é um corpo.
podem ser simbolizadas no cálculo sentencial, mas o dito não captura toda estrutura da sen-
tença. Os alvos do discurso (sujeito e objeto gramaticais) têm qualidade e mantêm relações.
O que procuramos? Uma linguagem mais rica que leva em conta a estrutura interna das senten-
ças
sujeito – predicado – objeto
na qual sujeito e objetos de quem se fala são elementos de um universo do discurso e são repre-
sentados por constantes, por objetos genéricos e não especificados (pronomes) que são repre-
sentados por variáveis; os predicados e as relações são explicitados. Incorpora o “para todo” e
o “existe” como primitivas da linguagem.
Exemplo 48. Num universo (de discurso) far, far away ....
Constantes: a para ’Armando’, d para ’Daniel’ e j para ’Jair’.
Predicados: P para ’é professor’ e A para ’é aluno’.
Relações: J para ’lecionam juntos’ e N para ’é mais novo’.
P (a) simboliza a sentença ’Armando é professor’.
¬A( j ) simboliza a sentença ’Jair não é aluno’.
J (a,d) simboliza a sentença ’Armando e Daniel lecionam juntos’.
M(d , a) simboliza a sentença ’Daniel é mais novo que Armando’.
Obervemos que, considerando o significado natural das sentenças, J(a,d) e J(d , a) têm o mesmo
significado, mas M(a,d) e M(d , a) não têm o mesmo significado.
Variáveis: usamos x, y, z . . . para representar membros genéricos do universo.
P (x) simboliza ’x é professor’ e M(x, y) simboliza ’x é mais novo que y’. Nem P (x) nem M(x, y) têm
valor lógico, não são sentenças no sentido da lógica proposicional vimos na Parte 1 destas notas.
São chamadas de sentenças abertas.
As sentenças abertas tornam-se sentenças lógicas quando substituímos as variáveis por constantes
ou se quantificamos.
Quantificadores: o quantificador ∀ é lido “para todo” e o quantificador ∃ é lido “existe”.
∀x P (x) simboliza a sentença ’para todo x, x é professor’ a qual pode ser atribuída valor lógico:
significa que todo elemento do universo do discurso é professor.
64
∃x P (x) simboliza a sentença ’existe x, x é professor’ a qual pode ser atribuída valor lógico: significa
que pelo menos um elemento do universo do discurso é professor.
Notemos que, por exemplo
(1) ∀x M(x, y) é uma sentença aberta
(2) ∃y ∀x M(x, y) e ∀x ∃y M(x, y) têm significados diferentes.
A sentença ’Todo aluno é mais novo que algum professor’ pode ser simbolizada por
∀x ∃y(A(x)∧P (y) → M(x, y))
A sentença ’Há um professor tal que todo aluno aprende algo com ele’, considerando as relações
B(x, y, z) para ’y aprende z com x’ e H(x) para ’x é um assunto’, pode ser simbolizada por
∃x�P (x)∧∀y
�A(y) →∃z (H(z)∧B(x, y, z))
��
Em matemática, muitas vezes tratamos de estruturas que consistem em um conjunto de ele-
mentos com várias operações sobre eles e relações entre eles. Por exemplo, na Teoria Elemen-
tar de Números o conjunto de elementos em discussão é o conjunto de números inteiros Z ={0,±1,±2, . . . } Pode-se precisar de símbolos para alguns números, para variáveis, para funções
(como · e +) e para as relações (como =, <, e |). A sentença “Para todo x, se x é inteiro igual a zero
ou maior que zero e todo inteiro é divisível por x, então x é igual a um” considerando que
• 0 e 1 são constantes;
• >(x, y) simboliza a relação “x é maior que y”;
• =(x, y) simboliza a relação “x é igual a y” e
• | (x, y) simboliza a relação “x divide y”,
é simbolizada como
∀x��>(x,0)∨=(x,0)
�∧∀y (| (x, y)) →=(x,1)�.
8.2. Linguagem formal da lógica de predicados. Há várias linguagens lógicas de primeira or-
dem e há símbolos comuns a todas, além de outros específicos de cada linguagem (e.g., ∈, +). A
seguir descrevemos a linguagem lógica L1 genérica de primeira ordem.
Alfabeto genérico. O alfabeto A1 ds símbolos permitidos para as expressões na linguagem L1
incluem
65
Variáveis: x1 x2 x3 . . .
Conectivos lógicos: ¬ →Quantificador: ∀Pontuação: ( )
Símbolo de igualdade:.=
Constantes: c1 c2 c3 . . .
Símbolos relacionais: para cada inteiro n ≥ 0, símbolos relacionais n-ários Rn1 ,Rn
2 ,Rn3 , . . .
Símbolos funcionais: para cada inteiro n ≥ 1, símbolos funcionais n-ários F n1 ,F n
2 ,F n3 , . . .
As constantes, os símbolos relacionais e funcionais são específicos de cada linguagem de pri-
meira ordem e um ou mais deles pode ser vazio, isto é, o conjunto das constantes pode ser vazio,
o conjuntos dos símbolos relacionais pode ser vazio e o conjunto símbolos funcionais pode ser
vazio. Os símbolos relacionais de aridade 0 são usados como símbolos proposicionais.
Os símbolos descritos nos quatros primeiros itens do alfabeto são os símbolos lógicos da lingua-
gem. Os símbolos lógicos são compartilhados por toda linguagem de primeira ordem. O símbolo
de igualdade é um símbolo relacional binário especial. Há autores que tratam a igualdade como
um símbolo símbolo lógico e outros que tratam como não-lógico de modo a distinguir-se as lin-
guagens de primeira ordem com igualdade e sem igualdade. Aqui não faremos essa distinção,
não o chamaremos de lógico mas consideraremos que toda linguagem de primeira ordem tem
o símbolo de igualdade. As constantes e os simbolos relacionais e funcionais são os símbolos
não-lógicos da linguagem, os quais, geralmente, dependem do uso pretendido.
Intuitivamente, as constantes são interpretadas como elementos específicos do universo de dis-
curso da linguagem; os símbolos da função n-ária são interpretados como funções específicas
que mapeiam n-úplas de elementos do universo de discurso à elementos do universo; os sím-
bolos de relação n-ária destinam-se a designar relações entre n elementos. O símbolo quantifi-
cador destina-se a representar “para todos” em referência à todos os elementos do universo e é
usado com variáveis.
Termos: são as sequências de símbolos do alfabeto obtidas a partir das regras abaixo.
(T1) Variáveis e constantes são termos.
(T2) Para qualquer natural n, e qualquer símbolo funcional F ni , se t1, t2, . . . , tn são termos en-
tão F ni t1t2 . . . tn é termo.
(T3) Não há outros termos além dos obtidos pela aplicação de um número finito de vezes das
regras acima.
66
Exemplo 49. São termos: c1, x101, F 12 x1, F 2
2 x1c8, F 41 c1c2x1x2. Note que F 2
2 x1 não é termo (por
quê?). A cadeia de símbolos F 11 F 2
1 x1x2 é um termo? F 11 F 2
1 F 11 x1x2 é um termo?
Metateorema 50 (Teorema da unicidade de representação dos termos). Se t é um termo de uma
linguagem, então uma, e apenas uma, das asserções abaixo é verdadeira:
• t é uma variável;
• t é uma constante;
• t é da forma F (t1, . . . , tn), onde t1, . . . , tn são termos e F é um símbolo funcional n-ário,
para únicos n, F e ti ’s.
Metateorema 51 (Princípio de indução para termos). Seja Γ um conjunto de termos de uma lin-
guagem de primeira ordem. Se
(1) as variáveis e as constantes pertencem a Γ;
(2) se t1, t2, . . . tn pertencem a Γ então F (t1, t2, . . . tn) pertence a Γ para qualquer que seja o
símbolo funcional F .
Então Γ é o conjunto de todos os termos da linguagem.
Fórmulas: ou fórmulas bem formadas, são as sequências de símbolos do alfabeto A1 obtidas a
partir das regras abaixo.
(F1) Se t e s são termos, então (.= t s) é uma fórmula. Também, para qualquer natural n, e
qualquer símbolo relacional Rni , se t1, . . . , tn são termos então Rn
i t1t2 . . . tn é uma fórmula.
As fórmulas da linguagem obtidas por aplicação exclusiva dessa regra são ditas atômica.
(F2) Se α e β são fórmulas, então (¬α) e (α→β) são fórmulas.
(F3) Se α é fórmula e x é uma variável, então (∀xα) é fórmula.
(F4) Não há outras fórmulas além daquelas obtidas pela aplicação um número finito de vezes
as regras acima.
Exemplo 52.��
R11 x1 → R3
2 x4x2c1�→ �∀x1((∀x2 R3
2c4x2c1) → (¬(.= F 1
1 x1F 11 c1)))
��.
Metateorema 53 (Teorema da unicidade de representação das fórmulas). Seja α uma fórmula
de uma linguagem. Então α satisfaz uma, e apenas uma, das condições abaixo
• α é uma fórmula atômica da forma R(t1, . . . , tn), onde R é um símbolo relacional n-ário e
t1, . . . , tn são termos, para únicos n, R e ti ’s;
• α é uma fórmula atômica da forma (s.= t ) onde s e t são termos, para únicos s e t ;
• α é da forma ¬β, para uma única fórmula β;
• α é da forma β→ γ para únicos β e γ fórmulas;
• α é da forma ∀xβ, para uma única fórmula β e uma única variável x.
67
Metateorema 54 (Princípio de indução para as fórmulas). Seja Γ um conjunto de fórmulas de
uma linguagem de primeira ordem. Se
(1) as fórmulas atômicas pertencem a Γ;
(2) se α pertence a Γ então ¬α pertence a Γ;
(3) se α e β pertencem a Γ então α→β pertence a Γ;
(4) se α pertence a Γ e x é uma variável, então ∀xα pertence a Γ.
Então Γ é o conjunto de todas as fórmulas da linguagem.
Simplificações, abreviaturas e omissão de parênteses. Vamos assumir algumas convenções de no-
tação para facilitar nossa vida.
Simplificações. No uso dos símbolos admitimos algumas simplificações na escrita, como já fize-
mos logo acima.
Fórmulas: α,β,γ, . . . possivelmente com índices.
Termos: s, t ,u, v possivelmente com índices.
Variáveis: x, w, y, z possivelmente com índices.
Constantes: a,b,c,d ,e, f possivelmente com índices.
Símbolos relacionais: Ao invés de Rni escrevemos R e também usamos
outros símbolos como P,Q,R,S,<,≺. Ainda, es-
crevemos
R(t1, t2, . . . , tn) ao invés de Rn t1t2 . . . tn .
Para as relações R binárias escrevemos
(a R b) ao invés de R(a,b)
como em (a < b), em particular, escrevemos
(t.= s) ao invés de
.= (t , s)
como é usual.
Símbolos funcionais: Ao invés de F ni escrevemos F e também usamos
outros símbolos como F,G , H ,+, ·. Ainda, ao invés
de F n t1t2 . . . tn escrevemos F (t1, t2, . . . , tn). Para as
operações binárias F escrevemos (a F b) ao invés
de F (a,b), como em (a +b).
Abreviaturas. Para resultados teóricos (metamatemáticos) é vantajoso possuirmos o mínimo
possível de símbolos, entretanto, para expressarmos de maneira clara e sucinta quanto mais
68
símbolos, melhor. Tratando alguns símbolos como abreviaturas de outros ganhamos dos dois
lados.
símbolo lê-se uso
∧ conjunção (α∧β) abrevia (¬(α→ (¬β)))
∨ disjunção (α∨β) abrevia ((¬α) →β)
↔ biimplica (α↔β) abrevia ((α→β)∧ (β→α))
∃ existe (∃xα) abrevia (¬(∀x(¬α)))
� não existe (� ∃xα) abrevia (¬(∃xα)) ou seja (¬(¬(∀x(¬α))))
�= diferente (s �= t ) abrevia (¬(s.= t ))
⊥ falsum abrevia (α∧ (¬α))
� verum abrevia (¬⊥)
Representamos os conectivos ∨, ∧, → e ↔ genericamente, pelo símbolo �, no caso de múltiplas
ocorrências de conectivos distintos usaremos índices �1, �2 e assim por diante. Com isso α�βindica uma fórmula composta por α, β e algum dos conectivos e qual deles, especificamente,
não importa no momento em que se usa o símbolo � com o cuidado de que duas ocorrências
numa mesma frase significa o mesmo conectivo; por exemplo em “α�η deve ser lido como
(α�η)” não deve ser entendido como, por exemplo, “α→ η deve ser lido como (α∧η)” mas sim
como “α→ η deve ser lido como (α→ η)” (e, respectivamente, o mesmo para � sendo ∧,∨,↔).
Ademais, representamos os quantificadores ∀ e ∃ genericamente por Q com as mesmas consi-
derações do parágrafo acima.
Omissão de parênteses.
• Omitimos os parênteses externos de uma fórmula, recolocando quando a usamos para
compor outras fórmulas. Por exemplo, escrevemos α→β no lugar de (α→β), mas reco-
locamos os parênteses quando escrevemos, por exemplo, ∀x(α→β).
• ∀ tem precedência sobre ¬ que tem precedência sobre →; considerando as abreviações
ordem de precedência é ∀,∃,¬,∧,∨,→,e ↔.
• Conectivos repetidos são agrupados pela direita, por exemplo, α→ β→ γ é lido como
(α→ (β→ γ)).
• Quando não houver riscos de más interpretações, omitimos os parênteses externos em
subfórmulas do tipo ∀xα, ∃xα e ¬α. Por exemplo, escrevemos ¬∀x∃yα, em vez de
¬(∀x(∃yα)).
Exemplo 55. De volta ao exemplo 52
��R1
1 x1 → R32 x4x2c1
�→ �∀x1((∀x2 R32c4x2c1) → (¬(
.= F 11 x1F 1
1 c1)))��
69
que simplificando fica escrito como
(R(x) → S(z, y,c)) → ∀x∀y�S(a, y,c) → (F (x) �= F (c))
�.
8.3. Linguagens de primeira ordem para a Aritmética. Vejamos um exemplo de linguagem de
primeira ordem para a Aritmética que consiste do estudo dos números naturais e suas proprie-
dades. Denotaremos essa linguagem por LN cujo alfabeto contém, além dos símbolos lógicos,
os não-lógicos
• a constante 0,
• o símbolo funcional unário S e os símbolos funcionais binários + e ·, e
• o símbolo relacional binário <.
São exemplos de termos dessa linguagem+·0x1 x2, SSSS0, +x1S0,.= ·x1+S0SS0 ·x1SSS0. Usando
as convenções de simplificação reescrevemo-os (0·x)+y , S(S(S(S(0)))), x+S(0), x·(S(0)+S(S(0))).=
x ·S(S(S(0))). São fórmulas da linguagem:
(1) < ·S0S0 +S0S0 ou, simplesmente, S(0) ·S(0) < S(0)+S(0).
(2) (∀x1.=+0x1x1) ou, simplesmente, ∀x(x +0
.= x).
(3)�∀x1
�∀x2(.=+S0x1 +x2S0 → .= x1x2)
��ou ∀x∀y (x +S(0)
.= y +S(0) → x.= y).
(4) Já simplificado ∀x∀y ∃z�y
.= x + z → (x < y ∨x.= y)
�.
A intenção é interpretar a constante 0 como o número zero, S como a função sucessor e +, ·,<interpretados como, respectivamente, a adição, a multiplicação é o menor que em N. Os ter-
mos 0,S0,SS0,SSS0,SSSS0, . . . intencionam descrever os números naturais zero, um , dois, três,
quatro, etc.
Com essa interpretação, que ainda é uma intenção, ela só vai ser dada quando falarmos da se-
mântica, podemos dar alguns exemplos intuitivos da expressão da aritmética nessa linguagem.
Exemplo 56. ’Não existe raiz de 2’ é expresso por �x(x · x.= S(S(0))) que reescrita usando somente
símbolos do alfabeto fica (¬(¬(∀x1(¬(.= ·x1x1SS0))))). Também podemos expressar a mesma ideia
usando (∀x1(¬(.= ·x1x1SS0))).
Exercício 57. Expresse em LN a sentença ’existem infinitos números primos’.
8.4. Outros exemplos de linguagens de primeira ordem. Uma linguagem de primeira ordem
tem os símbolos lógicos (comum às linguagens) e os símbolos extralógicos (específicos de cada
linguagem). Abaixo, para definir uma linguagem explicitamos só os símbolos extralógicos.
Exemplo 58. A linguagem da igualdade pura, L=:
Não há símbolos não-lógicos.
70
Ainda assim conseguimos expressar certas ideias, por exemplo, ’existe um único sujeito’ ∃x∀y(y.=
x), ou ’existem somente dois sujeitos’ ∃x ∃y((x �= y)∧∀z (z.= x ∨ z
.= y)).
Exemplo 59. Uma linguagem para Teoria dos Conjuntos LC :
Símbolo relacional binário: ∈
A intenção das variáveis é representar conjuntos e x ∈ y diria que o conjunto x é elemento do
conjunto y. A Teoria de Conjuntos de Zermelo–Fraenkel é escrita nessa linguagem. A existência
do conjunto vazio é expressa por ∃x∀y¬(y ∈ x). A existência do conjunto definido no paradoxo de
Russel (página 10) é expresso por ∃x∀y (y ∈ x ↔¬(y ∈ y)). Veremos que a negação dessa sentença
é uma tautologia.
Exercício 60. Escreva uma fórmula que simboliza a sentença “existe um conjunto vazio” em LC .
Escreva uma fórmula que simboliza a sentença “existe somente um objeto” em L=.
Escreva uma fórmula que simboliza a sentença “adição é associativa” em LN .
8.5. Variáveis livres e ligadas, sentenças. Dizemos que uma variável x ocorre livre em uma fór-
mula α se
(1) α é atômica e x ocorre em α;
(2) α é da forma (¬β) e x ocorre livre em β;
(3) α é da forma (β�γ) e x ocorre livre em β ou γ;
(4) α é da forma Q yψ e x é diferente de y e x ocorre livre em ψ.
Uma ocorrência de x emα que não é livre é dita ligada. O item 4 acima é a chave para classificar-
mos a ocorrência de uma variável como livre ou ligada: a ocorrência de uma variável x é ligada
se ela está no escopo de uma ocorrência de um quantificador. O escopo de um quantificador
numa fórmulaα é a subfórmula β na qual o quantificador se aplica (quando a regra de formação
de fórmula quantificada foi aplicada, isto é, em (∀xβ) o escopo de x é β).
Cada ocorrência de uma variável x é livre ou ligada, mas não ambas. Entretanto, a mesma variá-
vel pode ocorrer livre e ligada na mesma fórmula. Por exemplo,
(1) Em ∀x7(x5.= x7) a ocorrência de x5 é livre e a ocorrência de x7 é ligada.
(2) Em ∀x0 ((x0.= F (x6)) → (¬∀x6 R(x6))) a primeira ocorrência de x6 é livre e a última ocor-
rência é ligada.
(3) Em ∀z (∀x (P (x) → R(z))) → (Q(y) → P (x)) a variável x é livre e ligada, y é livre e z é
ligada.
Uma fórmula α sem ocorrência de variáveis livre é dita sentença.
71
Antes de irmos adiante, definimos indutivamente o conjunto V L das variáveis livres de uma
fórmula:
(1) se t é termo então
V L(t ) :=
�, se t é c
{x}, se t é x
V L(t1)∪ · · ·∪V L(tn), se t é F (t1, . . . , tn)
(2) se α é fórmula então
V L(α) :=
V L(t1)∪V L(t2), se α é t1.= t2
V L(t1)∪ · · ·∪V L(tn), se α é R(t1, . . . , tn)
V L(β), se α é ¬βV L(β)∪V L(γ), se α é β�γV L(β) \ {x}, se α é Q xβ
Pelos metateoremas de indução o conjunto V L está definido para todos os termos e todas as
formulas da linguagem L1.
8.6. Substituição de variáveis. Se t e s são termos e x é uma variável, definimos [t ]sx o termo
obtido substituindo toda ocorrência da variável x pelo termo s. Formalmente, definimos a subs-
tituição em termos indutivamente:
• [x]sx é o termo s e [y]s
x é o termo y ;
• se c é uma constante, [c]sx é o termo c;
• se t é da forma F (t1, . . . , tn), então [t ]sx é o termo F ([t1]s
x , . . . , [tn]sx ).
Se α é uma fórmula, x é uma variável e t é um termo, definimos [α]tx a fórmula obtida substi-
tuindo todas as ocorrências livres da variável x pelo termo t . Formalmente, definimos a substi-
tuição em fórmulas recursivamente:
• se α é (s.= t ) então [α]t
x é ([s]tx
.= [t ]tx );
• Se α é R(t1, t2, . . . , tn) então [α]tx é R([t1]t
x , [t2]tx , . . . , [tn]t
x );
• Se α é ¬β então [α]tx é ¬[β]t
x ;
• Se α é γ�β então [α]tx é [γ]t
x �[β]tx ;
• Se α é Q xβ então [α]tx é α; senão, sempre que y �= x, se α é ∀y β então [α]t
x é Q y [β]tx .
Por exemplo
(1) [(x.= y)]x
y é (x.= x).
(2) [(x.= y)]y
x é (y.= y).
72
(3) [∀x (x.= y)]y
x é ∀x (x.= y).
(4) [∀x (x.= y)]x
y é ∀x (x.= x).
(5) [(∀x P (x)) → P (x)]τx é ∀x P (x) → P (τ).
(6) [∀x (¬∀y (x.= y)) → (¬∀y (x
.= y))]yx é ∀x (¬∀y (x
.= y)) → (¬∀y (y.= y)).
(7) [∀x (P (x, y) → (¬Q(y)∨∃y P (x, y)))]F (y,z)y é ∀x (P (x,F (y, z)) → (¬Q(F (y, z))∨∃y P (x, y))).
Exemplo 61. Considere em LN a fórmula ∃x(y.= S(S(0))·x). Se substituímos y pelo termo S(S(S(0)))
temos ∃x (S(S(S(0))).= S(S(0)) · x). Se substituímos por x então temos ∃x(x
.= S(S(0)) · x)
Agora, a substituição da variável x pelo termo t na fórmulaϕ é admissível se nenhuma ocorrên-
cia livre de x emϕ estiver no escopo de um quantificador que liga qualquer variável que aparece
em t . Isto é, para cada variável y que aparece em t , nenhum lugar onde x ocorre livre em ϕ está
no escopo de ’∃y ’ ou ’∀y ’.
Por exemplo, o termo x não é admissível para a variável y na fórmula ∀xP (x, y); o termo F (x, y)
não é admissível para a variável x em ∀yP (x, y); o termo z é admissível para y em P (y, z) →∀yQ(y, z).
Formalmente, o termo t é admissível para a variável x na fórmula α se
(1) α é atômica;
(2) α é ¬β e t é admissível para t em β;
(3) α é β�γ e t é admissível para x em α e em β;
(4) α é Q y β e se x ∈V L(β) então y �∈V L(t ) e t é admissível para x em β.
Exercício 62. Prove usando indução em fórmulas que t é admissível para x em α se, e só se, as
variáveis de t na fórmula [α]tx não são ligadas por um quantificador.
Se x �∈ V L(ϕ), então [ϕ]tx é admissível para qualquer termo t e, nesse caso, as fórmulas ϕ e [ϕ]t
x
são idênticas. Uma variável x sempre é admissível para ela mesmo em qualquer fórmula e [ϕ]xx é
a fórmulaϕ. A variável y não é uma substituição admissível para x na fórmula ∀y (x.= y) porque
se substituímos x por y a nova ocorrência de y seria ligada. Isso fará diferença no valor verdade
de uma sentença, enquanto que ∀y (y.= y) será uma tautologia em qualquer interpretação, a
fórmula ∀y (x.= y) tem valor verdade que dependerá da interpretação.
Exercício 63. É x uma substituição admissível para z em ϕ se ϕ é z.= x →∀z (z
.= x)? Em caso
afirmativo, o que é [ϕ]xz ?
8.7. Generalização. Se α é uma fórmula então uma generalização de α é a fórmula
∀x1∀x2 · · ·∀xnα
para quaisquer coleção de variáveis x1, x2, . . . , xn , independente delas ocorrerem ou não em α.
73
Exemplo 64. São generalizações de x.= y as fórmulas: ∀x (x
.= y), ∀y (x.= y), ∀y∀x (x
.= y),
∀z∀y∀x (x.= y), ∀w∀z∀y∀x (x
.= y).
8.8. Exercícios.
(68) Simbolize as seguintes sentenças (abertas ou não) na linguagem da Aritmética.
(a) Todo número par maior do que dois pode ser escrito como soma de dois números
primos.
(b) x possui exatamente três divisores.
(c) Todo número positivo admite raiz quadrada.
(d) z é o máximo divisor comum de x e y .
(e) Existem infinitos números primos.
(69) Defina uma linguagem de primeira ordem F que trata das relações familiares e escreva
em símbolos as sentenças abaixo.
(a) Ana é irmã de José.
(b) Maria é irmã de Ana.
(c) Pedro é pai de Ana.
(d) Pedro é pai de Maria e de José.
(e) Ana é irmã de José e Maria é irmã de Ana, então Maria é irmã de José.
(f) Tarso é irmão de Pedro e tio de Ana.
(g) Tarso é irmão de Pedro então é tio de José.
(h) Tarso é tio de Maria.
(i) Tarso é tio de Maria e de Ana, que são irmãs de José, logo Tarso é tio de José.
(j) Ele é primo de Maria.
(k) Maria possui uma avó que tem quatro filhos(as).
(70) Identifique as ocorrências livres e não-livres de variáveis nas fórmulas abaixo.
(a) (∃x((1+ y).= x))∧∀y(y < x).
(b) (∃x(x · x.= 2)) → (x +1
.= 0).
(c) ∀x∃y(z < 1).
(d) (∃x((1+ y).= x))∧ (∀y(y < x)).
(e) ∀x(((x < 6)∧ (0 < x)) →∃y(x · y.= z)).
(f) (∀y∃z(x + y.= z)) → (x
.= 0).
(g) (x < y +1) →∀x∃y(x �= y).
(h) ∀x((x.= 0)∨ (0 < x))∧∃y(y · (1+1)
.= x).
(i) ∀x(x > (1+1) → y < (x + x)).
(j) ∀y∀z((y ·z .= x) → ((y¬z)∧((y.= 1)∨(z
.=1)))).
(71) Subfórmulas: Defina indutivamente o conceito de subfórmula. Exiba as subfórmulas de
cada uma das fórmulas que você encontrou no exercício 68.
(72) Dê uma definição precisa de escopo de um quantificador.
74
(73) Use indução para definir o grau de complexidade de uma fórmula (veja o exemplo 5).
Por exemplo grau(s.= t ) = 0, grau(R2(x, y)) = 0, grau(¬(s
.= t )) = 1, grau(∀x R2(x, y)) = 1,
grau(∀y ∀x R2(x, y)) = 2.
(74) Restabeleça os parênteses de acordo com as regras de omissão de parênteses.
(a) ∀x1R11 x1 ∧¬R1
1 x2.
(b) ∀x2R11 x2 ↔ R1
1 x2.
(c) ∀x2∃x1R21 x1, x2.
(d) ∀x1∀x3∀x4R11 x1 → R1
1 x2 ∧¬R11 x1
(e) ∃x1∀x2∃x3R11 x1 ∨∃x2¬∀x3R2
1 x3, x2.
(f) ∀x2¬R11 x1 → R3
1 x1, x1, x2 ∨∀x1R11 x1.
(g) ¬∀x1R11 x1 →∃x2R1
1 x2 → R21 x1, x2 ∧R1
1 x2.
(75) Use indução para mostrar que x é admissível para x em ϕ, para qualquer variável x e
qualquer fórmula ϕ, e [ϕ]xx é a fórmula ϕ.
(76) Sejam t é um termo e α uma sentença. O termo t é uma substituição admissível em α
para qualquer variável x? Qual é o resultado da substituição?
(77) O algoritmo da divisão diz que para quaisquer naturais a, b, com b �= 0, existem naturais
q e r únicos tais que a = bq+r e ≤ 0 < r < b. Expresse o teorema da divisão na linguagem
da aritmética.
(78) Defina indutivamente o conjunto LV (·) das variáveis ligadas de uma fórmula.
(79) Use o princípio de indução para termos para definir comprimento de um termo como o
número de símbolos do alfabeto que ocorrem no termo, exceto os de pontuação.
9. SISTEMA DEDUTIVO
Como na lógica proposicional, são conhecidos alguns sistemas dedutivos para o cálculo de pre-
dicados que são equivalentes no sentido de deduzirem os mesmos teoremas. Apresentaremos
um do tipo Sistema de Hilbert para a linguagem L1 da lógica de primeira ordem. Tal sistema é
axiomático, consiste numa lista finita de axiomas e outra de regras de inferência que podem ser
usados para derivar os teoremas do sistema.
Também como na lógica proposicional chamaremos de axioma e teorema, por exemplo, α→(β→α) e ∀x (α→β) → (α→∀xβ) o que, de fato, são esquemas de axiomas e de teoremas pois
usam variáveis da metalinguagem. Os axiomas são obtidos quando substituímos tais variáveis
por fórmulas nas quais figuram apenas símbolos do alfabeto de modo que toda ocorrência da
mesma (meta)variável é substituída pela mesma fórmula.
9.1. Axiomas. Um sistema dedutivo para uma linguagem de primeira ordem tem duas classes
de axiomas, os lógicos comuns a todas as linguagens e os não-lógicos. Um axioma lógico é uma
75
sentença ou uma fórmula universalmente válida (ou seja, é verdadeira em qualquer possível uni-
verso, não importa como os termos da fórmula são interpretados). Normalmente, toma-se como
axiomas lógicos algum conjunto mínimo de fórmulas suficiente para derivar todas as fórmulas
universalmente válidas. No exemplo 72 apresentamos três axiomas não lógicos da Teoria dos
Grupos. Os esquemas de axiomas lógicos são
(A1): α→ (β→α)
(A2): (α→ (β→ ξ)) → ((α→β) → (α→ ξ))
(A3): (α→β) → ((α→¬β) →¬α)
(A4): α→ (β→ (α∧β))
(A5): α∧β→α
(A6): α∧β→β
(A7): α→α∨β(A8): β→α∨β(A9): (α→ γ) → ((β→ γ) → (α∨β→ γ))
(A10): ¬¬α→α
(A11): (∀x (α→β)) → (∀xα→∀xβ).
(A12): (∀xα) → [α]tx sempre que t é admissível para x em α.
(A13): α→∀xα sempre que x �∈V L(α).
(A14): t.= t
(A15): t1.= t2 → t2
.= t1
(A16): (t1.= t2 ∧ t2
.= t3) → t1.= t3
(A17): (t1.= t �1 ∧ · · ·∧ tn
.= t �n) → �R(t1, . . . , tn) → R(t �1, . . . , t �n)
�
(A18): (t1.= t �1 ∧ · · ·∧ tn
.= t �n) → �F (t1, . . . , tn)
.= F (t �1, . . . , t �n)�
(A19): as generalizações dos esquemas de fórmulas acima.
em que α,β,γ,ξ são fórmulas, x é variável, t e t1, t2, t3, . . . , tn são termos, R é símbolo relacional
(podendo ser o.=)e F símbolo funcional.
Exemplo 65. Caso não houvesse restrição sobre a substituição de variável nos axiomas do ∀ se-
ria possível, por exemplo numa interpretação onde o universo tem mais de um elemento, que a
fórmula ∀x ∃y (x �= y) seja válida. Usando o esquema (A12) incondicionalmente teríamos o axi-
oma ∀x ∃y (x �= y) → [∃y (x �= y)]xy , ou seja, teríamos o axioma ∀x ∃y (x �= y) → ∃y (y �= y) que,
intuitivamente, deveria ser falso.
Exemplo 66. A fórmula
¬∀y ¬P (y) → �P (x) →¬∀y ¬P (y)
�
é uma instância do esquema (A1), portanto é um axioma.
76
A fórmula
(R(x, y) → (∃y (y.= 0)∨R(x, y))
é uma instância de β→ (α∨β), portanto é um axioma do esquema (A8).
A fórmula
∀x�¬∀y (x
.= y)�→ �¬∀y (z
.= y)�
é um axioma do esquema (A12). Também é a fórmula
∀x�
A(x) →∀y A(y)�→ �
A(y) →∀y A(y)�
porém a fórmula
∀x�∀y B(x, y)
�→∀y B(y, y)
não é um axioma desse esquema porque viola a condição de admissibilidade.
Exemplo 67. Na linguagem aritmética, por exemplo, temos o axioma lógico
(x < y) → (∃y (y.= 0)∨ (x < y))
do esquema β→ (α∨β).
Exercício 68. A fórmula (x.= y) → ((x +x
.= 0) → (x + y.= 0)) é um axioma?
9.2. Regras de inferência. Há uma única regra de inferência (de fato esquema) do sistema
(MP):α, α→β
β
9.3. Dedução. Sejamαuma fórmula da linguagem de primeira ordem L1 eΓ⊂L1 um conjunto
de hipóteses ou premissas. Uma prova de α a partir de Γ é uma sequência finita de fórmulas
⟨ϕ1,ϕ2, . . . ,ϕn⟩
tal que ϕn =α e, para i < n, ϕi é
(1) ou um axioma lógico
(2) ou uma fórmula de Γ
(3) ou uma fórmula obtida de ϕ1,ϕ2, . . . ,ϕi−1 por regra de inferência.
Γ�α e lê-se “α é deduzível de Γ”, ou “Γ prova α”, ou α é consequência sintática de Γ.
No caso Γ vazio escrevemos �α e, nesse caso, α é um teorema lógico.
Simplificações de notação: usamos as mesmas simplificações adotadas na lógica proposicional,
ao invés de {α} � β escrevemos α � β; ao invés de {α1, . . . ,αn} � β escrevemos α1, . . . ,αn � β; ao
invés de Γ∪ {α} �β escrevemos Γ,α�β .
77
9.3.1. Propriedades de �. As seguintes propriedades valem exatamente como na lógica de pro-
posições. Como os esquemas de axiomas (A1)–(A10) e a única regra de inferência são os mesmos
da lógica proposicional (agora para fórmulas da lógica de predicados) e definição de dedução é
a mesma, temos que o � na lógica de predicados tem as mesmas propriedades de � do sistema
dedutivo para a lógica de proposições.
Metateorema 69. Se Γ é um conjunto de fórmulas de L1
Autodedução: Γ�α para todo α ∈ Γ.
Monotonicidade: Se Γ�α então Γ∪Σ�α.
Regra do corte: Se Γ�αi para i = 1,2, . . . ,k e {α1, . . . ,αk } �β então Γ�β.
Compacidade: Γ�α se, e só se, existe Δ⊆ Γ finito tal que Δ�α.
Teorema da Dedução: α�β se, e somente se, �α→β ou, genericamente,
Γ,α�β se, e somente se, Γ�α→β. (8)
O teoremas lógicos proposicionais valem com a mesma dedução na lógica de predicados.
Teorema 8. �α→α
Prova. Deduz-se como no teorema 1.1. α→ ((α→α) →α)) (por A1)
2. (α→ ((α→α) →α)) → ((α→ (α→α)) → (α→α)) (por A2)
3. α→ (α→α)) (por A1)
4. (α→ (α→α)) → (α→α) (MP 2,1)
5 α→α (MP 3,4)■
Teorema 9 (Redução ao absurdo (RA)). α→β, α→¬β�¬α
Demonstração. Segue do Teorema da Dedução em (A3). ■
Teorema 10 (Introdução da conjunção (IC)). α, β�α∧β
Demonstração. Segue do Teorema da Dedução em (A4). ■
Teorema 11 (Eliminação da conjunção (EC1)). α∧β�α
Demonstração. Segue do Teorema da Dedução em (A5). ■
Teorema 12 (Eliminação da conjunção (EC2)). α∧β�β
Demonstração. Segue do Teorema da Dedução em (A6). ■
78
Teorema 13 (Introdução da disjunção (ID1)). α�α∨β
Demonstração. Segue do Teorema da Dedução em (A7). ■
Teorema 14 (Introdução da disjunção (ID2)). β�α∨β
Demonstração. Segue do Teorema da Dedução em (A8). ■
Teorema 15 (Duns Scotus (DS)). α, ¬α�β
Prova. Dá-se como na dedução do teorema 6.
1. α (hip.)
2. ¬α (hip.)
3. α→ (¬β→α) (A1)
4. ¬α→ (¬β→¬α) (A1)
5. ¬β→α (MP 1,3)
6. ¬β→¬α (MP 2,4)
7. (¬β→α) → �(¬β→¬α) →¬¬β�
(A3)
8. (¬β→¬α) →¬¬β (MP 5,7)
9. ¬¬β (MP 6,8)
10. ¬¬β→β (A10)
11. β (MP 9,10)■
Teorema 16 (Modus Tollens (MT)). α→β,¬β�¬α
Prova.1. α→β (hip.)
2. ¬β (hip.)
3. (α→β) → ((α→¬β) →¬α) (A3)
4. ¬β→ (α→¬β) (A1)
5. α→¬β (MP 2,4)
6. (α→¬β) →¬α (MP 1,3)
7. ¬α (MP 5,6)■
Teorema 17 (Contra-positiva (CP1)). α→β�¬β→¬α
Demonstração. Segue de Modus Tollens por aplicação do Teorema da Dedução. ■
Teorema 18 (Silogismo hipotético (SH)). α→β,β→ γ�α→ γ
79
Prova. Dá-se como a dedução do teorema 2. ■
Teorema 19 (Silogismo disjuntivo (SD)). α∨β, ¬α�β
Prova.1. α∨β (hip.)
2. ¬α→β (def. de ∨)
3. ¬α (hip.)
4. β (por MP 2,3)■
Teorema 20 (Troca condicional (TC)). θ→ (φ→ ξ) �φ→ (θ→ ξ)
Prova. Segue a dedução do teorema 3. ■
Teorema 21 (Dupla negação (DN1)). ¬¬α�α.
Prova. Segue de (A10) e o teorema da Dedução. ■
Teorema 22 (Dupla negação (DN2)). �α→¬¬α
Prova. Deduz-se como no teorema 5. ■
Teorema 23 (Contra-positiva (CP2)). ¬β→¬α�α→β
Prova.1. ¬β→¬α (hip.)
2. (¬β→¬α) → (¬¬α→¬¬β) (CP1)
3. ¬¬α→¬¬β (MP 1,2)
4. α→¬¬α (DN2)
5. ¬¬β→β (DN1)
6. α→¬¬β (SH 4,3)
7. α→β (SH 6,5)■
9.3.2. Regras de inferências derivadas. Os sistemas dedutivos do estilo de Hilbert têm poucas re-
gras de dedução. Aaas regras de inferência adicionais advindas dos teoremas lógicos não acres-
centam nenhum poder dedutivo ao sistema, no sentido de que uma dedução usando as novas
regras de dedução pode ser convertida em uma dedução usando apenas a dedução com a regra
original.
Uma regra de inferência derivada é uma regra de inferência que não é dada a nós como parte do
sistema dedutivo, mas que constitui uma abreviatura usando um teorema previamente provado.
80
Em particular, suponha que tenhamosΓ�α comΓ= {γ1, . . . ,γk } um conjunto finito de teoremas.
Então sempre que deduzimos, digamos numa prova de Σ � β, os teoremas de Γ, podemos usar
Γ�α para deduzir α. Assim, acrescentamos a regra
γ1, . . . ,γk
α
à nossa lista de regras de inferência. O teoremas acima nos dão várias regras derivadas, todas já
conhecidas do cálculo porposicional e que agora valem para fórmulas da lógica de predicados.
Vejamos algumas regras de inferência derivadas dos “novos” axiomas.
Teorema 24 (Instanciação universal (IU)). ∀xα� [α]tx , para todo termo t admissível para x.
Demonstração. Segue do Teorema da Dedução em (A12). ■
Teorema 25 (Generalização universal (G)). α�∀xα, se x �∈V L(α).
Demonstração. Segue do Teorema da Dedução em (A13). ■
Teorema 26 (Generalização existencial (GE)). [α]tx �∃xα, se t é admissível para x.
Prova. Provaremos � [α]tx →∃xα, se t é admissível para x; o teorema segue do teorema da De-
dução. Seja t uma substituição admissível para x em α.
1. ∀x¬α→¬[α]tx (A12)
2. (∀x¬α→¬[α]tx ) → (¬¬[α]t
x →¬∀x¬α) (CP1)
3. ¬¬[α]tx →¬∀x¬α (MP 1,2)
4. [α]tx →¬¬[α]t
x (DN2)
5. [α]tx →¬∀x¬α (SH 3,4)
6. [α]tx →∃xα (def. de ∃)
■
Teorema 27. �∀xα→∃xα
Prova. Fixado t admissível para x em α
1. ∀xα→ [α]tx (A12)
2. [α]tx →∃xα (GE)
3. ∀xα→∃xα (SH 1,2)■
Com a notação usual temos as seguintes regras derivadas dos teoremas acima.
(RA):α→β,α→¬β
¬α (IC):α,β
α∧β
81
(EC1):α∧βα
(EC2):α∧ββ
(ID1):α
α∨β
(ID2):β
α∨β
(DS):α,¬αβ
(MT):α→β,¬β
¬α
(SH):α→β,β→ γ
α→ γ
(TC):θ→ (φ→ ξ)
φ→ (θ→ ξ)
(CP1):α→β
¬β→¬α
(CP2):¬β→¬αα→β
(DN1):¬¬αα
(DN2):α
¬¬α
(G):α
∀xα, se x �∈V L(α).
(IU):∀xα
[α]tx
, se t admissível para x.
(GE):[α]t
x
∃α , se t admissível para x.
(∀/∃):∀xα
∃xα
Metateorema 70 (Teorema da Generalização). Seja Γ tal que a variável x não ocorre livre em
nenhuma fórmula de Γ. Se Γ�α então Γ�∀xα.
Demonstração. Suponha que Γ�α e seja ⟨θ1, . . . ,θn⟩ uma prova. Demonstraremos por indução
em i que Γ�∀x θi .
Se θ1 é axioma lógico então ∀x θ1 é axioma lógico, portanto Γ�∀x θ1.
Se θ1 ∈ Γ então x �∈V L(θ1) e podemos usar o esquema (A13) como em
1. θ1 (hip.)
2. θ1 →∀x θ1 (A13)
3. ∀x θ1 (MP 1,2)
Portanto, θ1 �∀x θ1 e por monotonicidade Γ�∀x θ1.
Assuma, como hipótese da indução, que Γ � ∀x θi para i = 1,2, . . . ,m − 1. Vamos provar Γ �∀x θm . Se θm é axioma lógico ou está em Γ então Γ�∀x θm (a demonstração é análoga ao caso
i = 1). Senão, existem j ,k < m tais que θm é modus ponens de θ j (na linha j ) e θ j → θm (na linha
k). Por hipótese de indução temos
Γ�∀x θ j e Γ�∀x (θ j → θm) (9)
agora
82
1. ∀x θ j (hip.)
2. ∀x (θ j → θm) (hip.)
3. ∀x (θ j → θm) → (∀x θ j →∀x θm) (A11)
4. ∀x θ j →∀x θm (MP 2,3)
5. ∀x θm (MP 1,4)
portanto ∀x θ j ,∀x (θ j → θm) �∀x θm e da regra do corte com (9) concluímos Γ�∀x θm .
Portanto Γ�∀x θi para todo i , 1 ≤ i ≤ n, em particular, Γ�∀xα. ■
Por exemplo, se x não ocorre livre em α
� (α→∀xβ) →∀x(α→β).
De fato, temos α→∀xβ�∀x(α→β)
1. α→∀xβ (hip.)
2. ∀xβ→β (A13)
3. α→β (SH 1,2)
4. ∀x(α→β) (TG)
Também, se x não ocorre livre em α
�∀x(α→β) → (α→∀xβ)
Prova.1. ∀x(α→β) (hip.)
2. ∀x(α→β) → (∀xα→∀xβ) (A11)
3. ∀xα→∀xβ (MP 1,2)
4. α→∀xα pois x �∈V L(α) (A13)
5. α→∀xβ (SH 3,4)■
portanto, se x não ocorre livre em α
� (α→∀xβ) ↔∀x(α→β).
Prova.1. ∀x(α→β) → (α→∀xβ) (teo.)
2. (α→∀xβ) ↔∀x(α→β) (teo.)
3. ∀x(α→β) → (α→∀xβ) ∧ (α→∀xβ) ↔∀x(α→β) (IC 1,2)
4. ∀x(α→β) ↔ (α→∀xβ) (def. ↔)■
Metateorema 71 (Teorema da Generalização em constantes). Sejam c uma constante e Γ um
conjunto de fórmulas em uma linguagem de primeira ordem tais que c não ocorre numa fórmula
83
ϕ e Γ�ϕ. Então há uma variável x que não ocorre em ϕ tal que Γ�∀x [ϕ]cx . Além disso, há uma
dedução Γ�∀x [ϕ]cx em que c não ocorre.
Demonstração. Exercício. Dica: seja ⟨θ1, . . . ,θn⟩uma prova deΓ�ϕ. Demonstre que ⟨[θ1]cx , . . . , [θn]c
x⟩é uma prova de Γ � [ϕ]c
x e considere Σ ⊂ Γ o conjunto (finito) de fórmulas que ocorrem nessa
prova. Se x não ocorre em Σ, pode-se usar o teorema de generalização. ■
Corolário 71.1 (regra (IE)). Assuma que a constante c não ocorre em ϕ,ψ,Γ e que Γ, [ϕ]cx � ψ.
Então Γ,∃xϕ�ψ e existe uma prova dessa dedução na qual c não ocorre.
Demonstração. Exercício. Dica: prove que se Γ� [ϕ]cx , e c não ocorre em Γ,ϕ, então Γ�∀xϕ e c
não ocorre nessa dedução. Use a contrapositiva em Γ, [ϕ]cx �ψ. ■
Note que (IE) não afirma ∃xϕ� [ϕ]cx que pode não ser válido.
Há axiomas redundantes. Observamos aqui que os axiomas que estabelecemos para o sistema
dedutivo não é o menor conjunto possível, dentre eles há várias redundâncias. Por exemplo, com
respeito a igualdade, podemos provar a propriedade simétrica (A14) usando os outros axiomas
� (x.= y) → (y
.= x) (10)
Prova.1. x
.= y (hipótese)
2. (x.= y ∧ x
.= x) → (x.= x → y
.= x) (A17)
3. (x.= y ∧ x
.= x) → (x.= x) (A6)
4. ((x.= y ∧ x
.= x) → (x.= x → y
.= x)) → (((x.= y ∧x
.= x) →4. (x
.= x)) → ((x.= y ∧x
.= x) → y.= x)) (A2)
5. ((x.= y ∧ x
.= x) → (x.= x)) → ((x
.= y ∧x.= x) → y
.= x) (MP 3,4)
6. (x.= y ∧x
.= x) → y.= x) (MP 4,5)
7. x.= x (A13)
8. x.= x → (x
.= y → (x.= y ∧x
.= x)) (A4)
9. x.= y → (x
.= y ∧ x.= x) (MP 7,8)
10. x.= y ∧ x
.= x (MP 1,9)
11. y.= x (MP 1,10)
Existem várias axiomatizações da lógica de predicados, uma vez que, para qualquer lógica, há
liberdade na escolha de axiomas e regras de inferência que caracterizam essa lógica. Descreve-
mos aqui um sistema axiomático à Hilbert. Poderíamos ter restringido os 10 primeiros axiomas
aos 3 seguintes
(1) φ→ �ψ→φ
�
84
(2)�φ→ �
ψ→ ξ��→ ��
φ→ψ�→ �
φ→ ξ��
(3)�¬φ→¬ψ�→ �
ψ→φ�
Esses axiomas descrevem a lógica proposicional clássica. Para manipular quantificadores uni-
versais basta
(4) ∀xφ→ [φ]tx onde t é admissível para x em φ
dos três esquemas de axioma lógico que usamos (aqui em outra ordem)
• ∀xφ→ [φ]tx onde t é admissível para x em φ
• ∀x�φ→ψ
�→ �∀xφ→∀xψ�
• φ→∀xφ onde x não é uma variável livre de φ.
os dois últimos são redundante se adotarmos a regra de generalização (G) como regra de infe-
rência primitiva.
Dos esquemas de axioma para a igualdade, basta
(5) x.= x para cada variável x
(6)�x
.= y�→ �
[φ]xz → [φ]y
z�
9.4. Axiomas não lógicos e teorias de primeira ordem. Uma teoria de primeira ordem ou teo-
ria consiste de uma linguagem de primeira ordem e um conjunto Γ de sentenças dessa lingua-
gem. Tais sentenças são os axiomas não lógicos da teoria.
Exemplo 72. Uma linguagem LG para a Teoria dos Grupos tem os símbolos não lógicos: uma
constante, denotada por e, e uma função binária, denotada por ◦. Essa teoria é dada pela lingua-
gem LG e os axiomas não lógicos
(G1) ∀x ((x ◦e.= x)∧ (e ◦ x
.= x));
(G2) ∀x∃y (x ◦ y.= e);
(G3) ∀x∀y∀z (x ◦ (y ◦ z).= (x ◦ y)◦ z).
9.4.1. Axiomas não lógicos da Aritmética. À linguagem LN acrescentamos, além dos axiomas
lógicos, os seguintes axiomas não lógicos da teoria elementar de números
(PA0) ∀x (Sx �= 0)
(PA1) ∀x∀y(Sx.= Sy → x
.= y)
(PA2) ∀x (x +0.= x)
(PA3) ∀x∀y (x +Sy.= S(x + y))
(PA4) ∀x (x ·0.= 0)
(PA5) ∀x∀y (x ·Sy.= (x · y)+x)
85
(PA6) Se ϕ ∈LN com x ∈V L(ϕ), então
�[ϕ]0
x ∧∀x�ϕ→ [ϕ]Sx
x
��→∀xϕ
Notemos que (PA0)–(PA5) são axiomas, i.e. fórmulas da linguagem, enquanto que (PA6) é um
esquema de axioma, é o esquema de axioma da indução. Além desses, os axiomas de ordem
(OA0) ∀x¬(x < 0)
(OA1) ∀x∀y (x < Sy ↔ x < y ∨x.= y)
(OA2) ∀x∀y (x < y ∨x.= y ∨ y < x) .
Exercício 73. Abaixo vamos usar o seguinte teorema
β, α→ γ�α→ (β∧γ) (*)
Solução. Do teorema de dedução e
1. β (hip.)
2. α→ γ (hip.)
3. α (hip.)
4. γ (MP 2,3)
5. β∧γ (IC 1,5)
■
Agora, denotamos por PA o conjunto de fórmulas
PA= {PA0,PA1,PA2,PA3,PA4,PA5,PA6,OA0,OA1,OA2}
e vamos provar usando o esquema de indução que
PA �∀y (0+ y.= y). (11)
cuja prova será feita por indução em y via
�[0+ y
.= y]0y ∧∀y
�0+ y
.= y → [0+ y.= y]Sy
y
��→∀y (0+ y
.= y)
A base da indução para (11) consiste em provar [0+ y.= y]0
y , ou seja, 0+0.= 0.
1. ∀x(x +0 = 0) (PA2)
2. ∀x(x +0 = 0) → 0+0 = 0 (A1I)
3. 0+0 = 0 (MP 1,2)
O passo indutivo para (11) consiste em provar ∀y�0+ y
.= y → [0+ y.= y]Sy
y
�, ou seja, vamos de-
rivar a fórmula ∀y (0+ y.= y → 0+Sy
.= Sy)
86
1. ∀x∀y(x +Sy.= S(x + y)) (PA3)
2. ∀x∀y(x +Sy.= S(x + y)) →∀y(0+Sy
.= S(0+ y)) (A1I)
3. ∀y(0+Sy.= S(0+ y)) (MP 1,2)
4. ∀y(0+Sy.= S(0+ y)) → 0+Sy
.= S(0+ y) (A1I)
5. 0+Sy.= S(0+ y) (MP 4,5)
6. 0+ y.= y → S(0+ y)
.= Sy (A18)
7. 0+ y.= y → (0+Sy
.= S(0+ y)∧S(0+ y).= Sy) (exerc. 73 5,6)
8. (0+Sy.= S(0+ y)∧S(0+ y)
.= Sy) → (0+Sy.= Sy) (A16)
9. 0+ y.= y → 0+Sy
.= Sy (SH 7,8)
10. ∀y (0+ y.= y → 0+Sy
.= Sy) (TG 9)
Feito isso, a conclusão de (11) se dá da seguinte forma.
1. 0+0.= 0 (base)
2. ∀y (0+ y.= y → 0+Sy
.= Sy) (passo)
3. (0+0.= 0)∧∀y (0+ y
.= y → 0+Sy.= Sy) (IC 1,2)
4.�(0+0
.= 0)∧∀y (0+ y.= y → 0+Sy
.= Sy)�→∀y (x + y
.= y +x) (PA6)
5. ∀y (0+ y.= y) (MP 3,4)
Exercício 74. Escreva uma prova formal para
PA�∀y (0+ y.= y +0). (12)
Note que provamos ∀y (0+ y.= 0) e que ∀y (y +0
.= 0) é axioma.
O exercício acima é a base da indução para provar que a soma é comutativa
PA�∀x∀y (x + y.= y +x).
Se provarmos que ∀x�(∀y (x + y
.= y + x)) → [∀y (x + y.= y + x)]Sx
x
�é consequência sintática de
PA então
1. ∀y (0+ y.= y +0) (base)
2. ∀x�(∀y (x + y
.= y +x)) → (∀y (Sx + y.= y +Sx)
�(passo)
3. ∀y (0+ y.= y +0)∧
∀x�(∀y (x + y
.= y + x)) → (∀y (Sx + y.= y +Sx)
�(IC 1,2)
4.�∀y (0+ y
.= y +0)∧∀x�(∀y (x + y
.= y + x)) →(∀y (Sx + y
.= y +Sx)��→∀x(∀y (x + y
.= y + x)) (PA6)
5. ∀x(∀y (x + y.= y + x)) (MP 3,4)
Exercício 75. PA�∀x�(∀y (x + y
.= y + x)) → (∀y (Sx + y.= y +Sx)
�
87
Exercícios.
(79) Para cada uma das fórmulas abaixo determine se é um axioma lógico.
(a) ∀x∀z (x.= y → (x
.= c → x.= y))
(b) x.= y → (y
.= z → z.= x)
(c) ∀z (x.= y → (x
.= c → y.= c))
(d) ∀w∃x (P (w, x) → P (w, w)) →∃x (P (x, x) → P (x, x))
(e) ∀x(∀x (c.= f (x,c) →∀x∀x (c
.= f (x,c))))
(f) (∃x P (x) →∃y ∀zR(z, f (y))) → ((∃xP (x) →∀y¬∀z R(z, f (y))) →∀x¬P (x))
(g) ∀x∃y (¬(y.= x)) →∃y (¬(y
.= 0))
(h) ∀x∃y (¬(x.= y))
(i) ∀x∃y(y < x) →∃y(y < y)
(j) ∀x ((0 < x) → (0 < x + x)) → ((0 < x) →∀x(0 < x +x))
(k) ∀x∀y ((x +1.= 0) → ((y
.= 1) → (x +1.= 0)))
(80) Escreva uma prova para
(a) � (∀x1(R11(x1)∨R1
2(x1))) → (R12(x1)∨R1
1(x1)).
(b) � R11(c1) → (R1
1(c2) → (R11(c1)∧ r 1
1 (c2))).
(c) �∀x1(∀x2(R11(x1) → (R1
1(x2) → R11(x1)))).
(d) {Q(x),∀y (Q(y) →∀z P (z))} �∀x P (x)
(e) � (α→∃xβ) ↔∃x (α→β) se x não ocorre livre em α
(f) � (∀xβ→α) ↔∃x (β→α) se x não ocorre livre em α
(g) � P (y) ↔∀x (x.= y → P (x))
(81) Demonstre as propriedades de �.
(82) Escreva uma prova para PA� S0+SS0.= SSS0 e para PA � 0 < S0.
(83) Escreva uma prova para PA�∀x(0 · x.= 0).
(84) Escreva uma prova para PA�∀x(x.= 0∨∃y(x
.= Sy)).
10. SEMÂNTICA DA LÓGICA DE PREDICADOS
10.1. Estrutura e valoração. Para interpretar as fórmulas de uma linguagem de primeira ordem,
precisamos estabelecer um universo de discurso, também chamado de domínio; os símbolos
funcionais n-ários correspondem à operações n-árias nesse domínio; os símbolos relacionais n-
ários serão interpretados como relações n-árias sobre o domínio e as constantes são elementos
do domínio.
Exemplo 76. Intuitivamente, para
∀x1 R21(x1, x1)
88
se o domínio é N e R21 representa a relação de divisibilidade então a fórmula é verdadeira, nos diz
que “todo número natural é divisível por ele mesmo”. Se o domínio é Z e R21 representa a rela-
ção menor que então a fórmula é falsa, não é verdade que “todo número inteiro é menor que ele
mesmo”.
Para
∃x1 (R21(x2, x1)∧R2
1(x1, x3))
no domínio Z e R21 a relação menor que, também devemos interpretar as variáveis livres x2, x3.
Se interpretamos x2 como 5 e x3 como 8 obtemos a sentença verdadeira “existe um inteiro n tal que
5 < n e n < 8”.
Se interpretamos x2 como 5 e x3 como 6 obtemos a sentença falsa “existe um inteiro n tal que 5 < n
e n < 6”.
Intuitivamente, para a linguagem da teoria dos grupos, exemplo 72, com domínio Z e interpre-
tando a constante e como o 0 ∈ Z e interpretando a operação ◦ como a soma de inteiros temos,
intuitivamente, que os axiomas G1, G2 e G3 são verdadeiros. Por outro lado, com domínio N e
interpretando a constante e como o 1 ∈ Z e interpretando a operação ◦ como a soma de números
naturais o axioma G3 é falso.
Uma interpretação é dada por uma estrutura matemática e uma valoração da varíáveis.
10.2. Estruturas. Uma estrutura E
E= (E ,c1,c2, . . . ,c�,R1, . . . ,Rm ,F1, . . . ,Fn)
é tal que E é um conjunto não vazio, c1,c2, . . . ,c� são alguns (possivelmente nenhum) elementos
tomados de E , R1, . . . ,Rm são relações (possivelmente nenhuma) sobre E e F1, . . . ,Fm operações
sobre E (possivelmente nenhuma) .
O conjunto E é denominado domínio ou universo de E. São estruturas
• B1 = ({0,1},0,1,max,min, ). Aqui max,min têm seus significados habituais no domínio
{0,1}, (x) = 1− x e não há relações ou constantes.
• B2 = (℘(X ),�, X ,∪,∩,�). Aqui X é um conjunto não vazio, ∪ e ∩ têm seus significados
habituais para conjuntos e �(A) = A� é o complemento do A com respeito a X .
• Uma estrutura para os números naturais é (N,0,1,<,+, ·), cujo universo é N e 0,1,<,+, ·têm os seus significados usuais.
• (R,0,1,+, ·) é o corpo dos números reais.
• (N,<) é o conjunto totalmente ordenado dos números naturais.
• (V ,E) com V não vazio e E uma relação binária é um grafo.
89
Se E não contém funções ou constantes, então E também é chamada de estrutura relacional,
como em (N,<) e (V ,E). Se E não tem relações é chamado de estrutura algébrica, como nas
álgebras booleanas B1 e B2 acima e o corpo dos números reais.
Uma estrutura para uma linguagem será formado por um conjunto não-vazio (chamado de do-
mínio ou universo), uma operação n-ária para cada símbolo funcional n-ário da linguagem,
uma relação n-ária para cada símbolo relacional n-ário e um elemento do domínio para cada
constante da linguagem.
Uma estrutura E= �E , (cEi )�i=1, (RE
j )mj=1, (FE
k )nk=1
�para a linguagem L consiste de
(1) um conjunto não vazio E chamado de domínio ou universo;
(2) cada constante c da linguagem corresponde a um elemento cEi de E ;
(3) cada símbolo relacional n-ário R da linguagem corresponde a uma relação n-ária REj em
E (isto é, REj ⊆ E n);
(4) cada símbolo funcional n-ário F corresponde a uma função FE de E n em E (isto é, FE :
E n → E).
Exemplo 77. Consideremos a linguagem LO com símbolo relacional binário < como o único sím-
bolo extralógico.
São estruturas para LO, ou LO-estruturas
(1) (N,<E) com <E= {(a,b) ∈N2 : a +n = b para algum natural n �= 0}.
(2) (Z,≤E) com ≤E= {(a,b) ∈N2 : a +n = b para algum natural n}.
(3) (N,N2).
(4) (℘(R),⊂E). com ⊂E= {(a,b) ∈℘(R)2
: a ⊂ b}.
Exemplo 78. Consideremos a linguagem LN , com os símbolos extralógicos 0, S, <, +, ·, com as
seguintes estruturas.
(1) definimos U= (E ,0U,SU,<U,+U, ·U) onde
• E = {1,2,3}, 0U = 1 e SU = {(1,1), (2,2), (3,3)};
• A relação binária é dada por <U= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)};
• as operações são dadas pelas seguintes tabelas (na linha i coluna j lê-se i +U j
+U 1 2 3
1 1 2 3
2 2 3 1
3 3 1 2
·U 1 2 3
1 1 1 1
2 1 2 3
3 1 3 2
(2) A interpretação usual N = (N,0N,<N,SN,+N, ·N) onde 0N é o número 0 ∈ N; a função
SU :N→N\{0} é dada por SU(n) = n+1, a relação binária é dada por <N= {(a,b) ∈N2 : a+
90
n = b para algum natural n �= 0} e as operações são a soma e produto usuais de números
naturais.
(3) Tomamos para algum conjunto X não vazio a estrutura C= (℘(X ),0C,<N,SC,+C, ·C) onde
0C é o conjunto vazio; a função SU é dada por SU(A) = A�, os operadores +C e ·C são, res-
pectivamente, a união e a interseção de conjuntos e a relação binária <C é definida pela
inclusão ⊂.
Valoração. Uma valoração para uma estrutura E = �E , (cEi )�i=1, (RE
j )mj=1, (FE
k )nk=1
�é uma atribui-
ção v : {x1, x2, . . . } → E . Dados uma estruturaE e uma valoração v , a interpretação de termos sob
a valoração é uma função v̄ que estende a função v a todos os termos da linguagem, conforme
as seguintes condições:
(1) se x é variável, v̄(x) = v(x);
(2) se c é uma constante, v̄(c) = cE;
(3) se F é um símbolo funcional n-ário e t1, . . . , tn são termos, então a interpretação do termo
F (t1, . . . , tn) é dada por v̄(F (t1, . . . , tn)) = FE(v̄(t1), . . . , v̄(tn)).
Exemplo 79. Com a LN -estrutura U do exemplo 78 e com v tal que v(x) = 1 e v(y) = 2 o valor do
termo +(·(0, x), y) é
v̄(+(·(0, x), y)) = +U(·U(v̄(0), v̄(x)), v̄(y))
= +U(·U(0U,1),2)
= +U(·U(1,1),2)
= +U(1,2)
= 2
Para o termo +(x, y) temos o valor
v̄(+(x, y)) =+U(v̄(x), v̄(y)) =+U(1,2) = 2
O valor do termo 1 é v̄(1) = 1U = 2, de modo que a fórmula+(x, y).= 1 é, intuitivamente, verdadeira
na interpretação dada porU com valoração v (a noção de verdade será definida precisamente mais
adiante).
Notemos que
• os números usados como argumentos de v̄ são símbolos da linguagem;
• a imagem de v̄ são objetos do domínio do modelo e, portanto, pertencem à metalingua-
gem.
91
Exercício 80. Intuitivamente, ∀x (+(x, y).= 0) é verdadeira no contexto do exemplo 79?
Exercício 81. Use o exercício 79 para provar que a extensão v̄ de uma valoração v a todos os termos
de uma linguagem é única.
Exercício 82. Use o exercício 79 para demonstrar:
(1) Seja E uma estrutura para a linguagem L . Para todo termo t de L , se v e w duas valora-
ções que coincidem nas variáveis que ocorrem em t, então v̄(t ) = w̄(t ).
(2) Seja (E, v) uma interpretação para uma linguagem L . Suponha que para variáveis x e y
temos que v(x) = v(y). Use indução para termos para demonstrar que se t é termo e s é
obtido de t substituindo-se uma ou mais ocorrências de x por y então v̄(s) = v̄(t ).
Valoração x-variante. Se v é uma valoração na estrutura E, então definimos a valoração [v]x�a ,
para qualquer a no domínio E de E pondo
[v]xi�a(x j ) =
a se j = i
v(x j ) se j �= i .
Por exemplo, se E =N e v(x j ) = j então [v]x3�0 é
[v]x3�0(x j ) =
0 se j = 3
j se j �= 3.
10.3. Satisfazibilidade, valor-verdade e modelo. A ideia por trás da semântica da lógica de pre-
dicados é muito simples. Seguindo Tarski, nós assumimos que uma sentença é verdadeira em
uma estrutura, se esse é realmente o caso.
Sejam L um linguagem de primeira ordem, E e v uma estrutura e uma valoração para a lingua-
gem L , respectivamente, e α uma fórmula de L . Escrevemos
(E, v) �α
para dizer que (E, v) satisfaz α, ou ainda, α é verdadeira na interpretação dada por (E, v). Satis-
fazibilidade é definida recursivamente do seguinte modo:
(1) (E, v) � (t1.= t2) se e só se v̄(t1) = v̄(t2);
(2) (E, v) � R(t1, . . . , tn) se e só se (v̄(t1), . . . , v̄(tn)) ∈ RE;
(3) (E, v) �¬γ se e só se (E, v) �� γ;
(4) (E, v) � γ→β se e só se
(E, v) �¬γ ou (E, v) �β.
(5) (E, v) �∀xβ se e só se
92
para todo a ∈ E , (E, [v]x�a) �β
em que R é um símbolo relacional n-ário da linguagem formal, t1, . . . , tn são termos, x é variável
e γ e β fórmulas da linguagem.
Das abreviaturas adotadas deduzimos que
(6) (E, v) � γ∨β se e só se (E, v) � γ ou (E, v) �β(7) (E, v) � γ∧β se e só se (E, v) � γ e (E, v) �β;
(8) (E, v) �∃xγ se e só se (E, [v]x�a) � γ para algum a ∈ E .
Exemplo 83. Por exemplo, com U do exemplo 78 de domínio {1,2,3} e v tal que v(y) = 2.
(U, v) �∀x (x + y.= 0) sse para todo a ∈ {1,2,3}, (U, [v]x�a) � (x + y
.= 0)
sse para todo a ∈ {1,2,3}, [v]x�a(x + y) = [v]x�a(0)
sse para todo a ∈ {1,2,3}, [v]x�a(x)+U [v]x�a(y) = 1
sse para todo a ∈ {1,2,3}, a +U 2 = 1
o que não é verdadeiro na estrutura pois 2+U 2 = 3, logo a fórmula ∀x (x + y.= 0) não é satisfeita
por essa interpretação, ou seja
(U, v) �� ∀x (x + y = 1).
Exemplo 84. A linguagem para Corpos LF tem símbolos extralógicos 0,1,+, ·. Tomemos a estru-
tura R= (R,0R,1R,+R, ·R) com os significados usuais e valoração v(xn) = n +1. Então
(R, v) �∀x1�(0 · x1
.= x3) → (x3.= 0)
�
pois (R, v) �∀x1�(0 · x1
.= x3) → (x3.= 0)
�
sse para todo a ∈R, (R, [v]x1�a) � �(0 · x1
.= x3) → (x3.= 0)
�
sse para todo a ∈R, (R, [v]x1�a) �¬(0 · x1.= x3) ou (R, [v]x1�a) � (x3
.= 0)
sse para todo a ∈R, (R, [v]x1�a) � (0 · x1 �= x3) ou (R, [v]x1�a) � (x3.= 0)
sse para todo a ∈R, [v]x1�a(0 · x1) �= [v]x1�a(x3) ou [v]x1�a(x3) = [v]x1�a(0)
sse para todo a ∈R, [v]x1�a(0) ·R [v]x1�a(x1) �= [v]x1�a(x3) ou [v]x1�a(x3) = [v]x1�a(0) =sse para todo a ∈R, 0R·Ra �= 4 ou 4 = 0R
isto é, o modelo satisfaz a fórmula se, e somente se, 0 �= 4 ou 4 = 0 em R. Portanto a interpretação
fornecida pela estrutura e pela valoração satisfaz a fórmula.
Exemplo 85. Em LO (símbolo extralógico <), considere a estrutura Q = (Q,<Q) com <Q o menor
usual e seja v uma valoração qualquer. Então
93
(1) (Q, v) �∀x1 (∃x2 (x1 < x2)) e
(2) (Q, v) �∃x3 (∃x4 (x3 < x4 → x3 = x4))
(Q, v) �∀x1 (∃x2 (x1 < x2))
sse para todo a ∈Q, (Q, [v]x1�a) �∃x2 (x1 < x2)
sse para todo a ∈Q, para algum b ∈Q, (Q, [v]x1�ax2�b
) � x1 < x2
sse para todo a ∈Q, para algum b ∈Q, [v]x1�ax2�b
(x1) <Q [v]x1�ax2�b
(x2)
sse para todo a ∈Q, para algum b ∈Q, a < b
o que é verdadeiro na estrutura.
Agora, (Q, v) �∃x3 (∃x4 (x3 < x4 → x3.= x4))
sse para algum a ∈Q, (Q, [v]x3�a) �∃x4 (x3 < x4 → x3.= x4)
sse para algum a ∈Q, para algum b ∈Q, (Q, [v]x3�ax4�b
) � (x3 < x4 → x3.= x4)
sse para algum a ∈Q, para algum b ∈Q, (Q, [v]x3�ax4�b
) �¬(x3 < x4) ou � (Q, [v]x3�ax4�b
)(x3.= x4)
sse para algum a ∈Q, para algum b ∈Q, [v]x3�ax4�b
(x3) ≥Q [v]x3�ax4�b
(4) ou [v]x3�ax4�b
(x3) = [v]x3�ax4�b
(x4)
sse para algum a ∈Q, para algum b ∈Q, a ≥Q b ou a = b
que é verdadeiro na estrutura.
Exemplo 86. Para qualquer (M, v), se a variável x não ocorre no termo t então
(M, v) �∃x (x.= t ).
(M, v) �∃x (x = t ) sse para algum a ∈ M , (M, [v]x�a) � (x.= t )
sse para algum a ∈ M , [v]x�a(x) = [v]x�a(t )
sse para algum a ∈ M , a = [v]x�a(t )
que é verdade pois, da definição, [v]x�a(t ) ∈ M e [v]x�a(t ) = v̄(t ) pois x não ocorre em t. Portanto,
(M, v) �∃x (x = t ).
10.3.1. Valor-verdade com respeito a uma valoração. Para cada fórmula α atribuímos um valor-
verdade v̂(α) ∈ {0,1} de acordo com a interpretação (E, v) que é definido recursivamente por
(1) v̂(s.= t ) = 1 sse v̄(s) = v̄(t );
(2) v̂(R(t1, . . . , tn)) = 1 sse (v̄(t1), . . . , v̄(tn)) ∈ RE;
(3) v̂(¬α) = 1 sse v̂(α) = 0;
(4) v̂(β→ γ) = max{1− v̂(β), v̂(γ)};
94
(5) v̂(∀xα) = mina∈E �[v]x�a(α).
Metateorema 87. Sejam E uma estrutura para uma linguagem L . Para toda fórmula α ∈L , se
v e w são valorações tais que v(y) = w(y), para toda variável y que ocorre livre em α, então
(E, v) �α se, e somente se, (E, w) �α.
Corolário 87.1. Se α é uma sentença de L e E é uma estrutura para L , então E�α ou E�¬α.
Demonstração do Teorema. A demonstração é por indução na fórmula α.
O teorema vale para fórmulas atômicas: se α é da forma t1.= t2, então toda variável da fórmula é
livre portanto v̄(t1) = w̄(t1) e v̄(t2) = w̄(t2) de modo que
(E, v) �α se, e somente se, (E, w) �α.
Se α é da forma R(t1, . . . , tn), então toda variável da fórmula é livre portanto v̄(ti ) = w̄(ti ) para
todo i de modo que (v̄(t1), . . . , v̄(tn)) = (w̄(t1), . . . , w̄(tn)) portanto (v̄(t1), . . . , v̄(tn)) ∈ RE se, e só
se, (w̄(t1), . . . , w̄(tn)) ∈ RE logo
(E, v) �α se, e somente se, (E, w) �α.
Se o teorema vale para α então vale para ¬α: se
(E, v) �α se, e somente se, (E, w) �α
então
(E, v) ��α se, e somente se, (E, w) ��αportanto
(E, v) �¬α se, e somente se, (E, w) �¬α.
Se o teorema vale para α e β então vale para α→β:
(E, v) �α→β sse
(E, v) �¬α ou (E, v) �β sse
(E, w) �¬α ou (E, w) �β sse
(E, w) �α→β
portanto
(E, v) �α→β se, e somente se, (E, w) �α→β
Se o teorema vale para α então vale para ∀xα: suponha (E, v) � ∀xα. Fixado um b ∈ E , temos
que (E, [v]x�b) �α. Agora, se y é uma variável livre em α e y �= x então
[v]x�b(y) = [w]x�b(y)
95
pois v(y) = w(y); se y = x
[v]x�b(y) = [w]x�b(y) = b.
Portanto, (E, [w]x�b) �α pois o teorema vale paraα. Como b é arbitrário, o argumento vale para
todo b, ou seja,
(E, w) �∀xα.
A recíproca (se (E, w) �∀xα então (E, v) �∀xα) é demonstrada com argumentação análoga.
Pelo Princípio da Indução para fórmulas, o Teorema vale para toda fórmula de L . ■
Demonstração do corolário. Seja α uma sentença e E uma estrutura.
Se E �� α então, para algum v , (E, v) �� α. Assim, para alguma valoração v , (E, v) � ¬α. Como α
não tem variáveis livres (E, w) �¬α, para qualquer valoração w . Portanto E�¬α. A recíproca é
análoga. ■
10.3.2. Modelo. Dizemos que a estrutura E é uma modelo para α se
(E, v) �α para todo v
e então escrevemos
E�α.
Dizemos que α é verdadeira na interpretação E se esse é um modelo para α; se nenhuma valo-
ração de E satisfaz α, dizemos que α é falsa na interpretação E.
Observemos que
• uma fórmula não pode ser verdadeira e falsa num modelo;
• se for verdadeira num modelo então a negação será falsa no mesmo modelo;
• uma fórmula com variáveis livres pode não ser nem verdadeira e nem falsa num modelo.
Agora, se vale
(E, v) �α para todo (E, v)
então α é uma tautologia, ou uma verdade lógica, e escrevemos
�α
como, por exemplo, em �∀x (x.= x).
Exemplo 88. � ∀x (x.= x) sse para quaisquer M e v vale (M, v) � ∀x (x
.= x) sse para todo a no
domínio do modelo (M, [v]x�a) � (x.= x).
96
Mas [v]x�a(x) = [v]x�a(x) para qualquer valoração v e qualquer a no domínio M, portanto
(M, [v]x�a) � (x = x).
Exercício 89. Verifique que �∀x ∃y (x.= y).
Exemplo 90. Seja D uma estrutura cujo domínio D tenha pelo menos dois elementos. Então
D�∀x ∃y (x �= y).
De fato, seja a ∈ D um elemento arbitrário. Como D tem pelo menos 2 elementos
dado a ∈ D, podemos escolher b ∈ D com b �= a de modo que (E, [v]x�a,y�b) � x �= y.
Como a foi arbitrário (E, v) �∀x ∃y (x �= y).
Exemplo 91. No exemplo 85
(1) Q �∀x1 (∃x2 (x1 < x2)).
(2) Q �∃x3 (∃x4 (x3 < x4 → x3.= x4)).
Notemos que enquanto para qualquer interpretação (E, v) temos que (E, v) � α ou (E, v) � ¬αpara qualquer fórmula α, no caso de modelo temos E � α ou E � ¬α somente para sentenças,
como provamos a seguir. Lembremos que fórmula α sem ocorrência de variáveis livre é dita
sentença.
Exemplo 92. A sentença ∀x∀y (x.= y) é falsa em qualquer modelo com pelo menos dois elementos
pois, fixado (M, v), se não for falsa nesse modelo, então será verdadeira e se esse é o caso (M, v) �∀x∀y (x
.= y) sse (M, [v]x�a,y�b) � x = y para todo a e todo b. Se o modelo tem pelo menos dois
elementos então podemos tomar a e b distintos, o que torna a sentença falsa.
Exercício 93. Demonstre usando indução para fórmula que se t é uma substituição admissível
para x em α então
(M , v) � [α]tx sse (M , [v]x�v̄(t )) �α.
Exercício 94. Verifique que os axiomas do sistema de Kleene são verdades lógicas.
10.4. Consequência lógica e equivalência semântica. Sejam L uma linguagem, (E, v) uma es-
trutura para L e Γ⊂L um conjunto de fórmulas. Escrevemos
(E, v) � Γ
e dizemos que (E, v) satisfaz Γ, se e só se,
(E, v) �α para todo α ∈ Γ.
97
Numa linguagem L a fórmula α é consequência lógica (ou consequência semântica) de Γ, e
escrevemos
Γ�αse para todo (E, v) tal que (E, v) � Γ tem-se (E, v) �α.
Exemplo 95. {α,α→β} �β
Se (E, v) � {α,α→β} então (E, v) �α e (E, v) �α→β ou seja
(1) (E, v) �α e
(2) (E, v) �¬α ou (E, v) �β
mas (E, v) �¬α se, e só se, (E, v) ��α, portanto (E, v) �β.
Exercício 96. {∀xα,∀xα→β} �∀xβ
Exercício 97. ∀xα� [α]tx sempre que a substituição é admissível.
Metateorema 98. Sejam Γ um conjunto de fórmulas e α e β fórmulas, todos de uma linguagem
L .
Γ,α�β se, e só se, Γ�α→β.
Demonstração. Assumimos a hipótese que Γ,α�β e provaremos Γ�α→β.
Se (E, v) � Γ temos
(1) (E, v) �α: nesse caso, pela hipótese, (E, v) �β; ou
(2) (E, v) ��α: nesse caso, por definição (E, v) �¬α.
porém, (E, v) �β ou (E, v) ��α sse (E, v) �α→β,
Portanto, Γ�α→β.
Agora, assumimos que Γ�α→β e provaremos Γ,α�β.
Se (E, v) � Γ∪ {α} então (E, v) �α→β. Pela consequência do exemplo anterior acima (E, v) �β.
Portanto, Γ,α�β. ■
Numa linguagem L α é semanticamente equivalente a β
α≡β
se
{β} �α e {α} �βequivalentemente
(E, v) �α sse (E, v) �β
98
para qualquer interpretação (E, v)
Exemplo 99.
∀x∀yα≡∀y∀xα
∀x(α∧β) ≡∀xα∧∀xβ
∃x∃yα≡∃y∃xα
∃x(α∨β) ≡∃xα∨∃xβ
¬(∀xα) ≡∃x¬α¬(∃xα) ≡∀x¬α
Exercício 100. Prove que α≡β é equivalente a �α↔β.
10.4.1. A teoria de uma estrutura. Se M é uma estrutura para a linguagem L , então a teoria de
M é o conjunto de todas as sentenças de L verdadeiras em M, ou seja
Th(M) = {τ : τ é uma sentença e M� τ}.
Exercícios.
(1) Na linguagem da aritmética LN com a estrutura canônica N e valoração v(x) = 2
(a) Verifique que (N, s) � x =+(1,1).
(b) Diga para quais valorações a seguinte fórmula é verdadeira: (∃x(x+x = y)) → (∃y(y+x = y))
(2) Seja L uma linguagem de primeira ordem com constante a, função unária G , relação
unária R e relações binárias {P,Q}. Seja A a estrutura definida por
• D :=N• aA := 2;
• GA(n) := n +1;
• RA(n) := {n ∈N : n é par};
• PA := {(n,m) ∈N×N : n ≤ m};
• QA =�.
Para cada uma das proposições, indique se é verdadeira ou falsa na estrututra.
(a) ¬R(a) →∀x∀yQ(x, y); (b) ∀x(R(x) →∀xR(G(G(x)));
(3) Seja LF a linguagem dos corpos com constantes 0 e 1, símbolos funcionais + e ·. Chama-
remos de axiomas de corpo o seguinte conjunto de sentenças da linguagem LF :
(C1) 0 �= 1;
(C2) ∀x (x +0 = x);
(C3) ∀x ((x �= 0) → (x ·1 = x));
(C4) ∀x∀y (x + y = y +x);
(C5) ∀x∀y (x · y = y ·x);
(C6) ∀x∀y∀z ((x + y)+ z = x + (y + z));
99
(C7) ∀x∀y∀z ((x · y) · z = x · (y · z));
(C8) ∀x∃y (x + y = 0);
(C9) ∀x ((x �= 0) →∃y (x · y = 1));
(C10) ∀x∀y∀z (x · (y + z) = (x · y)+ (x · z).
(3.1) Considere a estrutura U do exemplo proposto em aula (E = {1,2,3}). Mostre
que U satisfaz todos os axiomas de corpo.
(3.2) Considere a estrutura do exercício anterior e v uma valoração satisfazendo
v(x) = 1, v(y) = 2 e v(z) = 3. Verifique quais das seguintes fórmulas abaixo são verda-
deiras na interpretação (U, v)
(a) x + y = 0; (b) ∀y((y �= 0) → (y · x =y));
(c) ∀x(x ·0 = 0);
(3.3) Para cada fórmula α contendo variáveis livres do exercício anterior, considere
o fecho universal de α a sentença ∀x∀y∀z(α). Verifique se essas sentenças são verda-
deiras no modelo N do exercício 3.1.
(3.4) Verifique que a estrutura R= (R,0,1,+, ·) satisfaz os axiomas de corpo.
(4) Seja LG a linguagem dos grupos com constante e e símbolo funcional ◦ e axiomas
(G1) ∀x ((x ◦e = x)∧ (e ◦x = x));
(G2) ∀x∃y (x ◦ y = e);
(G3) ∀x∀y∀z (x ◦ (y ◦ z) = (x ◦ y)◦ z).
(a) Seja α a sentença ∀x (x ◦x = e).
Mostre que a sentença α é independente dos axiomas de grupo mostrando uma
interpretação para {G1,G2,G3,α} e outra interpretação para {G1,G2,G3,¬α}.
(b) Tome G a seguinte estrutura para LG
• D := {1,2};
• eG := 1;
•◦G 1 2
1 1 2
2 2 1Verifique se os axiomas são verdadeiros nesse modelo.
(5) Justifique as equivalências
∀x(φ∧ψ) ≡ ∀xφ∧∀xψ
∃xφ∨∃xψ ≡ ∃x(φ∨ψ)
∀x∀yϕ ≡ ∀y∀xϕ
∃x∃yϕ ≡ ∃y∃xϕ
100
(6) Considere a linguagem de primeira ordem com o predicados unários r, p, o predicado
binário q , as constantes a,b,c e os símbolos funcionais f e g , unário e binário, respecti-
vamente.
(a) Indentifique quas das expressões a seguir são fórmulas:
(i) r (a);
(ii) r ( f );
(iii) r (g (x, f (a)))∧ r ( f (y)) → x = y ;
(iv) r (x) →∀y(t (y));
(v) ∀x(∃y(r ( f (x)) →¬r (g (y, x))))
(b) Considere a estrutura E dada por
• E = {1};
• r E = pE = {1} ;
• qE = {(1,1)} ;
• aE = bE = cE = 1;
• f E : E → E , f E (x) = 1;
• g E : E ×E → E , g E (x, y) = x.
Verificar se as sentenças a seguir são verdadeiras
(i) ∀x1(∃x2(q(x1, x2) → (r (x2)∧ (x1 = g (x2,c))))).
(ii) ∀x(r (x));
(iii) ∀x(r (x) → r (x));
(iv) ∀x(q(x, x) → q(x, x));
(v) ∃x(p( f (x)) → r (x));
(c) Construa, se possível, uma estrutura para cada sentença ϕ acima de modo que E ��ϕ.
(7) Podemos dividir as fórmulas de uma linguagem de primeira ordem L em
primitiva: formada pelas fórmulas atômicas de L e as fórmulas da forma ∀xα de L .
Denote por V P o conjunto das fórmulas primitivas.
não-primitiva: formada pelas fórmulas da forma ¬α de L e as fórmulas da forma
α∧β e α∨β de L (os outros conectivos são abreviações).
Assim, qualquer fórmula de L é construída a partir das fórmulas primitivas pelas ope-
rações de negação, conjunção e disjunção.
Agora, considerando a Lógica Proposicional e tomando para as variáveis proposici-
onais as fórmulas primitivas do conjunto V P temos que as fórmulas da linguagem L
também são fórmulas da Lógica Proposicional.
Por exemplo, (∀y ¬P (y) →¬P (x)) → (P (x) →¬∀y ¬P (y)) é uma tautologia proposici-
onal
101
∀y ¬P (y) P (x) ¬∀y ¬P (y) ¬P (x) (∀y ¬P (y) →¬P (x)) → (P (x) →¬∀y ¬P (y))
0 0 1 1 1
0 1 1 0 1
1 0 0 1 1
1 1 0 0 1
Por outro lado, ∀x(P (x) → P (x)) não é tautologia (é uma fórmula atômica proposicio-
nal).
(a) Justifique que ∀x P (x) � P (a) na semântica dos predicados mas que ∀x P (x) �� P (a)
na semântica das proposições.
(b) Dado (M , v) para L defina uma interpretação (da lógica proposicional)
v : V P → {0,1}
que atribui um valor-verdade para cada fórmula primitiva pondo
v(α) = 1 sse (M , v) �α.
Demonstre que a (única) valoração V : L → {0,1} que estende v satisfaz
V (α) = 1 sse (M , v) �α.
(c) Use o exercício anterior para provar que se
Γ�α na semântica proposicional
então
Γ�α na semântica dos predicados.
Vale a recíproca?
