LgicaResumen prctico

Diego Gonzlez2007diesgomo@gmail.com1. Induccin y recursin

1.1 Conjuntos inductivos Definicin de definicin de conjuntos inductivos primitivamente:Para definir un conjunto inductivamente se procede de la siguiente manera:i. Se indica qu elemento pertenece.ii. A partir de los elementos que pertenecen se indica qu otros elementos pertenecen.iii. El conjunto definido ser dado por el menor conjunto que cumpla con i. y ii. Reglas generales a tener en cuenta:i. Definimos un conjunto y una manera de construir elementos en lii. Decimos que esta es la nica forma de construir elementos del conjuntoiii. Decimos que las dadas son formas distintas de construir objetos en el conjunto Pertenencia a un conjunto definido inductivamente:Para demostrar que un elemento pertenece a un conjunto definido inductivamente, basta mostrar cmo se forma aplicando las reglas que definen al conjunto. Principio de induccin para un conjunto inductivo:Para probar que una propiedad se cumple para todos los objetos de A conjunto definido inductivamente basta con:i. Probar que la propiedad se cumple para los objetos de A obtenidos de aplicar las clusulas baseii. Probar que la propiedad se cumple para los objetos de A obtenidos de aplicar clusulas inductivas, suponiendo que la misma se cumple para el (los) objeto(s) anterior(s)

1.2 Esquemas no primitivos Esquema de recursin primitiva para un conjunto inductivo:Para definir una funcin f: A B, alcanza con definir f mediante ecuaciones que determinen:i. El valor de f para los objetos de A obtenidos de aplicar clusulas baseii. E valor de f para los objetos de A obtenidos de aplicar clusulas inductivas, utilizando el valor de f en el (los) objeto(s) anterior(es) y tambin el (los) objeto(s) anterior(es) Esquemas no primitivos:A definido inductivamente. Para definir f: A B debo:i. Definir f para los objetos base de Aii. Definir f en los objetos obtenidos de aplicar clusulas inductivas usando el valor de f objetos anteriores. Definiciones inductivas libres[footnoteRef:1]: [1: Las definiciones inductivas no libres son problemticas para definir funciones usando el esquema de recursin primitiva. Para verificar que se est definiendo una funcin habra que probar que la funcin devuelve un nico resultado para un valor asignado.]

Una definicin de un conjunto inductivo es libre cuando cada elemento del conjunto se construye de una nica manera.

1.3 Esquema de resumen de definiciones

2. Lgica proposicional

2.1 Sintaxis[footnoteRef:2] [2: Sintaxis: orden de las palabras, lgica de formacin de las palabras.]

Definicin de alfabeto de la lgica proposicional:

SmboloTipoNombreSignificado

piSmbolo proposicionalLetra proposicionalRepresenta un hecho verdadero o falso

Conectivoy (and)Conjuncin

Conectivoo (or)Disjuncin

ConectivoSi ... entonces (if ... then)Implicancia

ConectivoSii, si y solo si (iff)Equivalencia, doble implicancia

Conectivono (not)Negacin

ConectivoAbsurdo (falsity)Falsedad, absurdo

Definicin de subconjuntos de PROP:

Definicin de subconjuntos de PROP[footnoteRef:3]: [3: ]

PROP es el menor conjunto que cumple que:i.

ii.

iii.

Principio de induccin primitiva para PROP:Si A es una propiedad que cumple que:i.

ii.

iii.

Definicin de secuencia de formacin:

Esquema de recursin primitiva para PROP:

Ejemplo de funcin para PROP: TREE:

Notacin:Para eliminar (, ) de las frmulas definimos las siguientes precedencias de mayor a menor:i.

ii.

iii.

Definicin de subfrmula:

3. Semntica y propiedades de la lgica proposicional

3.1 Semntica[footnoteRef:4] [4: Semntica: sentido de un texto.]

Definicin de la funcin v de verdad (valuacin)[footnoteRef:5]: [5: ]

Tablas de verdad[footnoteRef:6]: [6: ]

Definimos el significado de cada conectivo segn las siguientes tablas conocidas como Tablas de verdad:01

011

101

01

000

101

01

001

111

01

010

101

|01

011

110

01

10

0

Unicidad de la valuacin:

Unicidad de la valuacin segn los tomos de una frmula:

Definicin de tautologa[footnoteRef:7]: [7: Otra forma de definir esto es:Formas de verificar tautologas:Una es hacer una tabla de verdad con todos los valores posibles de las valuaciones y verificar que para todas su resultado es 1.Otra es el mtodo Quine: Consiste en tomar un rbol con la frmula a verificar y tomar una valor para un tomo y reducir, luego dar los valores para el otro tomo y repetir el resultado. Si todas las hojas dan 1, se trata de una tautologa.]

Definicin de consecuencia lgica[footnoteRef:8]: [8: Otra forma de definir esto es:]

Definicin de sustitucin de una frmula por una variable[footnoteRef:9]: [9: ]

Teorema de sustitucin:

Propiedad:

3.2 Propiedades Propiedades de los conectores:

Algunas propiedades tiles:

Equivalencia:

Definicin de conjunto completo de conectivos:

Conjuntos completos de conectivos:

Definicin de formas normales[footnoteRef:10]: [10: Se define para ello:]

Teorema:

Definicin de *:

Propiedades de *[footnoteRef:11]: [11: ]

Definicin de d:

Teorema dual:

4. Sintctica y deduccin natural

4.1 Deduccin natural El conjunto DER[footnoteRef:12]: [12: ]

Definicin de inclusin e hiptesis de una derivacin:

Definicin de consecuencia sintctica:

Definicin de CONS:

4.2 Completitud y consistencia Teorema de completitud:

Definicin de consistencia:

Teorema de las equivalencias de inconsistencia[footnoteRef:13]: [13: Otra forma de plantearlo es:]

Teorema:

Teorema[footnoteRef:14]: [14: ]

4.3 Teoras y consistencia maximal Definicin de consistencia maximal[footnoteRef:15]: [15: Observacin: La segunda condicin podra haberse reemplazado por:]

Definicin de teora[footnoteRef:16]: [16: ]

Teorema:

Consistencia y consistencia maximal:

5. Sintaxis de la lgica de predicados

5.1 Alfabeto de primer orden Definicin de estructura[footnoteRef:17]: [17: Se considera relacin a un tipo de funcin que no devuelve un valor numrico.]

Definicin de tipo de similaridad[footnoteRef:18]: [18: Informalmente, ri, aj, son los parmetros de Ri, Fj respectivamente. En caso de no haber relaciones o funciones se notar con guin.]

Definicin de alfabeto de primer orden[footnoteRef:19]: [19: A continuacin se explicitan algunas convenciones e informalidades a usar de aqu en ms:]

Definicin de TERMA el conjunto de trminos:

Definicin de FORMA el conjunto de frmulas:

5.2 Induccin y recursin para TERMA y FORMA Principio de induccin primitiva para TERMA:

Principio de induccin primitiva para FORMA:

Esquema e recursin primitiva para TERMA:

Esquema de recursin primitiva para FORMA:

5.3 Variables Definicin de alcance de un cuantificador:

Definicin de ocurrencias libres y ligadas:

Definicin de variables libres y ligadas[footnoteRef:20]: [20: Una ocurrencia de una variable en una frmula es o bien libre o bien ligada, pero no ambas al mismo tiempo. A su vez, una variable puede ser libre y ligada en una misma frmula.]

Definicin de conjunto de variables libres de un trmino:

Definicin de conjunto de variables libres de una frmula:

Definicin de trminos y frmulas abiertas y cerradas[footnoteRef:21]: [21: A una frmula cerrada se le llama sentencia. Cerrada si no hay trminos sin cuantificar.]

Definicin de sustitucin de trminos en trminos[footnoteRef:22]: [22: Anlogo a la nota de pie 7.]

Definicin de sustitucin de trminos en frmulas[footnoteRef:23]: [23: Anlogo a la nota de pie 7.Esto tiene una restriccin porque la frmula puede llegar a perder el sentido tras la sustitucin, por lo que para realizar las sustituciones se pide que las variables de t sean libres en el lugar x para la frmula ]

Definicin de trmino libre para una variable:

Definicin de sustitucin simultnea[footnoteRef:24]: [24: ]

Definicin de frmula libre para $:

Definicin de sustitucin de frmulas en frmulas:

6. Semntica de la lgica de predicados

6.1 Interpretacin de frmulas[footnoteRef:25] [25: ]

Definicin de lenguaje extendido para una estructura:

Definicin de interpretacin de frmulas de SENT:

Definicin de interpretacin de trminos cerrados de L(M) en M:

Definicin de interpretacin de sentencias de L(M) en M[footnoteRef:26]: [26: Sobre las valuaciones:]

6.2 Tautologas Definicin de clausura universal de una frmula:

Definicin de tautologa[footnoteRef:27]: [27: Otra forma equivalente de definirlo es:M se dice que es modelo de lo que deriva]

i.

ii.

iii.

iv.

Propiedades de las tautologas:

6.3 Propiedades de los cuantificadores Definicin de equivalencia:

Generalizacin de las leyes de De Morgan:

Distributividad generalizada:

Orden de los cuantificadores:

Cambio de variables:

Teorema de sustitucin:

6.4 Formas normales prenexas y cuantificadores Definicin de forma normal prenexa[footnoteRef:28]: [28: ]

Existencia de la forma normal prenexa:

Definicin de cuantificadores relativizados:

7. Deduccin natural, identidad y completitud de la lgica de predicados

7.1 Deduccin natural El conjunto DER:

Definicin de consecuencia sintctica:

Propiedades de los cuantificadotes:

Teorema de correccin de DER:

7.2 Identidad

Reglas de derivacin de los axiomas:

Sobre las funciones y relaciones: Funciones:

Relaciones:

7.3 Completitud[footnoteRef:29] [29: ]

Definicin de teora de Henkin[footnoteRef:30]: [30: ]

Para T teora:

Teorema de derivabilidad:

Definicin de TW:TW se define recursivamente como:i. T0 = Tii.

iii.

Teorema:

Teorema de Lindenbaum:

Teorema:

Definicin de modelo:

Definicin de Th:

Teorema de completitud: