Materia: Lgica

Ctedra: Barrio

Terico: N 7 11 de abril de 2012

Profesor: Eduardo Barrio.

Tema: Procedimientos algortmicos. -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-

Profesor: Bueno, recuerden que maana a la noche va a agregarse en el sitio nuevas

recomendaciones y nuevas preguntas. Todava ninguno me hizo la pregunta que me formularon en

privado, pero para que no me juzguen como alguien completamente irracional me dedico a hacer

una aclaracin. Alguien pudo haber preguntado por qu el profesor cuando agrega actividades y

preguntas los jueves roba las preguntas y actividades anteriores? Tiene algn sentido esa accin o

es una accin perversa que busca que la gente no tenga suficiente informacin? Aunque no me

hicieron la pregunta puedo dar algunas referencias. La verdad es que las preguntas que fueron

sufriendo no tienen ningn sentido de ser abordadas y respondidas tarde. La pregunta de la primera

semana eran preguntas relativas a la segunda semana. Y as siempre, slo la ltima pregunta es la

que va a tener sentido. El resto de cosas son preguntas que se les hicieron en el momento indicado

para que puedan chequear de qu va el asunto. Abordar esas mismas preguntas todas al final es

ridculo, no tiene nada que ver con el sentido cognitivo de la materia y no tienen ningn sentido

acumularlas al final. Las respuestas a las preguntas de la primera semana, esas mismas preguntas

dichas hoy estaran mal. La materia tiene esta estructura. El tipo de estrategia que estoy jugando

tiene que ver con el tipo de estrategia que es abordar los problemas en el momento en que los

problemas son problemas. Con los elementos que tenemos en ese momento. Puede haber otras

materias donde uno puede estudiar la semana final. El problema aqu es que la pregunta que se les

va a hacer es una pregunta que no apareci en ninguna de las semanas anteriores y que slo tiene

sentido en ese momento. Seguramente si el curso siguiera dos o tres semanas ms, el tipo de

preguntas que les dejara serian otras. Todo es acumulativo. Entonces haber dado una buena

respuesta en la semana dos pone a las personas en una buena situacin para dar una respuesta en la

semana tres, aunque por supuesto no es condicin suficiente. Las preguntas dejan de tener sentido la

semana siguiente, cuando las preguntas dejan de tener vigencia se pierden. De hecho el lenguaje

que habamos utilizado se pierde y vamos a adoptar algo mas sofisticado hoy. Si uno sigue paso por

paso lo que esta pasando en el curso lo que va a pasar en el examen es algo extrao, la sensacin

1

AdministradorText Box02-010-011 - 13 T

que van a tener es no se que mas tengo que hacer, no se que mas tengo que leer para el examen y

mi respuesta es nada. El parcial es a libro abierto. El que estudio, va mira la consigna,

seguramente va a ver un subconjunto de gente que no entiende ni siquiera lo que se les pregunta, el

lenguaje de la pregunta, entonces mira la pregunta, responde, tiene todo a su alcance si necesita

auxiliarse, y se va, eso es todo lo que va a pasar. No hay secretos.

Bien tienen alguna duda? Recuerden que estn las clases de consulta, es optativo pero es una

instancia para resolver alguna cuestin que no puedan solos. Hay alguna duda antes de empezar la

clase?

Estudiante: [Inaudible]

Profesor: Estos dos signos son lo mismo y ? No. Pero tienen alguna semejanza?

Comencemos con las semejanzas, no es completamente disparatado pensar que hay semejanzas

entre estas dos cosas. Entonces cuales son las semejanzas?

Estudiante: [Inaudible]

Profesor: Hay algo ms bsico. Las dos son implicaciones. Se trata de implicar, entonces son dos

relaciones de implicacin. Una lgica, la otra no. Ah comienzan a diferenciar.

[Interrupcin]

Profesor: aqu tengo un conjunto y una relacin metalingstica entre un conjunto y una frmula.

Noten que este conjunto podra tener un nico elemento. Aun as sigue siendo un conjunto, entonces

