Lógica Computacional 1 - Notas de aula do Professor Flávio

Prévia do material em texto

Lo´gica Computacional 1
Fla´vio L. C. de Moura
9 de Novembro de 2011
Calenda´rio de Aulas
1. 17.10.2011 -
2. 19.10.2011 -
3. 24.10.2011 -
4. 26.10.2011 -
5. 31.10.2011 -
6. 02.11.2011 - Feriado
7. 07.11.2011 -
8. 09.11.2011 -
9. 14.11.2011 - Na˜o havera´ aula
10. 16.11.2011 -
11. 21.11.2011 -
12. 23.11.2011 -
13. 28.11.2011 -
14. 30.11.2011 -
15. 05.12.2011 -
16. 07.12.2011 -
17. 12.12.2011 -
2
Cap´ıtulo 1
Induc¸a˜o Matema´tica
O princ´ıpio de induc¸a˜o nos permite provar propriedades sobre os nu´meros naturais. Como
exemplo provaremos que
1 + 2 + . . .+ n =
n(n+ 1)
2
(1.1)
Conta-se que uma professora de matema´tica, na tentativa de obter sileˆncio na classe e ocupar
seus alunos, propoˆs que os mesmos calculassem o resultado da soma dos nu´meros naturais de 1 a
100. Entre seus alunos estava o (futuro) famoso matema´tico alema˜o Karl Friedrich Gauss (1777-
1855) com enta˜o 8 anos de idade, que resolveu o problema em poucos segundos! Como Gauss fez
isto? Sera´ que ele conhecia a fo´rmula acima? Observe o seguinte padra˜o:
1 + 2 + 3 + . . . + 98 + 99 + 100
100 + 99 + 98 + . . . + 3 + 2 + 1
101 + 101 + 101 + . . . + 101 + 101 + 101
Assim temos 100 parcelas iguais a 101, ou seja, o resultado da soma e´ igual a
100 ∗ 101
2
= 5050
ja´ que a soma desejada esta´ sendo computada duas vezes. Enta˜o, para n = 100, a equac¸a˜o (1.1)
e´ verdadeira. Como garantir que esta equac¸a˜o e´ sempre verdadeira? Ou seja, como garantir
que a equac¸a˜o (1.1) e´ correta para qualquer natural n? Resposta: com o princ´ıpio de induc¸a˜o
matema´tica.
Para provar que uma propriedade M sobre os naturais e´ va´lida precisamos de duas coisas:
1. Base da Induc¸a˜o (BI): O nu´mero 0 satisfaz a propriedade, isto e´, precisamos de uma prova
de M(0);
2. Passo Indutivo (PI): Assumindo que o natural n satisfac¸a a propriedadeM podemos provar
que n+ 1 tambe´m satisfaz a propriedade, isto e´, temos uma prova de M(n)→M(n+ 1).
Este princ´ıpio e´ tambe´m conhecido com o princ´ıpio da induc¸a˜o finita.
O Princ´ıpio da Induc¸a˜o Finita: Primeira Forma
Formalmente definimos o princ´ıpio de induc¸a˜o da seguinte forma:
Definic¸a˜o 1. Seja P (n) uma propriedade associada aos nu´meros naturais. Em outras palavras, P
e´ um predicado una´rio cujo argumento e´ um nu´mero natural, e suponhamos que:
3
(a) Base da Induc¸a˜o (BI): P (0) e´ verdadeira;
(b) Passo Indutivo (PI): para todo nu´mero natural n, se P (n) e´ verdadeira enta˜o P (n + 1) e´
verdadeira.
Nestas condic¸o˜es, a propriedade P (n) e´ verdadeira para todo nu´mero natural n.
Esquematicamente o princ´ıpio de induc¸a˜o pode ser representado da seguinte forma:
[BI + PI] ⇒ ∀n, P (n).
O Princ´ıpio da Induc¸a˜o Finita Generalizado
Definic¸a˜o 2 (Princ´ıpio da Induc¸a˜o Finita Generalizado). Seja P (n) uma propriedade referente a
nu´meros naturais que satisfaz as seguintes condic¸o˜es:
1. (BI): O nu´mero natural m satisfaz a propriedade P ;
2. (PI): Se um nu´mero natural n satisfaz a propriedade P enta˜o seu sucessor tambe´m satisfaz
a propriedade P .
Enta˜o todos os nu´meros naturais maiores ou iguais a m satisfazem a propriedade P .
Vamos enta˜o retornar ao nosso problema inicial: provar que a equac¸a˜o (1.1) e´ verdadeira para
qualquer nu´mero natural. Seja P (n) a propriedade que expressa a seguinte ide´ia:
P (n) : 1 + 2 + . . .+ n =
n(n+ 1)
2
A base de induc¸a˜o corresponde a asserc¸a˜o: (BI) P (1) : 1 =
1(1 + 1)
2
, que e´ trivialmente verdadeira.
Para provarmos o (PI), assumimos que P (n) e´ uma proposic¸a˜o verdadeira, e precisamos mostrar
que P (n+ 1) tambe´m e´ verdadeira. Em outras palavras, se a igualdade
1 + 2 + . . .+ n =
n(n+ 1)
2
e´ verdadeira para um n fixo enta˜o 1 + 2 + . . .+ n+ (n+ 1) =
(n+ 1)((n+ 1) + 1)
2
tambe´m vale.
De fato,
1 + 2 + . . .+ n+ (n+ 1) =
n(n+ 1)
2
+ (n+ 1) =
n(n+ 1) + 2(n+ 1)
2
=
(n+ 1)(n+ 2)
2
, que por sua vez corresponde a P (n+ 1).
Logo, P (n+ 1) e´ verdadeiro, e portanto P (n) e´ verdadeira para todo n ≥ 1.
Como outro exemplo, considere a seguinte afirmac¸a˜o: 2n + 1 < 2n, para n ≥ 3. Para n = 3
(BI), a desigualdade e´ verdadeira pois 7 < 8. Para mostrarmos o (PI) assumimos que 2n+1 < 2n,
e vamos tentar concluir que 2(n + 1) + 1 < 2n+1. De fato, 2(n + 1) + 1 = (2n + 1) + 2 < 2n + 2,
onde a u´ltima desigualdade e´ obtida aplicando-se a hipo´tese de induc¸a˜o. Para n ≥ 3, temos que
2n + 2 < 2n + 2n = 2n+1, e portanto 2(n+ 1) + 1 < 2n+1 como quer´ıamos concluir.
4
Princ´ıpio da Induc¸a˜o Forte
Teorema 1. Seja P uma propriedade referente aos nu´meros naturais. Dado n ∈ N, se a validade
de P para todo nu´mero natural menor do que n implicar que P e´ verdadeira para n, enta˜o P e´
verdadeira para todos os nu´meros naturais.
Prova. Este teorema e´ uma consequeˆncia imediata da seguinte afirmac¸a˜o:
Um conjunto X ⊂ N com a propriedade (I) a seguir coincide com N.
(I) Dado n ∈ N, se todos os nu´meros naturais menores do que n pertencem a X, enta˜o n ∈ X.
�
Leitura recomendada: O Princ´ıpio da Induc¸a˜o - Elon Lages Lima.
Dispon´ıvel em http://www.obm.org.br/opencms/revista eureka/lista.html
Exerc´ıcios
1. Prove:
(a) n2 < 2n, para n ≥ 5.
(b) n! > 2n, para n ≥ 4.
(c) Para todo nu´mero natural n, 3 divide n3 − n.
(d) Demonstre que a soma dos n primeiros nu´meros ı´mpares e´ igual a n2.
(e) 12 + 22 + . . .+ n2 =
n(n+ 1)(2n+ 1)
6
(f) O conjunto {an|n ∈ N} e´ definido por:
a0 := 0
a1 := 1
ai+2 := 2ai+1 − ai (i ∈ N).
Encontre uma fo´rmula geral para an e prove a correc¸a˜o de sua afirmac¸a˜o.
(g) O conjunto {an|n ∈ N} e´ definido por:
a0 := 0
a1 := 4
ai+2 := 4(ai+1 − ai) (i ∈ N).
Prove que, para todo n, an = n.2
n+1.
2. Resolva os exerc´ıcios 8, 13, 14, 15, 17, 20 e 21 da leitura recomendada.
5
6
Cap´ıtulo 2
A Sintaxe da Lo´gica Proposicional
Linguagens naturais vs. Linguagens formais
Linguagens naturais, como o Portugueˆs ou o Ingleˆs, sa˜o suscet´ıveis a ambiguidades:
A ma˜e observou o filho em seu quarto.
Esta e´ uma das razo˜es pelas quais o estudo da lo´gica matema´tica e computacional utiliza uma
linguagem formal.
Mas o que e´ Lo´gica?
• Mendelson: “Lo´gica e´ a ana´lise de me´todos de racioc´ınio.”
• Mortari: “Lo´gica e´ a cieˆncia que estuda princ´ıpios e me´todos de infereˆncia, tendo o objetivo
principal de determinar em que condic¸o˜es certas coisas se seguem (sa˜o consequeˆncia), ou na˜o,
de outras.”
• Como veremos neste curso, “a Lo´gica esta´ interessada principalmente na forma e na˜o no
conteu´do dos argumentos.” (Souza)
Neste curso estudaremos basicamente duas lo´gicas:
1. Lo´gica proposicional;
2. Lo´gica de predicados (ou lo´gica de primeira ordem).
A Sintaxe da Lo´gica Proposicional
A lo´gica proposicional e´ baseada na noc¸a˜o de proposic¸a˜o. Entendemos por proposic¸a˜o como sendo
qualquer expressa˜o que possa ser qualificada como verdadeira ou falsa.
Exemplos de proposic¸o˜es:
1. O nu´mero 2 e´ par.
2. O conjunto dos nu´meros reais e´ enumera´vel.
3. Se a oferta de morangos aumentar enta˜o o seu prec¸o vai diminuir.
Na˜o sa˜o proposic¸o˜es:
7
1. Qual e´ o seu nome?
2. Feche a porta!
Algumas proposic¸o˜es sa˜o minimais (ou atoˆmicas) no sentido que na˜o existe uma parte menor
dela que ainda seja uma proposic¸a˜o. Por exemplo,
• 2 ∈ {1, 3, 5}
• O nu´mero 2 e´ par.
Proposic¸o˜es mais complexas sa˜o podem ser constru´ıdas a partir de proposic¸o˜es atoˆmicas por
meio de conectivos:
• 2 e´ um nu´mero par e √2 e´ um nu´mero racional.
• Se 2+2=5 enta˜o hoje e´ dia 10.
• 2 e´ um nu´mero par ou √2 e´ um nu´mero racional.
Para o estudo da Lo´gica Proposicional (e tambe´m da Lo´gica de Primeira Ordem) considerare-
mos dois aspectos: o sinta´tico e o semaˆntico. A sintaxe de uma linguagem nos permite conhecer
as expresso˜es bem formadas,enquanto que a semaˆntica se refere ao seu significado. Por exem-
plo, a palavra “lo´jica” na˜o e´ uma expressa˜o bem formada do Portugueˆs de acordo com as regras
gramaticais desta linguagem.
A representac¸a˜o simbo´lica da lo´gica e´ feita utilizando-se um alfabeto.
Definic¸a˜o 3 (Alfabeto da Lo´gica Proposicional). O alfabeto da lo´gica proposicional e´ definido por:
(a) S´ımbolos de pontuac¸a˜o: “(” e “)”;
(c) Um conjunto enumera´vel de s´ımbolos proposicionais: p0, p1, p2, . . .
(d) Conectivos lo´gicos:
– de aridade zero: ⊥;
– una´rio: ¬;
– bina´rios: ∧, ∨, →, ↔.
Os s´ımbolos proposicionais e ⊥ constituem proposic¸o˜es indivis´ıveis que chamaremos de a´tomos ou
proposic¸o˜es atoˆmicas.
As fo´rmulas da lo´gica proposicional sa˜o cadeias de s´ımbolos (strings) do alfabeto definidas
indutivamente. Conjuntos indutivos sa˜o particularmente importantes tanto em Matema´tica quanto
em Computac¸a˜o. O primeiro conjunto indutivo que tivemos contato foi o conjunto dos nu´meros
naturais:
nat ::= 0:nat | S:nat → nat
A definic¸a˜o acima nos diz que um nu´mero natural possui dois construtores: 0, e a func¸a˜o sucessor
S. Por exemplo, S 0, S(S 0) e S(S(S 0)) sa˜o nu´meros naturais constru´ıdos a partir da grama´tica
acima. Alternativamente, o conjunto dos nu´meros naturais pode ser definido da seguinte forma:
8
Definic¸a˜o 4. O conjunto N dos nu´meros naturais e´ o menor conjunto tal que:
(i) 0 ∈ N
(ii) se n ∈ N enta˜o S(n) ∈ N.
De maneira ana´loga podemos definir o conjunto PROPdas fo´rmulas das lo´gica proposicional:
Definic¸a˜o 5. O conjunto PROP das fo´rmulas bem formadas (fbf) da lo´gica proposicional e´ o menor
conjunto tal que:
1. p ∈ PROP (s´ımbolos proposicionais) e ⊥ ∈ PROP;
2. Se a, b ∈ PROP enta˜o (a ∧ b), (a ∨ b), (¬a), (a→ b), (a↔ b) ∈ PROP.
Exemplos:
(a) (¬((p ∧ q)→ r))
(b) ((p→ q) ∧ (¬((r ∨ p)→ q)))
(c) ((p→ q)→ (r → (s ∨ t)))
Teorema 2 (Princ´ıpio de induc¸a˜o). Seja A uma propriedade. Temos que A(ϕ) (i.e. a fo´rmula ϕ
satisfaz a propriedade A) para todo ϕ ∈ PROP se, e somente se
1. A(⊥) e´ verdadeira
2. A(p) e´ verdadeira para toda varia´vel proposicional p
3. Se A(ϕ) e A(ψ) enta˜o A(ϕ�ψ), onde � ∈ {→,↔,∧,∨}
4. Se A(ϕ) enta˜o A(¬ϕ)
Prova. Let X = {ϕ ∈ PROP | A(ϕ)}. Temos que X satisfaz os itens 1 e 2 da Definic¸a˜o 5 e
portanto PROP ⊆ X. Logo A(ϕ) e´ verdadeiro para toda fo´rmula ϕ. �
Propriedades sobre conjuntos indutivos sa˜o demonstradas utilizando-se induc¸a˜o, como explicado
no cap´ıtulo anterior. As fo´rmulas da lo´gica proposicional tambe´m sa˜o definidas indutivamente.
Definic¸a˜o 6. Definimos indutivamente as fo´rmulas bem formadas (fbf) da seguinte maneira:
1. Um s´ımbolo proposicional e ⊥ sa˜o uma fbf (chamada de fo´rmula atoˆmica);
2. Se a e b sa˜o fbf enta˜o (a ∧ b), (a ∨ b), (¬a), (a→ b) e (a↔ b) tambe´m sa˜o fbf.
3. Cla´usula maximal: a linguagem da lo´gica proposicional e´ o menor conjunto que satisfaz as
regras 1 ou 2 acima.
Pareˆnteses mais externos podem ser omitidos ja´ que estes na˜o geram ambiguidade:
(a) ¬((p ∧ q)→ r)
(b) (p→ q) ∧ (¬((r ∨ p)→ q))
9
(c) (p→ q)→ (r → (s ∨ t))
Adicionalmente, a fim de possibilitar eliminar mais pareˆnteses, adotaremos a seguinte ordem de
precedeˆncia para os conectivos:
1. ¬
2. ∧,∨
3. →, ↔
4. → associa-se a` direita;
5. ∧ e ∨ associam-se a` esquerda.
Exemplos 1. • p→ q → r representa (p→ (q → r));
• p ∧ q ∧ r representa (p ∧ q) ∧ r.
Recursa˜o
Teorema 3 (Definic¸a˜o por recursa˜o). Sejam H� : A2 → A and H¬ : A→ A func¸o˜es dadas, e seja
Hat uma func¸a˜o do conjunto de a´tomos em A. Enta˜o existe exatamente uma func¸a˜o F : PROP→ A
tal que:
• F (ϕ) = Hat(ϕ), se ϕ e´ atoˆmica;
• F (ϕ�ψ) = H�(F (ϕ), F (ψ)), onde � ∈ {→,↔,∧,∨}
• F (¬ϕ) = H¬(F (ϕ))
Prova.
�
Definic¸a˜o 7 (Subfo´rmula). Dada uma fbf H, definimos recursivamente as subfo´rmulas de H da
seguinte forma:
(a) H e´ uma subfo´rmula de H;
(b) Se H = ¬G enta˜o G e´ uma subfo´rmula de H;
(c) Se H = F ∧G,F ∨G,F → G enta˜o F e G sa˜o subfo´rmulas de H.
Exemplo 1. Denotando por Subf(H), o conjunto das subfo´rmulas de H, temos que
Subf((p ∨ ¬q)→ (r ∧ ¬q)) = {p, q, r,¬q, p ∨ ¬q, r ∧ ¬q,
(p ∨ ¬q)→ (r ∧ ¬q)}
Pela definic¸a˜o anterior, uma fo´rmula e´ sempre subfo´rmula de si mesma. Dizemos que uma
subfo´rmula H de F e´ pro´pria se H ∈ Subf(F ) e H 6= F .
Definic¸a˜o 8. O tamanho ou complexidade de uma fo´rmula A, representado por |A|, e´ um nu´mero
inteiro positivo definido por:
10
1. |p| = 1, para toda fo´rmula atoˆmica p;
2. |¬A| = 1 + |A|;
3. |A ◦B| = 1 + |A|+ |B|, para ◦ ∈ {∧,∨,→}.
Exemplos 2. Se p, q e r sa˜o varia´veis proposicionais enta˜o:
• |¬p| = 2
• |p→ q ∧ r| = 5
Exerc´ıcios
1. Determine quais das fo´rmulas a seguir sa˜o bem formadas:
(a) → p
(b) p ∧ q → p
(c) pq ∧ ¬b
(d) p¬
(e) p→ p→ q → q
(f) (p ∧ q)→ (p ∨ (q ∧ r))
2. Assumindo a ordem de precedeˆncia dada anteriormente, reescreva estas fo´rmulas colocando
tantos pareˆnteses quanto for poss´ıvel. Por exemplo, p ∧ q → r deve ser reescrito como
(p ∧ q)→ r ja´ que o conectivo ∧ tem maior prioridade do que →.
(a) ¬p ∧ q → r
(b) (p→ q) ∧ ¬(r ∨ p→ q)
(c) (p→ q)→ (r → s ∨ t)
(d) p ∨ (¬q → p ∧ r)
(e) p ∨ q → ¬p ∧ r
(f) p ∨ p→ ¬r
3. Determine todas as subfo´rmulas das fo´rmulas dadas no exerc´ıcio 2.
4. Calcule a complexidade das fo´rmulas dadas no exerc´ıcio 2.
5. Definir por induc¸a˜o sobre a estrutura das fo´rmulas a func¸a˜o at(φ) que retorna o conjunto de
todos os a´tomos que ocorrem na fo´rmula φ. Por exemplo, at(p ∧ (p→ q ∨ p)) = {p, q}.
6. Defina por induc¸a˜o sobre a estrutura das fo´rmulas a func¸a˜o imp(φ) que retorna o nu´mero de
implicac¸o˜es que ocorrem em φ. Exemplo: imp(p→ (p→ ¬q)) = 2.
7. Prove que uma fo´rmula da lo´gica proposicional com n conectivos possui, no ma´ximo, 2n+ 1
subfo´rmulas.
11
12
Cap´ıtulo 3
A Semaˆntica da Lo´gica Proposicional
A semaˆntica trata do significado dos objetos da lo´gica. Por exemplo, o significado que pretendemos
atribuir ao s´ımbolo de negac¸a˜o ¬ e´ tal que uma fo´rmula φ e´ verdadeira sempre que ¬φ for falsa e
vice-versa. Esta intenc¸a˜o pode ser expressa por meio da seguinte tabela verdade:
φ ¬φ
V F
F V
Para a conjunc¸a˜o, denotada por ∧, esperamos que uma fo´rmula da forma φ∧ψ seja verdadeira
sempre que φ e ψ forem verdadeiras:
φ ψ φ ∧ ψ
V V V
V F F
F V F
F F F
Para a disjunc¸a˜o, denotada por ∨, esperamos que uma fo´rmula da forma φ ∨ ψ seja verdadeira
sempre que φ ou ψ forem verdadeiras:
φ ψ φ ∨ ψ
V V V
V F V
F V V
F F F
Para a implicac¸a˜o, denotada por→, esperamos que uma fo´rmula da forma φ→ ψ seja verdadeira
em todos os casos, exceto quando φ for verdadeira e ψ for falsa:
φ ψ φ→ ψ
V V V
V F F
F V V
F F V
13
A bi-implicac¸a˜o, que abreviamos por ↔, e´ muito utilizado em Matema´tica e corresponde a
expressa˜o “se e somente se”:
p↔ q ≡ (p→ q) ∧ (q → p)
Para a bi-implicac¸a˜o, esperamos que uma fo´rmula da forma φ↔ ψ seja verdadeira sempre que
φ e ψ tiverem a mesma valorac¸a˜o:
φ ψ φ↔ ψ
V V V
V F F
F V F
F F V
Valorac¸a˜o de Fo´rmulas
Sabendo que as varia´veis p, q, r e s teˆm valor respectivamente igual a V , F , F e V , podemos
determinar o valor da fo´rmula φ ≡ (p→ q)↔ (r ∧ (s ∨ p)) a partir das tabelas dadas, da seguinte
forma:
p q r s p→ q s ∨ p r ∧ (s ∨ p) φ
V F F V F V F V
A partir da semaˆntica dada para os conectivos, vamos construir a tabela verdade de algumas
fo´rmulas.
Exemplos
Como construir a tabela verdade da fo´rmula p→ (p ∨ q)?
p q p ∨ q p→ (p ∨ q)
V V V V
V F V V
F V V V
F F F V
Uma fo´rmula que e´ sempre verdadeira independente da valorac¸a˜o dada a`s suas varia´veis e´ chamada
de tautologia.
Vejamos mais um exemplo: construir a tabela verdade da fo´rmula (p ∧ q) ∨ (p ∧ r).
p q r p ∧ q p ∧ r (p ∧ q) ∨ (p ∧ r)
V V V V V V
V V F V F V
V F V F V V
V F F F F F
F V V F F FF V F F F F
F F V F F F
F F F F F F
14
Interpretac¸o˜es
Definic¸a˜o 9. Uma interpretac¸a˜o I na lo´gica proposicional e´ uma func¸a˜o bina´ria tal que:
• o domı´nio de I e´ o conjunto das fo´rmulas da lo´gica proposicional;
• o contradomı´nio de I e´ o conjunto {V, F}.
Definic¸a˜o 10. Dadas uma fo´rmula φ e uma interpretac¸a˜o I, definimos o significado de φ, denotado
por I[φ], da seguinte maneira:
• Se φ e´ uma varia´vel proposicional p enta˜o I[φ] = I[p].
• Se φ = ¬ψ enta˜o:
– I[φ] = V , se I[ψ] = F ;
– I[φ] = F , se I[ψ] = V .
• Se φ = ψ ∧ ξ enta˜o:
– I[φ] = V , se I[ψ] = V e I[ξ] = V ;
– I[φ] = F , se I[ψ] = F ou I[ξ] = F .
• Se φ = ψ ∨ ξ enta˜o:
– I[φ] = V , se I[ψ] = V ou I[ξ] = V ;
– I[φ] = F , se I[ψ] = F e I[ξ] = F .
• Se φ = ψ → ξ enta˜o:
– I[φ] = V , se I[ψ] = F ou I[ξ] = V ;
– I[φ] = F , se I[ψ] = V e I[ξ] = F .
• Se φ = ψ ↔ ξ enta˜o:
– I[φ] = V , se I[ψ] = I[ξ];
– I[φ] = F , se I[ψ] 6= I[ξ].
Assim a tabela verdade de uma fo´rmula φ e´ a tabela que nos fornece todas as poss´ıveis interpretac¸o˜es
para φ. De fato, cada linha da tabela verdade e´ uma interpretac¸a˜o (ou valorac¸a˜o) distinta para φ.
Tautologias, contradic¸o˜es e contingeˆncias
Definic¸a˜o 11. • Uma fo´rmula φ e´ uma tautologia (ou ainda, e´ va´lida) se para toda inter-
pretac¸a˜o I, vale que I[φ] = V . Utilizamos a notac¸a˜o |= φ, para denotar que “φ e´ uma
tautologia”.
• Uma fo´rmula φ e´ uma contradic¸a˜o (ou insatisfat´ıvel) se para toda interpretac¸a˜o I, vale
que I[φ] = F .
• Uma fo´rmula φ e´ uma contingeˆncia se seu valor de verdade depende da interpretac¸a˜o.
• Uma fo´rmula φ e´ uma satisfat´ıvel se existir pelo menos uma interpretac¸a˜o I tal que I[φ] = V .
15
Relac¸o˜es entre as propriedades
• Se uma fo´rmula e´ uma tautologia enta˜o ela e´ satisfat´ıvel;
• Se uma fo´rmula e´ satisfat´ıvel enta˜o ela pode ser uma tautologia ou uma contingeˆncia;
• Se uma fo´rmula na˜o e´ satisfat´ıvel enta˜o ela e´ uma contradic¸a˜o;
• Se uma fo´rmula na˜o e´ uma contradic¸a˜o enta˜o ela e´ satisfat´ıvel e pode ser uma tautologia.
Exemplos
1. A fo´rmula p ∨ ¬p e´
• uma tautologia, e portanto tambe´m e´
• satisfat´ıvel.
2. A fo´rmula p ∧ ¬p e´
• uma contradic¸a˜o, e portanto tambe´m e´
• insatisfat´ıvel.
3. A fo´rmula (p ∧ q) ∨ (p ∧ r) possui a seguinte tabela verdade:
p q r p ∧ q p ∧ r (p ∧ q) ∨ (p ∧ r)
V V V V V V
V V F V F V
V F V F V V
V F F F F F
F V V F F F
F V F F F F
F F V F F F
F F F F F F
• E portanto e´ satisfat´ıvel. Mais ainda, e´ uma contingeˆncia.
4. A fo´rmula p→ (p ∨ q) possui a seguinte tabela verdade:
p q p ∨ q p→ (p ∨ q)
V V V V
V F V V
F V V V
F F F V
• E portanto e´ uma tautologia (ou seja, e´ va´lida).
16
Cap´ıtulo 4
Consequeˆncia Lo´gica e o Ca´lculo
Proposicional
A Semaˆntica da Implicac¸a˜o
Sabemos que a tabela verdade da implicac¸a˜o e´ dada como a seguir.
φ ψ φ→ ψ
V V V
V F F
F V V
F F V
• A primeira linha desta tabela nos diz que se temos duas sentenc¸as φ e ψ verdadeiras, enta˜o
a sentenc¸a φ→ ψ tambe´m e´ verdadeira. Isto e´ razoa´vel pois e´ verdadeiro que uma sentenc¸a
verdadeira implique em outra sentenc¸a verdadeira.
• A segunda linha nos diz que e´ falso concluir uma sentenc¸a falsa a partir de uma outra que
seja verdadeira. Isto tambe´m e´ razoa´vel; considere a seguinte situac¸a˜o:
p: Eu sou nadador profissional.
q: Eu tenho medo de piscinas.
Neste caso, a implicac¸a˜o p → q tem que ser falsa porque nenhum nadador profissional
pode ter medo de piscinas.
• Ja´ a terceira e quarta linhas desta tabela na˜o possuem uma ana´lise ta˜o imediata. O que
estas linhas dizem e´ que independentemente do valor de ψ, a implicac¸a˜o φ→ ψ e´ verdadeira
sempre que φ for falsa. Isto se justifica pelo fato de que e´ poss´ıvel concluir qualquer sentenc¸a
a partir de uma que seja falsa.
Uma outra justificativa pode ser dada considerando-se a seguinte fo´rmula:
p→ (p ∨ q)
17
Como qualquer argumento deve implicar em si mesmo e´ de se esperar que esta fo´rmula seja
verdadeira independente do significado de p ou q. Isto e´, p→ (p ∨ q) e´ uma tautologia:
p q p ∨ q p→ p ∨ q
V V V
V F V
F V V
F F V
Completando esta tabela de acordo com a semaˆntica dada para a disjunc¸a˜o, temos:
p q p ∨ q p→ p ∨ q
V V V V
V F V V
F V V V
F F F V
A partir desta tabela podemos ver que qualquer modificac¸a˜o nas linhas 3 ou 4 da tabela da
implicac¸a˜o resultaria que a fo´rmula acima na˜o seria uma tautologia.
• Mais um pouco sobre a semaˆntica da implicac¸a˜o: suponha que
p: x e´ um nu´mero real maior do que 10.
q: x2 e´ um nu´mero real maior do que 100.
Neste caso, claramente p→ q e´ verdadeiro, pois se p e´ verdadeiro enta˜o q e´ verdadeiro. Agora
suponha que p seja falso. Isto e´, x ≤ 10. Se x = 5 enta˜o x2 = 25 e portanto q e´ falsa. Mas
se x = −20, temos que p e´ falsa, mas q e´ verdadeira. Conclusa˜o: Nada se pode concluir a
respeito de q mesmo sabendo que p→ q e´ verdadeiro. Esta situac¸a˜o esta´ expressa nas linhas
3 e 4 da tabela verdade da implicac¸a˜o.
Causalidade e a Semaˆntica da Implicac¸a˜o
Conforme a tabela verdade da implicac¸a˜o, se q e´ verdadeiro enta˜o p → q e´ verdadeiro inde-
pendente do valor de verdade de p. Da mesma forma, se p e´ falso enta˜o p → q e´ verdadeiro inde-
pendentemente do valor de verdade de q. Isto significa que a implicac¸a˜o na˜o expressa a semaˆntica
da causalidade: na˜o e´ necessa´ria a relac¸a˜o de causa e efeito entre p e q para que se tenha p → q
verdadeiro.
Exerc´ıcios
1. Seja I uma interpretac¸a˜o e φ = p→ q uma fo´rmula da lo´gica proposicional.
(a) Se I[φ] = V , o que se pode concluir a respeito de I[p] e I[q]?
(b) Se I[φ] = V e I[p] = V , o que se pode concluir de I[q]?
(c) Se I[q] = V , o que se pode concluir de I[φ]?
(d) Se I[φ] = V e I[p] = F , o que se pode concluir de I[q]?
18
(e) Se I[q] = F e I[p] = V , o que se pode concluir de I[φ]?
2. Seja I uma interpretac¸a˜o tal que I[p → q] = V . O que se pode deduzir a respeito dos
resultados das interpretac¸o˜es a seguir?
(a) I[(p ∨ r)→ (q ∨ r)]
(b) I[(p ∧ r)→ (q ∧ r)]
(c) I[(¬p ∨ q)→ (p ∨ q)]
3. Repita o exerc´ıcio anterior supondo I[p→ q] = F .
4. Seja I uma interpretac¸a˜o tal que I[p ↔ q] = V . O que se pode concluir a respeito dos
resultados das interpretac¸o˜es a seguir?
(a) I[¬p ∧ q]
(b) I[p ∨ ¬q]
(c) I[q → p]
(d) I[(p ∧ r)↔ (q ∧ r)]
(e) I[(p ∨ r)↔ (q ∨ r)]
5. Repita o exerc´ıcio anterior supondo I[p↔ q] = F .
6. Demonstre se as seguintes afirmac¸o˜es sa˜o verdadeiras:
(a) Se (φ↔ ψ) e (ψ ↔ γ) sa˜o tautologias enta˜o (φ↔ γ) e´ uma tautologia.
(b) (φ↔ ψ) e´ uma tautologia se e somente se (φ ∧ ψ) ou (¬φ ∧ ¬ψ) e´ tautologia.
(c) Se I[φ↔ ψ] = V enta˜o I[φ ∧ ψ] = V ou I[¬φ ∧ ¬ψ] = V .
(d) ¬(φ↔ ψ) e´ tautologia se e somente se φ e ¬ψ sa˜o tautologias.
(e) Se I[¬(φ↔ ψ)] = V enta˜o I[φ] = I[¬ψ] = V .
Consequeˆncia Lo´gica
O que significa dizer que uma fo´rmula e´ consequeˆncia de outra fo´rmula? Ou ainda, o que significa
dizer que uma fo´rmula e´ consequeˆncia de um conjunto de fo´rmulas?
Definic¸a˜o 12. Sejam F e G fo´rmulas da lo´gica proposicional. Dizemos que a fo´rmula G e´ con-
sequeˆncia da fo´rmula F , denotado por F |= G, se qualquer interpretac¸a˜o que satisfaz F , tambe´m
satisfaz G.
Escrevemos |= F para dizer que F e´ satisfeita por qualquer interpretac¸a˜o. Em outras palavras,
F e´ uma tautologia.
Proposic¸a˜o 1. Sejam F e G fo´rmulas da lo´gica proposicional. Enta˜o G e´ consequeˆncia lo´gica de
F se, e somente se, F → G e´ uma tautologia.
Prova. Suponha que G seja consequeˆncia lo´gica de F ; ou seja qualquer interpretac¸a˜o que satisfaz
F tambe´m satisfaz G, e desta forma F → G e´ uma tautologia. Reciprocamente, se F → G e´ uma
tautologia enta˜o qualquer interpretac¸a˜o que satisfaz F tambe´m satisfaz G, e consequentemente G
e´ consequeˆncia lo´gicade F . �
19
Exemplos 3.
1. F ∧G |= F
2. F |= F ∨G
3. F ∧ ¬F |= G
A noc¸a˜o de consequeˆncia lo´gica pode ser estendida para conjuntos de forma imediata. De fato, se
Γ e´ um conjunto finito de fo´rmulas da lo´gica proposicional, dizemos que a fo´rmula F e´ consequeˆncia
lo´gica de Γ, denotado por Γ |= F , se qualquer interpretac¸a˜o que satisfac¸a todas as fo´rmulas de Γ
tambe´m satisfaz F .
Equivaleˆncia Lo´gica
Definic¸a˜o 13. Se F e´ consequeˆncia lo´gica de G, e G e´ consequeˆncia lo´gica de F enta˜o dizemos
que F e G sa˜o equivalentes, isto e´, F ≡ G.
Exemplos 4.
1. F ∧G ≡ G ∧ F
2. F ∨G ≡ G ∨ F
O Ca´lculo Proposicional
Estamos interessados em construir um ca´lculo para raciocinar e tirar concluso˜es a partir de um
certo conjunto de premissas. O ca´lculo que consideraremos aqui e´ conhecido como deduc¸a˜o natural.
O me´todo de deduc¸a˜o natural e´ baseado nos seguintes princ´ıpios:
• As infereˆncias sa˜o realizadas por regras de infereˆncia, onde hipo´teses podem ser introduzidas
na prova, mas devera˜o ser descartadas para a consolidac¸a˜o da prova.
• Para cada conectivo lo´gico, existem duas regras: uma para inserc¸a˜o do conectivo na prova, e
outra para remoc¸a˜o (ou eliminac¸a˜o) do conectivo.
Provas Formais
O fato de que a fo´rmula ψ pode ser obtida (ou provada, ou ainda deduzida) a partir do conjunto
(finito) de fo´rmulas φ1, . . . , φn e´ denotado por:
φ1, . . . , φn︸ ︷︷ ︸
premissas
` ψ ← conclusa˜o
Uma expressa˜o da forma φ1, . . . , φn ` ψ e´ chamada de sequente.
20
φ1 φ2
φ1 ∧ φ2
∧-i φ1 ∧ φ2
φ1
∧-e1
φ1 ∧ φ2
φ2
∧-e2
φ1
φ1 ∨ φ2
∨-i1
φ2
φ1 ∨ φ2
∨-i2
φ1 ∨ φ2
[φ1]
u
...
χ
[φ2]
v
...
χ
χ
∨-e,u, v
Regras de deduc¸a˜o natural (parte 1)
Exemplo 2. Vamos construir uma prova para o sequente p ∧ q, r ` q ∧ r.
1 p ∧ q premissa
2 r premissa
3 q ∧-e2 1
4 q ∧ r ∧-i 3, 2
Utilizando uma estrutura de a´rvores:
∧-e2
p ∧ q
q r
q ∧ r ∧-i
Exerc´ıcio 1. Construa uma prova para o sequente (p ∧ q) ∨ r ` (p ∨ r) ∧ (q ∨ r).
21
22
Cap´ıtulo 5
Deduc¸a˜o Natural (Parte 2)
[φ]u
...
ψ
φ→ ψ →-i, u
φ→ ψ φ
ψ
→-e
[φ]u
...
⊥
¬φ ¬-i,u
φ ¬φ
⊥ ¬-e
¬¬φ
φ
¬¬-e
Tabela 5.1: Regras de deduc¸a˜o natural (parte 2)
Exemplos
Vamos construir uma prova para o seguinte sequente: p, p→ q, p→ q → r ` r
1 p→ q → r premissa
2 p→ q premissa
3 p premissa
4 q → r → -e 1, 3
5 q → -e 2, 3
6 r → -e 4, 5
Exemplo
Considere o sequente: p, p→ q ` p ∧ q
23
1 p premissa
2 p→ q premissa
3 q → -e
4 p ∧ q ∧-i
Regras Derivadas
Apresentaremos agora algumas regras que sa˜o bastante u´teis na construc¸a˜o de provas, mas estas
regras podem ser obtidas a partir das regras ja´ apresentadas. A primeira delas nos permite concluir
qualquer fo´rmula φ a partir da constante ⊥.
⊥
φ
⊥-e
 ⊥ premissa
 ¬φ hipo´tese
 ⊥ co´pia 1
 ¬¬φ ¬-i 2− 3
 φ ¬¬-e 4
A prova dos exemplos a seguir utilizam a regra ⊥-e:
¬p ` p→ q
 ¬p premissa
 p hipo´tese
 ⊥ ¬-e 2, 1
 q ⊥-e 3
 p→ q → -i 2−4
