Tutorial Prático Sobre o Metodo de Deducao Natural

Prévia do material em texto

Lógica para 
Ciência da 
Computação 
MÉTODO DE DEDUÇÃO NATURAL 
 2 
UNIVERSIDADE FEDERAL FLUMINENSE 
CENTRO DE ESTUDOS GERAIS 
INSTITUTO DE MATEMÁTICA 
DEPARTAMENTO DE ANÁLISE 
 
 
 
 
 
 
TRABALHO DE MONITORIA 
 
 
 
 
 
Tutorial Prático sobre o 
Método de Dedução 
Natural 
 
 
 
 
 
 
 
 
Disciplina: Lógica para Ciência da Computação 
Monitor: Ariel Alves da Fonseca 
Professor Orientador: Marcelo da Silva Corrêa 
Período: Ano letivo de 2003 
 
MÉTODO DE DEDUÇÃO NATURAL 
 3 
 
 
 
Resumo 
 
 O Método de Dedução Natural é um dos tópicos tratados no curso de Lógica para 
Ciência da Computação, oferecido pelo Departamento de Análise. A carência de livros 
didáticos em português que abordam este método, usando árvores de prova, nos fez 
construir esse tutorial prático, tendo como objetivo principal oferecer a alunos e professores 
da disciplina um material didático complementar sobre o assunto. O texto é baseado na 
apresentação das técnicas básicas para construção de provas no sistema de dedução natural 
por meio de exemplos e discussão de estratégias simples. 
 
 
 
 
 
 
 
 
 
 
MÉTODO DE DEDUÇÃO NATURAL 
 4 
Dedução Natural 
 
 
Sistema de Dedução Natural 
 
A dedução natural é um método de demonstração introduzido independentemente 
por Gerhard Gentzen em 1935 e Stanislaw Jaskowski em 1934. Os sistemas de dedução 
natural caracterizam-se, entre outros aspectos, por não apresentarem um conjunto de 
axiomas, mas apenas um conjunto de regras de inferências. Neste tutorial apresentaremos 
um conjunto de regras primitivas de dedução natural, reservando para o final algumas 
regras derivadas. 
No sistema de dedução natural as regras de inferência são projetadas num padrão de 
regras de introdução e eliminação de conectivos e quantificadores, que são combinadas 
para a construção de uma prova. 
 
 Podemos representar as provas por árvores, sobrepondo as instâncias das regras de 
inferência utilizadas na sua obtenção. 
 Deixaremos um espaço reservado para inserir as premissas e as hipóteses geradas no 
processo. Esse espaço é chamado de base de premissas e hipóteses. 
 
Portanto, graficamente, uma prova possuirá a seguinte forma: 
 
 
 
 
 
 
 
 
 
 
A figura anterior mostra uma prova com apenas um ramo, mas uma prova pode ter vários 
ramos, dependendo da regra considerada, como é exemplificado na figura seguinte: 
 
 
 
 
 
 
 
 
 
 
 
Conclusão 
[Premissas e Hipóteses] 
. 
. 
. 
Premissas e Hipóteses 
Base de Premissas e Hipóteses 
Conclusão 
[Premissas e Hipóteses] 
. 
. 
. 
Premissas e Hipóteses 
Base de Premissas e Hipóteses 
. 
. 
. 
[Premissas e Hipóteses] 
1º ramo 2º ramo 
MÉTODO DE DEDUÇÃO NATURAL 
 5 
 
 
 É importante perceber que as hipóteses geradas especificamente no 1º ramo não 
poderão ser usadas no 2º ramo e vice-versa, ou seja, os ramos de prova são independentes. 
 
 
As regras de inferência 
 
 O Sistema de Dedução Natural para a Lógica Sentencial dispõe de onze regras 
básicas de inferência, que podem ser divididas em dois grupos: as regras não hipotéticas, e 
as regras hipotéticas. 
 
As regras não hipotéticas 
 
 Nesta seção introduziremos oito das onze regras básicas de inferência. 
 
Eliminação da implicação(→E): De um condicional e seu antecedente, podemos inferir seu 
conseqüente. Esta regra também é chamada de Modus Ponens, que abreviamos por ‘MP’. 
 
 
 
 
 
Exemplo: 
 
Prove: 
p, q →→→→ r, p →→→→ q r 
 
 
 
 
 
 
Usamos a regra → E em q e q → r, podemos inferir r, e da mesma forma, provar q a 
partir das premissas p e p → q, usando a mesma regra. 
 
Eliminação da negação(~E) : De uma sentença ~~φ, podemos inferir φ. 
 
 
 
 
 
 
 
 
φ φ →→→→ ψ 
ψ 
→→→→E 
p p →→→→ q →→→→E 
q q →→→→ r →→→→E 
r 
p, 
q →→→→ r 
p →→→→ q 
φ 
~~φ 
~E 
MÉTODO DE DEDUÇÃO NATURAL 
 6 
Exemplo: 
 
Prove: 
 ~p → ~~q , ~~~p q 
 
 
 
 
 
 
 
 
 
 
 Observe que a regra ~E não permite inferir ‘~p→q’ a partir de ‘~p → ~~q’, pois a 
premissa é uma sentença condicional. Assim, precisamos primeiro inferir ‘~~q’, por 
aplicação da regra →E, e desta forma usar ~E para inferir ‘q’. 
 
Introdução da conjunção (∧∧∧∧I): De quaisquer sentenças φ e Ψ, podemos inferir a 
conjunção φ ∧ Ψ. 
 
 
 
 
 
Eliminação da conjunção (∧∧∧∧E): De uma conjunção podemos inferir qualquer um dos seus 
componentes. 
 
 
 
 
 
Exemplo: 
 
p ∧ q q ∧ p 
 
 
 
 
 
 
 
Introdução da disjunção (∨∨∨∨I ) : Podemos inferir uma disjunção a partir de qualquer um de 
seus componentes. 
 
 
 ~~~p 
 
 ~p 
~E 
~~q 
q 
~E 
~p →→→→ ~~q →→→→E 
~p → ~~q 
 ~~~p 
 
 φ ψ 
∧I 
φ ∧ψ 
 
 φ ∧ψ 
∧∧∧∧E 
 φ 
 
 φ ∧ψ 
∧∧∧∧E 
 ψ 
 
 p ∧q 
∧∧∧∧E 
 q 
 
 p ∧q 
∧∧∧∧I 
∧∧∧∧E 
 p 
 
 p ∧q 
φ 
φ ∨ ψ 
∨∨∨∨I 
p ∧ q 
ψ 
φ ∨ ψ 
∨∨∨∨I 
MÉTODO DE DEDUÇÃO NATURAL 
 7 
 
 
 
Exemplo: 
 
p (p∨q) ∨ (p∨r) 
 
 
 
 
 
 
 
 
 
Introdução do bimplicação (↔↔↔↔I): A partir de sentenças (φ→ψ) e (ψ→φ) podemos inferir 
(φ↔ψ). 
 
 
 
 
 
Eliminação do bimplicação (↔↔↔↔E): A partir de uma sentença da forma (φ↔ψ) podemos 
inferir tanto (φ→ψ) quanto (ψ→φ). 
 
 
 
 
 
 
Exemplo: 
 
p↔(q∨r), q p 
 
 
 
 
 
 
p 
p ∨ q 
∨∨∨∨I 
∨∨∨∨I 
(p∨q) ∨ (p∨r) 
 
p 
φ→ψ 
ψ↔φ 
 ↔↔↔↔E 
 ↔↔↔↔I ψ→φ φ→ψ 
ψ↔φ 
q 
 ∨∨∨∨I ↔↔↔↔E 
 →→→→E 
p↔(q∨r) 
(q∨r) (q∨r)→p 
 p 
p↔(q∨r) 
q 
ψ→φ 
ψ↔φ 
 ↔↔↔↔E 
MÉTODO DE DEDUÇÃO NATURAL 
 8 
 
 
 
 
 
Introdução do ⊥⊥⊥⊥(⊥⊥⊥⊥I): Introduzimos o símbolo ⊥ para identificar a derivação de uma 
contradição. 
 
 
 
 
 
 
 
Regras Hipotéticas 
 
 Agora introduziremos as três regras restantes que completam as regras de inferência 
para o Lógica Sentencial. 
 As regras de introdução da implicação(→I) e da negação (~I) diferem das outras, 
pois elas empregam um raciocínio hipotético, ou seja, devemos construir uma prova de uma 
sentença tomando outra como uma hipótese local. A hipótese é descartada após a aplicação 
da regra e isto é denotado por um traço transversal sobre ela. Cada hipótese é numerada e 
seu identificador é colocado na barra que discrimina a aplicação da regra hipotética que 
permitiu sua adoção. 
 
