path: root/logic/n7.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style swiss
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
Un 
\series bold
sistema deductivo
\series default
 es un conjunto de axiomas y reglas de inferencia sintácticas (
\begin_inset Formula $\vdash$
\end_inset

).
 Una 
\series bold
demostración
\series default
 o 
\series bold
prueba formal
\series default
 es una secuencia de conjuntos de fórmulas en las que cada fórmula es un
 axioma o puede obtenerse del conjunto anterior mediante una regla de inferencia.
 Cada elemento 
\begin_inset Formula $\alpha$
\end_inset

 del último conjunto de la secuencia se llama 
\series bold
teorema por deducción
\series default
, y se dice que 
\begin_inset Formula $\alpha$
\end_inset

 es 
\series bold
demostrable
\series default
, lo que escribimos como 
\begin_inset Formula $\vdash\alpha$
\end_inset

.
\end_layout

\begin_layout Standard
Un sistema deductivo en L0 y L1 es 
\series bold
sólido
\series default
 si y sólo si 
\begin_inset Formula $\vdash\alpha\implies\vDash\alpha$
\end_inset

, es decir, si cualquier conclusión 
\series bold
derivable
\series default
 o 
\series bold
deducible 
\series default
a partir de las reglas es válida, y es 
\series bold
completo
\series default
 cuando 
\begin_inset Formula $\vDash\alpha\implies\vdash\alpha$
\end_inset

.
 Un conjunto de reglas es 
\series bold
inconsistente
\series default
 si 
\begin_inset Formula $\vdash\alpha\land\neg\alpha$
\end_inset

, y es 
\series bold
consistente
\series default
 si no es inconsistente.
\end_layout

\begin_layout Standard
Dada una oración 
\begin_inset Formula $\alpha$
\end_inset

 y un conjunto de oraciones 
\begin_inset Formula ${\cal F}$
\end_inset

, 
\begin_inset Formula $\vDash\alpha$
\end_inset

 significa que 
\begin_inset Formula $\alpha$
\end_inset

 es válida y 
\begin_inset Formula ${\cal F}\vDash\alpha$
\end_inset

 significa que 
\begin_inset Formula $\alpha$
\end_inset

 es consecuencia lógica de 
\begin_inset Formula ${\cal F}$
\end_inset

.
 Por su parte 
\begin_inset Formula $\vdash\alpha$
\end_inset

 significa que 
\begin_inset Formula $\alpha$
\end_inset

 es demostrable y 
\begin_inset Formula ${\cal F}\vdash\alpha$
\end_inset

 significa que 
\begin_inset Formula $\alpha$
\end_inset

 es deducible de 
\begin_inset Formula ${\cal F}$
\end_inset

, y representa una 
\series bold
deducción
\series default
 o 
\series bold
razonamiento
\series default
, donde 
\begin_inset Formula $\alpha$
\end_inset

 es la conclusión o 
\series bold
derivación
\series default
 y las 
\begin_inset Formula $\psi\in{\cal F}$
\end_inset

 son las premisas, las fórmulas usadas para llegar a 
\begin_inset Formula $\alpha$
\end_inset

.
 
\end_layout

\begin_layout Standard
Decimos que un conjunto de oraciones 
\begin_inset Formula ${\cal T}$
\end_inset

 es una 
\series bold
teoría
\series default
 si 
\begin_inset Formula $\forall\alpha({\cal T}\vDash\alpha\implies\alpha\in{\cal T})$
\end_inset

, y entonces cada 
\begin_inset Formula $\alpha\in{\cal T}$
\end_inset

 es un 
\series bold
teorema
\series default
.
 Una teoría es 
\series bold
axiomatizable
\series default
 si existe un subconjunto 
\begin_inset Formula ${\cal F}$
\end_inset

 tal que 
\begin_inset Formula ${\cal T}=\{\alpha|{\cal F}\vDash\alpha\}$
\end_inset

, y cada 
\begin_inset Formula $\alpha\in{\cal F}$
\end_inset

 es un 
