Диаграмма Эйлера

Эта статья об эйлеровых кругах теории множеств и логики. Чтобы узнать о геометрическом круге Эйлера, см. Круг из девяти точек .

Диаграмма Эйлера, показывающая, что набор «животных с четырьмя ногами» является подмножеством «животных», но набор «минералов» не пересекается (не имеет общих членов) с «животными».

Диаграмма Эйлера, показывающая взаимосвязи между различными Солнечной системы. объектами

Диаграмма Эйлера ( / ˈ ɔɪ l ər / , OY -lər ) — это схематическое средство представления множеств и их отношений. Они особенно полезны для объяснения сложных иерархий и пересекающихся определений. Они похожи на другой метод построения диаграмм множеств — диаграммы Венна . В отличие от диаграмм Венна, которые показывают все возможные отношения между различными множествами, диаграмма Эйлера показывает только соответствующие отношения.

Первое использование «кругов Эйлера» обычно приписывают швейцарскому математику Леонарду Эйлеру (1707–1783). В Соединенных Штатах диаграммы Венна и Эйлера были включены в обучение теории множеств в рамках нового математического движения 1960-х годов. С тех пор они также были приняты в других областях учебной программы, таких как чтение. а также организации и предприятия.

Диаграммы Эйлера состоят из простых замкнутых фигур в двухмерной плоскости, каждая из которых изображает набор или категорию. То, как эти формы перекрываются, демонстрирует отношения между наборами. Каждая кривая делит плоскость на две области или «зоны»: внутреннюю, которая символически представляет элементы множества , и внешнюю, которая представляет все элементы, не являющиеся членами множества. Кривые, которые не перекрываются, представляют собой непересекающиеся множества , не имеющие общих элементов. Две перекрывающиеся кривые представляют собой пересекающиеся множества , имеющие общие элементы; зона внутри обеих кривых представляет собой совокупность элементов, общих для обоих множеств ( пересечение множеств). Кривая, полностью находящаяся внутри другой, является подмножеством ее .

Диаграммы Венна представляют собой более ограничительную форму диаграмм Эйлера. Диаграмма Венна должна содержать все 2 ^н логически возможные зоны перекрытия между n его кривыми, представляющие все комбинации включения/исключения составляющих его множеств. Области, не входящие в набор, обозначаются черным цветом, в отличие от диаграмм Эйлера, где членство в наборе обозначается как перекрытием, так и цветом.

История

Страница из «Лекций по логике» Гамильтона . Символы A , E , I и O относятся к четырем типам категорических утверждений, которые могут встречаться в силлогизме . (см. описания слева ) В небольшом тексте слева ошибочно говорится: «Первое использование круговых диаграмм в логике ошибочно приписывается Эйлеру. Его можно найти у Кристиана Вайзе», книги, на самом деле написанной Иоганном Кристианом Ланге.

Схема справа от Couturat. в котором он помечает 8 областей диаграммы Венна. Современное название этих «регионов» — минтермс . Они показаны на диаграмме с переменными x , y и z согласно рисунку Венна. Символика следующая: логическое И [ & ] представлено арифметическим умножением, а логическое НЕ [ ¬ ] представлено « ' » после переменной, например, область x ' y ' z читается как «( NOT x ) И ( НЕ y ) И z "т.е. (¬ x ) & (¬ y ) & z .

И диаграмма Вейча, и карта Карно показывают все минтермы , но для сокращения формул Вейтч не особенно полезен. Обратите внимание на сильное сходство между диаграммами Венна и Карно; цвета и переменные x , y и z соответствуют примеру Венна.

Как показано на иллюстрации справа, сэр Уильям Гамильтон ошибочно утверждал, что первоначальное использование кругов для «ощущения… абстракций логики» был не Эйлер (1707–1783), а скорее Вейзе (1642–1708); однако последняя книга на самом деле была написана Иоганном Кристианом Ланге, а не Вайзе. Он ссылается на «Письма Эйлера к немецкой принцессе» .

В иллюстрации Гамильтона к четырем категорическим суждениям которые могут встретиться в силлогизме , обозначенном рисунками A , E , I и O, таковы:

