Logique et algèbre

Logique et algèbre

Damien Nouvel

Damien Nouvel (Inalco) Algèbre 1 / 32

Théorie des ensembles

Plan

1. Théorie des ensembles

2. Dénombrement

3. Applications



De l’algèbre aux ensembles

§ Quelques dates en l’algèbre‚ Mot de l’arabe al-jabr (par Al-Khwarizmi)ñ Construction à partir d’éléments‚ „ 1000 : utilisation des chiffres arabes‚ „ 1500 : apparition des symboles +, ´, =ñ Chiffres et équations

§ Vers la théorie des ensembles‚ Fin du XIXème siècleñ G. Cantor : “nous appelons ensemble tout réunion M

d’objets de notre conception, déterminés et bien distincts,que nous dénommerons éléments de M”

ñ Notion d’élément et d’appartenance x P Eñ Liens entre la logique et l’algèbre ?



Ensembles, individus et catégories

§ Relations ensemblistes‚ Relation partie-tout : méronymie / holonomie

‚ La roue est partie d’une voiture‚ La tête est une partie du corps‚ …

ñ Relation entre individus‚ Relation hiérarchique : subsomption

‚ La voiture est un véhicule‚ Le singe est un animal‚ …

ñ Relation entre catégories§ Pour les ensembles

‚ Regroupement d’individus dans des catégories‚ Une catégorie peut-être un individu



Notations ensemblistes et principes généraux

§ Conventions et symboles‚ Majuscules : ensembles (A, E, P, Q, R …)‚ Minuscules : éléments (x, y, a, b …)‚ Accolades t et u et barre verticale | : contenu d’un ensemble‚ H : ensemble vide (inclus dans tout ensemble)ñ P = tx, yu, P = tx|Dn, x = 2nu

§ Règles générales‚ Non-ordonnés : tx, y, zu = tz, x, yu‚ Sans répétitions : tx, y, yu = tx, yu‚ Peut-être de taille infinie (dénombrable ou non)

§ Un ensemble peut être défini par‚ Extension (dénotation, liste exhaustive) : P = tx, y, zu‚ Intention ou compréhension : P = tx est pairu‚ Récurrence ou induction : P = tx = 1 ou x/3 est dans Pu



Symboles et opérateurs

§ Appartenance : x P P et x R P ” ␣(x P P)§ Inclusion : P Ď Q (si stricte : P Ă Q)§ Complémentaire : P§ Union : PYQ§ Intersection : PXQ§ Différence (ensembliste) : PzQ§ Différence symétrique : P∆Q



Ensembles et sous-ensembles

§ Les prédicats définissent des ensembles‚ Cas unaire : l’ensemble des hommes H = tx|Homme(x) = Vu‚ Cas n-aire : lien parent-enfant P = t(x, y)|Enfant(x, y) = Vu

§ L’implication donne les sous-ensembles‚ Sous-ensemble P Ď Q si @x(x P P Ñ x P Q)‚ Sous-ensemble propre P Ă Q si @x(x P P Ñ x P Q)^ P ‰ Q‚ Si P Ď Q et Q Ď P alors P = Q et @x(x P P Ø x P Q)

§ Ensembles disjoints‚ Deux ensembles P et Q sont disjoints s’ils n’ont aucun

élément en commun‚ @x␣(x P P^ x P Q) ” ␣Dx(x P P^ x P Q)‚ PXQ =H



Opérateurs : intersection et union

§ Union Y de P et Q‚ Éléments qui appartiennent soit à P ou à Q‚ PYQ = tx|x P P_ x P Quñ tx, y, zu Y tx, z, tu = tx, y, z, tuñ H n’affecte pas l’union : PYH = Pñ Associative, commutative, H neutre

§ Intersection X de P et Q‚ Éléments qui appartiennent à la fois à P et Q‚ PXQ = tx|x P P^ x P Quñ tx, y, zu X tx, z, tu = tx, zuñ S’il n’y a aucun élément commun : Hñ Associative, commutative, H absorbant

§ Union et intersection sont distributifs l’un pour l’autre :PY (QX R) = (PYQ)X (PY R)



