diagrama de euler

Un diagrama de Euler ( / ˈ ɔɪ l ər / , OY -lər ) es un medio esquemático para representar conjuntos y sus relaciones. Son particularmente útiles para explicar jerarquías complejas y definiciones superpuestas. Son similares a otra técnica de diagramación de conjuntos, los diagramas de Venn . A diferencia de los diagramas de Venn, que muestran todas las relaciones posibles entre diferentes conjuntos, el diagrama de Euler muestra sólo relaciones relevantes.

El primer uso de "círculos eulerianos" se atribuye comúnmente al matemático suizo Leonhard Euler (1707-1783). En Estados Unidos, los diagramas de Venn y Euler se incorporaron como parte de la enseñanza de la teoría de conjuntos como parte del nuevo movimiento matemático de la década de 1960. Desde entonces, también han sido adoptados por otros campos curriculares como la lectura ^[1] , así como por organizaciones y empresas.

Los diagramas de Euler consisten en formas cerradas simples en un plano bidimensional y cada una representa un conjunto o categoría. Cómo o si estas formas se superponen demuestra las relaciones entre los conjuntos. Cada curva divide el plano en dos regiones o "zonas": la interior, que representa simbólicamente los elementos del conjunto, y la exterior, que representa todos los elementos que no son miembros del conjunto. Las curvas que no se superponen representan conjuntos disjuntos , que no tienen elementos en común. Dos curvas que se superponen representan conjuntos que se cruzan , que tienen elementos comunes; la zona dentro de ambas curvas representa el conjunto de elementos comunes a ambos conjuntos (la intersección de los conjuntos). Una curva completamente dentro del interior de otra es un subconjunto de ésta.

Historia

Como se muestra en la ilustración de la derecha, Sir William Hamilton en sus Lectures on Metaphysics and Logic (1858-1860), publicadas póstumamente, afirma erróneamente que el uso original de círculos para "sensualizar... las abstracciones de la lógica" (p. 180) No fue Leonhard Paul Euler (1707-1783) sino Christian Weise (1642-1708) en su Nucleus Logicae Weisianae que apareció póstumamente en 1712; sin embargo, este último libro en realidad fue escrito por Johann Christian Lange y no por Weise. ^[2]^[3] Hace referencia a las Cartas de Euler a una princesa alemana [Partie II, Lettre XXXV, 17 de febrero de 1791, ed. Cournot (1842), págs. 412–417. – ED.] ^{[nb 1]}

En la ilustración de Hamilton, las cuatro proposiciones categóricas que pueden aparecer en un silogismo simbolizado por los dibujos A, E, I y O son: ^[4]

R: El Afirmativo Universal , Ejemplo: “Todos los metales son elementos”.
E: El Negativo Universal , Ejemplo: “Ningún metal es sustancia compuesta”.
I: El Afirmativo Particular , Ejemplo: “Algunos metales son quebradizos”.
O: El Negativo Particular , Ejemplo: “Algunos metales no son quebradizos”.

En su Capítulo V de Lógica Simbólica de 1881 , "Representación diagramatica", John Venn (1834-1923) comenta sobre la notable prevalencia del diagrama de Euler:

"...de los primeros sesenta tratados de lógica, publicados durante el último siglo aproximadamente, que fueron consultados con este propósito: -un poco al azar, ya que resultaron ser los más accesibles:-pareció que treinta y cuatro apelaron a la ayuda de diagramas, casi todos ellos haciendo uso del Esquema Euleriano." (Nota al pie 1 página 100)

Sin embargo, sostuvo, "la inaplicabilidad de este esquema para los propósitos de una Lógica realmente general" (página 100) y en la página 101 observó que "encaja mal incluso con las cuatro proposiciones de la Lógica común a las que se refiere". normalmente se aplica." Venn termina su capítulo con la observación ilustrada en los ejemplos siguientes: que su uso se basa en la práctica y la intuición, no en una práctica algorítmica estricta:

"De hecho... esos diagramas no sólo no encajan con el esquema ordinario de proposiciones que se emplean para ilustrar, sino que no parecen tener ningún esquema reconocido de proposiciones al que puedan afiliarse consistentemente". (págs. 124 y 125)