` ¬p→ (p→ (p→ q))
 ¬p hipo´tese
 p hipo´tese
 ⊥ ¬-e 2, 1
 p→ q ⊥-e 3
 (p→ (p→ q)) → -i 2−4
 ¬p→ (p→ (p→ q)) → -i 1−5
24
Uma outra regra derivada importante chama-se ¬¬-i, e sua prova e´ deixada como exerc´ıcio:
φ
¬¬φ ¬¬-i
Provas por contradic¸a˜o sa˜o muito comuns em Matema´tica. A ide´ia e´: para provar φ inicialmente
assumimos ¬φ como hipo´tese e chegamos a uma contradic¸a˜o. Desta forma, ¬φ na˜o pode ser
verdadeira, e portanto φ e´ verdadeiro. A regra de prova por contradic¸a˜o, denotada por (PBC), e´
apresentada a seguir, e sua prova e´ deixada como exerc´ıcio:
[¬φ]u
...
⊥
φ
(PBC),u
Por fim, consideraremos mais uma regra derivada que, sem du´vida, sera´ muito u´til em provas.
Esta regra e´ conhecida como Lei do Terceiro Exclu´ıdo (LTE), e sua prova e´ apresentada a seguir:
φ ∨ ¬φ (LTE)
 ¬(φ ∨ ¬φ) hipo´tese
 φ hipo´tese
 φ ∨ ¬φ ∨-i1 2
 ⊥ ¬-e 1, 3
 ¬φ ¬-i 2− 4
 φ ∨ ¬φ ∨-i2 5
 ⊥ ¬-e 1, 6
 ¬¬(φ ∨ ¬φ) ¬-i 1− 7
 φ ∨ ¬φ ¬¬-e 8
Exerc´ıcios
1. Construa uma prova para a regra ¬¬-i:
φ
¬¬φ ¬¬-i
2. Construa uma prova para a regra (PBC).
25
3. Construa uma prova para a regra (MT):
φ→ ψ ¬ψ
¬φ (MT)
4. Prove a validade dos seguintes sequentes:
(a) (p→ r) ∧ (q → r) ` p ∧ q → r
(b) q → r ` (p→ q)→ (p→ r)
(c) p→ (q → r), p→ q ` p→ r
(d) p→ q, r → s ` p ∨ r → q ∨ s
(e) p ∨ q ` r → (p ∨ q) ∧ r
(f) (p ∨ (q → p)) ∧ q ` p
(g) p→ q, r → s ` p ∧ r → q ∧ s
(h) p→ q ` ((p ∧ q)→ p) ∧ (p→ (p ∧ q))
(i) ` q → (p→ (p→ (q → p)))
(j) p→ q ∧ r ` (p→ q) ∧ (p→ r)
(k) (p→ q) ∧ (p→ r) ` p→ q ∧ r
(l) ` (p→ q)→ ((r → s)→ (p ∧ r → q ∧ s))
5. Construa uma prova para os sequentes a seguir no ProofWeb:
(a) (p ∧ q) ∧ r, s ∧ t ` q ∧ s
(b) (p ∧ q) ` (q ∧ p)
(c) (p ∧ q) ∧ r ` p ∧ (q ∧ r)
(d) p→ (p→ q), p ` q
(e) q → (p→ r),¬r, q ` ¬p
(f) ` (p ∧ q)→ p
(g) p ` q → (p ∧ q)
(h) p ` (p→ q)→ q
(i) p→ q ` ¬q → ¬p
(j) p ∨ (p ∧ q) ` p
(k) r, p→ (r → q) ` p→ (q ∧ r)
(l) p→ (q ∨ r), q → s, r → s ` p→ s
(m) (p ∧ q) ∨ (p ∧ r) ` p ∧ (q ∨ r)
26
Cap´ıtulo 6
A correc¸a˜o da lo´gica proposicional
A correc¸a˜o da lo´gica proposicional
Neste cap´ıtulo provaremos que a lo´gica proposicional e´ correta. Isto significa que so´ conseguire-
mos construir provas de fo´rmulas que sejam verdadeiras segundo a semaˆntica das tabelas-verdade
apresentadas anteriormente. Formalmente, a correc¸a˜o da lo´gica proposicional e´ dada pelo seguinte
teorema:
Teorema 4. Sejam φ1, . . . , φn e ψ fo´rmulas da lo´gica proposicional. Se φ1, . . . , φn ` ψ enta˜o
φ1, . . . , φn |= ψ.
Prova. Se φ1, . . . , φn ` ψ enta˜o existe uma prova de ψ a partir das premissas φ1, . . . , φn. Seja
A(k) a seguinte asserc¸a˜o: “para todo sequente φ1, . . . , φn ` ψ (n ≥ 0) que possui uma prova de
comprimento k, temos que φ1, . . . , φn |= ψ.”
A prova segue por induc¸a˜o sobre k:
BI: Se a prova tem comprimento 1 enta˜o tem que ser da forma:
1. φ1 premissa
Este e´ o caso quando n = 1 e φ1 = ψ, ou seja estamos considerando o sequente ψ ` ψ. E´
claro que ψ |= ψ.
PI: Assuma que a prova do sequente φ1, . . . , φn ` ψ tenha comprimento k, e que a asserc¸a˜o
que queremos provar seja verdadeira para todos os naturais menores que k. Nossa prova tem
a seguinte estrutura:
1 φ1 premissa
2 φ2 premissa
...
n φn premissa
...
k ψ
Precisamos analisar caso a caso qual foi a u´ltima regra aplicada nesta prova:
27
1. Se a u´ltima regra aplicada foi (∧i) enta˜o sabemos que ψ e´ da forma ψ1 ∧ψ2 e a conclusa˜o da
linha k se refere a duas linhas anteriores que possuem ψ1 e ψ2 como conclusa˜o. Sejam k1 e k2
estas linhas. Como k1 e k2 sa˜o menores que k enta˜o temos que existem provas dos sequentes
φ1, . . . , φn ` ψ1 e φ1, . . . , φn ` ψ2 que teˆm comprimento menor que k. Por hipo´tese de induc¸a˜o
temos que φ1, . . . , φn |= ψ1 e φ1, . . . , φn |= ψ2 valem, e portanto φ1, . . . , φn |= ψ1 ∧ ψ2.
2. Se a u´ltima regra aplicada foi (∨e) enta˜o temos uma premissa ou uma prova de uma fo´rmula
da forma η1∨ η2 em uma linha k′ < k, onde a aplicac¸a˜o de (∨e) na linha k se refere a` fo´rmula
η1 ∨ η2 da linha k′. Graficamente temos a seguinte situac¸a˜o:
1 φ1 premissa
2 φ2 premissa
...
n φn premissa
...
k′ η1 ∨ η2
k′ + 1
k′′ − 1
η1
...
ψ
hipo´tese
k′′
k − 1
η2
...
ψ
hipo´tese
k ψ
Desta forma, temos uma prova (de comprimento menor do que k) do sequente φ1, . . . , φn `
η1 ∨ η2. Convertendo η1 em premissa obtemos uma prova para o sequente φ1, . . . , φn, η1 ` ψ,
que por sua vez possui comprimento menor do que k. Da mesma forma, obtemos uma prova
de comprimento menor do que k para o sequente φ1, . . . , φn, η2 ` ψ. Por hipo´tese de induc¸a˜o
conclu´ımos que as relac¸o˜es φ1, . . . , φn |= η1∨η2, φ1, . . . , φn, η1 |= ψ e φ1, . . . , φn, η2 |= ψ valem,
e portanto podemos concluir que φ1, . .. , φn |= ψ.
3. Se a u´ltima regra aplicada foi (→ i) enta˜o sabemos que ψ e´ da forma ψ1 → ψ2. Graficamente
temos a seguinte situac¸a˜o:
1 φ1 premissa
2 φ2 premissa
...
n φn premissa
...
k′ ψ1
...
ψ2
hipo´tese
k ψ1 → ψ2
28
4. Se a u´ltima regra aplicada foi (→ i) enta˜o sabemos que ψ e´ da forma ψ1 → ψ2. Graficamente
temos:
1. φ1 premissa
...
n φn premissa
...
k′
k − 1
ψ1
...
ψ2
hipo´tese
k ψ1 → ψ2
1. φ1 premissa
...
n φn premissa
n+ 1 ψ1 premissa
...
k − 1 ψ2
Sendo assim, convertendo ψ1 em hipo´tese temos uma prova do sequente φ1, . . . , φn, ψ1 ` ψ2
que possui comprimento menor do que k. Por hipo´tese de induc¸a˜o temos que φ1, . . . , φn, ψ1 |=
ψ2, e portanto φ1, . . . , φn |= ψ1 → ψ2 pelo teorema da deduc¸a˜o.
5. Se a u´ltima regra aplicada foi (∧e1) enta˜o temos uma prova do sequente φ1, . . . , φn ` ψ ∧ ψ′
de comprimento menor do que k. Por hipo´tese de induc¸a˜o temos que φ1, . . . , φn |= ψ ∧ ψ′, e
da´ı conclu´ımos que φ1, . . . , φn |= ψ.
6. A prova para (∧e2) e´ inteiramente ana´loga (exerc´ıcio).
7. Se a u´ltima regra aplicada foi (∨i1) enta˜o ψ e´ da forma ψ1∨ψ2. Ale´m disto, temos uma prova
do sequente φ1, . . . , φn ` ψ1 de comprimento menor do que k. Por hipo´tese de induc¸a˜o temos
que φ1, . . . , φn |= ψ1, e portanto φ1, . . . , φn |= ψ1 ∨ ψ2.
8. A prova para (∨i2) e´ ana´loga (exerc´ıcio).
9. Se a u´ltima regra aplicada foi (→ e) enta˜o temos uma prova dos sequentes φ1, . . . , φn ` φ→ ψ
e φ1, . . . , φn ` φ ambas de comprimento menor do que k. Por hipo´tese de induc¸a˜o temos que
φ1, . . . , φn |= φ→ ψ e φ1, . . . , φn |= φ. Portanto, φ1, . . . , φn |= ψ.
10. Se a u´ltima regra aplicada foi (¬i) enta˜o ψ e´ da forma ¬ψ1. Graficamente temos a seguinte
situac¸a˜o:
1. φ1 premissa
...
n φn premissa
...
k′
k − 1
ψ1
...
⊥
hipo´tese
k ¬ψ1
1. φ1 premissa
...
n φn premissa
n+ 1 ψ1 premissa
...
k − 1 ⊥
Sendo assim, temos uma prova do sequente φ1, . . . , φn, ψ1 ` ⊥ de comprimento menor do que
k. Por hipo´tese de induc¸a˜o temos que φ1, . . . , φn, ψ1 |= ⊥, e portanto φ1, . . . , φn |= ¬ψ1. �
29
A correc¸a˜o da lo´gica proposicional e´ u´til para garantirmos a na˜o existeˆncia de uma prova para
um dado sequente. De fato, suponha que voceˆ queira provar que φ1, . . . , φn ` ψ. Mas na˜o esteja
conseguindo... Como garantir que na˜o existe uma prova para este sequente? Pelo resultado
que acabamos de ver, basta encontrarmos uma interpretac¸a˜o para a qual as fo´rmulas φ1, . . . , φn
tenham valor de verdade V e ψ, F . Neste caso, na˜o temos φ1, . . . , φn |= ψ, e pela correc¸a˜o da lo´gica
proposicional o sequente φ1, . . . , φn ` ψ na˜o e´ va´lido.
Exerc´ıcio
1. Escreva a prova de correc¸a˜o da lo´gica proposicional incluindo todos os detalhes.
30
Cap´ıtulo 7
A Completude da Lo´gica
Proposicional
A Completude da Lo´gica Proposicional
A lo´gica proposicional e´ completa. Isto significa que sempre que φ1, . . . , φn |= ψ enta˜o existe uma
prova (em deduc¸a˜o natural) do sequente φ1, . . . , φn ` ψ. Este resultado complementa o teorema
da correc¸a˜o que foi provado na sec¸a˜o 6. Estes dois resultados combinados nos dizem que:
φ1, . . . , φn ` ψ sse φ1, . . . , φn |= ψ.
Temos assim a liberdade de qual me´todo utilizar: o primeiro envolve a busca de uma prova que
e´ onde se baseia o paradigma de programac¸a˜o lo´gica; o segundo praticamente consiste em computar
tabelas-verdade. Ambos os me´todos sa˜o intrata´veis em geral, mas para problemas particulares um
me´todo pode se mostrar mais adequado do que o outro.
A prova da completude da lo´gica proposicional sera´ dividida em treˆs passos:
1. Assumindo φ1, . . . , φn |= ψ, mostraremos que |= φ1 → (φ2 → (. . . (φn → ψ) . . .));
2. Da´ı mostraremos ` φ1 → (φ2 → (. . . (φn → ψ) . . .));
3. Por fim, mostraremos que φ1, . . . , φn ` ψ.
Inicialmente assuma que φ1, . . . , φn |= ψ. Para mostramos que a fo´rmula φ1 → (φ2 → (. . . (φn →
ψ) . . .)) e´ uma tautologia basta observar que a u´nica interpretac¸a˜o capaz de falsificar esta fo´rmula
e´ tal que:
→
uuu
uuu
uuu
II
II
II
II
II
V φ1 →
ww
ww
ww
ww
w
V φ2 →
zz
zz
zz
zz
z
CC
CC
CC
CC
V φn F ψ
31
Mas esta interpretac¸a˜o contradiz o fato de que φ1, . . . , φn |= ψ. Portanto, temos que |= φ1 →
(φ2 → (. . . (φn → ψ) . . .)). Provaremos o item 2 via um resultado mais geral:
Teorema 5. Se |= η, enta˜o ` η. Em outras palavras, se η e´ uma tautologia enta˜o η e´ um teorema.
Prova. Assuma que |= η. Se η possui n varia´veis proposicionais distintas p1, . . . , pn enta˜o
sabemos que η e´ verdadeira para cada uma das 2n poss´ıveis interpretac¸o˜es. Como, a partir desta
informac¸a˜o construir uma prova para η? Para casos particulares isto pode ser uma tarefa fa´cil, mas
aqui estamos interessados em um procedimento uniforme que possa ser utilizado sempre.
A ide´ia chave e´ codificar cada linha da tabela verdade de η como um sequente, e enta˜o construir
provas para cada um destes 2n sequentes. Finalmente combinamos estas provas em uma u´nica
prova para η. Isto sera´ feito com a ajuda da seguinte proposic¸a˜o:
Proposic¸a˜o 2. Seja φ uma fo´rmula da lo´gica proposicional onde p1, . . . , pn sa˜o todas as varia´veis
proposicionais que ocorrem em φ. Seja l uma linha qualquer na tabela-verdade de φ. Para todo
1 ≤ i ≤ n, seja pˆi igual a pi se pi na linha l e´ V e ¬pi caso contra´rio. Enta˜o temos:
1. pˆ1, . . ., pˆn ` φ se a entrada para φ na linha l e´ V ;
2. pˆ1, . . ., pˆn ` ¬φ se a entrada para φ na linha l e´ F .
Prova. A prova e´ por induc¸a˜o estrutural na fo´rmula φ:
1. Se φ e´ uma varia´vel proposicional p enta˜o precisamos provar que p ` p e ¬p ` ¬p, o que e´
trivial.
2. Se φ e´ da forma ¬φ1 enta˜o temos dois casos a considerar:
• Primeiro assuma que φ tem valor V . Neste caso, φ1 tem valor F . Ale´m disto φ1 conte´m
as mesmas varia´veis proposicionais de φ. Por hipo´tese de induc¸a˜o conclu´ımos que pˆ1, . . .,
pˆn ` ¬φ1.
• Se φ tem valor F enta˜o φ1 tem valor V e por hipo´tese de induc¸a˜o temos que pˆ1, . . .,
pˆn ` φ1. Utilizando a regra (¬¬i) podemos estender a prova de pˆ1, . . ., pˆn ` φ1 para
uma de pˆ1, . . ., pˆn ` ¬¬φ1, ou seja pˆ1, . . ., pˆn ` ¬φ.
Nos casos a seguir precisamos considerar duas sub-fo´rmulas, isto e´, φ e´ da forma φ1◦φ2, onde ◦ e´
igual a→, ∧ ou ∨. Em todos estes casos denotaremos por q1, . . . , ql as varia´veis proposicionais de φ1,
e por r1, . . . , rk as varia´veis proposicionais de φ2. Sendo assim temos que {q1, . . . , ql}∪{r1, . . . , rk} =
{p1, . . . , pn}.
3. Seja φ da forma φ1 → φ2.
• Se φ tem valor F enta˜o sabemos que φ1 tem valor V e φ2 tem valor F . Por hipo´tese de
induc¸a˜o, temos que qˆ1, . . ., qˆl ` φ1 e rˆ1, . . ., rˆk ` ¬φ2, e portanto pˆ1, . . ., pˆn ` φ1 ∧ ¬φ2.
Precisamos provar que
pˆ1, . . ., pˆn ` ¬(φ1 → φ2).
Isto e´ feito mostrando-se que φ1 ∧ ¬φ2 ` ¬(φ1 → φ2) (exerc´ıcio).
• Se φ tem valor V enta˜o temos treˆs casos a considerar:
32
(a) Primeiro, se φ1 e φ2 teˆm valor F enta˜o por hipo´tese de induc¸a˜o temos que
qˆ1, . . ., qˆl ` ¬φ1 e rˆ1, . . ., rˆk ` ¬φ2
e portanto pˆ1, . . ., pˆn ` ¬φ1 ∧ ¬φ2. Para concluir este caso, basta provar que
¬φ1 ∧ ¬φ2 ` φ1 → φ2 (exerc´ıcio).
(b) Se φ1 tem valor F e φ2 tem valor V , enta˜o utilizamos a hipo´tese de induc¸a˜o para
concluir que pˆ1, . . ., pˆn ` ¬φ1 ∧ φ2. Conclu´ımos este caso provando que ¬φ1 ∧ φ2 `
φ1 → φ2 (exerc´ıcio).
(c) Por fim, se φ1 e φ2 teˆm valor V enta˜o utilizando a hipo´tese de induc¸a˜o para concluir
que pˆ1, . . ., pˆn ` φ1 ∧ φ2. Finalizamos este caso provando que φ1 ∧ φ2 ` φ1 → φ2
(exerc´ıcio).
Os casos em que φ e´ da forma φ1 ∧ φ2 ou φ1 ∨ φ2 sa˜o ana´logos (exerc´ıcio!) �
Ao aplicarmos esta te´cnica para a fo´rmula φ1 → (φ2 → (. . . (φn → ψ) . . .)), como ela e´ uma
tautologia temos que todas as 2n linhas de sua tabela verdade teˆm valor verdadeV . Portanto, pela
proposic¸a˜o anterior obtemos 2n provas para o sequente
pˆ1, . . ., pˆn ` φ1 → (φ2 → (. . . (φn → ψ) . . .))
para cada um dos casos em que pˆi seja pi ou ¬pi. Nosso trabalho e´ juntar todas estas provas em
uma prova uma para o sequente ` φ1 → (φ2 → (. . . (φn → ψ) . . .)). Faremos isto atrave´s de um
exemplo para a tautologia p ∧ q → p.
A proposic¸a˜o anterior nos garante a existeˆncia de uma prova para os seguintes sequentes:
p, q ` p ∧ q → p
¬p, q ` p ∧ q → p
p,¬q ` p ∧ q → p
¬p,¬q ` p ∧ q → p
Para construir uma prova para o sequente ` p ∧ q → p utilizaremos a LTE para cada uma das
varia´veis proposicionais que aparecem na fo´rmula. Posteriormente assumimos cada um dos casos
pela utilizac¸a˜o da regra (∨e).
p ∨ ¬p LTE
p hip
q ∨ ¬q LTE
q hip
...
p ∧ q → p
¬q hip
...
p ∧ q → p
p ∧ q → p (∨e)
¬p hip
q ∨ ¬q LTE
q hip
...
p ∧ q → p
¬q hip
...
p ∧ q → p
p ∧ q → p (∨e)
p ∧ q → p (∨e)
33
O me´todo e´ apresentado para um exemplo, mas o mesmo e´ uniforme e pode ser utilizado para
tautologias em geral.
Finalmente precisamos encontrar uma prova para o sequente φ1, . . . , φn ` ψ a partir de uma
prova do sequente ` φ1 → (φ2 → (. . . (φn → ψ) . . .)). Isto pode ser feito aplicando sucessivamente
a regra (→ e) tomando φ1, . . . , φn como premissas:
φ1 premissa
...
φn premissa
...
φ1 → (φ2 → (. . . (φn → ψ) . . .))
φ2 → (. . . (φn → ψ) . . .) (→ e)
...
ψ (→ e)
Como consequeˆncia dos teoremas das correc¸a˜o e completude da lo´gica proposicional temos o
seguinte corla´rio:
Corola´rio 1. Sejam φ1, . . . , φn, ψ fo´rmulas da lo´gica proposicional. Enta˜o φ1, . . . , φn |= ψse, e
somente se o sequente φ1, . . . , φn ` ψ.
7.0.1 Exerc´ıcio
1. Complete os detalhes da prova apresentada neste cap´ıtulo.
34
Cap´ıtulo 8
Conjuntos Completos de Conectivos
Conjuntos Completos de Conectivos
Os conectivos lo´gicos que estamos utilizando (¬,∧,∨,→,↔) sa˜o, de certa forma, “redundantes”.
Isto e´ claro para o caso da dupla implicac¸a˜o uma vez que definimos este conectivo em func¸a˜o da
implicac¸a˜o e da conjunc¸a˜o:
φ↔ ψ ≡ (φ→ ψ) ∧ (ψ → φ)
onde ψ e phi sa˜o fo´rmulas quaisquer da lo´gica proposicional. Neste sentido podemos dizer que a
dupla implicac¸a˜o na˜o adiciona poder de expressividade a` linguagem constru´ıda a partir de varia´veis
e dos conectivos ¬, ∧, ∨ e →. Podemos, nos perguntar enta˜o se algum dos conectivos ¬, ∧, ∨
e → pode ser representado em func¸a˜o dos outros treˆs. Esta resposta tambe´m parece ser fa´cil
de responder porque conhecemos uma equivaleˆncia que nos permite representar a implicac¸a˜o em
func¸a˜o apenas da negac¸a˜o e da disjunc¸a˜o:
φ→ ψ ≡ ¬φ ∨ ψ
Desta forma, parece que precisamos pelo menos dos conectivos ¬, ∧ e ∨ para representar as
fo´rmulas da lo´gica proposicional. Sera´ poss´ıvel diminuir ainda mais este conjunto? A resposta e´
sim! Mostraremos que os conectivos ¬, ∨ sa˜o suficientes para expressar todos os outros. Neste caso,
dizemos que {¬,∨} e´ um conjunto completo de conectivos. Um conjunto de conectivos proposicionais
Ψ e´ completo quando for poss´ıvel expressar de forma equivalente, os conectivos ¬, ∧, ∨, → e ↔
utilizando apenas os conectivos de Ψ.
Definic¸a˜o 14. Seja Ψ um conjunto de conectivos. O conjunto Ψ e´ completo se, dada uma fo´rmula φ
do tipo ¬p, (p∨q), (p∧q), (p→ q) ou p↔ q, podemos determinar uma outra fo´rmula ψ equivalente
a φ e tal que ψ conte´m apenas os conectivos do conjunto Ψ e os s´ımbolos p e q presentes em φ.
Proposic¸a˜o 3. O conjunto {¬,∨} e´ completo.
Prova.
p→ q ≡ ¬p ∨ q
p ∧ q ≡ ¬(¬p ∨ ¬q)
p↔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p) ≡ ¬(¬(¬p ∨ q) ∨ ¬(¬q ∨ p)) �
35
Proposic¸a˜o 4. Seja φ uma fo´rmula da lo´gica proposicional. Enta˜o existe uma fo´rmula φ′ equi-
valente a φ e constru´ıda apenas os conectivos ∨ e ¬ e os s´ımbolos proposicionais que ocorrem em
φ.
Prova. Induc¸a˜o sobre a estrutura de φ:
• Se φ e´ uma varia´vel proposicional enta˜o tome φ′ = φ.
• Se φ e´ da forma ¬ψ enta˜o por hipo´tese de induc¸a˜o ψ pode ser expressa equivalentemente
por uma fo´rmula ψ′ que utiliza apenas os conectivos ∨, ¬ e os s´ımbolos proposicionais que
ocorrem em ψ. Neste caso, tome φ′ como sendo a fo´rmula ¬ψ′.
• Se φ e´ da forma ψ1 ∨ψ2 enta˜o por hipo´tese de induc¸a˜o, as fo´rmulas ψ1 e ψ2 podem ser repre-
sentadas equivalentemente por fo´rmulas ψ′1 e ψ′2 que satisfazem as condic¸o˜es da proposic¸a˜o.
Neste caso, fac¸a φ′ = ψ′1 ∨ ψ′2.
• Se φ e´ da forma ψ1 → ψ2 enta˜o φ ≡ ¬ψ1∨ψ2. Por hipo´tese de induc¸a˜o existem fo´rmulas ψ′1 e
ψ′2 que satisfazem as condic¸o˜es da proposic¸a˜o, e sa˜o respectivamente equivalentes a ψ1 e ψ2.
Enta˜o basta tomar φ′ como sendo a fo´rmula ¬ψ′1 ∨ ψ′2.
• Se φ e´ da forma ψ1 ∧ ψ2 enta˜o φ ≡ ¬(¬ψ1 ∨ ¬ψ2). Por hipo´tese de induc¸a˜o existem fo´rmulas
ψ′1 e ψ′2 que satisfazem as condic¸o˜es da proposic¸a˜o, e sa˜o respectivamente equivalentes a ψ1 e
ψ2. Enta˜o a fo´rmula ¬(¬ψ′1 ∨ ¬ψ′2) e´ a fo´rmula φ′ que desejamos.
• Se φ for uma dupla implicac¸a˜o podemos converteˆ-la a uma fo´rmula equivalente contendo
apenas os conectivos → e ∧, e recursivamente aplicar os passos de conversa˜o para cada um
destes conectivos. �
Proposic¸a˜o 5. Considere o considere o conectivo nand definido por:
p nand q ≡ ¬(p ∧ q)
O conjunto {nand} e´ completo. Ale´m disso, se φ e´ uma fo´rmula da lo´gica proposicional enta˜o φ
pode ser expressa equivalentemente utilizando apenas o conectivo nand e o s´ımbolos proposicionais
presentes em φ.
Prova. Completude de {nand}:
• ¬p ≡ p nand p.
• p ∨ q ≡ ((p nand p) nand (q nand q))
Induc¸a˜o sobre a estrutura de φ:
• Se φ e´ da forma ¬ψ enta˜o por hipo´tese de induc¸a˜o existe uma fo´rmula ψ′ equivalente a ψ
e que possui apenas o conectivo nand e os s´ımbolos proposicionais de ψ. Enta˜o a fo´rmula
ψ′ nandψ′ e´ equivalente a φ e possui apenas o conectivo nand e os s´ımbolos proposicionais
de φ.
• Se φ e´ da forma ψ1 ∨ψ2 enta˜o por hipo´tese de induc¸a˜o existem fo´rmulas ψ′1 e ψ′2 equivalentes
a ψ1 e ψ2 e que possuem apenas o conectivo nand e os s´ımbolos proposicionais de ψ1 e ψ2,
respectivamente. Enta˜o a fo´rmula (ψ′1 nand ψ′1) nand (ψ′2 nand ψ′2) e´ equivalente a φ e possui
apenas o conectivo nand e os s´ımbolos proposicionais de φ. �
36
Exemplo 3. Considere a fo´rmula p ∧ (r → s). Temos:
p ∧ (r → s) ≡
p ∧ (¬r ∨ s) ≡
p ∧ ¬¬(¬r ∨ s) ≡
p ∧ ¬(r ∧ ¬s) ≡
p ∧ (r nand (s nand s)) ≡
¬¬(p ∧ (r nand (s nand s))) ≡
¬(p nand (r nand (s nand s))) ≡
(p nand (r nand (s nand s))) nand (p nand (r nand (s nand s)))
Exerc´ıcios
1. Mostre que {∨,→} e´ um conjunto completo de conectivos.
37
38
Cap´ıtulo 9
Formas Normais
Formas Normais
Utilizar deduc¸a˜o natural para construir provas de sequentes e´ apenas uma possibilidade dentre
va´rias poss´ıveis. Da mesma forma, verificar instaˆncias de |= (consequeˆncia lo´gica) utilizando a
Definic¸a˜o 12 e´ apenas uma possibilidade para verificar que F |= G. Neste cap´ıtulo, estudaremos
outras alternativas para decidir se F |= G, ou de uma forma mais geral, se Γ |= G, onde Γ e´ um
conjunto finito de fo´rmulas. As alternativas aqui apresentadas sa˜o baseadas em transformac¸o˜es
sinta´ticas que preservam a semaˆntica das fo´rmulas. Iniciaremos com a definic¸a˜o de literal que
constitui uma componente fundamental das formas normais.
Definic¸a˜o 15 (Literal). Um literal e´ um a´tomo ou a negac¸a˜o de um a´tomo.
Definic¸a˜o 16 (Cla´usula). Uma cla´usula e´ uma disjunc¸a˜o de literais.
Definic¸a˜o 17 (Forma Normal Negada (FNN)). Uma fo´rmula da lo´gica proposicional esta´ em forma
normal negada se conte´m apenas os conectivos ¬, ∧ e ∨, e o conectivo de negac¸a˜o esta´ aplicado
apenas a fo´rmulas atoˆmicas.
Proposic¸a˜o 6. Toda fo´rmula da lo´gica proposicional possui uma forma equivalente em forma
normal negada.
Prova. Seja φ uma fo´rmula da lo´gica proposicional. As transformac¸o˜es a seguir preservam a
semaˆntica da fo´rmula, e umavez que nenhuma delas possa mais ser aplicada, teremos uma fo´rmula
em FNN. Note que se φ e´ uma varia´vel proposicional enta˜o ja´ esta´ em FNN e na˜o ha´ nada a fazer.
1. Reescreva toda subfo´rmula da forma ψ1 ↔ ψ2 para (ψ1 → ψ2) ∧ (ψ2 → ψ1).
2. Reescreva toda subfo´rmula da forma ψ1 → ψ2 para ¬ψ1 ∨ ψ2.
3. (Leis de de Morgan): Reescreva toda subfo´rmula da forma
¬(ψ1 ∧ ψ2) para ¬ψ1 ∨ ¬ψ2;
¬(ψ1 ∨ ψ2) para ¬ψ1 ∧ ¬ψ2.
4. Reescreva toda subfo´rmula da forma ¬¬ψ para ψ.
�
39
Exemplo 4. Considere a transformac¸a˜o a seguir, onde p e q sa˜o varia´veis proposicionais:
p→ ¬(p↔ q) ≡1
p→ ¬((p→ q) ∧ (q → p)) ≡2
¬p ∨ ¬((¬p ∨ q) ∧ (¬q ∨ p)) ≡3
¬p ∨ ¬(¬p ∨ q) ∨ ¬(¬q ∨ p)) ≡3
¬p ∨ (¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p) ≡4
¬p ∨ (p ∧ ¬q) ∨ (q ∧ ¬p)
Exemplo 5.
(¬p→ (¬p→ q)) ∧ (q → (¬p→ q)) ≡2
(¬¬p ∨ (¬¬p ∨ q)) ∧ (¬q ∨ (¬¬p ∨ q)) ≡4
(p ∨ p ∨ q) ∧ (¬q ∨ p ∨ q)
A fo´rmula obtida acima esta´ em FNN, mas observe que algumas simplificac¸o˜es sa˜o poss´ıveis.
De fato, a subfo´rmula p∨p e´ equivalente a p. Da mesma forma, q∨¬q e´ uma tautologia. Motivado
por estas observac¸o˜es apresentaremos a seguir algumas regras de simplificac¸a˜o:
1. Reescreva toda subfo´rmula da forma ψ ∨ ψ para ψ.
2. Reescreva toda subfo´rmula da forma ψ ∧ ψ para ψ.
3. Reescreva toda subfo´rmula da forma ψ ∨ ¬ψ para >.
4. Reescreva toda subfo´rmula da forma ψ ∧ ¬ψ para ⊥.
5. Reescreva toda subfo´rmula da forma ψ ∨ > para >.
6. Reescreva toda subfo´rmula da forma ψ ∧ > para ψ.
7. Reescreva toda subfo´rmula da forma ψ ∨ ⊥ para ψ.
8. Reescreva toda subfo´rmula da forma ψ ∧ ⊥ para ⊥.
Aplicando estas regras a fo´rmula (p∨ p∨ q)∧ (¬q∨ p∨ q) do exemplo anterior pode ser simplificada
para p ∨ q.
Forma Normal Conjuntiva (FNC)
Definic¸a˜o 18. Uma fo´rmula esta´ em forma normal conjuntiva (fnc) se for uma conjunc¸a˜o de
cla´usulas.
Assim, se L representa um literal, e D uma disjunc¸a˜o de literais enta˜o uma fo´rmula C em fnc
pode ser constru´ıda de acordo com a seguinte grama´tica:
L ::= p | ¬p
D ::= L | L ∨D
C ::= D | D ∧ C
40
Exemplo 6. As fo´rmulas (¬q ∨ p ∨ r) ∧ (¬p ∨ r) ∧ q e (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r) esta˜o em fnc,
enquanto que (¬(q ∨ p) ∨ r) ∧ (q ∨ r) na˜o esta´ porque q ∨ p na˜o e´ um literal.
Por que as formas normais conjuntivas sa˜o importantes? Uma das razo˜es e´ devido ao fato de
que as formas normais conjuntivas nos permitem checar facilmente se uma fo´rmula e´ va´lida ou na˜o.
Por exemplo, considere a fo´rmula (¬q∨ p∨ r)∧ (¬p∨ r)∧ q. Temos que |= (¬q∨ p∨ r)∧ (¬p∨ r)∧ q
se vale cada uma das relac¸o˜es semaˆnticas a seguir:
|= ¬q ∨ p ∨ r
|= ¬p ∨ r
|= q
E como cada uma destas fo´rmulas e´ um literal ou a disjunc¸a˜o de literais enta˜o podemos decidir a
validade da fo´rmula original da seguinte forma:
Lema 1. Uma disjunc¸a˜o L1 ∨L2 ∨ . . .∨Ln e´ va´lida se, e somente se, existem 1 ≤ i, j ≤ n tais que
Li = ¬Lj.
Prova. Se Li = ¬Lj enta˜o o resultado e´ claro. Reciprocamente, suponha que L1∨L2∨. . .∨Ln seja
va´lida. Suponha que na˜o existam 1 ≤ i, j ≤ n, tais que Li = ¬Lj . Enta˜o considere a interpretac¸a˜o
I tal que, para todo 1 ≤ k ≤ n, I(Lk) = F se Lk for um a´tomo, e I(Lk) = V se Lk for a negac¸a˜o de
um a´tomo. Claramente, I(L1∨L2∨ . . .∨Ln) = F o que contradiz nossa suposic¸a˜o inicial. �
Nosso objetivo e´ esboc¸ar a ide´ia geral de um algoritmo (ou seja, uma func¸a˜o) que receba
como entrada uma fo´rmula qualquer φ da lo´gica proposicional e retorne uma fo´rmula φ′ em forma
normal conjuntiva tal que φ ≡ φ′. Como esta func¸a˜o deve funcionar para qualquer fo´rmula, isto
sugere que a mesma seja contru´ıda por induc¸a˜o na estrutura da fo´rmula. Iniciaremos computando
a forma normal negada (fnn) (ver Definic¸a˜o 17) de φ, que denotaremos por fnn(φ). Note que
fnn(φ) conte´m ocorreˆncias apenas dos conectivos ¬, ∧ e ∨, e as negac¸o˜es esta˜o aplicadas apenas a`s
fo´rmulas atoˆmicas. A ide´ia geral para a construc¸a˜o da func¸a˜o fnn e´ dada na Proposic¸a˜o 6. Assim,
se a fo´rmula φ de entrada for uma conjunc¸a˜o da forma φ1 ∧ φ2 enta˜o precisamos recursivamente
computar a fnc de φ1 e de φ2, que chamaremos respectivamente de φ
′
1 e φ
′
2. Neste caso, φ
′
1 ∧ φ′2
esta´ em fnc, e e´ equivalente a` fo´rmula original φ.
Por fim, se a fo´rmula φ for uma disjunc¸a˜o da forma φ1 ∨ φ2, e φ1 for uma conjunc¸a˜o da forma
φ11 ∧ φ12 enta˜o precisamos aplicar a equivaleˆncia (φ11 ∧ φ12) ∨ φ2 ≡ (φ11 ∨ φ2) ∧ (φ12 ∨ φ2), e
recursivamente continuar a transformac¸a˜o das subfo´rmulas (φ11 ∨ φ2) e (φ12 ∨ φ2). O caso em que
φ2 e´ uma disjunc¸a˜o e´ ana´logo.
(F ∧G) ∨H ≡ (F ∨H) ∧ (G ∨H)
H ∨ (F ∧G) ≡ (H ∨ F ) ∧ (H ∨G).
Exerc´ıcios
Sabendo que p, q e r sa˜o varia´veis proposicionais, transforme cada uma das fo´rmulas a seguir para
a forma normal conjuntiva.
1. p→ q → r
2. (p→ q) ∧ (q → r)→ p→ r
41
3. (p ∧ q) ∨ (q ∧ r)
4. (p→ q)↔ (¬p ∨ q)
5. ((p→ q)→ p)→ p
Forma Normal Conjuntiva no ProofWeb
O objetivo desta sec¸a˜o e´ fornecer subs´ıdios para a construc¸a˜o da func¸a˜o fnc que computa a
forma normal conjuntiva de uma fo´rmula da lo´gica proposicional, segundo as ide´ias apresentadas
na sec¸a˜o anterior. O primeiro passo e´ definir uma grama´tica para representar as fo´rmulas da lo´gica
proposicional. Para isto precisaremos de um construtor para representar as varia´veis proposicionais,
e tambe´m para cada um dos conectivos ¬, ∨, ∧ e→. A definic¸a˜o a seguir apresenta uma grama´tica
poss´ıvel:
Inductive fprop : Set :=
| var : string -> fprop
| neg : fprop -> fprop
| con : fprop -> fprop -> fprop
| dis : fprop -> fprop -> fprop
| imp : fprop -> fprop -> fprop.
O construtor var e´ utilizado para representar as varia´veis proposicionais. Por exemplo, a
varia´vel proposicional p sera´ representada no ProofWeb por var ‘‘p’’, enquanto que a fo´rmula
p → q
sera´ representada por
imp (var ‘‘p’’) (var ‘‘q’’).
A construc¸a˜o da func¸a˜o fnc sera´ dividida em va´rias etapas. Em cada etapa faremos uma parte
da reduc¸a˜o. Iniciaremos com a func¸a˜o impl free que elimina as implicac¸o˜es que ocorrem na fo´rmula
de acordo com a equivaleˆncia φ→ ψ ≡ ¬φ ∨ ψ. A func¸a˜o impl free e´ apresentada parcialmente a
seguir; os detalhes sa˜o deixados como exerc´ıcio:
Fixpoint impl_free (t:fprop) : fprop :=
match t with
| var p => t
| neg F => (* completar *)
| con P Q => con (impl_free P) (impl_free Q)
| dis P Q => (* completar *)
| imp P Q => (* completar *)
end.
A definic¸a˜o acima utiliza a palavra reservada Fixpoint do Coq [CDT08] utilizada na definic¸a˜o de
func¸o˜es recursivas. A primeira linha da definic¸a˜o diz que impl free e´ uma func¸a˜o recursiva que
recebe um argumento t do tipo fprop, e retorna um outro termo do tipo fprop. A segunda linha e´
responsa´vel por fazer o pattern matching do argumento t com algum dos poss´ıveis construtores. O
primeiro construtor poss´ıvel e´ var. Neste caso, se o argumento t for da forma var p enta˜o nenhuma
42
transformac¸a˜o e´ necessa´ria e a func¸a˜o retorna o pro´prio termo t como resultado. Se o argumento t
for da forma neg F, ou seja for uma negac¸a˜o enta˜o recursivamente devemos eliminar as implicac¸o˜es
existente na subfo´rmula F (os detalhes deste caso sa˜o deixados como exerc´ıcio). Se a fo´rmula t for
uma conjunc¸a˜o da forma con P Q enta˜o devemos recursivamente eliminar as implicac¸o˜es existentes
em cada uma das subfo´rmulas P e Q. Os outros casos (disjunc¸a˜o e implicac¸a˜o) sa˜o deixados como
exerc´ıcio.
A pro´xima etapa consiste na construc¸a˜o da func¸a˜o fnn que recebe como argumento uma fo´rmula
sem implicac¸o˜es (→) e retorna uma fo´rmula equivalente em forma normal negada. A palavra re-
servada Function utilizada abaixo caracteriza uma func¸a˜o recursiva. De fato, Function generaliza
Fixpoint, mas este detalhe na˜o e´ importante aqui, o que precisamos entender na primeira linha
da definic¸a˜o abaixo e´ que fnn e´ uma func¸a˜o recursiva que recebe como argumento uma fo´rmulat
do tipo fprop, e que retorna como resultado uma outra fo´rmula. O texto {measure flength t}
e´ utilizado para informar ao Coq qual a me´trica que diminui a cada chamada da func¸a˜o recursiva,
que neste caso e´ o comprimento da fo´rmula que definimos atrave´s da func¸a˜o flength.
Fixpoint flength (t:fprop) :=
match t with
| var p => 1
| neg F => 1 + (flength F)
| con F G => 1 + (flength F) + (flength G)
| dis F G => 1 + (flength F) + (flength G)
| imp F G => 1 + (flength F) + (flength G)
end.
Function fnn (t:fprop) measure flength t: fprop :=
match t with
| neg(neg F) => (* completar *)
| neg(con F G) => (* completar *)
| neg(dis F G) => (* completar *)
| con F G => (* completar *)
| dis F G => (* completar *)
| _ => t
end.
Na definic¸a˜o da func¸a˜o fnn, primeiro analisamos se a fo´rmula dada como entrada e´ uma negac¸a˜o
de uma negac¸a˜o de uma fo´rmula, ou seja, neg(neg F). Neste caso, sabemos que devemos simples-
mente computar a forma normal negada de F. Quando t for uma negac¸a˜o de uma conjunc¸a˜o (ou de
uma disjunc¸a˜o) precisamos aplicar as lei de de Morgan e recursivamente computar a forma normal
negada de F e G. O u´ltimo caso utiliza o curinga “ ” para dizer que em “qualquer outro caso na˜o
considerado anteriormente”, a pro´pria fo´rmula t deve ser retornada.
A func¸a˜o distr recebe como argumento um par de fo´rmulas t1 e t2 em forma normal negada,
e computa a forma normal conjuntiva da disjunc¸a˜o t1 ∨ t2.
Function distr (t:fprop * fprop)
{measure (fun p => (flength (fst p)) +
(flength (snd p)))}:fprop :=
match t with
43
| (con t11 t12,_) => (* completar *)
| (_,con t21 t22) => (* completar *)
| _ => (* completar *)
end.
A construc¸a˜o da func¸a˜o fnc e´ deixada como exerc´ıcio.
Exerc´ıcios
1. Complete as definic¸o˜es das func¸o˜es impl free, fnn e distr.
2. Construa a func¸a˜o fnc que recebe como argumento uma fo´rmula φ qualquer da lo´gica propo-
sicional e retorna a forma normal conjuntiva de φ.
44
Cap´ıtulo 10
A Lo´gica de Primeira Ordem
A Lo´gica de Primeira Ordem: A necessidade de uma linguagem mais expressiva
O ca´lculo proposicional possui limitac¸o˜es com respeito a codificac¸a˜o de sentenc¸as declarativas. De
fato, o ca´lculo proposicional manipula de forma satisfato´ria componentes das sentenc¸as como na˜o,
e , ou, se . . . enta˜o, mas certos aspectos lo´gicos que aparecem em linguagens naturais ou artificiais
sa˜o muito mais ricos. Por exemplo, como expressar coisas do tipo: “Existe ...” e “Para todo . . . ”
na lo´gica proposicional?
Exemplo 7. Considere a seguinte sentenc¸a declarativa:
Todo estudante e´ mais jovem do que algum instrutor.
Na lo´gica proposicional podemos identificar esta sentenc¸a com uma varia´vel proposicional p. No
entanto, esta codificac¸a˜o na˜o reflete os detalhes da estrutura lo´gica desta sentenc¸a. De que trata
esta sentenc¸a?
• Ser um estudante.
• Ser um instrutor.
• Ser mais jovem do que algue´m.
Para expressar estas propriedades utilizaremos predicados. Por exemplo, podemos escrever
estudante(ana) para denotar que Ana e´ uma estudante. Da mesma forma podemos escrever instru-
tor(marcos) para denotar que Marcos e´ um instrutor. Por fim, podemos escrever jovem(ana,marcos)
para denotar que Ana e´ mais jovem do que Marcos. Nestes exemplos, estudante, instrutor e jovem
sa˜o exemplos de predicados.
Ainda precisamos codificar as noc¸o˜es de “todo” e “algum”. Para isto introduziremos o con-
ceito de varia´vel. Varia´veis sera˜o denotadas por letras latinas minu´sculas do final do alfabeto:
u, v, w, x, y, z (possivelmente acrescidas de sub-´ındices x1, x2, . . .). Varia´veis devem ser pensadas
como “lugares vazios” que podem ser preenchidos (ou instanciados) por elementos concretos, como
joa˜o, maria, etc. Utilizando varia´veis podemos especificar o significado dos predicados estudante,
instrutor e jovem de uma maneira mais formal:
estudante(x): x e´ um estudante.
instrutor(x): x e´ um instrutor.
jovem(x,y): x e´ mais jovem do que y.
45
Note que o nome das varia´veis na˜o e´ importante:
estudante(x): x e´ um estudante.
e´ equivalente a
estudante(y): y e´ um estudante.
Para
que possamos finalmente expressar em detalhes a sentenc¸a apresentada no exemplo precisamos
codificar o significado de Todo e algum em Todo estudante e´ mais jovem do que algum instrutor.
Os quantificadores ∀ e ∃ fazem este trabalho:
∀: significa para todo;
∃: significa existe.
Os quantificadores ∀ e ∃ esta˜o sempre ligados a alguma varia´vel:
∀x: para todo x;
∃x: existe um x (ou existe algum x).
Agora podemos finalmente codificar a sentenc¸a:
Todo estudante e´ mais jovem do que algum instrutor.
da seguinte forma:
∀x(estudante(x)→ (∃y(instrutor(y) ∧ jovem(x, y))))
Note que predicados diferentes podem ter um nu´mero distinto de argumentos: os predicados estu-
dante e instrutor admitem apenas um argumento e por isto sa˜o chamados de predicados una´rios,
enquanto que o predicado jovem admite dois argumentos, e portanto e´ um predicado bina´rio.
O nu´mero de argumentos de um predicado e´ chamado sua aridade. Assim, os predicados una´rios
teˆm aridade 1, enquanto que os predicados bina´rios teˆm aridade 2, etc. No ca´lculo de predicados
sa˜o permitidos predicados com qualquer aridade finita.
Exemplo 8. Considere a sentenc¸a:
Nem todos os pa´ssaros podem voar.
Escolhemos os seguintes predicados para expressar esta sentenc¸a:
passaro(x): x e´ um pa´ssaro.
voar(x): x pode voar.
Esta sentenc¸a pode ser codificada da seguinte forma:
¬(∀x(passaro(x)→ voar(x)))
Exemplo 9. Uma outra maneira de expressar a mesma ide´ia da sentenc¸a anterior e´ dizer que:
Existem alguns pa´ssaros que na˜o podem voar.
Esta u´ltima sentenc¸a pode ser codificada da seguinte maneira:
∃x(passaro(x) ∧ ¬voar(x))
Posteriormente veremos que as duas codificac¸o˜es dadas sa˜o semanticamente equivalentes. De
fato, existem transformac¸o˜es que convertem uma na outra.
46
A lo´gica de primeira ordem: uma linguagem formal
O vocabula´rio da lo´gica de primeira ordem consiste de treˆs conjuntos:
1. Um conjunto P de s´ımbolos de predicado;
2. Um conjunto F de s´ımbolos de func¸a˜o;
3. Um conjunto C de constantes.
onde cada s´ımbolo de predicado e de func¸a˜o vem com sua aridade bem definida. Os predicados
sa˜o casos especiais de func¸a˜o: enquanto as func¸o˜es possuem contra-domı´nio qualquer, os predicados
teˆm contra-domı´nio sempre igual a {V, F}. As constantes sa˜o func¸o˜es de aridade 0.
Definic¸a˜o 19. Termos sa˜o definidos da seguinte forma:
1. Qualquer varia´vel e´ um termo;
2. Se c ∈ F e´ uma func¸a˜o de aridade 0 enta˜o c e´ um termo;
3. Se t1, . . . , tn sa˜o termos e f ∈ F e´ uma func¸a˜o de aridade n > 0 enta˜o f(t1, . . . , tn) e´ um
termo.
4. Nada mais e´ termo.
Em BNF (Backus Naur form) temos:
t ::= x | c | f(t, . . . , t)
onde x percorre o conjunto de varia´veis V, c percorre os s´ımbolos de func¸a˜o de aridade 0 de F e f
percorre os elementos de aridade maior do que 0 de F .
Exemplo 10. Suponha que n, f e g sa˜o s´ımbolos de func¸a˜o de aridade respetivamente igual a 0,
1 e 2. Enta˜o g(f(n), n) e f(g(n, f(n))) sa˜o termos, mas g(n) e f(f(n), n) na˜o sa˜o termos por
violarem as aridades dos s´ımbolos.
A escolha dos conjuntos P e F para s´ımbolos de predicado e de func¸a˜o e´ definida a partir do
que se pretende descrever.
Definic¸a˜o 20. Definimos o conjunto de fo´rmulas sobre o conjunto S = (F ,P) indutivamente da
seguinte forma:
1. Se p ∈ P e´ um s´ımbolo de predicado de aridade n > 0, e se t1, . . . , tn sa˜o termos sobre F
enta˜o p(t1, . . . , tn) e´ uma fo´rmula.
2. Se φ e´ uma fo´rmula enta˜o (¬φ) e´ tambe´m uma fo´rmula.
3. Se φ e ψ sa˜o fo´rmulas enta˜o (φ ∧ ψ), (φ ∨ ψ), (φ→ ψ) e (φ↔ ψ) sa˜o fo´rmulas.
4. Se φ e´ uma fo´rmula e x e´ uma varia´vel enta˜o (∀xφ) e (∃xφ) tambe´m sa˜o fo´rmulas.5. Nada mais e´ fo´rmula.
47
Em BNF temos:
φ ::= p(t1,. . ., tn) | (¬φ) | (φ ∧ φ) | (φ ∨ φ) | (φ→φ) | (φ↔ ψ) | (∀xφ) | (∃xφ)
onde p e´ um s´ımbolo de predicado de aridade n > 0, ti sa˜o termos sobre F e x e´ uma varia´vel.
Convenc¸a˜o 1. Adotaremos a seguinte prioridade de operadores:
1. ¬, ∀, ∃;
2. ∧,∨;
3. →,↔.
Exemplo 11. Considere a seguinte sentenc¸a:
Todo filho de meu pai e´ meu irma˜o.
Podemos codificar esta fo´rmula de pelo menos duas formas distintas:
1. Representando a noc¸a˜o de “pai” como predicado: Neste caso escolhemos treˆs predicados: filho,
pai e irmao com os seguintes significados e aridades:
filho(x, y): x e´ filho de y
pai(x, y): x e´ pai de y
irmao(x, y): x e´ irma˜o de y.
Uma poss´ıvel codificac¸a˜o para a sentenc¸a dada utilizando estes predicados e´:
∀x∀y(pai(x, joao) ∧ filho(y, x)→ irmao(y, joao))
dizendo que: “para todo x e todo y, se x e´ o pai de joao e se y e´ um filho de x enta˜o y e´ um irma˜o
de joao”.
Representando a noc¸a˜o de “pai” como func¸a˜o, que chamaremos de f : Neste caso, f(x) retorna
o pai de x. Note que isto funciona apenas porque o pai de uma dado x e´ u´nico e esta´ sempre
definido, e portanto f e´ realmente uma func¸a˜o. Uma poss´ıvel codificac¸a˜o para esta sentenc¸a e´ dada
por:
∀x(filho(x, f(joao))→ irmao(x, joao))
significando que “para todo x, se x e´ um filho do pai de joao enta˜o x e´ um irmao de joao.
Esta codificac¸a˜o e´ menos complexa que a anterior porque envolve apenas um quantificador.
Especificac¸o˜es formais em geral exigem um domı´nio de conhecimento. Muitas vezes este co-
nhecimento na˜o esta´ explicitado no domı´nio. Sendo assim, um especificador pode desconsiderar
restric¸o˜es importantes para um modelo ou implementac¸a˜o. Por exemplo, as codificac¸o˜es dadas no
exemplo anterior podem parecer corretas, mas e se x for igual a joao? Se o domı´nio de relac¸o˜es
de parentesco na˜o e´ um conhecimento comum o especificador pode na˜o notar que uma pessoa na˜o
pode ser irma˜o dela mesma.
Definic¸a˜o 21. A abrangeˆncia de ∀x (respectivamente, ∃x) em ∀xφ (respectivamente, ∃xφ) e´ φ.
Uma ocorreˆncia de uma varia´vel ligada numa fo´rmula ψ, e´ uma ocorreˆncia de uma varia´vel x,
dentro do campo de abrangeˆncia de um quantificador ∀x ou ∃x. Uma ocorreˆncia de uma varia´vel
livre e´ uma ocorreˆncia de uma varia´vel x na˜o ligada.
48
Exemplo 12. Na fo´rmula ∃x(p(f(x), y) → q(x)), as duas ocorreˆncias da varia´vel x sa˜o ligadas,
enquanto a ocorreˆncia da varia´vel y e´ livre. Na fo´rmula ∃xp(f(x), y)→ q(x) a primeira ocorreˆncia
da varia´vel x e´ ligada, no entanto a segunda e´ livre.
Definic¸a˜o 22. Dada uma varia´vel x, um termo t e uma fo´rmula φ, definimos φ[x/t] como sendo
a fo´rmula obtida apo´s substituir cada ocorreˆncia livre de x em φ por t.
Exemplo 13. Considere novamente a fo´rmula ∀x((p(x)→ q(x)) ∧ s(x, y)), que chamaremos sim-
plesmente de φ. Temos que φ[x/f(x, y)] = φ. De fato, todas as ocorreˆncias de x em φ sa˜o ligadas,
e portanto a substituic¸a˜o [x/f(x, y)] na˜o tem nenhum efeito sobre esta fo´rmula.
Exemplo 14. Agora considere a fo´rmula
(∀x(p(x) ∧ q(x)))→ (¬p(x) ∨ q(y))
que chamaremos simplesmente de ψ. Neste caso temos uma ocorreˆncia livre de x e, portanto
ψ[x/f(x, y)] e´ igual a
(∀x(p(x) ∧ q(x)))→ (¬p(f(x, y)) ∨ q(y))
As substituic¸o˜es podem produzir efeitos colaterais indesejados:
Considere o termo f(x, y) e a fo´rmula ∀y(p(x, y)). Enta˜o (∀y(p(x, y)))[x/f(x, y)] resulta na
fo´rmula (∀y(p(f(x, y), y))) se fizermos uma substituic¸a˜o “ingeˆnua”. Observe que o termo resultante
possui uma semaˆntica diferente da esperada porque a varia´vel y do termo f(x, y) na˜o corresponde
a varia´vel y quantificada universalmente na fo´rmula dada. Como resolver este problema?
Definic¸a˜o 23. Dados um termo t, uma varia´vel x e uma fo´rmula φ, dizemos que t e´ livre para x
em φ se nenhuma ocorreˆncia livre de x em φ esta´ no escopo de ∀y ou ∃y para qualquer varia´vel y
que ocorra em t.
Exemplo 15. Considere a fo´rmula s(x) ∧ ∀y(p(x) → q(y)), que possui duas ocorreˆncias livres de
x. A ocorreˆncia de x mais a esquerda poderia, por exemplo, ser substitu´ıda pelo termo f(y, y),
no entanto a outra ocorreˆncia na˜o poderia ser substitu´ıda por este termo porque tal substituic¸a˜o
acarretaria captura da varia´vel y.
Quando precisamos realizar uma substituic¸a˜o de um termo t que na˜o esta´ livre para uma varia´vel
x em uma fo´rmula φ, o que fazemos e´ renomear as varia´veis ligadas para evitar capturas:
Exemplo 16. No caso do exemplo anterior, a substituic¸a˜o de x por f(y, y) em s(x) ∧ ∀y(p(x) →
q(y)) pode ser resolvida renomeando a varia´vel ligada y da fo´rmula para algum nome novo, por
exemplo w: s(x) ∧ ∀w(p(x)→ q(w)). Agora a substituic¸a˜o pode ser realizada sem provocar captura
de varia´veis.
49
50
Cap´ıtulo 11
Deduc¸a˜o Natural na Lo´gica de
Primeira Ordem
Deduc¸a˜o Natural
As provas a serem realizadas na lo´gica de primeira ordem (LPO) sa˜o semelhantes a`quelas realizadas
no ca´lculo proposicional, exceto que agora precisamos de novas regras para lidar com quantificadores
e com o s´ımbolo de igualdade. Vamos iniciar enta˜o com uma regra para a igualdade. A igualdade
que definiremos aqui na˜o e´ a igualdade sinta´tica, mas a igualdade em termos do resultado de uma
computac¸a˜o. A igualdade neste sentido tambe´m nos permite concluir que um termo e´ igual a ele
mesmo, e esta noc¸a˜o e´ expressa pela seguinte regra:
t = t
(=i)
esta regra representa um axioma ja´ que na˜o depende de nenhuma premissa.
A regra (= i) so´ pode ser utilizada para termos, ja´ que a linguagem da LPO na˜o nos permite
falar em igualdade de fo´rmulas. A regra (= i) na˜o e´ muito u´til por si so´. O que precisamos e´ de
um mecanismo que nos permita substituir iguais por iguais. Por exemplo, suponha que y ∗ (w+2)
seja igual a y ∗w+ y ∗ 2 enta˜o certamente e´ o caso que z ≥ y ∗ (w+2) implica que z ≥ y ∗w+ y ∗ 2.
Podemos expressar este princ´ıpio de substituic¸a˜o pela seguinte regra:
t1 = t2 φ[x/t1]
φ[x/t2]
(=e)
Para aplicar a regra (= e), precisamos que os termos t1 e t2 sejam livres para x em φ. Sempre
que escrevermos φ[x/t] assumimos que t e´ livre para x em φ, pois caso contra´rio esta substituic¸a˜o
na˜o tem sentido. O princ´ıpio da substituic¸a˜o juntamente com as regras para igualdade ja´ formam
um conjunto particularmente poderoso. Por exemplo, com estas regras podemos provar os seguintes
sequentes:
1. t1 = t2 ` t2 = t1
2. t1 = t2, t2 = t3 ` t1 = t3
Prova de t1 = t2 ` t2 = t1:
51
1 t1 = t2 premissa
2 t1 = t1 (= i)
3 t2 = t1 (= e) 1, 2
onde φ e´ x = t1, e portanto na linha 2 temos φ[x/t1].
Note que a representac¸a˜o φ[x/t1] na˜o aparece explicitamente na prova. De fato, o que aparece
nas provas e´ a fo´rmula que se obte´m apo´s realizar a substituic¸a˜o. No caso do exemplo anterior,
φ[x/t1] corresponde a (x = t1)[x/t1] de onde se obte´m t1 = t1 que aparece na linha 2 da prova
anterior.
Prova de t1 = t2, t2 = t3 ` t1 = t3:
1 t2 = t3 premissa
2 t1 = t2 premissa
3 t1 = t3 (= e)1, 2
onde φ e´ t1 = x, e portanto na linha 2 temos φ[x/t2].
Regras para a Quantificac¸a˜o Universal
A regra para a eliminac¸a˜o do quantificador ∀ e´ dada por:
∀xφ
φ[x/t]
(∀xe)
Esta regra nos diz que se ∀xφ e´ verdadeiro, enta˜o podemos substituir x por qualquer termo t (que
seja livre para x em φ), e o resultado φ[x/t] continua sendo verdadeiro.
Exemplo 17. Vejamos que a condic¸a˜o de que t seja livre para x em φ e´ essencial na regra (∀xe).
Suponha que φ tenha a forma ∃y(x < y), onde pretendemos substituir x por y. Vamos supor
que nosso domı´nio de interpretac¸a˜o seja o dos nu´meros inteiros com a relac¸a˜o usual de “menor
que”. A fo´rmula ∀xφ, i.e., ∀x(∃y(x < y)), nos diz que para todo inteiro x, existe um outro inteiro
y maior do que x, o que de fato e´ verdade. No entanto, (sem fazer renomeamentos) a fo´rmula
φ[x/y] e´ igual a∃y(y < y) que nos diz que existe um inteiro que e´ maior do que ele mesmo, que
naturalmente e´ falso. Para contornar este problema poder´ıamos renomear a varia´vel ligada y de φ
para posteriormente fazer a substituic¸a˜o.
A regra para a inclusa˜o da quantificac¸a˜o universal e´ um pouco mais complicada:
x0
...
φ[x/x0]
∀xφ
(∀xi)
Aqui utilizamos caixas novamente, mas neste caso uma caixa serve para estipular o escopo da
varia´vel x0 mais do que o escopo de uma hipo´tese. Esta regra nos diz que: se iniciando com
uma varia´vel “nova” x0, conseguirmos provar que φ[x/x0] enta˜o como x0 e´ uma varia´vel arbitra´ria
podemos concluir ∀xφ. Ale´m disto, nenhuma hipo´tese dentro da caixa pode depender de x0. De
fato, se p(x) e´ uma predicado significando “x e´ positivo”, ao tomarmos por exemplo, como hipo´tese
p(x0) estamos considerando que “x0 e´ positivo” o que tira o seu caracter arbitra´rio.
52
O importante na regra (∀xi) e´ que a varia´vel x0 deve realmente ser “nova” (fresh) e portanto
na˜o pode ocorrer em nenhum lugar fora da caixa. Neste sentido x0 pode ser pensado como um
termo arbitra´rio, e esta prova funciona com qualquer outro termo que coloquemos no lugar de x.
Desta forma podemos concluir ∀xφ.
Exemplos 5.
• p(t),∀x(p(x)→ ¬q(x)) ` ¬q(t).
• ∀x(p(x)→ q(x)), ∀xp(x) ` ∀xq(x).
Regras para a Quantificac¸a˜o Existencial
A regra de inclusa˜o do quantificador existencial e´ dada por:
φ[x/t]
∃xφ
(∃xi)
Esta regra nos diz que podemos deduzir ∃xφ sempre que tivermos φ[x/t] para algum termo t (que
seja livre para x em φ). Do ponto de vista computacional a regra (∃xi) nos diz mais do que
simplesmente ∃xφ. De fato, a fo´rmula ∃xφ expressa o fato de que existe um valor (na˜o especificado)
de x para o qual a fo´rmula φ vale, enquanto que φ[x/t] nos da´ explicitamente uma testemunha t
para tal fato.
A fo´rmula para eliminac¸a˜o da quantificac¸a˜o existencial e´ dada por:
∃xφ
x0 φ[x/x0]
...
χ
χ
(∃xe)
Esta regra nos diz que: sabendo que ∃xφ e´ verdadeiro, temos que φ e´ verdadeira para pelo menos
um “valor” de x. Enta˜o o que fazemos e´ analisar todos os poss´ıveis valores de x, denotando por x0
um valor arbitra´rio de x. Se a partir de φ[x/x0] podemos provar χ sem mencionar x0, enta˜o χ sera´
verdadeira sempre que o valor x0 fizer com que φ[x/x0] seja verdadeira.
Na regra (∃xe) exigimos que x0 na˜o aparec¸a fora da caixa, em particular, x0 na˜o pode ocorrer
em χ. Neste caso, a caixa esta´ controlando duas coisas:
1. o escopo de x0;
2. o escopo da hipo´tese φ[x/x0].
Exemplo 18. Provar a validade do sequente: ∀xφ ` ∃xφ.
1 ∀xφ premissa
2 φ[x/x] (∀xe), 1
3 ∃xφ (∃xi), 2
Exemplos 6.
• ∀x(p(x)→ q(x)), ∃xp(x) ` ∃xq(x).
• ∀x(p(x)→ q(x)), ∃x(r(x) ∧ p(x)) ` ∃x(r(x) ∧ q(x)).
• ∃xp(x), ∀x∀y(p(x)→ q(y)) ` ∀yq(y).
53
Equivaleˆncias
Nesta sec¸a˜o vamos estabelecer as equivaleˆncias entre os quantificadores que sa˜o mais utilizadas.
Algumas delas possuem mais de um quantificador, e portanto este to´pico vai ser u´til para adqui-
rirmos pra´tica na manipulac¸a˜o de quantificadores aninhados. Por exemplo, a fo´rmula ∀x∀yφ deve
ser equivalente a ∀y∀xφ ja´ que ambas dizem que φ deve valer para todos os valores de x e y.Mas o
que dizer, por exemplo, sobre (∀xφ) ∧ (∀xψ) e ∀x(φ ∧ ψ)?
Considere a sentenc¸a: “Nem todos os pa´ssaros podem voar” como
¬∀x(passaro(x)→ voar(x))
e
∃x(passaro(x) ∧ ¬voar(x))
As equivaleˆncias lo´gicas nos ajudara˜o a estabelecer especificac¸o˜es que sa˜o aparentemente diferentes,
mas que dizem a mesma coisa. A seguir apresentaremos algumas equivaleˆncias com as quais voceˆ
deve se familiarizar. Escreveremos φ1 ≡ φ2 como uma abreviac¸a˜o para a validade dos sequentes
φ1 ` φ2 e φ2 ` φ1.
Teorema 6. Sejam φ e ψ fo´rmulas da lo´gica de primeira ordem. Valem as seguintes equivaleˆncias:
1. (a) ¬∀xφ ≡ ∃x¬φ
(b) ¬∃xφ ≡ ∀x¬φ
2. Assumindo que x na˜o ocorra livre em ψ:
(a) (∀xφ) ∧ ψ ≡ ∀x(φ ∧ ψ)
(b) (∀xφ) ∨ ψ ≡ ∀x(φ ∨ ψ)
(c) (∃xφ) ∨ ψ ≡ ∃x(φ ∨ ψ)
(d) (∃xφ) ∨ ψ ≡ ∃x(φ ∨ ψ)
(e) ∀x(ψ → φ) ≡ ψ → ∀xφ
(f) ∃x(φ→ ψ) ≡ (∀xφ)→ ψ
(g) ∀x(φ→ ψ) ≡ (∃xφ)→ ψ
(h) ∃x(ψ → φ) ≡ ψ → ∃xφ
3. (a) ∀xφ ∧ ∀xψ ≡ ∀x(φ ∧ ψ)
(b) ∃xφ ∨ ∃xψ ≡ ∃x(φ ∨ ψ)
4. (a) ∀x∀yφ ≡ ∀y∀xφ
(b) ∃x∃yφ ≡ ∃y∃xφ
Exerc´ıcios
1. Prove a validade dos seguintes sequentes:
(a) (y = 0) ∧ (y = x) ` 0 = x
(b) t1 = t2 ` (t+ t2) = (t+ t1)
54
(c) (x = 0) ∨ ((x+ x) > 0) ` (y = (x+ x))→ ((y > 0) ∨ (y = (0 + x)))
2. Prove a validade dos seguintes sequentes:
(a) ∀xp(a, x, x),∀x∀y∀z(p(x, y, z)→ p(f(x), y, f(z))) ` p(f(a), a, f(a))
(b) ∀xp(a, x, x),∀x∀y∀z(p(x, y, z)→ p(f(x), y, f(z))) ` ∃zp(f(a), z, f(f(a)))
(c) ∀yq(b, y), ∀x∀y(q(x, y)→ q(s(x), s(y))) ` ∃z(q(b, z) ∧ q(z, s(s(b))))
(d) ∀x∀y∀z(s(x, y) ∧ s(y, z)→ s(x, z)),∀x¬s(x, x) ` ∀x∀y(s(x, y)→ ¬s(y, x))
(e) ∀x(p(x) ∨ q(x)), ∃x¬q(x), ∀x(r(x)→ ¬p(x)) ` ∃x¬r(x)
(f) ∀x(p(x)→ (q(x) ∨ r(x))),¬∃x(p(x) ∧ r(x)) ` ∀x(p(x)→ q(x))
(g) ∃x∃y(s(x, y) ∨ s(y, x)) ` ∃x∃ys(x, y)
(h) ∃x(p(x) ∧ q(x)), ∀x(p(x)→ r(x)) ` ∃x(r(x) ∧ q(x))
3. Construa uma prova para cada sequente dado no exerc´ıcio anterior no ProofWeb.
55
56
Cap´ıtulo 12
Semaˆntica da Lo´gica de Primeira
Ordem
Estruturas
Estruturas aparecem em matema´tica rotineiramente. Por exemplo, um grupo e´ um conjunto na˜o-
vazio equipado com duas operac¸o˜es, sendo uma bina´ria, uma una´ria e com um elemento neutro que
satisfaz certas leis. A seguir definiremos formalmente o que sa˜o estruturas, mas iniciaremos com a
definic¸a˜o de relac¸a˜o:
Definic¸a˜o 24. Uma relac¸a˜o R n-a´ria (n ≥ 0) sobre um conjunto na˜o-vazio A e´ um subconjunto
de An.
Definic¸a˜o 25. Uma estrutura A sobre o conjunto S = (F ,P) (de s´ımbolos de func¸a˜o e de relac¸a˜o)
e´ um par (A, a) com as seguintes propriedades:
1. A e´ um conjunto na˜o-vazio chamado de universo ou domı´nio de A.
2. a e´ uma func¸a˜o definida sobre o conjunto S satisfazendo as seguintes propriedades:
(a) para cada constante (func¸a˜o da aridade 0), f ∈ F , associamos um elemento concreto
a(f) de A;
(b) para cada s´ımbolo de func¸a˜o f ∈ F de aridade n > 0, a(f) e´ uma func¸a˜o An para A;
(c) para cada s´ımbolo de relac¸a˜o (predicado) p ∈ P de aridade n > 0, a(p) e´ uma relac¸a˜o
n-a´ria em A, ou seja, um subconjunto de An.
Ao inve´s de a(p), a(f) escreveremos, respectivamente, pA, fA. Uma estrutura A = (A, a) sobre os
conjuntos F = {f1, . . . , fn} e P = {p1, . . . , pm} sera´ escrita na forma A = (A, pA1 , . . . , pAm, fA1 , . . . , fAn ).
Exemplos 7.
1. (R,+, ·, −1, 0, 1) - o corpo dos nu´meros reais.
2. (N,≤) - o conjunto ordenado dos nu´meros naturais.
3. (Z, <,+,−, 0) - o grupo ordenado dos nu´meros inteiros (com a soma usual). Observe que,
neste caso − e´ uma func¸a˜o una´ria, enquanto que + e´ bina´ria.
57
4. (Q, ·, −1, 1) - o grupo (abeliano) dos nu´meros racionais (com a multiplicac¸a˜o usual).
5. (Z,+, ·, −1, 0, 1) - o anel dos nu´meros inteiros.
Observac¸a˜o 1. Notac¸a˜o: |A| = A, o universo de A. A estrutura A e´ dita (in)finita se o seu
universo e´ (in)finito.
Definic¸a˜o 26. Uma func¸a˜o de atribuic¸a˜o (ou designac¸a˜o) em uma estrutura A e´ uma func¸a˜o
l : var → A. Denotaremos por l[x 7→ a] a func¸a˜o de atribuic¸a˜o que leva x em a e qualquer outro
valor y e´ levado em l(y).
Definic¸a˜o 27. Uma interpretac¸a˜o I e´ um par (A, i), onde A e´ uma estrutura e i e´ uma designac¸a˜o.
Exemplo 19. Por exemplo, se a interpretac¸a˜o I = (A, i) e´ tal que A = (N, <,+, ·, 0, 1) e i(vn) = 2n
enta˜o a fo´rmula v2 · (v1 + v2) = v4 e´ lida como 4 · (2 + 4) = 8. Ja´ a fo´rmula ∀v0∃v1(v0 < v1) e´ lida
como “para todo nu´mero natural v0 existe um nu´mero natural v1 maior do que v0”.
Exerc´ıcios
1. Considere a interpretac¸a˜o I dada no exemplo anterior. Como as fo´rmulas a seguir sa˜o lidas
com esta interpretac¸a˜o?
(a) ∃v0(v0 + v0 = v1)
(b) ∃v0(v0 · v0 = v1)
(c) ∃v1(v0 = v1)
(d) ∀v0∃v1(v0 = v1)
(e) ∀v0∀v1∃v2(v0 < v1 ∧ v2 < v1)
Modelos
A noc¸a˜o de satisfac¸a˜o