Difference between revisions of "Exercícios de Dedução Natural"

From Logic Wiki
Jump to navigation Jump to search
m
Tag: 2017 source edit
Tag: 2017 source edit
 
(33 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
=== Derivabilidade de sequentes ===
 
=== Derivabilidade de sequentes ===
 
====<math>\varphi \land \psi \vdash \psi \land \varphi</math>====
 
====<math>\varphi \land \psi \vdash \psi \land \varphi</math>====
<!----><p>{{#ev:youtube|moh07B8dv2k|||||start=480&end=527&loop=1}}</p>
+
: {{#ev:youtube|moh07B8dv2k|||||start=480&end=527&loop=1}}
 
====<math>(\varphi \land \psi) \land \delta \vdash \varphi \land (\psi \land \delta)</math>====
 
====<math>(\varphi \land \psi) \land \delta \vdash \varphi \land (\psi \land \delta)</math>====
<!----><p>{{#ev:youtube|moh07B8dv2k|||||start=528&end=582&loop=1}}</p>
+
: {{#ev:youtube|moh07B8dv2k|||||start=528&end=582&loop=1}}
 
====<math>\varphi \vdash \varphi \land \varphi</math>====
 
====<math>\varphi \vdash \varphi \land \varphi</math>====
<!----><p>{{#ev:youtube|moh07B8dv2k|||||start=583&end=636&loop=1}}</p>
+
: {{#ev:youtube|moh07B8dv2k|||||start=583&end=636&loop=1}}
 
====<math>\alpha \land \beta, \gamma \land \delta \vdash \gamma \land \beta</math>====
 
====<math>\alpha \land \beta, \gamma \land \delta \vdash \gamma \land \beta</math>====
<!----><p>{{#ev:youtube|moh07B8dv2k|||||start=637}}</p>
+
: {{#ev:youtube|moh07B8dv2k|||||start=637}}
 
====<math>\alpha \to (\beta \to \gamma) \vdash \beta \to (\alpha \to \gamma)</math>====
 
====<math>\alpha \to (\beta \to \gamma) \vdash \beta \to (\alpha \to \gamma)</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=579}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=579}}
 
====<math>\vdash \alpha \to (\beta \to \alpha)</math>====
 
====<math>\vdash \alpha \to (\beta \to \alpha)</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=768}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=768}}
 
====<math>\vdash \alpha \to \alpha</math>====
 
====<math>\vdash \alpha \to \alpha</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=888}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=888}}
 
====<math>\alpha \to \beta \vdash \alpha \to (\alpha \to \beta)</math>====
 
====<math>\alpha \to \beta \vdash \alpha \to (\alpha \to \beta)</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=965}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=965}}
 
====<math>\alpha \to (\alpha \to \beta) \vdash \alpha \to \beta</math>====
 
====<math>\alpha \to (\alpha \to \beta) \vdash \alpha \to \beta</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=1015}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=1015}}
 
====<math>\gamma \to \alpha, \gamma \to \beta \vdash \gamma \to (\alpha \land \beta)</math>====
 
====<math>\gamma \to \alpha, \gamma \to \beta \vdash \gamma \to (\alpha \land \beta)</math>====
<!----><p>{{#ev:youtube|mlEYLd56pMg|||||start=1098}}</p>
+
: {{#ev:youtube|mlEYLd56pMg|||||start=1098}}
<!---->
 
 
====<math>\beta \lor (\alpha \land \beta) \vdash \beta</math>====
 
====<math>\beta \lor (\alpha \land \beta) \vdash \beta</math>====
<!----><p>{{#ev:youtube|yUejpYb2NgI|||||start=759}}</p>
+
: {{#ev:youtube|yUejpYb2NgI|||||start=759}}
 
====<math>(\alpha \lor \beta) \to \gamma \vdash (\alpha \to \gamma) \land (\beta \to \gamma)</math>====
 
====<math>(\alpha \lor \beta) \to \gamma \vdash (\alpha \to \gamma) \land (\beta \to \gamma)</math>====
<!----><p>{{#ev:youtube|yUejpYb2NgI|||||start=850}}</p>
+
: {{#ev:youtube|yUejpYb2NgI|||||start=850}}
====<math>\alpha \lor \beta \not\vdash \alpha \land \beta</math>====
 
<!----><p>{{#ev:youtube|yUejpYb2NgI|||||start=1231}}</p>
 
<!-- -->
 
 
====<math>\alpha \vdash \neg\neg\alpha</math>====
 
====<math>\alpha \vdash \neg\neg\alpha</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=463}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=463}}
 
====<math>\beta \to \alpha, \beta \to \neg\alpha \vdash \neg\beta</math>====
 
====<math>\beta \to \alpha, \beta \to \neg\alpha \vdash \neg\beta</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=498}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=498}}
 
====<math>\alpha, \neg\alpha \vdash \neg\beta</math>====
 
====<math>\alpha, \neg\alpha \vdash \neg\beta</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=570}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=570}}
 
====<math>\alpha\lor\beta, \neg\alpha\lor\gamma \vdash \beta\lor\gamma</math>====
 
====<math>\alpha\lor\beta, \neg\alpha\lor\gamma \vdash \beta\lor\gamma</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=596}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=596}}
 
====<math> \alpha\to\beta \vdash \neg\beta\to\neg\alpha</math>====
 
====<math> \alpha\to\beta \vdash \neg\beta\to\neg\alpha</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=741}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=741}}
 
====<math>\neg(\alpha \lor \beta) \dashv\vdash \neg\alpha\land\neg\beta</math>====
 
====<math>\neg(\alpha \lor \beta) \dashv\vdash \neg\alpha\land\neg\beta</math>====
<!----><p>{{#ev:youtube|-Exorelokdo|||||start=817}}</p>
+
: {{#ev:youtube|-Exorelokdo|||||start=817}}
  
 
===Derivabilidade de regras===
 
===Derivabilidade de regras===
  
 
==== <math>\mathrm{(DNE)}</math> a partir de <math>\mathrm{DN_{int}}</math> + (<math>\mathrm{\bot E_{cls}}</math>) ====
 
==== <math>\mathrm{(DNE)}</math> a partir de <math>\mathrm{DN_{int}}</math> + (<math>\mathrm{\bot E_{cls}}</math>) ====
<!---->{{#ev:youtube|0RiYJ5EinRE|||||start=312}}
+
: {{#ev:youtube|0RiYJ5EinRE|||||start=312}}
 
==== <math>(\mathrm{\bot E_{cls}})</math> a partir de <math>\mathrm{DN_{int}}</math> + <math>\mathrm{(DNE)}</math> ====
 
==== <math>(\mathrm{\bot E_{cls}})</math> a partir de <math>\mathrm{DN_{int}}</math> + <math>\mathrm{(DNE)}</math> ====
<!---->{{#ev:youtube|0RiYJ5EinRE|||||start=402}}
+
: {{#ev:youtube|0RiYJ5EinRE|||||start=402}}
 
==== <math>(\mathbb{M})</math> ====
 
==== <math>(\mathbb{M})</math> ====
<!---->{{#ev:youtube|jdHxUb2koy8|||||start=99}}
+
: {{#ev:youtube|jdHxUb2koy8|||||start=99}}
 
==== <math>(\mathbb{R})</math> ====
 
==== <math>(\mathbb{R})</math> ====
<!---->{{#ev:youtube|jdHxUb2koy8|||||start=184}}
+
: {{#ev:youtube|jdHxUb2koy8|||||start=184}}
 
==== <math>(\mathbb{T})</math> ====
 
==== <math>(\mathbb{T})</math> ====
<!---->{{#ev:youtube|jdHxUb2koy8|||||start=226}}
+
: {{#ev:youtube|jdHxUb2koy8|||||start=226}}
  
 
==Dedução Natural para a Lógica Proposicional Clássica==
 
==Dedução Natural para a Lógica Proposicional Clássica==
Line 61: Line 57:
  
 
====Terceiro Excluído / ''Tertium Non Datur'': <math>\vdash\varphi\lor\neg\varphi</math>====
 
====Terceiro Excluído / ''Tertium Non Datur'': <math>\vdash\varphi\lor\neg\varphi</math>====
<!---->{{#ev:youtube|kNyjuCFUzC8}}<!--
+
: {{#ev:youtube|kNyjuCFUzC8}}<!--
 
-->''Tarefa:'' Demonstrar a mesma fórmula, invertendo a ordem de aplicação das regras de introdução da disjunção.
 
-->''Tarefa:'' Demonstrar a mesma fórmula, invertendo a ordem de aplicação das regras de introdução da disjunção.
 
==== <math>\neg\neg\alpha \vdash \alpha</math> ====
 
==== <math>\neg\neg\alpha \vdash \alpha</math> ====
<!---->{{#ev:youtube|0RiYJ5EinRE|||||start=499}}
+
: {{#ev:youtube|0RiYJ5EinRE|||||start=499}}
 
==== <math>\neg\beta\to\alpha, \neg\beta\to\neg\alpha \vdash \beta</math> ====
 
==== <math>\neg\beta\to\alpha, \neg\beta\to\neg\alpha \vdash \beta</math> ====
<!---->{{#ev:youtube|0RiYJ5EinRE|||||start=545}}
+
: {{#ev:youtube|0RiYJ5EinRE|||||start=545}}
 
==== <math>\neg\alpha\to\neg\beta \vdash \beta\to\alpha</math> ====
 
==== <math>\neg\alpha\to\neg\beta \vdash \beta\to\alpha</math> ====
<!---->{{#ev:youtube|0RiYJ5EinRE|||||start=596}}
+
: {{#ev:youtube|0RiYJ5EinRE|||||start=596}}
 
==== <math>\vdash (\alpha \to \beta) \lor (\beta \to \alpha)</math>, via raciocínio por absurdo ====
 
==== <math>\vdash (\alpha \to \beta) \lor (\beta \to \alpha)</math>, via raciocínio por absurdo ====
<!---->{{#ev:youtube|9BdeXjhyJWs|||||start=45}}
+
: {{#ev:youtube|9BdeXjhyJWs|||||start=45}}
 
==== <math>\vdash (\alpha \to \beta) \lor (\beta \to \alpha)</math>, via terceiro excluído ====
 
==== <math>\vdash (\alpha \to \beta) \lor (\beta \to \alpha)</math>, via terceiro excluído ====
<!---->{{#ev:youtube|9BdeXjhyJWs|||||start=413}}
+
: {{#ev:youtube|9BdeXjhyJWs|||||start=413}}
 +
 
 +
==Dedução Natural para a Lógica de Primeira Ordem Intuicionista==
 +
=== Derivabilidade de sequentes ===
 +
==== <math>(\forall x)(\varphi \to \psi) \vdash (\forall x)\varphi \to (\forall x)\psi</math> ====
 +
: {{#ev:youtube|B7fFRZF_wao|||||start=1040}}
 +
==== <math>(\forall x)Q(x) \vdash (\forall y)Q(y)</math> ====
 +
: {{#ev:youtube|B7fFRZF_wao|||||start=1244}}
 +
==== <math>(\forall x_1)(\forall x_2)R(x_1,x_2) \vdash (\forall x_2)(\forall x_1)R(x_1,x_2)</math> ====
 +
: {{#ev:youtube|B7fFRZF_wao|||||start=1303}}
 +
==== <math>(\forall x) \varphi_1 \land \varphi_2 \dashv\vdash (\forall x) \varphi_1 \land (\forall x)\varphi_2</math> ====
 +
: {{#ev:youtube|B7fFRZF_wao|||||start=1678}}
 +
==== <math>(\exists x)P(x), (\forall x)(\forall y)(P(x) \to Q(y)) \vdash (\forall y) Q(y)</math> ====
 +
: {{#ev:youtube|C37Y-1vqRAY|||||start=810}}
 +
==== <math>(\forall x)A(x), (\exists y)(A(y) \to B(y)), (\forall z)(A(z) \to C(z)) \vdash (\exists w)(B(w) \land C(w))</math> ====
 +
: {{#ev:youtube|C37Y-1vqRAY|||||start=1152}}
 +
==== <math>(\exists x)(\varphi_1 \lor \varphi_2) \dashv \vdash (\exists x)\varphi_1 \lor (\exists x)\varphi_2</math> ====
 +
: {{#ev:youtube|C37Y-1vqRAY|||||start=1425}}
 +
==== <math>(\exists x)(\forall y) \varphi \vdash (\forall y)(\exists x) \varphi</math> ====
 +
: {{#ev:youtube|C37Y-1vqRAY|||||start=1701}}
 +
==== <math>(\forall x)\neg\varphi \vdash \neg(\exists x)\varphi</math> ====
 +
: {{#ev:youtube|C37Y-1vqRAY|||||start=1910}}
 +
 
 +
==Dedução Natural para a Lógica de Primeira Ordem Clássica==
 +
 
 +
=== Derivabilidade de sequentes ===
 +
 
 +
==== <math>\neg(\exists x)\neg\varphi \vdash (\forall x)\varphi</math> ====
 +
: {{#ev:youtube|8V6u6BrqJ-M|||||start=188}}
 +
==== <math>\vdash (\exists x)(\forall y)(B(y) \lor \neg B(x))</math> ====
 +
: {{#ev:youtube|8V6u6BrqJ-M|||||start=460}}
  
 
===Derivabilidade de regras===
 
===Derivabilidade de regras===
  
[AGUARDE!]
+
====Raciocínio por casos: <math>\Gamma_1, \neg\varphi\vdash\psi; \Gamma_2, \varphi\vdash\psi \, / \, \Gamma_1, \Gamma_2 \vdash \psi</math>====
 +
: {{#ev:youtube|w-f04Idz-6M|||||end=141&loop=1}}
 +
 
 +
====Raciocínio por redução ao absurdo: <math>\Gamma_1, \neg\varphi\vdash\neg\psi; \Gamma_2, \neg\varphi\vdash\psi \, / \, \Gamma_1, \Gamma_2 \vdash \varphi</math>====
 +
: {{#ev:youtube|w-f04Idz-6M|||||start=149&loop=1}}
 +
 
 +
==== <math>(\approx_{sim}) \Gamma \vdash t_1 \approx t_2 / \Gamma \vdash t_2 \approx t_1</math> ====
 +
: {{#ev:youtube|knltOmL0XEg|||||start=435}}
 +
==== <math>(\approx_{trn}) \Gamma_1 \vdash t_1 \approx t_2; \Gamma_2 \vdash t_2 \approx t_3/ \Gamma_1,\Gamma_2 \vdash t_1 \approx t_3</math> ====
 +
: {{#ev:youtube|knltOmL0XEg|||||start=515}}
 +
 
 +
==Para reflexão==
 +
 
 +
* O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica Intuicionista a regra<!--
 +
--><p><math> (\bot \mathrm{E}_{cls}) \; \Gamma, \neg\varphi \vdash \bot\, / \, \Gamma \vdash \varphi </math></p><!--
 +
--><p>adicionarmos uma regra da forma </p><!--
 +
--><p><math> \Gamma, \neg(\alpha \# \beta) \vdash \bot\, / \, \Gamma \vdash \alpha \# \beta </math></p><!--
 +
--><p>para algum conectivo binário <math>\#</math> da nossa linguagem? </p>
 +
 
 +
* O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica Intuicionista a regra <math> (\bot \mathrm{E}_{cls}) </math> adicionarmos a seguinte regra de ''consequentia mirabilis''?</p><!--
 +
--><p><math> (\neg_{cls}) \; \Gamma, \neg\alpha \vdash \alpha\, / \, \Gamma \vdash \alpha </math></p><!--
 +
--><p>(Será que podemos dizer, neste caso, que se trata de uma regra de introdução ou de eliminação?  E quanta diferença isso faz?)
 +
 
 +
* O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica de Primeira Ordem Intuicionista a regra <math> (\bot \mathrm{E}_{cls}) </math> adicionarmos a regra </p><!--
 +
--><p><math> (DNQ) \; \Gamma \vdash (\forall x)\neg\neg\varphi\, / \, \Gamma \vdash \neg\neg(\forall x)\varphi </math></p>
  
 
==Veja também==
 
==Veja também==
  
*[[Dedução Natural]]
+
* [[Dedução Natural]]
*[[Estratégias de demonstração]]
+
* [[Estratégias de demonstração]]
 +
* [[Introdução Computacional à Lógica Matemática]]
  
 
==Links externos==
 
==Links externos==
  
*
+
* [http://pt.wikipedia.org/wiki/Dedu%C3%A7%C3%A3o_natural Dedução natural]
 +
* [http://pt.wikipedia.org/wiki/Sistema_dedutivo Sistema dedutivo]

Latest revision as of 11:07, 23 July 2021

Contents

Dedução Natural para a Lógica Proposicional Intuicionista

Derivabilidade de sequentes

Derivabilidade de regras

a partir de + ()

a partir de +

Dedução Natural para a Lógica Proposicional Clássica

Derivabilidade de sequentes

Terceiro Excluído / Tertium Non Datur:

Tarefa: Demonstrar a mesma fórmula, invertendo a ordem de aplicação das regras de introdução da disjunção.

, via raciocínio por absurdo

, via terceiro excluído

Dedução Natural para a Lógica de Primeira Ordem Intuicionista

Derivabilidade de sequentes

Dedução Natural para a Lógica de Primeira Ordem Clássica

Derivabilidade de sequentes

Derivabilidade de regras

Raciocínio por casos:

Raciocínio por redução ao absurdo:

Para reflexão

  • O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica Intuicionista a regra

    adicionarmos uma regra da forma

    para algum conectivo binário da nossa linguagem?

  • O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica Intuicionista a regra adicionarmos a seguinte regra de consequentia mirabilis?

    (Será que podemos dizer, neste caso, que se trata de uma regra de introdução ou de eliminação? E quanta diferença isso faz?)

  • O que ocorre se ao invés de adicionarmos ao sistema de Dedução Natural para a Lógica de Primeira Ordem Intuicionista a regra adicionarmos a regra

Veja também

Links externos