Download parte 1 - Sitios de las cátedras Facultad de Ciencias Exactas y

Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
Lógica de Proposiciones
y de Predicado
Franco D. Menendez
LABIA
FACET - UNT
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
Contenido de la Materia
UNIDAD TEMÁTICA 2: DECISION EN EL LENGUAJE FORMAL
»Sistemas Axiomáticos. Noción General. Decisión Por Formas Normales. Forma
Normal Conjuntiva. Forma Normal Disyuntiva. Transformación de una EBF a
Forma Normal. Interpretación de FN. Decisión por Formas Normales.
Enunciados y Formas de Enunciados. El Razonamiento. Formas de
Razonamiento y Formas de Enunciados. Implicación y Derivación Lógica.
Implicación Lógica. Sistema de Derivación. Teorema de la Deducción. Decisión
por Cuadro Semántico. Literal. Consistencia y Modelos. Validez. Satisfacción.
Reglas Alfa y Beta. Construcción del Cuadro Semántico. Reglas de Formación de
Cuadro Semántico.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Noción general de sistemas axiomáticos
Un sistema axiomático, consiste en los siguientes objetos:
i.
Términos primitivos: constituidos por elementos, conjuntos o relaciones, cuya
naturaleza no queda especificada de antemano.
ii.
Axiomas: son funciones proposicionales cuantificadas, relativas a las variables (T.P.),
son propiedades a las que deben satisfacer dichos términos primitivos.
iii.
Definiciones: se definen todos los términos no primitivos.
iv.
Teoremas: propiedades que se deducen de los axiomas.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Ejemplos:
Un sistema axiomático:
i.
Términos primitivos: un conjunto A, y una relación R definida en A.
R= A x A
ii. Axiomas
A1: R es reflexiva en A.
A2: R es anti simétrica en A.
A3: R es transitiva en A.
R es una relación de orden Amplio en A.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Ejemplos:
Un sistema axiomático:
i.
Definición: en A, se considera la relación S.
(a,b)  S  (b,a)  R
ii.
Teoremas
S es reflexiva en A.
 a : a  A → (a,a)  R por A1
(a,a)  R → (a,a)  R por iii)
por ley del silogismo hipotético:
 a : a  A → (a,a)  S y en consecuencia , S es reflexiva en A.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Propiedades de los sistemas axiomáticos:
