Sémantique : introduction

Résumé

Cette leçon ouvre la troisième unité du cours, consacrée à la sémantique. Elle présente ses six leçons et le fil qui les unit, depuis le prolongement d’une valuation à toutes les formules jusqu’à l’algorithme des formes normales et aux circuits d’interrupteurs ; elle situe l’unité sur le chemin du cours, après la déduction, qui a obtenu des formules à partir d’autres sans prêter attention à leur signification, et avant la métathéorie, qui mettra en relation la déductibilité $\Gamma \vdash \varphi$ et la conséquence sémantique $\Gamma \models \varphi$ ; elle explique pourquoi une seule clause, celle du connecteur primitif, suffit à donner une signification à tout le langage, et pourquoi les valeurs de vérité se calculent avec des polynômes ; elle montre avec une table de quatre lignes ce que la sémantique décide sans chercher de déductions ni inventer de marquages ; elle précise ce que l’on prend des unités précédentes et donne des conseils pour l’étudier.

Objectifs d’apprentissage

Décrire la suite des six leçons de l’unité et expliquer quels résultats de chacune la suivante utilise.
Situer la sémantique dans le parcours du cours, distinguer la conséquence sémantique $\Gamma \models \varphi$ de la déductibilité $\Gamma \vdash \varphi$ et expliquer ce qu’affirmeront la correction et la complétude.
Expliquer pourquoi la bivalence et la vérifonctionnalité permettent de donner une signification à toutes les formules avec une seule clause, et décider avec une table de vérité si un schéma de raisonnement est valide.
Reconnaître ce que l’unité prend des précédentes, distinguer les symboles $=$ , $\eqsem$ , $\dashv\vdash$ , $\leftrightarrow$ et $\Leftrightarrow$ , et organiser l’étude à partir de l’évaluation d’entrée.

Évaluation d’entrée

Avant de parcourir l’unité, il convient de mesurer le point de départ. Cette évaluation est une autoévaluation : elle n’est pas notée, et son seul but est d’orienter l’étude. Ses quinze questions sont de deux sortes. Les quatre premières portent sur ce que l’unité tient pour acquis de la première : la définition par récurrence et la lecture unique, les abréviations officielles, les cas d’une induction sur la complexité et la substitution d’une sous-formule ; qui en manque une doit revoir, avant de poursuivre, la leçon que la question nomme. Les onze autres portent, dans l’ordre, sur les six leçons de cette unité : deux sur la première, deux sur la deuxième, une sur la troisième et deux sur chacune des trois dernières. Qui n’a jamais étudié la sémantique d’un langage formel ne doit pas s’attendre à les réussir, et cela n’a pas d’importance : chaque réponse, juste ou non, explique le point et nomme la leçon qui le traite. Les mêmes compétences sont mesurées de nouveau à la fin, dans la leçon de synthèse.

Évaluation d’entrée

Avant de commencer l’unité, mesurez votre point de départ. C’est une autoévaluation brève : elle n’est pas notée et son résultat n’est conservé que dans votre navigateur.

