Boris ENG

PhD Student in Computer Science, Team LoVe, LIPN (Université Sorbonne Paris Nord, France) [last name][first name]@hotmail.fr
« Return to Teaching

Logique

Responsable du cours : Christophe Fouquéré

Chargé de TP (GR6) : Moi (eng@lipn.fr)

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)


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.

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