Opérateurs : complémentaire et différence§ Complémentaire de P et P

‚ Tout élément qui n’est pas dans P‚ P = tx|␣(x P P)u = tx|x R Puñ Extension pas toujours possible à calculer‚ P = P

§ Différence de P et Q‚ Tout élément qui est dans P mais pas dans Q‚ PzQ = tx|x P P^ x R Qu = PXQñ Non-associative, non-commutative, H neutreñ Peu pratique, mais correspond à la soustraction

§ Différence symétrique de P et Q‚ Tout élément qui est dans P ou Q mais pas dans P et Q‚ P∆Q = tx|(x P P_ x P Q)^␣(x P P^ x P Q)uñ Associative, commutative, H neutreñ La différence symétrique est distributive pour l’intersection



Parties d’un ensemble

§ Sous-parties d’un ensemble‚ L’ensemble des sous-ensembles possibles‚ Pour un ensemble P, l’ensemble tQ|Q Ď Pu‚ Exemple : si P = tx, y, zu alors

Parties(P) = ttx, y, zu, tx, yu, tx, zu, ty, zu, txu, tyu, tzu,Hu§ Partition d’un ensemble

‚ Ensemble de sous-ensembles disjoints tels que leur unionreforme l’ensemble et que leurs intersections soient vides

‚ Exemple : si P = tx, y, zu alors‚ ttx, yu, tzuu‚ ttxu, tyu, tzuu‚ …

ñ Combien de sous-parties ou de partitions possibles ?



Ensembles mathématiques

§ N : nombres entiers naturels (positifs)§ Z : nombres entiers (positifs ou négatifs)§ Q : nombres rationnelsñ x P QØ Dy P Z, Dz P Zzt0u(x = y/z)§ R : nombres réels§ P : nombres premiers§ C : nombres complexesñ P Ă N Ă Z Ă Q Ă R§ Intervalles

‚ x P [a, b]Ø tx P R^ x ě a^ x ď bu‚ x P [a, b[Ø tx P R^ x ě a^ x ă bu‚ x P ]´8, b]Ø tx P R^ x ď bu



Structures ordonnées, les n-uplets

§ Importance de l’ordre des éléments‚ Coordonnées dans un plan : (1, 2) ‰ (2, 1)‚ Relation parent-enfant : (Pierre, Jean) ‰ (Jean,Pierre)‚ Attributs d’un objet dans une BDD

§ Composition d’éléments : n-uplets (triplets, quadruplets …)‚ Produit cartésien d’ensembles : PˆQñ Associatif, non-commutatif‚ Puissance : P2 = Pˆ P, Pn = Pˆ Pˆ Pˆ . . .P (n fois)‚ Exemples

ñ Coordonnée en 3D (x, y, z) P R3

ñ Âge et taille de personnes (x, y) P Nˆ Rñ Les éléments sont des composantes de l’objetñ Répétitions d’éléments : (1, 3, 1)ñ Sur un domaine D : prédicats n-aires dans Dn



Exercices : extension et intension

§ Soient A = ta, b, c, du et B = ta, d, eu, donnez l’extension de‚ AY B et AX B‚ Aˆ B et (AX B)3

‚ (Aˆ B)X (BˆA)‚ Les sous-parties possibles et deux partitions de A

§ Donnez l’extension des ensembles suivants‚ tx|x P N^ x ă 5u‚ tx|x P Z^ x2 ă 10u‚ tx|x P Q^ x ă 2^ 4 ˚ x P Nu

§ Donnez des définitions en intension des ensembles suivants‚ t´2,´1, 0, 1, 2, 3, 4u‚ t1, 3, 5, 7, 9u



Exercices : démonstrations

§ Soient A et B deux ensembles‚ Démontrez que A Ď AY B‚ Démontrez que AX B = AY B‚ Reformulez AzB par intersection et complémentaire‚ Reformulez A∆B par intersection, union et complémentaire‚ Démontrez que (AX B) ˚ C = (A ˚ C)X (B ˚ C)‚ Démontrez que (A ˚ B)X (B ˚A) = (AX B)2