Question 1Des unités précédentesOn définit une fonction sur les formules en donnant sa valeur en chaque variable et une règle qui calcule la valeur de $\sigI\varphi\psi$ à partir de $\varphi$ , de $\psi$ et des valeurs des deux. Qu’est-ce qui garantit qu’une fonction et une seule est ainsi définie ?
La lecture unique : chaque formule composée se décompose d’une seule façon en son disque initial et ses deux composantes.
Que la règle renvoie toujours $0$ ou $1$ .
Rien : il faudrait vérifier la valeur formule par formule, et comme elles sont en nombre infini, ce n’est pas faisable.
Que les abréviations $\neg$ , $\vee$ et $\wedge$ aient elles aussi la lecture unique.
Question 2Des unités précédentesAvec les abréviations officielles du cours, quelle formule est $(\varphi \vee \varphi)$ ?
La même chaîne que $\neg\neg\varphi$ .
$\varphi$ elle-même, par l’idempotence.
$(\varphi \downarrow \varphi)$ .
Aucune : une disjonction exige deux formules distinctes.
Question 3Des unités précédentesPour démontrer par induction sur la complexité que toutes les formules ont une certaine propriété, quels cas faut-il traiter ?
Les variables et l’unique règle de formation, $\sigI\varphi\psi$ , c’est-à-dire $(\varphi \downarrow \psi)$ .
Les variables, la négation, la conjonction et la disjonction.
Seulement la règle $(\varphi \downarrow \psi)$ : les variables en sont un cas particulier.
Les variables et les six connecteurs $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ et $\veebar$ .
Question 4Des unités précédentesQuand on substitue la formule $\alpha$ par la formule $\beta$ dans $\varphi$ , selon la définition de la leçon sur l’induction, quelles occurrences de $\alpha$ change-t-on ?
Toutes ses occurrences comme sous-formule, à la fois.
Seulement la première, en lisant la chaîne de gauche à droite.
Seulement celles que l’on voit dans l’écriture abrégée.
Celles de $\alpha$ et, ensuite, celles qui apparaissent dans les copies de $\beta$ .
Question 5Une valuation donne à $p$ la valeur $0$ et à $q$ la valeur $1$ . Si $(\varphi \downarrow \psi)$ vaut $1$ exactement quand $\varphi$ et $\psi$ valent $0$ , quelle valeur prend la formule $(p \downarrow (q \downarrow p))$ ?
$1$ .
$0$ , car $q$ vaut $1$ .
On ne peut pas la calculer sans connaître les valeurs des autres variables.
Cela dépend de la façon dont on regroupe les composantes.
Question 6Que signifie $\not\models \varphi$ ?
Qu’une valuation donne à $\varphi$ la valeur $0$ : $\varphi$ n’est pas valide.
Que $\varphi$ est une antilogie.
Qu’aucune valuation ne satisfait $\varphi$ .
Que $\varphi$ ne se déduit pas dans le système du cours.
Question 7On sait que $\Gamma \cup \{\varphi\} \models \psi$ : toute valuation qui satisfait $\Gamma$ et $\varphi$ satisfait $\psi$ . Qu’en découle-t-il ?
$\Gamma \models (\varphi \rightarrow \psi)$ .
$\Gamma \models \psi$ .
$\Gamma \models (\psi \rightarrow \varphi)$ .
$\models (\varphi \rightarrow \psi)$ .
Question 8La formule $(v_{1} \vee \neg v_{1})$ est valide. Laquelle des formules suivantes est valide par le théorème de substitution uniforme ?
$(\neg v_{2} \vee \neg\neg v_{2})$ .
$(v_{1} \vee \neg v_{2})$ .
$(\neg v_{2} \vee \neg v_{3})$ .
Aucune : la substitution uniforme permet seulement de changer des variables en d’autres variables.
Question 9Selon la convention du cours, quelle formule désigne l’expression $v_{1} \wedge v_{2} \wedge v_{3}$ , écrite sans parenthèses ?
$((v_{1} \wedge v_{2}) \wedge v_{3})$ .
$(v_{1} \wedge (v_{2} \wedge v_{3}))$ .
Les deux regroupements, car ce sont la même chaîne.
Aucune : sans parenthèses, l’expression ne désigne rien.
Question 10Une fonction de vérité à deux arguments attribue une valeur, $0$ ou $1$ , à chacune des quatre lignes $(1, 1)$ , $(1, 0)$ , $(0, 1)$ et $(0, 0)$ . Combien y a-t-il de fonctions de vérité à deux arguments ?
Question 11Une formule écrite seulement avec $\wedge$ et $\vee$ à partir des variables peut-elle valoir $0$ dans la valuation qui donne $1$ à toutes les variables ?
Non : toute formule écrite seulement avec $\wedge$ et $\vee$ vaut $1$ dans cette valuation.
Oui, si l’on emboîte suffisamment de conjonctions et de disjonctions.
Oui : comme la négation conjointe suffit à elle seule, la conjonction et la disjonction suffisent aussi.
On ne peut pas le savoir sans écrire la table de chaque formule.
Question 12Un littéral est une variable ou la négation d’une variable. Laquelle des formules suivantes est un littéral ?
$\neg v_{2}$ .
$\neg\neg v_{1}$ .
$(v_{1} \wedge v_{2})$ .
$\top$ .
Question 13La forme normale conjonctive $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ est-elle valide ?
Non : la deuxième clause ne contient aucune paire complémentaire, et la valuation qui donne $0$ à $v_{3}$ et $1$ à $v_{2}$ la réfute.
Oui : la première clause contient une paire complémentaire, et une suffit.
Oui, car elle est satisfaisable.
On ne peut pas le décider sans une table de huit lignes.
Question 14Pour mettre une formule en forme normale disjonctive, on distribue la conjonction sur la disjonction. Quelle est la règle juste ?
$(\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)$ .
Question 15Un circuit a deux interrupteurs directs, des leviers $p$ et $q$ , montés en série, et ce bloc est en parallèle avec un interrupteur direct du levier $r$ . Quelle formule dit quand il conduit ?
$((p \wedge q) \vee r)$ .
$((p \vee q) \wedge r)$ .
$((p \wedge q) \wedge r)$ .
$((p \vee q) \vee r)$ .