Aula 27/04 - Prova de Henkin

Olá para todos. 

Veremos na aula de amanhã, 27/04, os teoremas 32.2 até 32.10 da prova de Henkin (Hunter seção 32).

Abaixo, uma apostila com o passo a passo das provas e alguns comentários,

http://dl.dropbox.com/u/5959592/henkin_prop_1.pdf

Abraços

Prova de Henkin - lógica sentencial

Olá para todos.

Para fechar a prova da completude de Kalmar que vimos nas últimas aulas, tentem explicar em detalhe por que lemos no Hunter, no fim da p. 104, que qualquer sistema de lógica sentencial que tenha os teoremas 1 a 7 da p. 105 é completo.

Para a aula do dia 20/4, leiam o início da seção 32 do Hunter, sobre a prova da completude de Henkin (pp. 105-109). Hunter apresenta nas subseções (a), (b), (c) e (d) resultados preliminares que serão usados na prova da completude de Henkin.

Na seção (a) estão provas dos teoremas 1-7, listados nas pp. 105 e 106. Tentem prová-los usando um sistema de dedução natural que vocês estejam familiarizados e, depois, no sistema axiomático PS apresentado no Hunter. Lembrem-se de usar o teorema da dedução. Para provar o teorema 6 da p. 106 lancem A como hipótese para chegar a B e ØB. Usem ØB ® (B ® (Ø(A ® A))) para obter, com TD, A ®  Ø(A ® A). Agora usem dupla negação e o axioma 3. Notem que o teorema 6 simula em PS a regra de introdução da negação, ou redução ao absurdo.

Depois, leiam com atenção as seções (b) e (c). Deixem de lado por enquanto a seção (d).

Lembrem-se que em 25/4 não haverá aula. Aproveitem o dia livre para estudar as seções (b) e (c). Dia 27/4, quarta, faremos uma revisão dessas seções e começaremos a seção (d).

Abraços

Teorema da correção

Olá para todos.
Nas aulas dos dias 11 e 13 veremos, conforme combinado, as seções 24, 25 e 28 do Hunter.

Abaixo, uma apostila com o passo a passo da prova do teorema da correção, Hunter 28.4

http://dl.dropbox.com/u/5959592/correcao_hunter28.4.pdf

Se houver tempo, vamos começar no dia 13 a prova de Kalmar do teorema da completude. Leiam as seções 29 e 31 do Hunter, com atenção para o Lema 31.14. Há uma prova desse lema em Robbin p. 23, cujo passo a passo está em 

http://sites.google.com/site/textoslogica/arquivos/lema_6.2.pdf  

Compacidade

Na última aula, vimos a versão sintática do teorema da compacidade. A versão semântica vai depender do teorema da completude, que não provamos ainda.

No link http://dl.dropbox.com/u/5959592/read_compacidade.pdf há trechos do livro do Stephen Read, Thinking about Logic (OUP), que tratam do teorema da compacidade. Há problemas filosóficos muito interessantes relacionados à compacidade da lógica clássica de primeira ordem. O texto do Read é uma introdução acessível a tais problemas.

Dicas: Na Enciclopédia de termos lógico-filosóficos (ed. Murcho et al.): teoria dos modelos, teorema da compacidade e também outros mencionados nos verbetes acima.

Na Wikipedia : http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic

http://pt.wikipedia.org/wiki/Completude_%28l%C3%B3gica%29

http://pt.wikipedia.org/wiki/Teorema_da_compacidade

http://pt.wikipedia.org/wiki/Teorema_da_completude_de_G%C3%B6del

Para quem quiser se aventurar nos modelos não-standard da aritmética, ver também o capítulo do livro do Boolos & Jeffrey, Computability and Logic, no link http://dl.dropbox.com/u/5959592/non_std_arit.pdf

Após a leitura do texto, tente responder às seguintes perguntas: O que diz o teorema da compacidade em sua versão sintática e, dada a completude, em sua versão semântica? O que é a regra-w? Por que a regra-w não pode ser usada na teoria da prova clássica? Por que não podemos expressar, na lógica de primeira ordem, a sentença 'não existe um número que seja diferente de 0 e 1 e 2 e…'? 

Algumas reflexões sobre o chamado ‘princípio de composicionalidade’

Extraído do capítulo 5 de Thinking about Logic de Stephen Read, OUP

 