A : Универсальный утвердительный ответ

Пример: «Все металлы являются элементами».

E : Универсальный негатив.

Пример: «Никакие металлы не являются сложными веществами».

Я : Особое утвердительное утверждение

Пример: «Некоторые металлы хрупкие».

О : Особый негатив

Пример: «Некоторые металлы не хрупкие».

Венн (1834–1923) комментирует поразительную распространенность диаграммы Эйлера:

«...из первых шестидесяти логических трактатов, опубликованных в течение последнего столетия или около того, к которым обращались с этой целью – несколько случайно, поскольку они оказались наиболее доступными – оказалось, что тридцать четыре обратились к помощи диаграмм, почти все они используют схему Эйлера ».

Состоит из двух страниц из книги Венна (1881a) , стр. 115–116, показывающих его пример того, как преобразовать силлогизм из трех частей в его тип диаграммы. Венн называет эти круги «эйлеровыми кругами».

Но, тем не менее, он утверждал, что «неприменимость этой схемы для целей действительно общей логики» а затем заметил, что

«Оно вписывается, но плохо, даже в четыре положения общей логики, к которым оно обычно применяется».

Венн заканчивает свою главу наблюдением, проиллюстрированным в примерах ниже, — что их использование основано на практике и интуиции, а не на строгой алгоритмической практике:

«На самом деле... эти диаграммы не только не вписываются в обычную схему предложений, для иллюстрации которой они используются, но, по-видимому, не имеют какой-либо признанной схемы предложений, к которой их можно было бы последовательно отнести».

Наконец, в своей книге Венн переходит к решающей критике (выделена курсивом в цитате ниже); обратите внимание на иллюстрацию Гамильтона, что буквы O ( частный отрицательный ) и I ( частный утвердительный ) просто повернуты:

«Теперь мы подходим к известным кружкам Эйлера, которые впервые были описаны в его «Письмах к принцессе Аллеманской» ( Письма 102–105). Их слабое место состоит в том, что они лишь строго иллюстрируют действительные отношения классов друг к другу, а не несовершенное знание этих отношений, которым мы можем обладать или желать передать посредством предложения. Соответственно, они не согласуются с предложениями общей логики, а требуют образования новой группы соответствующих элементарных предложений. ... Этот недостаток, должно быть, был замечен с самого начала в случае частных утвердительных и отрицательных утверждений, поскольку одна и та же диаграмма обычно используется для обозначения их обоих, что она делает безразлично хорошо ». [курсив добавлен]

Как бы то ни было, вооружившись этими наблюдениями и критикой, Венн затем демонстрирует, как он вывел то, что стало известно как его диаграммы Венна, из «... старомодных диаграмм Эйлера». В частности, Венн приводит пример, показанный слева.

К 1914 году Кутюра (1868–1914) обозначил термины, как показано на рисунке справа. обозначил внешнюю область (показанную буквами « b » c ) Более того, он также . Он лаконично объясняет, как пользоваться диаграммой — нужно вычеркнуть области, которые должны исчезнуть:

«Метод Венна воплощен в геометрических диаграммах, которые представляют все составляющие, так что для получения результата нам нужно только вычеркнуть (заштриховав) те, которые исчезают из-за данных задачи». ]

Таким образом, учитывая назначения Венна, незаштрихованные области внутри кругов можно просуммировать, чтобы получить следующее уравнение для примера Венна:

« НЕТ y есть z и ВСЕ x есть y : поэтому x есть z » уравнение x'yz ' правильно + + x yz ' внутри x'y'z для незаштрихованной НЕТ ( но имеет области кругов это не совсем ; см. следующий абзац).

круги, не появляется: То есть термин, отмеченный «0», x'y'z У фон, окружающий Венна ' . Нигде это не обсуждается и не обозначается, но Кутюра исправляет это в своем рисунке. Правильное уравнение должно включать незаштрихованную область, выделенную жирным шрифтом:

« НЕТ y есть z и ВСЕ x есть y : НЕТ x есть z уравнение x'yz ' x'yz ​ + поэтому ​ x'y'z + ​ ' ​ x'y'z ​ + ​ ​ ​ ' . » имеет