Dénombrement

Plan


2. Dénombrement

3. Applications


Dénombrement

Cardinal d’un ensemble

§ Cardinal : nombre d’éléments que contient un ensemble‚ Pour un ensemble P, noté |P|‚ Nombre entier positif : |P| P N‚ Exemples

‚ |H| = 0‚ |ta, b, cu| = 3‚ |ta, a, b, c, b, cu| = 3‚ |tta, bu, tcuu| = 2

§ Quelques règles‚ Intersection : |PXQ| ď min(|P|, |Q|)‚ Union : |PYQ| = |P|+ |Q| ´ |PXQ|‚ Union : |PYQ| ď |P|+ |Q|‚ Si P et Q sont égaux : |PXQ| = |PYQ| = |P| = |Q|‚ Si P et Q sont disjoints : |PXQ| = 0 et |PYQ| = |P|+ |Q|


Dénombrement

Cardinal de n-uplet

§ Contraintes sur l’ordre et possibilité de répétitions‚ |PˆQ| = |P| ˚ |Q|‚ |Pn| = |P|n‚ Par exemple, si P = ta, bu alors

‚ P3 = t(a, a, a), (a, a, b), (a, b, a), (a, b, b),(b, a, a), (b, a, b), (b, b, a), (b, b, b)u

‚ |P3| = |P|3 = 23 = 8ñ Ordre important (b, a, a) ‰ (a, b, a) . . .


Dénombrement

Algèbre et combinatoire

§ Produit cartésien : nk (n-uplets avec remise)§ Permutations : n! (n-uplets sans remise)

‚ Premier élément parmi n‚ Second élément parmi les n´ 1 restants‚ …

§ Arrangements : Akn

‚ Sélection de k éléments ordonnés parmi nñ Ak

n = n ˚ (n´ 1) ˚ (n´ 2) ˚ . . . (n´ k + 1) =n!

(n´ k)!§ Combinaisons :

(nk)

(ouCkn)

‚ Regroupement des arrangements par ensembles‚ Une combinaison de k éléments donne k! permutations

ñ Ckn ˚ k! = Ak

n

ñ Ckn =

Akn

k! =n ˚ (n´ 1) ˚ (n´ 2) ˚ . . . (n´ k)

k ˚ (k´ 1) ˚ (k´ 2) ˚ . . . 1=

n!k! ˚ (n´ k)!


Dénombrement

Cardinalités avec/sans ordre et remise

§ Récapitulatif :

k parmi n avec ordre sans ordreavec remise nk (n + k ´ 1)!

k!(n ´ 1)!

sans remise n!(n´ k)!

n!k!(n´ k)!


Dénombrement

Cardinalités de parties d’ensembles

§ Sous-ensembles possibles par taille‚ Pour un ensemble de taille n, sous-ensembles

‚ Pour une taille k, combinaisons : |tQ Ă P^ |Q| = ku| = Ckn

‚ Pas d’intersection entre deux tailles :tQ Ă P^ |Q| = ku X tQ Ă P^ |Q| = l^ k ‰ lu =H

‚ Union des tailles : |tQ Ă Pu| =nř

k=0

|tQ Ă P^ |Q| = ku|

ñ |tQ Ă Pu| =nř

k=0

Ckn

§ Sous-ensembles possibles par présence d’éléments‚ Présence ou absence d’un élément : 2 possibilités‚ Pour un ensemble de taille n : 2n possibilités

ñ En corollaire :nř

k=0

Ckn = 2n


Dénombrement

Cardinalités de partitions d’ensembles

§ Pour un ensemble de taille n, partitions de taille k : Pkn

‚ P1n = Pn

n = 1

‚ Pn´1n =

n ˚ (n´ 1)

2‚ P2

n = 2n´1 ´ 1‚ Pour un k quelconque

‚ Par récurrence : Pkn = Pk´1

n´1 + k ˚ Pkn´1

‚ Calcul direct : Pkn =

1

k! ˚k

ř

i=1

Cki (´1)

k´iin

ñ Compliqué …


Dénombrement