\series bold
axioma
\series default
, y es 
\series bold
contradictoria
\series default
 o 
\series bold
inconsistente
\series default
 cuando 
\begin_inset Formula ${\cal T}\vDash\alpha$
\end_inset

 y 
\begin_inset Formula ${\cal T}\vDash\neg\alpha$
\end_inset

.
\end_layout

\begin_layout Standard
Una teoría es 
\series bold
decidible
\series default
 si se puede determinar la consistencia o inconsistencia de una fórmula
 mediante un algoritmo; 
\series bold
semidecidible
\series default
 si hay fórmulas cuya inconsistencia no puede ser probada algorítmicamente,
 e 
\series bold
indecidible
\series default
 si no es posible crear un algoritmo que determine la consistencia o inconsisten
cia de una fórmula.
\end_layout

\begin_layout Standard

\series bold
Hilbert
\series default
 opinaba que todo sistema fundamental matemático debía ser consistente,
 completo y decidible, pero Kurt
\series bold
 Gödel
\series default
 demostró que ningún sistema capaz de representar los números naturales
 puede ser a la vez consistente y completo, y que la consistencia no puede
 probarse con los propios axiomas del sistema, por lo que habrá verdades
 que no se pueden demostrar.
 Alan 
\series bold
Turing
\series default
, por su parte, demostró que solo sistemas muy restrictivos son decidibles.
\end_layout

\begin_layout Standard
Un sistema deductivo cumple el 
\series bold
teorema de la deducción
\series default
 si verifica que, dado el conjunto 
\begin_inset Formula ${\cal F}$
\end_inset

 y las fórmulas 
\begin_inset Formula $\alpha$
\end_inset

 y 
\begin_inset Formula $\beta$
\end_inset

, 
\begin_inset Formula ${\cal F}\cup\{\alpha\}\vdash\beta\iff{\cal F}\vdash\alpha\rightarrow\beta$
\end_inset

.
 Así, 
\begin_inset Formula ${\cal F}\cup\{\alpha_{1},\dots,\alpha_{n}\}\vdash\beta\iff{\cal F}\cup\{\alpha_{1},\dots,\alpha_{n-1}\}\vdash\alpha_{n}\rightarrow\beta\iff\dots\iff{\cal F}\vdash\alpha_{1}\rightarrow(\alpha_{2}\rightarrow\cdots(\alpha_{n}\rightarrow\beta)\cdots)$
\end_inset

.
 Este teorema simplifica mucho las demostraciones, si bien no se probó su
 corrección hasta 1930.
 No todos los sistemas cumplen en teorema de la deducción, si bien el Teorema
 de la Deducción Semántica (
\begin_inset Formula ${\cal F}\cup\{a\}\vDash\beta\iff{\cal F}\vDash\alpha\rightarrow\beta$
\end_inset

) se cumple siempre.
 Decimos que 
\begin_inset Formula ${\cal F}$
\end_inset

 es 
\series bold
sintácticamente completo
\series default
 si para todo 
\begin_inset Formula $\alpha$
\end_inset

, 
\begin_inset Formula ${\cal F}\vdash\alpha$
\end_inset

 o 
\begin_inset Formula ${\cal F}\vdash\neg\alpha$
\end_inset

.
\end_layout

\begin_layout Standard
Un 
\series bold
razonamiento deductivo
\series default
 es el que parte de unas hipótesis básicas para obtener unas consecuencias
 (
\begin_inset Formula $\alpha\vDash\beta$
\end_inset

).
 Normalmente parte de premisas sobre aspectos generales para concluir aspectos
 particulares.
 La relación entre premisas y conclusión es de implicación (
\begin_inset Formula $\alpha\vDash\beta\iff\vDash\alpha\rightarrow\beta$
\end_inset

).
 Algunos tipos de 
\series bold
demostración
\series default
 deductiva (de 
\begin_inset Formula $\vDash\alpha\rightarrow\beta$
\end_inset

):
\end_layout