Finalmente, en su Capítulo XX NOTAS HISTÓRICAS, Venn llega a una crítica crucial (en cursiva en la cita siguiente); observe en la ilustración de Hamilton que la O ( Particular Negativo ) y la I ( Particular Afirmativa ) simplemente se rotan:

"Llegamos ahora a los conocidos círculos de Euler, que fueron descritos por primera vez en sus Lettres a une Princesse d'Allemagne (Cartas 102-105). El punto débil de estos círculos consiste en el hecho de que sólo ilustran estrictamente las relaciones reales de clases. entre sí, en lugar del conocimiento imperfecto de estas relaciones que podemos poseer o desear transmitir por medio de la proposición. En consecuencia, no encajarán con las proposiciones de la lógica común, sino que exigirán la constitución de un nuevo grupo de proposiciones elementales apropiadas... Este defecto debe haber sido notado desde el principio en el caso de las afirmativas y negativas particulares, porque comúnmente se emplea el mismo diagrama para representar a ambas, lo cual lo hace indiferentemente bien ". (cursiva agregada: página 424)

(Sandifer 2003 informa que Euler también hace tales observaciones; Euler informa que su figura 45 (una simple intersección de dos círculos) tiene 4 interpretaciones diferentes). Cualquiera que sea el caso, armado con estas observaciones y críticas, Venn demuestra (págs. 100-125) cómo derivó lo que se conoce como sus diagramas de Venn a partir de los "... anticuados diagramas de Euler". En particular, da un ejemplo, el que se muestra a la izquierda.

En 1914, Louis Couturat (1868-1914) había etiquetado los términos como se muestra en el dibujo de la derecha. Además, también había etiquetado la región exterior (que se muestra como a'b'c'). Explica sucintamente cómo utilizar el diagrama: hay que tachar las regiones que van a desaparecer:

"El método de VENN se traduce en diagramas geométricos que representan todos los constituyentes, de modo que, para obtener el resultado, sólo necesitamos tachar (sombreando) aquellos que los datos del problema hacen desaparecer." (cursiva agregada p. 73)

Entonces, dadas las asignaciones de Venn, las áreas no sombreadas dentro de los círculos se pueden sumar para producir la siguiente ecuación para el ejemplo de Venn:

"Ningún Y es Z y TODO X es Y: por lo tanto, Ningún X es Z" tiene la ecuación x'yz' + xyz' + x'y'z para el área no sombreada dentro de los círculos (pero esto no es del todo correcto; consulte la siguiente párrafo).

En Venn, el término 0, x'y'z', es decir, el fondo que rodea los círculos, no aparece. En ninguna parte se comenta ni se etiqueta, pero Couturat lo corrige en su dibujo. La ecuación correcta debe incluir esta área sin sombrear que se muestra en negrita:

"Ningún Y es Z y TODO X es Y: por lo tanto, Ningún X es Z" tiene la ecuación x'yz' + xyz' + x'y'z + x'y'z' .

En el uso moderno, el diagrama de Venn incluye un "cuadro" que rodea todos los círculos; esto se llama universo del discurso o dominio del discurso .

Couturat ahora observa que, de manera algorítmica directa (formal, sistemática), no se pueden derivar ecuaciones booleanas reducidas, ni muestra cómo llegar a la conclusión "No X es Z". Couturat concluyó que el proceso "tiene... serios inconvenientes como método de resolución de problemas lógicos":

"No muestra cómo se exhiben los datos cancelando ciertos constituyentes, ni muestra cómo combinar los constituyentes restantes para obtener las consecuencias buscadas. En resumen, sólo sirve para exhibir un solo paso en el argumento, a saber, la ecuación del problema; no prescinde ni de los pasos anteriores, es decir, "lanzar el problema en una ecuación" y la transformación de las premisas, ni de los pasos posteriores, es decir, las combinaciones que conducen a las diversas consecuencias. es de muy poca utilidad, ya que los constituyentes pueden representarse tanto mediante símbolos algebraicos como mediante regiones planas, y son mucho más fáciles de tratar de esta forma." (p. 75)

Así la cuestión quedaría hasta 1952 cuando Maurice Karnaugh (1924-2022) adaptaría y ampliaría un método propuesto por Edward W. Veitch ; Este trabajo se basaría en el método de la tabla de verdad definido con precisión en la tesis doctoral de Emil Post de 1921 "Introducción a una teoría general de proposiciones elementales" y la aplicación de la lógica proposicional a la lógica de conmutación por (entre otros) Claude Shannon , George Stibitz y Alan Turing . ^{[nb 2]} Por ejemplo, en el capítulo "Álgebra booleana", Hill y Peterson (1968, 1964) presentan las secciones 4.5 y siguientes "La teoría de conjuntos como ejemplo de álgebra booleana", y en ella presentan el diagrama de Venn con sombreado y todo. Dan ejemplos de diagramas de Venn para resolver problemas de circuitos de conmutación, pero terminan con esta afirmación:

"Para más de tres variables, la forma ilustrativa básica del diagrama de Venn es inadecuada. Sin embargo, son posibles extensiones, la más conveniente de las cuales es el mapa de Karnaugh, que se discutirá en el Capítulo 6". (pág. 64)

En el Capítulo 6, sección 6.4 "Representación del mapa de Karnaugh de funciones booleanas" comienzan con:

"El mapa de Karnaugh ¹ [ ¹ Karnaugh 1953] es una de las herramientas más poderosas en el repertorio del diseñador lógico... Un mapa de Karnaugh puede considerarse como una forma pictórica de una tabla de verdad o como una extensión de la tabla de Venn. diagrama." (págs. 103 y 104)

La historia del desarrollo por parte de Karnaugh de su método de "gráfico" o "mapa" es oscura. Karnaugh en su 1953 hizo referencia a Veitch 1951, Veitch hizo referencia a Claude E. Shannon 1938 (esencialmente la tesis de maestría de Shannon en el MIT ), y Shannon a su vez hizo referencia, entre otros autores de textos de lógica, a Couturat 1914. En el método de Veitch las variables están dispuestas en un rectángulo o cuadrado; Como se describe en el mapa de Karnaugh , Karnaugh en su método cambió el orden de las variables para corresponder a lo que se conoce como (los vértices de) un hipercubo .

Relación entre los diagramas de Euler y Venn

Ejemplos de diagramas de Venn pequeños *(a la izquierda)* con regiones sombreadas que representan conjuntos vacíos , que muestran cómo se pueden transformar fácilmente en diagramas de Euler equivalentes *(derecha)*

Los diagramas de Venn son una forma más restrictiva de los diagramas de Euler. Un diagrama de Venn debe contener las 2 ⁿ zonas de superposición lógicamente posibles entre sus n curvas, que representen todas las combinaciones de inclusión/exclusión de sus conjuntos constituyentes. Las regiones que no forman parte del conjunto se indican coloreándolas de negro, a diferencia de los diagramas de Euler, donde la pertenencia al conjunto se indica tanto por superposición como por color. Cuando el número de conjuntos supera los 3, un diagrama de Venn se vuelve visualmente complejo, especialmente en comparación con el diagrama de Euler correspondiente. La diferencia entre los diagramas de Euler y Venn se puede ver en el siguiente ejemplo. Tome los tres conjuntos:

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

Los diagramas de Euler y Venn de esos conjuntos son:

diagrama de euler
diagrama de Venn

En un entorno lógico, se puede utilizar la semántica de la teoría de modelos para interpretar los diagramas de Euler, dentro de un universo de discurso . En los ejemplos siguientes, el diagrama de Euler muestra que los conjuntos Animal y Mineral son disjuntos ya que las curvas correspondientes son disjuntas, y también que el conjunto Cuatro Patas es un subconjunto del conjunto de Animales s. El diagrama de Venn, que utiliza las mismas categorías de Animal , Mineral y Cuatro Patas , no resume estas relaciones. Tradicionalmente, el vacío de un conjunto en los diagramas de Venn se representa mediante sombreado en la región. Los diagramas de Euler representan el vacío ya sea por sombreado o por la ausencia de una región.

A menudo se impone un conjunto de condiciones de buena formación; Estas son restricciones topológicas o geométricas impuestas a la estructura del diagrama. Por ejemplo, se podría imponer la conexión de zonas, o se podría prohibir la concurrencia de curvas o puntos múltiples, al igual que la intersección tangencial de curvas. En el diagrama adyacente, ejemplos de pequeños diagramas de Venn se transforman en diagramas de Euler mediante secuencias de transformaciones; algunos de los diagramas intermedios tienen concurrencia de curvas. Sin embargo, este tipo de transformación de un diagrama de Venn con sombreado en un diagrama de Euler sin sombreado no siempre es posible. Hay ejemplos de diagramas de Euler con 9 conjuntos que no se pueden dibujar usando curvas cerradas simples sin la creación de zonas no deseadas, ya que tendrían que tener gráficos duales no planos.

Ejemplo: diagrama de Euler a Venn y mapa de Karnaugh

Este ejemplo muestra los diagramas de Euler y Venn y el mapa de Karnaugh derivando y verificando la deducción "Ningún X es Z ". En la ilustración y la tabla se utilizan los siguientes símbolos lógicos:

1 se puede leer como "verdadero", 0 como "falso"
~ para NOT y abreviado como 'al ilustrar los términos mínimos, por ejemplo, x' = _definido NOT x,
+ para OR booleano (del álgebra booleana : 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1)
& (Y lógico) entre proposiciones; en los minitérminos AND se omite de una manera similar a la multiplicación aritmética: por ejemplo, x'y'z = _definido ~x & ~y & z (Del álgebra booleana: 0·0 = 0, 0·1 = 1·0 = 0, 1·1 = 1, donde "·" se muestra para mayor claridad)
→ (IMLICACIÓN lógica): leído como SI... ENTONCES..., o "IMPLICA", P → Q = _definido NO P O Q

Dada una conclusión propuesta como "Ningún X es una Z ", se puede comprobar si es una deducción correcta o no mediante el uso de una tabla de verdad . El método más sencillo es poner la fórmula inicial a la izquierda (abreviarla como P ) y poner la (posible) deducción a la derecha (abreviarla como Q ) y conectar las dos con implicaciones lógicas , es decir, P → Q , leídas como IF P THEN P. _ Si la evaluación de la tabla de verdad produce todos unos bajo el signo de implicación (→, el llamado conectivo mayor ), entonces P → Q es una tautología . Dado este hecho, se puede "separar" la fórmula de la derecha (abreviada como Q ) de la manera que se describe debajo de la tabla de verdad.

Dado el ejemplo anterior, la fórmula para los diagramas de Euler y Venn es:

"Ningún Y es Z " y "Todos los X son Y ": ( ~(y & z) & (x → y) ) = _definido P

Y la deducción propuesta es:

"No hay X s son Z s": ( ~ (x & z) ) = Q _definido

Entonces ahora la fórmula a evaluar se puede abreviar a:

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

IF ("Ningún Y es Z " y "Todos los X son Y ") ENTONCES ("Ningún X es Z ")

En este punto, la implicación anterior P → Q (es decir ~(y & z) & (x → y) ) → ~(x & z) ) sigue siendo una fórmula, y la deducción – el "desapego" de Q de P → Q – no ha ocurrido. Pero dada la demostración de que P → Q es tautología, el escenario está ahora preparado para el uso del procedimiento de modus ponens para "separar" Q: "Ningún X s es Z s" y prescindir de los términos de la izquierda. ^{[nota 3]}

