[Logica-l] A mais curta demonstração de que P =/= NP
== Teorema: P =/= NP Prova> Considere, conjuntivamente as seguintes asserções: (A) P =/= NP (B) Se P =/= NP então NP =/= P (C) Exatamente uma destas trës asserções é verdadeira. É claro que (B) é verdadeira, e que (C) não pode ser verdadeira (caso contrário, haveria pelo menos duas asserções verdadeiras). Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das trës asserções seja verdadeira. Em consequência, ou nenhuma delas é verdadeira (o que náo é o caso, pois pelo menos (B) é verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). Portanto P =/= NP. == O que está errado com este raciocínio? A única crítica é que este argumento é universal, ou seja, prova-se qualquer coisa em lugar de (A). Mas por acaso alguma noçao de demosnstraçao exclui uma tal; "trivialidade demonstrativa"? Abs, Walter Prof. Dr. Walter Carnielli Director Centre for Logic, Epistemology and the History of Science – CLE State University of Campinas –UNICAMP 13083-859 Campinas -SP, Brazil Phone: (+55) (19) 3521-6517 Fax: (+55) (19) 3289-3269 e-mail: walter.carnie...@cle.unicamp.br Website: http://www.cle.unicamp.br/prof/carnielli ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] Proposta de criação da Comissão Especial de Lógica na Computação
Para os interessados na criação da Comissão Especial de Lógica e Computação, Entrei em contato com o vice-presidente da SBC, prof. Marcelo Walter, e com o diretor de Eventos e Comissões Especiais da SBC, prof. Lisando Granville, e eles me informaram que, no momento, está congelada a criação de novas comissões especiais. Há uma discussão de uma nova proposta na qual, antes de se criar uma CE, deveria ser criado um grupo de interesse. Esta proposta está em análise e o prof. Lisando espera que a mesma fique concretizada durante o congresso de julho da SBC. Abraços a todos, Ana > -- Forwarded message -- > From: Marcelo Finger > Date: 2011/5/12 > Subject: [Logica-l] Proposta de criação da Comissão Especial de Lógica > na Computação > To: logica-l@dimap.ufrn.br > > > Caros. > > Conforme combinado reunião que tivemos no EBL2011, montamos uma página > com a > proposta inicial > de criação da Comissão Especial de Lógica na Computação junto à > SBC. > > Esta proposta encontra-se na página http://www.tecmf.inf.puc-rio.br/CELC > . > > à IMPORTANTÃSSIMO QUE AS PESSOAS INTERESSADAS SE CADASTREM NA PÃGINA. > > CrÃticas e sugestões são muito bem vindas, e serão discutidas no > próximo > LSFA em Belo Horizonte. > > Abraços cordiais > > Alexandre Rademaker > Marcelo Finger > Mário Benevides > > -- > Marcelo Finger >  Departamento de Ciencia da Computacao >  Instituto de Matematica e Estatistica >  Universidade de Sao Paulo >  Rua do Matao, 1010 >  05508-090   Sao Paulo, SP   Brazil >  Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) >  http://www.ime.usp.br/~mfinger > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
[Logica-l] [LC] Proposta de criação do Grupo de Interesse em Lógica na Computação
PessoALL: Aproveitando a informação da futura presidenta Ana Teresa sobre a criação do Grupo de Interesse em Lógica na Computação, junto à SBC, venho reiterar a importância de que os interessados em participar da criação deste Grupo de Interesse se inscrevam na wiki abaixo: http://www.tecmf.inf.puc-rio.br/CELC Vocês vão gastar nisto menos tempo do que gastaram para ler este email! Sim, e aqueles que irão participar da reunião da SBC aqui em Natal neste mês de julho (Aracele? mais alguém?) talvez possam nos informar a quantas andará a tal modificação dos estatutos correspondentes da SBC no que diz respeito à criação de novas Comissões Especiais / Grupos de Interesse, tendo em vista as modificações geradas pela ênfase da SBC nos Grandes Desafios da Computação para o século XXI. Quem eles devem procurar, Ana? O próprio Marcelo Walter? O professor Granville? Além disso, como recém informado pela Elaine, coordenadora do próximo LSFA, o nosso evento principal de Lógica na Computação, recordo que está aberto o sistema, até neste dia 15 de junho, para envio de pôsteres: http://www.mat.ufmg.br/lsfa2011/LSFA2011/Call_for_papers_posters.html Será esta também uma ótima oportunidade para discutirmos os próximos passos do nosso Grupo de Interesse. Vamos participar! Abraços, Joao Marcos -- http://sequiturquodlibet.googlepages.com/ ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] livros bons a respeito de sistemas lógicos em geral
Que tal: An Introduction to Non-Classical Logic: From If to Is Graham Priest 646 pages Cambridge University Press; 2 edition (June 2, 2008) ISBN-10: 0521854334 Classical and Nonclassical Logics: An Introduction to the Mathematics of Propositions Erick Schechter 536 pages Princeton University Press (August 8, 2005) ISBN-10: 9780691122793 Há ainda, em um outro tom, a série "Semantic Foundations of Logic" de Richard L. Epstein. JM 2011/5/25 Arthur Buchsbaum : > Caros colegas: > > > > Venho procurando há tempos um ou mais bons livros-texto a respeito de > sistemas lógicos em geral. Uma tendência mais recente dos cursos acadêmicos > de Lógica está em apresentar alguns sistemas simultaneamente, no mesmo > curso, e buscar relacioná-los entre si. > > Seriam livros que expõem, de uma forma mais ou menos unificada, com clareza > e economia de pensamento, alguns dos sistemas lógicos mais importantes, tais > como a lógica clássica (nos seus níveis proposicional, quantificacional, > equacional e, eventualmente, descritivo), a lógica intuicionista, uma ou > mais lógicas modais, e, eventualmente, uma ou mais lógicas da implicação > relevante. Exemplos de lógica paraconsistente e de lógica paracompleta (não > necessariamente intuicionista) parecem-me também de interesse para tais > cursos. > > Para cada um destes sistemas deveria haver, pelo menos, uma exposição > sintática (através de um cálculo de sequentes, ou axiomática, ou de dedução > natural) e uma contraparte semântica. > > Também, para um ou mais destes sistemas, poderia ser apresentada uma forma > de automatização, através de tablôs ou de outro método. > > Mais ou menos nesta linha, encontrei os seguintes livros: > > # “Logics”, 1997, de John Nolt (algumas provas por indução matemática pecam > por falta de concisão, poderiam ser mais curtas se fosse adotado o melhor > caminho); > > # “Logic: The Basics”, 2010, de J.C. Beall (só possui as apresentações > semânticas, e, dos sistemas lógicos, só a lógica clássica e exemplos de uma > lógica paraconsistente e uma paracompleta); > > # “Logical Pluralism”, 2006, de J.C. Beall e Greg Restall (só possui alguns > detalhes semânticos concernentes à lógica clássica, a algumas relevantes, à > intuicionista, a algumas lógicas livres e a algumas de ordem superior); > > # “Systems of Logic”, 1989, de Norman M. Martin (restringe-se quase que > exclusivamente a detalhes sintáticos da lógica clássica e a algumas de suas > sublógicas). > > # “Introduction to Logic”, 2ª Edição, 2010, de Harry J. Gensler. > > Todos os livros acima não me parecem satisfatórios. > > Se algum dos colegas tiver um ou mais livros a sugerir nesta linha (em suma, > livros-texto que apresentem a lógica clássica, a intuicionista, uma modal e, > eventualmente, outros sistemas importantes, pelo menos de uma forma > sintática e uma semântica), peço que mos apresente. > > a) Arthur Buchsbaum > > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > -- http://sequiturquodlibet.googlepages.com/ ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
Bertrand Russell é capaz de dizer o que há de errado com esta prova. []s 2011/6/3 Walter Carnielli > == > Teorema: P =/= NP > > Prova> > > Considere, conjuntivamente as seguintes asserções: > > (A) P =/= NP > > (B) Se P =/= NP então NP =/= P > > (C) Exatamente uma destas trës asserções é verdadeira. > > É claro que (B) é verdadeira, e que (C) não pode ser verdadeira > (caso contrário, haveria pelo menos duas asserções verdadeiras). > > Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das > trës asserções seja verdadeira. Em consequência, ou nenhuma delas é > verdadeira (o que náo é o caso, pois pelo menos (B) é > verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). > > Portanto P =/= NP. > > == > > O que está errado com este raciocínio? A única crítica é que > este argumento é universal, ou seja, prova-se qualquer coisa > em lugar de (A). Mas por acaso alguma noçao de demosnstraçao > exclui uma tal; "trivialidade demonstrativa"? > > Abs, > > Walter > > Prof. Dr. Walter Carnielli > Director > Centre for Logic, Epistemology and the History of Science – CLE > State University of Campinas –UNICAMP > 13083-859 Campinas -SP, Brazil > Phone: (+55) (19) 3521-6517 > Fax: (+55) (19) 3289-3269 > e-mail: walter.carnie...@cle.unicamp.br > Website: http://www.cle.unicamp.br/prof/carnielli > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > -- Marcelo Finger Departamento de Ciencia da Computacao Instituto de Matematica e Estatistica Universidade de Sao Paulo Rua do Matao, 1010 05508-090Sao Paulo, SP Brazil Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) http://www.ime.usp.br/~mfinger ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
Tá vivo?! 2011/6/3 Marcelo Finger : > Bertrand Russell é capaz de dizer o que há de errado com esta prova. > > []s > > 2011/6/3 Walter Carnielli > >> == >> Teorema: P =/= NP >> >> Prova> >> >> Considere, conjuntivamente as seguintes asserções: >> >> (A) P =/= NP >> >> (B) Se P =/= NP então NP =/= P >> >> (C) Exatamente uma destas trës asserções é verdadeira. >> >> É claro que (B) é verdadeira, e que (C) não pode ser verdadeira >> (caso contrário, haveria pelo menos duas asserções verdadeiras). >> >> Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das >> trës asserções seja verdadeira. Em consequência, ou nenhuma delas é >> verdadeira (o que náo é o caso, pois pelo menos (B) é >> verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). >> >> Portanto P =/= NP. >> >> == >> >> O que está errado com este raciocínio? A única crítica é que >> este argumento é universal, ou seja, prova-se qualquer coisa >> em lugar de (A). Mas por acaso alguma noçao de demosnstraçao >> exclui uma tal; "trivialidade demonstrativa"? >> >> Abs, >> >> Walter >> >> Prof. Dr. Walter Carnielli >> Director >> Centre for Logic, Epistemology and the History of Science – CLE >> State University of Campinas –UNICAMP >> 13083-859 Campinas -SP, Brazil >> Phone: (+55) (19) 3521-6517 >> Fax: (+55) (19) 3289-3269 >> e-mail: walter.carnie...@cle.unicamp.br >> Website: http://www.cle.unicamp.br/prof/carnielli >> ___ >> Logica-l mailing list >> Logica-l@dimap.ufrn.br >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> > > > > -- > Marcelo Finger > Departamento de Ciencia da Computacao > Instituto de Matematica e Estatistica > Universidade de Sao Paulo > Rua do Matao, 1010 > 05508-090 Sao Paulo, SP Brazil > Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) > http://www.ime.usp.br/~mfinger > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > -- Carlos D Santos Jr., PhD Research Fellow @ University of Nottingham https://www.horizon.ac.uk/ ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
Perfeito Walter 2011/6/3 Walter Carnielli > == > Teorema: P =/= NP > > Prova> > > Considere, conjuntivamente as seguintes asserções: > > (A) P =/= NP > > (B) Se P =/= NP então NP =/= P > > (C) Exatamente uma destas trës asserções é verdadeira. > > É claro que (B) é verdadeira, e que (C) não pode ser verdadeira > (caso contrário, haveria pelo menos duas asserções verdadeiras). > > Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das > trës asserções seja verdadeira. Em consequência, ou nenhuma delas é > verdadeira (o que náo é o caso, pois pelo menos (B) é > verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). > > Portanto P =/= NP. > > == > > O que está errado com este raciocínio? A única crítica é que > este argumento é universal, ou seja, prova-se qualquer coisa > em lugar de (A). Mas por acaso alguma noçao de demosnstraçao > exclui uma tal; "trivialidade demonstrativa"? > > Abs, > > Walter > > Prof. Dr. Walter Carnielli > Director > Centre for Logic, Epistemology and the History of Science – CLE > State University of Campinas –UNICAMP > 13083-859 Campinas -SP, Brazil > Phone: (+55) (19) 3521-6517 > Fax: (+55) (19) 3289-3269 > e-mail: walter.carnie...@cle.unicamp.br > Website: http://www.cle.unicamp.br/prof/carnielli > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
hahaha... mais uma versão sofisticada do paradoxo do mentiroso! Gostei! Vou ter diversão para hoje com meus netos! Vamos ver se eles descobrem por que C) não é uma sentença! Mas, como eles ainda nao sabem o que é ser P-completo ou NP completo, vou por no lugar de A) a sentença "0=1", ok? Mande mais dessas pra alegrar uma vovó aposentada! Beijos Andrea PS: Walter, a gente costumava dizer antigamente (quando eu ainda não era vovó) que o que você chama "trivialidade demonstrativa" era uma indicação de presença de inconsistência no ponto de partida... ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
Só falta agora juntarmos a isto uma demonstração qualquer para P = NP (o mesmo argumento serve, claro, trocando a premissa (A)), e aí podemos todos ficar felizes com a verdade simultânea de (A) & (B) & (C). :-) JM 2011/6/3 Marcelo Finger : > Bertrand Russell é capaz de dizer o que há de errado com esta prova. > > []s > > 2011/6/3 Walter Carnielli > >> == >> Teorema: P =/= NP >> >> Prova> >> >> Considere, conjuntivamente as seguintes asserções: >> >> (A) P =/= NP >> >> (B) Se P =/= NP então NP =/= P >> >> (C) Exatamente uma destas trës asserções é verdadeira. >> >> É claro que (B) é verdadeira, e que (C) não pode ser verdadeira >> (caso contrário, haveria pelo menos duas asserções verdadeiras). >> >> Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das >> trës asserções seja verdadeira. Em consequência, ou nenhuma delas é >> verdadeira (o que náo é o caso, pois pelo menos (B) é >> verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). >> >> Portanto P =/= NP. >> >> == >> >> O que está errado com este raciocínio? A única crítica é que >> este argumento é universal, ou seja, prova-se qualquer coisa >> em lugar de (A). Mas por acaso alguma noçao de demosnstraçao >> exclui uma tal; "trivialidade demonstrativa"? >> >> Abs, >> >> Walter >> >> Prof. Dr. Walter Carnielli >> Director >> Centre for Logic, Epistemology and the History of Science – CLE >> State University of Campinas –UNICAMP >> 13083-859 Campinas -SP, Brazil >> Phone: (+55) (19) 3521-6517 >> Fax: (+55) (19) 3289-3269 >> e-mail: walter.carnie...@cle.unicamp.br >> Website: http://www.cle.unicamp.br/prof/carnielli -- http://sequiturquodlibet.googlepages.com/ ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
Re: [Logica-l] A mais curta demonstração de que P =/= NP
Creio que o problema da prova é a autoreferência. D. Decio Krause Departamento de Filosofia Universidade Federal de Santa Catarina 88040-940 Florianópolis, SC -- Brasil deciokrause[at]gmail.com www.cfh.ufsc.br/~dkrause "Você não está pensando. Está meramente sendo lógico!" (Bohr para Einstein) Em 03/06/2011, às 10:25, Marcelo Finger escreveu: > Bertrand Russell é capaz de dizer o que há de errado com esta prova. > > []s > > 2011/6/3 Walter Carnielli > >> == >> Teorema: P =/= NP >> >> Prova> >> >> Considere, conjuntivamente as seguintes asserções: >> >> (A) P =/= NP >> >> (B) Se P =/= NP então NP =/= P >> >> (C) Exatamente uma destas trës asserções é verdadeira. >> >> É claro que (B) é verdadeira, e que (C) não pode ser verdadeira >> (caso contrário, haveria pelo menos duas asserções verdadeiras). >> >> Portanto (C) é falsa, e daí não é o caso que *exatamente* uma das >> trës asserções seja verdadeira. Em consequência, ou nenhuma delas é >> verdadeira (o que náo é o caso, pois pelo menos (B) é >> verdadeira), ou duas delas são verdadeiras, a saber, (A) e (B). >> >> Portanto P =/= NP. >> >> == >> >> O que está errado com este raciocínio? A única crítica é que >> este argumento é universal, ou seja, prova-se qualquer coisa >> em lugar de (A). Mas por acaso alguma noçao de demosnstraçao >> exclui uma tal; "trivialidade demonstrativa"? >> >> Abs, >> >> Walter >> >> Prof. Dr. Walter Carnielli >> Director >> Centre for Logic, Epistemology and the History of Science – CLE >> State University of Campinas –UNICAMP >> 13083-859 Campinas -SP, Brazil >> Phone: (+55) (19) 3521-6517 >> Fax: (+55) (19) 3289-3269 >> e-mail: walter.carnie...@cle.unicamp.br >> Website: http://www.cle.unicamp.br/prof/carnielli >> ___ >> Logica-l mailing list >> Logica-l@dimap.ufrn.br >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> > > > > -- > Marcelo Finger > Departamento de Ciencia da Computacao > Instituto de Matematica e Estatistica > Universidade de Sao Paulo > Rua do Matao, 1010 > 05508-090Sao Paulo, SP Brazil > Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) > http://www.ime.usp.br/~mfinger > ___ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
[Logica-l] Mas, afinal, o que eh Matematica?
Palestra - Logica do Espaco Tempo - Prof. Newton Carneiro Affonso da Costa Coloquio do Depto. de Matematica Aplicada do Institudo de Matematica e Estatistica da Universidade de Sao Paulo. Hoje, 03-06-2011, 16:00 - 17:00. Pergunta de alguem da plateia, ao final da palestra: Mas, afinal, o que eh Matematica? Resposta do Prof. Newton: "Talvez Matematica seja uma especie de luta pela vida.Antigamente o homem sobrevivia dando porrada.Hoje fazemos modelos matematicos da realidade." Eh sempre um prazer ouvir o Prof. Newton. A palestra teve que ser transferida para uma sala maior, devido a esperada super-lotacao. Bom fim de semana a todos, --- Julio (Stern) ___ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
