3730.sagews

Exercice 1 : Écrire une fonction "Implique(a,b)" qui vaut True si a=>b, False sinon.

def Implique(a,b): return (not a or b)

Exercice 2 : On représente une formule logique à deux inconnues par une fonction à deux arguments ({Vrai, Faux}² -> {Vrai, Faux}). Écrire une fonction qui prend en entrée deux telles formules et qui teste si elles sont équivalentes.

 

def Equiv(f,g):
    for a in [True, False]:
        for b in [True, False]:
            if f(a,b)!=g(a,b): return False
    return True

Exercice 3 : Construire une fonction, qui prend en entrée une formule logique et qui imprime sa table de vérité (de taille 4).

def TableVerite(f):
    print '  a   |    b   |   f(a,b) '
    for a in [True, False]:
        for b in [True, False]:
            print a,' | ',b,' | ',f(a,b)
            
TableVerite(Implique)

a | b | f(a,b) True | True | True True | False | False False | True | True False | False | True

Exercice 4 (*) : Même question, mais l'entrée est un entier n et une fonction à n arguments. Pour ce faire, sachez que * transforme une liste en arguments pour une fonction : par exemple, si args = [1,2,3], alors f(*args) = f(1,2,3).

def TableVeriten(n,f):
    args = [False]*n
    print args, f(*args)
    for i in range(2**n-1): 
        k=0
        while args[k]:
            args[k] = False
            k+=1
        args[k] = True
        print args, f(*args)

def and_imply(a,b,c): return Implique(a and b, c)

TableVeriten(3,and_imply)

[False, False, False] True [True, False, False] True [False, True, False] True [True, True, False] False [False, False, True] True [True, False, True] True [False, True, True] True [True, True, True] True

Exercice 5 (**) : On prend en entrée une chaîne de caractères de la forme "(p ou q) => r", bien parenthésée (où on admet que non, ou, et, =>, <=> sont des mots-clés, et les autres lettres des propositions). On veut obtenir une table de vérité complète. Bon courage !

Deuxième partie : ensembles.

On va essayer de modéliser des ensembles avec des structures de données qui ne sont pas forcément faites pour ça, à savoir des listes (d'entiers). Dans la suite, quand on parlera d'ensemble, on voudra dire liste sans prendre en compte les répétitions ou l'ordre des entrées. Dans la vraie vie, Sage utilise aussi les listes pour modéliser des ensembles vie l'opération "set".

Exercice 5 : Écrivez une fonction qui prend en entrée un ensemble E et un prédicat p (c'est-à-dire ici une fonction N -> {True, False}), et qui vérifie si on a "Pour tout x dans E, p(x)". Renvoyez juste True ou False.

def PourTout(E,p):
    for x in E:
        if not p(x): return False
    return True

Exercice 6 : Écrivez une fonction qui prend en entrée deux ensembles et qui écrit leur produit cartésien. Un couple est bien défini en Python et s'écrit simplement (a,b).

def ProduitCartesien(E,F):
    ExF=[]
    for x in E:
        for y in F:
            ExF.append((x,y))
    return ExF

Exercice 7 : Écrivez une fonction qui prend en entrée deux ensembles et qui teste s'ils sont égaux, sans les modifier.

def Egaux(E,F):
    for x in E:
        if not (x in F): return False
    for y in F:
        if not (y in E): return False
    return True

Exercice 8 : Écrivez une fonction qui, étant donné en entrée deux ensembles A et B et une fonction f, vérifie qu'on a bien f(A) inclus dans B, et indique si f est injective, surjective ou bijective.

def fdeAdansB(A,B,f):
    for x in A:
        if not (f(x) in B): return false
    return True
    
def InjSurjBij(A,B,f):
    Inj = True
    Surj = True
    for y in B:
        nbAntecedents = 0
        for x in A:
            if f(x) == y: 
                nbAntecedents = nbAntecedents+1
        if nbAntecedents == 0: Surj = 0
        elif nbAntecedents >1: Inj = 1
    if (not fdeAdansB(A,B,f)): print 'On a un problème de définition'
    elif Inj and Surj: print 'La fonction est surjective !'
    elif Inj: print 'La fonction est injective !'
    elif Surj: print 'La fonction est surjective !'
    else: print 'C est une fonction, c est déjà ça.'

Exercice 9 : Écrivez un fonction qui "nettoie" un ensemble, c'est-à-dire qui supprime les doublons. Vous pouvez utiliser une fonction appartient(E,x,i) qui teste si l'élément x fait partie des i premiers éléments de E. Si vous êtes perfectionniste, il existe une fonction qui trie les listes (trouvez-la).

def appartient(E,x,i):
        for k in range(i):
            if E[k]==x: return True
        return False

def Nettoie(E):
    resultat = []
    for i in range(len(E)):
        if (not appartient(E,E[i],i)): resultat.append(E[i])  
    return resultat

On va représenter une relation comme une fonction qui prend en entrée deux entiers et renvoie True ou False.

Exercice 10 : Écrivez une fonction qui prend en entrée un ensemble et une relation et qui teste si elle est réflexive, symétrique et/ou transitive.

def Relation(E,r):
    Refl, Sym, Trans = True, True, True
    for x in E:
        if not r(x,x): Refl = False
    for x in E:
        for y in E:
            if r(x,y) and not r(y,x): Sym = False
    for x in E:
        for y in E:
            for z in E:
                if r(x,y) and r(y,z) and not r(x,z): Trans = False
    return (Refl, Sym, Trans)

def r(a,b): return False
E = [1,2,3,4]
Relation(E,r)

(False, True, True)

Puis, étant donné un ensemble et une relation d'équivalence, passez l'ensemble au quotient.

def Quotient(E,r):
    quotient = []
    for x in E:
        NouvelleClasse = True
        for y in quotient:
            if r(x,y[0]): 
                y.append(x)
                NouvelleClasse = False
        if NouvelleClasse: quotient.append([x])
    return quotient

def r(a,b): return (a-b)%2 == 0
E = [1,2,3,4]
Quotient(E,r)

[[1, 3], [2, 4]]

Exercice 11 (*) : Écrivez une fonction qui, prenant en entrée quatre ensembles A, B, A', B' et deux fonctions f : A -> A' et g : B -> B', renvoie la fonction produit (x,y) -> (x', y'). Attention : cette fonction ne prend qu'un seul argument, et cet argument est un couple.

def Produit(f,g):
    def h(x):
        a,b = x
        return (f(a),g(b))
    return h

Exercice 12 (*) : Construire la fonction qui à un ensemble associe l'ensemble de ses parties.

def Parties(E):
    E = Nettoie(E)
    n = len(E)
    include = [False]*n
    parties = []
    def ajoute_partie():
        p = []
        for i in range(n):
            if include[i]: p.append(E[i])
        parties.append(p)
    ajoute_partie()
    for i in range(2**n-1): 
        k=0
        while include[k]:
            include[k] = False
            k+=1
        include[k] = True
        ajoute_partie()
    return parties

Parties([1,2,3])

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Bonus comique pour la fin : vous vous rappelez que je vous ai expliqué que Vrai pouvait s'écrire 1 et que Faux pouvait s'écrire 0 ?

False == 0

True

True + 2

3