Aulas Teóricas

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

(1) 21 Set 2004

Introdução. A Lógica como base do raciocínio. Tipos de raciocínio: dedutivo, abdutivo e indutivo e sua relação com a Lógica. A linguagem da 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. Proposições Atómicas. Constantes e sua interpretação. Símbolos predicativos, predicados, sua aridade e interpretação. Proposições atómicas. Símbolos Funcionais, funções e sua interpretação. 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) 24 Set 2004

A Lógica de Proposições Atómicas. Argumentação e demonstrações. Alguns exemplos que ilustram as características principais da argumentação. 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. Premissas, passos intermédios e conclusão. Justificações através de regras de inferência. Regras de inferência para o predicado da igualdade. A introdução da igualdade como formalização da propriedade reflexiva da igualdade. A eliminação da igualdade como formalização da propriedade de subsituição da igualdade. Verificação que as outras propriedades da igualdade.

(3) 8 Out 2004

Os Operadores Booleanos. Composição de proposições a partir de outras mais simples. Os 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) 12 Out 2004

A Lógica dos Operadores Booleanos. Estudo das noções de Necessidade, Possibilidade Inpossibilidade. Distinção entre essas noções ao nível lógico, tautológico ou em determinados contextos que determinam a interpretação de predicados específicos. Breve referência a lógicas modais e aos operadores de necessidade e possibilidade. Verificação que as noções de necessidade e possibilidade não são funcionais, já que impõe a análise de vários contextos. 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. Noções de equivalência de proposições ao nível lógico, tautológico e analógico em contextos específicos (ex. Mundo de Tarski).

(5) 15 Out 2004

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. Relação existente entre equivalência de proposições e consequência entre essas proposições. Demonstração da invalidade da consequência através de um contra-exemplo. 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) 19 Out 2004

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 absurdo e exemplos de aplicação em aritmética. O método de demonstração por casos e demonstrações informais de resultados da aritmética usando este método. Ilustração da combinação do raciocínio por absurdo e do raciocínio por casos.

(7) 22 Out 2004

Demonstrações Formais com Operadores Booleanos. 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. 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. Alguns exemplos de aplicaçã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.

(8) 26 Out 2004

Demonstrações Formais com Operadores Booleanos. Exemplos de aplicação do sistema Fitch para derivação de conclusões. Demonstração de verdades lógicas e tautológicas a partir de um conjunto vazio de premissas. Derivação das leis de de Morgan. Estratégias usadas na derivação de fórmulas. Raciocínio para trás para definir uma hipótese de derivação. Raciocínio por absurdo e sua utilização conjugada com a dupla negação. Utilização do raciocínio por casos. Erros frequentes em demonstrações no sistema Fitch, relacionados com a visibilidade (escopo) das fórmulas utilizadas. A possibilidade de utilizar demonstrações mais simples por introdução de tautologias e de fórmulas equivalentes.

(9) 29 Out 2004

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).

(10) 2 Nov 2003

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.

.

(11) 5 Nov 2004

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. Tradução de frases em língua natural para proposições da lógica de predicados. Correspondência entre a quantificação universal e a implicação e entre a quantificação existencial e a conjunção.

(12) 9 Nov 2004

A Lógica dos Quantificadores. Discussão da representação das formas aristotélicas. Implicações com implicante vazio e generalizações (inerentemente) vacuosas – equivalência formulação de conjuntos vazios. Símbolos funcionais em proposições quantificadas. Quantificação de objectos e não de propriedades. Distinção entre lógica de 1ª ordem e de ordens superiores. 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 intrepretação de quantificadores.

(13) 12 Nov 2004

Quantificação Múltipla. 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 anoção de consequência tautologica, logica ou meramente analógica. 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.

(14) 16 Nov 2004

Quantificação Múltipla. 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.

(15) 19 Nov 2004

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. A coerência e completude do sistema de Resolução na lógica proposicional.

(16) 23 Nov 2004

Resolução em Lógica de Predicados de 1ª Ordem. 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

(17) 26 Nov 2002

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.

(18) 30 Nov 2002

Métodos de Demonstração 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. A instanciação existencial como um método de atribuição de um “nome” ao objecto, que embora desconhecido, se sabe existir com uma determinada propriedade. Cuidados a ter para que o nome atribuido a esse objecto não permita a confusão com outros objectos já conhecidos. 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.

(19) 3 Dez 2004

Métodos de Demonstração com Quantificadores (cont.) 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. A noção de escolha arbitrária de objecto de uma classe e sua exemplificação com demonstrações no mundo de Tarski. 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.

(20) 7 Dez 2004

Métodos de Demonstração com Quantificadores (cont.) Comparação da Dedução Natural com a Resolução. Alguns exemplos tais como o paradoxo do barbeiro. A não observância de cuidados com os contextos/skolemização e a dedução, errada, de fórmulas com troca da ordem dos quantificadores universal e existencial. Introdução à axiomatização de um domínio. Axiomas como em regras universais. O exemplo do mundo de Tarski. Demonstrações de consequências analógicas através da explicitação dos axiomas do domínio. Exemplos com os axiomas da forma e do tamanho no mundo de Tarski.

(21) 10 Dez 2004

Quantificação Numérica. 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.

(22) 14 Dez 2004

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 geométricas e número de subconjuntos.