la relacin de consecuencia lgica es una relacin entre un conjunto de frmulas, vaco, de un

elemento, y frmula, y eso que est all abajo no es una relacin del metalenguaje. Por supuesto

puedo usar cosas como esto en el metalenguaje tambin. Que quiero decir en un acto de habla

como la afirmacin que est abajo? Que pase algo es suficiente para que pase tal cosa, o siempre

que pasa algo pasa tal otra. Por supuesto la intencin es decir algo como lo que acabo de decir. Es

condicin para que apruebe el examen, estudiar, ah no hay una relacin de inferencia lgica de

ningn tipo. Estoy diciendo que hay una condicin suficiente para aprobar el examen cual?

Estudiar. No que se siga lgicamente aprobar el examen.

Estudiante: [Inaudible]

2

Profesor: Eso es equivalente a no existe una valuacin tal que la valuacin de sea igual a uno y la

valuacin de A sea igual a cero. Ese signo se interpreta de esa manera. No existe una valuacin tal

que la valuacin de sea uno y la valuacin de A sea cero. No hay una funcin particular si se da

esta relacin de consecuencia lgica, esto quiere decir esto. Noten que esta afirmacin en cada caso

en particular est describiendo alguna cosa especial. Por ejemplo podra ser pq, p. Y A podra

ser q. que dice ahora en trminos lgicos? dice que no existe una valuacin uno a estas frmulas y

cero a esta otra. Eso dice esta afirmacin. Cuando uno arma un condicional, supongamos que un

alumno nuevamente con una honestidad brutal diga esto: Yo no se porqu pone tantos smbolos.

Por qu no hace eso directamente? Entonces, razones para no poder hacer eso.

Estudiante: [Inaudible]

Profesor: Esto representa una funcin del lenguaje natural que es veritativo funcional, la relacin

de consecuencia lgica no es un conectivo veritativo funcional. Pensemos cuando un condicional es

verdadero. Podra ser cuando el antecedente es falso, podra ser cuando el consecuente es

verdadero, ahora que un condicional sea verdadero quiere decir que hay una relacin de

consecuencia lgica entre el antecedente y el consecuente? Por ejemplo, yo digo esto: si tomo el

examen ahora, entonces la mayora de los alumnos desaprueba. Les parece verdadero eso? bueno

no se, supongamos que si. Eso es una afirmacin verdadera eso quiere decir que se sigue

lgicamente que ustedes desaprueben de que yo tome un examen ahora? No, no hay un vnculo

lgico entre ambas cosas. La relacin que uno est buscando es un vinculo ms estrecho que el

vinculo que hemos llamado implicacin material, si pasa esto entonces pasa lo otro.

Entonces hagamos lo siguiente para insistir en la diferencia entre ambos signos. Supongan que un

alumno dice No veo la diferencia, la verdad no la veo. Bueno, entonces, supongan que el alumno

presenta un caso particular para intentar mostrar que no hay diferencia. Primer caso particular: el

que yo dije antes. Supongamos que realmente quiero convencer de que hay una relacin de

consecuencia lgica en el enunciado condicional que acabo de decir recin. Entonces si tomo

examen ahora, entonces todos los alumnos desaprueban. Como quedara esto? pq. estas dos

cosas en realidad seria la misma cosa. Pero una objecin sera que por la definicin de frmula bien

formada no permite poner en el antecedente conjuntos de frmulas. El alumno dice lo siguiente: en

el caso de que haya una nica formula pone una frmula, en el caso que haya mas de una formula

ponga en conjuncin. Eso propone el alumno para reemplazar todas las apariciones de consecuencia

lgica en trminos de un condicional. Primera cuestin es este razonamiento vlido o transmisor

de verdad o un caso de esto? la respuesta es no, sin embargo yo dije algo verdadero en el lenguaje

3

natural. Si tomo el examen ahora, todos desaprueban. Es verdadero, sin embargo no es lgicamente

verdadero. Es verdadero por razones empricas. Pero no es verdadero por razones lgicas. Entonces

la relacin de implicacin que se da entre premisas y conclusin es una relacin ms fuerte que la