В современном использовании диаграмма Венна включает в себя «коробку», окружающую все круги; это называется вселенной дискурса или областью дискурса .

Кутюр заметил, что прямым алгоритмическим (формальным, систематическим) способом невозможно вывести сокращенные булевы уравнения, а также не показано, как прийти к выводу « NO x is z ». Кутюра пришел к выводу, что этот процесс «имеет… серьезные неудобства как метод решения логических задач»:

«Он не показывает, как данные представляются путем исключения определенных составляющих, а также не показывает, как объединить оставшиеся составляющие, чтобы получить искомые последствия. Короче говоря, он служит только для демонстрации одного единственного шага в аргументации, а именно уравнение задачи; оно не обходится ни с предыдущими шагами, т. е. «сведением задачи в уравнение» и преобразованием посылок, ни с последующими шагами, т. е. комбинациями, приводящими к различным следствиям. Приносит очень мало пользы, поскольку составляющие могут быть представлены алгебраическими символами так же, как и плоские области, и с ними гораздо легче иметь дело в этой форме».

Таким образом, вопрос будет оставаться в силе до 1952 года, когда Морис Карно (1924–2022) адаптирует и расширит метод, предложенный Эдвардом В. Вейтчем ; эта работа будет опираться на метод таблицы истинности, точно определенный Эмилем Постом. и применение логики высказываний к логике переключения (среди прочих) Шенноном , Стибитцем и Тьюрингом . Например, Хилл и Петерсон (1968). представь диаграмму Венна с штриховкой и все такое. Они приводят примеры диаграмм Венна для решения задач с коммутационными цепями, но в итоге приходят к следующему утверждению:

«Для более чем трех переменных основная иллюстративная форма диаграммы Венна недостаточна. Однако возможны расширения, наиболее удобным из которых является карта Карно, которая будет обсуждаться в главе 6».

В главе 6, раздел 6.4 «Представление булевых функций картой Карно» они начинаются с:

«Карта Карно ¹ [ ¹ Karnaugh 1953] — один из самых мощных инструментов в арсенале разработчика логики. ... Карту Карно можно рассматривать либо как графическую форму таблицы истинности, либо как расширение диаграммы Венна».

История развития Карно его метода «диаграммы» или «карты» неясна. Цепочка цитат превращается в академическую игру «зачет, зачет; «кто получил признание?»: Карно (1953) ссылается на Вейча (1952) , Вейтч ссылается на Шеннона (1938) , и Шеннон (1938) , в свою очередь, ссылались (среди других авторов текстов по логике) на Кутюра (1914) . В методе Вейтча переменные располагаются в прямоугольнике или квадрате; Как описано в карте Карно , Карно в своем методе изменил порядок переменных, чтобы он соответствовал тому, что стало известно как (вершины) гиперкуба .

Эйлера и

Примеры небольших диаграмм Венна (слева) с заштрихованными областями, представляющими пустые множества , показывающие, как их можно легко преобразовать в эквивалентные диаграммы Эйлера (справа)

Диаграммы Венна представляют собой более ограничительную форму диаграмм Эйлера. Диаграмма Венна должна содержать все 2 ^н логически возможные зоны перекрытия между n его кривыми, представляющие все комбинации включения/исключения составляющих его множеств. Области, не входящие в набор, обозначаются черным цветом, в отличие от диаграмм Эйлера, где членство в наборе обозначается как перекрытием, так и цветом. Когда количество наборов превышает 3, диаграмма Венна становится визуально сложной, особенно по сравнению с соответствующей диаграммой Эйлера. Разницу между диаграммами Эйлера и Венна можно увидеть на следующем примере. Возьмите три комплекта:

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

Диаграммы Эйлера и Венна этих наборов:

• 
  Диаграмма Эйлера
• 
  Диаграмма друзей

