un sistema es decidible si hay un procedimiento mecánico ("un procedimiento de decisión") para determinar, para cada fbf del sistema, si esa fbf es un teorema, [conjunto de las verdades del sistema], o no. Ejemplos: el cálculo de oraciones es decidible; todo el cálculo de predicados (incluyendo los predicados poliádicos así como los monádicos) no lo es. Las tablas de verdad proporcionan el procedimiento de decisión para el cálculo de oraciones; una prueba de tablas de verdad determina si una fbf es una tautología, y, por los resultados de corrección y completud, todas y solamente las tautologías son teoremas.
(Haack, 1978).
Cuando una fórmula no puede ser probada verdadera ni falsa, se dice que la fórmula es independiente, y que por lo tanto el sistema es no decidible. La única manera de incorporar una fórmula independiente a las verdades del sistema es postulándola como axioma. Dos ejemplos muy importantes de fórmulas independientes son el axioma de elección en la teoría de conjuntos, y el quinto postulado de la geometría euclidiana.
Decidibilidad sintáctica
Un sistema formal es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
La lógica de primer orden es sintácticamente decidible si se limita a predicados con un solo argumento (monádica). Si se incluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa y recursivamente enumerable es decidible sintácticamente. Por otro lado, toda teoría que incluya aritmética básica no es decidible sintácticamente.
Decidibilidad semántica
Un sistema formal es decidible semánticamente si existe un método lógico y finito para evidenciar que el axioma, proposición, fórmula etc. es un teorema.
(Wikipedia)
Mostrando entradas con la etiqueta Cálculo de predicados. Mostrar todas las entradas
Mostrando entradas con la etiqueta Cálculo de predicados. Mostrar todas las entradas
CÁLCULO DE PREDICADOS: 🔎
(o lógica de primer orden, también llamada lógica predicativa, lógica de predicados, L₁), es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden.
Los lenguajes de primer orden son, a su vez, lenguajes formales con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo.
El cálculo de predicados tiene un poder expresivo muy superior al de la lógica proposicional.
(Wikipedia)
Los lenguajes de primer orden son, a su vez, lenguajes formales con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo.
El cálculo de predicados tiene un poder expresivo muy superior al de la lógica proposicional.
(Wikipedia)
CÁLCULO LÓGICO: 🔎
o derivación lógica, es un algoritmo o sistema lógico que permite inferir o deducir un enunciado verdadero a partir de otro u otros que se tienen como válidamente verdaderos.
La inferencia o deducción es una operación lógica que consiste en obtener un enunciado como conclusión a partir de otro u otros, llamados premisas, mediante la aplicación de reglas de inferencia.
Decimos que alguien infiere o deduce "T" de "R" si acepta que si "R" tiene valor de verdad V, entonces, necesariamente, "T" tiene valor de verdad V.
En lo cotidiano utilizamos el razonamiento deductivo; partimos de enunciados empíricos, supuestamente verdaderos y válidos, para concluir en otro enunciado que se deriva de aquellos.
La lógica matemática, como ciencia formal, se ocupa de analizar y sistematizar las reglas que permiten la transformación de unos enunciados (premisas) en otros (conclusiones) con objeto de convertir las operaciones deductivas en un cálculo riguroso y eficaz.
Al aplicar las reglas de este cálculo lógico a los enunciados que forman un argumento, previa la simbolización adecuada de los enunciados en fórmulas o Expresiones bien formadas (fbf) construimos un modelo dentro de un sistema deductivo que, referido al lenguaje ordinario, llamamos de Cálculo de deducción natural.
La representación gráfica de los símbolos (constantes lógicas) no está normalizada, lo que lleva a veces a ciertas dificultades de interpretación.
(Wikipedia)
La inferencia o deducción es una operación lógica que consiste en obtener un enunciado como conclusión a partir de otro u otros, llamados premisas, mediante la aplicación de reglas de inferencia.
Decimos que alguien infiere o deduce "T" de "R" si acepta que si "R" tiene valor de verdad V, entonces, necesariamente, "T" tiene valor de verdad V.
En lo cotidiano utilizamos el razonamiento deductivo; partimos de enunciados empíricos, supuestamente verdaderos y válidos, para concluir en otro enunciado que se deriva de aquellos.
La lógica matemática, como ciencia formal, se ocupa de analizar y sistematizar las reglas que permiten la transformación de unos enunciados (premisas) en otros (conclusiones) con objeto de convertir las operaciones deductivas en un cálculo riguroso y eficaz.
Al aplicar las reglas de este cálculo lógico a los enunciados que forman un argumento, previa la simbolización adecuada de los enunciados en fórmulas o Expresiones bien formadas (fbf) construimos un modelo dentro de un sistema deductivo que, referido al lenguaje ordinario, llamamos de Cálculo de deducción natural.
La representación gráfica de los símbolos (constantes lógicas) no está normalizada, lo que lleva a veces a ciertas dificultades de interpretación.
(Wikipedia)
ATÓMICO: 🔎
una fbf atómica del cálculo de oraciones es una letra de oraciones, (por ejemplo "p"), en contraste con una fbf compuesta o "molecular", (por ejemplo, "p ∨ q").
Una fbf atómica del cálculo de predicados es una letra de predicado n-posicional seguida de n variables o términos singulares.
Un enunciado atómico, analogamente, es un enunciado que no contiene otros enunciados como componente. (Haack, 1978).
Una fbf atómica del cálculo de predicados es una letra de predicado n-posicional seguida de n variables o términos singulares.
Un enunciado atómico, analogamente, es un enunciado que no contiene otros enunciados como componente. (Haack, 1978).
Suscribirse a:
Entradas (Atom)