Lógica de predicados

Limites proposicionais

Nesse primeiro vídeo da segunda parte do nosso curso de lógica, veremos os limites expressivos das linguagens proposicionais. Por isso, introduziremos preliminarmente a expansão proposta na linguagem de predicados de primeira ordem.



Linguagem de primeira ordem

Exploraremos as linguagens de primeira ordem a partir de alguns exemplos. As linguagens de primeira ordem têm um incrível poder expressivo -- capazes, por exemplo, de dar conta de toda a matemática tradicional. Mostraremos os seus ingredientes e, em seguida, como os usar para produzir termos e fórmulas da linguagem.



lista-v2.pdf

Quantificadores e linguagem natural

A partir de exemplos, mostraremos como extrair a formalização de primeira ordem de frases da linguagem natural. Trataremos os casos universais e existenciais, mostrando a relação de oposição entre eles. Por fim, trataremos o caso do uso do artigo definido na linguagem natural e como formalizar esse uso em primeira ordem.



lista-v3.pdf

Fórmulas bem formadas

lista-v3-1.pdf

Sentenças e variáveis livres

Exploraremos os conceito de variáveis livres. A partir deste conceito, seremos capazes de tornar precisa a diferença entre fórmulas e sentenças. As fórmulas são expressões nas quais a presença de variáveis livres torna o seu significado incompleto.



lista-v4.pdf

Introdução à Semântica

Daremos início ao estudo da semântica de primeira ordem. Veremos como se opera a abstração de um modelo de primeira ordem. Em seguida veremos a relação de satisfação de modelos para fórmulas atômicas.



lista-v5.pdf

Semântica das funções e constantes

Daremos seguimento ao estudo da semântica de primeira ordem. Veremos como interpretar as funções e constantes em um modelo de primeira ordem. Em seguida, veremos a relação de satisfação de modelos para fórmulas algumas fórmulas..



lista-v6.pdf

Semântica dos quantificadores

Nesse vídeo, estudamos a semântica dos quantificadores universal e existencial na lógica de primeira ordem. Veremos como interpretar os quantificadores a partir de um modelo simples. Em seguida, veremos a relação de satisfação de modelos para fórmulas algumas fórmulas.



lista-v7.pdf

Satisfação em lógica de primeira ordem

Reunimos as definições semânticas trabalhadas nos vídeos anteriores, completando a caracterização dos modelos de primeira ordem. No fim, fazemos a avaliação de duas fórmulas em um modelo com quatro elementos.



lista-v8.pdf

Validade em lógica de primeira ordem

Estudados a validade em lógica de primeira ordem. De modo similar ao caso proposicional, uma fórmula é válida quando todos os modelos satisfazem a fórmula. Mostraremos como demonstrar que uma fórmula é válida usando duas estratégias: prova direta e prova por contradição. Por fim, exploramos um exemplo mais complicado com dois quantificadores.



Invalidades e contraexemplos

Estudamos as invalidades em lógica de primeira ordem. Mostraremos como usar contraexemplos para demonstrar que algumas sentenças não são logicamente válidas. Aproveitamos para elencar algumas validades importantes da lógica de primeira ordem, com inversão de ordem dos quantificadores e regras distributivas dos quantificadores nas operações lógicas.



lista-v9-v10.pdf

Teorias e silogismos

Estudamos as teorias de primeira ordem a partir de exemplos com silogismos. Definiremos de modo preciso a relação de consequência entre uma teoria e uma fórmula, algo muito similar ao que ocorre nos silogismos. Ao final, mostramos uma dedução em uma teoria mais familiar na matemática. 


lista-v11.pdf

Sistema dedutivo de lógica de primeira ordem

Introduzimos um sistema dedutivo para a lógica de primeira ordem. Esse sistema é uma extensão do que introduzimos para o cálculo proposicional. Faremos exemplos simples, além de introduzir uma simplificação para o cálculo proposicional que usaremos nos vídeos seguintes.


Teoremas de primeira ordem

Mostraremos alguns teoremas de primeira ordem. Começamos definindo o nosso sistema dedutivo com os axiomas de igualdade e identidade. Em seguida mostramos alguns teoremas próprios e básicos da lógica de predicados.


Equivalências e igualdade

Mostraremos alguns resultados a respeito de equivalências e igualdades em lógica de predicados. A Possibilidade de realizar substituições em fórmulas de subfórmulas equivalentes ou igualdades é uma poderosa ferramenta na lógica de primeira ordem.


lista-v12-v13-v14.pdf

Teorema da dedução

Apresentamos o teorema da dedução. Esse metateorema auxilia na demonstração de diversas fórmulas de primeira ordem, além de fundamentar o raciocínio hipotético. Mostraremos alguns exemplos. Ao final, provamos o método da prova por contradição usando o teorema da dedução.


Prova do teorema da dedução

Demonstramos o teorema da dedução a partir do método de indução matemática. A partir da suposição de que o teorema vale para fórmulas menos complexas, demonstramos que uma fórmula qualquer satisfaz o teorema.

lista-v15-v16.pdf

Teorema da generalização de constantes

Mostramos o teorema da generalização de constantes. Esse resultado representa um modo muito natural de fazer demonstrações universais na matemática e na linguagem natural. 

lista-v17.pdf

Teorema da completude de primeira ordem

Estudaremos o teorema da completude de primeira ordem. Mostraremos duas versões equivalentes do teorema e comentaremos o significado do teorema. Por fim, falaremos brevemente sobre decidibilidade e semi-decidibilidade.

Bibliografia recomendada: