Diagramme d'Euler

Un diagramme d'Euler illustrant que l'ensemble des « animaux à quatre pattes » est un sous-ensemble des « animaux », mais l'ensemble des « minéraux » est disjoint (il n'a pas de membres en commun) avec « animaux ».

Un diagramme d'Euler est un moyen de représentation diagrammatique des ensembles et des relations en leur sein. La première utilisation des « cercles Eulériens » est communément attribuée au mathématicien suisse Leonhard Euler (1707-1783). Ils sont étroitement liés aux diagrammes de Venn, mathématicien britannique (1834–1923).

Les diagrammes de Venn et d'Euler ont été incorporés à l'enseignement de la théorie des ensembles dans le cadre des mathématiques modernes dans les années 1960. Depuis lors, ils ont également été adoptés dans d'autres domaines du programme d'études tels que la lecture.

Aperçu

Les 22 (des 256) diagrammes de Venn essentiellement différents avec 3 cercles (en haut) et leurs diagrammes d'Euler correspondant (en bas).
Certains des diagrammes d'Euler ne sont pas caractéristiques, et certains sont même équivalents aux diagrammes de Venn. Les zones sont ombrées pour indiquer qu'elles ne contiennent aucun élément.

Les diagrammes d'Euler sont constitués de simples courbes fermées (habituellement des cercles) dans le plan qui représentent les ensembles. Les tailles ou formes des courbes ne sont pas importantes : la signification du diagramme est dans la façon dont les cercles se chevauchent. Les relations spatiales entre les régions délimitées par chaque courbe correspondent aux relations théoriques à ensembles (intersection, sous-ensembles et disjonction).

Chaque courbe d'Euler divise le plan en deux régions ou « zones » : l'intérieur, ce qui représente symboliquement les éléments contenus dans l'ensemble, et l'extérieur, qui représente tous les éléments qui ne sont pas membres de l'ensemble. Les courbes dont les zones intérieures ne se coupent pas représentent des ensembles disjoints. Deux courbes dont les zones intérieures se croisent représentent des ensembles qui ont des éléments communs ; la zone à l'intérieur de deux courbes représente l'ensemble des éléments communs aux deux ensembles (l'intersection des ensembles). Une courbe qui est entièrement contenue à l'intérieur de la zone intérieure d'une autre représente un sous-ensemble de celle-ci.

Exemples de petits diagrammes de Venn (à gauche) avec les régions ombragées représentant des ensembles vides, montrant comment ils peuvent être facilement transformés en diagrammes d'Euler (à droite).

Les diagrammes de Venn sont une forme plus restrictive des diagrammes d'Euler. Un diagramme de Venn doit contenir 2ⁿ zones possibles correspondant au nombre de combinaisons d'inclusion ou d'exclusion dans chacun des ensembles. Les régions qui ne font pas partie de l'ensemble sont indiqués par la couleur noir, contrairement aux diagrammes d'Euler, où l'appartenance à l'ensemble est indiquée par le chevauchement ainsi que la couleur. Lorsque le nombre d'ensembles devient supérieur à 3, un diagramme de Venn devient visuellement complexe, en particulier par rapport au diagramme d'Euler correspondant. La différence entre les diagrammes de Venn et d'Euler peut être vue dans l'exemple suivant. Soit trois ensembles :

• $A=\{1,2,5\}$
• $B=\{1,6\}$
• $C=\{4,7\}$

Les diagrammes de Venn et d'Euler de ces ensembles sont :

• 
  Diagramme d'Euler
• 
  Diagramme de Venn

Dans un cadre logique, on peut utiliser la sémantique théorique pour interpréter les diagrammes d'Euler, dans un univers du discours. Dans les exemples ci-dessus, le diagramme d'Euler montre que les ensembles Animal et Minéral sont disjoints puisque les courbes correspondantes sont disjointes, et que l'ensemble Quatre Pattes est un sous-ensemble de l'ensemble des Animal. Le diagramme de Venn, qui utilise les mêmes catégories Animal, Minéral, et Quatre Pattes, n'inclut pas ces relations. Traditionnellement le vide d'un ensemble dans un diagrammes de Venn est représenté par l'ombrage de la région concernée. Les diagrammes d'Euler représentent le vide, soit par l'ombrage, soit par l'absence de la région.

Histoire

Sir William Hamilton, dans son livre publié à titre posthume Lectures on Metaphysic and Logic (1858-1860) affirme que l'utilisation des cercles dans le but de Modèle:Citation (Modèle:P.) ne venait pas de Leonhard Paul Euler (1707-1783), mais plutôt de Modèle:Lien (1642-1708) dans son Nucleus Logicae Weisianae qui est paru en 1712 à titre posthume. Il fait référence à des lettres d'Euler à une princesse allemande [Partie ii., Lettre XXXV., Éd. Cournot. - ED].

Dans Symbolic Logic de 1881, au chapitre V (« Représentation diagrammatique »), John Venn commente sur la prévalence remarquable du diagramme d'Euler : Modèle:Citation bloc Néanmoins, il a soutenu Modèle:Citation (Modèle:P.). Venn termine son chapitre avec l'observation illustrée dans les exemples ci-dessous, que leur utilisation est basée sur la pratique et l'intuition, non pas sur une pratique algorithmique stricte : Modèle:Citation bloc

