Buscar

lista1 gabarito

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Universidade de Bras´ılia
Instituto de Cieˆncias Exatas
Departamento de Cieˆncia da Computac¸a˜o
CIC 117366 Lo´gica Computacional 1 - Turmas A e D (2016/1)
Esta´giario de Doceˆncia: Thiago Mendonc¸a Ferreira Ramos
thiagomendoncaferreiraramos N@SPAM yahoo.com.br
Monitora: Luiza Aguiar Hansen
luizaahansen N@SPAM gmail.com
7 de abril de 2016
Lista: Lo´gica Proposicional - Deduc¸a˜o Natural (Gabarito)
Em adic¸a˜o aos exerc´ıcios que aparecem nas notas de aula, solucione os listados a seguir. Nas
sua derivac¸o˜es, sempre indique qual regra dedutiva e´ utilizada em cada passo.
1. Nos seguintes exerc´ıcios use a prova por induc¸a˜o na estrutura das fo´rmulas.
(a) Demonstre que uma fo´rmula bem formada e´ balanceada, no sentido de que o
nu´mero de pareˆnteses abertos ”(”e´ igual ao de pareˆntese fechados ”)”, isto e´,
|ϕ|( = |ϕ|), para uma fo´rmula ϕ qualquer.
Soluc¸a˜o Consideramos cada um dos poss´ıveis construtores para fo´rmulas:
• Se ϕ for uma constante ou varia´vel proposicional, enta˜o a propriedade vale
por vacuidade, uma vez que neste caso ϕ na˜o possui pareˆnteses.
• Se ϕ = (ϕ1 ? ϕ2), onde ? ∈ {∧,∨,→} enta˜o por hipo´tese de induc¸a˜o |ϕ1|( =
|ϕ1|) e |ϕ2|( = |ϕ2|), logo |ϕ|( = |(ϕ1 ∧ ϕ2)|( = 1 + |ϕ1|( + |ϕ2|( h.i.= 1 + |ϕ1|) +
|ϕ2|) = |(ϕ1 ? ϕ2)|) = |ϕ|).
• Se ϕ = (¬ϕ1) enta˜o por hipo´tese de induc¸a˜o |ϕ1|( = |ϕ1|), logo |ϕ|( =
|(¬ϕ1)|( = 1 + |ϕ1|( h.i.= 1 + |ϕ1|) = |(¬ϕ1)|) = |ϕ|).
(b) Demonstre que para todo prefixo s de uma fo´rmula bem formada ϕ, vale |s|( ≥ |s|).
Soluc¸a˜o Consideramos cada um dos poss´ıveis construtores para fo´rmulas:
• Se ϕ for uma constante ou varia´vel proposicional, enta˜o os poss´ıveis prefixos
de ϕ sa˜o a palavra vazia ou ϕ. Em ambos os casos, temos que |s|( = 0 = |s|),
e portanto |s|( ≥ |s|).
• Se ϕ = (¬ϕ1) enta˜o, por hipo´tese de induc¸a˜o, para qualquer prefixo s′ de
ϕ1 temos que |s′|( ≥ |s′|). Adicionalmente, os poss´ıveis prefixos de ϕ sa˜o
�, (, (¬s′ ou ϕ. Nos dois primeiros casos, ou quando s = ϕ, claramente temos
que |s|( ≥ |s|). Se s = (¬s′ enta˜o |s|( = 1 + |s′|(
h.i.≥ 1 + |s′|) > |s′|) = |s|), e
portanto |s|( ≥ |s|).
1
• Se ϕ = (ϕ?ϕ2), onde ? ∈ {∧,∨,→} enta˜o por hipo´tese de induc¸a˜o temos que
se si e´ um prefixo de ϕi enta˜o |si|( ≥ |si|) (i ∈ {1, 2}). Os poss´ıveis prefixos
de ϕ sa˜o �, (s1, (ϕ1 ∧ s2 e ϕ. No primeiro e no u´ltimo casos, o resultado e´
trivial. Se s = (s1 enta˜o |s|( = 1 + |s1|(
h.i.≥ 1 + |s1|) > |s1|) = |s|), e portanto
|s|( ≥ |s|). Se s = (ϕ1 ? s2 enta˜o |ϕ1|( = |ϕ1|) ja´ que ϕ1 e´ uma fo´rmula bem
formada. Portanto, |s|( = 1+|ϕ1|(+|s2|( = 1+|ϕ1|)+|s2|(
h.i.≥ 1+|ϕ1|)+|s2|) >
|ϕ1|) + |s2|) = |s|). Logo, |s|( ≥ |s|).
(c) Demonstre que a palavra vazia na˜o e´ uma fo´rmula.
Soluc¸a˜o Fo´rmulas da lo´gica proposicional sa˜o constru´ıdas de acordo com a se-
guinte grama´tica:
ϕ ::= ⊥ | > | p | (¬ϕ) | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ→ ϕ)
Desta forma, qualquer fo´rmula possui pelo menos um s´ımbolo, e portanto a pala-
vra vazia na˜o e´ uma fo´rmula.
(d) Demonstre que uma fo´rmula bem formada na˜o tem prefixos pro´prios que sa˜o
tambe´m fo´rmulas: Se ϕ e´ uma fo´rmula bem formada e s e´ prefixo pro´prio de ϕ
enta˜o s na˜o pode ser uma fo´rmula bem formada.
Soluc¸a˜o Consideramos cada um dos poss´ıveis construtores para fo´rmulas:
• Se ϕ for uma constante ou varia´vel proposicional enta˜o a propriedade vale
por vacuidade, uma vez que ϕ na˜o possui prefixos pro´prios.
• Se ϕ = (¬ϕ1) enta˜o os poss´ıveis prefixos pro´prios de ϕ sa˜o �, ( e (¬s′, onde
s′ e´ um prefixo pro´prio de ϕ1. Os dois primeiros casos claramente na˜o sa˜o
fo´rmulas. Suponha que s = (¬s′. Por hipo´tese de induc¸a˜o s′ na˜o e´ fo´rmula
bem formada, e portanto s tambe´m na˜o e´.
• Se ϕ = (ϕ ? ϕ2), onde ? ∈ {∧,∨,→} enta˜o os poss´ıveis prefixos pro´prios de
ϕ sa˜o �, (s1, (ϕ1 e (ϕ1 ? s2, onde si e´ prefixo pro´prio de ϕi (i ∈ {1, 2}). No
primeiro e terceiro casos, na˜o temos fo´rmulas. Se s = (s1 [resp. s = (ϕ1 ? s)]
enta˜o por hipo´tese de induc¸a˜o s1 [resp. s2] na˜o e´ fo´rmula bem formada, e
portanto s na˜o e´ fo´rmula bem formada.
2. “Toda fo´rmula satisfat´ıvel e´ tautolo´gica.” Esta afirmac¸a˜o esta´ correta? Justifique.
Soluc¸a˜o Na˜o esta´, pois existem fo´rmulas que sa˜o satisfat´ıveis e que na˜o sa˜o tautologias.
Por exemplo, a → b satisfat´ıvel porque I(a → b) = T para a interpretac¸a˜o I tal que
I(a) = I(b) = T . No entanto, para a interpretac¸a˜o I ′ tal que I ′(a) = T e I ′(b) = F ,
temos que I ′(a→ b) = F , e portanto a→ b na˜o e´ tautologia.
3. Construa a tabela de verdade e verifique se as fo´rmulas a seguir sa˜o tautologias, con-
tradic¸o˜es ou contingeˆncias. Adicionalmente classifique-as como satisfat´ıveis ou insatis-
fat´ıveis:
2
(a) ψ → (φ→ (φ→ (ψ → φ)))
Soluc¸a˜o Tautologia, e portanto satisfat´ıvel.
φ ψ ψ → φ φ→ (ψ → φ) φ→ (φ→ (ψ → φ) ψ → (φ→ (φ→ (ψ → φ)))
F F T T T T
F T T T T T
T F F F F T
T T T T T T
(b) (φ→ ψ)→ ((δ → γ)→ (φ ∧ δ → ψ ∧ γ))
Soluc¸a˜o Contingeˆncia, e portanto satisfat´ıvel.
φ ψ δ γ φ→ ψ δ → γ φ ∧ δ ψ ∧ γ φ ∧ δ → ψ ∧ γ (δ → γ)→ (φ ∧ δ → ψ ∧ γ)
F F F F T T F F T T
F F F T T T F F T T
F F T F T F F F T T
F F T T T T F F T T
F T F F T T F F T T
F T F T T T F T T T
F T T F T F F F T T
F T T T T T F T T T
T F F F F T F F T T
T F F T F T F F T T
T F T F F F T F F T
T F T T F T T F F F
T T F F T T F F T T
T T F T T T F T T T
T T T F T F T F F T
T T T T T T T T T T
(c) φ→ ¬φ
Soluc¸a˜o Contingeˆncia, e portanto satisfat´ıvel.
φ ¬φ φ→ ¬φ
F T T
T F F
(d) (φ ∧ ψ)→ (ψ ∨ φ)
Soluc¸a˜o Tautologia, e portanto satisfat´ıvel.
φ ψ φ ∧ ψ ψ ∨ φ (φ ∧ ψ)→ (ψ ∨ φ)
F F F F T
F T F T T
T F F T T
T T T T T
(e) ((φ ∧ ψ) ∨ (φ→ δ)) ∧ (¬φ ∨ δ)
Soluc¸a˜o Contingeˆncia, e portanto satisfat´ıvel.
φ ψ δ ¬φ φ ∧ ψ φ→ δ ¬φ ∨ δ (φ ∧ ψ) ∨ (φ→ δ) ((φ ∧ ψ) ∨ (φ→ δ)) ∧ (¬φ ∨ δ)
F F F T F T T T T
F F T T F T T T T
F T F T F T T T T
F T T T F T T T T
T F F F F F F F F
T F T F F T T T T
T T F F T F F T F
T T T F T T T T T
4. Mostre que ¬φ→ ¬ψ e´ consequeˆncia lo´gica de ψ → φ, e vice-versa.
3
Soluc¸a˜o
Seja I uma interpretac¸a˜o qualquer. Temos as seguintes equivaleˆncias: I(ψ → φ) =
V ⇔ I(ψ) = F ou I(φ) = V ⇔ I(¬ψ) = V ou I(¬φ) = F ⇔ I((¬φ)→ (¬ψ)).
5. A a´rvore de deduc¸a˜o abaixo esta´ correta? Justifique e corrija caso a deduc¸a˜o esteja
errada. (Lembre-se que “a↔ b” abrevia “(a→ b) ∧ (b→ a)”.)
[(¬φ→ ψ)→ ¬φ]1 [¬φ→ ψ]2
¬φ (→e)
((¬φ→ ψ)→ ¬φ)→ ¬φ (→i) 1
[¬φ]3
(¬φ→ ψ)→ ¬φ (→i) 2
¬φ→ ((¬φ→ ψ)→ ¬φ) (→i) 3
((¬φ→ ψ)→ ¬φ)↔ ¬φ (∧i)
Soluc¸a˜o Na˜o esta´ correto, pois a hipo´tese 2 na˜o esta´ sendo descartada propriamente.
Na prova acima ha´ duas ramificac¸o˜es, e a hipo´tese 2 aparece na ramificac¸a˜o a esquerda,
logo ela deve ser descartada nesta ramificac¸a˜o, e na˜o na direita, como foi feito.
6. Prove os sequentes a seguir utilizando apenas a lo´gica proposicional intuicionista:
(a) ¬¬¬φ a` ¬φ.
Soluc¸a˜o
(¬i), v
(¬e)
¬¬¬φ (¬i), u
(¬e)
[¬φ]u [φ]v
⊥
¬¬φ
⊥
¬φ
¬φ [¬¬φ]u
⊥ (¬e)
¬¬¬φ (¬i), u
(b) ¬¬(φ→ ψ) ` ¬¬φ→ ¬¬ψ.
Soluc¸a˜o
¬¬(φ→ ψ)
[¬¬φ]u
[¬ψ]v
[φ→ ψ]x [φ]y
ψ
(→e)
⊥ (¬e)
¬φ (¬i), y
⊥ (¬e)
¬(φ→ ψ) (¬i), x
⊥ (¬e)
¬¬ψ (¬i), v
¬¬φ→ ¬¬ψ (→i), u
4
(c) ¬¬(φ ∧ ψ) ` ¬¬φ ∧ ¬¬ψ.
Soluc¸a˜o
¬¬(φ ∧ ψ)
[¬φ]u
[φ ∧ ψ]v
φ
(∧e)
⊥ (¬e)
¬(φ ∧ ψ) (¬i), v
⊥ (¬e)
¬¬φ (¬i), u
¬¬(φ ∧ ψ)
[¬ψ]x
[φ ∧ ψ]y
ψ
(∧e)
⊥ (¬e)
¬(φ ∧ ψ) (¬i), y
⊥ (¬e)
¬¬ψ (¬i), x
¬¬φ ∧ ¬¬ψ (∧i)
(d) ¬(φ ∨ ψ) a` ¬φ ∧ ¬ψ.
Soluc¸a˜o
(¬i), u
(¬e)
¬(φ ∨ ψ) (∨i)
[φ]u
φ ∨ ψ
⊥
¬φ
¬(φ ∨ ψ)
[ψ]v
φ ∨ ψ (∨i)
⊥ (¬e)
¬ψ (¬i), v
¬φ ∧ ¬ψ (∧i)
[(φ ∨ ψ)]u (¬e)
(∧e)
(¬φ ∧ ¬ψ)
¬φ [φ]x
⊥
(¬φ ∧ ¬ψ)
¬ψ (∧e) [ψ]y
⊥ (¬e)
⊥ (∨e), x, y
¬(φ ∨ ψ) (¬i), u
(e) φ→ ψ ` δ ∨ φ→ δ ∨ ψ
Soluc¸a˜o
[δ ∨ φ]z
φ→ ψ [φ]x
ψ
ψ ∨ δ (∨i)
(→e)
[δ]y
ψ ∨ δ (∨i)
ψ ∨ δ (∨e) , x, y
δ ∨ φ→ δ ∨ ψ (→i) , z
(f) (δ ∧ φ) ∨ (δ ∧ ψ) a` δ ∧ (φ ∨ ψ) (Distributividade)
Soluc¸a˜o5
(δ ∧ φ) ∨ (δ ∧ ψ)
[δ ∧ φ]u
δ
(∧e)
[δ ∧ ψ]v
δ
(∧e)
δ
(∨e) u, v
(δ ∧ φ) ∨ (δ ∧ ψ)
[δ ∧ φ]x
φ
(∧e)
φ ∨ ψ
(∨i)
[δ ∧ ψ]t
ψ
(∧e)
φ ∨ ψ
(∨i)
φ ∨ ψ
(∨e) x, t
δ ∧ (φ ∨ ψ) ∧i
δ ∧ (φ ∨ ψ)
φ ∨ ψ (∧e)
δ ∧ (φ ∨ ψ)
δ
(∧e)
[φ]x
δ ∧ φ (∧i)
(δ ∧ φ) ∨ (δ ∧ ψ) (∨i)
δ ∧ (φ ∨ ψ)
δ
(∧e)
[ψ]y
δ ∧ ψ (∧i)
(δ ∧ φ) ∨ (δ ∧ ψ) (∨i)
(δ ∧ φ) ∨ (δ ∧ ψ) (∨e), x, y
Questo˜es e itens “6e”e “6f”foram baseadas nos itens “b” e “e”da primeira questa˜o em:
http://wiki.di.uminho.pt/twiki/pub/Education/MFES/VF/exerciciosCoq.pdf
7. A lo´gica cla´ssica e´ obtida acrescentando-se qualquer uma das seguintes regras a` lo´gica
proposicional intuicionista:
[¬φ]u
...
⊥
φ
(PPC),u
φ ∨ ¬φ LTE
¬¬φ
φ
(¬¬-e)
((φ→ ψ)→ φ)→ φ LP
Prove que quaisquer treˆs destas regras pode ser provada a partir da quarta regra
restante, ou seja:
(a) Adicione a regra PPC ao conjunto de regras da lo´gica proposicional intuicionista.
Com este novo conjunto de regras prove os sequentes correspondentes a` lei do
terceiro exclu´ıdo e a` eliminac¸a˜o da dupla negac¸a˜o:
i. ` φ ∨ ¬φ
Soluc¸a˜o
[φ]v
φ ∨ ¬φ (∨i) [¬(φ ∨ ¬φ)]u
⊥ (¬e)
¬φ (¬i) , v
φ ∨ ¬φ (∨i) [¬(φ ∨ ¬φ)]u
⊥ (¬e)
φ ∨ ¬φ (PPC) , u
6
ii. ¬¬φ ` φ
Soluc¸a˜o
¬¬φ [¬φ]u
⊥ (¬e)
φ
(PPC) , u
iii. ` ((φ→ ψ)→ φ)→ φ
Soluc¸a˜o
[((φ→ ψ)→ φ)]x
[¬φ]u
¬ψ → ¬φ →i, ∅ [¬ψ]v
¬φ (→e) [φ]w
⊥ (¬e)
ψ
(PBC), v
φ→ ψ (→i), w
φ
(→e)
[¬φ]u
⊥ (¬e)
φ
(PBC), u
((φ→ ψ)→ φ)→ φ (→i), x
(b) Adicione a regra (¬¬-e) ao conjunto de regras da lo´gica proposicional intuicionista.
Com este novo conjunto de regras prove:
i. ` φ ∨ ¬φ
Soluc¸a˜o
[φ]v
φ ∨ ¬φ (∨i) [¬(φ ∨ ¬φ)]u
⊥ (¬e)
¬φ (¬i) , v
φ ∨ ¬φ (∨i) [¬(φ ∨ ¬φ)]u
⊥ (¬e)
¬¬(φ ∨ ¬φ) (¬i) , u
φ ∨ ¬φ (¬¬ -e)
ii. ¬φ→ ⊥ ` φ
Soluc¸a˜o
¬φ→ ⊥ [¬φ]u
⊥ (→e)
¬¬φ (¬i)
φ
(¬¬ -e)
7
iii. ` ((φ→ ψ)→ φ)→ φ
Soluc¸a˜o
[φ]1 [¬φ]y
⊥ (¬e)
ψ
(⊥e)
φ→ ψ (→i) , x [(φ→ ψ)→ φ]z
φ
(→e)
[¬φ]y
⊥ (¬e)
¬¬φ (¬i) , y
φ
(¬¬ -e)
((φ→ ψ)→ φ)→ φ (→i) , z
(c) Adicione a regra LEM ao conjunto de regras da lo´gica proposicional intuicionista.
Com este novo conjunto de regras prove:
i. ¬φ→ ⊥ ` φ
Soluc¸a˜o
φ ∨ ¬φ LEM [φ]v
¬φ→ ⊥ [¬φ]u
⊥ (→e)
φ
(⊥e)
φ
(∨e) , v, u
ii. ¬¬φ ` φ
Soluc¸a˜o
φ ∨ ¬φ LEM [φ]v
¬¬φ [¬φ]u
⊥ (→e)
φ
(⊥e)
φ
(∨e) , v, u
iii. ` ((φ→ ψ)→ φ)→ φ
Soluc¸a˜o
8
φ ∨ ¬φ LEM [φ]z
[¬φ]x [φ]y
⊥ (¬e)
ψ
(⊥e)
φ→ ψ (→i) , y [(φ→ ψ)→ φ]w
φ
(→e)
φ
(∨e) , x, z
((φ→ ψ)→ φ)→ φ (→i) , w
(d) Adicione a regra LP ao conjunto de regras da lo´gica proposicional intuicionista.
Com este novo conjunto de regras prove:
i. ¬φ→ ⊥ ` φ
Soluc¸a˜o
((φ→ ¬φ)→ φ)→ φ
¬φ→ ⊥
[φ→ ¬φ]x [φ]y
¬φ (→e) ¬φ→ ⊥
⊥ (→e)
¬φ (¬i) y
⊥ (→e)
φ
(⊥e)
(φ→ ¬φ)→ φ (→i) x
φ
(→e)
ii. ¬¬φ ` φ
Soluc¸a˜o
((φ→ ¬φ)→ φ)→ φ
¬¬φ
[φ→ (¬φ)]x ¬¬φ
¬φ (MT )
⊥ (¬e)
φ
(⊥e)
(φ→ ¬φ)→ φ (→i) x
φ
(→e)
iii. ` φ ∨ ¬φ
Soluc¸a˜o
(((φ ∨ ¬φ)→ ¬φ)→ (φ ∨ ¬φ))→ (φ ∨ ¬φ)
[φ]x
[(φ ∨ ¬φ)→ ¬φ]y
[φ]x
φ ∨ ¬φ (∨i)
¬φ (→e)
⊥ (¬e)
¬φ (¬i) x
φ ∨ ¬φ (∨i)
(((φ ∨ ¬φ)→ ¬φ)→ (φ ∨ ¬φ)) (→i) y
φ ∨ ¬φ (→e)
9
8. Construa provas para todas as variantes das regras MT e CP e indique quais derivac¸o˜es
sa˜o da lo´gica cla´ssica e quais da lo´gica intuicionista proposicional:
±φ→ ±ψ ∓ ψ
∓φ (MT1 e 2)
±/± φ→ ±/∓ ψ
∓/± ψ → ∓/∓ φ (CP1,2,3 e 4)
Soluc¸a˜o
Intuicionista
φ→ ψ [φ]x
ψ
(→e) ¬ψ
⊥ (¬e)
¬φ (¬i) x
Cla´ssica
¬φ→ ¬ψ [¬φ]x
¬ψ (→e) ψ
⊥ (¬e)
φ
(PBC) x
Intuicionista
φ→ ψ [¬ψ]u
¬φ MT
¬ψ → ¬φ (→i) u
Cla´ssica
¬φ→ ¬ψ
[ψ]u
¬¬ψ (¬¬i)
¬¬φ MT
φ
(¬¬e)
ψ → φ (→i) u
Intuicionista
φ→ ¬ψ [φ]x
¬ψ (→e) [ψ]y
⊥ (¬e)
¬φ (¬i) x
ψ → ¬φ (→i) y
Cla´ssica
¬φ→ ψ [¬φ]x
ψ
(→e)
[¬ψ]y
⊥ (¬e)
φ
(PBC) x
¬ψ → φ (→i) y
10
9. Construa deduc¸o˜es para provar que:
(a) (φ ∧ ψ) ∧ ϕ a` φ ∧ (ψ ∧ ϕ).
Soluc¸a˜o
∧e
∧e
(φ ∧ ψ) ∧ ϕ
(φ ∧ ψ)
φ
∧e
∧e
(φ ∧ ψ) ∧ ϕ
φ ∧ ψ
ψ
(φ ∧ ψ) ∧ ϕ
ϕ
∧e
(ψ ∧ ϕ) ∧i
φ ∧ (ψ ∧ ϕ) ∧i
∧i
∧e
φ ∧ (ψ ∧ ϕ)
φ
φ ∧ (ψ ∧ ϕ)
(ψ ∧ ϕ) ∧e
ψ
∧e
(φ ∧ ψ)
φ ∧ (ψ ∧ ϕ)
(ψ ∧ ϕ) ∧e
ϕ
∧e
(φ ∧ ψ) ∧ ϕ ∧i
(b) (φ ∨ ψ) ∨ ϕ a` φ ∨ (ψ ∨ ϕ).
Soluc¸a˜o
(φ ∨ ψ) ∨ ϕ
[(φ ∨ ψ)]x
[φ]z
φ ∨ (ψ ∨ ϕ) (∨i)
[ψ]w
(ψ ∨ ϕ) (∨i)
φ ∨ (ψ ∨ ϕ) (∨i)
φ ∨ (ψ ∨ ϕ) (∨e)z, w
[ϕ]y
(ψ ∨ ϕ) (∨i)
φ ∨ (ψ ∨ ϕ) (∨i)
φ ∨ (ψ ∨ ϕ) (∨e)x, y
φ ∨ (ψ ∨ ϕ)
[φ]x
(φ ∨ ψ) (∨i)
(φ ∨ ψ) ∨ ϕ (∨i)
[(ψ ∨ ϕ)]y
[ψ]u
(φ ∨ ψ) (∨i)
(φ ∨ ψ) ∨ ϕ (∨i)
[ϕ]v
(φ ∨ ψ) ∨ ϕ (∨i)
(φ ∨ ψ) ∨ ϕ (∨e)u, v
(φ ∨ ψ) ∨ ϕ (∨e)x, y
(c) ¬¬φ ∧ ¬¬ψ ` ¬¬(φ ∧ ψ).
Soluc¸a˜o
11
¬¬φ ∧ ¬¬ψ
¬¬φ (∧e)
φ
(¬¬ -e)
¬¬φ ∧ ¬¬ψ
¬¬ψ (∧e)
ψ
(¬¬ -e)
φ ∧ ψ (∧i) [¬(φ ∧ ψ)]x
⊥ (¬e)
¬¬(φ ∧ ψ) (¬i) x
(d) φ ∨ ψ a` ¬(¬φ ∧ ¬ψ).
Soluc¸a˜o
φ ∨ ψ
[¬φ ∧ ¬ψ]u
¬φ (∧e) [φ]x
⊥ (¬e)
[¬φ ∧ ¬ψ]u
¬ψ (∧e) [ψ]y
⊥ (¬e)
⊥ (∨e), x, y
¬(¬φ ∧ ¬ψ) (¬i), u
¬(¬φ ∧ ¬ψ)
(¬i), u
(¬e) [¬(φ ∨ ψ)]
w (∨i) [φ]
u
φ ∨ ψ
⊥
¬φ
[¬(φ ∨ ψ)]w
[ψ]v
φ ∨ ψ (∨i)
⊥ (¬e)
¬ψ (¬i), v
¬φ ∧ ¬ψ (∧i)
⊥ (¬e)
φ ∨ ψ (PBC) w
(e) φ ∧ ψ a` ¬(¬φ ∨ ¬ψ).
Soluc¸a˜o
[¬φ ∨ ¬ψ]u
φ ∧ ψ
φ
(∧e)
[¬φ]x
⊥ (¬e)
φ ∧ ψ
ψ
(∧e)
[¬ψ]y
⊥ (¬e)
⊥ (∨e), x, y
¬(¬φ ∨ ¬ψ) (¬i), u
¬(¬φ ∨ ¬ψ)
ψ ∨ ¬ψ LEM
[φ]z [ψ]x
φ ∧ ψ (∧i)¬(φ ∧ ψ)
⊥ (¬e)
¬φ (¬i) z
¬φ ∨ ¬ψ (∨i)
[¬ψ]y
¬φ ∨ ¬ψ (∨i)
¬φ ∨ ¬ψ (∨e) x, y
⊥ (¬e)
φ ∧ ψ (PBC), u
12
(f) φ↔ ψ a` ¬ψ ↔ ¬φ
Soluc¸a˜o
Inicialmente, observe que φ↔ ψ ≡ (φ→ ψ) ∧ (ψ → φ).
(φ→ ψ) ∧ (ψ → φ)
φ→ ψ
¬ψ → ¬φ CP1
(∧e)
(φ→ ψ) ∧ (ψ → φ)
ψ → φ
¬φ→ ¬ψ CP1
(∧e)
(¬ψ → ¬φ) ∧ (¬φ→ ¬ψ) (∧i)
(¬ψ → ¬φ) ∧ (¬φ→ ¬ψ)
¬ψ → ¬φ (∧e)
φ→ ψ CP2
(¬ψ → ¬φ) ∧ (¬φ→ ¬ψ)
¬φ→ ¬ψ (∧e)
ψ → φ CP2
(φ→ ψ) ∧ (ψ → φ) (∧i)
13

Outros materiais