В логической ситуации можно использовать теоретико-модельную семантику для интерпретации диаграмм Эйлера в рамках вселенной дискурса . В приведенных ниже примерах диаграмма Эйлера показывает, что множества Animal и Mineral не пересекаются, поскольку соответствующие кривые не пересекаются, а также что набор Four Legs является подмножеством множества Animal s. Диаграмма Венна, в которой используются одни и те же категории «Животное» , «Минерал » и «Четыре ноги» , не инкапсулирует эти отношения. Традиционно пустота множества на диаграммах Венна изображается штриховкой в ​​этой области. Диаграммы Эйлера представляют пустоту либо заштриховкой, либо отсутствием области.

Часто налагается набор условий правильности; это топологические или геометрические ограничения, налагаемые на структуру диаграммы. Например, можно обеспечить принудительное соединение зон или запретить совмещение кривых или нескольких точек, а также тангенциальное пересечение кривых. На соседней диаграмме примеры небольших диаграмм Венна преобразуются в диаграммы Эйлера с помощью последовательностей преобразований; некоторые из промежуточных диаграмм имеют совмещение кривых. Однако такое преобразование диаграммы Венна с штриховкой в ​​диаграмму Эйлера без штриховки не всегда возможно. Существуют примеры диаграмм Эйлера с 9 наборами, которые невозможно нарисовать с помощью простых замкнутых кривых без создания нежелательных зон, поскольку они должны были бы иметь неплоские двойственные графы.

Пример: диаграмма Эйлера-Венна и карта Карно

В этом примере показаны диаграммы Эйлера и Венна и карта Карно, позволяющие получить и проверить вывод «Никакие X не являются Z ».На иллюстрации и в таблице использованы следующие логические символы:

• 1 можно прочитать как «истина», 0 как «ложь».
• ~ для НЕ и сокращается до ' при иллюстрации минтермов, например, x' = _{определено} НЕ x,
• + для логического ИЛИ (из булевой алгебры : 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1)
• & (логическое И) между предложениями; в минтермах AND опускается аналогично арифметическому умножению: например, x'y'z = _{определено} ~x & ~y & z (Из булевой алгебры: 0⋅0 = 0, 0⋅1 = 1⋅0 = 0, 1⋅1 = 1, где для наглядности показано «⋅»)
• → (логическое ИМПЛИКАЦИЯ): читается как ЕСЛИ ... ТО ... или «ПОДРАЗУЕТСЯ», P → Q = _{определено} НЕ P ИЛИ Q.

Прежде чем его можно будет представить в виде диаграммы Венна или карты Карно, силлогизм диаграммы Эйлера «Нет Y есть Z , все X есть Y » необходимо сначала переформулировать на более формальный язык исчисления высказываний : «Это не тот случай, когда : Y И Z' И 'Если X , то Y' ». формулы Как только предложения сводятся к символам и формуле высказывания (~(y & z) & (x → y)), можно построить таблицу истинности ; из этой таблицы легко получить карту Венна и/или Карно. Используя смежность «1» на карте Карно (обозначенную серыми овалами вокруг членов 0 и 1 и вокруг членов 2 и 6), можно «сократить» логическое уравнение примера , т.е. (x'y'z' + x'y'z) + (x'yz' + xyz') всего к двум терминам: x'y' + yz'. Но из этого примера не вытекает средство вывода идеи о том, что «Нет X не есть Z», и то, как редукция связана с этим выводом.

Учитывая предложенный вывод, такой как «Ни один X не является Z », можно проверить, является ли этот вывод правильным, используя таблицу истинности . Самый простой метод - поместить исходную формулу слева (сокращенно P ), а (возможный) вывод справа (сокращенно Q ) и соединить их с помощью логической импликации , т. е. P → Q , читая как ЕСЛИ P ТО Вопрос . Если вычисление таблицы истинности дает все 1 под знаком импликации (→, так называемая мажорная связка ), то P → Q является тавтологией . Учитывая этот факт, можно «отсоединить» формулу справа (сокращенно Q ) способом, описанным ниже таблицы истинности.

Учитывая приведенный выше пример, формула диаграмм Эйлера и Венна выглядит следующим образом:

«Нет Y s являются Z s» и «Все X s являются Y s»: ( ~(y & z) & (x → y)) = _{определено} P

И предлагаемый вычет составляет:

«Нет X s не является Z s»: ( ~ (x & z)) = _{определено} Q

Итак, теперь вычисляемую формулу можно сократить до:

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

ЕСЛИ («Нет Y — это Z » и «Все X — это Y ») ТО («Нет X — это Z »)

Таблица истинности показывает, что формула ( ~(y & z) & (x → y)) → ( ~ (x & z)) является тавтологией, о чем свидетельствуют все единицы в желтом столбце.

Номер квадрата.	Венн, регион Карно		х	и	С		(~	(и	&	С)	&	(х	→	и))	→	(~	(х	&	С))
0	х'y'z'		0	0	0		1	0	0	0	1	0	1	0	1	1	0	0	0
1	х'у'з		0	0	1		1	0	0	1	1	0	1	0	1	1	0	0	1
2	х'yz'		0	1	0		1	1	0	0	1	0	1	1	1	1	0	0	0
3	х'yz		0	1	1		0	1	1	1	0	0	1	1	1	1	0	0	1
4	ху'з'		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	ксиз'		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

На этом этапе приведенная выше импликация P → Q (т. е. ~(y & z) & (x → y)) → ~(x & z) ) по-прежнему остается формулой, а вывод – «отделение» Q от P. → Q – не произошло. Но учитывая демонстрацию того, что P → Q является тавтологией, теперь подготовлена ​​почва для использования процедуры modus ponens для «отделения» Q: «Никакие X не являются Z » и отказа от терминов слева.

