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

23 24 25 26 27 28 29 30 31 32

(1) 1 Out 2001

Introdução. A importância da Lógica como base do raciocínio. Vários tipos de raciocínio: dedutivo, abdutivo e indutivo e sua relação com a Lógica. Relação entre a linguagem da Lógica de 1ª ordem e a linguagem natural. Limitações da Lógica de 1ª ordem para representar as proposições em língua natural: ausência de graus de incerteza ou probabilidade.

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

(2) 2 Out 2001

Proposições Atómicas. Constantes e sua interpretação. Símbolos predicativos, predicados e sua interpretação. Aridade dos predicados. Proposições atómicas. Símbolos Funcionais, funções e sua interpretação. Limitações do poder de expressão da Lógica de 1ª ordem por comparação com as proposições em língua natural: ausência de graus de incerteza ou probabilidade. A Lógica de 1ª Ordem como um esquema de linguagens de 1ª ordem. Contraste com lógicas de ordem superiores. Exemplos de instâncias da Lógica de 1ª Ordem. A linguagem de 1ª ordem da teoria de conjuntos. A linguagem de 1ª ordem da aritmética.

(3) 4 Out 2001

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. Argumentação informal e formal. Passos intermédios de uma demonstração formal e sua justificação baseada em regras de inferência. A dependência existente entre regras de inferência e riqueza da linguagem utilizada. O prdicado igualdade como predicado comum a todas as linguagens e sua interpretação rigorosa. Propriedades primitivas do predicado de igualdade: substituição e reflexividade. Propriedades derivadas: simetria e transitividade.

(4) 8 Out 2001

A Lógica de Proposições Atómicas. Formalização de uma demonstração no sistema Fitch. Numeração das proposições e distinção entre premissas e conclusões. Passos intermédios e conclusão final. Justificação dos passos intermédios e da conclusão final através de regras de inferência. Regras de inferência definidas 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 (simetria e transitividade) se podem demonstrar utilizando as regras de introdução e eliminação da igualdade. Verificação das limitações deste sistema, nomeadamente por não permitir incorporar a interpretação de outros predicados que não a igualdade. Exemplos do mundo de Tarski: impossibilidade de utilizar a simetria de predicados como SameRow.

(5) 9 Out 2001

Os Operadores Booleanos. Composição de proposições compostas de outras mais simples. Os operadores booleanos de negação, conjunção e disjunção e sua correspondência em lingua natural. Semântica dos operadores e verificação do seu carácter funcional (funções de verdade). Expressão das funções de verdade através de tabelas de verdade. Interpretação de proposições compostas através do “jogo da verdade” (Henkin-Hintikka). Regras do jogo para os diferentes operadores. Dificuldade na tradução literal de expressões em língua natural. Utilização de vários partículas para exprimir conjunções e disjunções. Facilidades sintáticas em língua natural sem correspondência em lógica proposicioanl (distribuição do sujeito por vários predicados e vice-versa). Ambiguidade nas disjunções inclusivas e exclusivas e desambiguação através do contexto. Incompleto poder de expressão das proposições em lógica proposicional para representar intenções e expectativas.

(6) 11 Out 2001

Os Operadores Booleanos. Equivalência de expressões envolvendo expressões booleanas. Exemplificação com a dupla negação e as leis de de Morgan. Verificação informal da validade destas equivalências. Con junções e disjunções com mais de duas componentes. Verificação informal das propriedades de comutatividade e de associatividade. Ambiguidade na interpretação de expressões envolvendo vários operadores e regras de precedência entre operadores. A utilização de parênteses para eliminar as ambiguidades. Alternativas à notação infixa. A notação polaca (prefixa) e a notação sufixa, e a não necessidade de parênteses nestas notações..

(7) 15 Out 2001

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. Verificação das características de necessidade e possibilidade tautológicas de proposições através de tabelas de verdade. Constatação que essas características ao nível lógico e para certos domínios não podem ser verificadas simplisticamente através de tabelas de verdade através de exemplos envolvendo o predicado de igualdade e certos predicados do mundo de Tarski. Noções de equivalência de proposições ao nível lógico, tautológico e em contextos específicos (ex. Mundo de Tarski).