afirmacin de implicacin material.

Busquemos ahora una relacin de implicacin que sea lo suficientemente fuerte como para

representar en el lenguaje la relacin de implicacin lgica, no la relacin de implicacin material.

Para distinguirla voy a reemplazar este signo, por este otro signo. Este es un indicador pero no es

un si...entonces del lenguaje natural, sino que implica lgicamente. Ahora digo que esto implica

lgicamente esto. Supongamos ahora lo siguiente. Esto es uno y esto es uno. Si este signo

representara la relacin de implicacin lgica, cual puede ser el valor de verdad de q? No hay otro

valor posible.

Bien, supongan ahora que esto es cero. Como tendra que ser el valor de verdad de la conclusin?

Puede dar cero o puede dar uno. Estas son tres valuaciones para este conectivo que no es el

conectivo de implicacin material. Implica lgicamente. Se acuerdan que al principio del captulo

los GAMUT dijeron que hay conectivos veritativo funcionales. Veamos la relacin lgica como un

implicador. Supongamos que fuese este cual es el caso prohibido para representar el caso de

implicacin lgica? El caso prohibido, por lo que vimos recin, sera uno en el cual todas las

premisas son verdaderas y esto es cero. Entonces si este fuese el condicional material como

debera ser la tabla de verdad de este condicional? El condicional es material y tiene que producirse

que sea verdadero el antecedente y falso el consecuente como debera ser este condicional material

para representar el vnculo lgico entre premisas y conclusin? Que deberamos prohibir?

deberamos prohibir que el condicional material fuese falso, debemos tener un condicional material

siepre verdadero. Como es un condicional material siempre verdadero? tautolgico. Entonces para

representar la relacin de consecuencia lgica con un condicional material hay que agregar algo que

se puede decirse en el metalenguaje, se tiene que decir que la tabla de verdad del condicional

material es una tautologa, pero no todo condicional material es tautolgico. Entonces para expresar

la implicacin lgica dentro del lenguaje, yo debera poder decir dentro del lenguaje, cosa que no

puedo hacer, que este condicional material es una tautologa y eso no lo puedo hacer, es obvio.

Tablas de verdad, funciones de valuacin no son expresables adentro del lenguaje. En que se

relacionan estos dos signos? Los dos representan ideas del lenguaje natural vinculados a la

implicacin, pero uno es un implicador lgico, el otro no. La relacin de implicacin material es

una relacin muy dbil.

Si digo Siempre que voy al cine me divierto que entienden de eso? Estoy diciendo que hay una

inferencia lgica de una cosa respecto de la otra? no hay una definicin de un estado, es muy poco

fuerte el vinculo entre una cosa y otra. Lo que estoy diciendo es que la relacin de implicacin

4

material que yo eventualmente podra construir en mi lenguaje poniendo en conjuncin a las

premisas y poniendo como consecuente la inferencia es una tautologa. Esta es la idea que

representa la idea de implicacin lgica porque? Porque la idea es una implicacin en donde

siempre el antecedente resulta verdadero, el consecuente tambin es verdadero. Y el condicional

material simplemente no expresa esa idea. La relacin de implicacin material es ms dbil que la

relacin de implicacin lgica. Pero no toda implicacin material es una implicacin lgica. Para

que una implicacin material pueda ser una implicacin lgica se tienen que dar cosas muy fuertes,

se tiene que dar que el condicional material resulte ser tautolgico, o sea, siempre verdadero. Por

qu es as? Porque si resulta ser siempre verdadero quiere decir que no hay una interpretacin

posible en donde siendo verdaderas todas las premisas, o sea, el antecedente resulte falsa la

conclusin. A veces en algunos prcticos se dice algo as como que existe un mtodo para probar

validez formal que se llama mtodo del condicional asociado. El mtodo del condicional asociado

consiste en formalizar un argumento del lenguaje natural, una vez que uno lo formaliza puede

obtener algo como esto. Una vez que alguien formaliza algo como esto construye un lenguaje LP

asociado al lenguaje del metalenguaje. Ponga en conjuncin todas las premisas y ponga la

