FERNANDO FERREIRA FERNANDO FERREIRA As aulas teóricas e, também, teórico-práticas começam logo na primeira semana lectiva do segundo semestre. Portanto, a primeira aula teórica é no dia 18 de Fevereiro.
Matéria:
Introdução às linguagens da lógica de primeira ordem com igualdade, desde o cálculo proposicional até ao cálculo de predicados. Em cada etapa estudam-se os aspectos sintácticos e semânticos e os métodos de demonstração associados ao fragmento em causa. Estudam-se a noção semântica de consequência lógica e uma noção sintáctica de dedução (sistema de dedução formal de Fitch).
Cálculo proposicional: constantes, símbolos relacionais (predicados),
símbolos funcionais, termos, igualdade, sentenças
atómicas; exemplos: as linguagens da teoria de conjuntos e da
aritmética; métodos de demonstração;
conectivos lógicos, sentenças, equivalência,
satisfação e tautologias, deduções formais,
formas normais conjuntivas e disjuntivas. Discussão informal da
completude proposicional do cálculo de dedução
formal apresentado. Sentenças de Horn e o algoritmo (eficiente)
de satisfação para sentenças de Horn. Método da resolução.
Cálculo de predicados: variáveis, fórmulas atómicas, quantificadores, fórmulas e sentenças, semântica; uso de quantificadores múltiplos, equivalência lógica e deduções formais envolvendo quantificadores; forma prenexa normal. Existência e unicidade. Acerca do cálculo de dedução formal estudado.
Páginas antigas da disciplina: 2005/06, 2006/07 e 2007/08.
Livro recomendado: “Language, Proof and Logic” de Jon Barwise e John Etchemendy. As aulas vão seguir este livro do capítulo 1 ao capítulo 14. Incluem-se também as secções 1, 3 e 4 do capítulo 17 (dadas intercaladamente entre o capítulo 8 e o capítulo 9).
Pode obter informações sobre este livro aqui. O livro encontra-se à venda na livraria do campus e está disponível na Biblioteca da Universidade. Pode aceder ao Catálogo Colectivo das Bibliotecas da Universidade de Lisboa aqui.
As folhas de exercícios encontram-se disponíveis no serviço de reprografias REPRO2000 do edifício C4 até Sábado, dia 14 de Fevereiro. A partir de 16 de Fevereiro encontram-se na REPRO2000 sito no Piso 1 do Edifício C6, Sala 6.1.38 (2ª a 6ª feira, 10h-13h e 15h-18h). Estes enunciados devem ser levados para as aulas teórico-práticas.
Os mundos que constam dos exercícios podem ser descarregados aqui (mas também se encontram nas folhas de exercícios): Mundo de Bolzano, Mundo de Boole, Mundo de Carroll, Mundo de Leibniz, Mundo de Lestrade, Mundo de Maigret, Mundo de Montague, Mundo de Peano, Mundo de Peirce, Mundo de Ramsey, Mundo de Reichenbach, Mundo de Sherlock, Mundo de Skolem e Mundo de Wittgenstein.
Neste ficheiro pode encontrar uma compilação das regras do sistema de dedução natural de Fitch (agradecimentos à Professora Isabel Ferreirim).
Podem descarregar aqui umas notas da Professora Isabel Ferreirim sobre o algoritmo de Horn.
O enunciado do teste intermédio assim como dos mini-testes estão aqui: mini-teste 1, mini-teste 2, mini-teste 3, mini-teste 4, teste intermédio (com mundos A, B, C).
Pode encontrar neste sítio (com este ficheiro anexo) a correcção do teste intermédio.
Apontadores para temas falados na aula teórica, de índole complementar e cultural.
Aristóteles foi o inventor da lógica, há cerca de vinte e quatro séculos. A sua lógica ficou conhecida por lógica silogística. Fundamentalmente, a lógica silogística está correcta (se descontarmos o problema técnico/interpretativo da "importação existencial"). Porém, trata-se dum sub-sistema muito restrito da lógica de primeira-ordem. Esta última generaliza a silogística aristoteliana e, portanto, veio claramente superá-la. Se Aristóteles voltasse a viver nos dias de hoje, certamente que se maravilharia com este avanço. Nos tempos medievais, criou-se uma mnemónica para ajudar os alunos (mais fracos?) a memorizar (em vez de compreender?) os silogismos. Essa mnemónica foi apurada e amplamente divulgada pelo lógico (e médico) português Pedro Hispano (que foi o único Papa português, João XXI). Pedro Hispano é também o autor do célebre quadrado da oposição da lógica silogística.
Gottlob Frege foi o criador do cálculo de predicados com a quantificação e, ao mesmo tempo, foi proponente do logicismo (redução da matemática à lógica). Porém, o sistema desenvolvido por Frege para reduzir a matemática à lógica enfermava dum paradoxo (paradoxo de Russell). Bertrand Russell procurou, no entanto, corrigir e salvar o programa logicista da redução da matemática à lógica. A execução do projecto revelou dificuldades insuperáveis, tornadas ainda mais agudas pelos teoremas da incompletude de Gödel de 1931. A filosofia da matemática é um assunto fascinante e, como curiosidade, menciono um escrito do Papa Bento XVI sobre a relação entre fé e razão e que, em dado momento, menciona esta temática (este escrito revela, além disso, um peculiar sentido de humor do Papa - veja-se a introdução; o escrito é, infelizmente, mais conhecido por ter dado origem a um pequeno atrito inter-religioso).
RSA é um sistema criptográfico de chave pública concebido no final dos anos setenta por Ron Rivest, Adi Shamir e Leonard Adleman. O problema P=NP foi formulado em 1971 e pode ser considerado o problema teórico mais importante da Ciência da Computação: com efeito, se ele tiver uma resposta positiva, os sistemas de chave pública seriam muito provavelmente inseguros. O Instituto Clay de Matemática dá um prémio de um milhão de dólares americanos para quem o conseguir resolver.
Fernando Ferreira:
Gabinete 6.2.8 do edifício C6 da Faculdade de Ciências da Universidade de Lisboa. Telefone: 217500294. Extensão interna 26208. Endereço de correio electrónico: ferferr@cii.fc.ul.pt. Quando me contactar por correio electrónico escreva “LPO2009” (não inclua as aspas) no campo do subject.
Horário de atendimento do professor de aula teórica: segunda-feira, 14h30m - 15h30m. Gabinete C6.2.08.
Aula teórica: quarta-feira das 10h:30m às 11h30m na sala 3.12.14; sexta-feira das 9h30m às 10h30m na sala 3.2.14.
As aulas teórico-práticas são as seguintes (ignorar outras informações):
Aulas da turma TP2 1: quinta-feira, 10h30m-12h, 6.2.46; sexta-feira, 8h:9h30m, 3.1.11.
Aulas da turma TP2 2: quarta-feira, 9h-10h30m, 3.1.9; quinta-feira, 12h:13h30m, 8.2.19.
Aulas da turma TP2 3: segunda-feira, 8h-9h30m, 6.2.50; terça-feira, 9h:10h30m, 8.2.13.
Aulas da turma TP2 4: segunda-feira, 12h30m-14h, 1.3.33A; quinta-feira, 9h:10h30m, 6.2.49.
Aulas da turma TP2 5: terça-feira, 9h-10h30m, 8.2.11; quarta-feira, 12h:13h30m, 6.2.46.
Aulas da turma TP2 6: terça-feira, 10h30m-12h, 6.2.46; sexta-feira, 8h:9h30m, 3.1.10.
Aulas da turma TP2 7: terça-feira, 10h30m-12h, 1.4.13; quarta-feira, 12h:13h30m, 6.2.47.
A avaliação é cumulativa e constituída por três componentes. Quatro mini-testes, um teste intermédio e um exame final.
Os quatro mini-testes decorrem nas aulas TP das semanas 3 (9 a 13 de Março), 6 (30 de Março a 3 de Abril), 11 (11 a 15 de Maio) e 13 (25 a 29 de Maio). Têm a duração de 15m. Cada mini-teste vale 0,5 valores mas a nota mais baixa dos quatro mini-testes é descartada. Por isso, esta componente da avaliação vale 1,5 valores.
O teste intermédio decorre na semana 8, mais precisamente no dia 22 de Abril. Este teste tem a duração de 50m e vale 2,5 valores.
O exame final escrito vale 16 valores e decorre na época de exames. A avaliação contínua (presenças, etc) pode desempenhar um papel importante em casos de fronteira entre a aprovação e a reprovação. O Professor reserva-se o direito de efectuar exame oral a um aluno se o considerar necessário.
Note-se que não há nota mínima nos testes ou mini-testes para o aluno se apresentar a exame final. Porém, o exame final vale apenas 16 valores.
Caso excepcional: Os alunos trabalhadores-estudantes e casos similares devidamente registados na secretaria podem optar por fazer apenas o exame final, caso em que este vale 20 valores. Desde que um aluno nesta situação opte por fazer qualquer mini-teste ou o teste intermédio, automaticamente prescinde desta opção.
AULA 1 [18/2] Apresentação. Bibliografia e material de apoio (folhas de exercícios). Descrição da avaliação. Considerações gerais sobre a matéria. Sintaxe vs semântica.
AULA 2 [20/2] Linguagens da lógica de primeira-ordem: constantes (ou nomes), símbolos predicativos (ou relacionais) e símbolos funcionais. Aridade. Termos e o seu papel semântico (referir). Sentenças atómicas e o seu papel semântico (serem verdadeiras ou falsas).
AULA 3 [4/3] Exemplos de linguagens da LPO. Primeira abordagem à noção de consequência lógica. Argumentos e contra-exemplos.
AULA 4 [6/3] Introdução ao sistema de dedução formal de Fitch. Regras de introdução e eliminação da igualdade. Regra de reiteração. Exemplos. Regras derivadas. Os conectivos vero-funcionais de negação, conjunção e disjunção.
AULA 5 [11/3] Equivalência lógica (sinal metalinguístico de equivalência lógica). Leis da dupla negação e leis de De Morgan. Tabelas de verdade. Tautologias e sentenças tt-satisfazíveis. O problema P vs NP. Tautologias e verdades lógicas (e necessidades do mundo de blocos): toda a tautologia é verdade lógica (mas não vice-versa).
AULA 6 [13/3] Uma sentença não é tt-satisfazível se, e somente se, a sua negação é uma tautologia. Equivalência tautológica. Consequência tautológica. Exemplos. Forma normal negativa (FNN). Leis associativas, comutativas, da idempotência, da absorção. Leis distributivas.
AULA 7 [18/3] Formas normais conjuntivas e disjuntivas (FNC e FND). Exemplos. Demonstrações informais. Como concluir uma conjunção e como concluir uma disjunção. Como usar uma conjunção. Método da demonstração por casos (ou: como usar uma disjunção). Exemplos.
AULA 8 [20/3] O método da demonstração por contradição (ou: como concluir uma negação). Exemplos. O exemplo da irracionalidade de raíz de 2. Premissas inconsistentes (ou contraditórias). Ex falso quodlibet.
AULA 9 [25/3] Regras de dedução formal do sistema de Fitch: introdução da conjunção e eliminação da conjunção; introdução da disjunção e eliminação da disjunção (método da demonstração por casos). Exemplos de deduções.
AULA 10 [27/3] O símbolo da contradição. Regras de dedução formal do sistema de Fitch: introdução da contradição e eliminação da contradição (ex falso quodlibet); introdução da negação (método da contradição) e eliminação da negação. Exemplos de deduções.
AULA 11 [1/4] Esclarecimento sobre a regra “ex falso quodlibet”. A noção de argumento “sound” (adequado): argumento logicamente válido em que as premissas são verdadeiras. Exemplos de deduções formais e informais.
AULA 12 [3/4] Resolução do mini-teste desta semana. Novo exemplo de uma dedução formal. Comentários. O conectivo da implicação (condicional). Antecedentes e consequentes, condições necessárias e condições suficientes. Locuções condicionais em português. Relação entre a consequência lógica e a implicação. Acervo de equivalências lógicas básicas com a implicação.
AULA 13 [15/4] O conectivo da equivalência (bicondicional). Relação entre a equivalência lógica e o bicondicional. Os conectivos da negação, conjunção e disjunção formam um conjunto de conectivos vero-funcionalmente completo (i.e., toda a função de verdade se pode exprimir por uma fórmula construída a partir destes três conectivos). O símbolo de Sheffer.
AULA 14 [17/4] Demonstrações formais e informais para o condicional e o bicondicional. Modus Ponens. Método da demonstração condicional. Exemplos. As regras formais da introdução e eliminação do condicional.
AULA 15 [22/4] Conclusão da aula anterior. Menção da correcção e completude das regras do cálculo proposicional do sistema de Fitch.
AULA 16 [24/4] Dedução formal da lei do terceiro excluído. Menção da lógica intuicionista (que não aceita a regra da eliminação da negação). Sentenças de Horn.
AULA 17 [29/4] Forma implicativa das sentenças de Horn. O algoritmo da satisfazibilidade de Horn. Exemplos.
AULA 18 [6/5] Novo exemplo do funcionamento do algoritmo de Horn (aplicado a decidir se certas cláusulas de Horn implicam um literal). Introdução à quantificação universal e existencial. Exemplos.
AULA 19 [8/5] Axiomas. As quatro formas aristotélicas. Descrição do que é uma linguagem da lógica de primeira-ordem com igualdade: termos e fórmulas. Variáveis livres e variáveis mudas. As sentenças são as fórmulas sem variáveis livres.
AULA 20 [13/5] Equivalências lógicas básicas da quantificação: leis de De Morgan para os quantificadores, leis (e falácias) associadas a conjunções e disjunções de quantificações, quantificações vazias, mudança da variável muda.
AULA 21 [15/5] Exemplos de traduções. Notas sobre quantificações múltiplas: a ordem dos quantificadores. Introdução à forma prenexa.
AULA 22 [20/5] Forma prenexa. Toda a fórmula da linguagem da LPO é logicamente equivalente a uma fórmula em forma prenexa. Exemplos vários. Forma proposicional duma fórmula da linguagem da LPO.
AULA 23 [22/5] As noções matematicamente rigorosas de tautologia (resp., consequência tautológica, equivalência tautológica) e validade FO (resp., consequência FO, equivalência FO). Comparação com a noção informal de verdade lógica (resp., consequência lógica, equivalência lógica). Argumentos informais: instanciação universal (eliminação da quantificação universal) e generalização existencial (introdução da quantificação existencial). Exemplo.
AULA 24 [27/5] Como usar uma premissa existencial? O método de introdução de nomes (novos) que testemunham a asserção existencial. Exemplos. Introdução ao método da demonstração condicional geral.
AULA 25 [29/5] Continuação da discussão do método da demonstração condicional geral. Exemplos. Breve acervo dos métodos dedutivos que envolvem quantificadores. Regras formais de dedução (sistema de Fitch) para os quantificadores: A-Elim, A-Intro (e GenCond), E-Elim e E-Intro.
AULA 26 [3/6] Exemplos de deduções formais envolvendo sentenças com quantificadores. Esclarecimentos.
AULA 27 [5/6] Exemplos de traduções para a linguagem da LPO. O paradoxo de Russell e um exemplo duma dedução formal associada. Quantificações numéricas (com ênfase na existência e unicidade). Nota breve sobre a completude do sistema dedutivo de Fitch. Por que razão a disciplina se chama Lógica de Primeira-ordem?