Cómo desmitificar los axiomas de la lógica proposicional?

Question

¿Cómo podría yo ir sobre conseguir algo de intuición en los típicos esquemas de axioma dado para la lógica proposicional? Parecen bastante misterioso a primera vista.

Por ejemplo, estas son tomadas de: http://en.wikipedia.org/wiki/Hilbert_system#Logical_axioms

• $\phi \to \phi$
• $\phi \to \left( \psi \to \phi \right)$
• $\left ( \phi \to ( \psi \rightarrow \xi \right)) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)$
• $\left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right)$

Answer 1

Hay buenas respuestas ya, pero una nota:

Otra manera de entender la elección de los tres primeros axiomas de citar es que son exactamente lo que usted necesita con el fin de ser capaz de demostrar el Teorema de la Deducción por inducción sobre la longitud de la interna de la prueba.

• $H\to H$ toma el cuidado de un paso en la prueba original que sólo se aplica la hipótesis.

• $A \to (H \to A)$ permite traducir un paso en la prueba original que introduce una lógica axioma.

• $(H \to (P\to Q)) \to ((H \to P) \to (H\to Q))$ es lo que usted necesita traducir una aplicación del Modus Ponens.

En realidad resulta que $H\to H$ puede ser derivada a partir de los otros dos (a pesar de que no es muy intuitivo), por lo que en muchas de las presentaciones será a la izquierda.

Hay muchas maneras diferentes para completar estos tres axiomas de tal manera que usted puede demostrar exactamente todos los proposicional tautologías que puede ser escrito utilizando $\neg$$\to$. El que usted está citando tiene la ventaja de ser relativamente simple, intuitiva y evidente, mientras que todavía siendo suficiente para permitir que todas las tautologías para ser probado.

Juntos, el Teorema de la Deducción y el Modus Ponens, nos dice mucho acerca de cómo la $\to$ conectivo funciona, pero resulta que hay proposicional tautologías escrito con $\to$ solo que no puede ser demostrado por estos dos ingredientes. Es notable que el simple aspecto cuarto axioma puede administrar en una sola respiración para decirnos todo lo demás que hay que saber acerca de $\to$, así como (al mismo tiempo) todo sobre $\neg$. No tengo ninguna buena explicación intuitiva de cómo lo hace. Sólo puedo demostrar que lo hace.

Answer 2

Supongo que usted entiende por qué estos axiomas son tautologías (es decir, bajo todas la verdad asignaciones) y que su pregunta es por qué estos fueron elegidos, de entre el número infinito de todas las tautologías, para servir como axiomas. Varios factores intervienen en esta elección (yo creo --- la elección se hizo realidad mucho antes de que yo estaba a su alrededor).

Primero, había bastante arbitraria decisión de utilizar $\to$ $\neg$ como la primitiva conectivos, a fin de que todas las otras conectivas ($\land,\lor, \iff$) son vistos como abreviaturas. Había otras conectivas sido elegido como primitiva, que han estado involucrados en los axiomas.

Segundo, haber incluido en $\to$ entre las nociones primitivas, uno de ellos tiene una muy simple y ampliamente utilizado (desde los tiempos antiguos) regla de inferencia, es decir, modus ponens: De$\phi\to\psi$$\phi$, inferir $\psi$. El deseo de usar esta regla puede haber motivado la elección de $\to$ como una de las nociones primitivas; el otro, $\neg$, puede haber sido motivado como la cosa más simple que, junto con la $\to$, permite definir todas las otras conectivas.

En tercer lugar, uno quiere lo suficiente como axiomas para apoyar, con modus ponens, un teorema de completitud. Es decir, cada tautología debe ser demostrable a partir de los axiomas mediante modus ponens. (En general, cada semántica consecuencia de cualquier conjunto $S$ de las fórmulas debe ser deducible de $S$ y los axiomas mediante modus ponens.) Una forma de encontrar un sistema de axiomas es, para empezar no hay axiomas, de empezar a tratar de escribir una prueba de integridad, y poco a poco agregar axiomas como se ve que no son necesarios para la integridad de la prueba. Con extrema de la buena suerte, esto podría llevar a que los axiomas de la pregunta. Con menos suerte, que le llevará a un desordenado conjunto de axiomas, que podría, a continuación, intenta "limpiar" mediante la eliminación de cualquiera de los despidos, de la sustitución de complicado axiomas por simples axiomas que implica complicados, etc. Espero que esta es la forma en que los axiomas fueron encontradas por primera vez. Por supuesto, una vez que los hayas encontrado, la gente como yo no se vaya a través de la labor de redescubrimiento de ellos, sino simplemente de copiar de los libros de texto.

Answer 3

El conjunto de axiomas que elegimos para la lógica es tanto una elección estética, ya que es un matemático de la elección. Cosas que nos gustaría en la lógica de los axiomas son:

1. La auto-evidencia - una persona puede interpretar cada axioma ver por qué se debe ser verdadera?
2. La simplicidad relativa a la auto-evidencia, pero la simplicidad tiene sus propias recompensas
3. Independencia - tendemos a querer que nuestros axiomas de no ser demasiado redundante. Si Axioma C puede ser demostrado a partir de Un Axioma y el Axioma B, ¿por qué C un axioma?

Estas son decisiones estéticas.

