Preguntas relacionadas con la lógica matemática y su uso en informática.
He oído hablar de inducción (estructural). Le permite construir estructuras finitas a partir de otras más pequeñas y le ofrece principios de prueba para razonar sobre tales estructuras. La idea es lo suficientemente clara. ¿Pero qué pasa con la coinducción? ¿Como funciona? ¿Cómo se puede decir...
En la página de Wikipedia para Fixed Point Combinators está escrito el texto bastante misterioso. El combinador Y es un ejemplo de lo que hace que el cálculo Lambda sea inconsistente. Por lo tanto, debe considerarse con sospecha. Sin embargo, es seguro considerar el combinador Y cuando se define...
Estoy aprendiendo la prueba de teorema automatizado / solucionadores SMT / asistentes de prueba por mi cuenta y publico una serie de preguntas sobre el proceso, comenzando aquí. Tenga en cuenta que estos temas no se digieren fácilmente sin un fondo en lógicas (matemáticas). Si tiene problemas con...
Podría haber una disculpa por hacer otra pregunta sobre los requisitos previos, pero estaba confundido acerca de los puntos de partida. Me he encontrado con varios términos como "Lógica modal", "Lógica temporal", "Lógica de primer orden", "Lógica de segundo orden" y "Lógica de orden...
Muchos libros de texto cubren los tipos de intersección en el cálculo lambda. Las reglas de tipeo para la intersección se pueden definir de la siguiente manera (además del cálculo lambda simplemente tipado con
El combinador de punto fijo FIX (también conocido como el combinador Y) en el cálculo lambda ( tipo) ( ) se define como:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y....
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
Tengo un conjunto de pares. Cada par tiene la forma (x, y) de modo que x, y pertenecen a enteros del rango [0,n). Entonces, si n es 4, entonces tengo los siguientes pares: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Ya tengo las parejas. Ahora, tengo que construir una combinación usando n/2pares de...
La mayoría de nosotros conocemos la correspondencia entre la lógica combinatoria y el cálculo lambda . Pero nunca he visto (tal vez no he mirado lo suficientemente profundo) el equivalente de "combinadores mecanografiados", correspondiente al cálculo lambda simplemente mecanografiado. ¿Existe tal...
La lógica constructivista es un sistema que elimina la Ley del Medio Excluido, así como la Doble Negación, como axiomas. Se describe en Wikipedia aquí y aquí . En particular, el sistema no permite pruebas por contradicción. Me pregunto, ¿alguien está familiarizado con cómo esto afecta los...
Me parece que 'implica' en el idioma inglés no significa lo mismo que el operador lógico 'implica', de manera similar a cómo la palabra 'OR' en la mayoría de los casos significa 'OR exclusivo' en nuestro uso cotidiano del idioma. Tomemos dos ejemplos: Si hoy es lunes, mañana es martes. Esto...
Estoy buscando un cálculo simple que admita el razonamiento sobre la reflexión , a saber, la introspección y la manipulación de programas en ejecución. ¿Existe una extensión de cálculo tipo que permita convertir los términos λ en una forma que pueda ser manipulada sintácticamente y luego...
Me gustaría saber si hay una regla para probar esto. Por ejemplo, si uso la ley distributiva solo obtendré .( A ∨ A ) ∧ ( A ∨ ¬ B )(A∨A)∧(A∨¬B)(A \lor A) \land (A \lor \neg
Que yo sepa, hay tres álgebras de procesos principales que han inspirado una amplia gama de investigaciones sobre modelos formales de concurrencia. Estos son: CCS y cálculo ambos por Robin Milnerππ\pi CSP por Tony Hoare y ACP por Jan Bergstra y Jan Willem Klop Los tres parecen tener hasta el...
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . En el script que estoy leyendo actualmente sobre el cálculo lambda, la equivalencia beta se define así: La...
¿Cómo podría expresar una puerta AND usando solo puertas
Considere un tipo inductivo que tiene algunas ocurrencias recursivas en una ubicación anidada, pero estrictamente positiva. Por ejemplo, árboles con ramificación finita con nodos que utilizan una estructura de datos de lista genérica para almacenar los elementos secundarios. Inductive LTree : Set...
Estoy aprendiendo la prueba de teorema automatizado / solucionadores SMT / asistentes de prueba por mi cuenta y publico una serie de preguntas sobre el proceso, comenzando aquí . ¿Cuáles son los probadores de teoremas automatizados relevantes? Encontré una revisión de los probadores de...
La Ley de De Morgan a menudo se introduce en un curso introductorio de matemáticas para ciencias de la computación, y a menudo lo veo como una forma de convertir las declaraciones de AND a OR negando los términos. ¿Existe una explicación más intuitiva de por qué esto funciona en lugar de solo...
Recientemente estuve pensando en la validez de la prueba por contradicción. He leído en los últimos días cosas sobre lógica intuicionista y teoremas de Godel para ver si me darían respuestas a mis preguntas. En este momento todavía tengo preguntas pendientes (tal vez relacionadas con el nuevo...