(8) 16 Out 2001

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 da noçã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. Formas equivalentes tautologicamente entre proposições envolvendo operadores booleanos. Demonstração da invalidade da consequência através de um contra-exemplo. Leitura deste contraexemplo em tabelas de verdade. 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. Utilização das propriedades de comutatividade, associatividade e idempotência para obtenção das formas normais conjuntiva e disjuntiva. Transformação de uma na outra.

(9) 18 Out 2001

Métodos de Demonstração em Lógica Booleana. A noção de demonstração como ums sequência de passos de demonstração suportados numa justificação. Equilíbrio entre a necessidade de pequenos passos facilmente justificáveis e grandes passos que permitem demonstrações mais concisas mas de compreensão e utilização mais problemática. Demonstrações formais e informais. Contraste entre estes estilos de demonstração na demonstração de teoremas da aritmética. Métodos complexos utilizados em demonstrações informais. O método de demonstração por absurdo. Introdução das hipóteses (absurdas) e obtenção de uma contradição para concluir a negação dessas hipóteses Exemplos de aplicação: a) O conjunto de números primos não é limitado; b) O número Ö2 é irracional..

(10) 22 Out 2001

Métodos de Demonstração em Lógica Booleana. O método de demonstração por casos. A obtenção da mesma conclusão através de todos os casos possíveis como justificação da validade da argumentação. Alguns exemplos de demonstrações informais de resultados da aritmética usando este método. Demonstração da existência de irracioanais, b e c, tais que b^c é racional. Verificação que apesar do caracter existencial do teorema a demonstração não obtém nenhum exemplo. Demostração que se n² é divisível por 3, também n é divisível por 3. Ilustração do estabelecimento e demeonstração de lemas. Análise de casos mais complexos: Se a soma de dois números é ímpar o seu produto é par. Ilustração da combinação do raciocínio por abusrdo e do raciocínio por casos.

(11) 23 Out 2001

Demonstrações Formais com Operadores Booleanos. A formalização de um sistema de dedução natural cujas regras de inferência sejam análogas às utilizadas no raciocínio informal. O sistema Fitch e as regras de inferência de introdução e eliminação para os diferentes operadores booleanos. As regras de introdução e eliminação da conjunção. Sua utilização para demonstração das propriedades de comutatividade, associatividade e idempotência da conjunção. A regra de introdução da disjunção. O carácter arbitrário dos disjuntos que são acrescentados e a sua determinação pelo contexto. Exemplo: A disjunção de duas proposições como consequência da sua conjunção. A regra de eliminação da disjunção e a sua analogia com o raciocínio por casos. Utilizção das regras da conjunção e da disjunção na demonstração da validade da distribuição da disjunção em relação à conjunção.

(12) 25 Out 2001

Demonstrações Formais com Operadores Booleanos. A dupla negação como base da regra de eliminação da negação. Introdução da negação e a sua analogia com 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. O caracter redundante destas regras e sua demonstração a aprtir das já existentes. Alguns exemplos de aplicação das regras da negação. Leis de de Morgan. 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. Estratégias de demonstração: raciocínio para trás e estabelecimento de conclusões intermédias. Importância da certificação da sua validade. Demonstração de verdades lógicas e tautológicas a partir de um conjunto vazio de premissas.

(13) 29 Out 2001

Operadores Condicionais. Exemplificação de várias expressões em língua natural envolvendo a ideia de condições. Dificuldades na interpretação de algumas dessas expressões e verificação que a semântica de algumas expressões compostas não pode ser avaliada pela verdade das componentes. Operadores de verdade não funcionais. Ultrapassagem dessas dificuldades pelo estabelecimento do operador de implicação como função de verdade, e vantagens desta formulação que incorpora 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).

(14) 30 Out 2001