A menudo tenemos una implícita técnico objetivo. Esencialmente, cuando estamos diseñando los axiomas, tenemos una idea de lo que los axiomas representan, y queremos "suficiente" de ellos para obtener todos los tipos de resultados que queremos.

Podemos comenzar con diferentes axioma conjuntos y obtener la misma lógica. La definición de cuando dos axioma sistemas son equivalentes puede ser un poco complejo, bucause un sistema puede tener un conjunto diferente de los símbolos que otro. (Por ejemplo, podemos hacer de la lógica sin $\to$$\land$, y obtener un equivalente lógico del sistema. A menudo, mantenemos los símbolos redundantes, porque los axiomas ser menos simple y menos evidente en sí mismo sin ellos.)

La mayoría de los incomprendidos elemento de la norma lógica proposicional es la $\to$ símbolo. A menudo es leer como "implica", pero que ha significado humano que una instrucción que sigue a partir del otro, de alguna manera directa. En particular, se tiende a pensar que "implica" como tener un cuantificador universal: "($x$ es incluso) $\to$ ($x+2$ es incluso)" hemos leído con un implícito "Para todos los $x\dots$" en el principio. Que no es realmente lo $\to$ significa, que es una razón por la que algunos axiomas de la lógica de no utilizar el $\to$ símbolo, o definir explícitamente $p\to q$ como una abreviación de $(\lnot p)\lor q$.

Así que usted puede ver que no sólo son los axiomas elegidos en base a la estética, sino el conjunto de símbolos que consideramos fundamentales son elegidos de la misma manera.

En la más absurda, se pueden obtener con sólo una operación lógica, y los axiomas en que la operación, para obtener todos los de la lógica proposicional. Por ejemplo, si definimos $p*q$ a significar "tanto en $p$ $q$ son falsas", a continuación, $p*p$ significaría "$p$ es falso". $(p*p)*(q*q)$ significaría " $p$ $q$ son ambas verdaderas." Por otro lado $(p*q)*(p*q)$ significa que "Al menos uno de $p$ $q$ es verdadero". Esto viola todas las de la estética - no hay nada acerca de $*$ que parece intuitivamente "fundamental", por ejemplo, y mientras $\land$ $\lor$ tienen algunas buenas intuitiva axiomas como la asociatividad, la traducción de aquellos a los axiomas de $*$ les hace bastante feo. Dicho esto, los matemáticos a menudo están interesados en tales reducciones debido a que el número de símbolos necesarios para entender un sistema es una medida de la complejidad del sistema.

Answer 4

Me gustaría ofrecer otro punto de vista. En la presencia de modus ponens, si tenemos un axioma de la forma $\phi_1\to(\ldots(\phi_n\to\psi)\ldots)$, se puede convertir en un admisible regla: $\phi_1, \ldots \phi_n \vdash \psi$. (Y en la presencia de la deducción del teorema podemos hacer a la inversa.) Vamos a ver lo que sucede cuando tratamos de convertir nuestros axiomas en tales reglas:

$\phi \to \phi$

Este axioma (aunque demostrable a partir de los próximos dos) se convierte en $$\phi\vdash\phi$$ Esto representa una propiedad fundamental de cualquier razonable, lógica de cálculo: toda proposición es demostrable a partir de sí mismo.

$\phi \to ( \psi \to \phi )$

Convierte a $$\phi, \psi \vdash \phi$$ De esta manera se expresa otro núcleo estructural de la regla de la mayoría de la lógica de los cálculos - la monoticity de vinculación, también llamado el debilitamiento del estado. Esto significa que libremente se puede agregar adicional hipótesis a una prueba.

$\left ( \phi \to ( \psi \rightarrow \xi )\right) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)$

Convierte a $$\phi\to(\psi \rightarrow \xi), \phi\to\psi, \phi \vdash \xi$$ De esta manera se expresa el concepto de la forma más general de la prueba de una implicación con dos premisas. Si conocemos $\phi$, una manera de probar la $\psi$$\phi$, luego de desempeñar tanto las premisas de $\phi\to(\psi \rightarrow \xi)$ a probar $\xi$.

Si nos especializamos este axioma $$\left ( \phi \to ( \psi \rightarrow \xi )\right) \to \left(\psi \to \left( \phi \to \xi \right) \right)$$ expresa el cambio estructural de la regla - siempre podemos intercambiar las premisas. (Podemos hacer esta especialización, ya que los anteriores axiomas nos dice que si tenemos $\psi$ siempre podemos probar a $\phi\to\psi$ a partir de ella, y, a continuación, utilizar el original axioma.)

Otra posible la especialización de este axioma es $$\left (( \psi \rightarrow \xi )\right) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)$$ (De nuevo, siempre podemos probar a $\left ( \phi \to ( \psi \rightarrow \xi )\right)$ $\psi \rightarrow \xi$ con el segundo axioma.) De esta manera se expresa la composición de las consecuencias.

Este tercer axioma se generaliza (en la presencia de la segunda) tanto la implicación de la composición y de cambio de las premisas.

$\left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right)$

Para ser honesto, yo no conozco a ningún buen interpretación de la regla. Se expresa completamente la relación entre el$\to$$\lnot$, en presencia de los otros axiomas (sin este axioma, se obtiene una intuitionistic lógica de implicación).