Teoria De La Computacion
Páginas: 2 (356 palabras)
Publicado: 10 de junio de 2012
APLICABILIDAD DE LA TEORIA DE LA COMPUTACION AL TEOREMA DE HERBRAND
Se reconoce como definición de la teoría de la computación que esta es una rama de la matemática y la computación que centra suinterés en las limitaciones y capacidades fundamentales de las computadoras específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un computo y la clasificación deproblemas, de acuerdo a ello tenemos que mediante la teoría de autómatas se podría proveer modelos matemáticos que formalicen el concepto de computadora ó algoritmo de una manera simplificada ygeneral para poder analizar sus capacidades y limitaciones, el modelo del teorema de HERBRAND es el resultado de más importante de la historia de la deducción automática en lógica clásica estableciendo unpuente entre el cálculo proposicional puesto que puede comprobar la validez en una fórmula cuantificada haciéndolo sucesivamente en distintas instancias proposicionales este mismo indica que sea Sun conjunto de clausulas. Son equivalentes:
1. S es consistente.
2. EH(S) es consistente (en el sentido proposicional).
Proposición: Sea S un conjunto de cláusulas, entonces sonequivalentes si:
1. S es consistente.
2. EH(S) tiene un subconjunto finito inconsistente (en el sentido proposicional).
3. Para algún i, EHi(S), es consistente (en el sentido proposicional).Lo anterior indica que la semidecision mediante el teorema de Herbrand es la siguiente , se tiene presente una ENTRADA que indica un conjunto finito de clausulas S, el procedimiento es elsiguiente:
➢ Se debe hacer i=0
➢ Se calcula EHi(S)
➢ Si EHi(S) es inconsistente en el sentido proposicional, se debe parar el procedimiento e indicar que S es inconsistente
➢ SiEHi(S) es consistente en el sentido proposicional, se debe hacer i = i + 1 y se debe retornar al paso 2 del presente procedimiento
se tiene adicionalmente una SALIDA inconsistente, si S es...
Se reconoce como definición de la teoría de la computación que esta es una rama de la matemática y la computación que centra suinterés en las limitaciones y capacidades fundamentales de las computadoras específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un computo y la clasificación deproblemas, de acuerdo a ello tenemos que mediante la teoría de autómatas se podría proveer modelos matemáticos que formalicen el concepto de computadora ó algoritmo de una manera simplificada ygeneral para poder analizar sus capacidades y limitaciones, el modelo del teorema de HERBRAND es el resultado de más importante de la historia de la deducción automática en lógica clásica estableciendo unpuente entre el cálculo proposicional puesto que puede comprobar la validez en una fórmula cuantificada haciéndolo sucesivamente en distintas instancias proposicionales este mismo indica que sea Sun conjunto de clausulas. Son equivalentes:
1. S es consistente.
2. EH(S) es consistente (en el sentido proposicional).
Proposición: Sea S un conjunto de cláusulas, entonces sonequivalentes si:
1. S es consistente.
2. EH(S) tiene un subconjunto finito inconsistente (en el sentido proposicional).
3. Para algún i, EHi(S), es consistente (en el sentido proposicional).Lo anterior indica que la semidecision mediante el teorema de Herbrand es la siguiente , se tiene presente una ENTRADA que indica un conjunto finito de clausulas S, el procedimiento es elsiguiente:
➢ Se debe hacer i=0
➢ Se calcula EHi(S)
➢ Si EHi(S) es inconsistente en el sentido proposicional, se debe parar el procedimiento e indicar que S es inconsistente
➢ SiEHi(S) es consistente en el sentido proposicional, se debe hacer i = i + 1 y se debe retornar al paso 2 del presente procedimiento
se tiene adicionalmente una SALIDA inconsistente, si S es...
Leer documento completo
Regístrate para leer el documento completo.