Metateoria: introdução

Resumo

Esta aula abre a quarta e última unidade de conteúdo do curso, dedicada à metateoria. Apresenta suas três aulas e o fio que as une: as duas unidades anteriores construíram, sobre a mesma linguagem, duas noções do que se segue de certas premissas, a dedução $\Gamma \vdash \varphi$ e a consequência semântica $\Gamma \models \varphi$ , e esta unidade demonstra que elas coincidem, primeiro para premissas finitas (correção, lema de Kalmár e completude), depois para premissas quaisquer (teorema da compacidade e completude forte), e oferece por último um terceiro modo de decidir a consequência, o método de resolução, do qual demonstra também que é correto e completo. Explica por que a compacidade se demonstra antes da completude forte, e não o contrário; mostra com dois exemplos as perguntas que nem a busca de deduções nem a tabela-verdade podem responder por si sós; precisa o que se toma das três unidades anteriores e dá conselhos para estudá-la.

Objetivos de aprendizagem

Descrever a sequência das três aulas da unidade, explicar que resultados de cada uma a seguinte usa e justificar que a compacidade se demonstre, por um argumento semântico, antes da completude forte.
Distinguir as duas faces do curso, a dedutibilidade $\Gamma \vdash \varphi$ , existencial e finita, e a consequência semântica $\Gamma \models \varphi$ , universal sobre infinitas valorações, e enunciar a correção e a completude em seus três graus.
Explicar por que a coincidência de ambas as relações não pode ser estabelecida caso a caso, mas sim com metateoremas, e reconhecer que instrumentos das unidades anteriores (induções, prova por casos, teoremas da dedução, lema da coincidência, formas conjuntivas) cada demonstração usará.
Ler deduções sobre deduções e argumentos semânticos da unidade distinguindo em cada passo a relação de que se fala, e organizar o estudo a partir da avaliação de entrada.

Avaliação de entrada

Antes de percorrer a unidade, convém medir o ponto de partida. Esta avaliação é uma autoavaliação: não se pontua, e seu único propósito é orientar o estudo. Suas quinze perguntas são de dois tipos. As seis primeiras tratam do que a unidade dá por sabido das anteriores: a definição da consequência semântica e sua redução à insatisfatibilidade, o valor da negação conjunta, o lema da coincidência, a finitude da dedução e a prova por casos; quem errar alguma deve rever, antes de seguir, a aula que a pergunta nomeia. As nove restantes tratam, em ordem, das três aulas desta unidade, três de cada uma. Quem nunca estudou a metateoria de um sistema lógico não deve esperar acertá-las, e isso não importa: cada resposta, certa ou não, explica o ponto e nomeia a aula que o trata. As mesmas habilidades voltam a ser medidas no final, na aula de síntese.

Avaliação de entrada

Antes de começar a unidade, meça seu ponto de partida. É uma autoavaliação breve: não recebe nota e seu resultado fica guardado apenas no seu navegador.