Modus ponens (o "la regla fundamental de inferencia" ^[5] ) a menudo se escribe de la siguiente manera: Los dos términos de la izquierda, P → Q y P , se llaman premisas (por convención unidos por una coma), el símbolo ⊢ significa "cede" (en el sentido de deducción lógica), y el término de la derecha se llama conclusión :

P → Q , P ⊢Q _

Para que el modus ponens tenga éxito, ambas premisas P → Q y P deben ser verdaderas . Porque, como se demostró anteriormente, la premisa P → Q es una tautología, la "verdad" siempre es el caso sin importar cómo se valoren x, y y z, pero la "verdad" sólo es el caso para P en aquellas circunstancias en las que P se evalúa como " verdadero" (por ejemplo, filas 0 O 1 O 2 O 6 : x'y'z' + x'y'z + x'yz' + xyz' = x'y' + yz'). ^{[nota 4]}

P → Q , P ⊢Q _

es decir: ( ~(y & z) & (x → y) ) → ( ~ (x & z) ), ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) )
es decir: SI "Ningún Y es Z " y "Todos los X son Y " ENTONCES "Ningún X es Z ", "Ningún Y es Z " y "Todos los X son Y " ⊢ "No X son Z "

Ahora uno es libre de "separar" la conclusión "Ningún X es Z ", tal vez para utilizarla en una deducción posterior (o como tema de conversación).