conclusin como consecuente del condicional, ese enunciado es el condicional asociado. El mtodo

consiste en construye una tabla de verdad, si la tabla de verdad resulta ser una tautologa entonces

usted puede concluir que este razonamiento es vlido. Es uno de los tantos mtodos que ustedes

pueden utilizar en los prcticos para resolver ejercicios.

Resumiendo: la relacin de implicacin lgica no es la relacin de implicacin material. La relacin

de relacin lgica es una implicacin, pero mucho mas fuerte que la relacin de implicacin

material. No toda relacin de implicacin material es una relacin de implicacin lgica. En

particular para que una relacin de implicacin material sea una implicacin lgica hay que agregar

que la tabla de verdad del razonamiento deba ser tautolgica, su tabla de verdad debe ser tal que no

haya ninguna relacin posible que de falso.

Estudiante: [Inaudible]

Profesor: se puede utilizar esto como mtodo de prueba formal de validez, yo no lo utilizo. De

hecho en el libro vern que esto as no esta explicado. No se construye un condicional asociado para

probar razonamientos.

Hay un argumento ms que se podra dar para mostrar que las dos relaciones no son la misma

relacin. El argumento se vincula bsicamente con lo que dijimos la clase pasada. A quien se le

ocurre? Supongamos que se pudiera, o sea, que la relacin de implicacin lgica se pudiera

representar en el lenguaje. Que se sigue de esto? en particular la relacin de implicacin lgica en

5

trminos de que estara definida? Semntica, en trminos de valuacin. En particular lo que uno

tiene que decir en el lenguaje es no existe la valuacin en donde las premisas son verdaderas y la

conclusin es falsa. Pero se pueden decir esas cosas adentro de LP? No, si tuviera que decir eso el

concepto de verdad sera expresable dentro de LP. Y eso no se puede hacer. Entonces la reunin

pasada vimos algn argumento adicional de la movida de considerar esto como un signo del

metalenguaje. Una analoga que tambin podramos utilizar para entender esto es la siguiente, si les

gustan los juegos. Una cosa son las fichas y las movidas de las fichas. El condicional es una ficha

del tablero, es una manera de mover. La relacin de implicacin lgica es el objetivo del juego. Hay

que mover las fichas de manera tal de obtener casos de implicacin lgica. Hay infinitas formas de

lograr esto, todas son relaciones de implicacin. Hay que distinguir de todas las movidas solo

aquellas que son relaciones de implicacin lgica. Hay que distinguir el gol o jaque mate de mover

una ficha o el jugador a los efectos de obtener el resultado deseado. Alguna pregunta ms?

Bueno, l [seala a un estudiante] me pregunt algunas cosas relacionadas a la diagonalizacin en el

horario de consulta. En algn momento yo voy a hacer algunas cosas vinculadas a pruebas

diagonales que son sorprendentes. Una cosa que yo le coment a l es que en algn prctico a veces,

para motivarlos, hacen alguna prueba diagonal al principio. No hay manera de entender El Aleph

de Borges sin saber lo que es una prueba diagonal. Eso requiere el cuento. Hay otra pregunta?

Este es el conjunto de todas las cosas que tienen la propiedad de ser tautolgicas.

A B C D

En particular son formas correctamente construidas en LP, no hay nada mal formado adentro de este

conjunto. No hay nada que resulte verdadero, tampoco que resulte falso, que sea un garabato

adentro de este conjunto. Es un conjunto de formulas bien formadas. Por supuesto, no cualquier

formula bien formada est adentro de este conjunto. Hay que decir que para estar adentro de este

conjunto la formula tiene que estar bien formada y ser una tautologa. Entonces lo primero que me

pregunto es cuantas formulas bien formadas hay?

Estudiante: Infinitas.

6

Profesor: Es cierto, pero es poco explicativo respecto de lo que estuvimos viendo respecto de este

nmero. Alguien puede decir algo ms explicativo que decir hay infinitas frmulas bien

formadas? Cual es el nmero de formulas bien formadas? Esta bien que me contesten que es