Introdução da implicação (→→→→I) : Dada uma derivação de uma sentença φ obtida ao 
tomarmos como hipótese uma sentença ψ, podemos inferir ψ→φ (descartando a hipótese 
após a aplicação da regra). 
 
 
 
 
 
 
 
 
 
Exemplo: 
 
p→q, q→ r p→r 
 
 
 
 
 
[ψ]1 
 →→→→I (1) 
. 
. 
. 
φ 
ψ → φ 
p→q 
q→ r 
[p] 1 
 
[p]1 p→q 
 p→r 
r 
 q q→r 
 →→→→I 
 →→→→E 
(1) 
⊥ 
ψ ~ψ 
⊥ I 
MÉTODO DE DEDUÇÃO NATURAL 
 9 
 
 
Introdução da Negação (~I) : Dada uma derivação de uma contradição a partir de uma 
hipótese ~φ, podemos descartar a hipótese e inferir φ. 
 
 
 
 
 
 
 
Exemplo: 
 
p→q, ~q ~p 
 
 
 
 
 
 
 
 
 Observe que somente a partir das premissas dadas não concluiriamos a sentença 
‘~p’, logo tentamos uma prova indireta, colocando como hipótese ‘p’. Isso nos permitiu 
concluir a prova facilmente. 
Eliminação da disjunção(∨∨∨∨E):De uma sentença da forma φ ∨ ψ, podemos inferir uma 
sentença θ se obtivermos uma derivação para θ, tomando φ como hipótese, e uma outra 
derivação de θ, tomando ψ como hipótese. 
 
 
 
 
 
 
 
 
Observe o seguinte argumento: 
 
 Hoje é sábado ou domingo. 
 Se hoje é sábado, então é fim de semana. 
 Se hoje é domingo, então é fim de semana. 
∴∴∴∴ É fim de semana. 
 
 
 
 
 
φ 
 ⊥ 
. 
. 
. 
[~φ]1 
 ~I (1) 
θ θ 
∨∨∨∨E 
 [φ]1 [ψ]2 
 . . 
 . . 
 . . 
φ ∨ ψ (1) (2) 
θ 
~p 
⊥ 
q ~q 
[p] 1 p →q 
 →→→→E 
 ~ I 
 ⊥⊥⊥⊥ I 
(1) 
p→q 
~q 
[p]1 
MÉTODO DE DEDUÇÃO NATURAL 
 10 
Formalizando o argumento teríamos: 
 
 
 
 
 
 
 
 
 
Uma prova para o argumento acima seria: 
 
 
p ∨ q, p → r, q → r r 
 
 
 
 
 
 
 
 
 
 
 
Erro comum ao tentar provar uma sentença a partir de uma disjunção : Extrair um 
componente da disjunção como nas formas abaixo. 
 
 
 
 
 
 
 
 Em ambos os casos, a inferência feita não é correta. Note que somente a partir da 
premissa ‘hoje é sábado ou domingo’, não podemos concluir que ‘hoje é sábado’ ou da 
mesma forma, não podemos concluir que ‘hoje é domingo’. 
 
Resumimos, na tabela seguinte, a coleção de regras de inferência para LS: 
 
 
 
 
 
 p ∨ q 
 p → r 
 q → r 
 r 
p : Hoje é sábado. 
q: Hoje é domingo. 
r: É fim de semana. 
 
p ∨ q 
p 
p ∨ q 
q 
ou 
 r 
 →→→→I 
 r 
[q]2 q → r [p]1 p → r 
 r 
 
→→→→I 
 p ∨ q (1) (2) ∨∨∨∨E 
p∨q 
p→r 
q→r 
[p]1 
[q]2 
MÉTODO DE DEDUÇÃO NATURAL 
 11 
Eliminação da implicação(→E) 
 
 
 
 
Introdução da implicação (→I) 
 
 
 
 
 
 
 
 
 
 
 
Eliminação da negação(~E) 
 
 
 
Introdução da negação (~ I) 
 
 
 
 
 
 
 
 
Introdução da conjunção (∧I) 
 
 
 
 
 
Eliminação da conjunção (∧E) 
 
 
 
 
 
 
 
Introdução da disjunção (∨I ) 
 
 
 
 
 
 
 
 
Eliminação da disjunção(∨E) 
 
 
 
 
 
 
 
 
 
 
 
φ φ →→→→ ψ 
ψ 
→→→→E 
φ 
~~φ 
~E 
 φ ψ 
∧∧∧∧I 
φ ∧ψ 
 
 φ ∧ψ 
∧∧∧∧E 
 φ 
 
φ 
φ ∨ ψ 
∨∨∨∨I 
θ θ 
∨∨∨∨E 
 [φ]1 [ψ]2 
 . . 
 . . 
 . . 
φ ∨ ψ (1) (2) 
θ 
[ψ]1 
 →→→→I (1) 
. 
. 
. 
φ 
ψ → φ 
φ 
 ⊥ 
. 
. 
. 
[~φ]1 
 ~ I (1) 
MÉTODO DE DEDUÇÃO NATURAL 
 12 
Introdução do bimplicação (↔I) 
 
 
 
 
 
 
Eliminação do bimplicação (↔E) 
 
 
 
 
 
 
 
 
 
 
 
Introdução do ⊥ 
 
 
 
 
 
 
 
Tabela 1. 
 
 
 
 
Como obter uma prova? 
 
 Não existe uma forma única de construir uma prova. Se um dado tipo de argumento 
é válido, então existem várias formas de prová-lo. A utilização de estratégias na busca por 
uma prova poderá facilitar a sua obtenção. Podemos destacar duas estratégias gerais, 
chamadas de análise e síntese, descritas a seguir. 
 
 
Síntese - inspeciona-se a conclusão buscando observar um modo de derivá-la a partir das 
 premissas e hipóteses. 
 
 
 
 
 
 
 
 
 
 
Premissas e Hipóteses 
. 
. 
. 
 
 ↔↔↔↔I ψ→φ φ→ψ 
ψ↔φ 
⊥ 
ψ ~ψ 
⊥⊥⊥⊥ I 
Conclusão 
φ→ψ 
ψ↔φ 
 ↔↔↔↔E 
ψ→φ 
ψ↔φ 
 ↔↔↔↔E 
ou 
MÉTODO DE DEDUÇÃO NATURAL 
 13 
 
 
Análise – inspeciona-se as premissas e hipóteses buscando um meio de derivar a conclusão. 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplos Resolvidos: 
 
Observação 
 
 Quando for utilizada a estratégia de análise, a sentença analisada será descrita com 
um tamanho maior de letra para contribuir na sua visualização. Em alguns casos será 
destacada apenas parte de uma sentença, para mostrar que a sentença alvo pode ser 
derivada especificamente daquela em destaque. 
 
Prove: 
 
~p→(q→r), ~p, q r 
 
 
 
 
 
 
 Este é um exemplo típico da utilização da estratégia de análise. Como a conclusão é 
atômica devemos tentar derivá-la a partir das premissas. 
 
 Após a consulta à base de premissas e hipóteses perceberemos a ocorrência das 
sentenças ‘q’ e ‘q→r’, a partir das quais, usando a regra →E, podemos inferir ‘r’. 
 
 
 
 
 
 
 
Premissas e Hipóteses 
. 
. 
. 
 
 
Conclusão 
 
r 
~p→(q→r) 
~p 
 q 
r 
q q→r →→→→E 
análise 
~p→(q→r) 
~p 
q 
MÉTODO DE DEDUÇÃO NATURAL 
 14 
 
 
 
 
 
A sentença ‘q’ é uma premissa, e por isso não precisa ser provada. Entretanto, a 
sentença ‘q→r’ é apenas parte de uma premissa. Como provar ‘q→r’ ? Podemos usar duas 
estratégias, análise ou síntese. No entanto, a sentença alvo é molecular, então poderíamos 
começar tentando uma estratégia de síntese, aplicando a regra → I. 
 
 
 
 
 
 
 
 
 
 
 
 
Observe que neste passo não houve uma progressão para uma solução, pois 
retornamos a situação inicial. Mudaremos de estratégia, vamos tentar análise, ou seja, 
provar ‘q→r’ a partir das premissas. 
 
 
 
 
 
 
 
 
 
 
 
Ao inspecionarmos a base de premissas e hipóteses, encontramos as sentenças ‘~p’, 
e ‘~p→(q→r)’ e a partir delas, usando a regra →E, podemos inferir ‘q→r’: 
 
 
 
 
 
 
 
 
 