Exercices : dénombrement

§ Soient P = ta, b, cu et Q = ta, du, donnez‚ |P|, |Q|, |PXQ|, |PYQ|‚ |t(x, y) P QˆQu|‚ |PˆQ|‚ |P3|

‚ |(PYQ)2|‚ |(PXQ)7|‚ |tE Ă P, |E| = 2u|‚ |tE Ă (P2 YQ2), |E| = 3u|‚ |tE Ă (PYQ)u|

§ Alphabet : en tirant 4 lettres d’un sac de 26 (sans remise)‚ Combien de combinaisons de lettres sont possibles ?‚ Combien ne contiennent que des voyelles ou des consonnes ?‚ Pour chaque possibilité, combien de mots peut-on former ?‚ Combien de mots de 4 ou 3 lettres peut-on former ?


Applications

Plan


2. Dénombrement

3. Applications


Applications

Notations

§ Application (fonction) : relation entre deux ensembles‚ Notation f : E Ñ F‚ Ensemble de départ E‚ Ensemble d’arrivée (ou image) Fñ Application est définie par le produit G Ă Eˆ F‚ Fonction mathématique : (x, y) P G ssi f(x) = yñ Sémantique portée par le nom de la fonction

§ Une seule image possible‚ @x P E,@y1 P G,@y2 P G, ((x, y1) P G^ (x, y2) P G Ñ y1 = y2)ñ Pour un élément x, on obtient qu’un seul f(x)ñ Pas de disjonction en sortie de la fonction

§ Exemples‚ f(x) = x3 : G = (0, 0), (1, 1), (2, 8), (3, 27), (4, 64) . . .‚ f(x, y) = x + 2y + 1 : G = ((0, 0), 1), ((0, 1), 3), ((1, 1), 5) . . .


Applications

Injection, surjection, bijection

§ Caractérisation de G§ Antécédent : si f(x) = y alors x P E est l’antécédent de y§ Injection

