Baixe o app para aproveitar ainda mais
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
Compartilhar