A Lógica dos operadores condicionais. Algumas equivalências entre proposições envolvendo condicionais. Implicação e Contraposição. Implicação como disjunção e negação de conjunção. Dupla implicação e conjunção de implicações. Dupla implicação e equivalência (disjunção de iguais). Utilização das equivalências como ajuda em demonstrações informais mas a necessidade de utilização de regras de inferência em demonstrações formais. Regra da eliminação da implicação (modus ponens). Raciocínio hipotético: sua exeplificação numa demonstração informal de um teorema da aritmética e sua formalização na regra de introdução da implicação. Utilização das regras de inferência da implicação para demonstração de equivalência entre proposições envolvendo a implicação e a disjunção.

(15) 5 Nov 2001

A Lógica dos operadores condicionais. Regras de inferência para a dupla implicação (equivalência) e sua correspondência Às regras da implicação em ambos os sentidos. Utilização desta analogia e da propriedade transitiva da implicação (silogismo hipotético) para verificação se podem demonstrar apenas algumas implicações para demonstrar toda uma cadeia de equivalências. Demonstração da equivalência ente o operador de dupla implicação e as sua definições em termos de conjunção de disjunções. Comparação das proposições que são consequência lógica de um conjunto de premissas e as que se podem deduzir através de um sistema formal como o Fitch. Noções de coerência e completude de um sistema formal e verificação da coerência de algumas das regras de inferência do sistema Fitch.

.

(16) 6 Nov 2001

A Lógica dos operadores condicionais. Aplicação das regras de inferência 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. Ilustração da técnica de obtenção de uma proposição não negada por absurdo, através da obtenção da sua dupla negação. Exemplificação de várias estratégias de obtenção de demonstrações, através do raciocínio para trás: montagem de uma demonstração a partir das fórmulas que se pretendem obter e preenchimento posterior dos passos intermédios. Verificação da validade das proposições intermédias e utilização das capacidades dedutivas do Fitch (dedução das consequências tautológicas) como auxiliar de validação das proposições intermédias. a disjunção. Demonstração de algumas tautologias a partir de um conjunto nulo de premissas.

(17) 8 Nov 2001

Introdução à Quantificação. Verificação que uma parte muito significativa do raciocínio lógico, nomeadamente silogismos, não se pode representar e formalizar na lógica proposicional. Necessidade de representação dos nomes comuns e sua analogia com conjuntos. Referências a elementos arbitrários desses conjuntos e etensão de proposições para o caso da utilização de variáveis nos predicados. Fórmulas bem formadas (FBFs) e sua definição recursiva. Ausência de significado para FBFs com variáveis livres e necessidade da sua quantificação. Vários tipos de quantificação e os tipos principais: universal e existencial. Extensão da definição de FBFs para os quantificadores. Semântica de quantificadores e constatação que ela não pode ser obtida através da semântica dos componentes (que não têm significado). Definição da semântica a partir da noção de satisfação de FBFs com variável livre por objectos do domínio.

(18) 12 Nov 2001

Introdução à Quantificação. Tradução de frases em língua natural para proposições da lógica de predicados. Convenção de utilização de um universo de discurso limitado para permitir que a quantificação apenas se refira a objectos nesse contexto. Correspondência entre a quantificação universal e a implicação e entre a quantificação existencial e a conjunção. Discussão da representação das formas aristotélicas A, E, I e O (todo o P é Q, algum P é Q, nenhum P é Q, algum P é não Q). Correspondência entre predicados e conjuntos e antre as formas aristotélicas e as noções de inclusão de conjuntos, interseção não nula de conjuntos, disjunção exclusiva de conjuntos e diferença de conjuntos. Implicações com implicante vazio e generalizações (inerentemente) vacuosas – equivalência formulação de conjuntos vazios. Símbolos funcionais em proposições quantificadas

(19) 13 Nov 2001

A Lógica dos Quantificadores. 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. 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.

(20) 15 Nov 2001