infinito pero no es slo infinito. Quiero que me contesten algo ms. No es cualquier conjunto como

es este conjunto?

Estudiante: Es recursivo.

Profesor: Es recursivo. Cuantas veces vieron la definicin de frmula bien formada? Hay que

incorporar la definicin para responder este tipo de preguntas. Bien ac tengo una sola pregunta: el

nmero de formulas de LP que caractersticas tiene? Es infinito, pero hay una definicin

constructiva de este nmero infinito. Yo puedo construir constructivamente cualquier frmula bien

formada. Hicimos ese esfuerzo para tener frutos, si no no lo hubisemos hecho. Podra haber algn

argumento en el lenguaje natural que le de plausibilidad a la definicin de la gramtica debera ser

recursiva? Que pasara si las formulas de mi lenguaje no pedirn ser generadas a travs de un

mecanismo recursivo? Para entender el lenguaje tendra que conocer la infinitud de oraciones. Slo

Funes hacia eso, nosotros no somos as, nosotros no tenemos infinita memoria. La idea que tenemos

del lenguaje est calcada de la idea de que hay un mecanismo recursivo de esta infinitud. Estamos

construyendo un modelo formal de algo que nosotros hacemos. Ese modelo es mucho mas pobre

que eso que nosotros hacemos. Entonces si ahora LP tuviera una estructura no recursiva sera

mucho mas rico que el lenguaje natural, porque no estara modelizando esa practica sobre la cual

hemos trabajado las primeras clases. Si es mas pobre debemos respetar al menos. Hay infinitas

formulas pero recursivamente generadas. La gramtica de LP es recursiva, llega a la infinitud a

partir de una estructura recursiva de generacin de compuestos a partir de lo simple. Si esto est

bien formado entonces esto tambin. Las clusulas son de este tipo. Entonces ahora la pregunta que

yo me hago es esta. Sea A una formula bien formada del lenguaje LP cualquiera, ni siquiera se cual,

yo lo que se es que para poder estar ac tiene que ser posible generar a partir de una construccin

recursiva de a partir de cosas simples. Eso lo se por definicin de formula bien formada. Entonces

ahora pregunto ser una verdad lgica? Dado que es una formula de LP, ser una tautologa?

Que me pueden decir de esta pregunta en este momento? Que tendran que saber para que ustedes

me puedan dar una respuesta? Cuales son las condiciones de respuesta? Si o no, la respuesta es o

afirmativa o negativa, noten que no toda pregunta tiene esas condiciones de respuesta. Hay muchas

preguntas que no se responden por si o por no, esta si. La pregunta es una pregunta acerca de la

complejidad de la tarea a realizar para darle una respuesta por si o por no a la pregunta que acabo de

7

hacer. Cuan complejo puede ser el clculo que ustedes o yo deberamos desempear para dar una

respuesta a esta pregunta?

Estudiante: [Inaudible]

Profesor: La pregunta es otra. Mi pregunta es general, es para cualquier . Entonces, alguien podra

hacer esto, que pasa si es p? es una formula bien formada, pero no es una tautologa. Entonces

cuanto me toma el clculo? Un paso, un clculo slo. Bien, si tenemos dos? Dos pasos. Que pasa

si tengo algo que me da contradiccin? Las contradicciones no van a estar adentro de este conjunto,

en toma dos pasos. Que pasa con esto pp? va a estar adentro de este conjunto? Siempre el valor

es uno, entonces pp est adentro de este conjunto.

Estudiante: [Inaudible]

Profesor: Terminaramos un da de ver este conjunto? No, no terminaramos nunca. Es tan general,

abarca tantos problemas que no se puede responder por si o por no.

Estudiante: [Inaudible]

Profesor: No tengo solamente una lista desordenada, tengo una lista estructurada a partir de una

definicin recursiva de frmula. Puedo generar una nueva formula? S, claro , agregue un nuevo

conectivo ms. Podra en algn punto de la secuencia tener un nmero infinito de conectivos para

una secuencia? No, ahora el nmero de tautologas como el nmero de formulas bien formadas es

