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