El uso de implicaciones tautológicas significa que existen otras posibles deducciones además de "Ningún X es Z "; El criterio para una deducción exitosa es que los 1 bajo el conectivo submayor de la derecha incluyan todos los 1 bajo el conectivo submayor de la izquierda (siendo el conectivo mayor la implicación que da como resultado la tautología). Por ejemplo, en la tabla de verdad, en el lado derecho de la implicación (→, el símbolo conectivo mayor), la columna en negrita debajo del símbolo conectivo submayor " ~ " tiene los mismos unos que aparecen en negrita. columna debajo del conectivo submayor del lado izquierdo & (filas 0 , 1 , 2 y 6 ), más dos más (filas 3 y 4 ).

Galería

Un diagrama de Euler ^[archivo] en el que se puede hacer clic que muestra las relaciones entre varias organizaciones y acuerdos multinacionales europeos

Un diagrama de Venn muestra todas las intersecciones posibles.
Diagrama de Euler que visualiza una situación real, las relaciones entre diversas organizaciones supranacionales europeas . ( versión en la que se puede hacer clic )
Diagrama humorístico que compara los diagramas de Euler y Venn .
Diagrama de Euler de tipos de triángulos , utilizando la definición de que los triángulos isósceles tienen al menos (en lugar de exactamente) 2 lados iguales.
Diagrama de Euler de terminología de las Islas Británicas .
Un diagrama de Euler que categoriza diferentes tipos de metaheurísticas .
Un diagrama de Euler que muestra la relación entre homógrafos, homófonos y sinónimos.
Los 22 (de 256) diagramas de Venn esencialmente diferentes con 3 círculos (arriba) y sus correspondientes diagramas de Euler (abajo)
Algunos de los diagramas de Euler no son típicos y algunos incluso son equivalentes a los diagramas de Venn. Las áreas están sombreadas para indicar que no contienen elementos.
Diagrama de relaciones entre animales vertebrados de Henri Milne-Edwards (1844), ilustrado como una serie de conjuntos anidados.

Ver también

Interseccionalidad
caja arcoiris
Diagrama de araña : una extensión de los diagramas de Euler que agrega existencia a las intersecciones de contornos
Modelo de tres círculos.

Notas

^ Cuando se publicaron estas conferencias de Hamilton, Hamilton también había muerto. Sus editores (simbolizados por ED.), responsables de la mayoría de las notas a pie de página, fueron los lógicos Henry Longueville Mansel y John Veitch .
^ Véase nota a pie de página en George Stibitz .
^ Este es un concepto sofisticado. Russell y Whitehead (2ª edición, 1927) en sus Principia Mathematica lo describen de esta manera: "La confianza en la inferencia es la creencia de que si las dos afirmaciones anteriores [las premisas P, P→Q] no son erróneas, la afirmación final no es errónea". en error... Una inferencia es la eliminación de una premisa verdadera [sic]; es la disolución de una implicación" (p. 9). Una discusión más detallada sobre esto aparece en "Ideas y proposiciones primitivas" como la primera de sus "proposiciones primitivas" (axiomas): *1.1 Cualquier cosa implícita en una proposición elemental verdadera es verdadera" (p. 94). En una nota a pie de página, los autores hacen referencia a la El lector vuelve a los Principios de Matemáticas de Russell de 1903 , §38.
^ Reichenbach analiza el hecho de que la implicación P → Q no tiene por qué ser una tautología (la llamada "implicación tautológica"). Incluso la implicación "simple" (conectiva o adjunta) funciona, pero sólo para aquellas filas de la tabla de verdad que se evalúan como verdaderas, cf. Reichenbach 1947:64-66.