Como a linguagem é possível? Como é possível, a partir da aprendizagem de um vocabulário básico e finito de uma linguagem, formar um sem número de novos enunciados, novas proposições que expressam pensamentos que nunca foram antes formulados? Pois isso é possível. Apesar do vocabulário de uma linguagem ser mundo grande, como uma olhada no dicionário revela, ele é pequeno quando comparado com o número imenso de sentenças que compõem os livros das bibliotecas espalhadas pelo mundo. Dentre essas sentenças, poucas são idênticas. Dentre as sentenças que lemos, poucas são as que nós vimos antes. Como é possível que o leitor compreenda essas sentenças? Como é possível que o leitor as conceba e formule?

A resposta é óbvia, mas suas implicações são poderosas. Nós podemos aprender uma linguagem porque seu vocabulário e suas regras gramaticais são relativamente pequenas – ambas podem ser reunidas em um pequeno número de volumes. Um dicionário de alguns volumes como o Oxford English Dictionary contém pouco mais que o vocabulário da maior parte dos falantes individuais do inglês. E mesmo esse dicionário consiste de dez ou doze volumes, o que é uma pequena parte da biblioteca onde ele está. A partir desse vocabulário, as regras gramaticais permitem a criação de um número infinitamente grande de sentenças. Para que possamos entender tais sentenças, os significados das palavras individuais são combinados de acordo com a estrutura estabelecida pela gramática. Em outras palavras, da mesma forma que uma sentença é literalmente composta pelas palavras que ela contém, o significado de uma sentença, a proposição, é de alguma maneira 'composto' pelos significados das palavras que ela contém. A idéia inicial é óbvia: entendemos novas sentenças porque entendemos como seus significados resultam dos significados das palavras que as constituem. As implicações disso não são óbvias, e o que isso diz não é tão claro: os significados das palavras se combinam de algum modo para compor o significado da sentença completa, a proposição por ela expressada.

O princípio em questão aqui é por vezes chamado de 'princípio da composicionalidade', outras vezes de 'princípio de Frege', o grande filósofo alemão da matemática e da linguagem do fim do século XIX. Os dois termos cobrem aplicações bastante diferentes da idéia básica. Mas a motivação subjacente é a mesma. De algum modo precisamos explicar a 'criatividade' da linguagem, o modo pelo qual uma criança, ao ouvir um número finito e pequeno de enunciados, desenvolve a habilidade de produzir e compreender um sem número de proposições que não estão entre os dados sobre os quais tal habilidade foi desenvolvida. A explicação é a mais simples e a mais plausível para preencher essa lacuna, e está de acordo com a experiência pessoal, do falante de uma linguagem, de participar de uma conversa – um conjunto de enunciados seus e de outros falantes. Os dados iniciais e os novos enunciados produzidos são analisados em componentes significativos, e é postulada uma conexão entre o todo e as partes. Mas o que é essa conexão?

Aqueles que chamam essa idéia de princípio de 'composicionalidade' estarão inclinados a interpretar essa conexão de modo bastante literal. Eu mencionei no capítulo 1 como Russell considerou que as proposições – significados das sentenças e objetos de crença – teriam como constituintes particulares e universais. Assim, por exemplo, a proposição que Sócrates é sábio teria, literalmente, Sócrates e a sabedoria como constituintes. Para Russell, o significado de 'Sócrates' era o próprio filósofo Sócrates, em pessoa; e o significado de 'é sábio' era o universal ou a propriedade sabedoria. Portanto, o significado da sentença 'Sócrates é sábio' seria composto por Sócrates e a sabedoria, do mesmo modo que a sentença é composta por sujeito e predicado. Uma visão mais sofisticada, diferentemente, aponta para uma dependência funcional do significado da expressão complexa em relação aos significados das suas partes. Considere uma analogia: 4 é o resultado do quadrado de dois, 4 = 2², mas 4 não contém literalmente o número 2 como um constituinte, tampouco contém a função y = x², que recebe um número x e o eleva ao quadrado produzindo um número y. Antes, 4 é o resultado de aplicar ao número 2 a função que eleva um número ao quadrado. Para Frege, é desse modo que se estabelece a conexão entre o significado de uma sentença e os significados das suas partes. O quadro é mais complicado porque Frege distinguia o significado da expressão dos seus componentes. Mas o princípio é preservado: o significado de uma expressão complexa, uma sentença por exemplo, resulta dos significados das suas partes e pode ser calculado a partir deles. Assim, a compreensão das partes e do modo elo qual o todo depende das partes explica a compreensão do todo.

* * * 

Material disponível e aulas dos dias 4 e 6 de abril

Olá para todos.

Nas próximas aulas, 4 e 6 de abril veremos:

1. O sistema axiomático de P de lógica sentencial (Hunter seções 22 e 23)