infinito. Pero, ninguna formula bien formada tiene infinitos conectivos. Por lo tanto la

descomposicin de formula bien formada cuan larga puede ser? Largusima, pero finita.

Para determinar la validez de una formula, cuando el nmero de variables resulta ser uno la

complejidad del calculo da dos, cuando el numero de variables es dos la complejidad del clculo es

cuatro. Cuando el numero de variables es tres la complejidad del calculo es ocho. Puede ser el

nmero de variables ser infinito? No. Necesito representar el clculo en la siguiente ecuacin.

2n

Dos es el nmero de variables permitido, n el nmero de variables que aparecen en la frmula, que

8

por definicin es siempre finito. La complejidad del clculo es n. Tengo que saber que caracterstica

tiene esta formula? Que se de ese x? yo se algo de ese x cuando es en es un nmero finito que se

acerca de ese x? que es un nmero natural y es finito el nmero de clculos que tendra que hacer

para descomponerlo. Entonces tener una respuesta a esta pregunta. Si me preguntan esto yo se que

puedo responder por si o por no en un tiempo, puede ser un tiempo muy grande pero finito. Yo

puedo decirles ahora a ustedes con certeza esperen que les voy a dar una respuesta cuanto tienen

que esperar? Un tiempo finito. De que depende ese tiempo? Si la pregunta me la hacen a m de mi

capacidad de procesamiento. Uno podra decir, cuanto mas rpido fuese yo mas rpido podra dar

una respuesta. Pero en cualquier caso la respuesta la tendra en un tiempo finito. Eso nos da

seguridad? No, que la respuesta se pueda dar en un tiempo finito no es garanta de que yo pueda

encontrar la respuesta. La respuesta est pero pasa algo ms respecto de la complejidad de este

problema. Primero un problema es super complejo. La pregunta general no es resoluble. Nos

enfrentamos con la eternidad. Nos dimos cuenta que esta es la estructura de , la pregunta no es tan

compleja y podemos dar una respuesta en un tiempo finito. Ahora la pregunta es mucho menos

compleja que esta. El tiempo es finito y el procedimiento que tengo hace que el problema sea menos

complejo que lo que parece. Cual es esta caracterstica? Es un procedimiento de que tipo?

Mecnico. Es un procedimiento nada creativo. Es solo una cuestin de recorrer esas posibilidades y

encontrar una solucin. Contrapongamos la idea de procedimiento creativo a procedimiento

mecnico. No hay nada creativo en la bsqueda a la respuesta a esa pregunta. Procesamiento

mecnico de informacin. No necesito una estrategia para resolver esta pregunta. Necesito una

receta mecnica para resolver los problemas. Noten el descubrimiento que hemos hecho. Dado un

conjunto infinito de formulas gramaticales de un lenguaje puedo dar una respuesta a la pregunta

para cualquier formula es esta formula una tautologa? ahora la respuesta es s, para cualquier

formula puedo contestar si es una tautologa. La estrategia no es buscar caso por caso, eso nos

llevara la vida y ms para resolver el problema. La complejidad era la complejidad de un infinito.

Ahora descubrimos que el problema es resoluble en tiempo finito, no solamente resoluble en un

tiempo finito sino que mecnicamente resoluble en un tiempo finito. El nmero de pasos que tengo

que hacer es siempre finito. Alguien podra quejarse de que el tiempo sea finito no quiere decir que

mi vida sea suficiente para abarcar el problema, incluso la vida de toda la humanidad. El problema

puede ser tan largo que yo no vea el resultado. El proceso contempla las formulas en este sentido,

para cualquier formula que aparezca hay un procedimiento mecnico capaz de determinar en un

tiempo finito si la formula est o no est en el conjunto. De la misma manera que con los nmeros

naturales nadie vio todo el conjunto, la cuestin es tener una receta para con un algoritmo para

cualquier cosa que est aqu determinar mecnimente la cuestin.

Hay funciones que no son de este tipo. Lo importante es que el procedimiento mecnico y finito

9

tambin es una funcin. Clculos o funciones son tan complejos que resolverlas no tiene esta