~p→(q→r) 
~p 
q 
[q]1 
r 
q q → r 
r →→→→I 
→→→→E 
(1) 
síntese 
r 
q q→r →→→→E 
~p→(q→r) 
~p 
q 
r 
q q→r →→→→E 
~p→(q→r) 
~p 
q 
~p→(q→r) ~p 
→→→→E 
análise 
MÉTODO DE DEDUÇÃO NATURAL 
 15 
 
 
 
Neste ponto a prova deve ser finalizada, pois o todo de todos os ramos da árvore é 
composto apenas por premissas ou hipóteses. 
 
Prove: 
 
(p∧q)→(r→s), ~~p, q s 
 
 
 
 
 
 
 
 
 Ao inspecionarmos a base de premissas e hipóteses, notamos que é possível inferir a 
sentença ‘s’ a partir da sentença ‘r∧s’. 
 
 
 
 
 
 
 
 
 
 
Neste passo, a sentença alvo é ‘r∧s’. Inspecionando a base de premissas e hipóteses, 
percebemos a existência da sentença ‘(p∧q)→(r∧s)’. Logo, se obtivermos a sentença ‘p∧q’ 
podemos inferir a sentença alvo ‘(r∧s)’. 
 
 
 
 
 
 
 
 
 
 
 A sentença alvo nesta etapa será ‘p∧q’. Como a sentença é uma conjunção, 
podemos começar tentando uma estratégia de síntese, pois se obtivermos cada componente 
da conjunção podemos provar a sentença alvo. 
 
s 
(p∧q)→(r∧s) 
~~p 
q 
s 
r∧s 
∧∧∧∧E 
(p∧q)→(r∧s) 
~~p 
q 
análise 
s 
r∧s 
→→→→E (p∧q)→(r∧s) 
~~p 
q 
(p∧q)→(r∧s) p∧q 
∧∧∧∧E 
análise 
MÉTODO DE DEDUÇÃO NATURAL 
 16 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Inspecionando a base de premissas é hipóteses notamos que podemos provar a 
sentença ‘p’ a partir da premissa ‘~~p’. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Neste ponto a prova pode ser finalizada. 
 
Observação: 
 
 Uma premissa pode ser usada várias vezes em uma mesma prova, e não há restrição 
na utilização de premissas em ramos diferentes. Mas o mesmo não ocorre em relação às 
hipóteses, estas devem ser usadas apenas nos ramos em que foram geradas. 
 Na prova abaixo exemplificaremos a utilização de uma mesma premissa em ramos 
distintos. 
 
Prove: 
 
p p∧ps 
r∧s 
→→→→E (p∧q)→(r∧s) 
~~p 
q 
(p∧q)→(r∧s) p∧q 
∧∧∧∧E 
p q ∧∧∧∧I 
síntese 
p∧p 
p 
s 
r∧s 
→→→→E (p∧q)→(r∧s) 
~~p 
q 
(p∧q)→(r∧s) p∧q 
~E 
p q ∧∧∧∧I 
~~p 
análise 
MÉTODO DE DEDUÇÃO NATURAL 
 17 
 
 
 
 
 
A conclusão é uma conjunção, logo devemos procurar as regras associadas a este 
conectivo. Note que se obtivermos cada componente da disjunção e usarmos a regra ∧I 
poderemos inferir a sentença ‘p∧p’. 
 
 
 
 
 
 
 
 
 Neste passo devemos focalizar a sentença ‘p’ do ramo direito. Entretanto, ‘p’ é uma 
premissa, logo não precisa ser provada. O mesmo ocorre para a sentença do ramo esquerdo, 
que também é uma premissa. Logo, a prova está finalizada. 
 
Um fato importante a ser percebido é que a premissa ‘p’ foi usada duas vezes na 
prova, sem haver restrições de ramos. 
 
 
 
Prove: 
 
p, ~~(p→q) (r∧s)∨q 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Como o conetivo principal da conclusão é uma sentença disjuntiva, podemos 
começar tentando provar ao menos um dos componentes da disjunção. Mas qual 
componente devemos escolher? A resposta é bem simples, o que mais se adeqüe à base de 
premissas é hipóteses. Observe que, neste caso, temos duas opções: provar a sentença ‘r∧s’ 
ou provar a sentença‘q’. 
p∧p 
p 
p p (∧∧∧∧I ) 
(r∧s)∨q 
p 
~~(p→q) 
MÉTODO DE DEDUÇÃO NATURAL 
 18 
Mas é importante notar que as sentenças ‘r’ e ‘s’ não ocorrem na base de premissas 
e hipóteses, logo seria uma péssima escolha optar pela conjunção delas. 
 
 
 
 
 
 
 
 
 
 
 Neste passo devemos focalizar a sentença ‘q’. Como ‘q’ é uma sentença atômica, 
podemos tentar derivá-la a partir das premissas. Ao inspecionar a base de premissas e 
hipóteses, notamos que podemos extrair ‘q’ a partir de parte da sentença ‘~~(p→q)’. 
 
 
 
 
 
 
 
 
 
 
Podemos considerar como sentença alvo a sentença ‘p’, mas esta é uma das 
premissas da base de premissas e hipóteses, logo, não precisamos prová-la. 
Assim, a sentença alvo passa a ser ‘(p→q)’ que pode se derivada a partir da 
premissa ‘~~(p→q), aplicando a regra ~ - E. 
 
 
 
 
 
 
 
 
 
 
 
 
 Como ‘~~(p→q)’ é uma premissa então a prova está finalizada. 
 
(r∧s)∨q 
p 
~~(p→q) 
q ∨∨∨∨I 
(r∧s)∨q 
p 
~~(p→q) 
q ∨∨∨∨I 
(p→q) p →→→→E 
(r∧s)∨q 
p 
~~(p→q) 
q ∨∨∨∨I 
(p→q) p →→→→E 
~~(p→q) ~E 
MÉTODO DE DEDUÇÃO NATURAL 
 19 
 
 
Quando aplicar a regra de eliminação do ∨∨∨∨? 
 
 
Nas provas em que a base de premissas possui sentenças disjuntivas devemos ter um 
pouco de cautela, pois uma sentença disjuntiva, quando eliminada pela regra ∨E , duplica a 
quantidade de ramos existentes na prova, dificultando a realização da derivação. Desta 
forma surge a necessidade de analisar a melhor hora de utilizar este tipo de sentença. 
Podemos tentar aplicar a regra ∨E no começo da prova, pois sempre conseguiremos 
demonstrar a validade de um argumento desta forma, mas não se esqueça dos custos 
associados à utilização desta técnica. Os dois exemplos seguintes ilustram a utilização da 
regra ∨E. 
 
Prove: 
 
p∨p, p→(q∧r) r 
 
 
 
 
 
 
 
 
 
 
 
 
Como temos uma premissa disjuntiva, então, primeiramente, vamos usar a regra ∨E, 
sobre ‘p∨p’ buscando obter duas derivações independentes para r, tomando como hipótese 
em cada uma delas um componente da disjunção. 
 
 
 
 
 
 
 
 
 
 
 
 
r 
p∨p 
p→(q∧r) 
p∨p 
p→(q∧r) 
[p]1 
r 
r r p∨p ∨∨∨∨E (1)(2) 
MÉTODO DE DEDUÇÃO NATURAL 
 20 
 Neste passo a sentença alvo será ‘r’, no entanto, como a sentença alvo é atômica, 
então podemos tentar uma estratégia de síntese. 
Inspecionando a base de premissas é hipóteses, notamos a ocorrência de ‘r’ na 
premissa ‘p→(q∧r)’ , mais especificamente em seu conseqüente, logo a partir da sentença 
‘(q∧r)’ e a regra do ∧E podemos inferir a sentença alvo. 
 
 
 
 
 
 
 
 
 
 
 
 A sentença alvo nesta etapa é ‘q∧r’. Observando a base de premissas e hipóteses 
notamos que a sentença alvo pode ser provada a partir da premissa ‘p→(q∧r)’ e da 
hipótese ‘p’ após a aplicação da regra →E. 
 
 
 
 
 
 
 
 
 
 
De forma análoga provamos r tomando como hipótese o segundo componente da disjunção, 
no ramo da direita: 
 
 
 
 
 
 
Note que o topo de cada ramo da árvore é composto apenas por hipóteses 
descartadas ou premissas por isso a prova deve ser finalizada. 
 
A prova contém duas “sub-provas” idênticas. Caso tivéssemos utilizado a 
eliminação do ∨ apenas quando necessário, como no exemplo seguinte, obteríamos uma 
prova ligeiramente mais curta. 
 
 
 