A Lógica dos Quantificadores. Análise da equivalência tautológica através do algoritmo de substituição de proposições quantificadas. Verificação que um grande númeo de equivalências é lógica e não tautológica. Interpretação dos quantificadores e generalização da verificação de equivalências para fórmulas bem formadas com variáveis livres através da noção de satisfação. Generalização das leis de de Morgan para a lógica de predicados. Correspondência entre as quantificações universal e existencial e as operações booleanas de conjunção e disjunção, respectivamente. Outras equivalências da lógica de predicados envolvendo quantificadores: conjunção e disjunção de fórmulas quantificadas, quantificação nula e substituição de variáveis ligadas.

(21) 19 Nov 2001

Quantificadores Múltiplos. Extensão das formas Aristoteleanas para frases com múltiplos quantificadores. Substituição de um predicado P(x) por uma expressão quantificada, mas mantendo livre a variável x. Exemplos de ilustração e proposições derivadas das quatro formas Aristoteleanas básicas através da substituição de predicados por expressões quantificadas. Verificação que os padrões básicos das formas aristoteleans se mantêm (quantificador universal associado à implicação e quantificador existencial associado à conjunção). Chamada de atenção para o facto de duas variáveis com nomes diferentes poderem referir-se ao mesmo objecto. Método passo a passo para traduzir frases em língua natural para frases da Lógica de 1ª ordem. Exemplos.

(22) 20 Nov 2001

Quantificadores Múltiplos. Traduções para a Lógica de 1ª Ordem através de paráfrases das frases originais. Exemplos. Ambiguidade existente na língua natural e formas fortes e fracas de tradução. Desambiguação dependente do contexto. Possibilidade de substituição de quantificação existencial por símbolos funcionais. Necessário garantir a 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 para colocação de todos os quantificadores à esquerda da fórmula. 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.

(23) 21 Nov 2001

Métodos de Demonstração com Quantificadores. A instanciação universal como regra de inferência para a qual se atribui a um determinado objecto uma propriedade válida para todos os objectos da “classe” a que ele pertence. Exemplificação com um argumento informal do mundo de Tarski. A generalização universal como regra de inferência que, a partir do facto de que uma propriedade é válida para um dado objecto, permite concluir a existência de (pelo menos) um objecto para o qual essa propriedade é válida. Exemplificação com um argumento informal do mundo de Tarski. A instanciação existencial como um método de atribuição de um “nome” a um 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.

(24) 3 Dez 2001

Métodos de Demonstração com Quantificadores. A generalização universal como método de inferência que permite atribuir a todos os objectos de uma classe uma propriedade que é válida para um objecto escolhido arbitrariamente nessa classe. A noção de escolha arbitrária de objecto de uma classe e sua exemplificação com demonstrações no domínio dos números (A raíz quadrada de um número primo é um número irracional) combinando vários métodos de prova, nomeadamente por absurdo. Utilização dos métodos informais de generalização e instanciação, existenciais e universais, para demonstração do paradoxo do barbeiro. A possibilidade de axiomatizar todas as regras relativas a um determinado domínio (por exemplo, o mundo de Tarski) em regras universais, de forma a permitir eliminar das demonstrações formais as consequências “analíticas”. Exemplos com os axiomas da forma e do tamanho no mundo de Tarski.

(25) 4 Dez 2001

Métodos Formais de Demonstração com Quantificadores. A aplicação em sistemas de dedução natural (como por exemplo o Fitch) das regras de generalização/instanciação universal/existencial. A instanciação universal e a regra de eliminação do quantificador universal. A generalização existencial e a introdução do quantificador existencial. A instanciação existencial e a eliminação do quantificador existencial, através de uma sub-demonstração com introdução de uma constante arbitrária e não utilizada anteriormente. A generalização universal e a regra de introdução do quantificador universal, através de uma sub-demonstração em que é tomada como hipótese uma constante arbitrária, quantificada universalmente no fecjho da sub-demonstração. Caso particular da generalização condicional, em que se assume que o objecto arbitrário pertence a uma classe, sendo a generalização feita apenas para elementos dessa classe. Exemplos no mundo do Tarski.