Referencias

^ "Estrategias para la comprensión lectora de diagramas de Venn". Archivado desde el original el 29 de abril de 2009 . Consultado el 20 de junio de 2009 .
^ ab Venn, John (1881). Lógica simbólica. Londres: MacMillan and Co. p. 509.
^ ab Mac Queen, Gailand (octubre de 1967). El diagrama lógico (PDF) (Tesis). Universidad McMaster . pag. 5. Archivado desde el original (PDF) el 14 de abril de 2017 . Consultado el 14 de abril de 2017 .(NB. Tiene una historia detallada de la evolución de los diagramas lógicos, incluido, entre otros, el diagrama de Euler).
^ Hamilton 1860:179. Los ejemplos son de Jevons 1881:71ff.
^ cf. Reichenbach 1947:64

Otras lecturas

Por fecha de publicación:

Sir William Hamilton 1860 Lectures on Metaphysics and Logic editadas por Henry Longueville Mansel y John Veitch , William Blackwood and Sons , Edimburgo y Londres.
W. Stanley Jevons 1880 Lecciones elementales de lógica: deductiva e inductiva. Con abundantes preguntas y ejemplos, y un vocabulario de términos lógicos , MA MacMillan and Co. , Londres y Nueva York.
Alfred North Whitehead y Bertrand Russell 1913 1.ª edición, 1927 2.ª edición Principia Mathematica hasta *56 Cambridge At The University Press (edición de 1962), Reino Unido, sin ISBN.
Louis Couturat 1914 El álgebra de la lógica: traducción autorizada al inglés de Lydia Gillingham Robinson con prefacio de Philip EB Jourdain , The Open Court Publishing Company , Chicago y Londres.
Emil Post 1921 "Introducción a una teoría general de proposiciones elementales" reimpreso con comentario de Jean van Heijenoort en Jean van Heijenoort, editor 1967 De Frege a Gödel: un libro de consulta de lógica matemática, 1879-1931 , Harvard University Press , Cambridge, MA , ISBN 0-674-32449-8 (pbk.)
Claude E. Shannon 1938 "Un análisis simbólico de circuitos de conmutación y relés", Transactions American Institute of Electrical Engineers vol 57, págs. Derivado de Claude Elwood Shannon: Collected Papers editado por NJA Solane y Aaron D. Wyner, IEEE Press , Nueva York.
Hans Reichenbach 1947 Elementos de lógica simbólica republicado en 1980 por Dover Publications, Inc. , Nueva York, ISBN 0-486-24004-5 .
Veitch, Edward Westbrook (3 de mayo de 1952) [2 de mayo de 1952]. "Un método gráfico para simplificar funciones de verdad". Transacciones de la reunión anual de la ACM de 1952 . Conferencia anual/Reunión anual de la ACM: Actas de la reunión anual de la ACM de 1952 (Pittsburgh, Pensilvania, EE. UU.). Nueva York, EE.UU.: Asociación de Maquinaria de Computación (ACM): 127–133. doi :10.1145/609784.609801. S2CID 17284651.
Karnaugh, Maurice (noviembre de 1953) [23 de abril de 1953, 17 de marzo de 1953]. "El método de mapas para la síntesis de circuitos lógicos combinacionales" (PDF) . Transacciones del Instituto Americano de Ingenieros Eléctricos, Parte I: Comunicaciones y Electrónica . 72 (5): 593–599. doi :10.1109/TCE.1953.6371932. S2CID 51636736. Documento 53-217. Archivado desde el original (PDF) el 16 de abril de 2017 . Consultado el 16 de abril de 2017 .
Frederich J. Hill y Gerald R. Peterson 1968, 1974 Introducción a la teoría de la conmutación y al diseño lógico , John Wiley & Sons , Nueva York, ISBN 978-0-471-39882-0 .
Sandifer, Ed (enero de 2004). "Cómo lo hizo Euler" (PDF) . maa.org . Archivado desde el original (PDF) el 26 de enero de 2013.

enlaces externos

Wikimedia Commons tiene medios relacionados con los diagramas de Euler .

Diagramas de Euler. Brighton, Reino Unido (2004). ¿Qué son los diagramas de Euler?