Dans l'usage moderne, le diagramme de Venn comprend une « boîte » qui entoure tous les cercles et représente l'univers du discours.

Couturat observe maintenant que, dans une algorithmique (systématique formelle) de manière directe, on ne peut pas tirer d'équations booléennes réduites, ni de démonstration à la conclusion « Aucun X n'est Z ». Couturat a conclu que le processus Modèle:Citation : Modèle:Citation bloc En 1952, Maurice Karnaugh adapte et développe une méthode proposée par Modèle:Lien ; ce travail se fonde sur la méthode des tables de vérité précisément définies en 1921 dans la thèse d'Emil Post Introduction à une théorie générale des propositions élémentaires et l'application de la logique propositionnelle à la logique des circuits par (entre autres) Claude Shannon, Modèle:Lien et Alan Turing. Par exemple, dans le chapitre « Boolean Algebra », Hill et Peterson (1968, 1964) Modèle:Pas clair 4.5ff « théorie des ensembles comme un exemple de l'algèbre de Boole » et Modèle:Pas clair, ils présentent le diagramme de Venn avec l'ombrage. Ils donnent des exemples de diagrammes de Venn pour résoudre, par exemple, des problèmes de circuit, mais finissent avec cette déclaration : Modèle:Citation bloc Dans le chapitre 6, section 6.4 (« Karnaugh Map Representation of Boolean Functions »), ils commencent par : Modèle:Citation bloc L'histoire du développement par Karnaugh de sa table est obscure. Karnaugh, dans son article de 1953, référence Modèle:Refsou, Veitch référence Shannon 1938 (essentiellement la thèse de master de Shannon au Modèle:Nobr et Shannon à son tour renvoie, entre autres auteurs de textes logiques, à Couturat 1914. Dans la méthode de Veitch, les variables sont disposées dans un rectangle ou un carré ; comme décrit dans la table de Karnaugh, Karnaugh a changé l'ordre des variables dans sa méthode pour correspondre à ce qui est maintenant connu sous le nom d'hypercube.

Exemple : diagramme d'Euler à Venn et table de Karnaugh

Cet exemple montre les diagrammes d'Euler de Venn et de Karnaugh vérifier la déduction « aucun X n'est Z ». Dans le tableau ci-dessous, les symboles logiques suivants sont utilisés :

1 peut être lu comme « vrai », 0 comme « faux » ;

~ pour NON et abrégé en '. Par exemple x' =_défini NON x ;

+ pour le OU logique (de l'algèbre de Boole : 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1) ;

& (ET logique) entre propositions ; il est parfois omis de la même manière que le signe de la multiplication : par exemple x'y'z =_défini ~x & ~y & z (de l'algèbre de Boole : 0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 = 1, où * figure pour plus de clarté) ;

→ (IMPLICATION logique) : à lire SI... ALORS..., ou « IMPLIQUE », P → Q =_défini NON P OU Q.

Compte tenu de la conclusion proposée comme « Aucun X n'est Z », on peut tester si une déduction est correcte par l'utilisation d'une table de vérité. La méthode la plus simple est de mettre la formule à gauche (abrégez "P") et mettre la déduction (possible) sur la droite (abrégez "Q") et les connecter grâce à l'implication logique, à savoir P → Q, lu comme SI P ALORS Q. Si l'évaluation de la table de vérité ne produit que des 1 sous le signe de l'implication alors P → Q est une tautologie. Étant donné ce fait, on peut « détacher » la formule de droite de la manière décrite sous la table de vérité.

Compte tenu de l'exemple ci-dessus, la formule pour les diagrammes d'Euler et de Venn est :

« Aucun Y n'est Z » et « Tout X est Y » : ( ~(y & z) & (x → y) ) =_défini P

et la déduction proposée est :

« Aucun X n'est Z » : ( ~ (x & z) ) =_défini Q

Alors maintenant, la formule à évaluer peut être abrégée :

( ~(y & z) & (x → y) ) → ( ~ (x & z) ): P → Q

SI (« Aucun Y n'est Z » et « Tout X est Y ») ALORS (« Aucun X n'est Z »).

La table de vérité montre que la formule ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) est une tautologie, comme indiqué par tous les 1 sur la colonne jaune

#	Venn, Karnaugh	x	y	z	(~	(y	&	z)	&	(x	→	y))	→	(~	(x	&	z))
0	x'y'z'	0	0	0	1	0	0	0	1	0	1	0	1	1	0	0	0
1	x'y'z	0	0	1	1	0	0	1	1	0	1	0	1	1	0	0	1
2	x'yz'	0	1	0	1	1	0	0	1	0	1	1	1	1	0	0	0
3	x'yz	0	1	1	0	1	1	1	0	0	1	1	1	1	0	0	1
4	xy'z'	1	0	0	1	0	0	0	0	1	0	0	1	1	1	0	0
5	xy'z	1	0	1	1	0	0	1	0	1	0	0	1	0	1	1	1
6	xyz'	1	1	0	1	1	0	0	1	1	1	1	1	1	1	0	0
7	xyz	1	1	1	0	1	1	1	0	1	1	1	1	0	1	1	1

À ce stade, l'implication ci-dessus P → Q (~(y & z) & (x → y) ) → ~(x & z) ) est encore une formule, et la déduction – le « détachement » de Q de P → Q – n'a pas eu lieu. Mais étant donné la démonstration selon laquelle P → Q est une tautologie, l'étape suivante est la procédure du modus ponens afin de « détacher » Q : « Aucun X n'est Z » et de distribuer les termes sur la gauche.

Le Modus ponens (ou Modèle:Citation) est souvent noté comme suit : les deux termes sur la gauche, « P → Q » et « P », sont appelés prémisses (par convention liées par une virgule), le symbole ⊢ signifie « prouve » (dans le sens de la déduction logique), et le terme de droite est appelée la conclusion :

P → Q, P ⊢ Q.

Pour que le modus ponens réussisse, les deux prémisses P → Q et P doivent être vraies. Parce que, comme l'a démontré ci-dessus, le prémisse P → Q est une tautologie, la « vérité » est toujours le cas, peu importe les valeurs que prennent x, y et z, mais la « vérité » ne sera le cas pour P dans ces circonstances que lorsque P sera évalué « vrai » (par exemple les colonnes 0 OU 1 OU 2 OU 6 : x'y'z' + x'y'z + x'yz' + xyz' = x'y' + yz').