Pergunta 1De unidades anterioresO que significa $\Gamma \models \varphi$ ?
Que toda valoração que satisfaz todas as fórmulas de $\Gamma$ satisfaz $\varphi$ .
Que existe uma dedução de $\varphi$ a partir de $\Gamma$ .
Que alguma valoração satisfaz ao mesmo tempo $\Gamma$ e $\varphi$ .
Que $\varphi$ é consequência de alguma fórmula de $\Gamma$ tomada sozinha.
Pergunta 2De unidades anterioresQual das afirmações seguintes equivale a $\Gamma \models \varphi$ ?
Que $\Gamma \cup \{\neg\varphi\}$ é insatisfatível.
Que $\Gamma \cup \{\varphi\}$ é satisfatível.
Que $\Gamma \cup \{\neg\varphi\}$ é satisfatível.
Que $\neg\varphi$ é insatisfatível.
Pergunta 3De unidades anterioresSe uma valoração $v$ dá a $\alpha$ o valor $1$ , que valor dá a $(\alpha \downarrow \beta)$ ?
$0$ , qualquer que seja o valor de $\beta$ .
Depende de $\beta$ : vale $1$ se $\beta$ vale $0$ .
$1 - v(\beta)$ .
$1$ , porque um dos componentes é verdadeiro.
Pergunta 4De unidades anterioresAs variáveis de $\varphi$ são $v_{2}$ e $v_{7}$ . Duas valorações $v$ e $w$ dão os mesmos valores a $v_{2}$ e a $v_{7}$ , e valores opostos a todas as demais variáveis. Se $v(\varphi) = 1$ , o que se pode afirmar de $w(\varphi)$ ?
Que $w(\varphi) = 1$ .
Nada, porque $v$ e $w$ diferem em infinitas variáveis.
Que $w(\varphi) = 0$ , porque $w$ inverte quase todos os valores de $v$ .
Que $w(\varphi) = 1$ só se $v$ e $w$ coincidem também em $v_{1}, \ldots, v_{6}$ .
Pergunta 5De unidades anterioresSeja $\Gamma$ um conjunto infinito de fórmulas tal que $\Gamma \vdash \varphi$ . O que se pode afirmar?
Que algum subconjunto finito de $\Gamma$ deduz $\varphi$ .
Que $\varphi$ é um teorema.
Que a dedução usa todas as fórmulas de $\Gamma$ .
Nada sem o teorema da compacidade, porque $\Gamma$ é infinito.
Pergunta 6De unidades anterioresSabe-se que $\Gamma \cup \{p\} \vdash \chi$ e que $\Gamma \cup \{\neg p\} \vdash \chi$ . O que a prova por casos permite concluir?
Que $\Gamma \vdash \chi$ .
Nada, enquanto não se souber se $\Gamma$ deduz $p$ ou deduz $\neg p$ .
Que $\Gamma \vdash (p \leftrightarrow \chi)$ .
Só que $\Gamma \cup \{p, \neg p\} \vdash \chi$ .
Pergunta 7O sistema do curso é correto. O que afirma essa propriedade?
Que, para todo conjunto $\Gamma$ , se $\Gamma \vdash \varphi$ , então $\Gamma \models \varphi$ .
Que se $\Gamma \models \varphi$ , então $\Gamma \vdash \varphi$ .
Que não existe nenhuma fórmula $\varphi$ com $\vdash \varphi$ e $\vdash \neg\varphi$ .
Que toda fórmula verdadeira é um teorema.
Pergunta 8Seja $v$ a valoração que dá $1$ a $p$ e $0$ a $q$ . O que afirma o lema de Kalmár, com as variáveis $p$ e $q$ , para a fórmula $(p \leftrightarrow q)$ ?
Que $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$ .
Que $\{p, \neg q\} \vdash (p \leftrightarrow q)$ .
Que $\{p, q\} \vdash \neg(p \leftrightarrow q)$ .
Que $\vdash \neg(p \leftrightarrow q)$ .
Pergunta 9Pode um sistema dedutivo ser correto sem ser completo?
Sim: o sistema de Łukasiewicz, sem a regra SDN, é correto e não deduz a tautologia $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ .
Não: a correção e a completude se inferem uma da outra.
Não: um sistema cujos axiomas são tautologias deduz todas as tautologias.
Sim, mas só se o sistema for inconsistente.
Pergunta 10O que afirma o teorema da compacidade?
Que um conjunto de fórmulas é satisfatível se e somente se todo subconjunto finito dele é satisfatível.
Que um conjunto de fórmulas é satisfatível se e somente se cada uma de suas fórmulas é satisfatível.
Que todo conjunto infinito de fórmulas é satisfatível.
Que um conjunto é satisfatível se algum subconjunto finito dele o é.
Pergunta 11Seja $\Gamma$ um conjunto infinito de fórmulas tal que $\Gamma \models \varphi$ . O que a compacidade assegura?
Que $\Gamma_{0} \models \varphi$ para algum subconjunto finito $\Gamma_{0}$ de $\Gamma$ .
Que $\varphi$ é consequência de alguma fórmula de $\Gamma$ tomada sozinha.
Que $\varphi$ é consequência de todo subconjunto finito de $\Gamma$ .
Que $\varphi$ é válida.
Pergunta 12A primeira aula demonstra a completude para conjuntos finitos de premissas. Por que a finitude da dedução não basta para estendê-la a um conjunto infinito $\Gamma$ ?
Porque a finitude fala de $\Gamma \vdash \varphi$ , e o que se tem é $\Gamma \models \varphi$ : é preciso que a consequência, não a dedução, se reduza a uma parte finita, e isso é a compacidade.
Basta, sim: se $\Gamma \models \varphi$ , a finitude dá um $\Gamma_{0}$ finito com $\Gamma_{0} \models \varphi$ .
Porque o lema de Kalmár não vale para fórmulas com infinitas variáveis.
Porque a completude é falsa para conjuntos infinitos de premissas.
Pergunta 13Qual é o resolvente das cláusulas $\{p, \neg q, r\}$ e $\{q, s\}$ ?
$\{p, r, s\}$ .
$\{p, \neg q, r, q, s\}$ .
$\{p, r\}$ .
Não têm resolvente, porque não compartilham nenhum literal.
Pergunta 14Para decidir por resolução se $\{(p \vee q), \neg p\} \models q$ , que conjunto de cláusulas se tenta refutar?
$\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$ .
$\{\{p, q\}, \{\neg p\}, \{q\}\}$ .
$\{\{p, q\}, \{\neg p\}\}$ .
$\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$ .
Pergunta 15Pode-se derivar por resolução a cláusula vazia $\Box$ do conjunto $\{\{p, q\}, \{\neg p, \neg q\}\}$ ?
Não: o conjunto é satisfatível, e a resolução é correta.
Sim, em um só passo, eliminando ao mesmo tempo os dois pares complementares.
Sim, em dois passos: primeiro sobre $p$ e depois sobre $q$ .
Não, porque nenhuma das duas cláusulas é unitária.