Aulas Teóricas

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

(1) 24 Set 2005

Introdução. A Lógica como base do raciocínio. Aplicações à Informática: programação em lógica, modelação e bases de dados (relacionais). Tipos de raciocínio: dedutivo, abdutivo e indutivo e sua relação com a Lógica. A Lógica de 1ª ordem e a linguagem natural. Limitações da Lógica de 1ª ordem: ausência de graus de incerteza ou probabilidade e conotações temporais. Linguagens de 1ª ordem. Símbolos predicativos e símbolos funcionais e sua aridade. Proposições Atómicas. Interpretação de constantes, funções e predicados A linguagem da aritmética como instância dos esquemas de Lógica de 1ª Ordem:

Apresentação da cadeira, objectivos e programa, bibliografia e métodos de avaliação, incluindo datas previstas dos testes. Discussão do método de trabalho a usar e os requisitos necessários para ter sucesso na cadeira.

(2) 7 Out 2005

A Lógica de Proposições Atómicas. Argumentação e demonstrações. Premissas e conclusão de um argumento. Validade e solidez de um argumento. Passos intermédios de uma demonstração formal e sua justificação baseada em regras de inferência. O predicado igualdade e suas propriedades primitivas (substituição e reflexividade) e derivadas (simetria e transitividade). Formalização de uma demonstração no sistema Fitch. Regras de inferência para o predicado da igualdade: introdução (reflexividade) e eliminação (subsituição). Derivação das outras propriedades da igualdade.

(3) 11 Out 2005

Os Operadores Booleanos. Composição de proposições tarvés dos operadores booleanos de negação, conjunção e disjunção. Sua semântica e carácter funcional (funções de verdade). Expressão das funções de verdade através de tabelas de verdade. Utilização de vários partículas para exprimir conjunções e disjunções em língua natural. Equivalência de expressões envolvendo expressões booleanas: dupla negação e as leis de de Morgan. Conjunções e disjunções com mais de duas componentes: comutatividade e associatividade. Ambiguidade na interpretação de expressões envolvendo vários operadores: regras de precedência entre operadores e utilização de parênteses.

(4) 14 Out 2005

A Lógica dos Operadores Booleanos. Estudo das noções de Verdade (Necessidade), Falsidade (Impossibilidade) e contingência (Possibilidade) de uma proposição. Níveis de avaliação destas noções: Tautológico, Lógico e Analógico (analítico). Validação das verdades e possibilidades tautológicas através de tabelas de verdade. Limitações a nível lógico devidas ao predicado de igualdade. Limitações em domínios específicos (exemplo: Mundo de Tarski).

(5) 18 Out 2005

A Lógica dos Operadores Booleanos. Noções de consequência entre proposições. Distinção do nível tautológico, lógico em contextos específicos (ex. Mundo de Tarski) da consequência. Verificação de consequência tautológica entre proposições através de tabelas de verdade. Demonstração da invalidade da consequência através de um contra-exemplo. Consequência e Equivalência. Utilização da dupla negação e das leis de de Morgan para eliminação de negações de disjunções e de conjunções. Forma nornal negativa. Obtenção das formas normais conjuntiva e disjuntiva. Transformação de uma na outra.

(6) 25 Out 2005

Métodos Naturais de Demonstração. Noção de Demonstração. Pequenos passos de demonstração facilmente justificáveis vs. grandes passos que permitem demonstrações mais concisas mas de compreensão e utilização mais problemática (ex. Aritmética). Métodos complexos utilizados em demonstrações informais. O método de demonstração por casos e demonstrações informais de resultados da aritmética usando este método. A formalização de um sistema de dedução natural. O sistema Fitch e as regras de introdução e eliminação dos operadores booleanos. As regras da conjunção e demonstração da comutatividade, associatividade e idempotência. As regras da disjunção disjunção e o raciocínio por casos. Distribuição da disjunção em relação à conjunção e desta em relação àquela. Erros frequentes em demonstrações no sistema Fitch, relacionados com a visibilidade (escopo) das fórmulas utilizadas.

(7) 28 Out 2004