P → Q , P ⊢ Q

c'est-à-dire : ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) , ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) )

c'est-à-dire : SI « Aucun Y n'est Z » et « Tout X est Y » ALORS « Aucun X n'est Z » (« Aucun Y n'est Z » et « Tout X est Y » ⊢ « Aucun X n'est Z »).

On est maintenant libre de « détacher » la conclusion « Aucun X n'est Z », qui peut être utilisée dans une déduction ultérieure.

L'utilisation de l'implication tautologique signifie que d'autres déductions possibles existent en plus de « Aucun X n'est Z ».

Galerie

• 
  Diagramme de Venn montrant toutes les intersections possibles.
• 
  Diagramme d'Euler représentant une situation réelle, à savoir les relations entre les différentes organisations européennes supranationales. (Version cliquable)
• 
  Diagramme humoristique comparant les diagrammes d'Euler et de Venn.
• 
  Diagramme d'Euler des types de triangles.

Voir aussi

Articles connexes

• Diagramme de Venn
• Diagramme de Carroll
• Syllogisme

Bibliographie

Classée par date de publication :

• Sir William Hamilton 1860 Lectures on Metaphysics and Logic édité par Modèle:Lien et Modèle:Lien, William Blackwood and Sons, Edinburgh et Londres.
• W. Stanley Jevons 1880 Elementary Lessons in Logic: Deductive and Inductive. With Copious Questions and Examples, and a Vocabulary of Logical Terms, M. A. MacMillan et Co., Londres et New York.
• John Venn 1881 Symbolic Logic, MacMillan et Co., Londres.
• Alfred North Whitehead et Bertrand Russell 1913 Modèle:1e, 1927 Modèle:2e, Principia Mathematica to *56, Cambridge University Press (éd. de 1962).
• Louis Couturat 1914 The Algebra of Logic: Authorized English Translation by Lydia Gillingham Robinson with a Preface by Philip E. B. Jourdain, The Open Court Publishing Company, Chicago et Londres.
• Emil Post 1921 "Introduction to a general theory of elementary propositions" réimprimé et commenté par Jean van Heijenoort, 1967, From Frege to Gödel: A Source Book of Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA Modèle:ISBN (pbk.)
• Claude E. Shannon 1938 "A Symbolic Analysis of Relay and Switching Circuits", Transactions American Institute of Electrical Engineers, vol. 57, Modèle:P.. Dérivé de Claude Elwood Shannon: Collected Papers édité par N.J.A. Solane et Aaron D. Wyner, IEEE Press, New York.
• Hans Reichenbach 1947 Elements of Symbolic Logic republié 1980 par Dover Publications, NY Modèle:ISBN.
• Edward W. Veitch (1952) « A Chart Method for Simplifying Truth Functions », Transactions of the 1952 ACM Annual Meeting "Pittsburgh", ACM, NY, Modèle:P..
• Maurice Karnaugh (novembre 1953) « The Map Method for Synthesis of Combinational Logic Circuits », AIEE Committee on Technical Operations for Presentation at the AIEE Summer General Meeting, Atlantic City, N. J., June 15–19, 1953, Modèle:P..
• Frederich J. Hill et Gerald R. Peterson 1968, 1974 Introduction to Switching Theory and Logical Design, John Wiley & Sons, NY Modèle:ISBN.
• Modèle:Lien brisé

Liens externes

• Modèle:Lien web
• Modèle:Lien web
• Modèle:Lien web
• Modèle:Lien web
• Brighton, UK (2004) Modèle:Lien web
• Modèle:Lien web