TEMA II 2da ParteRecursividad• La mayoría de los lenguajes son recursivos:
empleando un número finito de elementos es posible construir un número infinito de oraciones.
La mosca a la que persigue la araña a la que persigue el ratón al que persigue el gato al que persigue el perro es de color negro
Recursividad
• Una fuente de recursividad es la posibilidad de unir oraciones simples para formar compuestas.
• Las partículas lógicas desempeñan en esto un papel fundamental.
Recursividad• La recursividad comienza por tomar algunos
elementos básicos y definir cómo se construyen los elementos complejos a partir de ellos:
- Dadas las oraciones básicas ‘Hume canta’, ‘Kant baila’, también son oraciones las siguientes:
Hume canta y Kant bailaHume canta o Kant bailaSi Hume canta, Kant bailaHume no cantaKant no bailaHume canta si y sólo si Kant baila ETC.
Recursividad• Podemos seguir aplicando esto en general: dadas
las oraciones O y O’, son también oraciones las siguientes:O y O’, O o O’, Si O entonces O’, no O, etc.
• Podemos aplicar la regla cuantas veces queramos: dado que
• ‘Hume canta y Kant baila’ y ‘Hegel da palmas’ son oraciones, también lo será
• ‘Si Hume canta y Kant baila, Hegel da palmas’
Recursividad-Hume canta o Kant baila o Hegel da palmas-Hume canta y Kant baila y Hegel da palmas-Hume canta, Kant baila y Hegel da palmas-Hume canta o Kant baila, Hegel da palmas-Si Hume canta y Hegel da palmas, Kant baila-Hegel da palmas si y sólo si Kant baila-Si Hume canta y Kant baila, Hegel da palmas
Recursividad
• La recursividad permite construir algunas oraciones peculiares:-Hume canta y Kant baila y Hume canta y Kant baila y Hume canta y Kant baila…-Si Hegel da palmas, Hegel da palmas-Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta o Hume canta
Son peculiares desde el punto de vista pragmático, pero sintáctica y semánticamente están bien construidas
Recursividad• Nuestro lenguaje lógico también va a ser
recursivo.• Las oraciones en nuestro lenguaje se van a llamar
FÓRMULAS• Comenzaremos por definir cuáles son las
oraciones simples o fórmulas atómicas• A continuación daremos un método de
combinación de fórmulas atómicas para obtener oraciones compuestas o fórmulas moleculares
Fórmulas atómicas• Serán las que correspondan a las oraciones
simples del castellano: sin ninguna partícula lógica.
• Se trata por tanto de las constantes proposicionales:pqr…
son (algunas) fórmulas atómicas
Fórmulas moleculares
• Las formaremos a partir de las atómicas, empleando las conectivas lógicas:p qp rq pr q-q
son (algunas) fórmulas moleculares
Ambigüedad• En el lenguaje natural con frecuencia aparecen
posibles ambigüedades:Hume canta o Kant baila y Hegel dará palmas
¿Da o no da palmas Hegel?
Ahora sí: Hume canta o Kant baila, Hegel da palmas
Ahora no se sabe: Hume canta, o Kant baila y Hegel dará palmas
Ambigüedad• En lógica queremos construir fórmulas que
excluyan toda ambigüedad.• En el lenguaje natural usamos diversos
elementos para evitar la ambigüedad, como: 1) pausas prosódicas, 2) signos de puntuación y, 3) el contexto.
• Pero en lógica sólo tenemos un recurso (parecido a 2): construir las fórmulas con reglas muy precisas.
Ambigüedad- Nuestro principal recurso contra la ambigüedad son
los PARÉNTESIS.- Sea: p Hume canta ; q Kant baila;
r Hegel da palmas
p q r es AMBIGUA; equivale a:Hume canta o Kant baila y Hegel da palmas
p (q r) H canta, o K baila y He da palmas
(p q) r H canta o K baila, y He da palmas
Metavariables- Si la lógica es nuestro lenguaje objeto, el
castellano es su metalenguaje.- Pero necesitamos ampliar nuestro
metalenguaje con algunos símbolos que hacen las veces de abreviaturas.
- Para referirnos a fórmulas en general usaremos letras griegas:
…- Las llamaremos METAVARIABLES
Metavariables- Una constante, como p, representa aquello que la
hace verdadera o falsa (llueve; las rosas son rojas, etc)
- Una metavariable, como , representa cualquier fórmula:
p ; -q ; pr ; p (q r) ; p (p p)…
- Vamos a definir nuestras reglas de formación de fórmulas de manera más precisa
Reglas de formación
• (i) Toda constante proposicional sola es una fórmula (atómica)
• (ii) Si es fórmula, entonces - es fórmula• (iii) Si , son fórmulas, ( ), ( ), (
), ( ) son fórmulas• (iv) Sólo son fórmulas las secuencias que
satisfacen (i), (ii) o (iii)
Reglas de formación
(i) Toda constante proposicional sola es una fórmula
- De este modo obtenemos nuestras fórmulas atómicas:p q r s
tu p1 p2 p3 …
Reglas de formación
(ii) Si es fórmula, entonces - es fórmula- Dadas las anteriores, también son fórmulas:
-p -q -r -s -t-u -p1 -p2 -p3 …
-Podemos aplicar recursivamente (ii) sobre las fórmulas recién obtenidas: --p --q … ---pTodas estas también son fórmulas
Reglas de formación
(iii) Si , son fórmulas, ( ), ( ), ( ), ( ) son fórmulas
-Dadas (i) y (iii) serán fórmulas:(p q) (p s) (p r) … (q p ) …(p q) (p s) (p r) … (q p) …(p q) (p r) …(p q) (p r) …
Reglas de formación
(iii) Si , son fórmulas, ( ), ( ), ( ), ( ) son fórmulas
-Si además tenemos en cuenta (ii), son fórmulas:(p -q) (-p s) (p -r) … (q -p ) …(-p q) (p -s) (-p -r) … (-q p) …(p -q) (-p r) (-p -r) … (-p q) (p -r) (-p r) …
Reglas de formación
(iii) Si , son fórmulas, ( ), ( ), ( ), ( ) son fórmulas
-Y podemos aplicar otra vez (ii) sobre las últimas fórmulas :
-(p -q) -(-p s) -(p -r) … -(q -p ) …-(-p q) -(p -s) -(-p -r) …-(-q p) …-(p -q) -(-p r) -(-p -r) … -(-p q) -(p -r) -(-p r) …--(p q) … --(-p -q) … -(p --q) …
Reglas de formación
- Y podemos seguir aplicando (ii) y (iii) cuanto queramos:
(p (p q)) (-p (q -s)) (p -r) (q -p )(p ((-p q) (p -s))) ((-p -r) (-q p)) (p -q)…
Reglas de formación
(iv) Sólo son fórmulas las secuencias que satisfacen (i), (ii) o (iii)
- Esta es una cláusula de cierre, que limita nuestras fórmulas exclusivamente a las formadas por las reglas anteriores.
Reglas de simplificación
• Pueden suprimirse siempre:(a) Los dos paréntesis externos:
(p (q -r)) p (q -r)
(Nota: El símbolo se lee como ‘es equivalente a’)
Reglas de simplificación
• Pueden suprimirse siempre:(b) Los paréntesis internos no precedidos de negador
en secuencias compuestas totalmente por conyuntores o totalmente por disyuntores:
(p (q r)) (p q r) pero (p -(q r)) (p -q r) !!
(p (-q r)) (p -q r) pero (p -(q r)) (p -q r) !!
Conectiva dominante• Consideremos cómo se forman las fórmulas
moleculares:- La última regla de formación que hayamos usado
ha tenido que ser (ii) o (iii), i.e., la última regla ha introducido el negador o una conectiva binaria:
-p lo último introducido es el negador -q -r lo último introducido es el conyuntor p (q r) lo último introducido es el disyuntor -(p q) (-p -q) lo último introducido es
Conectiva dominante• La última conectiva introducida será la
CONECTIVA DOMINANTE de la fórmula.• Es importante distinguirla, porque es a la que
habrá que atender para determinar el valor de verdad de la fórmula.
p (r s)-(p (q r))-p (p (p p))-((p q) -(p q))(((p q) p) q) p-(p -(q r -(p q)))
-
el segundo el primer -
no es fórmula
Ejercicio: ¿cuáles son fórmulas?
(-(p -q)(p q) -p q((q (r -s)) (--p q)) -r-(s (p q-))-(p (-q -(r (-s t))))------+ ----------p(-q (r (-p q))) (q (-r (p -q)))
NO
NOSÍ
NOSÍ
NO
SÍ
Ejercicio: ¿cuáles son fórmulas?((-q r) -(p q)) -(q r) ((p -q) q)-(p -q) ¬r) -s) t))))(((p q -r) (-q -p)) (p -s)) (-p q r)(p (q -p r)) (p q)(((p (q -r)) (-q s)) (s -p)) (p q)(p q -r) (p -q -r) (-p q r)(p q) (-p q) (p -q) (-p -q)
NONO
SÍ
NONO
SÍ
SÍ
Ejercicio: conectiva dominante
-(p -q)(p q) (-p q)((q (r -s)) (--p q)) -r-(s (p q))-(p (-q -(r (-s t))))------------------p(-q (r (-p q))) (q (-r (p -q)))
el primer -
el primer -
el primer -
2º
Ejercicio: conectiva dominante(((-q r) -(p q)) -(q r)) ((p -q) q)-((((p -q) -r) -s) t)(((p q -r) (-q -p)) (p -s)) (-p q r)(p (q (-p r))) (p q)(((p (q -r)) (-q s)) (s -p)) (p q)(p q -r) (p -q -r) (-p q r)(p q) (-p q) (p -q) (-p -q)
2º el primer -
2º
3er cualquier
cualquier