Demonstrações Formais com Operadores Booleanos. O método de demonstração por absurdo e exemplos de aplicação em aritmética. Ilustração da combinação do raciocínio por absurdo e do raciocínio por casos.A dupla negação e eliminação da negação. Introdução da negação e o raciocínio por absurdo. Conveniência da introdução de um símbolo para representação da contradição. Regras de introdução e eliminação da contradição. A utilização de sub-demonstrações nas regras de introdução da negação e da eliminação da disjunção, e escopo de validade das proposições dentro de sub-demonstrações. Alguns exemplos de aplicação(derivação das leis de de Morgan) ilustrando as estratégias usadas na derivação de fórmulas. Raciocínio para trás e para a frente. Demonstração de tautologias, na ausência de premissas.

(8) 4 Nov 2005

Operadores Condicionais. Expressões em língua natural envolvendo a ideia de condições. Dificuldades na sua interpretação e verificação da sua eventual não funcionalidade. Operadores de verdade não funcionais. O operador de implicação como operador funcional e relação com a noção de argumentação. Dificuldades na sua utilização para tradução literal de proposições que envolvem intenções. O operador de dupla implicação e a sua relação com o estabelecimento de condições necessárias e suficientes. A redundância destes operadores face aos já existentes de negação, conjunção e disjunção. Completude destes operadores e obtenção de qualquer função nas formas normais conjuntiva e disjuntiva. Operadores completos (nand e nor).

(9) 8 Nov 2005

A Lógica dos operadores condicionais. Algumas equivalências entre proposições envolvendo condicionais. Contraposição e condições como disjunções. Dupla implicação e conjunção de implicações. Eliminação da implicação (modus ponens). Raciocínio hipotético: sua exemplificação em aritmética e formalização na introdução da implicação. Coerência e completude de um sistema formal e verificação da coerência de algumas das regras de inferência do sistema Fitch. As regras de introdução e eliminação de operadores condicionais para demonstrações de consequências tautológicas. Exemplos de demonstrações envolvendo raciocínio condicional, por casos e por absurdo. Demonstração de algumas tautologias a partir de um conjunto nulo de premissas.

.

(10) 11 Nov 2005

Introdução à Quantificação. Insuficiência do poder de expressão da lógica proposicional. Necessidade de representação dos nomes comuns e sua analogia com conjuntos. Fórmulas bem formadas (FBFs) e sua definição recursiva. Ausência de significado para FBFs com variáveis livres. Vários tipos de quantificação e os tipos principais: universal e existencial. Definição da semântica de quantificadores a partir da noção de satisfação de FBFs. Discussão da representação das formas aristotélicas. Símbolos funcionais em proposições quantificadas.

(11) 15 Nov 2004

A Lógica dos Quantificadores. A importância do tipo de quantificadores para a validade dos argumentos. Exemplos. Generalização de conceitos do lógica proposicional para a lógica de predicados. Proposições necessárias tautológicamente como proposições de que se demonstra a verdade sem apelar à interpretação de quaisquer predicados nem do interpretação de quantificadores. Algoritmo de substituição de proposições quantificadas para análise das tautologias. Diferenças em relação às proposições necessárias logicamente (em que se intrepretam a igualdade e os quantificadores) e analogicamente (em que se interpretam os predicados de um domínio). Idênticas definições para a noção de consequência tautologica, logica ou meramente analógica. Implicações com implicante vazio e generalizações (inerentemente) vacuosas – equivalência formulação de conjuntos vazios.

(12) 18 Nov 2005

Quantificação Múltipla. Extensão das formas Aristoteleanas para frases com múltiplos quantificadores. Manutenção dos padrões básicos (quantificador universal/implicação e quantificador existencial/conjunção). Referência ao mesmo objecto por duas variáveis com nomes diferentes. Método passo a passo para traduzir frases em língua natural para frases da Lógica de 1ª ordem e utilização de paráfrases das frases originais. Exemplos. A quantificação existencial e os símbolos funcionais - unicidade. Equivalência entre uma proposição com vários quantificadores e a sua forma Prenex. Algoritmo para obtenção da forma Prenex: eliminação da implicação, “interiorização” das negações, utilização da quantificação vazia. Exemplos de aplicação e verificação de casos em que a natureza dos quantificadores muda na forma Prenex – leitura da fórmula original e da forma Prenex e verificação da sua equivalência.

(13) 22 Nov 2005

Resolução em Lógica Proposicional. Forma Clausal de uma proposição. Cláusulas, literais e proposições atómicas (átomos). Sua obtenção a partir da CNF (Formal Normal Conjuntiva). O problema da satisfação de um conjunto de claúsulas. Método das tabelas de verdade. Complexidade Exponencial no pior caso. O caso particular das cláusulas de Horn. A regra de inferência da resolução. Sistemas de prova baseados na resolução. Demonstrações vistas como refutações (derivação da cláusula vazia). Alguns exemplos.

(14) 25 Nov 2005

Resolução em Lógica de Predicados de 1ª Ordem. A coerência e completude do sistema de Resolução na lógica proposicional. Conversão na forma clausal de fórmulas quantificadas. Passagem para a forma Prenex. Passagem para a forma CNF da matriz. A quantificação existencial. Constantes e funções de Skolem. Não equivalência da Skolemização e sua utilização num processo de refutação. Separação de cláusulas. Eliminação dos quantificadores universais. A regra de inferência da resolução para a Lógica de Predicados.

(15) 29 Nov 2005

Resolução em Lógica de Predicados de 1ª Ordem. Unificação. A unificação de termos em casos simples. Substituições e sua utilização em deduções. Substituições mais gerais. Unificação e Substituições. Limitações (“occurs check”). Negação da conclusão e sua passagem para a forma clausal. Derivação da claúsula vazia. Exemplos de aplicação. O paradoxo do barbeiro. Breve introdução à sua “história” e relação com a semi-decidibilidade da Lógica de 1ª ordem e o problema da paragem (teoria da computação). Sua demonstração por Resolução. Factorização de Cláusulas.

(16) 2 Dez 2005

Dedução Natural com Quantificadores. A instanciação universal e sua introdução em sistemas de dedução natural (Fitch) através da regra de eliminação do quantificador universal. Exemplo de aplicação. A generalização existencial e a introdução do quantificador existencial. Exemplificação com um argumento do mundo de Tarski. Cuidados a ter na escolha de nomes arbitrários. Introdução da instanciação existencial no Fitch como regra de eliminação do quantificador existencial. Comparação com a Skolemização em Resolução. A generalização universal como método de inferência para atribuir aos objectos de uma classe uma propriedade válida para um objecto arbitrário nessa classe. Cuidados a ter na escolha de nomes arbitrários. Introdução da generalização universal no Fitch como regra de introdução do quantificador universal. Exemplo de deduções com fórmulas em que aparecem vários quantificadores, de natureza diferente.

(17) 6 Dez 2005

Quantificação Numérica. Demonstrações de consequências analógicas através da explicitação dos axiomas do domínio. Exemplos com os axiomas relativos à posição de objectos (à frente, atrás e na mesma linha) no mundo de Tarski. Outros tipos de quantificação para além da existencial e universal (determinantes tais como “quase todos”, “a maioria”, “poucos”) e dificuldade (impossibilidade) em a exprimir através dos quantificadores existencial e universal. A quantificação numérica através da utilização de ambos os quantificadores e do predicado de igualdade. Quantificação de um número mínimo, máximo e exacto de n objectos. Impraticabilidade de utilização directa desta formalização e conveniência do desenvolvimento de sistemas aritméticos e algébricos.

(18) 13 Dez 2005

Indução Matemática. Conjuntos definidos indutivamente (recursivamente). Cláusulas de base, indutivas e de exclusão. Alguns tipos de expressões regulares (somas) com números naturais e operadores. Os números naturais. Demonstrações indutivas. Verificação pelos elementos de base das estruturas. Verificação indutiva da propriedade, através da demonstração de que a validade para um elemento genérico implica a validade para os elementos “seguintes. O caso importante mas não exclusivo dos números naturais. Alguns exemplos de demonstrações indutivas, nomeadamente a soma de séries aritméticas e geométricas..

(19) 16 Dez 2004

Programação em Lógica. A linguagem Prolog. Exemplos (famílias, listas).