TEMA II 2da Parte
Recursividad
• 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 baila
Hume canta o Kant baila
Si Hume canta, Kant baila
Hume no canta
Kant no baila
Hume 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:
p
son (algunas) fórmulas atómicas
q
r
…
Fórmulas moleculares
• Las formaremos a partir de las atómicas,
empleando las conectivas lógicas:
pq
pr
son (algunas) fórmulas moleculares
qp
rq
-q
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 ; pr ; 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
t
u
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 …
---p
Todas 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 primer el segundo 
no es fórmula
Ejercicio: ¿cuáles son fórmulas?
NO
(-(p  -q)
(p  q)  -p  q NO
SÍ
((q  (r  -s))  (--p  q))  -r
-(s  (p  q-))
NO
SÍ
-(p  (-q  -(r (-s  t))))
NO
------+ ----------p
(-q  (r  (-p  q)))  (q  (-r  (p  -q)))
SÍ
Ejercicio: ¿cuáles son fórmulas?
((-q  r)  -(p  q))  -(q  r)  ((p  -q)  q) NO
NO
-(p  -q)  ¬r) -s)  t))))
SÍ
(((p  q  -r)  (-q  -p))  (p  -s))  (-p  q  r)
(p  (q  -p  r))  (p  q) NO
(((p  (q  -r))  (-q  s))  (s  -p))  (p  q) NO
SÍ
(p  q  -r)  (p  -q  -r)  (-p  q  r)
(p  q)  (-p  q)  (p  -q)  (-p  -q)
SÍ
Ejercicio: conectiva dominante
el primer -(p  -q)
(p  q)  (-p  q) 

((q  (r  -s))  (--p  q))  -r
-(s  (p  q))
el primer -(p  (-q  -(r (-s  t))))
el primer ------------------p
(-q  (r  (-p  q)))  (q  (-r  (p  -q)))
2º 
Ejercicio: conectiva dominante
(((-q  r)  -(p  q))  -(q  r))  ((p  -q)  q) 2º 
el primer -((((p  -q)  -r) -s)  t)
(((p  q  -r)  (-q  -p))  (p  -s))  (-p  q  r) 2º
(p  (q  (-p  r)))  (p  q) 
(((p  (q  -r))  (-q  s))  (s  -p))  (p  q) 3er 
(p  q  -r)  (p  -q  -r)  (-p  q  r) cualquier 
(p  q)  (-p  q)  (p  -q)  (-p  -q)
cualquier 
Descargar

Tema II segunda parte - Sección 7101-13