Logique

Responsable du cours : Christophe Fouquéré

Taille des arbres binaires complets de hauteur n (TD1 Exercice 1, pas important)

Supposons que l’on a un arbre binaire complet (seulement des sommets à deux branches) de hauteur n. C’est-à-dire que la plus longue branche entre une feuille et la racine de l’arbre comporte $n$ arêtes.

Le nombre de sommet est $1+2^1+2^3+…+2^{n+1}$ car chaque niveau de hauteur représente une couche de sommets et le nombre de sommet double à chaque couche. On veut donc $n+1$ couches (rappelons que la hauteur dépend du nombre d’arêtes mais qu’il y a $n+1$ sommets sur cette branche). On a en fait :

$1+2^1+2^3+…+2^{n+1} = \sum_{i=0}^{n+1} 2^i = \frac{2^{n+1}-1}{2-1} = 2^{n+1}-1$. C’est dû au fait qu’on a $\sum_{i=0}^n r^i = \frac{r^n-1}{r-1}$. Prouvons-le :

On part de cette égalité : $\sum_{i=0}^n r^i = r^0+r^1+r^2+…+r^n$

On multiple par r des deux côtés : $r\sum_{i=0}^n r^i = r^1+r^2+r^3+…+r^{n+1}$

On soustrait la seconde expression par la première : $r\sum_{i=0}^n r^i-\sum_{i=0}^n r^i = (r^1+r^2+r^3+…+r^{n+1}) - (r^0+r^1+r^2+…+r^n)$

On simplifie et factorise à gauche : $\sum_{i=0}^n r^i (r-1) = r^{n+1}-1$

Ce qui nous donne finalement : $\sum_{i=0}^n r^i (r-1) = r^{n+1}-1$ et $\sum_{i=0}^n r^i = \frac{r^{n+1}-1}{r-1}$.

Définition inductive de hauteur et longueur d’une formule (utile)

On peut définir la hauteur et la longueur d’une formule par récurrence sur la structure des formules :

$l(A) = 1 \qquad\qquad l(\lnot G) = 1+l(G) \qquad\qquad l(G \ast H) = 1+l(G)+l(H)$

$h(A) = 0 \qquad\qquad h(\lnot G) = 1+h(G) \qquad\qquad h(G \ast H) = 1+max(h(G), h(H))$

Preuve par récurrence sur les formules (TD1 Exercice 2 et 3, important)

• Montrons que pour toute formule $F \in \mathcal{F}$, le nombre de parenthèses (noté $np(F)$) est pair. On raisonne par induction sur la taille/structure de la formule $F$ :
  • Cas $F = A$ (un atome). On a $np(A) = 0$ qui est pair.
  • Cas $F = \lnot G$. Par hypothèse de récurrence, on a $nb(G)$ pair. Montrons qu’on a $nb(\lnot G)$ pair. Comme la négation n’introduit par de parenthèses, on a $nb(\lnot G) = nb(G)$ donc $nb(\lnot G)$ est pair.
  • Cas $F = (G \ast H)$ pour un connecteur binaire $\ast \in \{\lor, \land, \Rightarrow, \Leftrightarrow\}$. Par hypothèse de récurrence, $np(G)$ et $np(H)$ sont pairs donc on peut les écrire sous la forme $np(G) = 2k$ et $np(H) = 2l$. On a $np((G \ast H)) = 2k+2l+2 = 2(k+l+1)$ qui est pair car on a un facteur 2.