Modus ponens (или «фундаментальное правило вывода»). ) часто пишут следующим образом: два термина слева, P → Q и P , называются посылками (по соглашению, соединенными запятой), символ ⊢ означает «выходы» (в смысле логической дедукции), а член справа называется выводом :

П → Q , П ⊢ Q

Для успеха modus ponens обе посылки P → Q и P должны быть истинными . Поскольку, как показано выше, посылка P → Q является тавтологией, «истина» всегда имеет место, независимо от того, как оцениваются x, y и z, но «истина» имеет место только для P в тех обстоятельствах, когда P оценивается как « true» (например, строки 0 ИЛИ 1 ИЛИ 2 ИЛИ 6 : x'y'z' + x'y'z + x'yz' + xyz' = x'y' + yz').

П → Q , П ⊢ Q

• т.е.: ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) , ( ~ (y & z) & (x → y) ) ⊢ ( ~ (x & z) )
• т.е.: ЕСЛИ «Нет Y — это Z » и «Все X — это Y » ТО «Нет X — это Z », «Нет Y — это Z » и «Все X — это Y » ⊢ «Нет» Xs - это Zs "

Теперь можно «отделить» вывод «Никакие X не являются Z », возможно, чтобы использовать его в последующих выводах (или в качестве темы для разговора).

Использование тавтологической импликации означает, что существуют и другие возможные выводы, кроме «Ни один X не является Z »; Критерием успешного вывода является то, что единицы под большой связкой справа включают в себя все единицы под большой связкой слева ( главная связка является импликацией, приводящей к тавтологии). Например, в таблице истинности в правой части импликации (→, главный соединительный символ) в столбце, выделенном жирным шрифтом под главным символом связи « ~ », есть все те же единицы, которые появляются в жирном шрифте. столбец под левой подмажорной связкой & (строки 0 , 1 , 2 и 6 ) плюс еще две (строки 3 и 4 ).

Галерея

Кликабельная диаграмма Эйлера ^[файл] показывая отношения между различными многонациональными европейскими организациями и соглашениями

• 
  Диаграмма Венна показывает все возможные пересечения.
• 
  Диаграмма Эйлера, визуализирующая реальную ситуацию, взаимоотношения между различными наднациональными европейскими организациями . ( кликабельная версия )
• 
  Юмористическая диаграмма сравнения диаграмм Эйлера и Венна .
• 
  Диаграмма Эйлера типов треугольников , использующая определение, согласно которому равнобедренные треугольники имеют по крайней мере (а не ровно) 2 равные стороны.
• 
  Эйлеровая диаграмма терминологии Британских островов .
• 
  Диаграмма Эйлера, которая классифицирует различные типы метаэвристики .
• 
  Диаграмма Эйлера, показывающая связь между омографами, омофонами и синонимами.