p∨p 
p→(q∧r) 
[p]1 
r 
r r p∨p ∨∨∨∨E (1)(2) 
(q∧r) ∧∧∧∧E 
p∨p 
p→(q∧r) 
[p]1 
[p]2 
r 
r r p∨p ∨∨∨∨E (1)(2) 
(q∧r) ∧∧∧∧E (q∧r) ∧∧∧∧E 
p→(q∧r) [p]1 p→(q∧r) [p]2 →→→→E →→→→E 
p∨p 
p→(q∧r) 
[p]1 
 
r 
r r p∨p ∨∨∨∨E (1)(2) 
(q∧r) ∧∧∧∧E 
p→(q∧r) [p]1 →→→→E 
MÉTODO DE DEDUÇÃO NATURAL 
 21 
 
 
 
 
 
 
 
 
 
 
Observação: 
 
 A partir deste ponto alguns passos mais simples serão omitidos no comentário, para 
evitar que a leitura se torne monótona. Mas caso tenha dúvidas, de como realizar certa 
etapa, busque rever os exemplos anteriores. 
 
Prove: 
 
(p∧q) ∨ (p∧r) p ∧ (q∨ r) 
 
 
 
 
 
 
 
 
Nesta prova podemos usar a regra do ∨E, pois existe uma única premissa é a 
conclusão é uma conjunção. 
 
 
 
 
 
 
 
 
 
 
 
Neste ponto tentaremos provar a sentença alvo ‘p∧(q∨r)’ a partir das sentenças ‘p’ e 
‘q∨r’, utilizando a regra ∧ I. 
 
 
 
 
p∧(q∨r) 
(p∧q) ∨ (p∧r) 
p∧(q∨r) 
(p∧q) ∨ (p∧r) 
[p∧q]1 
(p∧q) ∨ (p∧r) p∧(q∨r) 
 
p∧(q∨r) 
 
∨∨∨∨E (1)(2) 
r 
q∧r 
p 
 
p→q∧r 
p∨p 
 (1)(2) 
[p]1 [p]2 
∧ E 
∨∨∨∨ E 
→→→→ I 
p∧(q∨r) 
(p∧q) ∨ (p∧r) p∧(q∨r) 
 
p∧(q∨r) 
 
∨∨∨∨E (1)(2) 
p q∨r 
∧∧∧∧I 
(p∧q) ∨ (p∧r) 
[p∧q]1 
MÉTODO DE DEDUÇÃO NATURAL 
 22 
 
 
 
 
Continuamos a tentativa de construção de uma prova desenvolvendo o ramo mais a 
esquerda. Podemos escolher como sentença alvo ‘p’, que pode ser derivada a partir da 
hipótese 1, pela regra ∧E. 
Analisando a outra parte do ramo da esquerda, temos como sentença alvo ‘q∨r’ que 
pode ser derivada de um de seus componentes. No entanto, a escolha de qual componente 
desta disjunção deveremos provar é feita inspecionado a base de premissas de hipóteses, 
verificando qual componente pode ser mais facilmente obtido. Neste caso é a sentença ‘q’, 
visto que ela ocorre na hipótese 1, que é uma conjunção. 
 
 
 
 
 
 
 
 
 
 
 
 
Finalizamos a prova do ramo esquerdo, descartando a hipótese [p∧q]1, que não 
poderá ser utilizada na prova do outro ramo. 
Agora tentaremos obter uma prova referente ao ramo mais a direita. Neste ramo a 
sentença alvo é ‘p∧(q∨r)’, que é uma conjunção, e deveremos prová-la tomando como 
hipótese [p∧r]2, o outro componente da disjunção. Se observarmos atentamente as 
sentenças envolvidas para a prova neste ramo, perceberemos que são bem parecidas com as 
sentenças utilizadas no ramo esquerdo, com uma pequena, mas crucial, diferença, as 
hipóteses locais são distintas. 
 
 
 
 
 
 
 
 
 
 
 
Neste passo, temos que escolher com qual componente da disjunção devemos tentar 
provar. Entretanto note que a sentença ‘r’ pode ser facilmente inferida a partir da hipótese 
2. 
p∧(q∨r) 
(p∧q) ∨ (p∧r) 
[p∧q]1 
 
(p∧q) ∨ (p∧r) p∧(q∨r) 
 
p∧(q∨r) 
 
∨∨∨∨E (1)(2)p q∨r 
∧∧∧∧I 
[p∧q]1 q 
∨∨∨∨I 
[p∧q]1 
∧∧∧∧ E 
p∧(q∨r) 
(p∧q) ∨ (p∧r) 
[p∧q]1 
[p∧r]2 
(p∧q) ∨ (p∧r) p∧(q∨r) 
 
p∧(q∨r) 
 
∨∨∨∨E (1)(2) 
p q∨r 
∧∧∧∧ I 
[p∧r]2 q 
∨∨∨∨I 
p 
[p∧q]1 
[p∧q]1 
q∨r 
∧∧∧∧ E 
∧∧∧∧ I 
∧∧∧∧ E 
MÉTODO DE DEDUÇÃO NATURAL 
 23 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Neste ponto a prova está finalizada, pois todos os ramos já foram concluídos. 
 
Prove: 
 
p ↔ ~q ~(p∧q) 
 
 
 
 
 
 
 
 
 
 Nesta prova, utilizaremos a regra ~I, pois a sentença é uma negação. 
 
 
 
 
 
 
 
 
 
 
 
 Agora devemos escolher com quais sentenças formaremos uma contradição. 
Inspecionando a base de premissas e hipóteses perceberemos que podemos extrair a 
sentença ‘~q’ a partir da premissa ‘p↔~q’ e extrair ‘q’ a partir da hipótese 1. 
 
 
 
 
p∧(q∨r) 
~(p∧q) 
p↔~q 
(p∧q) ∨ (p∧r) 
[p∧q]1 
[p∧r]2 
(p∧q) ∨ (p∧r) p∧(q∨r) 
 
p∧(q∨r) 
 
∨∨∨∨E (1)(2) 
p q∨r 
∧∧∧∧ I 
[p∧r]2 q 
∨∨∨∨I 
[p∧q]1 
p 
r 
[p∧r]2 
[p∧q]1 
q∨r 
∧∧∧∧ E 
∧∧∧∧ I 
∨∨∨∨I 
∧∧∧∧ E 
~(p∧q) 
p↔~q 
[p∧q]1 
⊥ 
~I (1) 
MÉTODO DE DEDUÇÃO NATURAL 
 24 
 
 
 
 
 
 
 
 
 
 
 Neste passo poderíamos tentar provar o ramo da esquerda, desta forma, a sentença 
‘q’ pode ser derivada a partir da hipótese 1 utilizando a regra ∧ E. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Como provar a sentença ‘~q’? Analisando a base de premissas e hipóteses notamos 
que ‘~q’ pode ser derivada da premissa ‘p↔~q’ aplicando algumas regras, como realizado 
logo abaixo: 
 
 
 ∧∧∧∧ E 
 
 
 
 
 
 
 
 
 
Neste ponto a prova está finalizada, pois todos os ramos já foram provados. 
 
 
 
 
 
~(p∧q) 
p↔~q 
[p∧q]1 
⊥ 
q ~q 
~I 
⊥⊥⊥⊥- I 
(1) 
~(p∧q) 
p↔~q 
[p∧q]1 
⊥ 
q ~q 
~I 
⊥⊥⊥⊥ I 
(1) 
[p∧q]1 
∧∧∧∧ E 
~(p∧q) 
p↔~q 
[p∧q]1 
⊥ 
q ~q 
~I 
⊥⊥⊥⊥ I 
(1) 
[p∧q]1 
∧∧∧∧ E 
p p→~q 
p↔~q 
→→→→E 
↔↔↔↔E [p∧q]1 
MÉTODO DE DEDUÇÃO NATURAL 
 25 
Estratégias para construção de uma prova 
 
 Não há maneira única de se construir uma prova. Se uma sentença é derivável, ela 
pode ser provada de maneiras diferentes, trocando a ordem de aplicação das regras ou 
usando outras regras. No entanto, algumas estratégias contribuem para indicar um caminho 
mais direto para a obtenção de uma prova. É importante observar que isso não é feito como 
em um passe de mágica, para obter algumas provas será necessário pensar muito e testar 
vários caminhos, somente com a experiência as provas realmente serão realizadas mais 
facilmente. As tabelas que se seguem trazem alguns dos mais comuns procedimentos 
adotados, quando nos deparamos com alguns tipos de sentença alvo. 
 
Estratégias para Síntese 
 
Se a sentença alvo for um(a) Então 
Sentença atômica Tente prová-la a partir das premissas, adotando as 
estratégias de análise. 
⊥ Tente provar uma sentença e sua negação a partir das 
premissas, adotando as estratégias de análise. 
Negação Tente aplicar a regra ~I, gerando como hipótese a 
sentença alvo sem o símbolo da negação. 
Conjunção Tente aplicar ∧I, provando cada um das partes da 
conjunção separadamente. 
Disjunção Tente aplicar ∨I, provando um dos componentes da 
disjunção. 
Implicação Use a regra → I. 
Bimplicação Use a regra ↔ I . 
 