\begin_layout Itemize

\series bold
Vacía
\series default
 de 
\begin_inset Formula $\alpha\rightarrow\beta$
\end_inset

: 
\begin_inset Formula $\forall v_{I},v(\alpha)=F$
\end_inset

 (no se usa 
\begin_inset Formula $\beta$
\end_inset

).
\end_layout

\begin_layout Itemize

\series bold
Trivial
\series default
: 
\begin_inset Formula $\forall v_{I},v(\beta)=V$
\end_inset

 (no se usa 
\begin_inset Formula $\alpha$
\end_inset

).
\end_layout

\begin_layout Itemize

\series bold
Directa
\series default
: Probar que 
\begin_inset Formula $\alpha\vDash\beta$
\end_inset

 usando definiciones o teoremas ya probados, como el Modus Ponens.
\end_layout

\begin_layout Itemize

\series bold
Por contrarrecíproco
\series default
: 
\begin_inset Formula $\alpha\rightarrow\beta\equiv\neg\beta\rightarrow\neg\alpha$
\end_inset

.
\end_layout

\begin_layout Itemize

\series bold
Por contradicción
\series default
: 
\begin_inset Formula $\alpha\rightarrow\beta\equiv\alpha\land\neg\beta\rightarrow\gamma\land\neg\gamma$
\end_inset

.
\end_layout

\begin_layout Itemize

\series bold
Indirecta
\series default
: Si 
\begin_inset Formula $\alpha\vDash\gamma$
\end_inset

 y 
\begin_inset Formula $\gamma\vDash\beta$
\end_inset

 entonces 
\begin_inset Formula $\alpha\vDash\beta$
\end_inset

.
\end_layout

\begin_layout Standard
La 
\series bold
refutación por contraejemplo
\series default
 consiste en buscar 
\begin_inset Formula $a$
\end_inset

 tal que 
\begin_inset Formula $v(\alpha[a]\rightarrow\beta[a])=F$
\end_inset

.
\end_layout

\begin_layout Standard
Un 
\series bold
razonamiento inductivo
\series default
 consiste en obtener reglas generales a partir de casos particulares.
 Para ello se observan, registran y analizan hechos y se formulan leyes
 universales a modo de hipótesis o conjeturas, tras lo cual se diseñan experimen
tos para ver que estas leyes se cumplen.
\end_layout

\begin_layout Standard
La 
\series bold
inducción matemática
\series default
, sin embargo, se puede probar de forma deductiva, si bien esto requiere
 lógica de segundo orden.
 En 
\begin_inset Formula $\mathbb{N}$
\end_inset

, para un 
\begin_inset Formula $n_{0}\in\mathbb{N}$
\end_inset

, tenemos:
\end_layout

\begin_layout Itemize

\series bold
Principio de inducción débil
\series default
: 
\begin_inset Formula $\{P(n_{0})\}\cup\bigcup_{n\geq n_{0}}\{P(n)\rightarrow P(n+1)\}\vDash\forall n\geq n_{0},P(n)$
\end_inset

.
\end_layout

\begin_layout Itemize

\series bold
Principio de inducción fuerte
\series default
: 
\begin_inset Formula $\{P(n_{0})\}\cup\bigcup_{n\geq n_{0}}\{P(n_{0})\land\dots\land P(n)\rightarrow P(n+1)\}\vDash\forall n\geq n_{0},P(n)$
\end_inset

.
\end_layout

\begin_layout Standard
El 
\series bold
principio de inducción estructural
\series default
 para 
\series bold
demostración por recursión
\series default
 es una generalización de la inducción y afirma que, dado un conjunto de
 elementos definido por recursión con una serie de casos base y reglas de
 recursión sobre estos, si una propiedad se cumple para cada caso base,
 y si en cada regla de recursión si la propiedad se cumple para los parámetros
 de entrada también se cumple para el elemento resultante de aplicarla,
 entonces esta propiedad la cumplen todos los elementos del conjunto.
\end_layout

\end_body
\end_document