Nous allons dans ce chapitre étudier les règles formelles qui régissent le raisonnement à travers la logique des propositions. On distingue en général trois types (ou trois niveaux) de logiques. La logique d’ordre 0 (ou calcul des propositions) est celle qui régit le raisonnement classique par implications et équivalences. La logique d’ordre 1 (ou calcul des prédicats) introduit en plus les deux quantificateurs pour tout et il existe. Enfin la logique d’ordre 2 introduit en supplément le raisonnement par récurrence. Nous allons pour notre part nous limiter au raisonnement classique, c’est à dire au calcul des propositions.
Définition 4.1.1 On appelle proposition (ou assertion) toute phrase dont il est possible de dire si elle est vraie ou fausse.
Exemple
A partir d’une proposition p, on peut construire sa négation que nous noterons (très provisoirement) NON p. La règle à appliquer est que si p est vraie, alors NON p est fausse et que si p est fausse alors NON p est vraie.
Exemple
A partir de deux propositions p et q, on peut construire leur conjonction que nous noterons provisoirement p ET q. La proposition p ET q est vraie si et seulement si les deux propositions p et q sont vraies, dans tous les autres cas elle est fausse.
Exemple
A partir de deux propositions p et q, on peut construire leur disjonction que nous noterons provisoirement p OU q. La proposition p OU q est vraie si et seulement si l’une au moins des deux propositions p et q est vraie ; sinon elle est fausse.
Exemple
Remarque Il faut éviter de confondre le OU que nous venons d’introduire (ou inclusif ) de la conjonction de coordination ou du Français qui désigne souvent un ou exclusif (l’un des deux est vrai et seulement l’un des deux). A cet effet nous pourrons définir le symbole OUX pour désigner ce ou exclusif.
Nous avons donc introduit trois opérateurs (et même quatre si l’on compte en plus le ou exclusif ) sur les propositions. On sait également en Mathématiques que l’on est souvent amené à considérer deux opérateurs supplémentaires de raisonnement qui sont l’implication logique p IMPL q et l’équivalence logique p EQUIV q que nous considérerons comme deux opérateurs binaires supplémentaires, avec les règles suivantes
Définition 4.1.2 Si p et q désignent deux propositions, alors
Remarque Une autre façon de formuler l’implication est de remplacer p IMPL q par si p alors q. L’idée intuitive qui régit la valeur de l’implication peut parfois sembler étrange : pourquoi p IMPL q est-il vrai lorsque p est une proposition fausse. Mais cela se comprend assez bien sur un exemple. Imaginons que je vous fasse l’assertion suivante : si vous venez me voir demain alors je vous donnerai 1000F. Autrement dit, dans le cadre des propositions : vous venez me voir demain IMPL je vous donnerai 1000F. Examinons les différentes possibilités de comportement.
Nous venons de voir comment à partir de propositions qui sont des phrases, nous pouvions construire de nouvelles propositions en utilisant les opérateurs NON, ET, OU, IMPL et EQUIV. On construit ainsi des lois internes sur l’ensemble des propositions. Nous allons en conséquence transformer nos manipulations de phrases en un véritable calcul algébrique. De ce point de vue, il est essentiel de distinguer entre les règles formelles d’écriture des propositions (règles formelles que pourra appliquer l’ordinateur), c’est à dire la syntaxe du calcul des propositions, avec la signification que l’on va leur donner à travers une évaluation en vrai ou faux, autrement dit la sémantique de ce calcul.
A cet effet, nous considérerons des variables (en général p, q, r éventuellement indexées en p1,…,pn, q1,…, r1,…) auxquelles nous pourrons substituer n’importe quelles propositions ; ces variables seront appelées des variables propositionnelles. Pour supprimer toute connotation aux opérateurs, qui serait trop chargée de sens (et donc non signifiante pour une machine), nous remplacerons
Considérons alors l’ensemble A formé des variables propositionnelles, des symboles d’opérateurs logiques et des parenthèses ouvrante et fermante, c’est à dire des symboles suivants
et l’ensemble A* des suites finies d’éléments de A (écrites par juxtaposition de gauche à droite).
Définition 4.1.3 On appelle ensemble des formules logiques le sous ensemble de A* défini inductivement par
Nous nous autoriserons par la suite, dans une formule logique, à oublier une éventuelle parenthèse ouvrante initiale et la parenthèse fermante finale correspondante. Mais nous n’introduirons pas de règle de priorité sur les opérateurs logiques et en conséquence nous ne nous autoriserons pas à supprimer de quelconques parenthèses intermédiaires.
Exemple
Sans essayer de définir de manière précise les arbres informatiques (notion qui figure au programme de deuxième année), nous allons représenter graphiquement les formules logiques de manière inductive de la façon suivante
où Figure: fif11 représente la formule F.
Exemple La formule logique ((¬p1) ∨ p2) ⇐⇒ (q1 ∧ q2) admet la représentation arborescente Figure: fig00 où Figure: fig01 et Figure: fig02 désignent les représentations arborescentes respectives de (¬p1) ∨ p2 et q1 ∧ q2, soit encore Figure: fig1 et Figure: fig2.
On obtient ainsi la représentation arborescente Figure: fig3 pour l’expression totale.
Inversement, à partir d’un arbre dont les feuilles1 sont des variables propositionnelles, les noeuds2 d’ordre 1 sont étiquetés par le symbole ¬ et les noeuds d’ordre 2 sont étiquetés par l’un des symboles ∨,∧,⊗,⇒, ⇐⇒ , il est facile de reconstruire la formule logique de départ en appliquant récursivement les règles
lorsque F, F1 et F2 désignent les formules représentées par les sous arbres Figure: fif11, Figure: fig01 et Figure: fig02 et point d’interrogation l’un des opérateurs logiques binaires.
A chaque formule logique, nous allons maintenant assigner une signification logique lorsque les variables propositionnelles représentent des propositions susceptibles d’être vraies ou fausses. Pour faciliter le calcul algébrique sur les formules logiques, il est habituel de remplacer les mots vrai et faux qui sont les deux valeurs prises par les propositions par V et F ou encore mieux par 1 et 0. C’est cette dernière convention que nous suivrons par la suite.
Nous allons commencer par évaluer les opérateurs logiques ¬,∧,∨,⊗,⇒,⇔ en les rapprochant des opérateurs correspondants introduit précédemment sur les propositions, à savoir NON, ET, OU, OUX, IMPL, EQUIV. A cet effet nous introduirons les fonctions f¬,f∧,f∨,f⊗,f⇒,f⇔ définies
et à valeurs dans {0,1}, grâce aux formules suivantes (qui suivent exactement les valeurs de vérité de NON, ET, OU, OUX, IMPL, EQUIV).
Soit maintenant σ une application de l’ensemble des valeurs propositionnelles dans {0,1} (c’est à dire que l’on assigne à chaque variable propositionnelle l’une des valeurs faux ou vrai). On définit alors facilement la valeur d’une formule logique élémentaire, par exemple par V al(p∨q,σ) = f∨(σ(p),σ(q)). Nous allons étendre cette évaluation à toute formule logique de manière inductive grâce aux règles suivantes :
Remarque Cette évaluation des formules logiques est encore équivalente à l’opération suivante (très facile à exécuter à l’aide d’un logiciel de calcul formel) :
Soit F une formule logique dépendant de n variables propositionnelles distinctes (chacune
d’entre elles pouvant apparaître plusieurs fois dans la formule). A chacune des 2n applications
σ de l’ensemble des variables propositionnelles dans {0,1}, on sait donc associer la valeur de F
dans l’environnement σ, notée V al(F,σ) {0,1}.
Lorsque n n’est pas trop grand, on a l’habitude de regrouper dans un même tableau les différentes valeurs σ attribuées aux variables propositionnelles et l’évaluation de F correspondante. A cet effet on construit un tableau à n + 1 colonnes et à 2n lignes. Dans les n premières colonnes on met les valeurs 0 ou 1 attribuées aux valeurs propositionnelles (avec par exemple un ordre lexicographique consistant à faire varier d’abord la n-ième variable propositionnelle, puis la n - 1-ième et ainsi de suite jusqu’à la première) et dans la dernière colonne on met la valeur correspondante de V al(F,σ). Un tel tableau est appelé une table de vérité.
Commençons par construire les tables de vérité des opérations élémentaires sur les variables propositionnelles données par les opérateurs ¬,∧,∨,⊗,⇒ et ⇔.
p | ¬p |
1 | 0 |
0 | 1 |
p | q | p ∧ q |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
p | q | p ∨ q |
1 | 1 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
p | q | p ⊗ q |
1 | 1 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
p | q | p ⇒ q |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
p | q | p ⇔ q |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
La table de vérité d’une formule logique plus complexe peut alors se construire en introduisant des colonnes intermédiaires pour les sous formules. C’est ainsi que l’on pourra construire en plusieurs étapes la table de vérité de la formule logique
de la manière suivante
p | q | r | ¬p | (¬p) ∨ q | ((¬p) ∨ q) ∧ r | p ⊗ r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
On appelle tautologie toute formule logique qui est vraie quelles que soient les valeurs que l’on attribue aux variables propositionnelles. C’est donc une formule dont la table de vérité ne comprend que des 1 dans la dernière colonne, ou encore qui satisfait à la définition suivante.
Définition 4.1.4 On dit qu’une formule logique F est une tautologie si pour toute application σ de l’ensemble des variables propositionnelles dans {0,1}, l’évaluation de F dans l’environnement σ vérifie V al(F,σ) = 1.
Exemple La formule logique (p ⇒ q) ⇐⇒ ((¬p) ∨q) est une tautologie. En effet la table de vérité de cette formule est
p | q | p ⇒ q | ¬p | (¬p) ∨ q | (p ⇒ q) ⇐⇒ ((¬p) ∨ q) |
1 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 |
Nous dirons qu’une formule est satisfiable si l’on peut attribuer aux variables propositionnelles des valeurs pour lesquelles la formule est vraie. De manière précise, on a la définition suivante
Définition 4.1.5 On dit qu’une formule logique F est satisfiable s’il existe une application σ de l’ensemble des variables propositionnelles dans {0,1} telle que V al(F,σ) = 1.
Une formule qui n’est pas satisfiable est dite contradictoire ; on dit encore que c’est une contradiction. Une formule F est contradictoire si et seulement si la formule (¬F) est une tautologie. On constate ainsi que le problème de tester si une formule est une tautologie ou de tester si une formule est satisfiable sont intimement reliés.
Il existe un moyen évident de tester si une formule logique est satisfiable : c’est de construire la table de vérité de la formule et de tester l’existence d’un 1 dans la dernière colonne. Cela revient à donner les 2n valeurs possibles à la famille des n variables propositionnelles qui interviennent dans la formule et à évaluer la formule dans chacun de ces environnements. Le temps de calcul de cette méthode est clairement proportionnel à 2n. Aussi curieux que cela puisse paraître, on ne connait à l’heure actuelle aucun algorithme réellement plus performant que cet essai systématique et on ne sait même pas s’il peut en exister. Ce problème de la satisfiabilité d’une formule logique entre dans une catégorie de problèmes dont on peut montrer qu’ils sont en un certain sens équivalents, les problèmes NP-complets, problèmes dont à l’heure actuelle on ne connait que des solutions dont le temps de calcul est exponentiel en la taille des données. Parmi ceux ci on peut citer le problème du déménageur (optimiser le chargement d’un camion avec des colis de différentes tailles) et le problème du voyageur de commerce (trouver le plus court chemin reliant certaines villes données sans repasser deux fois dans la même ville).
Définition 4.2.1 On appelle fonction booléenne toute application f : {0,1}n →{0,1}.
Définition 4.2.2 Soit F une formule logique. Soit p1,…,pn un ensemble ordonné de
variables propositionnelles contenant3
toutes les variables propositionnelles intervenant dans F. On associe à F la fonction
booléenne fF de {0,1}n dans {0,1} définie par fF(x1,…,xn) = V al(F,σ) où σ est
définie par ∀i [1,n], σ(pi) = xi.
La fonction booléenne associée à une formule logique et à la famille de ses variables propositionnelles se lit directement sur la table de vérité de la formule logique. C’est la fonction qui aux éléments des n premières colonnes associe l’élément correspondant de la dernière colonne.
Exemple En reprenant une table de vérité précédente, si F = (((¬p) ∨q) ∧r) ⇐⇒ (p⊗r), on a la table de vérité
p | q | r | ¬p | (¬p) ∨ q | ((¬p) ∨ q) ∧ r | p ⊗ r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
ce qui donne fF(1, 0, 1) = fF(0, 1, 1) = fF(0, 1, 0) = fF(0, 0, 1) = fF(0, 0, 0) = 1 et fF(1, 1, 1) = fF(1, 1, 0) = fF(1, 0, 0) = 0.
Remarque Une formule F est une tautologie si et seulement si fF = 1. Une formule est satisfiable si et seulement si fF≠0.
Définition 4.2.3 On dit que deux formules logiques F1 et F2 sont équivalentes si pour toute application σ de l’ensemble des variables propositionnelles dans {0,1}, on a V al(F1,σ) = V al(F2,σ). On notera alors F1 ≡ F2.
Théorème 4.2.1 Soit F1 et F2 deux formules logiques, p1,…,pn un ensemble ordonné de variables propositionnelles contenant toutes les variables propositionnelles intervenant soit dans F1 soit dans F2, fF1 et fF2 les fonctions booléennes associées à F1 et F2. On a équivalence de
Démonstration: L’équivalence des deux premières assertions est évidente puisque seules les valeurs attribuées à p1,…,pn interviennent dans le calcul de V al(F1,σ) et de V al(F2,σ). L’équivalence entre la première assertion et la troisième résulte de ce que V al(F1 ⇔ F2) = f⇔(V al(F1,σ),V al(F2,σ)) qui d’après la définition de f⇔ vaut 1 si et seulement si V al(F1,σ) = V al(F2,σ).
Proposition 4.2.1 L’équivalence des formules logiques est une relation d’équivalence sur l’ensemble des formules logiques.
Démonstration: La définition même montre que cette relation est à la fois réfléxive, symétrique et transitive.
Théorème 4.2.2 (invariance de l’équivalence par substitution) Soit F1 et F2 deux formules logiques équivalentes dépendant des variables propositionnelles p1,…,pn et soit G1,…,Gn une famille de n formules logiques. Soit F1′ et F2′ les formules logiques obtenues en remplaçant dans F1 et F2 les variables p1,…,pn par G1,…,Gn. Alors F1′ et F2′ sont encore équivalentes.
Démonstration: Soit q1,…,qp les variables propositionnelles intervenant dans G1,…,Gn. Soit σ une application de {q1,…,qp} dans {0,1}. On démontre immédiatement par induction structurelle sur F1 que V al(F1′,σ) = fF1(V al(G1,σ),…,V al(Gn,σ)). Mais comme F1 et F2 sont équivalentes, on a fF1 = fF2, ce qui montre que ∀σ, V al(F1′,σ) = V al(F2′,σ), donc F1′ et F2′ sont équivalentes.
Remarque On s’autorisera par la suite à écrire 1 pour une tautologie générique et 0 pour une contradiction générique, si bien que
Tant qu’on ne s’intéresse qu’à la validité d’un raisonnement ou d’une assertion, on peut remplacer toute formule logique portant sur des variables propositionnelles p1,…,pn par une formule logique équivalente. Ceci nous conduit à examiner un certain nombre d’équivalences fondamentales.
Proposition 4.2.2 Soit F1,F2 et F3 trois formules logiques. Alors
Démonstration: D’après l’invariance de l’équivalence par substitution, il suffit de montrer ces équivalences lorsque F1, F2 et F3 sont trois variables propositionnelles p1, p2 et p3. La vérification est évidente sur les tables de vérités pour la première et la deuxième assertion. Pour la troisième, on peut construire les tables de vérités et on obtient par exemple pour la distributivité de la conjonction par rapport à la disjonction
p1 | p2 | p3 | p1 ∨ p2 | (p1 ∨ p2) ∧ p3 | p1 ∧ p3 | p2 ∧ p3 | (p1 ∧ p3) ∨ (p2 ∧ p3) |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Remarque A partir de maintenant, nous jouerons sur l’associativité de la disjonction pour noter F1 ∨… ∨ Fn à la place de (…((F1 ∨ F2) ∨ F3)…) ∨ Fn-1) ∨ Fn). Nous procéderons de même pour la conjonction.
Proposition 4.2.3 Soit F1 et F2 deux formules logiques. Alors
Démonstration: Comme précédemment, on utilise le théorème d’invariance par substitution pour se limiter au cas où les deux formules sont des variables propositionnelles. Il suffit alors d’établir les tables de vérité.
Proposition 4.2.4 Deux tautologies sont équivalentes. Deux contradictions sont équivalentes. Soit F une formule logique.
Démonstration: Même méthode en remplaçant F par une variable propositionnelle et la tautologie (resp. la contradiction) par une variable propositionnelle assujettie à ne prendre que la valeur 1 (resp. 0).
Proposition 4.2.5 Soit F1 et F2 deux formules logiques. Alors
Démonstration: Même méthode. La deuxième assertion peut également se montrer à l’aide de la première et de la loi du tiers exclu en écrivant
Proposition 4.2.6 Soit F1 et F2 deux formules logiques. Alors F1 ⊗ F2 ≡ (F1 ∧ (¬F2)) ∨ ((¬F1) ∧ F2)
Démonstration: Idem
Définition 4.2.4 On appelle disjonction toute formule logique F s’écrivant F = F1 ∨ …∨Fn où chaque Fi est un littéral, c’est à dire soit une variable propositionnelle pi, soit une négation de variable propositionnelle ¬pi.
Définition 4.2.5 On appelle conjonction toute formule logique F s’écrivant F = F1 ∧… ∧ Fn où chaque Fi est soit une variable propositionnelle pi soit une négation de variable propositionnelle ¬pi.
Remarque Si une variable p apparaît plusieurs fois dans une conjonction, on peut jouer sur la commutativité et les différentes formules p ∧ p ≡ p, (¬p) ∧ (¬p) ≡¬p, (p ∧ (¬p)) ≡ 0 pour transformer la conjonction en une conjonction équivalente où ne figure qu’une seule fois la variable p ou en une contradiction 0. De même, si la variable p apparaît plusieurs fois dans une disjonction, on peut jouer sur la commutativité et les formules p ∨ p ≡ p, (¬p) ∨ (¬p) ≡¬p, (p ∨ (¬p)) ≡ 1 pour transformer la conjonction en une conjonction équivalente où ne figure qu’une seule fois la variable p ou en une tautologie 1. A équivalence près, on pourra toujours supposer que les variables propositionnelles apparaissent au plus une fois dans les conjonctions ou disjonctions.
Lemme 4.2.1 Si F est une conjonction, alors ¬F est équivalente à une disjonction. Si F est une disjonction, alors ¬F est équivalente à une conjonction.
Démonstration: En effet, si F s’écritF = F1 ∨… ∨ Fn où chaque Fi est soit une variable propositionnelle pi, soit une négation de variable propositionnelle ¬pi, d’après les lois de Morgan, ¬F ≡ (¬F1) ∧… ∧ (¬Fp) et chacune des ¬Fi est soit une négation de variable propositionnelle (si Fi est une variable propositionnelle), soit équivalente à une variable propositionnelle (si Fi est une négation de variable propositionnelle). Donc ¬F est équivalente à une conjonction. La démonstration est similaire pour une conjonction F.
Théorème 4.2.3 Toute formule logique F est équivalente à une formule logique F′ = C1 ∨… ∨ Cp où chacune des Ci est une conjonction ; autrement dit toute formule logique est équivalente à une disjonction de conjonctions. De même, toute formule logique est équivalente à une formule logique F′′ = D1∧…∧Dq où chacune des Dj est une disjonction ; autrement dit toute formule logique est équivalente à une conjonction de disjonctions.
Démonstration: On montre les deux résultats à la fois par induction structurelle. Si F est réduite à une variable propositionnelle, alors F est à la fois une conjonction et une disjonction, donc le résultat est clair.
Si F = ¬F1 où F1 est équivalente à une disjonction de conjonctions, on a F1 ≡ C1 ∨… ∨ Cp et alors, d’après la loi de Morgan, F = ¬F1 ≡ (¬C1)∧…∧(¬Cp) ≡ D1∧…∧Dp si ¬Ci ≡ Di où Di est une disjonction (d’après le lemme précédent). De même, si F1 est équivalente à une conjonction de disjonctions, alors F est équivalente à une disjonction de conjonctions.
Si F = F1 ∨ F2 où F1 et F2 sont équivalentes à des disjonctions de conjonctions, on a F1 ≡ C1 ∨… ∨ Cp et F2 ≡ C1′∨… ∨ Cq′ d’où F1 ∨ F2 ≡ C1 ∨… ∨ Cp ∨ C1′∨… ∨ Cq′ qui est encore une disjonction de conjonctions. Si F = F1∨F2 où F1 et F2 sont équivalentes à des conjonctions de disjonctions, on a F1 ≡ D1 ∧… ∧ Dp et F2 ≡ D1′∧… ∧ Dq′, d’où, par distributivité de la disjonction par rapport à la conjonction
où chacune des Di ∨ Dj′ est de façon évidente une disjonction.
On montre de même que si F = F1 ∧ F2 où F1 et F2 sont à la fois des disjonctions de conjonctions et des conjonctions de disjonctions, il en est de même de F. (On peut aussi utiliser la loi de Morgan qui dit que F ≡¬((¬F1) ∨ (¬F2)) pour se ramener aux deux opérations précédentes.)
En ce qui concerne F = F1⊗F2, cela résulte alors de F ≡ (F1∧(¬F2))∨ ((¬F1) ∧ F2) et des résultats déjà démontrés. Il en est de même pour F = F1 ⇒ F2 ≡ (¬F1) ∨ F2. L’équivalence F1 ⇔ F2 ≡ (F1 ⇒ F2) ∧ (F2 ⇒ F1) garantit alors la véracité du résultat pour F = F1 ⇔ F2.
Exemple Soit F = (((¬p) ∨ q) ∧ r) ⇒ (p ⊗ r). On a alors
Pour obtenir une conjonction de disjonctions, il suffit d’utiliser la distributivité de ∨ par rapport à ∧ et d’utiliser les règles de simplification pour ne faire apparaître les variables qu’une seule fois dans chaque disjonction. On a alors
Les méthodes que nous venons de voir pour transformer une formule logique en une formule équivalente qui est soit une conjonction de disjonctions, soit une disjonction de conjonctions sont en fait basées sur des règles formelles de simplification de formules logiques à équivalence près (commutativité, distributivité, etc.). Nous allons maintenant voir d’autres méthodes qui utilisent la fonction booléenne associée à la formule logique.
Lemme 4.2.2 Soit p1,…,pn des variables propositionnelles et σ : {p1,…,pn}→{0,1}.
Posons Fi = pi si σ(pi) = 1 et Fi = (¬pi) si σ(pi) = 0. Soit Cσ la conjonction
Cσ = F1 ∧ … ∧ Fn. Alors pour toute application τ : {p1,…,pn} → {0,1}, on a
V al(Cσ,τ) = .
Démonstration: En effet V al(Fσ,τ) vaut 1 si et seulement si chacun
des V al(Fi,τ) vaut 1, c’est à dire si τ(pi) = ce qui équivaut
à dire que τ = σ.
Théorème 4.2.4 Soit F une formule logique, p1,…,pn les variables propositionnelles
intervenant dans F et pour toute application σ : {p1,…,pn} → {0,1}, soit Cσ la
conjonction définie ci dessus. Soit Σ l’ensemble des applications σ : {p1,…,pn}→{0,1}
telles que V al(F,σ) = 1. Alors F est équivalente à la disjonction de conjonctions
F ≡∨
σΣCσ.
Démonstration: Posons G = ∨
σΣCσ et soit τ une application de
{p1,…,pn} dans {0,1}. Alors V al(G,τ) = 1 si et seulement si au moins l’un
des V al(Cσ,τ) vaut 1 pour un σ
Σ, autrement dit si et seulement si τ est
l’un des σ
Σ, c’est à dire si et seulement si τ
Σ. Donc V al(G,τ) = 1 si et
seulement si V al(F,τ) = 1. Ceci montre bien que ∀τ, V al(G,τ) = V al(F,τ).
Donc F et G sont équivalentes.
Définition 4.2.6 La formule logique ∨
σΣCσ du théorème précédent s’appelle la
forme normale disjonctive de la formule logique F. Les Cσ sont appelés des minterms
(prononcer mine-termes).
Remarque Toutes les conjonctions intervenant dans la forme normale disjonctive de F ont la particularité de contenir toutes les variables propositionnelles de F une et une seule fois, soit par elle mêmes, soit par leur négation.
On peut construire la forme normale disjonctive à partir de la table de vérité de la formule F. On commence par supprimer toutes les lignes pour lesquelles l’évaluation de F donne 0 (correspondant aux σ telles que V al(F,σ)≠1). Pour chaque ligne restante on construit la conjonction obtenue en prenant toutes les variables propositionnelles, celles ayant pour valeur 1 dans la ligne étant prises directement, celles ayant pour valeur 0 étant niées (la conjonction obtenue n’est autre que Cσ). On prend alors la disjonction de toutes les conjonctions ainsi obtenues.
Exemple Repartons de F = (((¬p) ∨ q) ∧ r) ⇔ (p ⊗ r). On a précédemment construit la table de vérité
p | q | r | ¬p | (¬p) ∨ q | ((¬p) ∨ q) ∧ r | p ⊗ r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
Si l’on ne garde que les lignes donnant la valeur 1 on obtient une table réduite
p | q | r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) | conjonction correspondante |
1 | 0 | 1 | 1 | p ∧ (¬q) ∧ r |
0 | 1 | 1 | 1 | (¬p) ∧ q ∧ r |
0 | 1 | 0 | 1 | (¬p) ∧ q ∧ (¬r) |
0 | 0 | 1 | 1 | (¬p) ∧ (¬q) ∧ r |
0 | 0 | 0 | 1 | (¬p) ∧ (¬q) ∧ (¬r) |
d’où
Pour trouver maintenant une conjonction de disjonctions équivalente à une formule F, on peut appliquer la méthode précédente à la formule ¬F puis appliquer les lois de Morgan, c’est à dire remplacer les conjonctions par des disjonctions, les disjonctions par des conjonctions, les pi par des ¬pi et les ¬pi par des pi. Sur la table de vérité, cela revient à ne garder que les lignes pour lesquelles la valeur de F vaut 0 ; pour chacune de ces lignes on construit la disjonction obtenue en prenant toutes les variables logiques, celles ayant pour valeur 0 étant prises directement, celles ayant pour valeur 1 étant niées. On prend alors la conjonction de toutes les disjonctions ainsi obtenues.
Exemple Repartons de F = (((¬p) ∨ q) ∧ r) ⇔ (p ⊗ r). On a précédemment construit la table de vérité
p | q | r | ¬p | (¬p) ∨ q | ((¬p) ∨ q) ∧ r | p ⊗ r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
Si l’on ne garde que les lignes donnant la valeur 0 on obtient une table réduite
p | q | r | (((¬p) ∨ q) ∧ r) ⇐⇒ (p ⊗ r) | disjonction correspondante |
1 | 1 | 1 | 0 | (¬p) ∨ (¬q) ∨ (¬r) |
1 | 1 | 0 | 0 | (¬p) ∨ (¬q) ∨ r |
1 | 0 | 0 | 0 | (¬p) ∨ q ∨ r |
si bien que
Définition 4.2.7 La formule logique ∧
σΣDσ ainsi obtenue s’appelle la forme normale
conjonctive de la formule logique F.
Remarque Toutes les disjonctions intervenant dans la forme normale conjonctive de F ont la particularité de contenir toutes les variables propositionnelles de F une et une seule fois, soit par elle mêmes, soit par leur négation.
Bien entendu les deux méthodes précédentes peuvent s’appliquer à toute fonction booléenne, ce qui montre que toute fonction booléenne est la fonction associée à une conjonction de disjonctions et aussi la fonction associée à une disjonction de conjonctions.
Une discussion s’impose alors sur l’utilité de ce que nous venons de faire. La transformation d’une formule logique en une conjonction de disjonctions (ou une disjonction de conjonctions) équivalente est une opération fondamentale dans la programmation logique (dont un exemple est le langage Prolog qui sert en particulier dans de nombreux domaines de l’intelligence artificielle) ; elle est à la base des algorithmes de raisonnement. Deux méthodes sont possibles pour obtenir une telle formule équivalente. La première est celle du paragraphe précédent ; elle utilise certaines règles mécaniques (associativité, commutativité, distributivité, lois de Morgan, tiers exclu) ; elle est d’un emploi pénible à la main, mais relativement facile à implémenter avec un outil de calcul formel rompu à ce genre de manipulations. La deuxième, celle des tables de vérité, est relativement facile à effectuer à la main dans le cas d’un petit nombre de variables ; par contre on sait qu’elle est coûteuse en temps de calcul puisque l’établissement d’une table de vérité pour une formule logique à n variables demande un temps proportionnel à 2n.
Il s’agit ici, sans rentrer dans les détails techniques, de décrire l’implémentation physique
possible de l’évaluation d’une formule logique. Donnons nous une formule logique F dépendant
des variables propositionnelles p1,…,pn. Nous allons chercher à construire un circuit
électronique disposant de n entrées P1,…,Pn et d’une sortie Q. Chacune de ces
entrées Pi peut être portée soit à la tension 0 Volts, soit à la tension + 5 Volts (les
chiffres réels n’ont pas d’importance) suivant que la valeur attribuée à la variable pi
vaut 0 ou 1. A chaque application σ = {p1,…,pn}→{0,1} correspond donc une
distribution de tensions sur les entrées P1,…,Pn du circuit. On cherche à faire en sorte
que la tension sur la sortie Q soit alors 0 Volts si V al(F,σ) = 0 et de 5 Volts si
V al(F,σ) = 1.
Il est clair que si un circuit logique effectue l’évaluation d’une formule logique F, il effectue aussi l’évaluation de toute formule logique équivalente à F.
Nous supposerons par la suite que nous disposons d’un certain nombre de circuits élémentaires que nous pourrons assembler en reliant leurs entrées soit à une des entrée Pi soit à la sortie d’un autre circuit élémentaire. Ces circuits élémentaires sont appelés des portes logiques.
Un assemblage de portes logiques réalisant l’évaluation d’une formule logique particulière pourra ensuite être considérée comme un nouveau circuit élémentaire susceptible de réutilisation en tant que porte logique.
Nous allons décrire un système d’assemblage de portes logiques utilisant deux portes élémentaires4 : une porte ”non” et une porte ”ou” ; ces deux portes logiques sont facilement réalisables par un assemblage d’un ou deux transistors.
La porte ”non” est une porte logique à une entrée P et une sortie Q : Q est à la tension 5V si et seulement si P est à le tension 0V. La porte ”non” réalise donc l’évaluation de la formule logique q = ¬p. Nous la symboliserons sous la forme
Figure: circuit01 ou même sous forme simplifiée par un simple cercle Figure: circuit01b, ce simple cercle pouvant être éventuellement accolé à un autre symbole en entrée ou en sortie.
La porte ”et” est une porte logique à deux entrées P1 et P2 et une sortie Q. La sortie Q est à le tension 5V si et seulement si chacune des deux entrées est à la tension 5V. La porte ”et” réalise donc l’évaluation de la formule logique q = p1 ∧ p2. Nous la symboliserons sous la forme
Figure: circuit02
On peut alors réaliser un circuit logique qui effectue l’évaluation de la formule logique q = p1 ∨p2. Il suffit d’utiliser la loi de Morgan qui nous dit que p1 ∨p2 ≡¬((¬p1) ∧ (¬p2)) ce qui nous donne un circuit logique
Figure: circuit03
Etant donné l’utilité de ce circuit logique, nous en ferons une nouvelle porte logique, que nous appellerons porte ”ou” et que nous symboliserons sous la forme
Figure: circuit04 (ou encore avec le symbole Figure: circuit04b)
On peut alors assembler ces trois portes logiques pour évaluer les autres opérateurs logiques élémentaires. En ce qui concerne l’opérateur xor que nous avons noté ⊗, on peut utiliser p1 ⊗ p2 ≡ ((¬p1) ∧ p2) ∨ (p1 ∧ (¬p2)) d’où le circuit logique
Figure: circuit05
Remarque Par convention, dans un circuit logique, lorsque deux fils se croisent, ils sont considérés comme passant sur deux niveaux différents et donc être isolés l’un de l’autre. Lorsque l’on veut connecter deux fils, on doit expliciter cette connexion par un rond noir qui la symbolise. Dans la réalisation pratique de circuit logique, ces croisements de fils sur plusieurs niveaux sont difficilement réalisables et la conception de circuits intégrés comportant des centaines de milliers ou des millions de portes logiques interconnectées pose de redoutables problèmes de géométrie combinatoire dans lesquels la théorie des graphes joue un rôle essentiel.
Pour ce qui est de l’opérateur d’implication, on peut utiliser p1 ⇒ p2 ≡ p2 ∨ (¬p1) ce qui donne le circuit
Figure: circuit06
Quant à l’opérateur d’équivalence, on peut remarquer que p1 ⇔ p2 ≡¬(p1 ⊗ p2) ce qui nous fournit le circuit
Figure: circuit07
ou encore que p1 ⇔ p2 ≡ (p1 ⇒ p2) ∧ (p2 ⇒ p1) ce qui nous donne le circuit
Figure: circuit07b
Reprenons le dernier circuit logique que nous avons construits, où nous avons écrit que
La représentation arborescente de cette dernière formule est
Figure: circuit08a
Effectuons une rotation de cette représentation arborescente. Nous obtenons alors un arbre ”couché”
Figure: circuit08b
que nous pouvons comparer avec le circuit logique qui évalue la formule
Figure: circuit07b
Nous constatons que la structure du circuit logique et la structure de l’arbre sont tout à fait identiques :
Ceci se généralise de manière évidente à toute formule logique ne faisant intervenir que les opérateurs ∧,∨ et ¬ ; à partir de la représentation arborescente de la formule logique, on peut construire un circuit logique évaluant la formule en remplaçant tous les noeuds de l’arbre par les portes logiques correspondantes, en reliant les feuilles de l’arbre aux entrées du circuit portant la même étiquette et en reliant la racine de l’arbre à la sortie du circuit.
Pour les formules logiques faisant intervenir les opérateurs ⊗,⇒ et ⇔, on remplace les noeuds correspondant par les circuits logiques construits dans le paragraphe précédent, considérés comme de nouvelles portes logiques.
Nous allons maintenant progresser dans la compréhension du microprocesseur en étudiant comment des combinaisons de portes logiques peuvent servir à concevoir des circuits logiques réalisant des opérations arithmétiques élémentaires comme l’addition de deux nombres entiers. Prenons deux nombres écrits en base 2 avec p chiffres, m = xp…x0 et n = yp…y0, chacun des xi et yi étant égal soit à 0 soit à 1. On peut alors effectuer l’addition de ces deux nombres suivant le même algorithme qu’en base 10. On additionne les chiffres de droite à gauche en base 2 en tenant compte des retenues éventuelles. Autrement dit on effectue l’algorithme suivant (où ci désigne la retenue)
L’écriture en base 2 de m + n est alors cp+1zp…z0.
Remarque Dans la pratique des ordinateurs, p + 1 est fixe égal à 8, 16, 32 ou même 64 suivant les processeurs. En règle générale, le résultat retourné par une addition est non pas cp+1zp…z0 mais simplement zp…z0. La dernière retenue cp+1 est donc négligée dans le résultat final. Elle sert cependant à positionner un drapeau qui signalera un débordement éventuel dans l’addition, autrement dit que le résultat ne tient pas vraiment sur p + 1 bits.
Nous allons tout d’abord construire un circuit logique qui étant donné deux entrées x, y calcule z et une retenue c. Un tel circuit est appelé demi-additionneur parce qu’il ne tient pas compte d’une retenue précédente qu’il faut ajouter ensuite au résultat obtenu : ceci nécessitera un deuxième demi-additionneur pour confectionner un additionneur complet. Pour cela nous allons simplement calculer une table de vérité à deux entrées et deux sorties.
x | y | c | z |
1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 |
Nous constatons immédiatement que z = f⊗(x,y) et que c = f∧(x,y). Ceci nous permet de construire notre circuit demi-additionneur.
Figure: addit1
Nous symboliserons par la suite un tel circuit demi-additionneur sous la forme
Figure: addit2
Construisons alors un circuit additionneur complet qui prend trois entrées x, y et c (la retenue précédente) et qui retourne un chiffre z et une nouvelle retenue c′.
Pour cela on commence par additionner x et y obtenant un chiffre z1 et une retenue c1. Il faut ensuite que nous additionnions z1 et c pour obtenir un chiffre qui n’est autre que z et une retenue c2. Mais remarquons que si c1 = 1, alors nécessairement z1 = 0 (voir la table de vérité ci dessus) et donc nécessairement c2 = 0, et alors c′ = c1. Si par contre c1 = 0, alors c′ = c2. Autrement dit, on a toujours c′ = f∨(c1,c2). On peut aussi constater de visu le résultat sur la table de vérité à trois entrées
x | y | c | z1 | c1 | z | c2 | c′ |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Ceci nous conduit à un circuit additionneur, complet de la forme
Figure: addit3
Nous symboliserons un tel circuit additionneur sous la forme
Figure: addit4
Par assemblage, on peut alors construire un circuit additionneur p bits de la manière suivante
Figure: addit5
Remarque En fait la réalisation d’un tel circuit pose de délicats problèmes de temporisation. En effet l’établissement des tensions dans les sorties n’est pas instantanée et il est essentiel qu’un additionneur ne prenne en compte la retenue provenant de l’additionneur de gauche qu’après qu’elle ait été clairement établie. Le cadencement est donc une étape importante de la conception des circuits intégrés, d’où le rôle des quartz qui jouent le rôle de chefs d’orchestre de tous les circuits logiques.