{"id":289,"date":"2022-02-27T18:30:43","date_gmt":"2022-02-27T18:30:43","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=289"},"modified":"2022-03-02T22:41:27","modified_gmt":"2022-03-02T22:41:27","slug":"plf-partie-d","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/plf-partie-d\/","title":{"rendered":"PLF : partie D"},"content":{"rendered":"\n<div class=\"wp-block-jetpack-markdown\"><h1>Programmation logique et fonctionnelle &#8211; partie D<\/h1>\n<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1>La logique du premier ordre<\/h1>\n<p>Les activit\u00e9s <strong>#.dec<\/strong> (<strong>dec<\/strong> pour D\u00e9couverte) consistent \u00e0 \u00e9tudier des <strong>pr\u00e9sentations explicatives<\/strong> et \u00e0 traiter tous les <strong>exercices de d\u00e9couverte<\/strong> propos\u00e9s. Si vous ne r\u00e9pondez pas correctement \u00e0 un exercice de d\u00e9couverte, revenez en arri\u00e8re pour relire les explications et identifier la cause de votre erreur.<\/p>\n<p>Les activit\u00e9s <strong>#.ent<\/strong> (<strong>ent<\/strong> pour Entrainement) consistent \u00e0 traiter des <strong>exercices d&rsquo;entra\u00eenement<\/strong>. Vous devez d&rsquo;abord tenter de traiter ces exercices sans d\u00e9voiler d&rsquo;indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de d\u00e9couverte ou d&rsquo;entra\u00eenement pr\u00e9c\u00e9demment trait\u00e9s.<\/p>\n<h2>Activit\u00e9 de d\u00e9couverte D.dec<\/h2>\n<h3>Introduction<\/h3>\n<p><strong>En logique propositionnelle<\/strong> (partie C), les formules sont constitu\u00e9es de variables, connecteurs logiques ($\\vee$, $\\wedge$, $\\neg$, $\\to$, $\\leftrightarrow$), de parenth\u00e8ses, et des constantes $\\top$ et $\\bot$. Lorsqu&rsquo;on <strong>interpr\u00e8te<\/strong> ces formules, pour d\u00e9terminer leur <strong>valeurs de v\u00e9rit\u00e9s<\/strong>, on assigne des valeurs de v\u00e9rit\u00e9 0 ou 1 (<code>vrai<\/code> ou <code>faux<\/code>) \u00e0 leurs variables.<\/p>\n<p><strong>En logique du premier ordre<\/strong>, les variables peuvent prendre des valeurs diverses et vari\u00e9es (par exemple des entiers naturels, des r\u00e9els, des symboles) appartenant \u00e0 un domaine d&rsquo;interpr\u00e9tation. Ces variables peuvent \u00eatre li\u00e9es par des <strong>quantificateurs<\/strong> $\\forall$ et $\\exists$. En plus, un nombre illimit\u00e9 de nouveaux symboles apparaissent : les <strong>symboles fonctionnels<\/strong> et les <strong>symboles relationnels<\/strong>, aussi appel\u00e9s <strong>symboles de pr\u00e9dicats<\/strong>.<\/p>\n<p>Par convention, nous repr\u00e9senterons les variables du premier ordre par des lettres majuscules ou des mots commen\u00e7ant par une lettre majuscule, alors que les symboles fonctionnels et relationnels seront repr\u00e9sent\u00e9s par des lettres minuscules ou des mots commen\u00e7ant par une lettre minuscule.<\/p>\n<p>Les formules de la logique du premier ordre sont donc beaucoup plus riches que celles de la logique propositionnelle, ce qui leur permet de mod\u00e9liser beaucoup plus de choses. Mais il va falloir prendre le temps d&rsquo;assimiler diff\u00e9rents concepts avant de parvenir \u00e0 saisir l&rsquo;int\u00e9r\u00eat et la puissance de ce paradigme.<\/p>\n<h3>D.dec1 : Les termes fonctionnels<\/h3>\n<p>Les <strong>termes fonctionnels<\/strong> font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des <strong>symboles fonctionnels<\/strong> qui ont vocation \u00e0 \u00eatre interpr\u00e9t\u00e9s comme des fonctions. Mais pour le moment nous les consid\u00e9rerons comme des objets purement syntaxiques.<\/p>\n<p><strong>D\u00e9finition<\/strong> : Une <strong>signature fonctionnelle<\/strong> est un ensemble de symboles ayant chacun une arit\u00e9, qui est un entier naturel.<\/p>\n<p>Voici un exemple de signature fonctionnelle :<\/p>\n<p>${\\text{coul}\/1, \\text{mix}\/2, \\text{noir}\/0}$<\/p>\n<p>Le symbole $\\text{coul}$ est d&rsquo;arit\u00e9 1, le symbole $\\text{mix}$ est d&rsquo;arit\u00e9 2 et le symbole $\\text{noir}$ est d&rsquo;arit\u00e9 0. Les symboles d&rsquo;arit\u00e9 0 sont appel\u00e9 <strong>constantes fonctionnelles<\/strong>.<\/p>\n<p><strong>D\u00e9finition<\/strong> : On appelle <strong>terme fonctionnel<\/strong> compatible avec une signature fonctionnelle $F$ tout terme pouvant \u00eatre construit de mani\u00e8re inductive avec les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>Une variable est un terme fonctionnel.<\/li>\n<li>Une constante fonctionnelle (i.e., un terme fonctionnel d&rsquo;arit\u00e9 0) appartenant \u00e0 $F$ est un terme fonctionnel compatible avec $F$.<\/li>\n<li>Si $\\mathcal{T}_1, \\dots, \\mathcal{T}_n$ sont des termes fonctionnels compatibles avec $F$ et $\\mathcal{S}$ un symbole fonctionnel d&rsquo;arit\u00e9 $n$ appartenant \u00e0 $F$, alors $\\mathcal{S}(\\mathcal{T}_1, \\dots, \\mathcal{T}_n)$ est un terme fonctionnel compatible avec $F$.<\/li>\n<\/ul>\n<p>Voici quelques exemples de termes fonctionnels compatibles avec  la signature fonctionnelle ${\\text{coul}\/1, \\text{mix}\/2, \\text{noir}\/0}$ :<\/p>\n<p>$X, ~ \\text{coul}(X), ~ \\text{mix}(\\text{noir}, \\text{coul}(\\text{coul}(Y)))$<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x1<\/h5>\n<p>Parmi les expressions suivantes, quel sont les termes fonctionnels compatibles avec la signature ${\\text{coul}\/1, \\text{mix}\/2, \\text{noir}\/0}$ ?<\/p>\n<ul>\n<li>$\\text{noir} $<\/li>\n<li>$\\text{coul}(\\text{coul (Y)} ) $<\/li>\n<li>$\\text{coul}(\\text{coul (noir)} ) $<\/li>\n<li>$Y$<\/li>\n<li>$\\text{mix(X,Y)} $<\/li>\n<li>$\\text{mix}(\\text{noir}, \\text{noir}) $<\/li>\n<li>$\\text{mix}(\\text{mix}(X,\\text{noir} ) ) $<\/li>\n<li>$X(\\text{noir} )$<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les termes fonctionnels compatibles avec la signature donn\u00e9e sont :<\/p>\n<ul>\n<li>$\\text{noir} $<\/li>\n<li>$\\text{coul}(\\text{coul (Y)} ) $<\/li>\n<li>$\\text{coul}(\\text{coul (noir)} ) $<\/li>\n<li>$Y$<\/li>\n<li>$\\text{mix(X,Y)} $<\/li>\n<li>$\\text{mix}(\\text{noir}, \\text{noir}) $<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec2 : Les atomes<\/h3>\n<p>Les <strong>atomes<\/strong> font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des <strong>symboles relationnels<\/strong> qui ont vocation \u00e0 \u00eatre interpr\u00e9t\u00e9s comme des pr\u00e9dicats, c&rsquo;est \u00e0 dire des fonctions \u00e0 valeurs dans ${\\text{vrai},\\text{faux}}$. Mais pour le moment nous les consid\u00e9rerons comme des objets purement syntaxiques.<\/p>\n<p><strong>D\u00e9finition<\/strong> : Une <strong>signature relationnelle<\/strong> est un ensemble de symboles ayant chacun une arit\u00e9, qui est un entier naturel.<\/p>\n<p>Voici un exemple de signature relationnelle :<\/p>\n<p>${\\text{arc}\/2, \\text{source}\/1}$<\/p>\n<p>Les symboles $\\text{arc}$ et $\\text{source}$ sont d&rsquo;arit\u00e9s respectives 2 et 1. Les symboles d&rsquo;arit\u00e9 0 sont appel\u00e9s variables propositionnelles. Ce sont en fait les variables de la logique propositionnelles qui ont \u00e9t\u00e9 introduites dans la partie C.<\/p>\n<p><strong>D\u00e9finition<\/strong> : On appelle <strong>signature<\/strong> tout couple $(F,R)$ o\u00f9 $F$ est une signature fonctionnelle et $R$ une signature relationnelle telles que $F \\cap R$ est vide.<\/p>\n<p><strong>D\u00e9finition<\/strong> : On appelle <strong>atome<\/strong> compatible avec une signature $S=(F,R)$ tout terme pouvant \u00eatre construit de mani\u00e8re inductive avec les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>Un symbole relationnel d&rsquo;arit\u00e9 0 appartenant \u00e0 la signature relationnelle $R$ est un atome compatible avec $S$.<\/li>\n<li>Si $\\mathcal{T}_1, \\dots, \\mathcal{T}_n$ sont des <strong>termes fonctionnels<\/strong> compatibles avec la signature fonctionnelle $F$ et si est $\\mathcal{R}$ un symbole relationnel d&rsquo;arit\u00e9 $n$ appartenant \u00e0 la signature relationnelle $R$, alors $\\mathcal{R}(\\mathcal{T}_1, \\dots, \\mathcal{T}_n)$ est un atome compatible avec $S$.<\/li>\n<\/ul>\n<p>Voici quelques exemples d&rsquo;atomes compatibles avec la signature $({\\text{coul}\/1}, {\\underline{\\text{arc}}\/2, \\underline{\\text{source}}\/1})$ :<\/p>\n<p>$\\text{arc}(X,Y), ~ \\text{source}(\\text{coul}(X)), ~ \\text{arc}(\\text{coul}(Y),Z)    $<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x2<\/h5>\n<p>Parmi les expressions suivantes, quel sont les atomes compatibles avec la signature $({\\text{coul}\/1}, {\\underline{\\text{arc}}\/2, \\underline{\\text{source}}\/1})$ ? (Les symboles relationnels ont \u00e9t\u00e9 soulign\u00e9s.)<\/p>\n<ul>\n<li>$\\text{arc}(X) $<\/li>\n<li>$\\text{coul}(Y) $<\/li>\n<li>$\\text{coul}(\\text{arc}(X,Y) ) $<\/li>\n<li>$\\text{arc}(X,\\text{coul(X)} ) $<\/li>\n<li>$\\text{source}(\\text{coul}(\\text{coul}(X) ) ) $<\/li>\n<li>$Z$<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ul>\n<li>$\\underline{\\text{arc}}(X,\\text{coul(X)} ) $<\/li>\n<li>$\\underline{\\text{source}}(\\text{coul}(\\text{coul}(X) ) ) $<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec3 : Interpr\u00e9tation d&rsquo;une signature<\/h3>\n<p>Les symboles fonctionnels et relationnels ne sont&#8230; que des symboles tant qu&rsquo;on ne leur donne pas une <strong>interpr\u00e9tation<\/strong>.<\/p>\n<p>Une interpr\u00e9tation donne un sens \u00e0 chaque symbole relationnel et chaque symbole fonctionnel d&rsquo;une signature.<\/p>\n<p>Une interpr\u00e9tation d&rsquo;une signature $(F,R)$ est constitu\u00e9e :<\/p>\n<ul>\n<li>D&rsquo;un <strong>domaine d&rsquo;interpr\u00e9tation<\/strong> qui est un ensemble non vide $D$.<\/li>\n<li>Pour chaque chaque constante fonctionnelle $\\mathcal{F}\/0\\in F $, d&rsquo;une valeur de $D$.<\/li>\n<li>Pour chaque symbole fonctionnel d&rsquo;arit\u00e9 non nulle $\\mathcal{F}\/n \\in F$, d&rsquo;une application de $D^n$ dans $D$.<\/li>\n<li>Pour chaque symbole relationnel $R\/0 \\in R$, d&rsquo;une valeur de v\u00e9rit\u00e9 0 ou 1.<\/li>\n<li>Pour chaque symbole relationnel d&rsquo;arit\u00e9 non nulle $\\mathcal{R}\/n $, d&rsquo;une application de $D^n$ dans ${\\text{vrai},\\text{faux}}$. Une telle fonction est appel\u00e9e <strong>pr\u00e9dicat<\/strong>.<\/li>\n<\/ul>\n<p>On associe donc \u00e0 chaque constante fonctionnelle une valeur du domaine d&rsquo;interpr\u00e9tation, \u00e0 chaque symbole fonctionnel d&rsquo;arit\u00e9 non nulle une fonction, \u00e0 chaque symbole relationnel un pr\u00e9dicat (ou de mani\u00e8re \u00e9quivalente, une relation) et \u00e0 chaque symbole relationnel d&rsquo;arit\u00e9 0 une valeur de v\u00e9rit\u00e9.<\/p>\n<p>Voici deux exemples concrets d&rsquo;interpr\u00e9tations d&rsquo;une m\u00eame signature :<\/p>\n<p>$S = ({\\text{zero}\/0, \\text{plus}\/2 },{\\underline{\\text{egal}}\/2 })$<\/p>\n<p><strong>Interpr\u00e9tation 1<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble $\\mathbb{N}$ des entiers naturels.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme standard qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $x+y$.<\/li>\n<li>Le symbole $\\text{egal}$ repr\u00e9sente la relation d&rsquo;\u00e9galit\u00e9 standard : $\\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l&rsquo;\u00e9galit\u00e9 entre entiers naturels.<\/li>\n<\/ul>\n<p><strong>Interpr\u00e9tation 2<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble ${0,1,2}$.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme modulo 3 qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $(x+y) \\mod 3$.<\/li>\n<li>Le symbole $\\text{egal}$ repr\u00e9sente la relation d&rsquo;\u00e9galit\u00e9 standard : $\\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l&rsquo;\u00e9galit\u00e9 entre entiers naturels.<\/li>\n<\/ul>\n<h5>Exercice de d\u00e9couverte D.dec.x3<\/h5>\n<p>Combien y a t-il d&rsquo;interpr\u00e9tations diff\u00e9rentes de la signature $S = ({\\text{zero}\/0 },{\\underline{\\text{egal}}\/2 })$ ayant l&rsquo;ensemble ${1,2}$ comme domaine d&rsquo;interpr\u00e9tation ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le symbole $\\text{zero} $ peut \u00eatre interpr\u00e9t\u00e9 par 1 ou par 2.<\/p>\n<p>Le symbole $\\text{egal} $ peut repr\u00e9senter n&rsquo;importe quelle relation (ou pr\u00e9dicat) d&rsquo;arit\u00e9 2. On peut voir chacune de ces interpr\u00e9tations comme une table de v\u00e9rit\u00e9. Voici un exemple d&rsquo;une telle table de v\u00e9rit\u00e9 :<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$X$<\/th>\n<th style=\"text-align:center\">$Y$<\/th>\n<th style=\"text-align:center\">$\\text{egal}(X,Y) $<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">$\\text{faux} $<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">2<\/td>\n<td style=\"text-align:center\">$\\text{faux} $<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">2<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">$\\text{faux} $<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">2<\/td>\n<td style=\"text-align:center\">2<\/td>\n<td style=\"text-align:center\">$\\text{faux} $<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Il y a autant d&rsquo;interpr\u00e9tations diff\u00e9rentes du symbole relationnel $\\text{egal} $ qu&rsquo;il y a de tables de v\u00e9rit\u00e9 diff\u00e9rentes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Avec le domaine d&rsquo;interpr\u00e9tation ${1,2}$, il y a 2 interpr\u00e9tations diff\u00e9rentes du symbole $\\text{zero} $ et 16 interpr\u00e9tation diff\u00e9rentes du symboles $\\text{egal} $.<\/p>\n<p>Il existe donc 32 interpr\u00e9tations diff\u00e9rentes de la signature $({\\text{zero}\/0 },{\\underline{\\text{egal}}\/2 })$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec4 : Interpr\u00e9tation des termes fonctionnels<\/h3>\n<p>On appelle <strong>valuation<\/strong> d&rsquo;un ensemble $V$ de variables sur un domaine d&rsquo;interpr\u00e9tation $D$ toute application de $V$ dans $D$. En d&rsquo;autre termes, une valuation assigne \u00e0 chaque variable un \u00e9l\u00e9ment du domaine d&rsquo;interpr\u00e9tation.<\/p>\n<p>\u00c9tant donn\u00e9s :<\/p>\n<ul>\n<li>un terme fonctionnel $f$,<\/li>\n<li>une interpr\u00e9tation $I$ des symboles fonctionnels apparaisant dans $f$,<\/li>\n<li>une valuation $A$ des variables apparaissant dans le terme $f$,<\/li>\n<\/ul>\n<p><strong>L&rsquo;interpr\u00e9tation<\/strong> de $f$ pour la valuation $A$ consiste \u00e0 d\u00e9terminer la valeur $\\text{Val}(f,A)$ par induction d&rsquo;apr\u00e8s les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>La valeur d&rsquo;une constante fonctionnelle est celle qui lui est assign\u00e9e par l&rsquo;interpr\u00e9tation $I$.<\/li>\n<li>La valeur d&rsquo;une variable est celle qui lui est assign\u00e9e par la valuation $A$.<\/li>\n<li>Pour tout symbole $\\mathcal{F}\/n$ ayant pour interpr\u00e9tation la fonction $\\text{Val}_ \\mathcal{F}$, $\\text{Val}(\\mathcal{F}(f_1,&#8230;,f_n),A)$ $=$ $\\text{Val}_ \\mathcal{F}(\\text{Val}(f_1,A),&#8230;,\\text{Val}(f_n,A))$.<\/li>\n<\/ul>\n<p><strong>Exemple<\/strong> :<\/p>\n<p>On consid\u00e8re la signature fonctionnelle ${\\text{zero}\/0, \\text{plus}\/2 }$ et l&rsquo;interpr\u00e9tation suivante de cette signature :<\/p>\n<p><strong>Interpr\u00e9tation 1<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble $\\mathbb{N}$ des entiers naturels.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme standard qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $x+y$.<\/li>\n<\/ul>\n<p>Soit le terme fonctionnel $f = \\text{plus}(\\text{plus}(\\text{zero},X),Y))$ et la valuation $A = {(X,1), (Y,2)}$.<\/p>\n<p>L&rsquo;interpr\u00e9tation de $f$ pour $A$ est 3 car :<\/p>\n<ul>\n<li>$\\text{Val}(\\text{zero},A) = 0$,<\/li>\n<li>$\\text{Val}(X,A) = 1$<\/li>\n<li>$\\text{Val}(Y,A) = 2$<\/li>\n<li>$\\text{Val}(\\text{plus}(\\text{zero},X),A) = 1$<\/li>\n<\/ul>\n<p>En termes informels, interpr\u00e9ter un terme fonctionnel consiste \u00e0 d\u00e9terminer sa valeur \u00e0 partir des valeurs de ses variables et des fonctions assign\u00e9es \u00e0 ses symboles fonctionnels par leur interpr\u00e9tation.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x4<\/h5>\n<p>Donnez la valeur du terme fonctionnel $f = \\text{plus}(\\text{plus}(\\text{zero},X),Y)$ pour la valuation $A = {(X,1), (Y,2)}$ et l&rsquo;interpr\u00e9tation suivante :<\/p>\n<p><strong>Interpr\u00e9tation 2<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble ${0,1,2}$.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme modulo 3 qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $(x+y) \\mod 3$.<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ul>\n<li>$\\text{plus}(\\text{zero},X)$ s&rsquo;interpr\u00e8te \u00e0 1, c&rsquo;est \u00e0 dire $(0 + 1) \\mod 3$.<\/li>\n<li>$f = \\text{plus}(\\text{plus}(\\text{zero},X),Y)$ s&rsquo;interpr\u00e8te \u00e0 0, c&rsquo;est \u00e0 dire $(2 + 1) \\mod 3$<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec5 : Interpr\u00e9tation des atomes<\/h3>\n<p>Pour m\u00e9moire, la <strong>valuation<\/strong> d&rsquo;un ensemble $V$ de variables sur un domaine d&rsquo;interpr\u00e9tation $D$ est une application qui assigne \u00e0 chaque variable de $V$ un \u00e9l\u00e9ment de $D$.<\/p>\n<p>\u00c9tant donn\u00e9s :<\/p>\n<ul>\n<li>un atome $t$,<\/li>\n<li>une interpr\u00e9tation $I$ des symboles fonctionnels et du symbole relationnel apparaissant dans $t$,<\/li>\n<li>une valuation $A$ des variables apparaissant dans $t$,<\/li>\n<\/ul>\n<p><strong>L&rsquo;interpr\u00e9tation<\/strong> de $t$ pour la valuation $A$ consiste \u00e0 d\u00e9terminer la valeur $\\text{Val}(t,A)$ par induction d&rsquo;apr\u00e8s les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>La valeur d&rsquo;une constante relationnelle est celle qui lui est assign\u00e9e par l&rsquo;interpr\u00e9tation $I$ ($\\text{vrai} $ ou $\\text{faux}$).<\/li>\n<li>Pour tout terme relationnel $\\mathcal{T}\/n$ ayant pour interpr\u00e9tation la fonction $\\text{Val}_ \\mathcal{T}$, $\\text{Val}(\\mathcal{T}(f_1,&#8230;,f_n),A)$ $=$ $\\text{Val}_ \\mathcal{T}(\\text{Val}(f_1,A),&#8230;,\\text{Val}(f_n,A))$.<\/li>\n<\/ul>\n<p><strong>Exemple<\/strong> :<\/p>\n<p>On consid\u00e8re la signature fonctionnelle $S = ({\\text{zero}\/0, \\text{plus}\/2 },{\\underline{\\text{egal}}\/2 })$ et l&rsquo;interpr\u00e9tation suivante de cette signature :<\/p>\n<p><strong>Interpr\u00e9tation 1<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble $\\mathbb{N}$ des entiers naturels.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme standard qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $x+y$.<\/li>\n<li>Le symbole $\\text{egal}$ repr\u00e9sente la relation d&rsquo;\u00e9galit\u00e9 standard : $\\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l&rsquo;\u00e9galit\u00e9 entre entiers naturels.<\/li>\n<\/ul>\n<p>Soit l&rsquo;atome $t =$ $\\text{egal}(\\text{zero}, \\text{plus}(\\text{plus}(\\text{zero},X),Y)) )$ et la valuation $A = {(X,1), (Y,2)}$.<\/p>\n<p>L&rsquo;interpr\u00e9tation de $f$ pour $A$ est $\\text{faux} $ car :<\/p>\n<ul>\n<li>$\\text{plus}(\\text{plus}(\\text{zero},X),Y)) = 3$<\/li>\n<li>et $\\text{egal(0,3}) = \\text{faux}$<\/li>\n<\/ul>\n<p>En termes informels, interpr\u00e9ter un atome consiste \u00e0 d\u00e9terminer sa valeur \u00e0 partir des valeurs de ses variables, des fonctions associ\u00e9es \u00e0 ses symboles fonctionnels, et de la relation associ\u00e9e \u00e0 son symbole relationnel par leur interpr\u00e9tation.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x5<\/h5>\n<p>Donnez la valeur de l&rsquo;atome $t = \\text{p}( \\text{plus}(\\text{plus}(\\text{zero},X),Y))$ pour la valuation $A = {(X,1), (Y,2)}$ et l&rsquo;interpr\u00e9tation suivante :<\/p>\n<p><strong>Interpr\u00e9tation 2<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble ${0,1,2}$.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme modulo 3 qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $(x+y) \\mod 3$.<\/li>\n<li>Le symbole $\\text{p}$ repr\u00e9sente la fonction telle que $\\text{p}(0) = \\text{p}(2) = \\text{vrai}$ et $\\text{p}(1) = \\text{faux} $.<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ul>\n<li>$\\text{plus}(\\text{plus}(\\text{zero},X),Y)$ s&rsquo;interpr\u00e8te \u00e0 0 (vu dans l&rsquo;exercice pr\u00e9c\u00e9dent).<\/li>\n<li>donc $t$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec6 : Formules<\/h3>\n<p>Jusqu&rsquo;\u00e0 maintenant, nous n&rsquo;avons vu que des parties de formules appel\u00e9es <strong>termes fonctionnels<\/strong> et <strong>atomes<\/strong>. Ces expressions sont construites \u00e0 partir de symboles fonctionnels, variables et symboles relationnels.<\/p>\n<p>Une formule du premier ordre est constitu\u00e9e d&rsquo;atomes, de connecteurs logiques, de parenth\u00e8ses et de quantificateurs.<\/p>\n<p>On appelle <strong>formule compl\u00e8tement parenth\u00e9s\u00e9e<\/strong> toute expression pouvant \u00eatre construite par induction en utilisant les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>Tout atome est une formule.<\/li>\n<li>Si $\\sigma$ est une formule, alors $\\neg \\sigma$ en est une.<\/li>\n<li>Si $\\sigma_1$ et $\\sigma_2$ sont des formules, alors $(\\sigma_1 \\vee \\sigma_2)$, $(\\sigma_1 \\wedge \\sigma_2)$, $(\\sigma_1 \\to \\sigma_2)$ et $(\\sigma_1 \\leftrightarrow \\sigma_2)$ sont des formules.<\/li>\n<li>Si $\\sigma$ est une formule et $X$ une variable, alors $(\\exists X \\sigma)$ et $(\\forall X \\sigma)$ sont des formules.<\/li>\n<\/ul>\n<p>Voici un exemple de formule compl\u00e8tement parenth\u00e9s\u00e9e dans la quelle les atomes ont \u00e9t\u00e9 soulign\u00e9s :<\/p>\n<p>$(\\exists Y((\\forall X \\underline{\\text{egal}(\\text{plus}(X,Y),X)})$ $\\to$ $\\neg \\underline{\\text{egal}(\\text{zero},Y)}))$<\/p>\n<p>Attention, on ne s&rsquo;int\u00e9resse pas, pour le moment, aux valeurs de v\u00e9rit\u00e9 des formules, qui peuvent d\u00e9pendre de l&rsquo;interpr\u00e9tation de leurs symboles fonctionnels er relationnels, comme nous le verrons plus loin.<\/p>\n<p>On peut supprimer certaines parenth\u00e8ses en utilisant les m\u00eames r\u00e8gles d&rsquo;associativit\u00e9 et priorit\u00e9s que pour la logique propositionnelle, auxquelles s&rsquo;ajoutent les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>Les quantificateurs ont la m\u00eame priorit\u00e9 que le connecteur $\\neg$, donc une priorit\u00e9 plus \u00e9lev\u00e9e que les connecteurs $\\vee, \\wedge, \\to, \\leftrightarrow$.<\/li>\n<li>Les quantificateurs sont associatifs \u00e0 droite (donc par exemple $\\exists X \\forall Y \\exists Z ~ \\sigma$ se lit $\\exists X (\\forall Y (\\exists Z ~ \\sigma))$).<\/li>\n<\/ul>\n<p>La formule donn\u00e9e en exemple peut donc s&rsquo;\u00e9crire :<\/p>\n<p>$\\exists Y(\\forall X \\underline{\\text{egal}(\\text{plus}(X,Y),X)}$ $\\to$ $\\neg \\underline{\\text{egal}(\\text{zero},Y)})$<\/p>\n<p>Mais pour am\u00e9liorer la lisibilit\u00e9, n&rsquo;h\u00e9sitez pas \u00e0 mettre plus de parenth\u00e8ses que ce qui est strictement n\u00e9cessaire.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x6<\/h5>\n<p>Voici une formule compl\u00e8tement parenth\u00e9s\u00e9e :<\/p>\n<p>$(\\exists X((\\forall Y(\\text{p}(X,Y) \\wedge \\text{q}(Y)))$ $\\to$ $(\\forall Y(\\text{p}(Y,X) \\vee \\text{q}(X) ))))$<\/p>\n<p>Supprimez les parenth\u00e8ses qui ne sont pas strictement n\u00e9cessaires.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\exists X(~ \\forall Y(\\text{p}(X,Y) \\wedge \\text{q}(Y))$ $\\to$ $\\forall Y(\\text{p}(Y,X) \\vee \\text{q}(X) ) ~)$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Y-a-t-il des symboles relationnels dans cette formule ? Si oui lesquels ? Y-a-t-il des symboles fonctionnels ? Si oui lesquels. Soulignez tous les atomes.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les symboles relationnels sont $\\text{p}$ et $\\text{q}$. Il n&rsquo;y a pas de symboles fonctionnels. En effet, des symboles fonctionnels ne peuvent se trouver que <strong>dans<\/strong> les atomes, qui sont d\u00e9finit \u00e0 l&rsquo;aide de symboles relationnels.<\/p>\n<p>$\\exists X(~ \\forall Y(\\underline{\\text{p}(X,Y)} \\wedge \\underline{\\text{q}(Y)})$ $\\to$ $\\forall Y(\\underline{\\text{p}(Y,X)} \\vee \\underline{\\text{q}(X)} ) ~)$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec7 : Formules closes<\/h3>\n<p>Les variables apparaissant dans une formule peuvent \u00eatre <strong>li\u00e9es<\/strong> ou <strong>libres<\/strong>.<\/p>\n<p>Les variables li\u00e9es sont introduites par les quantificateurs $\\forall$ et $\\exists$. Chaque quantificateur lie entre elles toutes les occurrences de la variable qu&rsquo;il quantifie et qui se situent dans sa port\u00e9e, c&rsquo;est \u00e0 dire entre les parenth\u00e8ses associ\u00e9es \u00e0 ce quantificateur dans la forme compl\u00e8tement parenth\u00e9s\u00e9e de la formule.<\/p>\n<p>Voici un exemple de formule o\u00f9 les occurrences de variables li\u00e9es par chaque quantificateur sont mises en \u00e9vidence.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd1.png\" alt=\"plfd1\"><\/p>\n<p>Les variables qui ne sont pas li\u00e9es sont dites <strong>libres<\/strong>.<\/p>\n<p>Toute formule dont toutes les variables sont li\u00e9es est dite <strong>close<\/strong>.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x7<\/h5>\n<p>Dans la formule suivante, soulignez les atomes, reliez par des fl\u00e8ches les occurrences de variables li\u00e9es entre elles, et entourez les variables libres.<\/p>\n<p>$\\forall A ~ \\text{p}(A,B)$ $\\to$ $\\exists A ~ (~ q(A,C) \\vee \\exists B ~ t(f(B))~) $<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/plfd2bis.png\" alt=\"plfd2\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Cette formule est-elle close ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, car elle contient des variables libres.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec8 : Interpr\u00e9tation d&rsquo;une formule close<\/h3>\n<p>Nous avons vu pr\u00e9c\u00e9demment comment interpr\u00e9ter les termes fonctionnels et les atomes de formules en nous basant sur un <strong>domaine d&rsquo;interpr\u00e9tation<\/strong> et en donnant un <strong>sens<\/strong> aux symboles fonctionnels et aux symboles relationnels.<\/p>\n<p>Interpr\u00e9ter une formule close consiste \u00e0 d\u00e9terminer sa valeur de v\u00e9rit\u00e9 pour une interpr\u00e9tation donn\u00e9e de ses symboles fonctionnels et de ses symboles relationnels.<\/p>\n<p>Pour une valuation $A$ donn\u00e9e de ses variables, un atome s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$ ou $\\text{faux}$. Une formule constitu\u00e9e uniquement d&rsquo;atomes et de connecteurs logiques s&rsquo;interpr\u00e8te selon les m\u00eames r\u00e8gles qu&rsquo;en logique propositionnelle, bas\u00e9es sur les tables de v\u00e9rit\u00e9s des connecteurs.<\/p>\n<p>Toujours pour une valuation donn\u00e9e, la valeur de v\u00e9rit\u00e9 d&rsquo;une formule est d\u00e9termin\u00e9e par induction d&rsquo;apr\u00e8s les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>La valeur de v\u00e9rit\u00e9 d&rsquo;un atome $t$ (qui est un cas particulier de formule) pour une valuation $A$ de ses variables est $\\text{Val}(t,A)$. (Voir section D.dec5).<\/li>\n<li>Si $\\Sigma$ est une formule, alors $\\text{Val}(\\neg \\Sigma,A)$ $=$ $\\underline\\neg \\text{Val} (\\Sigma, A)$<\/li>\n<li>Si $\\Sigma$ et $\\Omega$ sont des formules, alors :\n<ul>\n<li>$\\text{Val}(\\Sigma \\vee \\Omega, A)$ $=$ $\\text{Val}(\\Sigma,A) \\underline\\vee \\text{Val}(\\Omega,A)$<\/li>\n<li>$\\text{Val}(\\Sigma \\wedge \\Omega, A)$ $=$ $\\text{Val}(\\Sigma,A) \\underline\\wedge \\text{Val}(\\Omega,A)$<\/li>\n<li>$\\text{Val}(\\Sigma \\to \\Omega, A)$ $=$ $\\text{Val}(\\Sigma,A) \\underline\\to \\text{Val}(\\Omega,A)$<\/li>\n<li>$\\text{Val}(\\Sigma \\leftrightarrow \\Omega, A)$ $=$ $\\text{Val}(\\Sigma,A) \\underline\\leftrightarrow \\text{Val}(\\Omega,A)$<\/li>\n<\/ul>\n<\/li>\n<li>Si $\\Sigma$ est une formule et $X$ une variable non assign\u00e9e par $A$, alors $\\text{Val}(\\exists X ~ \\Sigma,A) = \\text{vrai}$ si et seulement si  il existe au moins un \u00e9l\u00e9ment $x$ du domaine d&rsquo;interpr\u00e9tation tel que $\\text{Val}(\\Sigma, A\\cup{(X,x)}) = \\text{vrai}$.<\/li>\n<li>Si $\\Sigma$ est une formule et $X$ une variable non assign\u00e9es par $A$, alors $\\text{Val}(\\forall X ~ \\Sigma,A) = \\text{vrai}$ si et seulement si  pour tout \u00e9l\u00e9ment $x$ du domaine d&rsquo;interpr\u00e9tation, $\\text{Val}(\\Sigma, A\\cup{(X,x)}) = \\text{vrai}$.<\/li>\n<\/ul>\n<p>Le sens des quantificateurs est donc celui usuellement utilis\u00e9 en math\u00e9matique.<\/p>\n<p>En r\u00e9sum\u00e9, pour attribuer une valeur de v\u00e9rit\u00e9 \u00e0 une formule $\\Sigma$, il faut :<\/p>\n<ul>\n<li>Une interpr\u00e9tation, incluant un domaine d&rsquo;interpr\u00e9tation et une interpr\u00e9tation de tous les symboles fonctionnels et relationnels apparaissant dans $\\Sigma$.<\/li>\n<li>Une valuation des variables <strong>libres<\/strong> apparaissant dans $\\Sigma$.<\/li>\n<\/ul>\n<p>L&rsquo;interpr\u00e9tation d&rsquo;une <strong>formule close<\/strong> repose <strong>uniquement<\/strong> sur une interpr\u00e9tation de ses symboles fonctionnels et relationnels.<\/p>\n<p>Consid\u00e9rons l&rsquo;exemple suivant.<\/p>\n<p>$\\Sigma =$ $\\exists Y(\\forall X ~ \\underline{\\text{egal}(\\text{plus}(X,Y),X)}$ $\\to$ $\\neg \\underline{\\text{egal}(\\text{zero},Y)})$<\/p>\n<p>Cette formule est close. Sa valeur de v\u00e9rit\u00e9 d\u00e9pend uniquement de l&rsquo;interpr\u00e9tation de la signature $({\\text{zero}\/0, \\text{plus}\/2 },{\\underline{\\text{egal}}\/2 })$, c&rsquo;est \u00e0 dire du domaine d&rsquo;interpr\u00e9tation consid\u00e9r\u00e9 et du sens donn\u00e9 aux symboles $\\text{egal}$, $\\text{plus}$ et $\\text{zero}$.<\/p>\n<p>Pour certaines interpr\u00e9tations, la formule a la valeur $\\text{vrai}$ et pour d&rsquo;autre elle a la valeur $\\text{faux}$.<\/p>\n<p>Prenons l&rsquo;interpr\u00e9tation que nous avons d\u00e9j\u00e0 utilis\u00e9e section D.dec5.<\/p>\n<p><strong>Interpr\u00e9tation 1<\/strong> :<\/p>\n<ul>\n<li>Le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble $\\mathbb{N}$ des entiers naturels.<\/li>\n<li>Le symbole $\\text{zero}$ repr\u00e9sente l&rsquo;entier 0. (Attention, pas la valeur faux.)<\/li>\n<li>Le symbole $\\text{plus}$ repr\u00e9sente la fonction somme standard qui \u00e0 tout couple $(x,y)$ d&rsquo;entiers naturels associe $x+y$.<\/li>\n<li>Le symbole $\\text{egal}$ repr\u00e9sente la relation d&rsquo;\u00e9galit\u00e9 standard : $\\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l&rsquo;\u00e9galit\u00e9 entre entiers naturels.<\/li>\n<\/ul>\n<p>Quelle est la valeur de v\u00e9rit\u00e9 de $\\Sigma$  pour cette interpr\u00e9tation ?<\/p>\n<p>Pour le savoir, il nous faut d\u00e9terminer s&rsquo;il existe une valeur de $Y$  telle que&#8230;<\/p>\n<p>$\\Sigma =$ $\\underbrace{\\forall X ~ \\text{egal}(\\text{plus}(X,Y),X)}_ {\\sigma_1}$ $\\to$ $\\neg \\underbrace{\\text{egal}(\\text{zero},Y)}_ {\\sigma_2}$<\/p>\n<p>&#8230; s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$.<\/p>\n<p>Or pour $Y=1$, par exemple, $\\sigma_1$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$ (puisque pour cette valuation de $Y$, $\\sigma_1$ dit que pour tout $X$, on a $X+1=X$) et $\\sigma_2$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$, donc $\\sigma_1 \\to \\sigma_2$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$ (d&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$).<\/p>\n<p>On en conclut que notre interpr\u00e9tation donne la valeur $\\text{vrai}$ \u00e0 $\\Sigma$.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x8<\/h5>\n<p>On reprend la m\u00eame interpr\u00e9tation, mais une formule diff\u00e9rente :<\/p>\n<p>$\\Omega =$ $\\forall X(\\exists Y ~ \\text{egal}(X,Y) \\to \\text{egal}(\\text{zero},X))$<\/p>\n<p>Donnez la valeur de v\u00e9rit\u00e9 de $\\Omega$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On d\u00e9compose la formule comme ceci pour faciliter le raisonnement :<\/p>\n<p>$\\Omega =$ $\\forall X(\\underbrace{\\exists Y ~ \\text{egal}(X,Y)}_ {\\omega_1}$ $\\to$ $\\underbrace{\\text{egal}(\\text{zero},X)}_ {\\omega_2})$<\/p>\n<p>Pour $X=1$, la formule $\\omega_1$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$ puisqu&rsquo;il existe une valeur de $Y$, en l&rsquo;occurrence 1, qui satisfait l&rsquo;atome $\\text{egal}(X,Y)$, et $\\omega_2$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$, donc $\\omega_1 \\to \\omega_2$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$.<\/p>\n<p>Puisqu&rsquo;il existe au moins une valeur de $X$ qui falsifie $\\omega_1 \\to \\omega_2$ , $\\Omega$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec9 : Validit\u00e9 et coh\u00e9rence<\/h3>\n<p>On s&rsquo;int\u00e9resse uniquement aux formules <strong>closes<\/strong> de la logique du premier ordre.<\/p>\n<p>On dit qu&rsquo;une interpr\u00e9tation $I$ <strong>satisfait<\/strong> une formule $\\Sigma$ si et seulement si elle donne \u00e0 cette formule la valeur $\\text{vrai}$. Dans le cas contraire, on dit que $I$ <strong>falsifie<\/strong> $\\Sigma$. On appelle <strong>mod\u00e8le<\/strong> d&rsquo;une formule close $\\Sigma$ toute interpr\u00e9tation qui satisfait $\\Sigma$. Toute interpr\u00e9tation qui falsifie $\\Sigma$ est appel\u00e9e <strong>contre-mod\u00e8le<\/strong> de $\\Sigma$.<\/p>\n<p>Une formule close est une <strong>tautologie<\/strong>, ou formule <strong>valide<\/strong>, si et seulement si elle n&rsquo;admet aucun contre-mod\u00e8le. Autrement dit, la formule s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$ quels que soient le domaine d&rsquo;interpr\u00e9tation et le sens donn\u00e9 \u00e0 ses symboles relationnels et \u00e0 ses symboles fonctionnels. En quelque sorte, une telle formule est &quot;toujours vraie&quot;.<\/p>\n<p>Une formule close est <strong>coh\u00e9rente<\/strong> si et seulement si elle admet au moins un mod\u00e8le. Dans le cas contraire, elle est dite <strong>incoh\u00e9rente<\/strong>.<\/p>\n<p>Prenons comme exemple la formule $\\Sigma = \\forall X~ \\text{p}(X,X)$. Une interpr\u00e9tation de cette formule d\u00e9finit un domaine d&rsquo;interpr\u00e9tation et donne un sens au symbole relationnel $\\text{p}$. Consid\u00e9rons deux interpr\u00e9tations ayant pour domaine  ${1,2}$. Ces deux interpr\u00e9tations se diff\u00e9rencient donc uniquement par le sens donn\u00e9 au  symbole $\\text{p}$.<\/p>\n<p><strong>Interpr\u00e9tation<\/strong> $I_1$ :<\/p>\n<p>Voici trois repr\u00e9sentations de la m\u00eame interpr\u00e9tation $I_ 1$. Une seule est suffisante, mais c&rsquo;est l&rsquo;occasion  de voir les diff\u00e9rentes mani\u00e8res de repr\u00e9senter l&rsquo;interpr\u00e9tation d&rsquo;un symbole relationnel d&rsquo;arit\u00e9 2 lorsque le domaine d&rsquo;interpr\u00e9tation comporte relativement peu de valeurs.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd3.png\" alt=\"plfd3\"><\/p>\n<p>La premi\u00e8re repr\u00e9sentation est dite <strong>sagittale<\/strong>. Elle marque par une fl\u00e8che les couples $(x,y)$ pour lesquels $\\text{p}(x,y) = \\text{vrai}$. La deuxi\u00e8me repr\u00e9sentation donne ces m\u00eames couples sous la forme d&rsquo;une matrice avec le premier argument en ligne et le deuxi\u00e8me en colonne. La troisi\u00e8me repr\u00e9sentation est g\u00e9n\u00e9ralisable aux symboles relationnels d&rsquo;arit\u00e9 quelconque.<\/p>\n<p>Cette interpr\u00e9tation <strong>falsifie<\/strong> $\\Sigma$ puisque par exemple pour $X=1$, $\\text{p}(X,X)$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$.<\/p>\n<p><strong>Interpr\u00e9tation<\/strong> $I_2$ :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd4.png\" alt=\"plfd4\"><\/p>\n<p>Cette interpr\u00e9tation <strong>satisfait<\/strong> $\\Sigma$ puisque pour toutes les valeurs de $X$, $\\text{p}(X,X)$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$.<\/p>\n<hr>\n<p>La formule $\\Sigma$ est coh\u00e9rente, puisqu&rsquo;elle a au moins un mod\u00e8le, mais ce n&rsquo;est pas une tautologie car elle admet au moins un contre-mod\u00e8le.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x9<\/h5>\n<p>Donnez une interpr\u00e9tation qui falsifie et une qui satisfait la formule suivante :<\/p>\n<p>$\\Omega =$ $\\underbrace{(\\forall X \\exists Y ~ \\text{p}(X,Y))}_ {\\omega_1}$ $\\to$ $\\underbrace{(\\forall X \\exists Y ~ \\neg \\text{p}(X,Y))}_ {\\omega_2}$<\/p>\n<p>Les deux interpr\u00e9tations doivent avoir pour domaine l&rsquo;ensemble ${1,2}$. Commencez par rechercher un mod\u00e8le (r\u00e9ponse 1), puis un contre-mod\u00e8le (r\u00e9ponse 2).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il existe plusieurs mod\u00e8les. Par exemple, toute interpr\u00e9tation de $\\text{p}$ qui falsifie $\\omega_1$ est un mod\u00e8le de $\\Omega$ en vertu de la table de v\u00e9rit\u00e9 du connecteur $\\to$.<\/p>\n<p>Les repr\u00e9sentations sagittales de ces mod\u00e8les se caract\u00e9risent par une ou deux valeurs d&rsquo;o\u00f9 ne part aucune fl\u00e8che. Voici trois exemples.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd5.png\" alt=\"plfd5\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Un contre-mod\u00e8le, en vertu de la table de v\u00e9rit\u00e9 du connecteur $\\to$ (qu&rsquo;il vaut mieux avoir toujours \u00e0 port\u00e9e de main), doit satisfaire $\\omega_1$ et falsifier $\\omega_2$. Avec un domaine d&rsquo;interpr\u00e9tation de cardinal 2, sa repr\u00e9sentation sagittale se caract\u00e9rise par le fait que :<\/p>\n<ul>\n<li>de chaque valeur part au moins une fl\u00e8che,<\/li>\n<li>d&rsquo;au moins une valeur part 2 fl\u00e8ches. Voici trois exemples.<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/plfd6bis.png\" alt=\"plfd6bis\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>D.dec10 : Cons\u00e9quence logique<\/h3>\n<p>La cons\u00e9quence logique et l&rsquo;\u00e9quivalence logique sont d\u00e9finies exactement de la m\u00eame fa\u00e7on en logique propositionnelle et en logique du premier ordre.<\/p>\n<p>Une formule $\\Omega$ est <strong>cons\u00e9quence logique<\/strong> d&rsquo;une formule $\\Sigma$, i.e., $\\Sigma \\models \\Omega$ si et seulement si tout mod\u00e8le de $\\Sigma$ est un mod\u00e8le de $\\Omega$.<\/p>\n<p>Deux formules sont <strong>logiquement \u00e9quivalentes<\/strong> si et seulement si elles ont les m\u00eame mod\u00e8les.<\/p>\n<p>La grosse diff\u00e9rence entre la logique du premier ordre et la logique propositionnelle tient \u00e0 la notion de mod\u00e8le. En logique propositionnelle, un mod\u00e8le est simplement une valuation des variables qui satisfait la formule. En logique du premier ordre, un mod\u00e8le est une interpr\u00e9tation qui satisfait la formule. Une formule du premier ordre \u00e0 une infinit\u00e9 d&rsquo;interpr\u00e9tations diff\u00e9rentes, chacune constitu\u00e9e d&rsquo;un domaine (qui peut \u00eatre fini ou infini) et de fonctions donnant un sens \u00e0 chacun des symboles fonctionnel et relationnel utilis\u00e9s.<\/p>\n<p>En logique propositionnelle, comme en logique du premier ordre, d\u00e9terminer si une formule est cons\u00e9quence logique d&rsquo;une autre est de m\u00eame difficult\u00e9 que d\u00e9terminer si une formule est une tautologie ou que d\u00e9terminer si une formule est coh\u00e9rente.<\/p>\n<p>En logique propositionnelle, d\u00e9terminer si une formule est coh\u00e9rente ou si elle est valide est un probl\u00e8me <strong>NP-complet<\/strong>, pour lequel aucun algorithme efficace, au sens d&rsquo;une complexit\u00e9 en temps polynomiale, n&rsquo;est connu.<\/p>\n<p>En logique du premier ordre c&rsquo;est encore pire : le probl\u00e8me est <strong>ind\u00e9cidable<\/strong>. Aucun algorithme ne peut, pour toute formule plac\u00e9e en entr\u00e9e, d\u00e9terminer en un temps fini si cette formule est une tautologie. D\u00e9terminer si une formule est coh\u00e9rente est \u00e9galement ind\u00e9cidable.<\/p>\n<p>En pratique, il est possible de d\u00e9terminer si certaines formules sont valides ou sont coh\u00e9rentes en r\u00e9alisant des d\u00e9ductions.<\/p>\n<p>Par exemple, consid\u00e9rons la formule suivante :<\/p>\n<p>$\\Sigma =$ $\\underbrace{\\forall X ~ \\text{p}(X)}_ {\\sigma_1} \\to \\underbrace{ \\exists X ~ \\text{p}(X)}_ {\\sigma_2}$<\/p>\n<p>Il est \u00e9vident que $\\Sigma$ est une tautologie. En effet, si une interpr\u00e9tation $I$ est un mod\u00e8le de $\\sigma_1$, alors $\\text{p}(X)$, tel que d\u00e9fint par $I$, est $\\text{vrai}$ pour toute valeur $X$ du domaine d&rsquo;interpr\u00e9tation de $I$. Donc $\\text{p}(X)$ est vrai pour au moins une valeur $X$ du domaine d&rsquo;interpr\u00e9tation de $I$, donc $I$ est aussi un mod\u00e8le de $\\sigma_2$.<\/p>\n<p>Il existe des algorithmes permettant de d\u00e9terminer si certaines formules sont des tautologies en utilisant des ensembles de r\u00e8gles appel\u00e9s <strong>syst\u00e8mes de preuve<\/strong>. Cela rel\u00e8ve d&rsquo;un champ de l&rsquo;intelligence artificielle appel\u00e9 <strong>raisonnement automatique<\/strong>. Comme le probl\u00e8me sous-jacent est ind\u00e9cidable, de tels algorithmes ne s&rsquo;arr\u00eatent jamais et ne peuvent pas conclure pour <strong>certaines<\/strong> formules plac\u00e9es en entr\u00e9e. Mais il peuvent traiter certaines autres formules. Ces algorithmes sont qualifi\u00e9s de corrects parce que s&rsquo;ils s&rsquo;arr\u00eatent et fournissent un r\u00e9sultat (par exemple : la formule d&rsquo;entr\u00e9e est une tautologie), alors ce r\u00e9sultat est correct. Par contre, pour certaines formules, il ne s&rsquo;arr\u00eatent jamais. Si le programme ne s&rsquo;est pas arr\u00eat\u00e9 apr\u00e8s un certain temps, vous n&rsquo;avez aucun moyen de savoir s&rsquo;il va fournir une r\u00e9ponse plus tard ou si son ex\u00e9cution va se prolonger ind\u00e9finiment :slightly_smiling_face:. Et le probl\u00e8me, c&rsquo;est que m\u00eame dans les cas o\u00f9 le programme va s&rsquo;arr\u00eater en th\u00e9orie, en pratique l&rsquo;ex\u00e9cution peut \u00eatre d&rsquo;une dur\u00e9e astronomique, sans vous laisser aucune chance d&rsquo;avoir le r\u00e9sultat.<\/p>\n<h3>D.dec11 : Mod\u00e9lisation<\/h3>\n<p>La logique du premier ordre permet de formaliser des \u00e9nonc\u00e9s faisant intervenir des objets (les \u00e9l\u00e9ments du domaine d&rsquo;interpr\u00e9tation), des propri\u00e9t\u00e9s et des relations entre ces objets (les interpr\u00e9tations des symboles relationnels et des symboles fonctionnels).<\/p>\n<p>On dit qu&rsquo;une formule $\\Sigma$ <strong>mod\u00e9lise<\/strong> un \u00e9monc\u00e9 $E$ si et seulement si elle est satisfaite par les interpr\u00e9tations qui ne sont pas en contradiction avec $E$, et seulement pour ces interpr\u00e9tations.<\/p>\n<p>Prenons pour exemple l&rsquo;\u00e9nonc\u00e9 suivant :<\/p>\n<blockquote>\n<p>Tout humain qui poss\u00e8de un chien est anglophone.<\/p>\n<\/blockquote>\n<p>Cet \u00e9nonc\u00e9 est-il vrai ou faux ? Cela d\u00e9pend, pour commencer, du sens donn\u00e9 aux mots chien, humain, poss\u00e8de et anglophone. Mais admettons que nous leur donnions leur sens usuel. La valeur de v\u00e9rit\u00e9 de l&rsquo;\u00e9nonc\u00e9 d\u00e9pend du <strong>domaine d&rsquo;interpr\u00e9tation<\/strong>. S&rsquo;il s&rsquo;agit des \u00eatres vivants terrestres, alors clairement l&rsquo;\u00e9nonc\u00e9 est faux. Mais si on r\u00e9duit ce domaine aux \u00eatres vivant situ\u00e9s dans le village de Capel, en Angleterre, il n&rsquo;est pas impossible que l&rsquo;\u00e9nonc\u00e9 soit vrai. Et si le domaine d&rsquo;interpr\u00e9tation est l&rsquo;ensemble des \u00eatres vivants de l&rsquo;ile de Achi Kochi au Japon, o\u00f9 il est interdit de poss\u00e9der un chien, alors l&rsquo;\u00e9nonc\u00e9 est&#8230; vrai ! En effet, si personne ne poss\u00e8de de chien, alors il est vrai que toute personne humaine en poss\u00e9dant un parle anglais.<\/p>\n<p>Pour mod\u00e9liser cet \u00e9nonc\u00e9 par une formule du premier ordre, il nous faut d\u00e9finir les symboles relationnels et symboles fonctionnels utilis\u00e9s. Dans la suite, nous ne travaillerons qu&rsquo;avec des symboles relationnels pour simplifier les exercices, compte tenu du faible nombre d&rsquo;heures d&rsquo;enseignement consacr\u00e9es \u00e0 la logique du premier ordre.<\/p>\n<p>Ici, nous utiliserons les symboles relationnels suivants : $\\text{hum}\/1$, $\\text{chien}\/1$, $\\text{angl}\/1$ et $\\text{poss}\/2$.<\/p>\n<p>L&rsquo;\u00e9nonc\u00e9 peut alors \u00eatre mod\u00e9lis\u00e9 ainsi :<\/p>\n<p>$\\forall X$ $[\\underbrace{(\\text{hum}(X) \\wedge \\underbrace{\\exists Y~(\\text{chien}(Y) \\wedge \\text{poss}(X,Y)}_ {\\mu})}_ {\\sigma}$ $\\to$ $\\underbrace{\\text{angl}(X)}_{\\omega} ]$<\/p>\n<p>La sous-formule $\\omega$ mod\u00e9lise la propri\u00e9t\u00e9 : $X$ est anglophone.<\/p>\n<p>La sous formule $\\mu$ mod\u00e9lise la propri\u00e9t\u00e9 : $X$ poss\u00e8de un chien.<\/p>\n<p>La sous-formule $\\sigma$ mod\u00e9lise la propri\u00e9t\u00e9 : $X$ est un humain qui poss\u00e8de un chien.<\/p>\n<p>L&rsquo;utilisation du symbole $\\to$ traduit l&rsquo;implication sous-jacente \u00e0 l&rsquo;\u00e9nonc\u00e9 : &quot;Si $X$ est un humain qui poss\u00e8de un chien, alors $X$ est anglophone&quot;.<\/p>\n<p>Le quantificateur $\\forall$ traduit le fait que pour satisfaire l&rsquo;\u00e9nonc\u00e9, il faut que <strong>tout<\/strong> humain poss\u00e9dant un chien soit anglophone.<\/p>\n<p>Le quantificateur $\\exists$ traduit la condition &quot;$X$ poss\u00e8de <strong>au moins un<\/strong> chien&quot;, i.e., il existe au moins un chien poss\u00e9d\u00e9 par $X$.<\/p>\n<h5>Exercice de d\u00e9couverte D.dec.x10<\/h5>\n<p>Nous reprenons la formule&#8230;<\/p>\n<p>$\\forall X$ $[\\underbrace{(\\text{hum}(X) \\wedge \\underbrace{\\exists Y~(\\text{chien}(Y) \\wedge \\text{poss}(X,Y)}_ {\\mu})}_ {\\sigma}$ $\\to$ $\\underbrace{\\text{angl}(X)}_{\\omega} ]$<\/p>\n<p>&#8230;qui mod\u00e9lise l&rsquo;\u00e9nonc\u00e9 :<\/p>\n<blockquote>\n<p>Tout humain qui poss\u00e8de un chien est anglophone.<\/p>\n<\/blockquote>\n<p>Imaginons une plan\u00e8te o\u00f9 il n&rsquo;y a aucun humain, o\u00f9 nul \u00eatre vivant ne peut \u00eatre \u00e0 la fois une salade et un chien, et qui est peupl\u00e9e uniquement :<\/p>\n<ul>\n<li>d&rsquo;un chien anglophone nomm\u00e9 $\\alpha$, qui ne poss\u00e8de rien.<\/li>\n<li>d&rsquo;une salade nomm\u00e9e $\\beta$ (son vrai nom est $\\beta$via) qui ne parle pas anglais et poss\u00e8de le chien et rien d&rsquo;autre.<\/li>\n<\/ul>\n<p>La situation sur cette plan\u00e8te est-elle en contradiction avec l&rsquo;\u00e9nonc\u00e9 $E$ ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, la situation est compatible avec l&rsquo;\u00e9nonc\u00e9 puisqu&rsquo;il n&rsquo;y a pas d&rsquo;humain sur la plan\u00e8te.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donnez l&rsquo;interpr\u00e9tation correspondante (dont le domaine d&rsquo;interpr\u00e9tation est ${\\alpha, \\beta}$).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une repr\u00e9sentation graphique de l&rsquo;interpr\u00e9tation.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd7.png\" alt=\"plfd7\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Cette interpr\u00e9tation est-elle un mod\u00e8le de $\\Sigma$ ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Quel que soit la valeur de $X$, la sous-formule $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$ donc $\\sigma \\to \\omega$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$ (d&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$).<\/p>\n<p>L&rsquo;interpr\u00e9tation est bien un mod\u00e8le de $\\Sigma$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Activit\u00e9 d&rsquo;entra\u00eenement D.ent<\/h2>\n<p>Chacune des deux it\u00e9rations propose un panel d&rsquo;exercices couvrant les comp\u00e9tences qui seront \u00e9valu\u00e9es \u00e0 l&rsquo;examen.<\/p>\n<h3>It\u00e9ration D.ent1<\/h3>\n<h4>Exercice d&rsquo;entrainement D.ent1.1<\/h4>\n<p>Soit la formule :<\/p>\n<p>$\\Sigma = \\forall X \\exists Y$ $\\underbrace{[\\underbrace{(p(X) \\wedge p(Y))}_ {\\sigma_1} \\to \\underbrace{(q(X) \\vee q(Y))}_ {\\sigma_2}]}_ {\\sigma}$<\/p>\n<p>L&rsquo;interpr\u00e9tation suivante est-elle un mod\u00e8le de $\\Sigma$ ? (Les valeurs entour\u00e9es sont celles qui satisfont l&rsquo;interpr\u00e9tation du symbole relationnel d&rsquo;arit\u00e9 1 mentionn\u00e9 au dessus.)<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd8.png\" alt=\"plfd8\"><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les questions auxquelles il faut r\u00e9pondre pour conclure sont :<\/p>\n<ol>\n<li>Pour $X=1$, existe-t-il une valeur de $Y$ telle que $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$  ?<\/li>\n<li>Pour $X=2$, existe-t-il une valeur de $Y$ telle que $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$  ?<\/li>\n<li>Pour $X=3$, existe-t-il une valeur de $Y$ telle que $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$  ?<\/li>\n<li>Pour $X=4$, existe-t-il une valeur de $Y$ telle que $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{vrai}$  ?<\/li>\n<\/ol>\n<p>Si la r\u00e9ponse \u00e0 ces 4 questions est positive, alors l&rsquo;interpr\u00e9tation satisfait $\\Sigma$ (i.e., est un mod\u00e8le de $\\Sigma$), sinon elle la falsifie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>La valeur $Y=3$ permet de r\u00e9pondre positivement aux 4 questions. En effet, avec cette valeur de $Y$,  $p(Y)$ est faux donc $\\sigma_1$ est faux, donc $\\sigma$ est vrai.<\/p>\n<p>L&rsquo;interpr\u00e9tation satisfait $\\Sigma$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donnez un contre-mod\u00e8le de $\\Sigma$ ayant le m\u00eame domaine mais une interpr\u00e9tation diff\u00e9rente des symboles relationnels $p$ et $q$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il faut que pour au moins une valeur de $X$, par exemple $X=1$, $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$ pour toutes les valeurs possibles de $Y$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une solution simple :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd9.png\" alt=\"plfd9\"><\/p>\n<p>Comme $p$ est toujours interpr\u00e9t\u00e9 \u00e0 $\\text{vrai}$ et $q$ \u00e0 $\\text{faux}$, $\\sigma$ s&rsquo;interpr\u00e8te \u00e0 $\\text{faux}$ pour toute valeur de $X$ et toute valeur de $Y$, donc l&rsquo;interpr\u00e9tation falsifie $\\Sigma$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.2<\/h4>\n<p>Soit les formules suivantes :<\/p>\n<ul>\n<li>$\\Sigma_1 = \\forall X ~ r(X,X)$<\/li>\n<li>$\\Sigma_2 =$ $\\forall X \\forall Y (r(X,Y) \\to r(Y,X))$<\/li>\n<li>$\\Sigma_3$ $=$ $\\forall X \\forall Y \\forall Z$ $(~[(r(X,Y) \\wedge r(Y,Z)] \\to r(X,Z)~)$<\/li>\n<\/ul>\n<p>L&rsquo;interpr\u00e9tation suivante est-elle un mod\u00e8le de $\\Sigma_1$ ? de $\\Sigma_2$ ? de $\\Sigma_3$ ?<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd10.png\" alt=\"plfd10\"><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>L&rsquo;interpr\u00e9tation satisfait $\\Sigma_1$ puisqu&rsquo;une fl\u00e8che relie chaque \u00e9l\u00e9ment \u00e0 lui m\u00eame.<\/p>\n<p>Elle ne satisfait pas $\\Sigma_2$ car $r(d,e)$ est vrai alors que $r(e,d)$ est faux.<\/p>\n<p>Elle ne satisfait pas non plus $\\Sigma_3$ car $r(e,c)$ et $r(c,d)$ sont vrai alors que $r(e,d)$ est faux.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Proposez une modification minimale (en termes de nombre d&rsquo;arcs ajout\u00e9s ou enlev\u00e9s) pour que l&rsquo;interpr\u00e9tation satisfasse les trois formules.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd11.png\" alt=\"plfd11\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.3<\/h4>\n<p>Donnez une interpr\u00e9tation $I_1$ qui satisfait (R\u00e9ponse 1) et une interpr\u00e9tation $I_2$ qui falsifie (R\u00e9ponse 2) la formule suivante :<\/p>\n<p>$\\Omega = [\\forall X \\exists Y~ p(X,Y)]$ $\\to$ $[\\exists Y \\forall X~ p(X,Y)]$<\/p>\n<p>Ces deux interpr\u00e9tations doivent avoir pour domaine ${1,2}$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Une interpr\u00e9tation dans laquelle $p$ est toujours vrai est un mod\u00e8le de la formule.<\/p>\n<p>$p(1,1) = p(1,2)$ $=$ $p(2,1) = p(2,2)$ $=$ $\\text{vrai}$<\/p>\n<p>Mais il y en a bien d&rsquo;autres, comme par exemple celle o\u00f9 $p$ est toujours faux.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;IndiceR\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\Omega = \\underbrace{[\\forall X \\exists Y~ p(X,Y)]}_ {\\omega_1}$ $\\to$ $\\underbrace{[\\exists Y \\forall X~ p(X,Y)]}_ {\\omega_2}$<\/p>\n<p>Pour falsifier $\\Omega$, Il faut une interpr\u00e9tation qui satisfait $\\omega_1$ et qui falsifie $\\omega_2$. Pour que $\\omega_1$ soit vrai, il faut, sur le diagramme sagittal repr\u00e9sentant l&rsquo;intrepr\u00e9tation de $p$, qu&rsquo;au moins une fl\u00e8che parte de chaque valeur du domaine d&rsquo;interpr\u00e9tation. Et pour falsifier $\\omega_2$ ?<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici deux exemples de contre-mod\u00e8les de $\\Omega$. Il me semble que ce sont les deux seuls.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd14.png\" alt=\"plfd14\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.4<\/h4>\n<p>Soient les 2 formules suivantes :<\/p>\n<ul>\n<li>$\\Omega_1 = \\exists Y \\forall X~ p(X,Y)$<\/li>\n<li>$\\Omega_2 = \\exists Y \\forall X~ p(Y,X)$<\/li>\n<\/ul>\n<p>Quel crit\u00e8re doit respecter la repr\u00e9sentation sagittale de l&rsquo;interpr\u00e9tation du symbole relationnel $p$ pour que $\\Omega_1$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de fl\u00e8ches et avec le domaine ${1,2,3}$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il doit y avoir une valeur recevant une fl\u00e8che provenant de toutes les valeurs (y compris elle-m\u00eame).<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd15.png\" alt=\"plfd15\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel crit\u00e8re doit respecter la repr\u00e9sentation sagittale de l&rsquo;interpr\u00e9tation du symbole relationnel $p$ pour que $\\Omega_2$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de fl\u00e8ches et avec le domaine ${1,2,3}$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il vaut au moins une valeur de laquelle partent des fl\u00e8ches allant vers toutes les autres valeurs, y compris elle-m\u00eame.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd16.png\" alt=\"plfd16\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>La formule $\\Omega_1 \\leftrightarrow \\Omega_2$ est-elle une tautologie ? Justifiez votre r\u00e9ponse.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, ce n&rsquo;est pas une tautologie car $\\Omega_1$ et $\\Omega_2$ n&rsquo;ont pas les m\u00eame mod\u00e8les. Par exemple, les mod\u00e8les de $\\Omega_1$  donn\u00e9s en r\u00e9ponse \u00e0 la premi\u00e8re question ne sont pas des mod\u00e8les de $\\Omega_2$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.5<\/h4>\n<p>Mod\u00e9lisez la phrase suivante par une formule de la logique du premier ordre.<\/p>\n<blockquote>\n<p>Il existe au moins un plombier riche.<\/p>\n<\/blockquote>\n<p>Les symboles relationnels sont $\\text{plombier}\/1$ et $\\text{riche}\/1$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\Sigma = \\exists X~ (\\text{plombier}(X) \\wedge \\text{riche}(X))$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Pourquoi la formule suivante n&rsquo;est-elle <strong>pas<\/strong> une mod\u00e9lisation correcte de la phrase ?<\/p>\n<p>$\\Omega =$ $\\exists X$ $(\\underbrace{\\text{plombier}(X) \\to \\text{riche}(X)}_{\\omega})$<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il suffit qu&rsquo;un \u00e9l\u00e9ment du domaine d&rsquo;interpr\u00e9tation ne soit pas plombier pour que $\\Omega$ soit satisfaite, m\u00eame si aucun plombier n&rsquo;est riche.<\/p>\n<p>Par exemple, consid\u00e9rons l&rsquo;interpr\u00e9tation $I$\b suivante :<\/p>\n<pre><code>Domaine : {donald, picsou}\nriche(donald) = faux, riche(picsou) = vrai\nplombier(donald) = vrai, plombier(picsou) = faux\n<\/code><\/pre>\n<p>Clairement, cette interpr\u00e9tation n&rsquo;est pas compatible avec l&rsquo;\u00e9nonc\u00e9 et elle falsifie $\\Sigma$. Mais elle satisfait $\\Omega$ car il existe une valeur du domaine, en l&rsquo;occurrence <code>picsou<\/code>, qui satisfait $\\omega$. ($\\text{faux} \\to \\text{vrai}$ s&rsquo;\u00e9value \u00e0 $\\text{vrai} $ d&rsquo;apr\u00e8s le table de v\u00e9rit\u00e9 du connecteur $\\to$.)<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Mod\u00e9lisez maintenant la phrase :<\/p>\n<blockquote>\n<p>Tous les plombiers sont riches.<\/p>\n<\/blockquote>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\Theta = \\forall X~ (\\text{plombier}(X) \\to \\text{riche}(X))$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Pourquoi la formule suivante n&rsquo;est-elle <strong>pas<\/strong> une mod\u00e9lisation correcte de la phrase ?<\/p>\n<p>$\\Lambda = \\forall X$ $(\\underbrace{\\text{plombier}(X) \\wedge \\text{riche}(X)}_{\\omega})$<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>La formule $\\Lambda$ est satisfaite si et seulement si tous les \u00e9l\u00e9ments du domaine d&rsquo;interpr\u00e9tation sont plombiers et riches, ce qui n&rsquo;est pas le cas de la formule $\\Theta$.<\/p>\n<p>Voici une interpr\u00e9tation qui satisfait $\\Theta$ mais qui falsifie $\\Lambda$.<\/p>\n<pre><code>Domaine : {donald, picsou}\nriche(donald) = faux, riche(picsou) = vrai\nplombier(donald) = faux, plombier(picsou) = vrai\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.6<\/h4>\n<p>Mod\u00e9lisez la phrase suivante par une formule de la logique du premier ordre.<\/p>\n<blockquote>\n<p>Nul n&rsquo;a assassin\u00e9 un souverain auquel il \u00e9tait fid\u00e8le.<\/p>\n<\/blockquote>\n<p>Les symboles relationnels sont $\\text{souv}\/1$, $\\text{ass}\/2$ et $\\text{fid}\/2$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Une solution peut avoir la structure suivante :<\/p>\n<p>$\\Omega = \\neg \\exists X[\\underbrace{~\\exists S(~ ~\\sigma ~ ~)~}_{\\omega}]$<\/p>\n<p>Supposons, pour faciliter le raisonnement, que le domaine d&rsquo;interpr\u00e9tation soit un ensemble de personnes.  $\\Omega$ se pr\u00e9sente comme la n\u00e9gation d&rsquo;une formule qui mod\u00e9lise &quot;Au moins une personne a assassin\u00e9 un souverain auquel elle \u00e9tait fid\u00e8le&quot;.<\/p>\n<p>La sous-formule $\\omega$ mod\u00e9lise : &quot;Il existe un souverain auquel $X$ \u00e9tait fid\u00e8le et qui a \u00e9t\u00e9 assassin\u00e9 par $X$&quot;.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\neg \\exists X$ $[~\\exists S(\\text{souv}(S) \\wedge \\text{fid}(X,S) \\wedge \\text{ass}(X,S))~]$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.6<\/h4>\n<p>Soit la formule suivante :<\/p>\n<p>$\\Sigma = $ $\\forall X$ $[\\exists Y~p(X,Y) \\to \\exists Y~q(X,Y)]$<\/p>\n<p>Parmi les interpr\u00e9tations suivantes ayant pour domaine ${1,2}$, lesquelles sont des mod\u00e8les de $\\Sigma$ ?<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd18.png\" alt=\"plfd18\"><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Pour que l&rsquo;interpr\u00e9tation soit un mod\u00e8le de $\\Sigma$, il faut que pour toute valeur $X$ du domaine d&rsquo;interpr\u00e9tation,<\/p>\n<ul>\n<li>soit aucune fl\u00e8che ne parte de $X$ dans la repr\u00e9sentation sagittale de $p$,<\/li>\n<li>soit une fl\u00e8che parte de $X$ dans la repr\u00e9sentation sagittale de $q$.<\/li>\n<\/ul>\n<p>Les interpr\u00e9tations qui r\u00e9pondent \u00e0 ce crit\u00e8re sont celles num\u00e9rot\u00e9es 1 et 3.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent1.7<\/h4>\n<p>On d\u00e9finit une relation $r$ sur une ensemble $D$ par un ensemble de couples d&rsquo;\u00e9l\u00e9ments de $D$ (fl\u00e8ches sur la repr\u00e9sentation sagittale).<\/p>\n<p>La relation <strong>compl\u00e9mentaire<\/strong> d&rsquo;une relation $r$ est d\u00e9finie par l&rsquo;ensemble :<\/p>\n<p>{$(x,y) \\in D \\times D$, $(x,y) \\notin r$}<\/p>\n<p>Mod\u00e9lisez la propri\u00e9t\u00e9&#8230;<\/p>\n<blockquote>\n<p>$q$ est la relation compl\u00e9mentaire de $r$<\/p>\n<\/blockquote>\n<p>&#8230;en utilisant les symboles de pr\u00e9dicats $r\/2$ et $q\/2$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\forall X \\forall Y$ $[r(X,Y) \\leftrightarrow \\neg q(X,Y)]$<\/p>\n<p>On peut aussi l&rsquo;\u00e9crire avec deux implications :<\/p>\n<p>$\\forall X \\forall Y$ $[r(X,Y) \\to \\neg q(X,Y)]$ $\\wedge$ $[\\neg r(X,Y) \\to q(X,Y)]$<\/p>\n<p>Ou encore :<\/p>\n<p>$\\forall X \\forall Y$ $[r(X,Y) \\to \\neg q(X,Y)]$ $\\wedge$ $[\\neg q(X,Y) \\to r(X,Y)]$<\/p>\n<p>Toutes ces formules sont logiquement \u00e9quivalentes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>It\u00e9ration D.ent2<\/h3>\n<h4>Exercice d&rsquo;entrainement D.ent2.1<\/h4>\n<p>Soit la formule :<\/p>\n<p>$\\Sigma =$ $\\exists Y \\forall X$ $\\underbrace{[\\underbrace{(p(X) \\wedge q(Y))}_ {\\sigma_1} \\to \\underbrace{(p(X) \\vee q(Y))}_ {\\sigma_2}]} _{\\sigma}$<\/p>\n<p>L&rsquo;interpr\u00e9tation suivante est-elle un mod\u00e8le de $\\Sigma$ ? (Les valeurs entour\u00e9es sont celles qui satisfont l&rsquo;interpr\u00e9tation du symbole relationnel d&rsquo;arit\u00e9 1 mentionn\u00e9 au dessus.)<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd20.png\" alt=\"plfd20\"><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les questions auxquelles il faut r\u00e9pondre pour conclure sont :<\/p>\n<ol>\n<li>Pour $Y=1$, $\\sigma$ s&rsquo;interpr\u00e8te-t-elle \u00e0 $\\text{vrai}$ pour toutes les valeurs de $X$  ?<\/li>\n<li>Pour $Y=2$, $\\sigma$ s&rsquo;interpr\u00e8te-t-elle \u00e0 $\\text{vrai}$ pour toutes les valeurs de $X$  ?<\/li>\n<li>Pour $Y=3$, $\\sigma$ s&rsquo;interpr\u00e8te-t-elle \u00e0 $\\text{vrai}$ pour toutes les valeurs de $X$  ?<\/li>\n<li>Pour $Y=4$, $\\sigma$ s&rsquo;interpr\u00e8te-t-elle \u00e0 $\\text{vrai}$ pour toutes les valeurs de $X$  ?<\/li>\n<\/ol>\n<p>Si la r\u00e9ponse \u00e0 <strong>une<\/strong> de ces 4 questions est positive, alors l&rsquo;interpr\u00e9tation satisfait $\\Sigma$ (i.e., est un mod\u00e8le de $\\Sigma$), sinon elle le falsifie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Par chance, on peut r\u00e9pondre oui \u00e0 la question 1. Si $Y=1$ alors $q(Y)$ est vrai donc $\\sigma_2$ est vraie, donc, d&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$, $\\sigma$ est vraie. (La seule mani\u00e8re de rendre fausse une formule du type $\\omega \\to \\mu$ est que $\\omega$ soit vraie et $\\mu$ soit fausse.)<\/p>\n<p>L&rsquo;interpr\u00e9tation satisfait $\\Sigma$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent2.2<\/h4>\n<p>Soit la formule :<\/p>\n<p>$\\Sigma =$ $[\\forall X(g(X) \\vee h(X))]$ $\\to$ $([\\forall X ~ g(X)] \\vee [\\forall X ~ h(X)])$<\/p>\n<p>Donnez une interpr\u00e9tation $I_1$ qui satisfait $\\Sigma$ (R\u00e9ponse 1) et une interpr\u00e9tation $I_2$ qui falsifie $\\Sigma$ (R\u00e9ponse 2). ces deux interpr\u00e9tations doivent avoir pour domaine ${1,2}$.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Pour $I_1$, on peut prendre par exemple l&rsquo;interpr\u00e9tation dans laquelle $g$ et $h$ sont toujours interpr\u00e9t\u00e9s \u00e0 $\\text{vrai} $ :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd12.png\" alt=\"plfd12\"><\/p>\n<p>Mais celle ou les deux symboles relationnels sont toujours interpr\u00e9t\u00e9s \u00e0 $\\text{faux}$ convient aussi, et il y en a d&rsquo;autres qui satisfont la formule, incluant toutes celles o\u00f9 $g$ est toujours vrai et celles ou $h$ est toujours vrai.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici un exemple d&rsquo;interpr\u00e9tation qui falsifie $\\Sigma$ :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd13.png\" alt=\"plfd13\"><\/p>\n<p>En effet, cette interpr\u00e9tation satisfait la sous-formule de gauche $\\forall X(g(X) \\vee h(X))$, mais pas la sous formule de droite $[\\forall X ~ g(X)] \\vee [\\forall X ~ h(X)]$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent2.3<\/h4>\n<p>Soit la formule suivante :<\/p>\n<p>$\\Omega =$ $\\underbrace{[\\exists X \\forall Y~ p(X,Y)]}_ {\\omega_1}$ $\\to$ $\\underbrace{[\\forall Y \\exists X~ p(X,Y)]}_ {\\omega_2}$<\/p>\n<p>Quel crit\u00e8re doit respecter la repr\u00e9sentation sagittale de l&rsquo;interpr\u00e9tation du symbole relationnel $p$ pour que $\\omega_1$ soit satisfaite ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il faut qu&rsquo;il y ait au moins une valeur d&rsquo;o\u00f9 partent des fl\u00e8ches vers toutes les valeurs y compris elle-m\u00eame.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel crit\u00e8re doit respecter la repr\u00e9sentation sagittale de l&rsquo;interpr\u00e9tation du symbole relationnel $p$ pour que $\\omega_2$ soit satisfaite ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il faut que chaque valeur soit la destination d&rsquo;au moins une fl\u00e8che (pouvant provenir d&rsquo;une autre valeur ou d&rsquo;elle m\u00eame).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Existe-t-il une interpr\u00e9tation qui satisfait $\\omega_1$ et falsifie $\\omega_2$ ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, car s&rsquo;il y a une valeur du domaine d&rsquo;interpr\u00e9tation d&rsquo;o\u00f9 part une fl\u00e8che vers toutes les autres valeurs, alors au moins une fl\u00e8che arrive \u00e0 chaque valeur, donc tout mod\u00e8le de $\\omega_1$ satisfait aussi $\\omega_2$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>$\\Omega$ est-elle une tautologie ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, car pour toute interpr\u00e9tation $I$,<\/p>\n<ul>\n<li>soit $I$ est mod\u00e8le de $\\omega_1$, et donc aussi de $\\omega_2$ (d&rsquo;apr\u00e8s les r\u00e9ponses aux questions pr\u00e9c\u00e9dentes), et donc est mod\u00e8le de $\\Omega$,<\/li>\n<li>soit $I$ falsifie $\\omega_1$ et donc (d&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$), satisfait $\\Omega$.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<p>Si on change le sens du connecteur $\\to$, la formule devient :<\/p>\n<p>$\\Theta =$ $\\underbrace{[\\forall Y \\exists X~ p(X,Y)]}_ {\\omega_2}$ $\\to$ $ \\underbrace{[\\exists X \\forall Y~ p(X,Y)]}_ {\\omega_1}$<\/p>\n<p>Cette nouvelle formule est-elle une tautologie ? Autrement dit tout mod\u00e8le de $\\omega_2$ est-il un mod\u00e8le de $\\omega_1$ ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non. Par exemple, les interpr\u00e9tations suivantes satisfont $\\omega_2$ et falsifient $\\omega_1$.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd17.png\" alt=\"plfd17\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent2.4<\/h4>\n<p>Mod\u00e9lisez la phrase suivante par une formule de la logique du premier ordre.<\/p>\n<blockquote>\n<p>Tous les humains qui poss\u00e8dent une voiture ont un chien.<\/p>\n<\/blockquote>\n<p>Les symboles relationnels sont $\\text{hum}\/1$ (pour humain), $\\text{chien}\/1$, $\\text{voit}\/1$ (pour voiture) et $\\text{poss}\/2$ (pour poss\u00e8de).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici un squelette de formule mod\u00e9lisant la phrase.<\/p>\n<p>$\\forall X[~(\\text{hum}(X) \\wedge (~ ~ \\sigma_1 ~ ~)~ ) \\to (~ ~ \\sigma_2 ~ ~)~]$<\/p>\n<p>La sous-formule $\\sigma_1$ mod\u00e9lise &quot;$X$ poss\u00e8de une voiture&quot; et la sous-formule $\\sigma_2$ mod\u00e9lise &quot;$X$ poss\u00e8de un chien&quot;.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\forall X\\left[\\right.$ $(\\text{hum}(X)$ $\\wedge$ $\\exists V( [\\text{voit}(V) \\wedge \\text{poss}(X,V))] )$ $\\to$ $[\\exists C( \\text{chien}(C) \\wedge \\text{poss}(X,C))]$ $\\left. \\right]$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent2.5<\/h4>\n<p>Soit la formule suivante :<\/p>\n<p>$\\Sigma =$ $\\forall X$ $\\forall Y$ $[p(X,Y) \\to (q(X) \\wedge \\neg q(Y))]$<\/p>\n<p>On consid\u00e8re uniquement les interpr\u00e9tations ayant pour domaine ${1,2}$. Donnez deux mod\u00e8les de $\\Sigma$ pour lesquels la repr\u00e9sentation sagittale de $p$ comporte exactement une fl\u00e8che.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfd19.png\" alt=\"plfd19\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Combien y a-t-il de mod\u00e8les pour lesquels la repr\u00e9sentation sagittale de $p$ comporte au moins deux fl\u00e8ches ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Aucune. Pour satisfaire $\\Sigma$, il faut que si une fl\u00e8che relie une valeur $X$ \u00e0 une valeur $Y$, alors $q(X)=\\text{vrai}$ et $q(Y)=\\text{faux}$.<\/p>\n<p>Si une fl\u00e8che relie une valeur \u00e0 elle-m\u00eame, alors aucune interpr\u00e9tation de $q$ ne permet de satisfaire la formule car il faudrait que pour une telle valeur, $q$ soit \u00e0 la foi vrai et faux. Il reste une seule autre possibilit\u00e9, qui est l&rsquo;interpr\u00e9tation dans laquelle $p(1,2) = \\text{vrai}$, $p(2,1) = \\text{vrai}$, $p(1,1) = \\text{faux}$, $p(2,2) = \\text{faux}$, mais aucune interpr\u00e9tation de $q$ ne permet de satisfaire $\\Sigma$ avec cette interpr\u00e9tation de $p$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Combien y a-t-il de mod\u00e8les pour lesquels la repr\u00e9sentation sagittale de $p$ ne comporte aucune fl\u00e8che ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il y en a 4. En effet, si $p$ est toujours faux alors la sous-formule entre crochet est satsifaite quelle que soit l&rsquo;interpr\u00e9tation de $q$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement D.ent2.6<\/h4>\n<p>Mod\u00e9lisez l&rsquo;\u00e9nonc\u00e9 suivant :<\/p>\n<blockquote>\n<p>Tout nombre pair sup\u00e9rieur \u00e0 2 est la somme de 2 nombres premiers.<\/p>\n<\/blockquote>\n<p>On appelle nombre toute valeur du domaine d&rsquo;interpr\u00e9tation. Les symboles relationnels \u00e0 utiliser sont les suivants :<\/p>\n<ul>\n<li>$\\text{pair}\/1$ : $\\text{pair}(X)$ mod\u00e9lise &quot;$X$ est pair&quot;<\/li>\n<li>$\\text{prem}\/1$ : $\\text{prem}(X)$ mod\u00e9lise &quot;$X$ est premier&quot;<\/li>\n<li>$\\text{sup2}\/1$ : $\\text{sup2}(X)$ mod\u00e9lise &quot;$X$ est sup\u00e9rieur \u00e0 2&quot;<\/li>\n<li>$\\text{add}\/3$ : $\\text{add}(X,Y,Z)$ mod\u00e9lise &quot;$Z$ est la somme de $X$ et $Y$&quot;<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Une solution peut avoir la forme suivante, dans laquelle la sous-formule $\\sigma$ mod\u00e9lise &quot;$X$ est un nombre pair sup\u00e9rieur \u00e0 2&quot; et la sous-formule $\\omega$ mod\u00e9lise &quot;$X$ est la somme de 2 nombre premiers&quot;, c&rsquo;est \u00e0 dire &quot;Il existe deux nombres premiers $A$ et $B$ tels que $X$ est la somme de $A$ et $B$.<\/p>\n<p>$\\forall X$ $[$ $(~ ~ \\sigma ~ ~)$ $\\to$ $(~ ~ \\omega ~ ~)$  $]$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>$\\forall X$ $[$ $(\\text{pair}(X) \\wedge \\text{sup2}(X))$ $\\to$ $($ $\\exists A$  $\\exists B $ $[$ $\\text{prem}(A)$ $\\wedge$ $\\text{prem}(B)$ $\\wedge$ $\\text{add}(A,B,X)$ $]$  $)$  $]$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-289","post","type-post","status-publish","format-standard","hentry","category-general","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/289","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=289"}],"version-history":[{"count":10,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/289\/revisions"}],"predecessor-version":[{"id":346,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/289\/revisions\/346"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=289"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=289"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}