2. O teorema da dedução para P (Hunter seção 26).

As seções do Hunter você encontra em 

http://dl.dropbox.com/u/5959592/books/Metalogic_Hunter.pdf

E uma apostila sobre o t. da dedução está em 

http://dl.dropbox.com/u/5959592/teorema_da_deducao.pdf

Abraços

Material disponível - Metalógica

Olá para todos.

Abaixo, as seções 21 e 22 do Hunter que estudaremos nas aulas dos dias 28 e 30 de março.

http://dl.dropbox.com/u/5959592/hunter_21_22.pdf

Leiam também a seção 16.1, sobre indução, do livro do Barwise & Etchemendy, Language, Proof and Logic, que está no link

http://dl.dropbox.com/u/5959592/inducao/LPL_Induction.pdf

Há também exercícios de indução nas apostilas 

http://dl.dropbox.com/u/5959592/inducao/inducao_1.pdf

http://dl.dropbox.com/u/5959592/inducao/inducao_2.pdf

A primeira lista de exercícios está no link

http://dl.dropbox.com/u/5959592/meta_lista_1.pdf

A prazo de entrega é até 6/4, quarta-feira.  

Palestra sobre ensino da lógica e minicurso de teoria dos modelos

Palestra: O Ensino da Lógica nos Cursos de Graduação em Filosofia

Dia 23 de março, sala 3042, 12h

Prof. Antonio Coelho (UFSC)

Minicurso: Teoria dos Modelos 

Dias 23, 24 e 25 de março de 2011, sala 2013, com início às 14h

Prof. Antonio M.N. Coelho (UFSC). 

Programa:

Primeira aula - breves observações sobre uma prova, ao modo de Henkin, do teorema da completude; o teorema da compacidade e a inexistência de axioma de finitude.
Segunda aula - o teorema de Löwenheim-Skolem e o chamado Paradoxo de Skolem.
Terceira aula - modelos não-standard da aritmética.
 
Referências:
Boolos, G.& Jeffrey,R.- Computability and Logic - third edition, Cambridge University Press, Cambridge, 1989
Shoenfield, J.R.- Mathematical Logic - Association for Symbolic Logic & A K
Peters, Natick, Massachusetts,2000( publicado originalmente pela Addison-Wesley em 1967)
Chang, C.C.& Keisler, H.J.- Model Theory - third edition, North-Holland Publishing Company, Amsterdam, 1990

Metalógica - material disponível, programação das aulas etc.

Olá para todos.

Vamos iniciar o curso com uma revisão da lógica de primeira ordem, começando pela lógica sentencial.

Tópicos: funções, sintaxe da lógica sentencial, semântica (funções de verdade), tautologias e contradições, consistência semântica, consequência lógica semântica.