Em qualquer caso Se nenhuma estratégia tem sucesso, tente aplicar a 
regra derivada RA, apresentada a seguir. 
 
Estratégias para Análise 
 
Se a premissa ou hipótese for uma 
Sentença atômica Este tipo de sentença é usado em várias situações, por 
exemplo: 
- Como antecedente de uma implicação para 
aplicação da regra →E. 
- Contribuindo para formar as contradições para a 
utilização da regra ~I. 
- Um dos componentes de uma conjunção, 
provada através da regra ∧ I . 
- Para provar uma disjunção, através da regra ∨ I 
Negação Pode ser usada da mesma forma que as sentenças 
atômicas ou na aplicação da regra ~E. 
Conjunção Pode ser usada da mesma forma que as fórmulas 
MÉTODO DE DEDUÇÃO NATURAL 
 26 
atômicas ou usada na aplicação da regra ∧ E. 
Disjunção Usa-se ∨ E para obter uma prova para uma certa 
sentença. 
Implicação Normalmente tenta-se usar a regra →E. 
Bimplicação Usa-se a regra ↔E, obtendo-se a implicação desejada. 
 
 
Regras Derivadas 
 
 
As regras de introdução e eliminação de conectivos nem sempre determinam as 
provas mais simples ou curtas. Os matemáticos utilizam algumas outras regras que 
facilitam a tarefa de construir provas. Muitas delas são provadas a partir das regras 
apresentadas acima e são chamadas de regras derivadas. Apresentaremos algumas delas a 
seguir: 
 
 
Redução ao Absurdo (RA): Dada uma derivação de uma contradição a partir de uma 
hipótese ~φ, podemos descartar a hipótese e inferir φ. Normalmente, esta regra é usada 
quanto nenhuma estratégia imediata tem sucesso. 
 
 
 
 
 
 
 
 
 Esta regra condensa as aplicações, em seqüência, das regras ~I e ~E. 
 
 
 
 
 
 
 
 
 
 
Prove: 
 
~p→q ~q→p 
 
 
 
 
 
φ 
 ⊥ 
. 
. 
. 
[~φ]1 
 RA (1) 
~~φ 
 ⊥ 
. 
. 
. 
[~φ]1 
 ~ I (1) 
~E 
 φ 
MÉTODO DE DEDUÇÃO NATURAL 
 27 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Utilizaremos a regra RA para provar ‘p’, pois não foi possível prová-la diretamente 
a partir da premissa ‘~p→q’ e da hipótese ‘~q’. 
 
Prove: 
 
~(p→q) p 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Convém destacar que apesar de termos tomado a sentença ‘~q’ como hipótese, em 
função da aplicação da regra RA para a prova da sentença ‘q’, não foi necessário utilizá-la, 
pois já havia uma contradição envolvendo duas outras hipóteses. 
 
Em geral, nas aplicações de regras hipotéticas, não é obrigatória a utilização da 
respectiva hipótese na prova. Por outro lado, é possível utilizar a hipótese mais de uma vez, 
como ocorreu em exemplos anteriores. Tais aspectos são peculiaridades da Lógica 
Matemática, que não ocorrem em algumas outras lógicas. 
 
Prove: 
 p∨~p 
 
p 
(p→q) ~(p→q) 
RA (1) ⊥ 
~(p→q) 
[~p]1 
[p]2 
[~q]3 q 
⊥⊥⊥⊥ I 
→→→→ I 
⊥ 
[~p]1 
RA 
[p]2 
(3) 
⊥⊥⊥⊥ I 
~q→p 
~p→q 
[~q]1 
[~p]2 
 
p 
⊥ 
q [~q]1 
[~p]2 ~p→q 
RA 
⊥⊥⊥⊥ I 
→→→→ E 
→→→→ I (1) 
(2) 
MÉTODO DE DEDUÇÃO NATURAL 
 28 
 Podemos tentar provar esta sentença utilizando uma instância de uma das regras de 
introdução do conectivo ∨: 
 
 
 
 
 
 
 
 Entretanto, não seria possível provar ‘p’, no primeiro caso, e nem provar ‘~p’, pois 
não há qualquer premissa ou hipótese que nos auxilie nestas tarefas. Portanto, resta-nos 
apenas a opção de utilizar a regra RA. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Modus Tollens (MT): 
 
 
 
 
 
 
Prove: 
 
p→q, ~q ~p 
 
 
 
 
 
 
 
 
~φ 
 
 
~ψ φ → ψ 
 MT 
~p 
 ⊥ 
q ~q 
[p] 1 p →q 
 →→→→E 
 ~ - I 
 ⊥⊥⊥⊥ - I 
(1) 
p→q 
~q 
[p]1 
p∨~p 
p∨~p [~ (p∨~p)]1 
RA (1) ⊥ 
[~ (p∨~p)]1 
[p]2 
 
~p 
⊥⊥⊥⊥ I 
∨∨∨∨ I 
⊥ RA (2) 
⊥⊥⊥⊥ I [~ (p∨~p)]
1
 p∨~p 
[p]2 
∨∨∨∨ I 
p 
p∨~p 
∨∨∨∨ I 
~p 
p∨~p 
∨∨∨∨ I 
MÉTODO DE DEDUÇÃO NATURAL 
 29 
 
 
p→q, ~q ~p 
 
 
 
 
 
 
 
 
 
Silogismo Hipotético(SH): ψ → φ, φ → Φ ψ → Φ 
 
 
 
 
 
 
 
Prove:p→q, q→r p→ r 
 
 
 
 
 
 
 
 
 
 
 
Absorção (ABS) : ψ → φ ψ→(ψ ∧ φ) 
 
Prove: 
 
p→ q p→(p∧q) 
 
 
 
 
 
 
 
 
 
 
Contradição (CONTRAD) : φ , ~φ ψ 
ψ → Φ 
 
 ψ → φ 
 SH φ → Φ 
→ I 
p→ r 
r 
q q→ r 
[p]1 p→q 
p→(p∧q) 
p∧q 
[p]1 
(1) 
q 
[p]1 p→q 
p→q 
q→r 
[p]1 
 → E 
(1) 
∧∧∧∧ - I 
→→→→ I 
→→→→ - I 
p→ q 
[p]1 
~p 
~q p→q MT 
 p→q 
~q 
MÉTODO DE DEDUÇÃO NATURAL 
 30 
 
Prove: 
 
p, ~p q 
 
 
 
 
 
Silogismo Disjuntivo: ψ ∨ φ, ~φ ψ ou também pode ser escrito ψ ∨ φ, ~ψ φ 
 
 
 
 SD SD 
 
 
 
Prove: 
p ∨ q, ~p q 
 
 
 
 
 
 
 
 
 
Outra prova, utilizando diretamente o Silogismo Disjuntivo: 
 
 
 p ∨ q ~p 
 SD 
 q 
 
 
Prove: 
p ∨ q ~p→ q 
 
 
 p ∨ q [~p]1 
 SD 
 q 
 → I 
 ~p→q 
 
 
 
q 
⊥ RA 
⊥ I 
~p p 
φ 
ψ∨φ ~ψ 
ψ 
ψ∨φ ~φ 
q 
q [q]2 p∨q (1) (2) 
[p]1 
 
~p 
 
CONTRAD 
∨∨∨∨ - E 
(1) 
p ∨ q 
[~p]1 
[q]2 
 
 
p 
~p 
[~q]1 
p ∨ q 
[~p]1 
 
 
 
MÉTODO DE DEDUÇÃO NATURAL 
 31 
 
O Sistema de Dedução Natural para a Lógica 
de Predicados de Primeira Ordem (LPPO) 
 
 
Na Lógica de Predicados de Primeira Ordem o conjunto de regras do Sistema de 
Dedução Natural consiste no acréscimo de quatro regras à coleção de regras básicas 
apresentadas para a Lógica Sentencial, podendo assim avaliar a validade de qualquer tipo 
de argumento da LPPO. 
 
Apresentaremos a seguir as quatro regras do Sistema de Dedução Natural para a Lógica de 
Predicados de Primeira Ordem. 
 
Introdução do ∀∀∀∀: Se pudermos provar α para uma constante arbitrária a, então podemos 
inferir ∀x α. 
 
 
 
 
 
 
 