(26) 6 Dez 2001

Quantificação Numérica. Outros tipos de quantificação para além da existencial e universal. Quantificação induzida por 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. A existência de um e um só objecto, expressa através da existência de um objecto (existencial) e a imposição de que qualquer outro objecto é igual ao primeiro (quantificação universal e igualdade). Generalização deste procedimento para a quantificação de um número n exacto de objectos, através da existência de no mínimo n objectos distintos (existencial e um número quadrático de desigualdades) e de no máximo n objectos distintos (universal e disjunção de n igualdades). Quantificadores numéricos e suas fórmulas equivalentes

(27) 10 Dez 2001

Teoria de Conjuntos de 1ª Ordem. Noção intuitiva de conjuntos e seus elementos. Operadores elementares de pertença e igualdade. A teoria “ingénua” de conjuntos baseada nos axiomas da Extensão e da Compreensão (intenção). Estudo de várias proposições que decorrem destes dois axiomas: Unicidade do conjunto definido por uma fórmula bem formada P(x), noção de conjunto vazio e de conjuntos singulares. Distinção entre conjunto singular e o seu elemento (único). Operação de inclusão entre conjuntos e sua definição formal. Verificação das propriedades reflexiva, transitiva e anti-simétrica da relação de inclusão. Operações de união e intersecção de conjuntos e suas propriedades básicas (idempotência, comutatividade, simetria e distribuição. Relação com a inclusão..

(28) 11 Dez 2001

Teoria de Conjuntos de 1ª Ordem. Conjuntos de conjuntos. Sua utilização para definição de pares ordenados. Generalização para triplos e tuplos n-ários. Produto cartesiano e relações como subconjuntos dos produtos cartesianos Estudo de propriedades importantes em relações binárias: Reflexividade e Irreflexividade, Simetria, Antisimetria e Assimetria, Transitividade. Exemplos. Equivalência e classes de equivalência. Conjuntos de subconjuntos e conjunto potência. Cardinalidade de conjuntos como relação de equivalência, Cardinalidade de conjuntos finitos e infinitos com exemplificação nos inteiros e reais. Método da diagonalização de Cantor. Conjunto de Russel, e sua existência baseada no axioma da Compreensão. Paradoxo de Russel, sua analogia com o paradoxo do Barbeiro, e constatação que a teoria ingénua de conjuntos não é coerente. Breve menção a formas de “reparar” a teoria (Axiomas de Zermelo-Frankel).

(29) 12 Dez 2001

Indução Matemática. Estruturas definidas indutivamente (recursivamente). Clausulas de base, indutivas e de exclusão. Exemplos: Dominós, Alguns tipos de expressões regulares, 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”. Exemplos com expressões regulares e dificuldades que podem ser enconstradas se as propriedades a demonstrar forem “fracas”. 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.

(30) 17 Dez 2001

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. Claúsulas Definidas (de Horn): positivas, negativas e mistas. O algoritmo para verificação da satisfação de cláusulas Horn: sua complexidade polinomial (não exponencial). Exemplificação. Generalização do algoritmo para claúsulas não-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) Vantagens em relação aos sistemas de dedução natural em termos de implementação computacional. e sua mais fácil implementação . Exemplos: Modus Ponens, Modus Tollens, Silogismo, algumas tautologias.

(31) 7 Jan 2002

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. Skolemização e não equivalência. Utilização num processo de refutação. Eliminação dos quantificadores universais. Separação de cláusulas. Resolução e necessidade de tornar idênticos os literais. 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. Derivação da claúsula vazia. Exemplos de aplicação.

(32) 8 Jan 2002

Resolução em Lógica de Predicados de 1ª Ordem. Alguns exemplos de aplicação da resolução, abordando aspectos da passagem para a forma clausal incluindo a skolemização. Noção de pesquisa e completude da demonstração com resolução linear. Cláusulas de Horn e Prolog. Exemplo de introdução com um problemas de famílias.