Semântica: introdução

Resumo

Esta aula abre a terceira unidade do curso, dedicada à semântica. Apresenta suas seis aulas e o fio que as une, desde a extensão de uma valoração a todas as fórmulas até o algoritmo das formas normais e os circuitos de interruptores; situa a unidade no caminho do curso, depois da dedução, que obteve fórmulas de outras sem atender a seu significado, e antes da metateoria, que relacionará a dedutibilidade $\Gamma \vdash \varphi$ com a consequência semântica $\Gamma \models \varphi$ ; explica por que uma só cláusula, a do conectivo primitivo, basta para dar significado a toda a linguagem, e por que os valores de verdade se calculam com polinômios; mostra com uma tabela de quatro linhas o que a semântica decide sem buscar deduções nem inventar marcas; precisa o que se toma das unidades anteriores e dá conselhos para estudá-la.

Objetivos de aprendizagem

Descrever a sequência das seis aulas da unidade e explicar que resultados de cada uma a seguinte usa.
Situar a semântica no percurso do curso, distinguir a consequência semântica $\Gamma \models \varphi$ da dedutibilidade $\Gamma \vdash \varphi$ e explicar o que afirmarão a correção e a completude.
Explicar por que a bivalência e a verofuncionalidade permitem dar significado a todas as fórmulas com uma só cláusula, e decidir com uma tabela-verdade se um esquema de raciocínio é válido.
Reconhecer o que a unidade toma das anteriores, distinguir os símbolos $=$ , $\eqsem$ , $\dashv\vdash$ , $\leftrightarrow$ e $\Leftrightarrow$ , 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 quatro primeiras tratam do que a unidade dá por sabido da primeira: a definição por recursão e a leitura única, as abreviaturas oficiais, os casos de uma indução sobre a complexidade e a substituição de uma subfórmula; quem errar alguma deve rever, antes de seguir, a aula que a pergunta nomeia. As onze restantes tratam, em ordem, das seis aulas desta unidade: duas da primeira, duas da segunda, uma da terceira e duas de cada uma das três últimas. Quem nunca estudou a semântica de uma linguagem formal 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 anterioresUma função sobre as fórmulas se define dando seu valor em cada variável e uma regra que calcula o valor de $\sigI\varphi\psi$ a partir de $\varphi$ , de $\psi$ e dos valores de ambas. O que garante que assim fique definida exatamente uma função?
A leitura única: cada fórmula composta se decompõe de um só modo em seu disco inicial e suas duas componentes.
Que a regra devolva sempre $0$ ou $1$ .
Nada: seria preciso verificar o valor fórmula por fórmula, e como são infinitas, isso não pode ser feito.
Que as abreviaturas $\neg$ , $\vee$ e $\wedge$ também tenham leitura única.
Pergunta 2De unidades anterioresCom as abreviaturas oficiais do curso, que fórmula é $(\varphi \vee \varphi)$ ?
A mesma cadeia que $\neg\neg\varphi$ .
A própria $\varphi$ , pela idempotência.
$(\varphi \downarrow \varphi)$ .
Nenhuma: uma disjunção exige duas fórmulas distintas.
Pergunta 3De unidades anterioresPara demonstrar por indução sobre a complexidade que todas as fórmulas têm certa propriedade, que casos é preciso tratar?
As variáveis e a única regra de formação, $\sigI\varphi\psi$ , isto é, $(\varphi \downarrow \psi)$ .
As variáveis, a negação, a conjunção e a disjunção.
Só a regra $(\varphi \downarrow \psi)$ : as variáveis são um caso particular.
As variáveis e os seis conectivos $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ e $\veebar$ .
Pergunta 4De unidades anterioresAo substituir a fórmula $\alpha$ pela fórmula $\beta$ em $\varphi$ , segundo a definição da aula sobre a indução, que ocorrências de $\alpha$ se mudam?
Todas as suas ocorrências como subfórmula, ao mesmo tempo.
Só a primeira, lendo a cadeia da esquerda para a direita.
Só as que se veem na escrita abreviada.
As de $\alpha$ e, depois, as que apareçam nas cópias de $\beta$ .
Pergunta 5Uma valoração dá a $p$ o valor $0$ e a $q$ o valor $1$ . Se $(\varphi \downarrow \psi)$ vale $1$ exatamente quando $\varphi$ e $\psi$ valem $0$ , que valor toma a fórmula $(p \downarrow (q \downarrow p))$ ?
$1$ .
$0$ , porque $q$ vale $1$ .
Não pode ser calculado sem conhecer os valores das demais variáveis.
Depende de como se agrupem as componentes.
Pergunta 6O que significa $\not\models \varphi$ ?
Que alguma valoração dá a $\varphi$ o valor $0$ : $\varphi$ não é válida.
Que $\varphi$ é uma contradição.
Que nenhuma valoração satisfaz $\varphi$ .
Que $\varphi$ não se deduz no sistema do curso.
Pergunta 7Sabe-se que $\Gamma \cup \{\varphi\} \models \psi$ : toda valoração que satisfaz $\Gamma$ e $\varphi$ satisfaz $\psi$ . O que se segue?
$\Gamma \models (\varphi \rightarrow \psi)$ .
$\Gamma \models \psi$ .
$\Gamma \models (\psi \rightarrow \varphi)$ .
$\models (\varphi \rightarrow \psi)$ .
Pergunta 8A fórmula $(v_{1} \vee \neg v_{1})$ é válida. Qual das fórmulas seguintes é válida pelo teorema da substituição uniforme?
$(\neg v_{2} \vee \neg\neg v_{2})$ .
$(v_{1} \vee \neg v_{2})$ .
$(\neg v_{2} \vee \neg v_{3})$ .
Nenhuma: a substituição uniforme só permite mudar umas variáveis por outras.
Pergunta 9Pela convenção do curso, que fórmula designa a expressão $v_{1} \wedge v_{2} \wedge v_{3}$ , escrita sem parênteses?
$((v_{1} \wedge v_{2}) \wedge v_{3})$ .
$(v_{1} \wedge (v_{2} \wedge v_{3}))$ .
Os dois agrupamentos, porque são a mesma cadeia.
Nenhuma: sem parênteses a expressão não designa nada.
Pergunta 10Uma função de verdade de dois argumentos atribui um valor, $0$ ou $1$ , a cada uma das quatro linhas $(1, 1)$ , $(1, 0)$ , $(0, 1)$ e $(0, 0)$ . Quantas funções de verdade de dois argumentos existem?
Pergunta 11Pode uma fórmula escrita só com $\wedge$ e $\vee$ a partir das variáveis valer $0$ na valoração que dá $1$ a todas as variáveis?
Não: toda fórmula escrita só com $\wedge$ e $\vee$ vale $1$ nessa valoração.
Sim, se se aninharem suficientes conjunções e disjunções.
Sim: como a negação conjunta basta por si só, também bastam a conjunção e a disjunção.
Não se pode saber sem escrever a tabela de cada fórmula.
Pergunta 12Um literal é uma variável ou a negação de uma variável. Qual das fórmulas seguintes é um literal?
$\neg v_{2}$ .
$\neg\neg v_{1}$ .
$(v_{1} \wedge v_{2})$ .
$\top$ .
Pergunta 13É válida a forma normal conjuntiva $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ ?
Não: a segunda cláusula não contém nenhum par complementar, e a valoração que dá $0$ a $v_{3}$ e $1$ a $v_{2}$ a refuta.
Sim: a primeira cláusula contém um par complementar, e basta uma.
Sim, porque é satisfatível.
Não se pode decidir sem uma tabela de oito linhas.
Pergunta 14Para levar uma fórmula à forma normal disjuntiva, distribui-se a conjunção sobre a disjunção. Qual é a regra correta?
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$ .
Pergunta 15Um circuito tem dois interruptores diretos, das alavancas $p$ e $q$ , unidos em série, e esse bloco está em paralelo com um interruptor direto da alavanca $r$ . Que fórmula diz quando ele conduz?
$((p \wedge q) \vee r)$ .
$((p \vee q) \wedge r)$ .
$((p \wedge q) \wedge r)$ .
$((p \vee q) \vee r)$ .