No toda elección arbitraria de términos primitivos y de propiedades relativas a
estos, caracteriza un determinado sistema axiomático. Es necesario que de los
axiomas no se derive ninguna contradicción. O si en el sistema aparecen dos
axiomas o teoremas contradictorios, entonces el sistema es incompatible o
inconsistente.
Otra propiedad es la independencia del sistema, en el sentido de que ningún
axioma puede probarse a expensas del resto de los axiomas presentes dentro del
sistema. La no independencia no niega la consistencia del sistema.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
»i) términos primitivos constituidos por proposiciones y por conectivos principales lógicos.
En algunos casos son denominados también como símbolos terminales cuando son simples
y no terminales cuando son compuestos.
»ii) axiomas y teoremas, que fundamentalmente son funciones proposicionales, relativas a
las variables que representan a los términos primitivos; es decir, son tautologías que deben
satisfacer dichos términos primitivos. Los axiomas son fbf tautológicas que no pueden ser
deducidos de otras fbf tautológicas, es decir son independientes. En cambio los teoremas
son fbf tautológicas que pueden ser deducidos o probados a través de la utilización de los
axiomas.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: Sistemas Axiomáticos
»iii) definiciones, expresiones, fórmulas lógicas que son derivadas de los teoremas o
axiomas y que a veces son considerados como términos no primitivos.
»iv) reglas, es decir, propiedades que deben cumplir las proposiciones o fórmulas lógicas.
De entre ellas tenemos:
Reglas de Formación. Son aquellas que dan lugar a la constitución
sintáctica del sistema axiomático cuando el mismo es considerado
como un lenguaje formal.
Reglas Transformación Son aquellas que permiten la transformación de fbf
tautológicas en otras fbf tautológicas y además existen las denominadas
Reglas de Inferencia, las que definen las operaciones sintácticas por la cual
pueden generarse nuevas fórmulas fbf.
»v) signos auxiliares o términos no primitivos constituidos por todos aquellos elementos no
primitivos, entre ellos podemos considerar los símbolos de puntuación lógicos.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
Sistemas GENTZEN
Definición: El sistema formal G consiste de axiomas y de reglas de inferencia. Un Axioma
es cualquier conjunto de formulas U que contienen un par complementario de literales: (p,
p)  U y las reglas de inferencia son de la siguiente forma:
U1  (1, 2)
U1  (1)
A partir de las premisas se infiere la conclusión, si tenemos pruebas independientes de dos
formulas podemos en consecuencia inferir su conjunción y si tenemos una prueba de un
conjunto de formulas podemos entonces inferir sus conjunciones
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
Definición: Una prueba en G es una secuencia de formulas tales que cada elemento es un
axioma o puede ser inferido a partir de uno o dos elementos previos de una secuencia
utilizando una regla de inferencia. Si A es el ultimo elemento de una secuencia, la secuencia
es denominada como una prueba de A y de este modo A es demostrable. (ͰA)
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
La comprobación es escrita como una secuencia de conjuntos de formulas las que
son numeradas para una referencia conveniente. A la derecha de cada conjunto
numerado de formulas colocamos la justificación con la cual cada conjunto puede
ser inferido. La justificación puede ser el axioma a aplicarse o una regla de
inferencia aplicada al conjunto o conjuntos de formulas en el paso anterior de la
secuencia.
Ejemplo : Ͱ(p q)  (q  p)
Demostración
1. p, q, p
2. q, q, p
3.  (p  q), q, p
4.  (p  q), q  p
5. (p q)  (q  p)
Axioma
Axioma
Regla- - ,(1), (2)
Regla- - ,(3)
Regla- - ,(4)
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
Sistema Axiomático de RUSSEL
A. Términos primitivos
1. «» Negación
2. «» Disyunción
3. p, q, s Proposiciones
B. Axiomas o Teoremas
A1: (p q)  p
A2: q  (p q)
A3: (p q)  (q p)
A4: (q  r)  [(p  q)  (p  r)]
C. Definiciones
1. p  q  df. ( p  q)
2. p  q  df ( p   q)
3. (p  q)  df. (p  q)  ( p   q)
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
D. Reglas
a) de Formación
1: las formulas p, q, r, s están bien formadas (fbf)
2: Si p es una fbf, entonces  p es una fbf.
3: Si una conectiva lógica esta flanqueada por una fbf, el conjunto constituye una
fbf.
b) De Transformación
1: Regla de Sustitución Uniforme: Si en una tautología sustituimos una variable
proposicional en todos los casos por una fbf, la formula resultante también es
tautológica.
2: Regla de Inferencia: Si en una implicación, que es teorema, el antecedente lo
es también, en consecuencia el consecuente es también un teorema.
E. Signos Auxiliares
1: Todos los signos de puntuación lógica
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
SISTEMA AXIOMÁTICO DE HILBERT
»A. Términos Primitivos
1:
""
Negación.
2:
" "
Disyunción
3:
" "
Conjunción
4:
""
Implicación
5:
p, q, s
Proposiciones
»B. Axiomas o Teoremas
A1 :
p  (q  p)
A2 :
[p  (q  r)]  [(p  q)  (p  r)]
A3 :
(p  q)  p
Simplificación
A4 :
(p  q)  q
Simplificación
A5 :
(p  (q  (p  q)))
A6 :
p  (p  q)
Adición
A7 :
q  (p  q)
Adición
A8 :
(p  r)  [(q  r)  ((p  q)  r)]
A9 :
[(p  q)  ((p   q)   p)]
A10:
pp
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
»11. Ͱ
»12. Ͱ
»13. Ͱ
»14. Ͱ
»15. Ͱ
»16. Ͱ
»17. Ͱ
»18. Ͱ
»19. Ͱ
»20. Ͱ
»21. Ͱ
»22. Ͱ
»23. Ͱ
»24. Ͱ
»25. Ͱ
»26. Ͱ
»27. Ͱ
»28. Ͱ
»29. Ͱ
»30. Ͱ
»31. Ͱ
»32. Ͱ
»33. Ͱ
pp
 p  (p  q)