estructura. Es una pregunta precisa no acerca de LP sino acerca de las formulas de LP. Lo que hasta

ahora respond es que si esta es una propiedad semntica es una propiedad que se puede determinar

de manera mecnica en un tiempo finito. Esta propiedad es algortmica. Por supuesto tambin es

algortmica otra propiedad.

Ahora yo pregunto esto: es una formula bien formada? Es una pregunta distinta a la que habla de

las posibilidades de combinaciones de las valuaciones de la formula de LP. Hasta ahora tenemos dos

propiedades, frmula bien formada y valuaciones, las dos propiedades son determinables

algortmicamente.

Estudiante: [Inaudible]

Profesor: Suponete que vos fueras un programador de juegos de computacin y yo te contrato a vos

para disear un juego de ajedrez cuantas partidas de ajedrez posibles existen en el universo?

Infinitas. Como un ser humano hace para resolver esa tarea? Si la computadora esta bien

programada...

Estudiante: [Inaudible]

Profesor: Eso es lo que hicimos. 2n es en efecto el clculo que tenemos que hacer. Yo no he hablado

de algo muy importante. Yo hable de la definicin recursiva de frmula bien formada, pero me

saltee hablar de algo muy importante. Cual es la definicin de valuacin?

Estudiante: [Inaudible]

Profesor: la estructura de la definicin del concepto de valuacin de x.

Estudiante: [Inaudible]

Profesor: Tenemos que definir los pasos. Primero el caso de las letras atmicas, el caso mas simple.

Luego de las conectivas. Tendramos que decidir que la valuacin de A es igual a uno si y slo si

la valuacin de A es igual a cero. Entonces que estructura tiene la definicin del concepto de

valuacin?

10

V (x) 0

1

V(A)=1 ssi V(A)=0

La definicin de valuacin es una definicin recursiva. Se construye sobre que? Se dieron cuenta

de que tenemos que usar la negacin, el condicional... para cada clusula de la definicin recursiva

de formula bien formada hay una y solo una clusula anloga para la funcin de valuacin. Es decir,

las estructuras de ambas definiciones estn calcadas. Para cualquier complejo que aparezca voy a

poder asignar valores a las formulas del lenguaje LP. Todas tienen valores asignados. Entonces

podemos ver claramente que la posibilidad semntica que uno tiene, la receta o regla esta

determinada mecnicamente por la aplicacin de estas clusulas. Esto ser posible? S, lo es, si

esto es una formula bien formada. Y como se que es una formula bien formada? podra

descomponer esto y hacer un rbol finito de manera que las ramas sean formulas atmicas, es el

resultado de haber utilizado alguna de las clusulas de formula bien formada. El nmero de

variables y conectivos que he utilizado es finito. Veamos un ejemplo.

((pq))(st))(zt)

Hay seis variables distintas, por lo tanto el nmero es 26 cuantas variables distintas podran

aparecer en una frmula como esta? n, siendo n cualquiera de los nmeros naturales. Entonces la

complejidad de la pregunta general es 2n esto quiere decir que yo he dado la respuesta para cada

una de las frmulas posibles? S, en el siguiente sentido, para cualquier partida de ajedrez tengo una

partida a disputar, pero las partidas son infinitas, no es que las enumer todas, slo se que para

cualquiera que se me plantee tengo una respuesta, mecnica y finita. Y eso es todo lo que

necesitamos.

Estudiante: [Inaudible]

Profesor: es una frmula del metalenguaje que puede representar cualquiera de las frmulas de

LP. Si la pregunta es es una tautologa? depende de qu reemplace por . En particular puedo

reemplazar por cualquier formula bien formada del lenguaje. Lo que se es que la complejidad del

11

clculo es tal que tengo una respuesta garantizada por si o por no, esa respuesta la voy a dar en un

tiempo finito y el procedimiento es un procedimiento no creativo, mecnico. Ahora se como

responder esta pregunta para cualquiera de las frmulas que aparezcan aqu.

Estudiante: [Inaudible]

