Oi João. Eu uma vez tive uma discussão com o Ruy Excel sobre um assunto similar: o grau de interesse de um teorema. A gente informalmente discutiu que o nível de interesse é a razão entre o tamanho da menor prova conhecida (usando a regra que v quiser) e o tamanho do teorema. Quanto maior esta razão , maior o interesse. O problem é que isso relativiza o interesse pelo sistema de dedução utilizado.
[]s Marcelo 2013/3/6 Joao Marcos <[email protected]> > Gostaria de fazer uma consulta simples entre os colegas com mais > intuição do que eu sobre este assunto. > > Um aluno me perguntou como poderia fazer para "comparar o nível de > dificuldade de duas derivações", em dedução natural. A gente faz em > sala de aula aquelas asserções ingênuas, do tipo "se você usou a regra > do absurdo clássico, trata-se de uma derivação não trivial", "se você > usou regras com descarte, a derivação é potencialmente mais complexa", > "se você precisou usar lemas, a derivação não é tão básica assim", e > até "se você construiu sua derivação de forma construtiva, ela pode > até ter custado mais, mas é mais confiável"... > > Pois bem, minha primeira sugestão ao aluno foi que comparasse o nível > de dificuldade de duas derivações executando dois passos: primeiro, > converta estas derivações para uma forma *normalizada*; em seguida, > conte o número de nós destas versões normalizadas, e o número de > aplicações da regra do absurdo clássico. A Valeria me chamou a > atenção em privado para a necessidade de considerar também outras > variáveis, como o numero de regras usadas, e não somente o numero de > regras do absurdo. > > E o que acham os colegas? Como vocês comparariam, em princípio, o > *nível de dificuldade* de duas derivações, digamos, em dedução > natural? > > Abraços, > Joao Marcos > > -- > http://sequiturquodlibet.googlepages.com/ > _______________________________________________ > Logica-l mailing list > [email protected] > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > -- Marcelo Finger Department of Computer Science, Cornell University on leave from: Departament of Computer Science, IME University of Sao Paulo http://www.ime.usp.br/~mfinger _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