(p  (q  r))  (q  (p  r))
(p  q)  ((q  r)  (p  r))
(q  r)  ((p  q)  (p  r))
(p  (q  r))  ((p  q)  r)
((p  q)  r)  (p  ( q  r))
(p  q)  ((p  r)  (p  (q  r)))
(p  q)  ((r  s)  ((p  r)  (q  s)))
(p  r)  ((q  r)  ((p  q)  r))
( p  q)  (p   q)
(p  q)  ( p   q)
( p  p)  p
(p  q)  ( p   q)
(p  q)  ( p   q)
pp
(p  q)  (q  p)
(p  q)  (q  p)
((p  q)  r)  (p (q  r))
p  (p  p)
p  (p  p)
(p  q)  ( q   p)
(p (q  r))  (p  q)  (p  r)
Tautología
De Morgan
De Morgan
Doble Negación
Conmutativa de 
Conmutativa de 
Asociativa de 
Idempotencia
Idempotencia
Transposición
Distributiva
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
»C. Definiciones
Def.:
p  q  ( p  q)  (p   q)
»D. Reglas
a). De Formación
1:Las fórmulas p, q, r, s están bien formadas (fbf).
2:Si p es una fbf, entonces  p es una fbf.
3:Si una conectiva lógica está flanqueada por una fbf, el conjunto
constituye una fbf.
b). De Transformación
1:Regla de Sustitución Uniforme. Si en una tautología (axioma o
teorema) sustituimos una variable proposicional en todos los casos
por una fbf, la fórmula resultante también es tautológica.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
2:Regla de Inferencia. Consideramos la regla del Modus Ponens
((p  q)  p)  q
pq
p

q
»E. Signos Auxiliares
1: Todos los símbolos de puntuación lógica
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
DECISION POR FORMAS NORMALES
»Las formas normales o canónicas, llamadas así acaso porque el pensamiento expresado
en ellas ofrece mayor claridad, son fórmulas o EBF construidas solamente con los
conectivos lógicos de conjunción y disyunción y bajo ciertas condiciones.
»Existen dos formas normales; la forma normal conjuntiva (que abreviamos de la siguiente
forma: f.n.c.) y la forma normal disyuntiva (que abreviamos f.n.d.).
»Forma Normal Conjuntiva
Una forma normal conjuntiva es una serie continua de conjunciones y donde los
factores de esas conjunciones son sólo disyunciones.
»Por ejemplo, consideremos lo siguiente expresión lógica que es una f.n.c.:
( p  q)  (p   q)  ( p   q)
»Forma Normal Disyuntiva
Una forma normal disyuntiva es una serie continua de disyunciones y donde los
factores de esas disyunciones son sólo conjunciones.
(p  q)  (p   q)  ( p  q)
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : DECISION EN EL LENGUAJE FORMAL
»1).La f.n.c. no es tautológica. Transformada en f.n.d., se observa que no es
contradictoria. Entonces es indefinida.
»2).La f.n.c. no es tautológica. Transformada en f.n.d. cada factor incluye una
variable proposicional y su negación. Entonces es una contradicción.
»3).La f.n.d. no es contradictoria. Transformada en f.n.c., se observa que no es
tautológica. Entonces es indefinida.
»4).La f.n.d. no es contradictoria. Transformada en f.n.c. cada factor incluye una
variable proposicional y su negación. Entonces es una tautología.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
BIBLIOGRAFIA
»ESTRUCTURAS DE MATEMÁTICAS DISCRETAS. Bernard Kolman. Robert Busby & Sharon Ross. –
2003.
»MATEMÁTICA DISCRETA Y LÓGICA. Roberto H. Fanjul – 2005.
»MATEMÁTICAS DISCRETAS - SEXTA EDICIÓN Richard Johnsonbaugh - PRENTICE HALL INC. –
2005.
»LÓGICA COMPUTACIONAL. Roberto H. Fanjul. Autor y Editor. Primera Edición – 2005.
»MATEMÁTICAS DISCRETA Y COMBINATORIA Ralph P. Grimaldi- Addison Wesley Longman – 2001.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
¡GRACIAS!
Preguntas?
» [email protected]