TP Python – Vérifier une équivalence par énumération

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S08

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Toutes les combinaisons de valeurs

Écris combinaisons(n) qui renvoie la liste des \(2^n\) combinaisons de n booléens, sous forme de tuples, dans l'ordre de la table de vérité (False avant True, la première variable change le moins vite). Indice : le numéro de ligne k, écrit en binaire sur n bits (S01), donne les valeurs.

J'anticipe. Que doit renvoyer combinaisons(2) ? Quelle ligne de la table correspond à k = 2 ?

###

assert combinaisons(1) == [(False,), (True,)]bksl-nlassert combinaisons(2) == [(False, False), (False, True), (True, False), (True, True)]bksl-nlassert combinaisons(3)[5] == (True, False, True)bksl-nlassert len(combinaisons(4)) == 16bksl-nlassert combinaisons(0) == [()]bksl-nlbksl-nl ∞/∞

def combinaisons(n):bksl-nl """Liste des 2py-strpy-strn tuples de n booléens, dans l'ordre de la table de vérité."""bksl-nl liste = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl ligne = []bksl-nl for i in range(n):bksl-nl # À compléter : le bit de rang (n - 1 - i) de k, converti en booléenbksl-nl ligne.append(False)bksl-nl liste.append(tuple(ligne))bksl-nl return listebksl-nlbksl-nl

Exercice B – Équivalence par énumération

À l'aide de combinaisons, écris equivalentes(f, g, n) qui renvoie True si les fonctions f et g (à n arguments booléens) donnent le même résultat sur toutes les combinaisons.

###

assert equivalentes(lambda p, q: not (p and q), lambda p, q: (not p) or (not q), 2) is Truebksl-nlassert equivalentes(lambda p, q: not (p or q), lambda p, q: (not p) and (not q), 2) is Truebksl-nlassert equivalentes(lambda p, q: (not p) or q, lambda p, q: (not q) or p, 2) is Falsebksl-nlassert equivalentes(lambda p, q, r: p and (q or r), lambda p, q, r: (p and q) or (p and r), 3) is Truebksl-nlassert equivalentes(lambda p, q, r: p or (q and r), lambda p, q, r: (p or q) and r, 3) is Falsebksl-nlbksl-nl ∞/∞

def combinaisons(n):bksl-nl liste = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl ligne = []bksl-nl for i in range(n):bksl-nl ligne.append(bool((k >> (n - 1 - i)) & 1))bksl-nl liste.append(tuple(ligne))bksl-nl return listebksl-nlbksl-nldef equivalentes(f, g, n):bksl-nl """True si f et g donnent le même résultat sur toutes les combinaisons de n booléens."""bksl-nl ...bksl-nlbksl-nl

Je comprends. Vérifie avec equivalentes les lois de De Morgan et l'équivalence \(p \Rightarrow q \equiv \neg p \vee q\). Quelle différence avec une preuve par table sur papier ?

Exercice C – Tautologie et comptage

Écris est_tautologie(f, n) et nombre_de_vrais(f, n).

###

assert estpy-undtautologie(lambda p: p or not p, 1) is Truebksl-nlassert estpy-undtautologie(lambda p: p and not p, 1) is Falsebksl-nlassert estpy-undtautologie(lambda p, q: (not p) or q, 2) is Falsebksl-nlassert estpy-undtautologie(lambda p, q: (not (((not p) or q) and p)) or q, 2) is Truebksl-nlassert estpy-undtautologie(lambda p, q: (not (p or q)) or p, 2) is Falsebksl-nlassert nombrepy-unddepy-undvrais(lambda p, q: p or q, 2) == 3bksl-nlassert nombrepy-unddepy-undvrais(lambda p, q, r: (p and not q) or r, 3) == 5bksl-nlassert nombrepy-unddepy-undvrais(lambda p, q: p != q, 2) == 2bksl-nlbksl-nl ∞/∞

def combinaisons(n):bksl-nl liste = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl ligne = []bksl-nl for i in range(n):bksl-nl ligne.append(bool((k >> (n - 1 - i)) & 1))bksl-nl liste.append(tuple(ligne))bksl-nl return listebksl-nlbksl-nldef estpy-undtautologie(f, n):bksl-nl """True si f vaut True pour toutes les combinaisons."""bksl-nl ...bksl-nlbksl-nldef nombrepy-unddepy-undvrais(f, n):bksl-nl """Nombre de combinaisons pour lesquelles f vaut True."""bksl-nl ...bksl-nlbksl-nl

Exercice D – La règle de pare-feu

Écris autorise(protocole, port) qui applique la règle \((t \wedge (a \vee b)) \vee i\) de l'exercice 7.

###

assert autorise("TCP", 80) is Truebksl-nlassert autorise("TCP", 443) is Truebksl-nlassert autorise("TCP", 22) is Falsebksl-nlassert autorise("ICMP", 0) is Truebksl-nlassert autorise("UDP", 53) is Falsebksl-nlassert autorise("UDP", 443) is Falsebksl-nlbksl-nl ∞/∞

def autorise(protocole, port):bksl-nl """Règle : (TCP et port 80 ou 443) ou ICMP."""bksl-nl ...bksl-nlbksl-nl

Exercice E – Table de vérité affichée

Écris afficher_table(f, n) qui affiche une ligne par combinaison, avec V ou F (essaie avec lambda p, q: p and q).

###

def combinaisons(n):bksl-nl liste = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl ligne = []bksl-nl for i in range(n):bksl-nl ligne.append(bool((k >> (n - 1 - i)) & 1))bksl-nl liste.append(tuple(ligne))bksl-nl return listebksl-nlbksl-nldef afficherpy-undtable(f, n):bksl-nl """Affiche une ligne par combinaison : les valeurs puis le résultat, en V / F."""bksl-nl for valeurs in combinaisons(n):bksl-nl ...bksl-nlbksl-nlafficherpy-undtable(lambda p, q: p and q, 2)bksl-nlbksl-nl