Restrição da regra: A constante a não pode ocorrer em qualquer hipótese da qual α 
dependa. 
 
 
Eliminação do ∀∀∀∀: Se pudermos provar ∀x α, então podemos inferir qualquer instância de 
α, ou seja, α(x/t), para qualquer termo t. 
 
 
 
 
 
 
 
 
Introdução do ∃∃∃∃: Se pudermos provar α para um termo t, então podemos inferir que ∃x α. 
 
 
 
 
 
 
 
α(x/t) 
∃x α 
∀∀∀∀ - E 
∀x α 
α(x/t) 
∀∀∀∀ - E 
∀x α 
α(x/a) 
∀∀∀∀ - I 
MÉTODO DE DEDUÇÃO NATURAL 
 32 
Eliminação do ∃∃∃∃: O que podemos inferir a partir da sentença ∃x α? É certo que não 
podemos inferir ‘α(x/a)’, pois, intuitivamente, estaríamos afirmando que o objeto particular 
representado pela constante ‘a’ satisfaz a propriedade representada por α, quando temos 
garantida apenas a existência de um tal objeto (não conhecido). Assim, só podemos inferir 
alguma sentença que não dependa da escolha de tal objeto (ou do conhecimento de 
propriedades específicas dele) . Isto é capturado pela regra a seguir: 
 
 
 
 
 
 
 
 
 
Dado que: 
 
a) A constante a não pode ocorrer em β. 
b) A constante a não pode ocorrer em ∃xα. 
c) A constante a não pode ocorrer em qualquer premissa ou hipótese (diferente de 
α(x/a)) da qual β dependa. 
 
Podemos ver o quantificador ∃ como sendo uma disjunção infinita, α(x/a1) ∨ 
α(x/a2)∨.... , onde as constantes a1, a2,... representam todos os indivíduos do domínio de 
uma estrutura. Assim, esta regra pode ser entendida fazendo-se um paralelo com a regra 
∨E, sendo que, ao invés de obtermos uma prova de β a partir de cada componente dessa 
disjunção infinita, provamos β a partir de α tomando uma constante ‘a’ arbitrária, ou 
melhor, que mostraremos ser arbitrária por satisfazer as restrições descritas acima. 
 
Exemplos: 
 
 
Prove: 
 
 
∀xP(x) ∃xP(x) 
 
 
 
 
 
 
 
 
 
∃x α β 
. 
. 
. 
[α(x/a)] 
β 
∃∃∃∃- E 
∃xP(x) 
∀xP(x) 
MÉTODO DE DEDUÇÃO NATURAL 
 33 
Para provar a sentença ‘∃xP(x)’ podemos usar a sentença ‘P(a)’, aplicando a regra 
do ∃ - I. 
 
 
 
 
 
 
 
 
 
 
 
 
 Neste passo a sentença ‘P(a)’ pode ser provada a partir da premissa ‘∀xP(x)’, 
aplicando a regra do ∀ - E. 
 
 
 
 
 
 
 
 
 
 
 Neste ponto a prova está finalizada . 
 
 
 
Prove: 
 
∀x(P(x)→Q(x)),∀xP(x) ∀xQ(x) 
 
 
 
 
 
 
 
 
 
 
 
 
 
∃xP(x) 
∀xP(x) 
P(a) ∃ - I 
∃xP(x) 
∀xP(x) 
P(a) ∃ - I 
∀xP(x) ∀ - E 
∀x(P(x)→Q(x)) 
∀xP(x) 
∀xQ(x) 
MÉTODO DE DEDUÇÃO NATURAL 
 34 
 Como a conclusão é uma sentença quantificada, tentaremos utilizar a regra ∀I. No 
entanto, é importante não esquecermos de verificar se as restrições desta regra serão 
satisfeitas ao completarmos a nossa tentativa de construção da prova. 
 
 
 
 
 
 
 
 
 
 
 
 
 Note que podemos inferir a sentença ‘Q(a)’ a partir das sentenças ‘P(a)’ e 
‘P(a)→Q(a)’ usado a regra →E. 
 
 
 
 
 
 
 
 
 
 
 
Neste passo podemos provar sentença ‘P(a)’ a partir da premissa ‘∀xP(x)’ aplicando 
a regra do ∀-E. 
 
 
 
 
 
 
 
 
 
 
 
 
Para obtermos a prova da sentença ‘P(a)→Q(a)’, podemos tentar usar a regra →I, 
no entanto, neste caso podemos derivá-la a partir da premissa ‘∀x(P(x)→Q(x))’ usando a 
regra ∀-E, gerando desta forma, uma prova mais simples do que se usássemos a primeira 
tentativa. 
∀x(P(x)→Q(x)) 
∀xP(x) 
∀xQ(x) 
Q(a) ∀∀∀∀ - E 
∀x(P(x)→Q(x)) 
∀xP(x) 
∀xQ(x) 
Q(a) ∀∀∀∀ - E 
P(a) P(a)→Q(a) →→→→ - E 
∀x(P(x)→Q(x)) 
∀xP(x) 
∀xQ(x) 
Q(a) ∀∀∀∀ - E 
P(a) P(a)→Q(a) →→→→ - E 
∀xP(x) ∀∀∀∀ - E 
MÉTODO DE DEDUÇÃO NATURAL 
 35 
 
 
 
 
 
 
 
 
 
 
Neste ponto a prova deve ser finalizada pois o topo de todos os ramos da árvore de 
prova é composto apenas por premissas. 
 
 
Prove: 
 
 
 ~∃xP(x) → ∀x~P(x) 
 
 
 
 
 
 
 
 
 
 
 Nesta prova começaremos utilizando a regra → I, tomando como hipótese a 
sentença ‘~∃xP(x)’. 
 
 
 
 
 
 
 
 
 
 
 
 
Para provarmos a sentença ‘∀x~P(x)’ podemos utilizar a regra ∀ I, na sentença 
‘~P(a)’. 
 
 
~∃xP(x) → ∀x~P(x) 
 
 
~∃xP(x) → ∀x~P(x) 
 
→→→→ I 
 
[~∃xP(x)]1 
∀x~P(x) (1) 
∀x(P(x)→Q(x)) 
∀xP(x) 
∀xQ(x) 
Q(a) ∀∀∀∀ - E 
P(a) P(a)→Q(a) →→→→ - E 
∀xP(x) ∀∀∀∀ - E ∀x(P(x)→Q(x)) ∀∀∀∀ - E 
MÉTODO DE DEDUÇÃO NATURAL 
 36 
 
 
 
 
 
 
 
 
 
 
 Neste ponto, podemos tentar provar a sentença ‘P(a)’ a partir da base de premissas e 
hipóteses. No entanto, não existe qualquer regra que possa inferir a sentença ‘~P(a)’ a partir 
da hipótese ‘[~∃xP(x)]’. Desta forma, devemos tentar uma prova indireta, usando a regra 
‘RA’ e logo depois ⊥ I. 
 
 
 
 
 
 
(2) 
 
 
 
 
 
 
 
 Para provar a sentença ‘∃xP(x)’ podemos usar a regra ∃ I na hipótese [P(a)]. 
 
 
 
 
 
 
 
(2) 
 
 
 
 
 
 
Neste passo a prova está finalizada, pois todos os ramos da árvore contêm apenas 
premissas ou hipóteses. 
 
 
~∃xP(x) → ∀x~P(x)→→→→ - I 
 
[~∃xP(x)]1 
∀x~P(x) (1) 
~P(a) ∀∀∀∀ - I 
 
~∃xP(x) → ∀x~P(x) 
 
→→→→ - I 
 
[~∃xP(x)]1 
[P(a)]2 
∀x~P(x) (1) 
~P(a) ∀∀∀∀ - I 
 
RA ⊥ 
⊥⊥⊥⊥ I [~∃xP(x)]
1
 ∃xP(x) 
~∃xP(x) → ∀x~P(x) 
 
→→→→ - I 
 
[~∃xP(x)]1 
[P(a)]2 
∀x~P(x) (1) 
~P(a) ∀∀∀∀ - I 
 
RA ⊥ 
⊥⊥⊥⊥ I [~∃xP(x)]
1
 ∃xP(x) 
∃∃∃∃ - I [P(a)]2 
MÉTODO DE DEDUÇÃO NATURAL 
 37 
Prove: 
 
∀x(F(x) ∧ G(x)) ∀xF(x) ∧ ∀xG(x) 
 
 
 
 
 
 
 
 
 
Inicialmente podemos tentar provar cada componente da conjunção, e depois aplicar 
a regra do ∧I para inferir a conclusão. 
 
 
 
 
 
 
 
 
 
 Podemos provar a sentença ‘∀xF(x)’ com uma estratégia de síntese, usando a 