Referências: Hunter seções 15 a 19 (aqui: http://dl.dropbox.com/u/5959592/hunter_15_19.pdf) + apostilas de lógica 1 e 2 + respectivos capítulos do Mortari.

As apostilas de lógica 1 e 2 estão na página http://sites.google.com/site/textoslogica/. 

(Notem que a linguagem que começaremos a estudar, seguindo o Hunter, tem implicação e negação como primitivos. Veremos mais adiante por que estamos começando com essa linguagem.) 

Para a revisão da lógica de predicados vamos usar os capítulos 10 e 11 do Mortari e as apostilas disponíveis nos links

http://dl.dropbox.com/u/5959592/stx_log_pred.pdf
http://dl.dropbox.com/u/5959592/sem_log_pred.pdf


Abraços

Minicurso de Teoria dos Modelos

Nos dias 23, 24 e 25 de março de 2011 será ministrado no Departamento de Filosofia da UFMG um minicurso de Teoria dos Modelos. 

Serão três aulas, uma por dia, com três horas de duração cada. O ministrante será o professor Antonio M.N. Coelho, do Departamento de Filosofia da UFSC. O conteúdo será desenvolvido da seguinte maneira:

Primeira aula - breves observações sobre uma prova, ao modo de Henkin, do teorema da completude; o teorema da compacidade e a inexistência de axioma de finitude.

Segunda aula - o teorema de Löwenheim-Skolem e o chamado Paradoxo de Skolem.

Terceira aula - modelos não-standard da aritmética.
 

Referências:
Boolos, G.& Jeffrey,R.- Computability and Logic- third edition, Cambridge University Press, Cambridge, 1989
Shoenfield, J.R.- Mathematical Logic- Association for Symbolic Logic & A K
Peters, Natick, Massachusetts,2000( publicado originalmente pela Addison-Wesley em 1967)
Chang, C.C.& Keisler, H.J.- Model Theory- third edition, North-Holland Publishing Company, Amsterdam, 1990

Optativa 2011.1 - Metalógica

Olá para todos.
Em 2011.1 será oferecida na graduação uma disciplina optativa de lógica. O título será Tópicos de filosofia da linguagem: metalógica.
Não haverá, em 2011.1, o grupo de estudos de lógica.
Objetivo, ementa e avaliação da disciplina estão abaixo.

Serão disponibilizadas apostilas em português, como é feito nos cursos de Lógica 1 e 2. 
Abraços e boas férias.

Metalógica 

Objetivo: Apresentar alguns resultados básicos da metateoria da lógica clássica de primeira ordem. O curso é concebido para estudantes de filosofia e procura conciliar os aspectos técnicos com os aspectos filosóficos e históricos dos resultados estudados.

Ementa: Linguagens formalizadas: sintaxe e semântica. Provas indutivas. Sistemas axiomáticos. Teorema da dedução. Independência de axiomas. Provas de consistência. Teoremas da correção, completude e compacidade. Sistemas de dedução natural e cálculo de sequentes.

Avaliação: 100 pontos divididos da seguinte forma: 30 pontos: assiduidade e listas de exercícios; 30 pontos: trabalho escrito; 40 pontos: prova individual.

Bibliografia básica: Robbin, Mathematical Logic: A First Course; Hunter, G., Metalogic: An Introduction to the Metatheory of Standard First Order Logic; Troelstra et al. Basic Proof Theory. Mais indicações bibliográficas serão disponibilizadas durante o curso na página http://logicaetc.blogspot.com. 

E na filosofia?

Quanto aos créditos, infelizmente não lembro como isso veio parar no
meu computador. Informação sobre será bem-vinda.

Grupo de Lógica - 18/11

Abaixo, uma apostila com alguns exercícios sobre regras para quantificadores - sistemas G3i e G3c.

http://dl.dropbox.com/u/5959592/regras_qtfs.pdf

Veremos isso no encontro do grupo dia 18/11.

Abraços

Palestras com o Prof. Walter Carnielli

FACULDADE DE FILOSOFIA E CIÊNCIAS HUMANAS
Programa de Pós-Graduação em Filosofia
Linha de Pesquisa - Lógica e Filosofia da Ciência


Palestras com o Professor Walter Carnielli


Multimodalidades: lógica, computação e filosofia
Quarta-feira, 27/10/2010, 14h, sala 3048 FAFICH 

A ideia de necessidade, à qual se  opõe  o que é contingente,  é
antiga  no pensamento filosófico. A par da necessidade metafísica, os
lógicos  e filósofos se referem às  necessidade  lógica, física e ao
necessário a posteriori, às quais estão ligadas várias noções de
possibilidade. De que maneira  a lógica modal, vista como o estudo do
raciocínio que envolve o uso das expressões  'necessariamente' e
'possivelmente', trabalha com tudo isso? Existem modalidades
não-clássicas, ou as  noções de modalidade não as  admitem? Seria a
'consistência' uma noção modal?  E o que tem isso tudo a ver com os
mundos possíves? E com os mundos impossíveis? Pretendo introduzir  a
matemática das modalidades e das multimodalidades, incluindo ideias
básicas da  combinação de  lógicas, discutir alguns  de seus problemas
e ajudar a   compreender porque a  lógica modal ocupa hoje uma posição
tão privilegiada na  filosofia, na computação e na linguística.


Lógica, argumentação e pensamento crítico: um programa
Quinta-feira, 28/10/2010, 12h, sala 3048 FAFICH

Nos últimos 30 anos, o estudo da argumentação conheceu um grande
desenvolvimento e se transformou num campo de estudo independente e de
alto valor estratégico, mas  que é ainda  pouco difundido  no  Brasil.
Contudo, conhecer a estrutura íntima dos argumentos é fundamental para
o discurso filosófico, científico e político-social. Pretendo discutir
a proposta de um  programa introdutório  à atividade  de pensar
criticamente  com bases  rigorosas e com suporte na Lógica, embora
não-formal,  enfatizando  não somente a persuasão e a formulação de
bons argumentos mas a defesa contra ataques argumentativos.

Lógica Quântica, suas Vertentes Modais e a Incompletude

Quinta-feira, 28/10/2010, 16h45, sala 3060 ICEx

A palestra pretende  oferecer  uma  introdução gentil e convidativa  a
certas questões envolvendo  lógica e informação  quãntica. Mostro como

algumas classes de  lógicas  multi-modais com formas fracas de negação
são incompletáveis com respeito às semânticas de  Kripke. Argumento
que esta dificuldade,  além de seu interesse  filosófico intrínseco,
pode ser relevante  para a expressabilidade da informação quântica em
termos lógicos. Contudo, a incompletude não afetaria em princípio as
"semânticas modais de traduções possíveis"; considerando que tais
semânticas, tanto quanto as semânticas de Kripke, caracterizam lógicas
modais com vocação quântica, a adoção das semânticas modais de
traduções possíveis pode ser uma interessante alternativa. Discuto
outras abordagens e problemas ligados a esta questão.

Palestra - From Natural Deduction to Lambda Calculus

Palestra com o professor Alexis Saurin PPS/Paris-França

From Natural Deduction to Lambda Calculus

Quinta-feira, sala 4094, 18h

Grupo de Lógica - dia 30/09

Olá para todos.

No próximo encontro do grupo de lógica, que terá início às 17h no local de sempre, veremos os seguintes tópicos do livro da Negri:

Teorema 2.5.6 - sequentes não-demonstráveis na lógica intuicionista (em G3ip) - p.43

Independência dos conectivos na lógica intuicionista - p. 45

A definição de trace formula - p. 51

Teorema 3.1.4 - equivalência entre C e a conjunção das trace formulas de C - p. 51

Os capítulos correspondentes já foram disponibilizados.

Abraços

Regras inversíveis - G3ip

Abaixo, apostilas sobre equivalência entre G1ip e G3ip
http://dl.dropbox.com/u/5959592/eqvl_g1ip_g3ip.pdf
e sobre regras inversíveis em G3ip
http://dl.dropbox.com/u/5959592/regras_inver_G3ip.pdf
abraços

Algumas provas em G1

Olá para todos.
Abaixo, uma apostila com algumas provas em G1 (mais precisamente, G1ip, i.e. G1 para lógica proposicional intuicionista, que vimos no último encontro).
http://dl.dropbox.com/u/5959592/G1.pdf
Minha sugestão é que vocês peguem alguma lista de tautologias - do
Mortari por exemplo - e verifiquem com G1ip todas que valem
intuicionisticamente.
Abraços

Texto Kolmogorov e encontro da próxima quinta

Olá para todos.

Para quem estiver interessado, na próxima quinta-feira às 17h faremos um revisão do que já foi visto em sistemas axiomáticos e dedução natural. 

O horário das 18h fica mantido

Abaixo, um pdf do texto do Kolmogorov sobre o terceiro excluído.
http://dl.dropbox.com/u/5959592/kolmogorov_excluded_middle_heijnoort.pdf

Abraços

Material disponível e outros assuntos

Olá para todos.

No último encontro do grupo de lógica vimos como transformar provas em
dedução natural em provas em sistemas de Hilbert e vice-versa. Usamos
as apostilas abaixo
http://dl.dropbox.com/u/5959592/hilbert_prop.pdf
http://dl.dropbox.com/u/5959592/Hilbert_DN.pdf

Há também uma lista de exercícios no link
http://dl.dropbox.com/u/5959592/exercicios_H_DN.pdf

E no link
http://dl.dropbox.com/u/5959592/books/NEGRI_intro_1.pdf
está a introdução e o capítulo 1 da Negri e von Plato, From natural

deduction to sequent calculus.

Quem estiver com dúvidas e quiser fazer uma revisão sobre dedução
natural e sistemas axiomáticos podemos marcar um horário às 17h, antes
do grupo. Envie email para abilio.arf@gmail.com.
Mas o horário do grupo continua sendo 18h.

Abaixo, algumas leituras recomendadas para quem estiver interessado
nas motivações filosóficas e aspectos históricos das lógicas
intuicionista e minimal.

Um capítulo do livro da Maria da Paz, Traduções via teoria da Prova:
aplicações à lógica linear, 2002, EDUFRN
http://dl.dropbox.com/u/5959592/books/dapaz.pdf

Verbetes da Stanford sobre intuicionismo,
http://plato.stanford.edu/entries/logic-intuitionistic/
http://plato.stanford.edu/entries/intuitionistic-logic-development/
e teoria da prova
http://plato.stanford.edu/entries/proof-theory-development/

Vale a pena também ler o texto do Kolmogorov, On the principle of
excluded middle.  Está na coletânea do van Heijenoort, From Frege to
Gödel.

E abaixo
http://dl.dropbox.com/u/5959592/books/gentzen_logical_deduction.pdf
o texto do Gentzen, Investigations into logical deduction.

Abraços