‚ Chaque élément image a au plus un antécédent‚ @x1 P E,@x2 P E,@y P F, (f(x1) = y^ f(x2) = y Ñ x1 = x2)‚ @x1 P E,@x2 P E, (f(x1) = f(x2)Ñ x1 = x2)‚ @x1 P E,@x2 P E, (x1 ‰ x2 Ñ f(x1) ‰ f(x2)‚ Contre-exemple : racine carrée sur R

§ Surjection‚ Chaque élément image a au moins un antécédent‚ @y P F, Dx P E, f(x) = y‚ Exemple : valeur absolue sur [0,+8[

ñ Bijection : application injective et surjectiveDamien Nouvel (Inalco) Algèbre 25 / 32

Applications

Exercice

§ Dites si ces fonctions sont injectives et/ou surjectives‚ RÑ R : f(x) = x + 3‚ Nzt0u Ñ]0, 1] : g(x) = 1/x‚ R2 Ñ R : f(x, y) = x + y‚ R+ ˆ t´1,+1u Ñ R : f(x, y) = x ˚ y‚ NÑ N : f(n) = n3


Applications

Morphismes

§ Groupe : ensemble et loi de composition associative‚ Loi de composition : application de Eˆ E dans E‚ Notation par opérateur (infixe), par exemple : E ‚ E‚ Associativité : @x,@y,@z, (x ‚ y) ‚ z = x ‚ (y ‚ z)‚ Exemples : (R,+), (R, ˚), mais pas (R,´), (R,˜)

§ Morphisme : lien entre les groupes de départ et d’arrivée‚ Entre les opérateurs de chaque groupes‚ Notation : f : (E, ‚)Ñ (F, ˛)‚ @x P E,@y P E, f(x ‚ y) = f(x) ˛ f(y)‚ Exemples

‚ Objets à attacher (O, att) et leur poids (R,+)‚ Chaînes à concaténer (Σ, .) et leur taille (N,+)‚ Taille de chaîne (N,+) et chaînes possibles (N, ˚)

‚ Contre-exemple : tas de grains (N,+) et hauteur (N,+)


Applications

Composition de morphismes

§ Application h : appliquer f, puis g au résultat de fñ Composition de fonctions h(x) = g(f(x))§ Notation h = g ˝ f§ Exemples

‚ Somme puis division par N‚ Compression puis taille d’un fichier‚ Résumé puis traduction d’un texte


Applications

Types de morphismes

§ Homomorphisme : morphisme§ Endomorphisme

‚ Mêmes groupes de départ et d’arrivée‚ Exemple : f(x) = |x| (valeur absolue) dans (R, ˚)‚ Possibilité de composition de morphismes f ˝ g

§ Isomorphisme (homéomorphisme, difféomorphisme)‚ Morphisme f : E Ñ F qui admet un inverse g : F Ñ Eñ Composition : f ˝ g = IdE et g ˝ f = IdFñ Pour les ensembles : applications bijectives‚ Exemple : entiers

f : (Nzt0u ˆ t+1,´1u, ˚)Ñ (Zzt0u, ˚), f(x, y) = x ˚ y§ Automorphisme : endomorphisme et isomorphisme

‚ Exemple : exponentielle f : (R, ˚)Ñ (R,+), f(x) = ex


Applications

Relations

§ Relation R binaire sur un ensemble E‚ Sous-ensemble du produit cartésien : R Ă Eˆ E‚ Propriétés possibles

‚ Réflexive : @x P E, xRx‚ Irréflexive : @x P E,␣xRx‚ Symétrique : @(x, y) P E2, (xRy Ñ yRx)‚ Anti-symétrique : @(x, y) P E2, (xRy^ yRx Ñ x = y)‚ Transitive : @(x, y, z) P E3, (xRy^ yRz Ñ xRz)‚ Circulaire : @(x, y, z) P E3, (xRy^ yRz Ñ zRx)

‚ Exemples‚ = sur N : réflexive, symétrique, anti-symétrique, transitive‚ ď sur N : réflexive, anti-symétrique, transitive‚ ă sur N : irréflexive, transitive‚ diviseur sur N : réflexive, anti-symétrique, transitive‚ ancetre sur personnes : irréflexive, transitive


Applications

Relations d’ordre

ñ Les relations peuvent ordonner les éléments d’un ensemble§ Types d’ordres

‚ Pré-ordre : relation réflexive et transitive‚ Équivalence : pré-ordre symétrique‚ Ordre : relation réflexive, anti-symétrique et transitive

‚ Ordre Total : @(x, y) P E2, x ‰ y Ñ xRy_ yRxñ Les éléments deux-à-deux sont toujours en relation‚ Ordre Partiel (treillis) : D(x, y)␣xRy^␣yRxñ Il existe des paires d’éléments sans relation‚ Arbre : @(x, y, z) P E3, xRy^ xRz^ x ‰ y ‰ z Ñ yRz_ zRy

§ Exemples‚ diviseur sur N : pré-ordre‚ dizaine, cousinade : équivalence‚ inclusion, sous-chaîne : ordre partiel‚ ď sur N : ordre total‚ Ordre alphabétique / lexicographique : ordre total


Applications

Exercices : morphismes et relations

§ Morphisme par concaténation‚ Soit L un langage basé sur un alphabet Σ de 26 lettres (a …z)‚ L’application de concaténation c() (telle que

c(ab, cd) = abcd) est-elle surjective ? Quelle contraintefaudrait-il ajouter pour qu’elle soit injective ?

‚ L’application t(α) qui compte le nombre de caractères d’unechaîne est-elle injective, surjective ?

‚ Nous transformons la concaténation comme opérateur “.”(point, tel que ab.cd = abcd)‚ Est-il associatif ? Commutatif ?‚ Pour quels opérateurs t est un morphisme de L dans N ?

‚ On définit la relation sub sur ce langage par le principe desous-chaîne : α sub β Ø Dγ, δ P L2, α = γ.β.δ‚ Quelles sont les propriétés de l’ordre ainsi défini ?‚ Quelle est le type de cet ordre ?‚ Dessinez le treillis pour Σ = ta, bu et tα P L, t(α) ď 3u


Documents

Logique et algèbre