sentença ‘F(a)’ e a regra ∀ I. 
 
 
 
 
 
 
 
 
 
 
 Como provar a sentença ‘F(a)’? Podemos inicialmente tentar uma estratégia de 
síntese, no entanto, note que a sentença ‘F(a)’ e derivável da premissa ‘F(a)∧G(a)’ usando a 
regra ∧∧∧∧ E. 
 
 
 
 
 
 
 
 
∀xF(x) ∧ ∀xG(x) 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∧ ∀xG(x) 
∧∧∧∧ - I 
 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∀xG(x) 
∀xF(x) ∧ ∀xG(x) 
∧∧∧∧ - I 
 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∀xG(x) 
F(a) 
∀∀∀∀ - I 
∀xF(x) ∧ ∀xG(x) 
∧∧∧∧ - I 
 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∀xG(x) 
F(a) 
∀∀∀∀ - I 
 
 F(a)∧G(a) 
∧∧∧∧ - E 
MÉTODO DE DEDUÇÃO NATURAL 
 38 
 
 
 
A sentença ‘F(a)∧G(a)’ pode ser obtida a partir da premissa ‘∀x(F(x)∧G(x))’ 
usando a regra ∀∀∀∀ E: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Analogamente, obtemos uma prova para o ramo direito. 
 
 
 
 
 
 
 
 
 
 
 
 Neste ponto a prova pode ser finalizada. 
 
Prove: 
 
∀x (P(x)→Q(x)), ∀x(Q(x)→R(x)) ∀x(P(x)→R(x)) 
 
 
 
 
 
 
 
 
 
 
 
∀xF(x) ∧ ∀xG(x) 
∧∧∧∧ - I 
 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∀xG(x) 
F(a) 
∀∀∀∀ - E 
 
 
F(a)∧G(a) 
∧∧∧∧ - E 
∀x(F(x)∧G(x)) 
∀xF(x) ∧ ∀xG(x) 
∧∧∧∧ - I 
 
