Chapitre 4
Notions de logique

4.1 Eléments du calcul propositionnel

4.1.1 Introduction à la logique

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.

4.1.2 Les 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 

4.1.3 Propositions composées

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.

4.1.4 Syntaxe des formules logiques

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

p,q,r,p1,...,q1,...,r1,...,¬,∧,∨,⊗,⇒,  ⇐⇒  , ( , )

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 

4.1.5 Représentation arborescente d’une formule logique

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

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.

4.1.6 Sémantique : évaluation des formules logiques

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).

{            {                               {
 f¬(0) = 1 ,  f∧(1,1) = 1                 ,    f∨(0,0) = 1
 f¬(1) = 0    f∧(1,0) = f∧(0,1) = f∧(0,0) = 0  f∨(1,0) = f∨(0,1) = f∨ (1,1) = 1
{f⊗ (1,1) = f⊗ (0,0) = 0  {f⇒ (1,0) = 0
 f⊗ (1,0) = f⊗ (0,1) = 1 , f⇒ (1,1) = f⇒(0,1) = f⇒(0,0) = 1
{
 f⇔ (1,1) = f⇔(0,0) = 1
 f⇔ (1,0) = f⇔(0,1) = 0

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(pq,σ) = 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) :

4.1.7 Tables de vérité

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


  



pqp q



11 1
10 0
01 0
00 0



  



pqp q



11 1
10 1
01 1
00 0



  



pqp q



11 0
10 1
01 1
00 0








pqp q



11 1
10 0
01 1
00 1



  



pqp q



11 1
10 0
01 0
00 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

(((¬p)∨ q)∧r) ⇐ ⇒  (p ⊗ r)

de la manière suivante









pqr¬p(¬p) q((¬p) q) rp r(((¬p) q) r) ⇐⇒ (p r)








111 0 1 1 0 0
110 0 1 0 1 0
101 0 0 0 0 1
100 0 0 0 1 0
011 1 1 1 1 1
010 1 1 0 0 1
001 1 1 1 1 1
000 1 1 0 0 1








4.1.8 Tautologies, satisfiabilité

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







pqp q¬p(¬p) q(p q) ⇐⇒ ((¬p) q)






11 1 0 1 1
10 0 0 0 1
01 1 1 1 1
00 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).

4.2 Fonctions booléennes

4.2.1 Fonctions booléennes

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) ⇐⇒ (pr), on a la table de vérité









pqr¬p(¬p) q((¬p) q) rp r(((¬p) q) r) ⇐⇒ (p r)








111 0 1 1 0 0
110 0 1 0 1 0
101 0 0 0 0 1
100 0 0 0 1 0
011 1 1 1 1 1
010 1 1 0 0 1
001 1 1 1 1 1
000 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 fF0.

4.2.2 Equivalence des formules logiques

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

  1. F1 F2
  2. fF1 = fF2
  3. (F1 F2) est une tautologie

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 F1et F2les formules logiques obtenues en remplaçant dans F1 et F2 les variables p1,,pn par G1,,Gn. Alors F1et F2sont 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 F1et F2sont é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

4.2.3 Equivalences fondamentales

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









p1p2p3p1 p2(p1 p2) p3p1 p3p2 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

F1 ⇒ F2 ≡ (¬F1) ∨F2 ≡ (¬(¬F2))∨ (¬F1 ) ≡ (¬F2) ⇒ (¬F1 )

Proposition 4.2.6 Soit F1 et F2 deux formules logiques. Alors F1 F2 (F1 (¬F2)) ((¬F1) F2)

Démonstration: Idem

4.2.4 Formes normales des formules logiques

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′′ = D1Dq 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 = ¬F1F1 est équivalente à une disjonction de conjonctions, on a F1 C1 Cp et alors, d’après la loi de Morgan, F = ¬F1 (¬C1)(¬Cp) D1Dp si ¬Ci DiDi 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 F2F1 et F2 sont équivalentes à des disjonctions de conjonctions, on a F1 C1 Cp et F2 C1′∨ Cqd’où F1 F2 C1 Cp C1′∨ Cqqui est encore une disjonction de conjonctions. Si F = F1F2F1 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

F  ∨ F ≡ (D  ∧ ...∧ D )∨ (D ′∧...∧ D′) = ∧ (D  ∨ D′)
  1   2     1       p      1       q    i,j  i   j

où chacune des Di Djest de façon évidente une disjonction.

On montre de même que si F = F1 F2F1 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 = F1F2, 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

F  ≡ (¬(((¬p)∨ q)∧r))∨ (p ⊗r)≡ (¬((¬p )∨q)∨ (¬r))∨ ((p∧ (¬r))∨ ((¬p)∧ r)
                 ≡ (p∧(¬q))∨(¬r)∨ (p ∧(¬r))∨((¬p)∧r)
qui est une disjonction de conjonctions.

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

F  ≡  ((p∧ (¬q))∨ (¬r)∨(p∧ (¬r)))∨ (((¬p)∧ r)                             )
   ≡    (p ∨(¬r))∧((¬q)∨(¬r)) ∨  (p∨(¬p)∧ (p∨r)∧ ((¬r)∨ (¬p))∧ ((¬r)∨ r)
      (                    )   (                       )
   ≡    (p ∨(¬r))∧((¬q)∨(¬r)) ∨  1∧ (p ∨r)∧ ((¬r)∨ (¬p ))∧ 1

      (                    )   (                 )
   ≡    (p ∨(¬r))∧((¬q)∨(¬r)) ∨  (p∨r)∧ ((¬r)∨ (¬p))
      (             )  (                 )
   ≡    p∨ (¬r)∨ p∨ r ∧  p∨ (¬r)∨(¬r)∨ (¬p)
        (              )   (                   )
      ∧  (¬q)∨(¬r)∨ p∨r  ∧  (¬q )∨(¬r)∨(¬r)∨ (¬p)
      (    )   (      )  (          )  (              )
   ≡    p∨ 1 ∧  1∨ (¬r ) ∧  p∨ (¬q)∨ 1  ∧ (¬p)∨ (¬q) ∨(¬r)

   ≡  1 ∧1 ∧1∧ (¬p)∨(¬q)∨ (¬r) ≡(¬p)∨ (¬q) ∨(¬r)
qui est une conjonction d’une seule disjonction.

4.2.5 Utilisation de tables de vérité

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σ) = {
  1si σ = τ
  0si σ ⁄= τ.

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) = {1si σ(pi) = 1
 0si σ(pi) = 0 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é









pqr¬p(¬p) q((¬p) q) rp r(((¬p) q) r) ⇐⇒ (p r)








111 0 1 1 0 0
110 0 1 0 1 0
101 0 0 0 0 1
100 0 0 0 1 0
011 1 1 1 1 1
010 1 1 0 0 1
001 1 1 1 1 1
000 1 1 0 0 1








Si l’on ne garde que les lignes donnant la valeur 1 on obtient une table réduite






pqr(((¬p) q) r) ⇐⇒ (p r)conjonction correspondante





101 1 p (¬q) r
011 1 (¬p) q r
010 1 (¬p) q (¬r)
001 1 (¬p) (¬q) r
000 1 (¬p) (¬q) (¬r)





d’où

   (         )  (        )  (           ) (           )  (              )
F ≡  p∧(¬q)∧r ∨  (¬p)∧q ∧r ∨  (¬p)∧q∧(¬r) ∨  (¬p)∧ (¬q)∧r  ∨ (¬p)∧(¬q)∧(¬r)

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é









pqr¬p(¬p) q((¬p) q) rp r(((¬p) q) r) ⇐⇒ (p r)








111 0 1 1 0 0
110 0 1 0 1 0
101 0 0 0 0 1
100 0 0 0 1 0
011 1 1 1 1 1
010 1 1 0 0 1
001 1 1 1 1 1
000 1 1 0 0 1








Si l’on ne garde que les lignes donnant la valeur 0 on obtient une table réduite






pqr(((¬p) q) r) ⇐⇒ (p r)disjonction correspondante





111 0 (¬p) (¬q) (¬r)
110 0 (¬p) (¬q) r
100 0 (¬p) q r





si bien que

    (              )   (            )  (         )
F ≡  (¬p)∨ (¬q)∨ (¬r) ∧  (¬p)∨(¬q)∨ r ∧  (¬p)∨q ∨r

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.

4.3 Circuits logiques élémentaires

4.3.1 Notion de circuit logique

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 C 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.

4.3.2 Portes logiques et circuits élémentaires

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

4.3.3 Circuits logiques et représentations arborescentes

Reprenons le dernier circuit logique que nous avons construits, où nous avons écrit que

p1 ⇔ p2 ≡ (p1 ⇒ p2)∧ (p2 ⇒ p1) ≡ (p2 ∨ (¬p1))∧((¬p2)∨ p1)

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.

4.3.4 Additionneurs

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 = xpx0 et n = ypy0, 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+1zpz0.

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+1zpz0 mais simplement zpz0. 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.





xycz




1110
1001
0101
0000




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









xycz1c1zc2c








111 0 1 1 0 1
110 0 1 0 0 1
101 1 0 0 1 1
100 1 0 1 0 0
011 1 0 0 1 1
010 1 0 1 0 0
001 0 0 1 0 0
000 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.