• Montrons que pour toute formule $F \in \mathcal{F}$, on a $h(F) \leq l(F)$ c’est-à-dire que la hauteur d’une formule est toujours inférieur ou égal à sa longueur. On raisonne par induction sur la taille/structure de la formule $F$ :
  • Cas $F = A$ (une variable). On a $h(A) = 0$ qui est bien inférieur ou égal à $l(A) = 1$.
  • Cas $F = \lnot G$. Par hypothèse de récurrence, on suppose $h(G) \leq l(G)$. On a $h(\lnot G) = 1+h(G)$ qui est bien inférieur ou égal à $l(\lnot G) = 1+l(G)$ par hypothèse de récurrence et le fait que $x \leq y$ implique $1+x \leq 1+y$.
  • Cas $F = (G \ast H)$ pour un connecteur binaire $\ast \in \{\lor, \land, \Rightarrow, \Leftrightarrow\}$. Par hypothèse de récurrence, $h(G) \leq l(G)$ et $h(H) \leq l(H)$. On veut montrer $h((G \ast H)) \leq l((G \ast H))$. Il s’agit d’ajouter un connecteur à deux formules. Quand on fait cela, on ajoute une arête entre la racine et une feuille de l’arbre correspondant à la formule et la hauteur dépend du maximum entre la hauteur des deux-sous formules. On en conclut que $h((G \ast H)) = 1+max(h(G), h(H))$. Ensuite, on a $l((G \ast H)) = 1+l(G)+l(H)$ (car les symboles de $(G \ast H)$ sont ceux de $G$, ceux de $H$ et le connecteur binaire que l’on rajoute). Ce que l’on doit montrer revient à montrer $max(h(G), h(H)) \leq l(G)+l(H)$ (on ignore les +1 pour simplifier). On raisonne cas par cas (car il y a deux possibilités) :
    • Supposons que $max(h(G), h(H)) = h(G)$. On sait que $h(G) \leq l(G)$, donc on a nécéssairement $h(G) \leq l(G)+l(H)$. C’est ce qu’on voulait montrer.
    • Même chose pour l’autre cas où l’on a $max(h(G), h(H)) = h(H)$.

Calcul efficace de la hauteur (TD3 Exercice 1, utile)

On remarque que lorsque des parenthèses ouvrantes s’enchaînent, la hauteur d’une formule s’accumule. On aimerait le prouver par récurrence. Montrons que pour toute formule $F$, on a $h(F) = maxp(F)$ où $maxp(F)$ est la plus grande chaîne de parenthèses ouvrantes dans $F$. On pense à mettre toutes les parenthèses autour des connecteurs et on raisonne par récurrence.

• Cas $F = A$ (une variable). On a $h(A) = 0 = maxp(A)$ (il n’y a pas de parenthèse).
• Cas $F = (\lnot G)$. Par hypothèse de récurrence, $h(G) = maxp(G)$. On a $h((\lnot G)) = h(G)+1$ et $maxp((\lnot G)) = maxp(G)+1$ (car on a ajouté une parenthèse ouvrante). Les deux sont donc égaux en utilisant l’hypothèse de récurrence.
• Cas $F = (G \ast H)$ pour un connecteur binaire $\ast \in \{\lor, \land, \Rightarrow, \Leftrightarrow\}$. Par hypothèse de récurrence, on a $h(G) = maxp(G)$ et $h(H) = maxp(H)$. En calculant la hauteur de $F$, on obtient $h((G \ast H)) = 1+max(h(G), h(H))$. Si on veut calculer la plus longue chaîne de parenthèses ouvrantes, cela dépend qui a la plus longue chaîne entre $G$ et $H$ puis on ajoute une parenthèse ouvrante. On a donc $maxp((G \ast H)) = 1+max(maxp(G), maxp(H))$ ce qui coïncide avec la hauteur. Donc on a bien $h(F) = maxp(F)$.

Analyse sémantique (TD3 Exercice 4.3, utile)

On a la formule $J = p \Rightarrow ((p \land q) \lor (p \land \lnot q))$. L’analyse sémantique consiste à prouver des choses en utilisant des équivalences logiques (par exemple lois de De Morgan) ou des équivalences par substitutions. On peut par exemple, par transformations, ramener la formule à une tautologie connue.

$p \Rightarrow ((p \land q) \lor (p \land \lnot q))$

$\equiv p \Rightarrow (p \land (q \lor \lnot q))$ (par factorisation)

$\equiv p \Rightarrow p$ (car le tiers exclu est toujours vrai et donc la vérité de la conjonction dépend seulement de $p$)

La formule qu’on obtient est une tautologie connue (toute formule implique elle-même). On remarque aussi que le “ou” et le “et” ont les mêmes propriétés que l’addition et la multiplication ($1$ est un élément absorbant pour $\land$).