∀x(F(x) ∧ G(x)) 
∀xF(x) ∀xG(x) 
F(a) 
∀∀∀∀ - E 
∀∀∀∀ - I 
G(a) 
F(a)∧G(a) 
∧∧∧∧ - E 
∀x(F(x)∧G(x)) 
F(a)∧G(a) 
∧∧∧∧ - E 
∀∀∀∀ - E 
∀x(F(x)∧G(x)) 
∀x(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
MÉTODO DE DEDUÇÃO NATURAL 
 39 
 
 Note que a conclusão pode ser derivada da premissa ‘P(a)→R(a)’ aplicando a regra 
∀∀∀∀ - I. 
 
 
 
 
 
 
 
 
2 
 
 
 
 A prova para a sentença ‘R(a)’, pode ser obtida a partir das sentenças ‘P(a)’ e 
‘P(a)→Q(a)’ usando a regra →→→→E. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Neste passo podemos provar a sentença ‘R(a)’ utilizando a regra →→→→E nas sentenças 
‘P(a)’ e ‘P(a)→R(a)’. 
 
 
 
 
 
 
 
 
 
 
 
 
 
∀x(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
P(a)→Q(a) ∀∀∀∀ - I 
∀x(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
[P(a)]1 
P(a)→R(a) ∀∀∀∀ - I 
R(a) →→→→ - I 
∀X(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
[P(a)]1 
P(a)→R(a) ∀∀∀∀ - I 
R(a) →→→→ - I 
Q(a) P(a)→R(a) →→→→ - E 
(1) 
MÉTODO DE DEDUÇÃO NATURAL 
 40 
 Utilizando uma estratégia de análise podemos derivar a sentença ‘Q(a)’ a partir das 
sentenças ‘[P(a)]1]’ e ‘P(a)→Q(a)’. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Podemos provar a sentença ‘Q(a)→R(a)’ a partir da premissa ‘∀x(Q(x)→R(x))’ 
usando a regra ∀∀∀∀ E. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Neste passo podemos provar a sentença ‘P(a)→Q(a)’ a partir da premissa 
‘∀x(P(x)→Q(x))’ usando a regra ∀∀∀∀ E. 
 
 
 
 
 
 
 
 
 
 
 
 
∀X(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
[P(a)]1 
P(a)→R(a) ∀∀∀∀ - I 
R(a) →→→→ - I 
Q(a) Q(a)→R(a) →→→→ - E 
[P(a)]1 P(a)→Q(a) →→→→ E 
∀x(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
[P(a)]1 
P(a)→R(a) ∀∀∀∀ - I 
R(a) →→→→ - I 
Q(a) Q(a)→R(a) →→→→ - E 
[P(a)]1 P(a)→Q(a) →→→→ E ∀x(Q(x)→R(x)) ∀∀∀∀ - E 
∀x(P(x)→R(x)) 
 
∀x (P(x)→Q(x)) 
∀x(Q(x)→R(x)) 
[P(a)]1 
P(a)→R(a) ∀∀∀∀ - I 
R(a) →→→→ - I 
Q(a) Q(a)→R(a) →→→→ - E 
[P(a)]1 P(a)→Q(a) →→→→ E ∀x(Q(x)→R(x)) ∀∀∀∀ - E 
∀x(P(x)→Q(x)) ∀∀∀∀ - E 
 
MÉTODO DE DEDUÇÃO NATURAL 
 41 
 
 
 
 
 A prova deve ser finalizada, pois o topo de todos os ramos é formado apenas por 
hipóteses ou premissas. 
 
Prove: 
 
 ∀x~P(x)→ ~∃xP(x) 
 
 
 
 
 
 
 
 Para provar a sentença ‘∀x~P(x)→ ~∃xP(x)’ tentaremos usar a regra do →I gerando 
como hipótese a sentença ‘∀x~P(x)’. 
 
 
 
 
 
 
 
 
 
 
 
Neste passo a sentença ‘~∃xP(x)’ é uma sentença negada, e isso é um indicativo da 
utilização da regra ⊥ I, gerando como hipótese a sentença ‘∃xP(x)’. 
 
 
 
 
 
 
 
 
 
 
 
 
∀x~P(x)→ ~∃xP(x) 
 
 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
~∃xP(x) → I (1) 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
~∃xP(x) → I (1) 
⊥ ⊥ I (2) 
MÉTODO DE DEDUÇÃO NATURAL 
 42 
Agora, devemos investigar e descobrir quais sentenças podem ser utilizadas para 
caracterizar uma contradição. Podemos usar a hipótese ‘∀x~P(x)’, pois desta forma 
precisaríamos provar apenas a sua negação ‘~(∀x~P(x))’. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Podemos tentar provar a sentença ‘~∀x~P(x)’ aplicando a regra ∃ E, o que 
determina que devemos tomar como hipótese a sentença ‘P(a)’. 
 
 
 
 
 
 
 
 
 
 
 
 
Agora o problema passa a ser como provar a sentença ‘~∀x~P(x)’ a partir da 
hipótese P(a). Naturalmente, poderemos utilizar as outras duas hipóteses. Podemos seguir 
uma estratégia de síntese, tentando aplicar a regra ~I. Isto determina que devemos tomar 
como hipótese a sentença ‘∀xP(x)’. 
 
 
 
 
 
 
 
 
 
 
 
 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
~∃xP(x) → I (1) 
[∀x~P(x)]1 ~(∀x~P(x)) ⊥ I 
⊥ ~ I 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
[P(a)]3 
~∃xP(x) →→→→ I (1) 
[∀x~P(x)]1 ~∀x~P(x) ⊥⊥⊥⊥ I 
⊥ ~ I 
[∃xP(x)]2 ~∀x~P(x) ∃∃∃∃ - E 
(2) 
(3) 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
[P(a)]3 
 
~∃xP(x) →→→→ I (1) 
[∀x~P(x)]1 ~∀x~P(x) ⊥⊥⊥⊥ I 
⊥ ~ I 
[∃xP(x)]2 ~∀x~P(x) ∃∃∃∃ - E 
(2) 
⊥ ~ I 
(3) 
MÉTODO DE DEDUÇÃO NATURAL 
 43 
 
 
Neste passo, devemos novamente tentar encontrar sentenças contraditórias. 
Podemos consultar a base de premissas e hipóteses em busca de uma sentença de tal modo 
que a sua negação possa ser provada Neste caso podemos usar a hipótese ‘P(a)’ e tentar 
provar a sua negação. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 A sentença ‘~P(a)’ pode ser inferida a partir da premissa ‘∀x~P(x)’, usando a regra 
∀∀∀∀ E. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Neste ponto a prova está finalizada. 
 
 
 
 
 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
[P(a)]3 
 
~∃xP(x) →→→→ I (1) 
[∀x~P(x)]1 ~∀x~P(x) ⊥⊥⊥⊥ I 
⊥ ~ I 
[∃xP(x)]2 ~∀x~P(x) ∃∃∃∃ - E 
(2) 
⊥ ~ I 
(3) 
[P(a)]3 ~P(a) ⊥⊥⊥⊥ I 
∀x~P(x)→ ~∃xP(x) 
 
[∀x~P(x)]1 
[∃xP(x)]2 
[P(a)]3 
 
~∃xP(x) →→→→ I (1) 
[∀x~P(x)]1 ~∀x~P(x) ⊥⊥⊥⊥ I 
⊥ ~ I 
[∃xP(x)]2 ~∀x~P(x) ∃∃∃∃ - E 
(2) 
⊥ ~ I 
(3) 
[P(a)]3 ~P(a) ⊥⊥⊥⊥ I 
[∀x~P(x)]1 ∀∀∀∀ E 
MÉTODO DE DEDUÇÃO NATURAL 
 44 
Prove: 
 
 
~∃x P(x) ∀x ~P(x) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Para provar a sentença ‘∀x ~P(x)’, podemos usar a regra ∀ I. 
 
 
 
 
 
 
 
 
 
 
 
 Para provar a sentença ‘~P(a)’ tentaremos aplicar a regra ~I, tomando como 
hipótese a sentença‘P(a)’. 
 
 
 
 
 
 
 
 
 
 
 
 
 
~∃x P(x) 
∀ x ~P(x) 
~∃ x P(x) 
∀ x ~P(x) 
~P(a) 
~∃x P(x) 
[P(a)]1 
∀ x ~P(x) 
~P(a) 
⊥ 
∀∀∀∀ I 
~I 
∀∀∀∀ - I 
MÉTODO DE DEDUÇÃO NATURAL 
 45 
Neste passo, devemos encontrar sentenças que podem formar uma contradição, para 
isto podemos usar a premissa ‘~∃x P(x)’ e a sentença ‘∃x P(x)’. 
 
 
 
 
 
 
 
 
 
 
 Finalmente, inferimos a sentença ∃ x P(x) a partir da hipótese [P(a)]1. 
 
 
 
 
 
 
 
 
 
 
Prove: 
 
~∀x P(x) ∃x~P(x) 
 
 
 
 
 
 
 
 
 
 
 
 Para provar a sentença ‘∃x ~P(x)’ podemos inicialmente tentar derivá-la da 
sentença ‘~P(a)’ usando a regra ∃ I. 
 
 
 
 
 
 
 
~∃x P(x) 
[P(a)]1 
∀ x ~P(x) 
~P(a) 
⊥ 
∀∀∀∀ I 
~I 
~∃ x P(x) ∃ x P(x) ⊥⊥⊥⊥ I 
~∃x P(x) 
[P(a)]1 
∀ x ~P(x) 
~P(a) 
⊥ 
∀∀∀∀ I 
~I 
~∃ x P(x) ∃ x P(x) ⊥⊥⊥⊥ I 
[P(a)]1 ∃ I 
∃x~P(x) 
~∀x P(x) 
∃x~P(x) 
~∀x P(x) 
∃∃∃∃ I ~P(a) 
MÉTODO DE DEDUÇÃO NATURAL 
 46 
 
 
Como provar ‘~P(a)’? Novamente, tentaremos aplicar a regra ~I. 
 
 
 
 
 
 
 
 
 
 
 
 Podemos caracterizar a obtenção de uma contradição, aplicando a regra ⊥I, 
utilizamos a premissa ‘~∀xP(x)’ e a tentamos provar a sentença ‘∀xP(x)’ . 
 
 
 
 
 
 
 
 
 
 
 Neste ponto ocorre um fato interessante, pois a sentença ‘∀xP(x)’ não pode ser 
provada a partir da hipótese ‘P(a)’, isso ocorre devido as restrições da regra ∀ I, pois a 
constante a não pode ocorrer em qualquer hipótese da qual a sentença ‘∀xP(x)’ dependa. 
 
 
 
 
 
 
 
 
 
 
 
A forma correta de se realizar esta prova é feita abaixo: 
 
 
 
 
 
∃x~P(x) 
~∀x P(x) 
∃x~P(x) 
~∀x P(x) 
[P(a)]1 
∃∃∃∃ I ~P(a) 
⊥ ~I 
⊥⊥⊥⊥ I 
∀xP(x) ~∀xP(x) 
(1) 
∃x~P(x) 
~∀x P(x) 
[P(a)]1 
∃∃∃∃ I ~P(a) 
⊥ ~I 
⊥⊥⊥⊥ I 
∀xP(x) ~∀xP(x) 
[P(a)]1 ∀∀∀∀ I ERRADO 
(1) 
∃x~P(x) 
~∀x P(x) 
[P(a)]1 
∃∃∃∃ I ~P(a) 
⊥ 
~I (1) 
MÉTODO DE DEDUÇÃO NATURAL 
 47 
 Vamos realizar esta prova de uma forma um pouco diferente da tentativa anterior, 
pois usaremos primeiramente a regra RA, tomando como hipótese a sentença ‘~∃x~P(x)’. 
 
 
 
 
 
 
 
 
 
 
 Neste ponto, podemos utilizar a premissa ‘~∀xP(x)’ e a sentença ‘∀xP(x)’ para 
formar a contradição. 
 
 
 
 
 
 
 
 
 
 
 
 
 Podemos derivar a sentença ‘∀xP(x)’ a partir da sentença ‘P(a)’, visto que, a 
constante a não ocorre em qualquer hipótese da qual ‘∀xP(x)’ dependa. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Como provar a sentença ‘P(a)’? Poderíamos tentar derivá-la a partir das premissas, 
no entanto, isso não é possível, pois não existe qualquer premissa que possa contribuir 
nesta tarefa. Contudo, podemos tentar uma prova indireta, tomando como hipótese a 
sentença ‘~P(a)’. 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1 
⊥ RA (1) 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1 
⊥ RA 
~∀x P(x) ∀x P(x) 
⊥⊥⊥⊥ I 
(1) 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1 
⊥ RA 
~∀x P(x) ∀x P(x) 
⊥⊥⊥⊥ I 
P(a) ∀∀∀∀ I 
(1) 
MÉTODO DE DEDUÇÃO NATURAL 
 48 
 
 
 
 
 
 
 
 
 
 
 
 Podemos utilizar a hipótese ‘~∃x~P(x)’ e a sentença ‘∃x~P(x)’ para formar a 
contradição. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Podemos finalizar a prova derivando a sentença ‘∃x~P(x)’ a partir da hipótese 
‘~P(a)’, usando a regra ∃ I. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1 
[~P(a)]2 
⊥ RA 
~∀x P(x) ∀x P(x) 
⊥⊥⊥⊥ I 
P(a) 
∀∀∀∀ I 
⊥ RA 
(2) 
(1) 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1
 
 
[~P(a)]2 
⊥ ~I 
~∀x P(x) ∀x P(x) 
⊥⊥⊥⊥ I 
P(a) 
∀∀∀∀ I 
⊥ RA 
[~∃x~P(x)]1 ∃x~P(x) 
⊥⊥⊥⊥ I 
(2) 
(1) 
∃x~P(x) 
~∀x P(x) 
[~∃x~P(x)]1
 
 
[~P(a)]2 
⊥ ~I 
~∀x P(x) ∀x P(x) 
⊥⊥⊥⊥ I 
P(a) 
∀∀∀∀ I 
⊥ RA 
[~∃x~P(x)]1 ∃x~P(x) 
⊥⊥⊥⊥ I 
[~P(a)]2 
(2) 
∃∃∃∃ I 
(1) 
MÉTODO DE DEDUÇÃO NATURAL 
 49 
Conclusão 
 
 A discussão do processo de busca por uma prova através de exemplos, considerando 
a aplicação de estratégias simples como a análise e síntese, têm como principal intuito 
propiciar ao aluno uma visão dinâmica deste processo, destacando a forma estruturada 
como as provas são apresentadas no Método de Dedução Natural. 
 
 É importante ressaltar que ao propormos e discutirmos a aplicação de estratégias, 
tentamos mostrar ao aluno um possível caminho a ser seguido. Contudo, não é obrigatório 
aplicá-las, cada pessoa pode escolher como buscará construir uma prova. A utilização de 
exemplos resolvidos e discutidos permite explicitar que a utilização das estratégias 
propostas pode ser encarada como uma maneira de raciocinar ou proceder na construção de 
uma prova. 
 
Cremos que o texto é de fácil compreensão e pode ser utilizado pelos alunos de 
forma autônoma, a fim de apoiar ou complementar as atividades desenvolvidas na 
disciplina Lógica para a Ciência da Computação, que trata do assunto em questão.