Profesor: No. Hay varias maneras de hacer irresoluble, o sea infinito. Una es admitir formulas en

LP que tuviesen conectivas infinitas, permitiendo que haya formulas infinitas en LP, eso hara que el

problema sea irresoluble. Hay otra manera, como crece la ecuacin? La ecuacin crece con el

nmero 2n , ese nmero puede variar. Entonces habilitamos un nmero infinito de variables.

Estudiante: [Inaudible]

Profesor: Otra manera es agregar un tercer valor de verdad. Si existe el valor indeterminado el

problema no seria resoluble. Si tuviramos una lgica con infinitos valores de verdad el problema se

volvera irresoluble mecnicamente. Un problema se vuelve irresoluble cuando no es decidible

mecnicamente. Podra haber manera de resolver problemas no mecnicas. Hasta ahora hemos visto

problemas lgicos que se resuelven de manera mecnica. Tautologicidad es un problema lgico

resoluble de manera mecnica. La pregunta general es ser que todo problema lgico es un

problema que se resuelve mecnicamente? Por que pongo tanto nfasis en que este problema sea

algortmico, resoluble, mecnico, en un tiempo finito? Por qu creen que es tan importante esto?

Estudiante: [Inaudible]

Profesor: escucharon lo que contest l? Lo que contest l es que podramos pensar ahora esto.

Supongamos que encontremos un problema que no es soluble mecnicamente, problemas que no

son abarcables en nuestra mente porque requeran barrer una infinitud de cosas, no se resuelven

dando un nmero finito de pasos sino usando otra estrategia. Podra quedar la idea siguiente. Si un

problema vinculado con una tarea finita no es resoluble por este procedimiento ser que no es

resoluble en absoluto? Si encuentro alguna propiedad cuyo clculo no pueda resolverse mediante un

algoritmo, ser que ese problema no tiene resolucin? Uno me podra decir si no tiene una

resolucin humana que importa que haya una resolucin? Entonces podra haber un proceso de

resolucin de problemas que sea no mecnico. Podra haber ciertas propiedades lgicas cuya

resolucin lo sea por medio de un procedimiento no algortmico. Que implicancias filosficas

tendra descubrir procesos resolubles pero no mecnicamente resolubles? El punto es si hubiera

12

procesos resolubles no mecnicamente habra limites en aquello que llamamos computabilidad.

Habra procesos solubles no computables. Habra algunas preguntas que no se las podra responder

de manera mecnica. Es obvio que si me pongo a competir con mquinas respecto de tautologicidad

va a ganar la mquina en tiempo. Supnganse que yo me ponga a competir la computadora que

formulas buscaran para hacer ganar a uno o a otro? El procedimiento es mecnico. Ella me gana

respecto de lo que yo puedo hacer. Si dan una frmula con 500 variables ganara la computadora, yo

no puedo retener eso. Ahora quiere decir que la maquina puede superarme en cualquier actividad

de este tipo? Esa es la pregunta que les dejo para que piensen para el lunes.

Material del sitio www.accionfilosofica.com

1. Evale: Mc Taggart argumenta que el tiempo no es real, a partir del supuesto de que si lo fuera, los cambios tambin seran reales. Pero, si los cambios fueran reales, los hechos tendran inflexiones temporales. Pero, l muestra que ka idea de que los hechos tengan inflexiones temporales, conduce a contradiccin. De lo que concluye que el tiempo no es real. 2. Qu es un procedimiento algortmico? La propiedad de ser consecuencia lgica de un conjunto de frmulas de Lp, Es algortmica? Relacione algoritmo con proceso computable (busque en Internet la respuesta a este vnculo). Imagine o busque en Internet tareas que no puedan ser computadas. 3. Qu quiere decir que dos frmulas son lgicamente equivalentes? Y cundo una frmula implica lgicamente otra? 4. Demuestre el teorema 2 del cap. 2. Bibliografa: Semana del 15 de Abril: Gamut, L Introduccin a la lgica. Introduccin y Captulo 2. Ficha de Metalgica. Picollo /Teijeiro (hasta p. 25).

13