{"id":282,"date":"2022-02-26T12:05:11","date_gmt":"2022-02-26T12:05:11","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=282"},"modified":"2022-02-28T19:35:04","modified_gmt":"2022-02-28T19:35:04","slug":"plf-partie-c","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/plf-partie-c\/","title":{"rendered":"PLF : Partie C"},"content":{"rendered":"\n<div class=\"wp-block-jetpack-markdown\"><h1>Programmation logique et fonctionnelle &#8211; partie C<\/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 propositionnelle<\/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 C.dec<\/h2>\n<h3>Introduction<\/h3>\n<p>La logique a pour r\u00f4le premier de donner un fondement math\u00e9matique aux notions d&rsquo;\u00e9nonc\u00e9s, de raisonnement, de d\u00e9duction et de preuve.<\/p>\n<p>La logique proportionnelle, que nous abordons dans cette premi\u00e8re partie, s&rsquo;int\u00e9resse aux \u00e9nonc\u00e9s dont les variables peuvent prendre deux valeurs possibles, vrai ou faux, ne sont pas quantifi\u00e9es (les formules n&rsquo;ont pas de quantificateurs tels que $\\forall$ et $\\exists$), et sont construites \u00e0 l&rsquo;aide de connecteurs logiques (et, ou, non etc.).<\/p>\n<p>Il s&rsquo;agit donc de formules tr\u00e8s simples, ayant une puissance d&rsquo;expression limit\u00e9e, mais qui permettent d\u00e9j\u00e0 de mod\u00e9liser des probl\u00e8mes pos\u00e9s dans de nombreux domaines comme par exemple la v\u00e9rification de circuits \u00e9lectroniques, la conception d&#8217;emplois du temps, l&rsquo;ordonnancement de t\u00e2ches, l&rsquo;allocation de ressources, ou encore la gestions de d\u00e9pendances dans des configurations logicielles.<\/p>\n<h3>C.dec1 : Les formules<\/h3>\n<p>Les <strong>formules de la logique propositionnelle<\/strong> sont constitu\u00e9es des symboles suivants :<\/p>\n<ul>\n<li>Les <strong>constantes<\/strong> $\\top$, appel\u00e9e <strong>symbole vrai<\/strong> et $\\bot$, appel\u00e9 <strong>symbole faux<\/strong>.<\/li>\n<li>Les <strong>variables<\/strong>, que nous repr\u00e9senterons par des lettres minuscules ou des mots, \u00e9ventuellement avec des indices, comme par exemple $a, b, x_1, x_2$.<\/li>\n<li>Les <strong>connecteurs<\/strong> $\\neg, \\vee, \\wedge, \\to, \\leftrightarrow$, appel\u00e9s respectivement connecteur non, ou, et, implique et \u00e9quivalent.<\/li>\n<li>Les <strong>parenth\u00e8ses<\/strong> $($ et $)$.<\/li>\n<\/ul>\n<p>On appelle <strong>formule compl\u00e8tement parenth\u00e9s\u00e9es<\/strong> toute expression pouvant \u00eatre construite par induction avec les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>$\\top$et $\\bot$ sont des formules.<\/li>\n<li>Toute variable est une formule.<\/li>\n<li>Si $\\Sigma$ est une formule, alors $\\neg \\Sigma$ est une formule.<\/li>\n<li>Si $\\Sigma$ et $\\Omega$ sont des formules, alors $(\\Sigma \\vee \\Omega)$, $(\\Sigma \\wedge \\Omega)$, $(\\Sigma \\to \\Omega)$ et $(\\Sigma \\leftrightarrow \\Omega)$ sont des formules.<\/li>\n<\/ul>\n<p>Par exemple, $((\\neg(a \\vee \\neg b) \\to b)$ $\\wedge$ $(\\neg a \\vee c))$ est une formule <strong>compl\u00e8tement parenth\u00e9s\u00e9e<\/strong>.<\/p>\n<p>L&rsquo;int\u00e9r\u00eat des formules compl\u00e8tement parenth\u00e9s\u00e9es est qu&rsquo;elles se d\u00e9composent d&rsquo;une mani\u00e8re unique en un <strong>arbre syntaxique<\/strong> qui permet d&rsquo;identifier sans ambiguit\u00e9 chacune des deux sous-formules reli\u00e9es par chaque connecteur $\\neg, \\vee, \\wedge, \\to, \\leftrightarrow$ .<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfc1bis.png\" alt=\"plfc1\"><\/p>\n<p>L&rsquo;inconv\u00e9nient est qu&rsquo;elle contiennent plein de parenth\u00e8ses qui peuvent nuire \u00e0 la lisibilit\u00e9. Les parenth\u00e8ses les plus ext\u00e9rieures \u00e0 une formule peuvent \u00eatres supprim\u00e9es d&#8217;embl\u00e9e. On peut supprimer <strong>certaines<\/strong> autres parenth\u00e8ses en adoptant des conventions syntaxiques d&rsquo;<strong>associativit\u00e9<\/strong> et de <strong>priorit\u00e9 des op\u00e9rateurs<\/strong>.<\/p>\n<p><strong>L&rsquo;ordre de priorit\u00e9 des op\u00e9rateurs<\/strong> est le suivant : $\\neg, \\wedge, \\vee, \\to, \\leftrightarrow$.<\/p>\n<p>Donc par exemple la formule $b \\vee (\\neg a \\wedge c)$ <strong>pourrait<\/strong> aussi s&rsquo;\u00e9crire $b \\vee \\neg a \\wedge c$ en vertu de la priorit\u00e9 de $\\wedge$ sur $\\vee$, mais on peut laisser certaines parenth\u00e8ses facultatives pour faciliter la compr\u00e9hention de la structure de la formule.<\/p>\n<p><strong>Les connecteurs $\\vee$ et $\\wedge$ sont associatifs \u00e0 gauche<\/strong> (comme les op\u00e9rateurs arithm\u00e9tiques que nous utilisaons dans la vique quotidienne), donc par exemple $a \\wedge (\\neg b \\to a)$ $\\wedge$ $\\neg c$ $\\wedge$ $(a \\vee \\neg c)$ est \u00e9quivalent \u00e0 $((a \\wedge (\\neg b \\to a)) \\wedge \\neg c)$ $\\wedge$ $ (a \\vee \\neg c)$ tout en \u00e9tant bien plus lisible.<\/p>\n<p>L&rsquo;associativit\u00e9 syntaxique des connecteurs  $\\to$ et  $\\leftrightarrow$ n&rsquo;est pas totalement consensuelle dans la litt\u00e9rature. L&rsquo;associativit\u00e9 \u00e0 droite est la plus fr\u00e9quemment rencontr\u00e9e, mais il et plus s\u00fbr de lever toute ambig\u00fcit\u00e9 avec des parenth\u00e8ses dans le cas o\u00f9 plus de deux sous-formules sont successivement reli\u00e9es par ces op\u00e9rateurs, comme par exemple dans la formule $a \\to (b \\to c)$ qui pourrait s&rsquo;\u00e9crire $a \\to b \\to c$ en vertu de l&rsquo;associativit\u00e9 \u00e0 droite du connecteur $\\to$, mais avec le risque de se fourvoyer par la suite.<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x1<\/h5>\n<p>Mettez toutes les parenth\u00e8ses dans la formule suivante pour qu&rsquo;elle soit compl\u00e8tement parenth\u00e9s\u00e9e.<\/p>\n<p>$a \\vee b \\wedge \\neg c \\vee d$ $\\to$ $a \\vee b \\wedge c$<\/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>On commence par parenth\u00e9ser ce qui est reli\u00e9 par le connecteur le plus prioritaire, c&rsquo;est \u00e0 dire $\\wedge$.<\/p>\n<p>$a \\vee (b \\wedge \\neg c) \\vee d$ $\\to$ $a \\vee (b \\wedge c)$<\/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>On continue avec le $\\vee$ en prenant en compte l&rsquo;associativit\u00e9 \u00e0 gauche.<\/p>\n<p>$((a \\vee (b \\wedge \\neg c)) \\vee d)$ $\\to$ $(a \\vee (b \\wedge c))$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.dec2 : Notion d&rsquo;interpr\u00e9tation<\/h3>\n<p>Une <strong>formule<\/strong>, telle que d\u00e9crite dans la section pr\u00e9c\u00e9dente, est un <strong>objet math\u00e9matique purement syntaxique<\/strong>.<\/p>\n<p>Pour mod\u00e9liser un <strong>raisonnement<\/strong> permettant de d\u00e9montrer qu&rsquo;une formule est une cons\u00e9quence logique d&rsquo;une autre, il faut donner un sens \u00e0 la notion de valeur de v\u00e9rit\u00e9 d&rsquo;une formule et \u00e0 la notion de cons\u00e9quence logique. Pour ce faire, il faut introduire deux notions : la <strong>valuation<\/strong> et l&rsquo;<strong>interpr\u00e9tation<\/strong>.<\/p>\n<p>Une <strong>valuation<\/strong> d&rsquo;un ensemble $V$ de variables propositionnelle est une fonction de $V$ dans ${0,1}$. Les deux \u00e9l\u00e9ments de cet ensemble sont appel\u00e9s <strong>valeurs de v\u00e9rit\u00e9<\/strong>. On peut aussi les noter <code>FAUX<\/code> et <code>VRAI<\/code>. Les deux notations pourront \u00eatre utilis\u00e9es dans la suite de ce document.<\/p>\n<p>Par exemple, on note ${(a,0), (b,1), (c,0)}$ la valuation de l&rsquo;ensemble de variables ${a, b, c}$ qui attribue la valeur <code>FAUX<\/code> \u00e0 $a$, la valeur <code>VRAI<\/code> \u00e0 $b$ et la valeur <code>FAUX<\/code> \u00e0 $c$.<\/p>\n<p><strong>L&rsquo;interpr\u00e9tation standard<\/strong> de la logique propositionnelle est une fonction $\\text{Val}$ qui \u00e0 tout couple $(\\Sigma,A)$, o\u00f9 $\\Sigma$ est une formule et $A$ une valuation des variables de $\\Sigma$, associe une valeur de v\u00e9rit\u00e9. Il existe d&rsquo;autres interpr\u00e9tations, telle que l&rsquo;interpr\u00e9tation intuitioniste, qui sortent du cadre de ce cours. Nous utiliserons donc toujours le mot interpr\u00e9tation dans le sens d&rsquo;interpr\u00e9tation standard.<\/p>\n<p>L&rsquo;interpr\u00e9tation d&rsquo;une formule repose sur le sens donn\u00e9 aux connecteurs $\\neg$, $\\wedge$, $\\vee$, $\\to$ et $\\leftrightarrow$  par des fonctions pouvant \u00eatre repr\u00e9sent\u00e9es sous la forme de tables de v\u00e9rit\u00e9.<\/p>\n<p>Commen\u00e7ons par le connecteur $\\neg$. La s\u00e9mantique de ce connecteur est d\u00e9finie par la n\u00e9gation Bool\u00e9enne, c&rsquo;est \u00e0 dire la fonction de ${0,1}$ dans ${0,1}$ qui \u00e0 $0$ associe $1$ et \u00e0 $1$ associe 0. On notera $\\underline{\\neg} 0 = 1$ et $\\underline{\\neg} 1 = 0$.<\/p>\n<p>Voici les tables de v\u00e9rit\u00e9 d\u00e9finissant les fonctions $\\underline{\\wedge}$, $\\underline{\\vee}$, $\\underline{\\to}$ et $\\underline{\\leftrightarrow}$ qui donnent un sens aux connecteurs logiques. Les symboles repr\u00e9sentant ces fonctions ont \u00e9t\u00e9 soulign\u00e9s pour les distinguer des connecteurs correspondants.<\/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\">$ x\\underline{\\wedge}y$<\/th>\n<th style=\"text-align:center\">$ x\\underline{\\vee}y$<\/th>\n<th style=\"text-align:center\">$ x\\underline{\\to}y$<\/th>\n<th style=\"text-align:center\">$ x\\underline{\\leftrightarrow}y$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<blockquote>\n<p><strong>En toute rigueur<\/strong>, les variables $x$ et $y$ dans cette table de v\u00e9rit\u00e9 ne sont pas des variables propositionnelles mais des variables math\u00e9matiques pouvant avoir pour valeur 0 ou 1. Les variables propositionnelles sont des objets math\u00e9matiques purement syntaxiques.<\/p>\n<p>De m\u00eame, le symbole $\\wedge$ est une brique de construction des formules, alors que $\\underline{\\wedge}$ d\u00e9signe la fonction Bool\u00e9enne qui donne un sens \u00e0 ce symbole. Ces deux notations d\u00e9signent des objets math\u00e9matiques situ\u00e9s \u00e0 deux niveaux d&rsquo;abstraction diff\u00e9rents, mais ce n&rsquo;est pas dramatique si vous avez du mal \u00e0 les distinguer. Cela ne vous emp\u00eachera pas d&rsquo;atteindre les objectifs p\u00e9dagogiques de cette partie du cours.<\/p>\n<p>Si vous voulez, par la suite, approfondir votre compr\u00e9hension de la logique, vous devrez comprendre la distinction entre l&rsquo;aspect s\u00e9mantique et l&rsquo;aspect syntaxique qui est faite ici.<\/p>\n<\/blockquote>\n<p>L&rsquo;interpr\u00e9tation d&rsquo;un formule pour une valuation $A$ de ses variables est d\u00e9finie de mani\u00e8re inductive par les r\u00e8gles suivantes :<\/p>\n<ul>\n<li>\n<p>L&rsquo;interpr\u00e9tation d&rsquo;une variable $v$ est sa valuation : $\\text{Val}(v,A) = A(v)$.<\/p>\n<\/li>\n<li>\n<p>L&rsquo;interpr\u00e9tation de $\\top$est <code>VRAI<\/code> et l&rsquo;interpr\u00e9tation de $\\bot$ est <code>FAUX<\/code> : $\\text{Val}(\\top,A) = 1$, $\\text{Val}(\\bot,A) = 0$.<\/p>\n<\/li>\n<li>\n<p>L&rsquo;interpr\u00e9tation d&rsquo;une formule $\\neg \\Sigma$ est la n\u00e9gation logique de l&rsquo;interpr\u00e9tation de $\\Sigma$ :<\/p>\n<\/li>\n<\/ul>\n<p>$\\text{Val}(\\neg \\Sigma,A)$ $=$  $\\underline{\\neg}\\text{Val}(\\Sigma,A)$<\/p>\n<ul>\n<li>L&rsquo;interpr\u00e9tation d&rsquo;une formule $(\\Sigma_1 \\wedge \\Sigma_2)$ est d\u00e9finie par :<\/li>\n<\/ul>\n<p>$\\text{Val}(\\Sigma_1 \\wedge \\Sigma_2,A)$ $=$ $\\text{Val}(\\Sigma_1,A) \\underline\\wedge \\text{Val}(\\Sigma_2,A)$<\/p>\n<ul>\n<li>L&rsquo;interpr\u00e9tation d&rsquo;une formule $(\\Sigma_1 \\vee \\Sigma_2)$ est d\u00e9finie par :<\/li>\n<\/ul>\n<p>$\\text{Val}(\\Sigma_1 \\vee \\Sigma_2,A)$ $=$ $\\text{Val}(\\Sigma_1,A) \\underline\\vee \\text{Val}(\\Sigma_2,A)$<\/p>\n<ul>\n<li>L&rsquo;interpr\u00e9tation d&rsquo;une formule $(\\Sigma_1 \\to \\Sigma_2)$ est d\u00e9finie par :<\/li>\n<\/ul>\n<p>$\\text{Val}(\\Sigma_1 \\to \\Sigma_2,A)$ $=$ $\\text{Val}(\\Sigma_1,A) \\underline\\to \\text{Val}(\\Sigma_2,A)$<\/p>\n<ul>\n<li>L&rsquo;interpr\u00e9tation d&rsquo;une formule $(\\Sigma_1 \\leftrightarrow \\Sigma_2)$ est d\u00e9finie par :<\/li>\n<\/ul>\n<p>$\\text{Val}(\\Sigma_1 \\leftrightarrow \\Sigma_2,A)$ $=$ $\\text{Val}(\\Sigma_1,A) \\underline\\leftrightarrow \\text{Val}(\\Sigma_2,A)$<\/p>\n<p>De mani\u00e8re moins formelle, on peut dire que la valeur de v\u00e9rit\u00e9 attribu\u00e9e \u00e0 une formule par l&rsquo;interpr\u00e9tation standard de la logique propositionnelle est obtenue \u00e0 partir d&rsquo;une valuation des variables de cette formule en appliquant les tables de v\u00e9rit\u00e9 des connecteurs logique. Cette formulation est incompl\u00e8te (que signifie exactement &quot;appliquer une table de v\u00e9rit\u00e9&quot; ?) et manque de rigueur, mais tout le monde comprend le principe apr\u00e8s avoir trait\u00e9 quelques exemples.<\/p>\n<p>Voici un exemple. Soit la formule $\\Sigma=(a \\to b) \\vee \\neg a$ et la valuation $A = {(a,1),(b,0)}$. Quelle est l&rsquo;interpr\u00e9tation de $\\Sigma$ pour la valuation $A$ ?<\/p>\n<p>La table de v\u00e9rit\u00e9 du connecteur $\\to$ nous indique que $(a\\to b)$ s&rsquo;interpr\u00e8te \u00e0 0. Formellement, $\\text{Val}(a \\to b,I) = 1 \\underline\\to 0 = 0$.<\/p>\n<p>La table de v\u00e9rit\u00e9 du connecteur $\\neg$ nous indique que $\\neg a$ s&rsquo;interpr\u00e8te \u00e0 $0$.<\/p>\n<p>La table de v\u00e9rit\u00e9 du connecteur $\\vee$ nous indique que $\\Sigma$ s&rsquo;interpr\u00e8te \u00e0 $0$.<\/p>\n<p>$\\Sigma=\\underbrace{ \\underset{0}{(a \\to b) } \\vee \\underset{0}{\\neg a}} _0$<\/p>\n<p>On a donc $\\text{Val}(\\Sigma,A) = 0$.<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x2<\/h5>\n<p>Soit la formule $\\Sigma=(a \\to b) \\to a$. Donnez les interpr\u00e9tations de $\\Sigma$ pour chacune des valuations suivantes :<\/p>\n<ol>\n<li>$A_1 = {(a,1),(b,0)}$<\/li>\n<li>$A_2 = {(a,0),(b,1)}$<\/li>\n<\/ol>\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>$\\underbrace{\\underbrace{(\\underset{1}{a} \\to \\underset{0}{b})} _0 \\to \\underset{1}{a}} _1$<\/p>\n<p>Formellement, $\\text{Val}(\\Sigma,A_1) = 1$<\/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>$\\underbrace{\\underbrace{(\\underset{0}{a} \\to \\underset{1}{b})} \\to \\underset{0}{a}} _0$<\/p>\n<p>Formellement, $\\text{Val}(\\Sigma,A_2) = 0$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.dec3 : Validit\u00e9 et coh\u00e9rence<\/h3>\n<p>Une formule propositionnelle $\\Sigma$ est dite <strong>valide<\/strong> si et seulement si elle s&rsquo;interpr\u00e8te toujours \u00e0 <code>VRAI<\/code> quelle que soit la valuation de ses variables. On dit aussi que $\\Sigma$ est une <strong>tautologie<\/strong>.<\/p>\n<p>Une formule propositionnelle $\\Sigma$ est dite <strong>coh\u00e9rente<\/strong> si et seulement s&rsquo;il existe au moins une valuation de ses variables pour laquelle $\\Sigma$ s&rsquo;interpr\u00e8te \u00e0 <code>VRAI<\/code>. On dit aussi que $\\Sigma$ est satisfaisable, ou encore satisfiable (mais c&rsquo;est un anglicisme).<\/p>\n<p>Une formule qui n&rsquo;est pas coh\u00e9rente est dite <strong>incoh\u00e9rente<\/strong>.<\/p>\n<p>On peut donc classer les formules propositionnelles dans trois cat\u00e9gories :<\/p>\n<ul>\n<li>Les formules valides, qui sont &quot;toujours vraies&quot; (dans le sens o\u00f9 elle s&rsquo;interpr\u00e8tent \u00e0 <code>VRAI<\/code> pour toutes les valuations possibles de leurs variables.)<\/li>\n<li>Les formules incoh\u00e9rentes, qui sont &quot;toujours fausses&quot;.<\/li>\n<li>Les formules coh\u00e9rentes mais pas valides, qui sont &quot;parfois vraies et parfois fausses&quot; (selon la valuation de leurs variables).<\/li>\n<\/ul>\n<h5>Exercice de d\u00e9couverte C.dec.x3<\/h5>\n<p>La formule $a \\to a$ est-elle une tautologie, est elle coh\u00e9rente sans \u00eatre valide, ou est-elle incoh\u00e9rente ?<\/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>D&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$, c&rsquo;est une tautologie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5>Exercice de d\u00e9couverte C.dec.x4<\/h5>\n<p>La formule $a \\to \\neg a$ est-elle une tautologie, est elle coh\u00e9rente sans \u00eatre valide, ou est-elle incoh\u00e9rente ?<\/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>Elle est coh\u00e9rente mais pas valide. D&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\to$, ,si $a$ vaut 0 alors $(a \\to \\neg a)$ s&rsquo;interpr\u00e8te \u00e0 1, mais si $a$ vaut 1 $(a \\to \\neg a)$ s&rsquo;interpr\u00e8te \u00e0 0.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5>Exercice de d\u00e9couverte C.dec.x5<\/h5>\n<p>La formule $a \\wedge \\neg a$ est-elle une tautologie, est elle coh\u00e9rente sans \u00eatre valide, ou est-elle incoh\u00e9rente ?<\/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>C&rsquo;est une formule incoh\u00e9rente.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5>Exercice de d\u00e9couverte C.dec.x6<\/h5>\n<p>La formule $(a \\wedge b) \\vee (\\neg a \\wedge b)$ est-elle une tautologie, est elle coh\u00e9rente sans \u00eatre valide, ou est-elle incoh\u00e9rente ?<\/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 peut reprendre dans une table de v\u00e9rit\u00e9 les interpr\u00e9tations des diff\u00e9rentes sous-formules pour faciliter le calcul des valeurs de v\u00e9rit\u00e9 de la formule compl\u00e8te.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$a \\wedge b$<\/th>\n<th style=\"text-align:center\">$\\neg a \\wedge b$<\/th>\n<th style=\"text-align:center\">$(a \\wedge b) \\vee (\\neg a \\wedge b)$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On voit que la formule s&rsquo;interpr\u00e8te \u00e0 <code>VRAI<\/code> pour certaines valuations des variables et \u00e0 <code>FAUX<\/code> pour d&rsquo;autres. C&rsquo;est donc une formule coh\u00e9rente, mais pas une tautologie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Une valuation $A$ pour laquelle une formule $\\Sigma$ s&rsquo;interpr\u00e8te \u00e0 <code>VRAI<\/code> est appel\u00e9e un <strong>mod\u00e8le<\/strong> de $\\Sigma$. On dit aussi que $A$ <strong>satisfait<\/strong> $\\Sigma$. Une valuation $A$ pour laquelle une formule $\\Sigma$ s&rsquo;interpr\u00e8te \u00e0 <code>FAUX<\/code> est appel\u00e9e un <strong>contre-mod\u00e8le<\/strong> de $\\Sigma$. On dit aussi que $A$ <strong>falsifie<\/strong> $\\Sigma$.<\/p>\n<p>Une formule valide, ou tautologie, est donc une formule n&rsquo;ayant aucun contre-mod\u00e8le. Une formule incoh\u00e9rente est une formule n&rsquo;ayant aucun mod\u00e8le.<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x7<\/h5>\n<p>Donnez les mod\u00e8les de la formule $\\neg a \\to \\neg 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>La formule a trois mod\u00e8les :<\/p>\n<ul>\n<li>${(a,0),(b,0)}$<\/li>\n<li>${(a,1),(b,0)}$<\/li>\n<li>${(a,1),(b,1)}$<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.dec4 : Cons\u00e9quence logique et \u00e9quivalence logique<\/h3>\n<p><strong>D\u00e9finition<\/strong> : On dit qu&rsquo;une formule $\\Omega$ est une <strong>cons\u00e9quence logique<\/strong> d&rsquo;une formule $\\Sigma$ si et seulement si tout mod\u00e8le de $\\Sigma$ est un mod\u00e8le de $\\Omega$. On note :<\/p>\n<p>$\\Sigma \\models \\Omega$<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfc2.png\" alt=\"plfc2\"><\/p>\n<p><strong>Attention<\/strong> : le symbole $\\models$ n&rsquo;est <strong>pas<\/strong> un connecteur logique. Si $\\Sigma$ et $\\Omega$ sont des formules propositionnelles, l&rsquo;expression $\\Sigma \\models \\Omega$ n&rsquo;est <strong>pas<\/strong> une formule propositionnelle, mais une notation math\u00e9matique qui exprime une propri\u00e9t\u00e9 reliant deux formules propositionnelles.<\/p>\n<blockquote>\n<p>Encore une fois, la nuance tient au fait que les formules sont des objets math\u00e9matiques purement syntaxiques, alors que le symbole $\\models$ repr\u00e9sente une propri\u00e9t\u00e9 s\u00e9mantique en rapport avec les interpr\u00e9tations des formules.<\/p>\n<\/blockquote>\n<p>Il y a toutefois une propri\u00e9t\u00e9 qui \u00e9tablit un lien entre le symbole s\u00e9mantique $\\models$ et le connecteur $\\to$.<\/p>\n<p><strong>Propri\u00e9t\u00e9<\/strong> : Pour toutes formules propositionnelles $\\Sigma$ et $\\Omega$, $\\Sigma \\models \\Omega$ si et seulement si la formule $\\Sigma \\to \\Omega$ est une tautologie.<\/p>\n<p><strong>Exemple<\/strong> : $a \\vee b$ est une cons\u00e9quence logique de $a \\wedge b$, autrement dit, $a \\wedge b \\models a \\vee b$. En effet, toute valuation de $a$ et $b$ qui satisfait $a \\wedge b$ (il y en a une seule), satisfait aussi $a \\vee b$. De fait, la formule $(a \\wedge b)\\to(a \\vee b)$ est une tautologie.<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x8<\/h5>\n<p>L&rsquo;affirmation $a \\to b \\models a \\vee b$ est elle correcte ?<\/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 peut r\u00e9pondre \u00e0 cette question en comparant les tables de v\u00e9rit\u00e9s des deux formules.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$a \\to b$<\/th>\n<th style=\"text-align:center\">$ a \\vee b $<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>La r\u00e9ponse \u00e0 la question pos\u00e9e est <strong>non<\/strong> : $a \\vee b$ n&rsquo;est pas une cons\u00e9quence logique de $a \\to b$ car la valuation repr\u00e9sent\u00e9e par la premi\u00e8re ligne de la table de v\u00e9rit\u00e9,  ${(a,0), (b,0)}$, est un mod\u00e8le de  $a \\to b$ mais pas de $a \\vee b$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p><strong>D\u00e9finition<\/strong> : On dit que deux formules $\\Sigma$ et $\\Omega$ sont <strong>logiquement \u00e9quivalentes<\/strong> si et seulement si elles ont les m\u00eames mod\u00e8les. On note :<\/p>\n<p>$\\Sigma \\equiv \\Omega$<\/p>\n<p><strong>Propri\u00e9t\u00e9<\/strong> : Pour toutes formules propositionnelles $\\Sigma$ et $\\Omega$, $\\Sigma \\equiv \\Omega$ si et seulement si $\\Sigma \\models \\Omega$ et $\\Omega  \\models \\Sigma$.<\/p>\n<p><strong>Propri\u00e9t\u00e9<\/strong> : Pour toutes formules propositionnelles $\\Sigma$ et $\\Omega$, $\\Sigma \\equiv \\Omega$ si et seulement si la formule $\\Sigma \\leftrightarrow \\Omega$ est une tautologie.<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x9<\/h5>\n<p>L&rsquo;affirmation $a \\to b$ $\\equiv$ $\\neg b \\to \\neg a$ est elle correcte ?<\/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>Avec seulement deux variables, le moyen le plus simple de v\u00e9rifier si les deux formules sont \u00e9quivalentes est de comparer leurs tables de v\u00e9rit\u00e9.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$a \\to b$<\/th>\n<th style=\"text-align:center\">$ \\neg b \\to \\neg a $<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Toutes les lignes des 2 tables de v\u00e9rit\u00e9 sont identiques, donc les deux formules sont logiquement \u00e9quivalentes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Certaines propri\u00e9t\u00e9s permettent de simplifier des formules contenant des constantes $\\top$ et\/ou $\\bot$ en les rempla\u00e7ant par des formules \u00e9quivalentes. Ces propri\u00e9t\u00e9s d\u00e9coulent directement des tables de v\u00e9rit\u00e9 des connecteurs logiques.<\/p>\n<ol>\n<li>$\\neg \\top \\equiv \\bot$<\/li>\n<li>$\\neg \\bot \\equiv \\top$<\/li>\n<li>$\\top \\wedge \\Sigma \\equiv \\Sigma \\wedge \\top \\equiv \\Sigma$<\/li>\n<li>$\\bot \\wedge \\Sigma \\equiv \\Sigma \\wedge \\bot \\equiv \\bot$<\/li>\n<li>$\\top \\vee \\Sigma \\equiv \\Sigma \\vee \\top \\equiv \\top$<\/li>\n<li>$\\bot \\vee \\Sigma \\equiv \\Sigma \\vee \\bot \\equiv \\Sigma$<\/li>\n<li>$\\top \\to \\Sigma \\equiv \\Sigma$<\/li>\n<li>$\\bot \\to \\Sigma \\equiv \\top$<\/li>\n<li>$\\Sigma \\to \\top \\equiv \\Sigma$<\/li>\n<li>$\\Sigma \\to \\bot \\equiv \\neg \\Sigma $<\/li>\n<li>$\\top \\leftrightarrow \\Sigma \\equiv \\Sigma \\leftrightarrow \\top \\equiv \\Sigma$<\/li>\n<li>$\\bot \\leftrightarrow \\Sigma \\equiv \\Sigma \\leftrightarrow \\bot \\equiv \\neg \\Sigma$<\/li>\n<\/ol>\n<h3>C.dec5 : Raisonnement par s\u00e9paration<\/h3>\n<p>D\u00e9terminer si une formule est une cons\u00e9quence logique d&rsquo;une autre permet d&rsquo;utiliser la logique propositionnelle pour mod\u00e9liser un raisonnement. Mais la m\u00e9thode de comparaison des tables de v\u00e9rit\u00e9 devient fastidieuse au del\u00e0 de trois variables, inapplicable &quot;\u00e0 la main&quot; au de 6 ou 7 variables (pour 7 variables, les tables comportent 128 lignes), et inapplicable avec un ordinateur au del\u00e0 de quelques dizaines de variables.<\/p>\n<p>On peut parfois aller un peu plus vite en choisissant une variable et en raisonnant s\u00e9par\u00e9ment sur les interpr\u00e9tations de la formule pour les valuations o\u00f9 cette variable a la valeur 0 et celles o\u00f9 elle a la valeur 1. Dans el premier cas, cela revient \u00e0 remplacer la variable de s\u00e9paration par $\\bot$ et dans le deuxi\u00e8me cas \u00e0 la remplacer par $\\top$. On peut ensuite appliquer les r\u00e8gles de simplification vues dans la section pr\u00e9c\u00e9dente.<\/p>\n<p>Prenons pour exemple la formule suivante :<\/p>\n<p>$\\Sigma = ((a \\to b)\\wedge(a \\to c))$ $\\to$ $((\\neg a \\vee b \\vee \\neg c) \\wedge (\\neg a \\vee \\neg b \\vee c))$<\/p>\n<p>Il nous faut choisir une variable de s\u00e9paration, par exemple la variable $a$. On distingue alors deux cas.<\/p>\n<p><strong>Cas 1<\/strong> : La variable $a$ est assign\u00e9e \u00e0 0. On s&rsquo;int\u00e9resse uniquement aux valuations qui assignent 0 \u00e0 $a$. Les valeurs de v\u00e9rit\u00e9 de la formule $\\Sigma$ pour ces valuations sont celles de la formule $\\Sigma\\vert_{a=\\bot}$, c&rsquo;est \u00e0 dire la formule dans laquelle on remplace toutes les occurrences de $a$ par la constante propositionnelle $\\bot$, qui s&rsquo;interpr\u00e8te \u00e0 0.<\/p>\n<p>$\\Sigma\\vert_{a=\\bot}$ $=$ $((\\bot \\to b)\\wedge(\\bot \\to c))$ $\\to$ $((\\top \\vee b \\vee \\neg c) \\wedge (\\top \\vee \\neg b \\vee c))$<\/p>\n<p>En appliquant les r\u00e8gles de simplification, on obtient :<\/p>\n<p>$\\Sigma\\vert_{a=\\bot}$ $=$ $(\\top\\wedge \\top) \\to (\\top \\wedge \\top)$<\/p>\n<p>D&rsquo;apr\u00e8s les tables de v\u00e9rit\u00e9 des connecteurs $\\wedge$ et $\\to$, cette formule se simplifie en $\\top$ et s&rsquo;interpr\u00e8te \u00e0 1.<\/p>\n<p><strong>Cas 2<\/strong> : La variable $a$ est assign\u00e9e \u00e0 1. On s&rsquo;int\u00e9resse uniquement aux valuations qui assignent 1 \u00e0 $a$. Les valeurs de v\u00e9rit\u00e9 de la formule $\\Sigma$ pour ces valuations sont celle de la formule $\\Sigma\\vert_{a=\\top}$, c&rsquo;est \u00e0 dire la formule dans laquelle on remplace toutes les occurrences de $a$ par la constante propositionnelle $\\top$, qui s&rsquo;interpr\u00e8te \u00e0 1.<\/p>\n<p>$\\Sigma\\vert_{a=\\top}$ $=$ $((\\top \\to b)\\wedge(\\top \\to c))$ $\\to$ $((\\bot \\vee b \\vee \\neg c) \\wedge (\\bot \\vee \\neg b \\vee c))$<\/p>\n<p>La formule se simplifie en :<\/p>\n<p>$\\Sigma\\vert_{a=\\top}$ $=$ $(b \\wedge c)$ $\\to$ $(( b \\vee \\neg c) \\wedge (\\neg b \\vee c))$<\/p>\n<p>On peut alors utiliser une nouvelle variable de s\u00e9paration, par exemple $b$.<\/p>\n<p><strong>Cas 2.1<\/strong> : $b$ est assign\u00e9e \u00e0 0.<\/p>\n<p>$\\Sigma\\vert_{a=\\top, b=\\bot}$ $=$ $(\\bot \\wedge c)$ $\\to$ $(( \\bot \\vee \\neg c) \\wedge (\\top \\vee c))$<\/p>\n<p>$\\Sigma\\vert_{a=\\top, b=\\bot}$ $=$ $\\bot$ $\\to$ $(\\neg c \\wedge \\top) = \\top$<\/p>\n<p><strong>Cas 2.2<\/strong> : $b$ est assign\u00e9e \u00e0 1<\/p>\n<p>$\\Sigma\\vert_{a=\\top, b=\\top}$ $=$ $(\\top \\wedge c)$ $\\to$ $(( \\top \\vee \\neg c) \\wedge (\\bot \\vee c))$<\/p>\n<p>$\\Sigma\\vert_{a=\\top, b=\\top}$ $=$ $c$ $\\to$ $(\\top  \\wedge  c) = c \\to c = \\top$<\/p>\n<p>Pour toutes les valuations possibles des variables, la formule s&rsquo;interpr\u00e8te \u00e0 1. C&rsquo;est donc un tautologie.<\/p>\n<p>Le raisonnement est r\u00e9sum\u00e9 par ce sch\u00e9ma :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfc3.png\" alt=\"plfc3\"><\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x10<\/h5>\n<p>Utilisez le principe de s\u00e9paration pour montrer que $\\underbrace{(a \\wedge b) \\to c} _\\Sigma$ $;\\equiv;$ $\\underbrace{a \\to (b \\to c)} _\\Omega$.<\/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>On peut raisonner s\u00e9par\u00e9ment sur les deux formules en utilisant $a$ comme variable de s\u00e9paration. Les simplifications d\u00e9coulent directement des tables de v\u00e9rit\u00e9 des connecteurs logiques.<\/p>\n<p><strong>Cas 1<\/strong> : on remplace $a$ par $\\bot$.<\/p>\n<p>$\\Sigma\\vert_{a=\\bot} = \\underbrace{(\\bot \\wedge b)} _{\\bot} \\to c$<\/p>\n<p>$\\Sigma\\vert_{a=\\bot} = \\underbrace{\\bot \\to c} _{\\top}$<\/p>\n<p>$\\Sigma\\vert_{a=\\bot} = \\top$<\/p>\n<p>$\\Omega\\vert_{a=\\bot} = \\underbrace{\\bot \\to (b \\to c)} _{\\top}$<\/p>\n<p>$\\Omega\\vert_{a=\\bot} = \\top$.<\/p>\n<p>Donc pour toutes les valuations attribuant 0 \u00e0 la variable $a$, les deux formules $\\Sigma$ et $\\Omega$ s&rsquo;interpr\u00e8tent \u00e0 <code>VRAI<\/code>.<\/p>\n<p>Il reste \u00e0 traiter la cas o\u00f9 $a$ est remplac\u00e9e par $\\top$ pour pouvoir conclure.<\/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><strong>Cas 2<\/strong> : on remplace $a$ par $\\top$.<\/p>\n<p>$\\Sigma\\vert_{a=\\top} = \\underset{b}{(\\top \\wedge b)} \\to c$<\/p>\n<p>$\\Sigma\\vert_{a=\\top} = b \\to c$<\/p>\n<p>$\\Omega\\vert_{a=\\top} = \\underbrace{\\top \\to (b \\to c)}_ {b \\to c}$<\/p>\n<p>$\\Omega\\vert_{a=\\top} = b \\to c$<\/p>\n<p>Donc pour toutes les valuations attribuant 1 \u00e0 la variable $a$, les deux formule $\\Sigma$ et $\\Omega$ s&rsquo;interpr\u00e8tent comme $b \\to c$.<\/p>\n<p><strong>Conclusion<\/strong> : les formules $\\Sigma$ et $\\Omega$ sont logiquement \u00e9quivalentes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.dec6 : Mod\u00e9lisation<\/h3>\n<p>La logique propositionnelle permet de mod\u00e9liser des probl\u00e8mes dans lesquels, parmi un nombre fini de sc\u00e9narios, certains sont autoris\u00e9s par un \u00e9nonc\u00e9 $E$ (exprim\u00e9 en langage naturel ou en langage math\u00e9matique), et certains sont interdits par $E$.<\/p>\n<p><strong>Exemple<\/strong> : Deux b\u00e2timents num\u00e9rot\u00e9s $1$ et $2$ doivent \u00eatre gard\u00e9s par Anne, Bart et Carl. Chaque personne peut \u00eatre dans le b\u00e2timent $1$, dans le b\u00e2timent $2$, ou dans aucun des deux. Un sc\u00e9nario repr\u00e9sente la situation des trois personnes \u00e0 un moment donn\u00e9. Les sc\u00e9narios autoris\u00e9s sont ceux dans lesquels il y a au moins une personne dans chaque b\u00e2timent.<\/p>\n<p>On peut mod\u00e9liser le probl\u00e8me avec 6 variables :<\/p>\n<ul>\n<li>$a_1$ et $a_2$ qui sont associ\u00e9es \u00e0 Anne. Par convention, $a_1 = 1$ signifie qu&rsquo;Anne est dans le b\u00e2timent 1 et $a_2 = 1$ signifie qu&rsquo;elle se trouve dans le b\u00e2timent 2. Les deux variable \u00e0 $0$ indiquent qu&rsquo;Anne n&rsquo;est dans aucun b\u00e2timent. Les deux variables \u00e0 ne peuvent \u00eatre \u00e0 $1$ dans les sc\u00e9narios possibles.<\/li>\n<li>$b_1$ et $b_2$ qui sont associ\u00e9es \u00e0 Bart, avec les m\u00eames conventions que pour les variables $a_1$ et $a_2$.<\/li>\n<li>$c_1$ et $c_2$ qui sont associ\u00e9es \u00e0 Carl, avec les m\u00eames conventions que pour les autres variables.<\/li>\n<\/ul>\n<p>Voici trois exemples de valuations :<\/p>\n<ol>\n<li>$(a_1,1)$, $(a_2,1)$, $(b_1,0)$, $(b_2,1)$, $(c_1,0)$, $(c_2,1)$ repr\u00e9sente un sc\u00e9nario impossible dans lequel Anne serait dans les deux b\u00e2timents en m\u00eame temps.<\/li>\n<li>$(a_1,0)$, $(a_2,0)$, $(b_1,1)$, $(b_2,0)$, $(c_1,0)$, $(c_2,0)$ repr\u00e9sente un sc\u00e9nario possible, mais interdit, dans lequel le b\u00e2timent 2 n&rsquo;est pas surveill\u00e9.<\/li>\n<li>$(a_1,0)$, $(a_2,1)$, $(b_1,1)$, $(b_2,0)$, $(c_1,0)$, $(c_2,1)$ repr\u00e9sente un sc\u00e9nario autoris\u00e9 dans lequel Anne et Charlie sont dans le b\u00e2timent 2 et Bart est dans le b\u00e2timent 1.<\/li>\n<\/ol>\n<p>Le but est de trouver une formule $\\Sigma$ qui soit satisfaite par toutes les valuations repr\u00e9sentant les sc\u00e9narios autoris\u00e9s et falsifi\u00e9e par toutes les autres valuations.<\/p>\n<p>On peut construire cette formule comme une conjonction de sous-formules v\u00e9rifiant chacune une partie des propri\u00e9t\u00e9s des sc\u00e9narios autoris\u00e9s.<\/p>\n<ul>\n<li>$\\neg (a_1 \\wedge a_2)$ v\u00e9rifie qu&rsquo;Anne ne peut se trouver en m\u00eame temps dans les deux b\u00e2timents, c&rsquo;est \u00e0 dire que $a_1$ et $a_2$ ne peuvent avoir toutes les deux la valeur $1$.  En effet, cette formule est falsifi\u00e9e si et seulement si les deux variables ont la valeur $1$.<\/li>\n<li>$\\neg (b_1 \\wedge b_2)$ v\u00e9rifie que Bart ne peut se trouver en m\u00eame temps dans les deux b\u00e2timents.<\/li>\n<li>$\\neg (c_1 \\wedge c_2)$ v\u00e9rifie que Charlie ne peut se trouver en m\u00eame temps dans les deux b\u00e2timents.<\/li>\n<li>$a_1 \\vee b_1 \\vee c_1$ v\u00e9rifie qu&rsquo;il y a au moins une personne dans le b\u00e2timent 1.<\/li>\n<li>$a_2 \\vee b_2 \\vee c_2$ v\u00e9rifie qu&rsquo;il y a au moins une personne dans le b\u00e2timent 2.<\/li>\n<\/ul>\n<p>On obtient :<\/p>\n<p>$\\Sigma  =$ $\\neg (a_1 \\wedge a_2)$ $\\wedge$ $\\neg (b_1 \\wedge b_2)$ $\\wedge$ $\\neg (c_1 \\wedge c_2)$ $\\wedge$ $(a_1 \\vee b_1 \\vee c_1)$ $\\wedge$ $(a_2 \\vee b_2 \\vee c_2)$<\/p>\n<p>Toute formule logiquement \u00e9quivalente \u00e0 celle-ci convient aussi, comme par exemple :<\/p>\n<p>$(\\neg a_1 \\vee \\neg a_2)$ $\\wedge$ $(\\neg b_1 \\vee \\neg b_2)$ $\\wedge$ $(\\neg c_1 \\vee \\neg c_2)$ $\\wedge$ $(a_1 \\vee b_1 \\vee c_1)$ $\\wedge$ $(a_2 \\vee b_2 \\vee c_2)$<\/p>\n<h5>Exercice de d\u00e9couverte C.dec.x11<\/h5>\n<p>Vous devez mod\u00e9liser plusieurs r\u00e8gles applicables \u00e0 des feux tricolores situ\u00e9s \u00e0 une carrefour.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfc4.png\" alt=\"plfc4\"><\/p>\n<ol>\n<li>Une et une seule des ampoules de la rue 1 est allum\u00e9e (soit la verte, soit la jaune, soit le rouge)<\/li>\n<li>Si le feu de la rue 1 est au vert ou \u00e0 l&rsquo;orange, alors celui de la rue 2 est au rouge.<\/li>\n<\/ol>\n<p>L&rsquo;\u00e9tat des ampoules des feux du feu de la rue 1 est repr\u00e9sent\u00e9 par les variables $v_1$ pour l&rsquo;ampoule verte (1 si allum\u00e9e, 0 sinon), $j_1$ pour l&rsquo;ampoule jaune, et $r_1$ pour l&rsquo;ampoule rouge. L&rsquo;\u00e9tat des ampoules des feux du feu de la rue 2 est repr\u00e9sent\u00e9 par les variables $v_2, j_2, r_2$ avec les m\u00eames conventions.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il existe plusieurs mani\u00e8res de mod\u00e9liser la premi\u00e8re r\u00e8gle. L&rsquo;une d&rsquo;elle consiste \u00e0 partir de sa table de v\u00e9rit\u00e9.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$v_1$<\/th>\n<th style=\"text-align:center\">$j_1$<\/th>\n<th style=\"text-align:center\">$r_1$<\/th>\n<th style=\"text-align:center\">Autoris\u00e9 ?<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">non<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\"><strong>oui<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\"><strong>oui<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">non<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\"><strong>oui<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">non<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">non<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">non<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Trois valuations correspondent \u00e0 des sc\u00e9narios autoris\u00e9s. On peut construire la formule sous la forme d&rsquo;une disjonction de trois sous-formules dont chacune est satisfaite uniquement par une des valuations repr\u00e9sentant un sc\u00e9nario autoris\u00e9.<\/p>\n<p>Par exemple, la sous-formule $\\neg v_1 \\wedge \\neg j_1 \\wedge r_1$ s&rsquo;interpr\u00e8te \u00e0 1 si et seulement si les variables $v_1$ et $j_1$ ont la valeur 0 et la variable $r_1$ a la valeur 1.<\/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>$\\Sigma_1$ $=$ $\\underbrace{(\\neg v_1 \\wedge \\neg j_1 \\wedge r_1)} _{\\sigma_1}$ $\\vee$ $\\underbrace{(\\neg v_1 \\wedge j_1 \\wedge \\neg r_1)} _{\\sigma_2}$ $\\vee$ $\\underbrace{(v_1 \\wedge \\neg j_1 \\wedge \\neg r_1)} _{\\sigma_3}$<\/p>\n<p>La formule $\\sigma_1$ est satisfaite par une seule valuation qui correspond au cas o\u00f9 l&rsquo;ampoule rouge est allum\u00e9e et les deux autres \u00e9teintes. Les formules $\\sigma_2$ et $\\sigma_3$ sont satisfaites par les valuation correspondant aux deux autres sc\u00e9narios autoris\u00e9s. Les mod\u00e8les de $\\Sigma_1$ sont les valuations qui correspondent aux trois sc\u00e9narios autoris\u00e9s.<\/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;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Pour mod\u00e9liser la deuxi\u00e8me r\u00e8gle, on pourrait utiliser la m\u00eame m\u00e9thode que pour la premi\u00e8re. Cette m\u00e9thode est utilisable lorsque 2, 3, voire 4 variables interviennent dans la formule \u00e0 mod\u00e9liser. Mais La mani\u00e8re dont la r\u00e8gle \u00e0 mod\u00e9liser est sp\u00e9cifi\u00e9e permet une approche plus simple et plus rapide. En effet, la formule <strong>si<\/strong> &#8230; <strong>alors<\/strong> peut se mod\u00e9liser avec une implication.<\/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>$\\Sigma_2 = (v_1 \\vee j_1) \\to r_2$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Activit\u00e9 d&rsquo;entra\u00eenement C.ent<\/h2>\n<p>Cette activit\u00e9 est essentielle. C&rsquo;est gr\u00e2ce \u00e0 elle que vous apprendrez vraiment \u00e0 comprendre et utiliser les notions vues pr\u00e9c\u00e9demment. Elle se d\u00e9compose en deux <strong>it\u00e9rations<\/strong> : <strong>ent1<\/strong>, <strong>ent2<\/strong>. Vous devez r\u00e9aliser au moins une it\u00e9ration et \u00e9valuer votre niveau de r\u00e9ussite.<\/p>\n<p>Si vous avez eu beaucoup de difficult\u00e9 \u00e0 traiter les exercices et fait beaucoup d&rsquo;erreurs, vous devrez traiter \u00e0 nouveau l&rsquo;activit\u00e9 de d\u00e9couverte pr\u00e9c\u00e9dente, en laissant passer au moins une nuit, avant de revenir \u00e0 cette activit\u00e9 d&rsquo;entra\u00eenement en r\u00e9alisant \u00e0 nouveau la premi\u00e8re l&rsquo;it\u00e9ration. Vous devez aussi essayer d&rsquo;identifier les points de blocage et demander \u00e0 votre enseignant de vous aider \u00e0 les surmonter.<\/p>\n<p>Si vous avez r\u00e9ussi certains exercices, mais \u00e9chou\u00e9 \u00e0 d&rsquo;autres, vous devrez d&rsquo;abord comprendre ce qui vous a conduit \u00e0 des erreurs et \/ ou ce qui vous a bloqu\u00e9. Si vous avez des doutes, des difficult\u00e9s, essayez de trouver les r\u00e9ponses dans les pr\u00e9sentations et explications de l&rsquo;activit\u00e9 de d\u00e9couverte et demandez toute l&rsquo;aide n\u00e9cessaire \u00e0 votre enseignant. Ensuite, vous devrez r\u00e9aliser l&rsquo;it\u00e9ration suivante apr\u00e8s au moins une nuit de sommeil et au plus une semaine.<\/p>\n<p>Si vous avez r\u00e9ussi presque tous les exercices et que vos rares erreurs sont dues \u00e0 l&rsquo;inattention, vous devriez revenir traiter l&rsquo;it\u00e9ration suivante apr\u00e8s un d\u00e9lai de plusieurs semaines.<\/p>\n<p>Si besoin, apr\u00e8s avoir trait\u00e9 la deuxi\u00e8me it\u00e9ration, vous pouvez revenir \u00e0 la premi\u00e8re. Vous pouvez aussi traiter des annales d&rsquo;\u00e9valuations de l&rsquo;unit\u00e9 d&rsquo;enseignement.<\/p>\n<h3>It\u00e9ration C.ent1<\/h3>\n<h4>Exercice d&rsquo;entrainement C.ent1.1<\/h4>\n<p>La formule $a \\to ((a \\to b) \\to (b \\to a))$ est elle coh\u00e9rente ? Est-elle une tautologie ?<\/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>La formule comporte seulement deux variables. Dans un tel cas, le moyen le plus simple est de r\u00e9aliser sa table de v\u00e9rit\u00e9.<\/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>$\\Sigma = a \\to \\underbrace{(\\underset{\\sigma_1}{(a \\to b)} \\to \\underset{\\sigma_2}{(b \\to a)})}_{\\sigma}$<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$\\sigma_1$<\/th>\n<th style=\"text-align:center\">$\\sigma_2$<\/th>\n<th style=\"text-align:center\">$\\sigma$<\/th>\n<th style=\"text-align:center\">$\\Sigma$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On constate que toutes les valuations sont des mod\u00e8les de $\\Sigma$. La formule est donc une tautologie. Elle est donc coh\u00e9rente.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent1.2<\/h4>\n<p>La formule suivante est elle une tautologie ? Est-elle coh\u00e9rente ?<\/p>\n<p>$\\Sigma$ $=$ $(a \\vee \\neg b)$ $\\wedge$ $(b \\vee \\neg c)$ $\\wedge$ $(c \\vee \\neg d)$ $\\wedge$ $(d \\vee \\neg e)$ $\\wedge$ $(\\neg a)$ $\\wedge$ $(e)$<\/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 y a trop de variables pour que la m\u00e9thode de la table de v\u00e9rit\u00e9 soit applicable. Il est plus pertinent, dans un tel cas, de raisonner par s\u00e9paration et d\u00e9ductions.<\/p>\n<p>$\\Sigma$ $=$ $\\underset{\\sigma_1}{(a \\vee \\neg b)}$ $\\wedge$ $\\underset{\\sigma_2}{(b \\vee \\neg c)}$ $\\wedge$ $\\underset{\\sigma_3}{(c \\vee \\neg d)}$ $\\wedge$ $\\underset{\\sigma_4}{(d \\vee \\neg e)}$ $\\wedge$ $\\underset{\\sigma_5}{(\\neg a)}$ $\\wedge$ $\\underset{\\sigma_6}{(e)}$<\/p>\n<p>Pour satisfaire $\\Sigma$, il faut satisfaire chacune des sous-formules $\\sigma_1$ \u00e0 $\\sigma_6$. Or pour satisfaire $\\sigma_5$ il faut assigner la valeur 0 \u00e0 la variable $a$ et pour satisfaire $\\sigma_6$ il faut assigner 1 \u00e0 la variable $e$. On peut donc d\u00e9j\u00e0 affirmer que $\\Sigma$ n&rsquo;est pas une tautologie.<\/p>\n<p>On peut aussi d\u00e9duire que pour satisfaire $\\Sigma$, il faut satisfaire $\\Sigma\\vert_{a=\\bot,e=\\top}$. A vous de continuer le raisonnement.<\/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>En rempla\u00e7ant $a$ par $\\bot$ et $e$ par $\\bot$, on obtient :<\/p>\n<p>$\\Sigma_1$ $=$ $\\underset{\\sigma_1}{(\\bot \\vee \\neg b)}$ $\\wedge$ $\\underset{\\sigma_2}{(b \\vee \\neg c)}$ $\\wedge$ $\\underset{\\sigma_3}{(c \\vee \\neg d)}$ $\\wedge$ $\\underset{\\sigma_4}{(d \\vee \\bot)}$<\/p>\n<p>Pour satisfaire $\\Sigma_1$, il faut assigner $b$ \u00e0 0 et $d$ \u00e0 1. On peut \u00e0 nouveau simplifier et ramener le probl\u00e8me \u00e0 la recherche d&rsquo;un mod\u00e8le de la formule :<\/p>\n<p>$\\Sigma_2 = \\underset{\\sigma_2}{(\\bot \\vee \\neg c)} \\wedge \\underset{\\sigma_3}{(c \\vee \\bot)}$<\/p>\n<p>Or cette formule est incoh\u00e9rente puisqu&rsquo;elle est falsifi\u00e9e si on donne \u00e0 $c$ la valeur 1 et aussi si on lui donne la valeur $0$.<\/p>\n<p>On peut en d\u00e9duire que la formule initiale $\\Sigma$ est incoh\u00e9rente.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent1.3<\/h4>\n<p>Soient les formules suivantes :<\/p>\n<ul>\n<li>$\\Sigma = (a \\wedge \\neg b) \\vee (\\neg a \\wedge b)$<\/li>\n<li>$\\Omega = a \\vee b$<\/li>\n<\/ul>\n<p>Lesquelles de ces trois propositions sont correctes ?<\/p>\n<ol>\n<li>$\\Sigma \\models \\Omega$<\/li>\n<li>$\\Omega \\models \\Sigma$<\/li>\n<li>$\\Sigma \\equiv \\Omega$<\/li>\n<\/ol>\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>La comparaison des tables de v\u00e9rit\u00e9 des deux formules permet de r\u00e9pondre :<\/p>\n<ol>\n<li>Tout mod\u00e8le de $\\Sigma$ est-il un mod\u00e8le de $\\Omega$ ?<\/li>\n<li>Tout mod\u00e8le de $\\Omega$ est-il un mod\u00e8le de $\\Sigma$ ?<\/li>\n<li>$\\Sigma$ et $\\Omega$ ont-elles exactement les m\u00eames mod\u00e8les ?<\/li>\n<\/ol>\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>$\\Sigma = \\underbrace{(a \\wedge \\neg b)} _{\\sigma_1} \\vee \\underbrace{(\\neg a \\wedge b)} _{\\sigma_2}$<\/p>\n<p>$\\Omega = a \\vee b$<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$\\Omega$<\/th>\n<th style=\"text-align:center\">$\\sigma_1$<\/th>\n<th style=\"text-align:center\">$\\sigma_2$<\/th>\n<th style=\"text-align:center\">$\\Sigma$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>$\\Sigma$ et $\\Omega$ n&rsquo;ont pas les m\u00eames mod\u00e8les, donc ne sont pas logiquement \u00e9quivalentes. La proposition 3 est incorrecte. Tous les mod\u00e8les de $\\Sigma$ sont des mod\u00e8les de $\\Omega$, donc $\\Sigma \\models \\Omega$. La proposition 1 est correcte. Un mod\u00e8le de $\\Omega$ ne satisfait pas $\\Sigma$, donc la proposition 2 est incorrecte.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent1.4<\/h4>\n<p>Soient les formules suivantes :<\/p>\n<ul>\n<li>$\\Sigma = (a \\vee b) \\to c$<\/li>\n<li>$\\Omega = a \\to c$<\/li>\n<\/ul>\n<p>Lesquelles de ces trois propositions sont correctes ?<\/p>\n<ol>\n<li>$\\Sigma \\models \\Omega$<\/li>\n<li>$\\Omega \\models \\Sigma$<\/li>\n<li>$\\Sigma \\equiv \\Omega$<\/li>\n<\/ol>\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 trois variables et compte tenu du nombre de propositions \u00e0 v\u00e9rifier, la m\u00e9thode des tables de v\u00e9rit\u00e9 sera la plus rapide.<\/p>\n<p>$\\Sigma = \\underset{\\sigma}{(a \\vee b)} \\to c$<\/p>\n<p>$\\Omega = a \\to c$<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$c$<\/th>\n<th style=\"text-align:center\">$\\sigma$<\/th>\n<th style=\"text-align:center\">$\\Sigma$<\/th>\n<th style=\"text-align:center\">$\\Omega$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On constate que parmi les trois propositions, la seule correcte est $\\Sigma \\models \\Omega$ (tout mod\u00e8le de $\\Sigma$ est mod\u00e8le de $\\Omega$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent1.5<\/h4>\n<p>On consid\u00e8re une boule rouge, une bleue, une verte et une urne. Chaque boule peut \u00eatre soit dans l&rsquo;urne, soit \u00e0 l&rsquo;ext\u00e9rieur. Les situations des boules sont repr\u00e9sent\u00e9es par 3 variables $r, v, b$. Par convention, la variable $r$ a la valeur 1 si la boule rouge est dans l&rsquo;urne et 0 sinon. Les variables $b$ et $v$ repr\u00e9sentent les boules bleue et verte avec la m\u00eame convention.<\/p>\n<p>Vous devez mod\u00e9liser chacune des deux propositions suivantes par une formule propositionnelle.<\/p>\n<ol>\n<li>Il y a exactement 2 boules dans l&rsquo;urne.<\/li>\n<li>Il y a au moins 2 boules dans l&rsquo;urne.<\/li>\n<\/ol>\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 une solution pour la proposition 1.<\/p>\n<p>$(r \\wedge v \\wedge \\neg b)$ $\\vee$ $(r \\wedge \\neg v \\wedge b)$ $\\vee$ $(\\neg r \\wedge v \\wedge b)$<\/p>\n<p>Il y en a d&rsquo;autres (toutes logiquement \u00e9quivalentes). Si vous en avez une, vous pouvez v\u00e9rifier qu&rsquo;elle est correcte en comparant sa table de v\u00e9rit\u00e9 avec celle de la formule ci-dessus. Soyez vigilants car certaines formules peuvent para\u00eetre correctes \u00e0 une personne inexp\u00e9riment\u00e9e alors qu&rsquo;elles ne le sont pas.<\/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 une solution pour la proposition 2.<\/p>\n<p>$(r \\wedge v) \\vee (r \\wedge b) \\vee ( v \\wedge b)$<\/p>\n<p>Pour satisfaire cette formule, il est n\u00e9cessaire et suffisant qu&rsquo;au moins une des sous-formules $r \\wedge v$, $r \\wedge b$ ou $v \\wedge b$ soit satisfaite, ce qui suppose qu&rsquo;au moins deux des variables ait la valeur 1.<\/p>\n<p>Mais des formules syntaxiquement tr\u00e8s diff\u00e9rentes peuvent \u00eatre aussi des solutions. Pour v\u00e9rifier, il faut comparer leurs tables de v\u00e9rit\u00e9 \u00e0 celle de la solution propos\u00e9e.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent1.6<\/h4>\n<p>On consid\u00e8re deux type de pions : les blancs et les noirs, et un damier de 4 cases num\u00e9rot\u00e9es comme indiqu\u00e9 sur la figure ci-dessous.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/plfc5.png\" alt=\"plfc5\"><\/p>\n<p>On repr\u00e9sente les situations (sc\u00e9narios) du damier avec 8 variables propositionnelles : $b_1, b_2, b_3, b_4$ et $n_1, n_2, n_3, n_4$. Par convention, les valeurs des variables ont le sens suivant :<\/p>\n<ul>\n<li>$b_i$ vaut 1 si un pion blanc se trouve sur la case $i$ et vaut 0 dans le cas contraire.<\/li>\n<li>$n_i$ vaut 1 si un pion noir se trouve sur la case $i$ et vaut 0 dans le cas contraire.<\/li>\n<\/ul>\n<p>Donnez les formules permettant de mod\u00e9liser chacune des propositions suivantes :<\/p>\n<ol>\n<li>Une case ne peut contenir \u00e0 la fois un pion blanc et un pion noir. (Elle peut \u00eatre vide ou contenir un pion blanc ou un pion noir.)<\/li>\n<li>Il y a exactement un pion noir sur le damier.<\/li>\n<li>Au moins une des deux diagonales est vide (elle ne contient aucun pion).<\/li>\n<\/ol>\n<p><strong>Conseil<\/strong> : pour chacune des trois formules, commencez par identifier les variables concern\u00e9es.<\/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>Mod\u00e9lisation de la proposition 1 :<\/p>\n<p>$\\neg (b_1 \\wedge n_1)$ $\\wedge$ $\\neg (b_2 \\wedge n_2)$ $\\wedge$ $\\neg (b_3 \\wedge n_3)$ $\\wedge$ $\\neg (b_4 \\wedge n_4) $<\/p>\n<p>ou encore<\/p>\n<p>$(\\neg b_1 \\vee \\neg n_1)$ $\\wedge$ $(\\neg b_2 \\vee \\neg n_2)$ $\\wedge(\\neg b_3 \\vee \\neg n_3)$ $\\wedge$ $(\\neg b_4 \\vee \\neg n_4)$<\/p>\n<p>ou toute formule logiquement \u00e9quivalente.<\/p>\n<p>Dans les deux solutions donn\u00e9es, chaque sous-formule \u00e9limine le sc\u00e9nario dans lequel une des cases contient un pion blanc et un pion noir.<\/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>Mod\u00e9lisation de la proposition 2 :<\/p>\n<p>$(n_1 \\wedge \\neg n_2 \\wedge \\neg n_3 \\wedge \\neg n_4)$ $\\vee$ $(\\neg n_1 \\wedge  n_2 \\wedge \\neg n_3 \\wedge \\neg n_4)$ $\\vee$ $(\\neg n_1 \\wedge \\neg n_2 \\wedge n_3 \\wedge \\neg n_4)$ $\\vee$ $(\\neg n_1 \\wedge \\neg n_2 \\wedge \\neg n_3 \\wedge n_4)$<\/p>\n<blockquote>\n<p>La premi\u00e8re sous-formule est satisfaite si la case 1 contient un pion noir et si les autres cases n&rsquo;en contiennent pas. Les autres sous formules sont satisfaites par les trois autres configurations autoris\u00e9es pour les pions noirs. Les pions blancs ne sont pas pris en compte ici car ils ne sont pas concern\u00e9 par la proposition \u00e0 mod\u00e9liser.<\/p>\n<\/blockquote>\n<p>Autre solution :<\/p>\n<p>$(n_1 \\vee n_2 \\vee n_3 \\vee n_4)$ $\\wedge$ $\\neg (n_1 \\wedge n_2)$ $\\wedge$ $\\neg (n_1 \\wedge n_3)$ $\\wedge$ $\\neg (n_1 \\wedge n_4)$ $\\wedge$ $\\neg (n_2 \\wedge n_3)$ $\\wedge$ $\\neg (n_2 \\wedge n_4)$ $\\wedge$ $\\neg (n_3 \\wedge n_4)$<\/p>\n<blockquote>\n<p>La premi\u00e8re sous-formule impose qu&rsquo;il y ait au moins un pion noir dans une case. Chacune des autres interdit que deux cases distinctes contiennent un pion noir.<\/p>\n<\/blockquote>\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\u00e9ponse3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Mod\u00e9lisation de la proposition 3 :<\/p>\n<p>$(\\neg b_1 \\wedge \\neg b_4 \\wedge \\neg n_1 \\wedge \\neg n_4)$ $\\vee$ $(\\neg b_2 \\wedge \\neg b_3 \\wedge \\neg n_2 \\wedge \\neg n_3)$<\/p>\n<blockquote>\n<p>La premi\u00e8re sous-formule est satisfaite si et seulement si la diagonale constitu\u00e9es des cases 1 et 4 ne contient aucun pion. La deuxi\u00e8me sous-formule exprime la m\u00eame chose pour l&rsquo;autre diagonale.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<h3>It\u00e9ration C.ent2<\/h3>\n<h4>Exercice d&rsquo;entrainement C.ent2.1<\/h4>\n<p>La formule suivante est elle une tautologie ? Est-elle coh\u00e9rente ?<\/p>\n<p>$\\neg((a \\to b) \\wedge (b \\to c)) \\vee (a \\to c)$<\/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>Avec trois variables, la m\u00e9thode de la table de v\u00e9rit\u00e9 est applicable. On pourra faire apparaitre les valeurs de v\u00e9rit\u00e9 des sous-formules $\\sigma_1$, $\\sigma_2$, $\\sigma_3$, $\\sigma$, $\\neg \\sigma$.<\/p>\n<p>$\\Sigma$ $=$ $\\neg\\underbrace{(\\underset{\\sigma_1}{(a \\to b)} \\wedge \\underset{\\sigma_2}{(b \\to c)})} _{\\sigma} \\vee \\underset{\\sigma_3}{(a \\to c)}$<\/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<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$c$<\/th>\n<th style=\"text-align:center\">$\\sigma_1$<\/th>\n<th style=\"text-align:center\">$\\sigma_2$<\/th>\n<th style=\"text-align:center\">$\\sigma$<\/th>\n<th style=\"text-align:center\">$\\neg \\sigma$<\/th>\n<th style=\"text-align:center\">$\\sigma_3$<\/th>\n<th style=\"text-align:center\">$\\Sigma$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On constate que $\\Sigma$ est une tautologie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent2.2<\/h4>\n<p>Soient les formules suivantes :<\/p>\n<ul>\n<li>$\\Sigma = (a \\wedge b) \\to c$<\/li>\n<li>$\\Omega = a \\to c$<\/li>\n<\/ul>\n<p>Lesquelles de ces trois propositions sont correctes ?<\/p>\n<ol>\n<li>$\\Sigma \\models \\Omega$<\/li>\n<li>$\\Omega \\models \\Sigma$<\/li>\n<li>$\\Sigma \\equiv \\Omega$<\/li>\n<\/ol>\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 trois variables et compte tenu du nombre de propositions \u00e0 v\u00e9rifier, la m\u00e9thode des tables de v\u00e9rit\u00e9 sera la plus rapide.<\/p>\n<p>$\\Sigma = \\underbrace{(a \\wedge b)}_{\\sigma} \\to c$<\/p>\n<p>$\\Omega = a \\to c$<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$a$<\/th>\n<th style=\"text-align:center\">$b$<\/th>\n<th style=\"text-align:center\">$c$<\/th>\n<th style=\"text-align:center\">$\\sigma$<\/th>\n<th style=\"text-align:center\">$\\Sigma$<\/th>\n<th style=\"text-align:center\">$\\Omega$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On constate que parmi les trois propositions, la seule correcte est $\\Omega \\models \\Sigma$ (tout mod\u00e8le de $\\Omega$ est mod\u00e8le de $\\Sigma$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent2.3<\/h4>\n<p>On repr\u00e9sente un entier $A$ compris entre 0 et 3 par 2 variables propositionnelles $a_1, a_0$. Les valeurs de ces deux variables repr\u00e9sentent la valeur de $A$ en base 2.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align:center\">$A$<\/th>\n<th style=\"text-align:center\">$a_1$<\/th>\n<th style=\"text-align:center\">$a_0$<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">0<\/td>\n<td style=\"text-align:center\">1<\/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\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align:center\">3<\/td>\n<td style=\"text-align:center\">1<\/td>\n<td style=\"text-align:center\">1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>On repr\u00e9sente un entier $B$ de mani\u00e8re similaire avec deux variables propositionnelles $b_1, b_0$.<\/p>\n<p>Donnez une formule propositionnelle mod\u00e9lisant la propri\u00e9t\u00e9 $A \\neq 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>$\\underbrace{(a_0 \\wedge \\neg b_0) \\vee (\\neg a_0 \\wedge b_0)}_ {\\sigma_1}$ $\\vee$ $\\underbrace{(a_1 \\wedge \\neg b_1) \\vee (\\neg a_1 \\wedge b_1)}_ {\\sigma_2}$<\/p>\n<p>La sous-formule $\\sigma_1$ est satisfaite si et seulement si $a_0$ a une valeur diff\u00e9rente de $b_0$ (l&rsquo;une a la valeur 0 et l&rsquo;autre a la valeur 1). La sous-formule $\\sigma_2$ est satisfaite si et seulement si $a_1$ a une valeur diff\u00e9rente de $b_1$.<\/p>\n<p>Or $A\\neq B$ si et seulement si leurs repr\u00e9sentations en base 2 diff\u00e8rent par la valeur d&rsquo;au moins un bit, c&rsquo;est \u00e0 dire si $\\sigma_1$ ou $\\sigma_2$ s&rsquo;interpr\u00e8te \u00e0 1.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement C.ent2.4<\/h4>\n<p>Soit un mot binaire de 5 bits. Chaque bit est repr\u00e9sent\u00e9 par une variable propositionnelle. Les variables sont nomm\u00e9es $b_0$ (bit le plus \u00e0 droite) \u00e0 $b_4$ (le plus \u00e0 gauche). Donnez une formule aussi courte que possible qui mod\u00e9lise pr\u00e9cis\u00e9ment la proposition suivante : \u00ab Le mot ne comporte aucune s\u00e9quence de deux bits \u00e0 1 cons\u00e9cutifs. \u00bb Par exemple, 01110 ne v\u00e9rifie pas la propri\u00e9t\u00e9 car il comporte au moins une s\u00e9quence de deux bits \u00e0 1 situ\u00e9s l\u2019un apr\u00e8s l\u2019autre, alors que 01000 satisfait la propri\u00e9t\u00e9 \u00e0 mod\u00e9liser.<\/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>On peut construire la formule comme une conjonction de sous-formules.<\/p>\n<p>$\\Sigma = \\sigma_0 \\wedge \\cdots \\wedge \\sigma_3$<\/p>\n<p>Chaque sous-formule $\\sigma_i$ concerne les deux bits repr\u00e9sent\u00e9s par les variables $b_i$ et $b_{i+1}$ et interdit que les deux variables aient la valeur 1.<\/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>$\\Sigma$ $=$ $\\neg (b_0 \\wedge b_1)$ $\\wedge$ $\\neg (b_1 \\wedge b_2)$ $\\wedge$ $\\neg (b_2 \\wedge b_3)$ $\\wedge$ $\\neg (b_3 \\wedge b_4)$<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Activit\u00e9 C.top<\/h2>\n<p>Cette activit\u00e9 propose des exercices de <strong>consolidation<\/strong> qui ne doivent \u00eatre abord\u00e9s que par les personnes apprenantes ma\u00eetrisant bien la partie A et les parties suivantes disponibles.<\/p>\n<p>Par exemple, si les parties actuellement disponibles sont A et B, vous devez d&rsquo;abord ma\u00eetriser la parie B avant de faire cette activit\u00e9 de consolidation de la partie A.<\/p>\n<h3>C.top1<\/h3>\n<h4>Exercice de consolidation C.top1<\/h4>\n<p>On appelle litt\u00e9ral une variable propositionnelle ou la n\u00e9gation d&rsquo;une variables propositionnelle. Par exemple, $a$ et $\\neg a$ sont des litt\u00e9raux. Pour tout litt\u00e9ral $w$, $\\neg \\neg w$ se simplifie en $w$.<\/p>\n<p>Soit $L_1 = {x_1, \\cdots, x_n}$ et $L_2 = {y_1, \\cdots, y_k}$  deux ensembles de litt\u00e9raux respectant les deux propri\u00e9t\u00e9s suivantes :<\/p>\n<ol>\n<li>$\\forall w \\in L_1, \\neg w \\notin L_2$<\/li>\n<li>$\\forall w \\in L_2, \\neg w \\notin L_1$<\/li>\n<\/ol>\n<p>En d&rsquo;autres termes, aucun des deux ensembles ne contient la n\u00e9gation d&rsquo;un litt\u00e9ral appartenant \u00e0 l&rsquo;autre ensemble.<\/p>\n<p>Soit $z$ un litt\u00e9ral n&rsquo;appartenant ni \u00e0 $L_1$, ni \u00e0 $L_2$.<\/p>\n<p>Soient :<\/p>\n<ul>\n<li>$p = (x_1 \\vee \\cdots \\vee x_n \\vee z)$,<\/li>\n<li>$q = (y_1 \\vee \\cdots \\vee y_k \\vee \\neg z)$,<\/li>\n<li>$r = (x_1 \\vee \\cdots \\vee x_n \\vee y_1 \\vee \\cdots \\vee y_k)$.<\/li>\n<\/ul>\n<p>Montrez que $p \\wedge q \\models r$.<\/p>\n<p>Pour bien visualiser la propri\u00e9t\u00e9 \u00e0 d\u00e9montrer, observons un exemple d&rsquo;application de cette propri\u00e9t\u00e9 :<\/p>\n<p>$\\underbrace{(a \\vee b \\vee \\neg c)} _{p} \\wedge \\underbrace{(a \\vee \\neg d \\vee c)} _{q}$ $\\models$ $\\underbrace{(a \\vee b \\vee \\neg d)} _{r}$<\/p>\n<p>La variable $c$, qui apparait sous forme &quot;n\u00e9gative&quot; dans $p$ et &quot;positive&quot; dans $q$ est appel\u00e9e <strong>variable pivot<\/strong>. Il doit y a voir une et une seule variable pivot pour que la propri\u00e9t\u00e9 soit applicable. La formule $r$ est appel\u00e9e <strong>r\u00e9solvante<\/strong> de $p$ et $q$.<\/p>\n<p>L&rsquo;application directe de la propri\u00e9t\u00e9 \u00e0 d\u00e9montrer donne la r\u00e9solvante $(a \\vee b \\vee a \\vee \\neg d)$ qui se simplifie en $(a \\vee b \\vee \\neg d)$.<\/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>Pour montrer la cons\u00e9quence logique, on peut proc\u00e9der par s\u00e9paration en utilisant la variable pivot comme variable de s\u00e9paration. Il faut monter que tout mod\u00e8le de $p \\wedge q$ dans lequel la variable pivot a la valeur 0 est un mod\u00e8le de $r$ et que tout mod\u00e8le de $p \\wedge q$ dans lequel la variable pivot a la valeur 1 est un mod\u00e8le de $r$.<\/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;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On revient au cas g\u00e9n\u00e9ral :<\/p>\n<p>Soient :<\/p>\n<ul>\n<li>$p = (x_1 \\vee \\cdots \\vee x_n \\vee z)$,<\/li>\n<li>$q = (y_1 \\vee \\cdots \\vee y_k \\vee \\neg z)$,<\/li>\n<li>$r = (x_1 \\vee \\cdots \\vee x_n \\vee y_1 \\vee \\cdots \\vee y_k)$.<\/li>\n<\/ul>\n<p>On veux monter que $p \\wedge q \\models r$.<\/p>\n<p>Soit un mod\u00e8le $M$ de $p \\wedge q$ pour lequel le litt\u00e9ral $z$ vaut 0. D&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\wedge$, $M$ satisfait n\u00e9cessairement $p$, donc il satisfait au moins un des litt\u00e9raux $x_1, \\cdots, x_n$, donc il satisfait $r$.<\/p>\n<p>Soit un mod\u00e8le $M$ de $p \\wedge q$ pour lequel le litt\u00e9ral $z$ vaut 1. D&rsquo;apr\u00e8s la table de v\u00e9rit\u00e9 du connecteur $\\wedge$, $M$ satisfait n\u00e9cessairement $q$, donc il satisfait au moins un des litt\u00e9raux $y_1, \\cdots, y_k$, donc il satisfait $r$.<\/p>\n<p>Donc tout mod\u00e8le de $p \\wedge q$ est un mod\u00e8le de $r$.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice de consolidation C.top2<\/h4>\n<p>Cet exercice fait suite \u00e0 l&rsquo;exercice pr\u00e9c\u00e9dent et utilise la propri\u00e9t\u00e9 qui y est d\u00e9montr\u00e9e. On appelle <strong>clause<\/strong> toute disjonction de litt\u00e9raux $(w_1 \\wedge \\cdots \\wedge w_n)$. La r\u00e8gle de d\u00e9duction pr\u00e9sent\u00e9e pr\u00e9c\u00e9demment est appel\u00e9e <strong>R\u00e9solution<\/strong> (avec un grand R). Elle s&rsquo;applique \u00e0 deux clauses $p$ et $q$, appel\u00e9es <strong>pr\u00e9misses<\/strong>, r\u00e9pondant aux conditions suivantes :<\/p>\n<ul>\n<li>Une unique variable pivot $u$ apparait sous forme positive $u$ dans une des clauses et n\u00e9gative $\\neg u$ dans l&rsquo;autre.<\/li>\n<li>Aucune autre variable que $u$ n&rsquo;apparait sous forme positive dans une des clause et n\u00e9gative dans l&rsquo;autre.<\/li>\n<\/ul>\n<p>Elle permet de d\u00e9duire une clause cons\u00e9quence logique des deux pr\u00e9misses, appel\u00e9e <strong>r\u00e9solvante<\/strong>, dans la quelles on retrouve les litt\u00e9raux de $p$ et $q$ \u00e0 l&rsquo;exception de ceux bas\u00e9s sur la variable pivot.<\/p>\n<p>Par exemple, la r\u00e9solvante de $(a \\vee b \\vee c)$ et de $(b \\vee \\neg c)$ est la clause $(a \\vee b)$.<\/p>\n<p>Incidemment, si une variable $v$ apparait sous forme positive et n\u00e9gative dans une m\u00eame clause, cette clause est une tautologie qui peut \u00eatre simplifi\u00e9e en $\\top$, puisqu&rsquo;elle est n\u00e9cessairement satisfaite quelle que soit la valeur de v\u00e9rit\u00e9 de $v$. Par exemple, la clause $(a \\vee \\neg b \\vee \\neg a)$ est une tautologie.<\/p>\n<p>D&rsquo;autre part, dans le cas particulier o\u00f9 les deux pr\u00e9misses contiennent uniquement la variable pivot, la r\u00e9solvante est la clause vide, qui est \u00e9quivalente \u00e0 $\\bot$. Par exemple la r\u00e9solvante de $(a)$ et $(\\neg a)$ est $()$, c&rsquo;est \u00e0 dire $\\bot$.<\/p>\n<p>Le but de l&rsquo;exercice est de monter que la formule suivante est incoh\u00e9rente en produisant des r\u00e9solvantes jusqu&rsquo;\u00e0 obtenir la clause vide.<\/p>\n<p>$\\Sigma$ $=$ $(a \\vee b)$ $\\wedge$ $(\\neg a \\vee b)$ $\\wedge$ $(a \\vee \\neg b)$ $\\wedge$ $(\\neg a \\vee \\neg b \\vee c)$ $\\wedge$ $(\\neg a \\vee \\neg b \\vee \\neg c)$<\/p>\n<p>Chaque r\u00e9solvante produite \u00e9tant une cons\u00e9quence logique de $\\Sigma$, elle peut \u00eatre utilis\u00e9e ult\u00e9rieurement comme pr\u00e9misse pour r\u00e9aliser de nouvelles d\u00e9duction.<\/p>\n<blockquote>\n<p><strong>Pour information<\/strong> : On dit de toute formule constitu\u00e9e d&rsquo;une conjonction de clauses (des clauses reli\u00e9es par des connecteurs $\\wedge$ ) qu&rsquo;elle est sous forme CNF.<\/p>\n<p>La r\u00e8gle de R\u00e9solution permet de d\u00e9terminer, en un nombre fini d&rsquo;\u00e9tapes, pour toute formule $\\Sigma$ sous forme CNF, si $\\Sigma$ est incoh\u00e9rente ou coh\u00e9rente. Si la clause vide est produite, alors $\\Sigma$ est incoh\u00e9rente. Si  aucune nouvelle r\u00e9solvante ne peut \u00eatre produite et que la clause vide n&rsquo;a pas \u00e9t\u00e9 produite, alors $\\Sigma$ est coh\u00e9rente.<\/p>\n<\/blockquote>\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>On peut num\u00e9roter les clauses :<\/p>\n<p>$\\Sigma$ $=$ $\\underset{q_1}{(a \\vee b)}$ $\\wedge$ $\\underset{q_2}{(\\neg a \\vee b)}$ $\\wedge$ $\\underset{q_3}{(a \\vee \\neg b)}$ $\\wedge$ $\\underset{q_4}{(\\neg a \\vee \\neg b \\vee c)}$ $\\wedge$ $\\underset{q_5}{(\\neg a \\vee \\neg b \\vee \\neg c)}$<\/p>\n<p>Une premi\u00e8re r\u00e9solvante peut \u00eatre produite avec les deux premi\u00e8re clauses :<\/p>\n<p>$q_1 \\wedge q_2 \\models \\underset{q_7}{(b)}$<\/p>\n<p>\u00c0 vous de continuer. Le r\u00e9sultat ne d\u00e9pend pas de l&rsquo;ordre dans lequel vous faites les d\u00e9ductions.<\/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>$q_7 \\wedge q_3 \\models \\underset{q_8}{(a)}$<\/p>\n<p>$q_8 \\wedge q_4 \\models \\underset{q_9}{(\\neg b \\vee c)}$<\/p>\n<p>$q_8 \\wedge q_5 \\models \\underset{q_{10}}{(\\neg b \\vee \\neg c)}$<\/p>\n<p>$q_9 \\wedge q_{10} \\models \\underset{q_{11}}{(\\neg b)}$<\/p>\n<p>$q_7 \\wedge q_{11} \\models \\bot$<\/p>\n<p><\/div>\n\t\t\t<\/div>\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-282","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\/282","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=282"}],"version-history":[{"count":14,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/282\/revisions"}],"predecessor-version":[{"id":331,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/282\/revisions\/331"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}