Parte
1
Sistemas de Hilbert
Neste capı́tulo definiremos uma linguagem adequada ao estabelecimento do
Cálculo Proposicional Clássico como uma lógica de primeira espécie. Faremos isso baseado em um Sistema de Hilbert com apenas dois conectivos
(negação ¬ e implicação →) a definição do que sejam fórmulas e um conjunto
de cinco axiomas.
1.1
Lógica de Predicados: Axiomas da Lógica
Vamos então definir uma linguagem L para o Cálculo Proposicional Clássico.
Definição 1.1. Definimos a linguagem L para o Cálculo Proposicional
Clássico por:
1. Um conjunto de elementos α, βγ, . . . possivelmente indexados representado por letras gregas minúsculas denominados de fórmulas atômicas
ou átomos ou simplesmente proposições.
2. Dois conectivos lógicos negação ¬ e implicação →.
Em seguida definiremos o conceito de uma fórmula ou fórmula molecular
em L (é o equivalente a palavras em uma linguagem natural).
2
Lógica Matemática
Definição 1.2. Definimos uma fórmula em L por:
1. Se α é uma proposição então α é uma fórmula.
2. Se α e β são fórmulas então ¬α e α → β são fórmulas.
3. Nada mais é fórmula.
Jan Lukasiewicz nasceu
em 21 de Dezembro de
1878 em Lviv na Ucrânia
Já de posse da linguagem L para o cálculo proposicional clássico podemos
complementar com uma estrutura que possa gerar fórmulas válidas. Para
e morreu em 13 de Fevereiro de 1956 em Dublin na Irlanda.
Foi
isto usaremos cinco axiomas. A saber: Dois axiomas ligados a igualdade:
A1 x = x Axioma da identidade.
um lógico polonês notável
pelo seu desenvolvimento
A2 (x = y), P (x) ` P (y) Axioma da substituição.
da lógica multivalente (e
E três esquemas de axiomas, propostos inicialmente por Jan Lukasiewicz
lógica fuzzy) e seus estudos
sobre
a
história
:
da lógica, particularmente
sua interpretação da lógica
aristotélica.
Conhecido
também, pela introdução
na lógica da notação polonesa que dispensa o uso de
parenteses.
A3 α → (β → α)
A4 (α → (β → γ)) → ((α → β) → (α → γ))
A5 (¬α → ¬β) → (β → α)
OBS 1.1. O uso do termo “Esquema de Axiomas” no lugar de apenas
“Axiomas” quer dizer que no lugar de das fórmulas α, β e γ em A3, A4 e
A5 podem ser colocadas quaisquer fórmulas.
Completando os esquemas de axiomas temos uma regra de inferência
(modus pones).
MP α, α → β ` β
OBS 1.2. Uma crı́tica que se faz deste conjunto de axiomas é o fato de
ser muito artificial. Não tem um significado claro. Mais estranho ainda é
desenvolver toda a lógica das proposições com um sistema axiomático de
dois conectivos ¬ e → e apenas um axioma . A saber:
Fundamentos de Matemática
h
3
i
(a → b) → (¬c → ¬d) → c → e → (e → a) → (d → a) ,
de Carew Arthur Meredith.
Os demais conectivos mais conhecidos do cálculo proposicional clássico,
conjunção ∧, disjunção ∨ e dupla implicação ↔, são definidos por:
def
Def1 α ∨ β = ¬α → β
def
Def2 α ∧ β = ¬(¬α ∨ ¬β)
def
Def3 α ↔ β = (α → β) ∧ (β → α)
Definiremos também, o que é uma prova na linguagem L de primeira
ordem definida pelos cinco axiomas acima.
Definição 1.3. Uma prova em L de uma conclusão α a partir de uma
conjunto de premissas Γ, é uma seqüência finita de fórmulas bem formadas
β1 , β2 , . . . , βn tais que βn = α e para cada membro da seqüência βk , 1 ≤ k ≤
n temos:
1. βk é uma premissa
2. βk é um axioma de L
3. βk é derivada das fórmulas anteriores por modus ponnes
Se de um conjunto de fórmulas (premissas) Γ podemos construir uma
prova de α denotaremos Γ ` α.
OBS 1.3. Se podemos construir uma prova da fórmula α (conclusão) sem
necessidade de premissas podemos denotar ∅ ` α ou simplesmente ` α ao que
denominamos de “Teorema”. Em particular os axiomas de L são teoremas
de L.
OBS 1.4. Observamos que o sistema axiomático que dá suporte às demonstrações na linguagem L admite somente demonstrações diretas. Não
4
Lógica Matemática
são permitidas demonstrações indiretas por contra-positiva nem por redução
ao absurdo. Também não é permitido o uso de hipóteses como apoio às demonstrações.
1.1.1
Algumas Demonstrações
Vejamos como utilizar os axiomas acima e demonstrar alguns teoremas e
construir algumas provas.
A primeira das demonstrações é a auto-implicação, que diz que toda
proposição é uma conseqüência de si mesma.
Exemplo 1.1. Auto-implicação (A-imp) ` α → α.
PROVA:
1
α → ((α → α) → α)
A3 β = α → α
2
(α → ((α → α) → α)) → ((α →
A4 α = α, β = α → α e γ = α
(α → α)) → (α → α))
3
(α → (α → α)) → (α → α)
1+2 MP
4
α → (α → α)
A3 α = α e β = α
5
α→α
4+3 MP
OBS 1.5. O teorema da auto-implicação pode ser visto como um esquema
de teorema onde a fórmula α pode ser substituı́da por qualquer fórmula da
linguagem L. Como exemplos podemos substituir α na auto-implicação por
¬α e obter ¬α → ¬α ou substituir por α → β e obter (α → β) → (α → β).
Como próxima demonstração veremos o “Silogismo Hipotético”, uma
espécie de propriedade transitiva para o conectivo de implicação.
Exemplo 1.2. Silogismo hipotético (S-Hip) α → β, β → γ ` α → γ.
PROVA:
Fundamentos de Matemática
5
1
α→β
Premissa
2
β→γ
Premissa
3
(β → γ) → (α → (β → γ))
A3 α = β → γ e β = α
4
α → (β → γ)
2+3 MP
5
(α → (β → γ)) → ((α → β) →
A4
(α → γ))
6
(α → β) → (α → γ)
4+5 MP
7
α→γ
1+6 MP
A seguir apresentaremos a demonstração de uma de duas regra da dupla
negação. Mais precisamente a regra diz que a negação da negação de uma
proposição implica na própria proposição. Esta regra é aceita pelo “Cálculo
Proposicional Clássico” porém, não é aceito pela “Lógica Intuicionista”.
Exemplo 1.3. A regra da dupla negação (DN1) primeira parte ` ¬¬α →
α.
PROVA:
1
¬¬α → (¬¬¬¬α → ¬¬α)
A3 α = ¬¬α e β = ¬¬¬¬α
2
(¬¬¬¬α → ¬¬α) → (¬α → ¬¬¬α)
A5 α = ¬¬¬α e β = ¬α
3
(¬α → ¬¬¬α) → (¬¬α → α)
A5 α = α e β = ¬¬α
4
¬¬α → (¬α → ¬¬¬α)
1+2 S-Hip
5
¬¬α → (¬¬α → α)
4+3 S-Hip
6
(¬¬α → ¬¬α)
A-imp α = ¬¬α
7
(¬¬α → (¬¬α → α)) → ((¬¬α →
A4 α = ¬¬α, β = ¬¬α e γ = α
¬¬α) → (¬¬α → α))
8
(¬¬α → ¬¬α) → (¬¬α → α)
5+7 MP
9
¬¬α → α
6+8 MP
OBS 1.6. Do ponto de vista da definição formal de prova, a demonstração
6
Lógica Matemática
acima não é uma prova. Tecnicamente falando, a linha 6 onde usamos o
teorema da auto-implicação teria que ser substituı́da pela demonstração da
auto-implicação onde toda ocorrência de α seria substituı́da por ¬¬α. A
substituição da linha 6 pela demonstração do teorema da auto-implicação
faria a prova da dupla negação satisfazer a definição de prova. No entanto,
a prova seria muito mais extensa. Além do que, isto seria bastante tedioso e
a ideia é poupar esforços não provando novamente um resultado já provado
anteriormente e assim justificamos na linha 6 apenas a menção do teorema
da auto-implicação onde o α foi substituı́do por ¬¬α. Isto é equivalente a
encarar o teorema da auto-implicação como um axioma e estaremos preservando a definição original de prova sem a necessidade de uma redefinição
para enquadrar a nova situação.
OBS 1.7. Observamos também, que nas linhas 4 e 5 são feitas menções à
prova do silogismo hipotético S-Hip o que também não constitui uma prova
na essência de sua definição. Tecnicamente falando as linhas 4 e 5 teriam que
ser substituı́das pela demonstração do silogismo hipotético a exemplo na linha 4 a fórmula α seria substituı́da pela fórmula ¬¬α , β por ¬¬¬¬α → ¬¬α
e γ por ¬α → ¬¬¬α. Bastante complicado convenhamos e também seria
bastante tedioso e como a ideia continua sendo poupar esforços não provando
novamente um resultado já provado anteriormente, assim justificamos na linhas 4 e 5 apenas a menção do silogismo hipotético com as substituições
adequadas. Como o silogismo hipotético S-Hip depende de premissas, pode
ser encarado como uma regra de inferência adicional passando ao estatus do
modus ponnes. Assim, não precisaremos redefinir o conceito de prova.
Como quarta demonstração veremos o “Teorema da Dedução”. Na verdade trata-se de um meta-teorema i.e. não um teorema da linguagem e
sim um teorema sobre a linguagem. O Teorema da Dedução nos diz que se
nos podemos construir a demonstração de um resultado β partindo de um
conjunto de premissas Γ e mais uma premissa adicional α então podemos
Fundamentos de Matemática
7
construir uma demonstração da proposição condicional, α → β, partindo
apenas do conjunto original de premissas Γ. Na demonstração do Teorema
da Demonstração usaremos duas técnicas de demonstração a primeira conhecida como “Estudo de Casos” a segunda é a “Demonstração por Indução”.
Vamos em frente.
Exemplo 1.4. Se Γ ∪ {α} ` β então Γ ` α → β (Teorema da Dedução)
PROVA:
Suponhamos que Γ ∪ {α} ` β. Portanto, existe uma seqüência de fórmulas
β1 , β2 , . . . , βn , que satisfaz a definição de prova de β. Em outras palavras
temos que βn = β e para cada 1 ≤ k < n temos um dos três casos:
1. βk é uma premissa.
2. βk é um axioma de L.
3. βk é deduzida das proposições anteriores por modus ponnes.
Usaremos uma demostração por indução, mostrando que para cada etapa
βk , 1 ≤ k ≤ n da demonstração teremos que: Γ ` α → βk .
Seja γk uma etapa arbitrária. Por indução supomos que Γ ` α → βj ,
∀j = 1, . . . , k − 1. Temos então os seguintes casos:
Caso 1: βk é uma premissa, o que pode ser subdividido em dois casos:
Caso 1.1: βk = α. Neste caso usando a auto-implicação temos:
α → α. Como βk = α usamos o axioma A2 e substituı́mos a segunda instancia de α por βk e teremos:
α → βk . Portanto, Γ ` α → βk .
Caso 1.2: βk 6= α (βk ∈ Γ). Neste caso usando o axioma A3 com α = βk
e β = α teremos:
βk → (α → βk ). Como βk é uma premissa (assumida como válida) usando
modus ponnes teremos:
α → βk . Portanto, Γ ` α → βk .
Caso 2: βk é um axioma de L (portanto uma fórmula válida) e pode ser
8
Lógica Matemática
introduzido na prova a qualquer momento.
Por outro lado, o axioma A3 com α = βk e β = α pode ser introduzido a
qualquer momento na prova:
Como temos βk (axioma) aplicando modus ponnes temos:
α → βk . Portanto, Γ ` α → βk .
Caso 3: βk vem de passos anteriores por aplicação de modus ponnes.
Suponhamos que no passo i < k tenhamos βi e no passo j < k tenhamos
βj = βi → βk e o no passo k pela aplicação de modus ponnes obviamente
teremos βk .
Aqui é onde necessitaremos a hipótese de indução que ∀m ≤ l ≤ k − 1, Γ `
α → βm . Portanto temos:
Passo m = i < k temos: Γ ` α → βi .
Passo m = j < k temos: Γ ` α → βj . Como βj = βi → βk temos:
Γ ` α → (βi → βk ).
Por outro lado do axioma A4 com α = α, β = βi e γ = βk temos:
(α → (βi → βk )) → ((α → βi ) → (α → βk ))
Aplicando it modus ponnes com (α → (βi → βk ) temos:
(α → βi ) → (α → βk ).
Finalmente aplicando modus ponnes com α → βi temos:
α → βk . Portanto, Γ ` α → βk .
Como em qualquer dos casos temos e em qualquer passo k Γ ` α → βk , em
particular para k = n como βn = β temos:
Γ ` α → β, O Teorema da dedução pode ser usado para derivar novas provas, diminuindo por aplicações sucessivas, do mesmo. Podem ser derivados também,
teoremas na linguagem L. Como exemplo podemos obter, por duas aplicações
do teorema da dedução aplicada à regra de inferência modus ponnes o seguinte teorema:
Fundamentos de Matemática
9
Exemplo 1.5. Teorema ` ¬α → ((¬α → β) → β).
PROVA:
1
¬α, ¬α → β ` β
MP α ← ¬α
2
¬α ` (¬α → β) → β
TD
3
` ¬α → (¬α → β) → β
TD
A segunda regra da dupla negação diz que uma proposição implica na
negação de sua negação. Esta regra em particular é aceita também pela
“Lógica Intuicionista”.
Exemplo 1.6. A regra da dupla negação (DN2) segunda parte ` α → ¬¬α.
PROVA:
1
(¬¬¬α → ¬α) → (α → ¬¬α)
A5 α = ¬¬α e β = α
2
(¬¬¬α → (¬¬¬α → ¬α)) →
A4 α = ¬¬¬α, β = ¬¬¬α e
((¬¬¬α → ¬¬¬α) → (¬¬¬α →
γ = ¬α
¬α))
3
¬¬¬α → ¬¬¬α
A-imp α = ¬¬¬α
4
¬α → (¬¬¬α → ¬α)
A3 α = ¬α e β = ¬¬¬α
5
¬¬¬α → ¬α
DN1 α = ¬α
6
¬¬¬α → (¬¬¬α → ¬α)
5+4 S-Hip
7
(¬¬¬α → ¬¬¬α) → (¬¬¬ → ¬α)
6+2 MP
8
¬¬¬α → ¬α
3+7 MP
9
α → ¬¬α
8+1 MP
Nossa próxima demonstração é a contra-positiva. Em linguagem coloquial: “Se aqui tem fogo então aqui tem oxigênio” pode ser substituı́da por
“Se aqui não tem oxigênio então aqui não tem fogo” é um exemplo do uso
10
Lógica Matemática
da contra-positiva.
Exemplo 1.7. Contra-positiva (C-Pos) α → β ` ¬β → ¬α.
PROVA:
1
α→β
Premissa
2
¬¬α → α)
DN1
3
¬¬α → β
2+1 S-Hip
4
β → ¬¬β
2+1 DN2 α = β
5
¬¬α → ¬¬β
3+4 S-Hip
6
(¬¬α → ¬¬β) → (¬β → ¬αA5
α = ¬α, β = ¬β
7
¬β → ¬α
5+6 MP
OBS 1.8. Podemos, utilizando o Teorema da dedução, reescrever o propriedade Contra-positiva C-Pos na forma: ` (¬α → ¬β) → (β → α).
Mais uma outra dedução onde o teorema da dedução pode ser aplicado
é na derivação de um teorema que pode substituir o axioma A5 em nossa
linguagem L. A rigor a substituição de um axioma no sistema dedutivo de
uma linguagem gera uma nova linguagem que pode ou não ser equivalente à
primeira. Vamos demonstrar o seguinte teorema: ` (¬α → ¬β) → ((¬α →
β) → α)
Exemplo 1.8. Teorema ` (¬α → ¬β) → ((¬α → β) → α) PROVA:
1
¬α, ¬α → β ` β
MP α ← ¬α
2
¬α ` (¬α → β) → β
TD
3
` ¬α → ((¬α → β) → β)
TD
Fundamentos de Matemática
4
((¬α → β) → β) → (¬β →
11
C-Pos α ← (¬α → β)
¬(¬α → β))
5
` ¬α → (¬β → ¬(¬α → β))
3+4 S-Hip
6
(¬α → (¬β → ¬(¬α → β))) →
3+4 A4 α ← ¬α, β ← ¬β,
((¬α → ¬β) → (¬α → ¬(¬α →
γ ← ¬(¬α → β)
β)))
7
(¬α → β) → (¬α → ¬(¬α → β))
5+6 S-Hip
8
(¬α → ¬(¬α → β)) → ((¬α →
A5 β ← (¬α → β)
β) → α)
9
(¬α → ¬β) → ((¬α → β) → α)
7+8 S-Hip
A regra da simplificação, a próxima a ser demonstrada, corresponde à
regra da eliminação da conjunção em “Dedução Natural” e simbolizada por
E∧.
Exemplo 1.9. A regra da simplificação (Simp) α ∧ β ` β.
PROVA:
1
α∧β
Premissa
2
α ∧ β = ¬(¬α ∨ ¬β)
Def-1
3
¬α ∨ ¬β = ¬¬α → ¬β
Def2 α = ¬α e β = ¬β
4
α ∧ β = ¬(¬¬α → ¬β)
A2 3, 2
5
¬(¬¬α → ¬β)
A2 4,1
6
¬β → (¬¬α → ¬β)
A3 α = ¬β e β = ¬¬α
7
¬(¬¬α → ¬β) → ¬¬β
C-pos α = ¬β, β = ¬¬α → ¬β
8
¬¬β → β)
DN1
9
¬(¬¬α → ¬β) → β
7+8 S-Hip
10
β
5+9 MP
Abriremos espaço, agora, para demonstrar uma das velhas e conheci-
12
Lógica Matemática
das propriedades da igualdade. A propriedade simétrica. O axioma A1
representa a propriedade reflexiva. A propriedades simétrica, pode ser demonstrada usando-se os axiomas A1 e A2. Vamos ao trabalho de demonstrar a propriedade simétrica. Quanto a propriedade transitiva necessita de
mais propriedade que ainda não foram demonstradas, deixaremos para mais
adiante.
Exemplo 1.10. Propriedade simétrica da igualdade (S-igual) x = y ` y =
x.
PROVA:
1
x=y
Premissa
2
(x = x) → (x = x)
A1+A-imp
3
(x = y) → (y = x)
1+2 A1
4
y=x
1+3 MP
O princı́pio do terceiro excluı́do nos diz que uma proposição ou sua
negação é válida. A primeira referência ao princı́pio do terceiro excluı́do
deve-se a Aristóteles quando disse que “de duas proposições contraditórias,
uma deve ser verdade e a outra deve ser falsa”. O princı́pio do terceiro
excluı́do é conhecido como Tertium non datur.
Exemplo 1.11. Princı́pio do terceiro excluı́do (TE) ` α ∨ ¬α.
PROVA:
1
¬α → ¬α
A-imp α = ¬α
2
α ∨ ¬α = ¬α → ¬α
Def1 β = ¬α
3
¬α → ¬α = α ∨ ¬α
S-Igual
4
α ∨ ¬α
3+1A2
Modus tollens (ou modus tollendo tollens) será nossa próxima demons-
Fundamentos de Matemática
13
tração. Simplificando o modus tollens diz que se o conseqüênte de uma
implicação for falso então o antecedente também o será.
Exemplo 1.12. Modus Tollens (MT) ¬β, α → β ` ¬α.
PROVA:
1
¬β
Premissa
2
α→β
Premissa
3
¬¬α → α
DN1
4
¬¬α → β
3+2 S-Hip
5
β → ¬¬β
DN2
6
¬¬α → ¬¬β
4+5 S-Hip
7
(¬¬α → ¬¬β) → (¬β → ¬α)
A5 α = ¬α e β = ¬β
8
¬β → ¬α
6+7 MP
9
¬α
1+8 MP
Nosso próximo passo será a demonstração da comutatividade da disjunção em sua primeira versão. Uma segunda forma de comutatividade da
disjunção será demonstrada mais adiante.
Exemplo 1.13. Comutatividade da disjunção parte 1 (C-Disj-1) α ∨ β `
β ∨ α.
PROVA:
1
α∨β
Premissa
2
α ∧ β = ¬α → β
Def-1
3
¬α → β
2+1 A2
4
β → ¬¬β
DN2 α = β
5
¬α → ¬¬β
3+4 S-Hip
6
(¬α → ¬¬β) → (¬β → α)
A5 α = α e β = ¬β
7
¬β → α
5+6 MP
14
Lógica Matemática
8
β ∨ α = ¬β → α
Def-1 α = β e β = α
9
¬β → α = β ∨ α
S-igual
10
β∨α
9+7 A2
Neste ponto faremos uma pausa com pequenos teoremas que serão muito
úteis nas próximas demonstrações. A saber:
Exemplo 1.14. Teorema 1 (Theor.1) ` (α → ¬¬β) → (α → β).
PROVA:
1
¬¬β → β
DN1
2
(¬¬β → β) → (α → (¬¬β → β))
A3 α = ¬¬β → β e β = α
3
α → (¬¬β → β)
1+2 MP
4
(α → (¬¬β → β)) → ((α →
A4 α = α, β = ¬¬β e γ = β
¬¬β) → (α → β))
5
(α → ¬¬β) → (α → β)
3+4 MP
Exemplo 1.15. Teorema 2 (Theor.2) ` (α → β) → (α → ¬¬β).
PROVA:
1
β → ¬¬β
DN2
2
(β → ¬¬β) → (α → (β → ¬¬β))
A3 α = β → ¬¬β e β = α
3
α → (β → ¬¬β)
1+2 MP
4
(α → (β → ¬¬β)) → ((α → β) →
A4 α = α, β = β e γ = ¬¬β
(α → ¬¬β))
5
(α → β) → (α → ¬¬β)
3+4 MP
Exemplo 1.16. Teorema 3 (Theor.3) ` (¬α → β) → (¬β → α).
PROVA:
Fundamentos de Matemática
15
1
(¬α → β) → (¬α → ¬¬β)
Teor.2 α = ¬α, β = β
2
(¬α → ¬¬β) → (¬β → α)
A5 α = α e β = ¬β
3
(¬α → β) → (¬β → α)
1+2S-Hip
Exemplo 1.17. Teorema 4 (Theor.4) ` ¬(¬α → β) → ¬(¬β → α).
PROVA:
1
(¬β → α) → (¬α → β)
Teor.3 α = β, β = α
2
¬(¬α → β) → ¬(¬β → α)
1+ C-pos α = (¬β → α), β = (¬α → β)
Provaremos agora um dos princı́pios básicos da Lógica Matemática que
é o “Princı́pio da Não Contradição”. Basicamente o princı́pio da não contradição nos diz que na Lógica Matemática não é possı́vel provar ao mesmo
tempo uma proposição e sua negação.
Exemplo 1.18. A regra da não contradição(NC) α → (β ∧ ¬β) ` ¬α.
PROVA:
1
α → (β ∧ ¬β)
Premissa
2
β ∧ ¬β = ¬(¬β ∨ ¬¬β)
Def-2 α = β e β = ¬β
3
¬β ∨ ¬¬β = ¬¬β → ¬¬β
Def1 α = ¬β e β = ¬¬β
4
β ∧ ¬β = ¬(¬¬β → ¬¬β)
4+3 A2
5
α → ¬(¬¬β → ¬¬β)
4+1 A2
6
¬¬(¬¬β → ¬¬β) → ¬α
C-Pos 5
7
¬¬β → ¬¬β
A-Imp α = ¬¬β
8
(¬¬β → ¬¬β) → ¬¬(¬¬β → ¬¬β)
DN2 α = ¬¬β → ¬¬β
9
(¬¬β → ¬¬β) → ¬α
8+6 S-Hip
10
¬α
7+9 MP
Agora uma das regras de introdução da Dedução Natural chamada in-
16
Lógica Matemática
trodução da disjunção, I∨ ou simplesmente adição.
Exemplo 1.19. Adição (AD) β ` α ∨ β.
PROVA:
1
β
Premissa
2
β → (¬α → β)
A3 α = β e β = ¬α
3
¬α → β
1+2 MP
4
α ∨ β = ¬α → β
Def 1
5
¬α → β = α ∨ β
C-igual
6
α∨β
3+5 A2
Provaremos agora uma segunda forma da comutatividade da disjunção.
Exemplo 1.20. Comutatividade da disjunção parte 2 (C-Disj-2) ` α∨β →
β ∨ α.
PROVA:
1
(¬α → β) → (¬β → α)
Theor.3
2
α ∨ β = ¬α → β
Def-1
3
β ∨ α = ¬β → α
Def-1 α = β, β = α
4
¬α → β = α ∨ β
2 S-igual
5
¬β → α = β ∨ α
3S-igual
6
(α ∨ β) → (¬β → α)
1+4 A2
7
(α ∨ β) → (β ∨ α)
5+6 A2
Continuando provaremos agora a comutatividade da conjunção. Para
isto necessitaremos da comutatividade da disjunção na forma da parte 2.
Exemplo 1.21. Comutatividade da conjunção 1 (C-conj-1) α ∧ β ` β ∧ α.
Fundamentos de Matemática
17
PROVA:
1
α∧β
Premissa
2
α ∧ β = ¬(¬α ∨ ¬β)
Def-2
3
¬α ∨ ¬β = ¬(¬¬α → ¬β)
DN1 α = ¬α e eβ = ¬β
4
α ∧ β = ¬(¬¬α → ¬β)
3+2 A2
5
β ∧ α = ¬(¬¬β → ¬α)
4α=β eβ=α
6
(¬β ∨ ¬α) → (¬α ∨ ¬β)
C-Disj α = β e β = α
7
¬β ∨ ¬α = ¬¬β → ¬α
Def-1 α = ¬β e β = ¬α
8
¬α ∨ ¬β = ¬¬α → ¬β
Def-1 α = ¬α e β = ¬β
9
(¬¬β → ¬α) → (¬α ∨ ¬β)
7+6 A2
10
(¬¬β → ¬α) → (¬¬α → ¬β)
8+9 A2
11
¬(¬¬α → ¬β) → ¬(¬¬β → ¬α)
C-Pos. 9
12
(α ∧ β) → ¬(¬¬β → ¬α)
4+11 A2
13
(α ∧ β) → (β ∧ α)
5+12 A2
14
β∧α
1+13 MP
Provaremos agora uma segunda forma da comutatividade da conjunção.
Exemplo 1.22. Comutatividade da conjunção parte 2 (C-Conj-2) ` α ∧
β → β ∧ α.
PROVA:
1
¬(¬¬α → ¬β) → ¬(¬¬β → ¬α)
Theor.4 α = ¬α, β = ¬β
2
α ∧ β = ¬(¬¬α → ¬β)
Def-2
3
β ∧ α = ¬(¬¬β → ¬α
Def-2 α = β, β = α
4
¬(¬¬α → ¬β) = α ∧ β
2 S-igual
5
¬(¬¬β → ¬α) = β ∧ α
3S-igual
6
(α ∧ β) → (¬β → α)
1+4 A2
18
Lógica Matemática
7
(α ∧ β) → (β ∧ α)
5+6 A2
Neste ponto vamos nossa atenção novamente para mostrar as propriedades da igualdade, provando a propriedade transitiva. Para isto usaremos as
propriedades comutativa da conjunção e a regra da simplificação. A saber
Exemplo 1.23. ∀x∀y∀z, x = y ∧ y = z ` x = z Trans.. PROVA:
1
x=y∧y =z
Premissa
2
y =z∧x=y
C-Conj 1
3
y=z
Simp. 1
4
x=y
Simp. 2
5
x=z
3+4 A2
Completando nossa incursão no mundo da igualdade, podemos agora,
definir a igualdade de proposições. Até agora, a igualdade era apenas um
operador abstrato referenciada apenas nos axiomas A1 e A2 e em nossas
demonstrações das propriedades simétrica e transitiva.
Definição 1.4. Dada duas proposições α e β dizemos que α é igual a β,
denotado α = β se, somente se: α ` β ∧ β ` α.
Provaremos agora a propriedade associativa da disjunção parte 1
Exemplo 1.24. Associatividade da disjunção parte 1 (A-Disj.1) α ∨ (β ∨
γ) ` (α ∨ β) ∨ γ.
PROVA:
1
α ∨ (β ∨ γ)
Premissa
2
α ∨ (β ∨ γ) = ¬α → (β ∨ γ)
Def-1 α = α e β = β ∨ γ
3
β ∨ γ = ¬β → γ
Def-1 α = β e β = γ
4
α ∨ (β ∨ γ) = ¬α → (¬β → γ)
A2 2, 3
Fundamentos de Matemática
19
5
¬α → (¬β → γ)
A2 4, 1
6
α → (¬β → α)
A3 α = α e β = ¬β
7
(¬β → α) → (¬α → β)
Theor-1 α = β e β = α
8
α → (¬α → β)
S-Hip 6,7
9
¬(¬α → β) → ¬α
C-Pos. 8
10
¬(¬α → β) → (¬β → γ)
S-Hip 9, 5
11
(¬(¬α → β) → (¬β → γ)) →
A4 α = ¬(¬α → β), β = ¬β e γ = γ
((¬(¬α → β) → ¬β) → (¬(¬α →
β) → γ))
12
β → (¬α → β)
A3 α = β e β = ¬α
13
¬(¬α → β) → ¬β
C-Pos. 12
14
(¬(¬α → β) → ¬β) → (¬(¬α →
MP 10, 11
β) → γ)
15
¬(¬α → β) → γ
MP 13, 14
16
α ∨ β = ¬α → β
Def-1
17
¬(α ∨ β) → γ
A2 16, 15
18
(α ∨ β) ∨ γ = ¬(α ∨ β) → γ
Def-1 α = α ∨ β e β = γ
19
(α ∨ β) ∨ γ
A2 18, 17
Provaremos agora a propriedade associativa da disjunção parte 2
Exemplo 1.25. Associatividade da disjunção parte 2 (A-Disj.2) (α ∨ β) ∨
γ ` α ∨ (β ∨ γ).
PROVA:
1
(α ∨ β) ∨ γ
Premissa
2
(α ∨ β) ∨ γ = ¬(α ∨ β) → γ
Def-1 α = (α ∨ β e β = γ
3
α ∨ β = ¬α → β
Def-1 α = α e β = β
4
(α ∨ β) ∨ γ = ¬(¬α → β) → γ)
2+3 A2
5
¬(¬α → β) → γ
4+1 A2
20
Lógica Matemática
6
¬γ → (¬α → β)
C-Pos
7
(¬γ → (¬α → β)) → ((¬γ →
A4 α = ¬γ, β = ¬α, γ = β
¬α) → (¬γ → β))
8
(¬γ → ¬α) → (¬γ → β)
6+7 MP
9
(¬γ → β) → (¬β → γ)
Theor.3 α = γ, β = β
10
(¬γ → ¬α) → (¬β → γ)
*+9 S-Hip
11
¬α → (¬γ → ¬α)
A3 α = ¬α, β = ¬γ
12
¬α → (¬β → γ)
10+11 S-Hip
13
α ∨ (β ∨ γ = ¬α → (β ∨ γ)
Def1 α = α, β = β ∨ γ
14
β ∨ γ = ¬β → γ
Def-1 α = β, β = γ
15
α ∨ (β ∨ γ) = ¬α → (¬β → γ)
13+14 A2
16
α ∨ (β ∨ γ)
15+12 A2
Nossa próxima demonstração faz parte também, do elenco da regras da
“Dedução Natura”.Trata-se da regra da introdução da conjunção, simbolizada por I∧.
Exemplo 1.26. Introdução da conjunção (I-Conj) α, β ` α ∧ β.
PROVA:
1
α
Premissa
2
β
Premissa
3
(¬α ∨ ¬β) ∨ ¬(¬α ∨ ¬β)
TE α = ¬α ∨ ¬β
4
α ∧ β = ¬(¬α ∨ ¬β)
2+3 Def-2
5
(¬α ∨ ¬β) ∨ (α ∧ β)
4+3 A2
6
¬α ∨ (¬β ∨ (α ∧ β))
A-Disj.2 α = ¬α, β = ¬β,
γ =α∧β
7
8
¬α ∨ (¬β ∨ (α ∧ β) = ¬¬α → (¬β ∨
Def-1 α = ¬α, β = ¬β ∨ (α ∧
(α ∧ β))
β)
¬¬α → (¬β ∨ (α ∧ β))
6+7 A2
Fundamentos de Matemática
21
9
¬β ∨ (α ∧ β) = ¬¬β → (α ∧ β)
Def-1 α = ¬β, β = α ∧ β
10
¬¬α → (¬¬β → (α ∧ β))
8+9 A2
11
α → ¬¬α
DN2
12
α → (¬¬β → (α ∧ β))
10+11 S-Hip
13
¬¬β → (α ∧ β)
1+12 MP
14
β → ¬¬β
DN2 α = β
15
β → (α ∧ β)
13+14 S-Hip
16
α∧β
2+15 MP
A seguir demonstraremos as regras de D’Morgan. Serão ao todo quatro
demonstrações. Duas correspondendo a conjunção e duas correspondendo
a disjunção. Antes porém, vamos demonstrar alguns teoremas que serão
muito úteis.
Exemplo 1.27. Teorema 5 (theor.5) ` (α ∨ ¬¬β) → (α ∨ β).
PROVA:
1
(¬α → ¬¬β) → (¬α → β)
Theor.1 α = ¬α
2
α ∨ ¬¬β = ¬α → ¬¬β
Def-1 β = ¬¬β
3
¬α → ¬¬β = α ∨ ¬¬β
S-Igual
4
α ∨ β = ¬α → β
Def-1
5
¬α → β = α ∨ β
S-Igual
6
(α ∨ ¬¬β) → (α ∨ β)
1+3+5 A2
Exemplo 1.28. Teorema 6 (theor.6) ` (¬¬α ∨ ¬¬β) → (α ∨ β).
PROVA:
1
(¬¬α ∨ ¬¬β) → (¬¬α ∨ β)
Theor.5 α = ¬¬α
2
(¬¬α ∨ β) → (β ∨ ¬¬α)
C-Disj-2
3
(β ∨ ¬¬α) → (β ∨ α)
Theor.5 α = β, β = α
22
Lógica Matemática
4
(β ∨ α) → (α ∨ β)
C-Disj-2
5
(β ∨ ¬¬α) → (α ∨ β)
3+4 S-Hip
6
(¬¬α ∨ β) → (α ∨ β)
2+5 S-Hip
7
(¬¬α ∨ ¬¬β) → (α ∨ β)
1+6 S-Hip
Exemplo 1.29. Teorema 7 (theor.7) ` (α ∨ β) → (α ∨ ¬¬β).
PROVA:
1
(¬α → β) → (¬α → ¬¬β)
Theor.2 α = ¬α
2
α ∨ ¬¬β = ¬α → ¬¬β
Def-1 β = ¬¬β
3
¬α → ¬¬β = α ∨ ¬¬β
S-Igual
4
α ∨ β = ¬α → β
Def-1
5
¬α → β = α ∨ β
S-Igual
6
(α ∨ β) → (α ∨ ¬¬β)
1+3+5 A2
Exemplo 1.30. Teorema 8 (theor.8) ` (α ∨ β) → (¬¬α ∨ ¬¬β).
PROVA:
1
(¬¬α ∨ β) → (¬¬α ∨ ¬¬β)
Theor.7 α = ¬¬α
2
(β ∨ ¬¬α) → (¬¬α ∨ β)
C-Disj-2
3
(β ∨ ¬¬α) → (¬¬α ∨ ¬¬β)
1+2 S-Hip
4
(β ∨ α) → (β ∨ ¬¬α)
Theor.7 α = β, β = α
5
(β ∨ α) → (¬¬α ∨ ¬¬β)
3+4 S-Hip
6
(α ∨ β) → (β ∨ α)
C-Disj-2
7
(α ∨ β) → (¬¬α ∨ ¬¬β)
5+6 S-Hip
Exemplo 1.31. Teorema 9 (theor.9) ` (α ∧ ¬¬β) → (α ∧ β).
PROVA:
Fundamentos de Matemática
23
1
(¬¬α → ¬β) → (¬¬α → ¬¬¬β)
Theor.2 α = ¬¬α, β = ¬β
2
¬(¬¬α → ¬¬¬β) → ¬(¬¬α → ¬β)
C-Pos
3
α ∧ β = ¬(¬¬α → ¬β
Def-2
4
¬(¬¬α → ¬β) = α ∧ β
S-Igual
5
α ∧ ¬¬β = ¬(¬¬α → ¬¬¬β
Def-2 β = ¬¬β
6
¬(¬¬α → ¬¬¬β) = α ∧ ¬¬β
S-Igual
7
(α ∧ ¬¬β) → (α ∧ β)
1+4+6 A2
Exemplo 1.32. Teorema 10 (theor.10) ` (¬¬α ∧ ¬¬β) → (α ∧ β).
PROVA:
1
(¬¬α ∧ ¬¬β) → (¬¬α ∧ β)
Theor.9 α = ¬¬α
2
(¬¬α ∧ β) → (β ∧ ¬¬α)
C-Conj-2
3
(β ∧ ¬¬α) → (β ∧ α)
Theor.9 α = β, β = α
4
(β ∧ α) → (α ∧ β)
C-Conj-2
5
(β ∧ ¬¬α) → (α ∧ β)
3+4 S-Hip
6
(¬¬α ∧ β) → (α ∧ β)
2+5 S-Hip
7
(¬¬α ∧ ¬¬β) → (α ∧ β)
1+6 S-Hip
Exemplo 1.33. Teorema 11 (theor.11) ` (α ∧ β) → (α ∧ ¬¬β).
PROVA:
1
(¬¬α → ¬¬¬β) → (¬¬α → ¬β)
Theor.1 α = ¬¬α, β = ¬β
2
¬(¬¬α → ¬β) → ¬(¬¬α → ¬¬¬β)
C-Pos
3
α ∧ ¬¬β = ¬(¬¬α → ¬¬¬β)
Def-2β = ¬¬β
4
¬(¬¬α → ¬¬¬β) = α ∧ ¬¬β
S-Igual
5
α ∧ β = ¬(¬¬α → ¬β)
Def-2
6
¬(¬¬α → ¬β) = α ∧ β
S-Igual
7
(α ∧ β) → (α ∧ ¬¬β)
1+4+6 A2
24
Lógica Matemática
Exemplo 1.34. Teorema 12 (theor.12) ` (α ∧ β) → (¬¬α ∧ ¬¬β).
PROVA:
1
(¬¬α ∧ β) → (¬¬α ∧ ¬¬β)
Theor.11 α = ¬¬α
2
(β ∧ ¬¬α) → (¬¬α ∧ β)
C-Conj-2
3
(β ∨ ¬¬α) → (¬¬α ∨ ¬¬β)
1+2 S-Hip
4
(β ∧ α) → (β ∧ ¬¬α)
Theor.11 α = β, β = α
5
(β ∧ α) → (¬¬α ∧ ¬¬β)
3+4 S-Hip
6
(α ∧ β) → (β ∧ α)
C-Conj-2
7
(α ∧ β) → (¬¬α ∧ ¬¬β)
5+6 S-Hip
Bom depois de todos estes teoremas vejamos como usa-los nas demonstrações das regras de D’Morgan. Começaremos pela regra de D’Morgan da
disjunção parte 1. A saber.
Exemplo 1.35. D’Morgan da disjunção parte 1 (DM-Disj-1) ` ¬(α∨β) →
(¬α ∧ ¬β).
PROVA:
1
(¬¬α ∨ ¬¬β) → (α ∨ β)
Theor.6
2
¬(α ∨ β) → ¬(¬¬α ∨ ¬¬β)
Cpos
3
¬α ∧ ¬β = ¬(¬α ∨ ¬β)
Def-2 α = ¬α, β = ¬β
4
¬(¬α ∨ ¬β) = ¬α ∧ ¬β
S-Igual
5
¬(α ∨ β) → (¬α ∧ ¬β)
2+4 A2
Continuando, agora demonstraremos a regra D’Morgan da disjunção
parte 2
Exemplo 1.36. D’Morgan da disjunção parte 2 (DM-Disj-2) ` (¬α ∧
¬β) → ¬(α ∨ β).
PROVA:
Fundamentos de Matemática
25
1
(α ∨ β) → (¬¬α ∨ ¬¬β)
Theor.8
2
¬(¬¬α ∨ ¬¬β) → ¬(α ∨ β)
Cpos
3
¬α ∧ ¬β = ¬(¬α ∨ ¬β)
Def-2 α = ¬α, β = ¬β
4
¬(¬α ∨ ¬β) = ¬α ∧ ¬β
S-Igual
5
(¬α ∧ ¬β) → ¬(α ∨ β)
2+4 A2
E agora teremos a demonstração da regra de D’Morgan da conjunção
parte 1. A saber.
Exemplo 1.37. D’Morgan da conjunção parte 1 (DM-Conj-1) ` ¬(α ∧
β) → (¬α ∨ ¬β).
PROVA:
1
(¬¬α ∧ ¬¬β) → (α ∧ β)
Theor.10
2
¬(α ∧ β) → ¬(¬¬α ∧ ¬¬β)
Cpos
3
¬¬α ∧ ¬¬β = ¬(¬¬¬α ∨ ¬¬¬β)
Def-2 α = ¬¬α, β = ¬¬β
4
¬(α ∧ β) → ¬¬(¬¬¬α ∨ ¬¬¬β)
2+3 A2
5
¬¬(¬¬¬α ∨ ¬¬¬β) → (¬¬¬α ∨
DN1
¬¬¬β)
6
¬(α ∧ β) → (¬¬¬α ∨ ¬¬¬β)
4+5 S-Hip
7
(¬¬¬α ∨ ¬¬¬β) → (¬α ∨ ¬β)
4+5 Theor.6 α = ¬α, β = ¬β
8
¬(α ∧ β) → (¬α ∨ ¬β)
6+7 S-Hip
E agora teremos a demonstração da regra de D’Morgan da conjunção
parte 2. A saber.
Exemplo 1.38. D’Morgan da conjunção parte 2 (DM-Conj-2) ` (¬α ∨
¬β) → ¬(α ∧ β).
PROVA:
26
Lógica Matemática
1
(α ∧ β) → (¬¬α ∧ ¬¬β)
Theor.12
2
¬(¬¬α ∧ ¬¬β) → ¬(α ∧ β)
Cpos
3
¬¬α ∧ ¬¬β = ¬(¬¬¬α ∨ ¬¬¬β)
Def-2 α = ¬¬α, β = ¬¬β
4
¬¬(¬¬¬α ∨ ¬¬¬β) → ¬(α ∧ β)
2+3 A2
5
(¬¬¬α ∨ ¬¬¬β) → ¬¬(¬¬¬α ∨
DN2
¬¬¬β)
6
(¬¬¬α ∨ ¬¬¬β) → ¬(α ∧ β)
4+5 S-Hip
7
(¬α ∨ ¬β) → (¬¬¬α ∨ ¬¬¬β)
4+5 Theor.8 α = ¬α, β = ¬β
8
(¬α ∨ ¬β) → ¬(α ∧ β)
6+7 S-Hip
Vamos agora demonstrar mais uma regra da “Dedução Natural” denominada de eliminação da disjunção, simbolizada por: E∨ e bem estranha por
sinal.
Exemplo 1.39. Eliminação da disjunção (E-Disj) α → γ,β → γ,α ∨ β ` γ.
PROVA:
1
α→γ
Premissa
2
β→γ
Premissa
3
α∨β
Premissa
4
α ∨ β = ¬α → β
Def-1
5
¬α → β
3+4 A2
6
¬α → γ
2+5 S-Hip
7
¬γ → ¬α
1 C-Pos β ← γ
8
¬γ → ¬¬α
6 C-Pos α ← ¬α
9
¬¬α → α
DN1
10
¬γ → α
8+9 S-Hip
11
(¬γ → ¬α) → ((¬γ → α) → γ)
Teorema α ← γ, β ← α
12
(¬γ → α) → γ
7+11 S-Hip
13
γ
9+12 S-Hip
Fundamentos de Matemática
27
REFERÊNCIAS BIBLIOGÁFICAS
MORTARI, Cezar Augusto., Introdução à Lógica, Editora UNESP. São
Paulo. 2001.
GASPAR, Marisa, Introdução à Lógica Matemática. Disponı́vel em: http://
mjgaspar.sites.uol.com.br/logica/logica. Acessado em 13/01/2007
ABAR, Celina, Noções de Lógica Matemática. Disponı́vel em: http://www.
pucsp.br/∼logica/. Acessado em 13/01/2007
Índice Remissivo
associatividade
da disjunção, 18, 19
dedução natural, 26
disjunção, 3
auto-implicação, 4
dupla implicação, 3
axioma, 2
dupla negação, 5, 9
da identidade, 2
eliminação
da substituição, 2
da disjunção, 26
de Jan Lukasiewicz, 2
axioma: esquema de, 2
fórmula, 2
molecular, 1
cálculo proposicional clássico, 1
fórmulas
comutatividade
atômicas, 1
da conjunção, 16, 17
da disjunção, 13, 16
conclusão, 3
conectivos, 1, 3
conjunção, 3
simplificação da, 11
inferência, 2
modus ponnes, 2
introdução
da conjunção, 20
da disjunção, 16
contra-positiva, 10
Jan Lukasewicz, 2
D’MOrgan
Jan Lukasiewicz, 2
da disjunção, 24
lógica aristotélica, 2
D’Morgan
lógica intuicionı́sta, 5, 9
da conjunção, 25
da disjunção, 24
meta-teorema, 6
regras de, 21
modus ponnes, 6
Fundamentos de Matemática
modus tollens, 13
não contradição, 15
premissa, 3
princı́pio do terceiro excluı́do, 12
proposição, 1
propriedade
reflexiva, 12
simetrica
da igualdade, 12
transitiva, 12
da igualdade, 18
proriedade
simétrica, 12
prova, 3
por estudo de casos, 7
por indução, 7
silogismo hipotético, 4, 6
teorema da dedução, 6
tertium non datur, 12
29