• 
  22 (из 256) существенно разных диаграмм Венна с тремя кругами (вверху) и соответствующие им диаграммы Эйлера (внизу)
  Некоторые диаграммы Эйлера нетипичны, а некоторые даже эквивалентны диаграммам Венна. Области заштрихованы, чтобы указать, что они не содержат элементов.
• 
  Диаграмма взаимоотношений позвоночных животных Анри Милна-Эдвардса (1844 г.), иллюстрированная серией вложенных наборов.
• 
  Диаграмма Эйлера чисел до 100

См. также

• Интерсекциональность
• Радужная коробка
• Диаграмма паука - расширение диаграмм Эйлера, добавляющее существование пересечениям контуров.
• Модель трех кругов

Источники

• Кутюра, Луи (1914). Алгебра логики: авторизованный английский перевод Лидии Джиллингем Робинсон с предисловием Филиппа Э.Б. Журдена . Чикаго и Лондон: Издательская компания Open Court .
• Сэр Уильям Гамильтон (1860). Мансель, Генри Лонгвиль ; Вейч, Джон (ред.). Лекции по метафизике и логике . Эдинбург и Лондон: Уильям Блэквуд и сыновья .
• Джевонс, В. Стэнли (1880). Элементарные уроки логики: дедуктивная и индуктивная. С обильными вопросами и примерами, а также словарем логических терминов . Лондон и Нью-Йорк: MA MacMillan and Co.
• Карно, Морис (ноябрь 1953 г.) [23 апреля 1953 г., 17 марта 1953 г.]. «Метод карт для синтеза комбинационных логических схем» (PDF) . Труды Американского института инженеров-электриков, Часть I: Связь и электроника . 72 (5): 593–599. дои : 10.1109/TCE.1953.6371932 . S2CID   51636736 . Документ 53-217. Архивировано из оригинала (PDF) 16 апреля 2017 г. Проверено 16 апреля 2017 г.
• Сандифер, Эд (январь 2004 г.). «Как это сделал Эйлер» (PDF) . maa.org . Архивировано из оригинала (PDF) 26 января 2013 г.

• Вейч, Эдвард Уэстбрук (3 мая 1952 г.) [02 мая 1952 г.]. «Диаграммный метод для упрощения функций истинности». Протоколы ежегодного собрания ACM 1952 года . Ежегодная конференция/Ежегодное собрание ACM: материалы ежегодного собрания ACM 1952 года (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. дои : 10.1145/609784.609801 . S2CID   17284651 .

Дальнейшее чтение

По дате публикации:

• Альфред Норт Уайтхед и Бертран Рассел , 1913 г., 1-е издание, 1927 г., 2-е издание Principia Mathematica до *56 Cambridge At The University Press (издание 1962 г.), Великобритания, без ISBN.
• Эмиль Пост, 1921 г., «Введение в общую теорию элементарных предложений», перепечатано с комментариями Жана ван Хейеноорта в книге Жана ван Хейеноорта, редактор 1967 г. От Фреге до Гёделя: справочник по математической логике, 1879–1931 , издательство Гарвардского университета , Кембридж, Массачусетс. , ISBN   0-674-32449-8 (пбк.)
• Клод Э. Шеннон 1938 «Символический анализ релейных и коммутационных цепей», Труды Американского института инженеров-электриков , том 57, стр. 471–495. Взято из книги Клод Элвуд Шеннон: Сборник статей под редакцией NJA Солейн и Аарона Д. Винера, IEEE Press , Нью-Йорк.
• Ганс Райхенбах , 1947 г., «Элементы символической логики», переизданные в 1980 г. издательством Dover Publications, Inc. , Нью-Йорк, ISBN   0-486-24004-5 .
• Фредерик Дж. Хилл и Джеральд Р. Петерсон, 1968, 1974, « Введение в теорию переключения и логическое проектирование» , John Wiley & Sons , Нью-Йорк, ISBN   978-0-471-39882-0 .

Внешние ссылки

• Диаграммы Эйлера. Брайтон, Великобритания (2004 г.). Что такое диаграммы Эйлера?